Syncronization Primitives Equivalence

sync.md

Syncronization Primitives Equivalences

Pseudocode inspiration from: https://people.eecs.berkeley.edu/~kubitron/courses/cs162-F10/hand-outs/synch.html

Interfaces

ThreadQueue() {
    var queue: Queue<Thread>;

    sleep() {
        queue.enqueue(Thread.current());
        Thread.current().sleep();
    }

    wake() {
        if (!queue.empty()) {
            var thread = queue.dequeue();
            thread.wake();
        }
    }

    wakeAll() {
        while (!queue.empty()) {
            var thread = queue.dequeue();
            thread.wake();
        }
    }
}

Semaphore(counter) {
    // increment atomically the counter
    increment()
    // decrements atomically the counter if greater than zero or wait other thread to call increment
    decrement()
}

Lock() {
    // acquire the lock or wait if already acquired from other thread
    acquire()
    // release the lock
    release()
}

ConditionVariable(lock, predicate) {
    // wait until signal is called for this thread and predicate returns true
    wait()
    // signal first thread in queue
    signal()
    // broadcast signal to all threads in queue
    broadcast()
}

Equivalences

Semaphore using Locks and ConditionVariables

Semaphore(counter) {
    var counter: Unsigned Integer;
    var lock: Lock;
    var notZero: ConditionVariable(lock, { counter > 0 });

    decrement() {
        lock.acquire();
        notZero.wait(); // wait until counter becomes greater than zero
        counter--;
        lock.release();
    }

    increment() {
        lock.acquire();
        counter++;
        notZero.signal(); // signal counter might have become greater than zero
        lock.release();
    }
}

Lock using Semaphores

Lock() {
    var semaphore: Semaphore(1);

    acquire() {
        semaphore.decrement();
    }

    release() {
        semaphore.increment();
    }
}

ConditionVariable using (Locks and) Semaphores

ConditionVariable(lock, predicate) {
    var lock: Lock;
    var threadCount: Semaphore(0); // number of threads waiting on this ConditionVariable.
    var signalEmitted: Semaphore(0); // 0 or 1 if signal is present or not

    wait() {
        lock.release();
        sleepingThreads.increment();
        do {
            signalEmitted.decrement(); // wait for a signal to check the predicate
        } while(!predicate()); // check the predicate and if false retry
        sleepingThreads.decrement();
        lock.acquire();
    }

    signal() {
        signalEmitted.increment();
    }

    broadcast() {
        repeat(threadCount.counter) {
            signalEmitted.increment();
        }
    }
}