Synchronization Primitives: Implementation and Examples

Synchronization Primitives: Implementation and Examples

Implementation

The macros DisableInterrupts() and RestoreInterrupts() are useful below:

#define DisableInterrupts() IntStatus __oldLevel = kernel->interrupt->SetLevel(IntOff)
#define RestoreInterrupts() kernel->interrupt->SetLevel(__oldLevel)

A ThreadQueue is a useful abstraction for the implementation of synchronization primitives. All these operations assume interrupts are already disabled. Nachos requires that interrupts be disabled while manipulating the ready list and upon a call to Thread::Sleep.

ThreadQueue {
    var queue: List of Thread;

    sleep() {
        enqueue current thread;
        put current thread to sleep;
    }

    wake() {
        if (queue not empty) {
            dequeue thread;
            wake thread;
        }
    }

    wake-all() {
        while (queue not empty)
            wake();
    }
}

A semaphore is a very general synchronization primitive, and most other synchronization operations can be reduced to semaphore operations (this is how Nachos implements locks and condition variables). Semaphores are in most cases too basic an abstraction to be used effectively. There are a few simple problems that are best solved with semaphores, but in general locks and condition variables are a much better abstraction.

Semaphore(counter) {
    var counter: Unsigned Integer;
    var waitQueue: ThreadQueue;

    P() {
        DisableInterrupts()

        while (counter == 0)
            waitQueue.sleep()
        counter--

        RestoreInterrupts()
    }

    V() {
        DisableInterrupts()

        counter++
        waitQueue.wake()

      RestoreInterrupts()
    }
}

A lock is an object that can be held by at most one thread at a time. Only the thread that last acquired a lock is allowed to release that lock. Locks are useful for guarding critical sections. Keep in mind that multiple methods can be part of the same critical section.

Lock {
    var isHeld: boolean;
    var waitQueue: ThreadQueue;

    acquire() {
        DisableInterrupts()

        while (isHeld)
            waitQueue.sleep();
        isHeld = true;

        RestoreInterrupts()
    }

    release() {
        DisableInterrupts()

        isHeld = false;
        waitQueue.wake();

        RestoreInterrupts()
    }
}

A condition variable is an object used in combination with its associated lock to allow a thread to wait for some condition while it is inside a critical section. Only a thread holding the associated lock is allowed to use a condition variable associated with that lock. A condition variable has only one associated lock, but multiple condition variables may be associated with a single lock.

Condition(lock) {
    var lock: Lock;
    var waitQueue: ThreadQueue;

    wait() {
        DisableInterrupts()

        lock.release()
        waitQueue.sleep()
        lock.acquire()

        RestoreInterrupts()
    }

    signal() {
        DisableInterrupts()

        waitQueue.wake();

        RestoreInterrupts()
    }

    broadcast() {
        DisableInterrupts()

        waitQueue.wake-all();

        RestoreInterrupts()
    }
}

Note that Condition::wait() must release the lock and go to sleep atomically. This is accomplished by disabling interrupts..

A monitor is a critical section guarded by a lock, plus all the condition variables associated with that lock. A straightforward example of a monitor is the set of synchronized methods in a Java class. Each Java Object that has synchronized methods also has a lock and a single conditional variable. When you call a synchronized method, Java automatically does a lock.acquire(), and when you return from the method (explicitly or through a throw statement), Java automatically releases the lock.

Examples with Semaphores

Very rarely are semaphores the best abstraction to use. But one example of where they are useful is a two-thread barrier. A thread that enters the barrier cannot leave until the other thread arrives. This can be used to ensure that both threads are caught up to a point before continuing.

S1: Semaphore(0);
S2: Semaphore(0);

Thread A	Thread B
... S1.V() S2.P() ...	... S2.V() S1.P() ...

A second important use of semaphores is in interrupt handlers. Condition variables cannot be used in interrupt handlers because interrupt handlers cannot acquire locks (consider what would happen if the lock were already held by another thread… or worse, if the lock were already held by the current thread).

Semaphore::V turns out to be the only synchronization operation that can be safely used in an interrupt handler. Shared variables protected by locks cannot be safely accessed in interrupt handlers. Typically, a dedicated device thread gets woken up by the interrupt handler:

