Cannot implement Mutex correctly

Question

I am trying to implement a Mutex WITHOUT busy-waiting. Basically, if a thread wants the lock, it checks to see if the Mutex is already locked, if so, put the thread to sleep and add it to a FIFO queue. When the thread holding the lock goes to unlock the Mutex, it checks to see if any threads are waiting to gain access to the critical region, if so, remove the thread from the queue and add it to a 'ready' queue which controls the order of the threads being used.

I cannot get the Mutex to work, but the Semaphore below it works fine. Any ideas? Thanks.

// DOESN'T WORK

class Mutex {

    Thread * thisThread;
    Thread * threadWithLock;

     lock() {
         // disable interrupts
         interrupts.disable();

         // if no-one has lock, give lock to the current thread and set the lock
         // else put the thread to sleep and add it to the waiting thread queue
         if (lockStatus == 0) {
             lock = 1
             threadWithLock = thisThread;
         } else {
             sleepingThreads.enqueue(thisThread);
             thisThread.sleep();
         }

         // re-enable previous interrupt status
         interrupts.revert();
    }


    unlock() {
        // disable interrupts
        interrupts.disable();

        // if there is a thread waiting for the lock, add it to the ready list
        if (sleepingThreads.isEmpty() == false) {
            Thread * t = sleepingThreads.dequeue();
            t.updateStatus(READY);
            threadReadyList.enqueue(t);
        }

        // release lock
        threadWithLock = null;
        lock = 0;

        // re-enable previous interrupt status
        interrupts.revert();
    }

}

// WORKS

class Semaphore {

    Thread * thisThread;

    down() {
        // disable interrupts
        interrupts.disable();

        readyCount -= 1;
        if (readyCount < 0) {
            sleepingThreads.enqueue(thisThread);
            thisThread.sleep();
        }

        // re-enable previous interrupt status
        interrupts.revert();
    }

    up () {
        // disable interrupts
        interrupts.disable();

        readyCount += + 1;
        if (readyCount <= 0) {
            Thread * t = null;
            t = sleepingThreads.dequeue();
            t.updateStatus(READY);
            threadReadyList.enqueue(t);
        }

        // re-enable previous interrupt status
        interrupts.revert();
    }

}

EDIT: The problem was that I was not handing the lock over to the next thread waiting in the queue. It had nothing to do with the interrupt status. Correct unlock() shown below...

    unlock() {
        // disable interrupts
        interrupts.disable();

        // if there is a thread waiting for the lock, add it to the ready list,
        // and hand the lock over
        if (sleepingThreads.isEmpty() == false) {
            Thread * t = sleepingThreads.dequeue();
            t.updateStatus(READY);
            threadReadyList.enqueue(t);
            threadWithLock = t;
        } else {
            //release the lock
            threadWithLock = null;
            lock = 0
        }

        // re-enable previous interrupt status
        interrupts.revert();
    }

I think you might have future problems with the interrupts being disabled troughout the wait. You might want to revert interrupts after adding your waiting thread to the queue. — Greyson
I think, mutex implementation isn't correct. A thread which locks mutex has to unlock the mutex which is not the case with semaphore. — bjskishore123
@Greyson .. or, to put it another way, disabling interrupts is a total disaster for any preemptive multitasker. sleep() will only work under such a condition if the interval is so short that the compiler inserts a polling loop on a high-frequency timer, (or equivalent), instead of changing the thread state to [anything that is not running]. — Martin James

Eric Eric · Accepted Answer · 2014-10-20T18:38:50

The problem was that I was not handing the lock over to the next thread waiting in the queue. It had nothing to do with the interrupt status. Correct unlock() shown below...

    unlock() {
        // disable interrupts
        interrupts.disable();

        // if there is a thread waiting for the lock, add it to the ready list,
        // and hand the lock over
        if (sleepingThreads.isEmpty() == false) {
            Thread * t = sleepingThreads.dequeue();
            t.updateStatus(READY);
            threadReadyList.enqueue(t);
            threadWithLock = t;
        } else {
            //release the lock
            threadWithLock = null;
            lock = 0
        }

        // re-enable previous interrupt status
        interrupts.revert();
    }

Cannot implement Mutex correctly

1 Answers