S: Semaphore(0);
lock: Lock;

Interrupted Thread

...
interrupt immediately transfers control to interrupt handler {
S.V()
return from interrupt handler
}
...

Dedicated Device Thread

while (1) {
    S.P()
    lock.acquire()
    deal with interrupt (probably signal somebody at least)...
    lock.release()
}

This ends the usefulness of semaphores. For almost everything else, you should probably use monitors (though occasionally you’ll need something as low-level as the ThreadQueue)… two examples of monitors follow.

Examples with Monitors

Bounded-Buffer Problem (see Silberschatz section 6.1)

BoundedBuffer(size, buffer) {
    var buffer: Finite-Size Container;
    var size,count: Integer;
    var lock: Lock;
    var notEmpty,notFull: Condition(lock);

    Produce(item) {
        lock.acquire()

        while (count == size)
            notFull.Wait()
        buffer.add(item)
        notEmpty.Signal()

        lock.release()
    }

    Consume() {
        lock.acquire()

        while (count == 0)
            notEmpty.Wait()
        item = buffer.remove()
        notFull.Signal()

        lock.Release()
        return item
    }
}

Semaphore implemented as a monitor

Semaphore(counter) {
    var counter: Unsigned Integer;
    var lock: Lock;
    var notZero: Condition(lock);

    P() {
        lock.acquire()

        while (counter == 0)
            notZero.wait()
        counter--

        lock.release()
    }

    V() {
        lock.acquire()

        counter++
        notZero.signal()

        lock.release()
    }
}

Notes About Monitors

Note the usage pattern of locks and condition variables within the sample monitors above. Every method follows a few simple rules:

The first step is to acquire the lock on the monitor
The last step before returning is to release the lock on the monitor
Call Condition::Wait only in while loops
Whenever one of the conditions being waited on might have changed from FALSE to TRUE, signal the corresponding condition variable

The first two requirements are relatively straightforward. Any method in a monitor that needs to manipulate shared state, but is called from a method outside the monitor, must acquire the lock on the monitor first. There is no significant advantage to delaying this lock acquire, and monitors tend to be cleaner if these rules are followed.

Note that in Java, this is actually mandatory: the lock acquires and releases are automatically placed in the beginning of the method and right before every return statement. For example, the following Java implementation of Semaphores would translate to the C++ one above:

class Semaphore {
    private unsigned counter;

    public Semaphore(unsigned counter) { this.counter = counter; }

    public synchronized void P() {
        while (counter == 0)
            try { wait(); } catch (Exception e) {}
        counter--;
    }

    public synchronized void V() {
        counter++;
        notify();
    }
}

The code makes use of the fact that every Java object with synchronized methods has a built-in condition variable. There is no mention of the lock, except in specifying which methods are synchronized.

The third rule, that Wait be called from within a while loop, has to do with the fact that we use Mesa-style condition variables. What this means is that, when a thread waiting on a condition variable gets a signal, it does not get to run immediately (this would be a transition from the blocked state to the running state, which we do not allow). Any number of other threads can run in between the time a thread is woken up and the time it actually gets to run. What this means for condition variables is that the condition that the threads was waiting for, which was true at the time it got the signal, might not be true any longer. So it is necessary when using Wait to recheck the condition after Wait returns, by using a while loop:

while (!(condition-waiting-for))
condition-variable.Wait()

For example, in the Semaphore code, P() waits until counter is non-zero, by using the loop

while (counter == 0)
notZero.Wait();

Finally, whenever you change some shared state such that another thread waiting on the condition variable might want to wake up, signal that condition variable (you should signal before you release the lock, either explicitly or through a call to Wait). Because your condition checks are enclosed in while loops, it is actually OK to signal even when the corresponding condition is not true, or already is true (though, if abused, this can cause performance problems, like busy waiting).

For example, again in the Semaphore code, V() increments the counter, and then immediately signals the notZero condition variable. It does this because incrementing the counter potentially allows one more sleeping thread to get out of P(). Even if there are no sleeping threads, Signal still works.