In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with a preemptive scheduler (a thread has no way to prevent the scheduler from preempting it). I'm exploring how minimalistic the system can get while remaining powerful and efficient enough for my needs.
From the hardware, I get a basic atomic primitive such as compare-and-swap or load-link/store-conditional. You can assume that the word size for these instructions is large enough to store a pointer or a thread identifier. Furthermore all threads see the same memory.
From the kernel, I get three primitives:
sleep(): suspend the current thread until a thread has called
tis the current thread. If the current thread's wake-up flag is already set then
sleep()returns immediately. Returning from
sleepclears the wake-up flag.
wake(t): wake thread
tif it's asleep. If
tisn't asleep then its wake-up flag is set and
t's next call to
sleepwill return immediately. Note that non-participating threads may call
wake— as far as the locking mechanism is concerned, it's thus possible for a thread's wake flag to become set non-deterministically.
yield(): give all other threads that are not asleep a chance to run.
mis taken, sleep until it is free. Mark
mas free. If some other thread is waiting for it to become free, that thread is woken up.
wait(c, m): wait for the event
cto happen. If
chas already happened, don't block. When
waitreturns, it atomically locks the mutex
m. When a thread notices
c, the event is cleared.
signal(c): signal an event on the condition
c. This wakes up one thread that's waiting on
A good solution must avoid starvation: if a thread tries to lock a mutex, it must eventually get it provided that every thread that acquires it releases it eventually. Preferably, threads should obtain the lock on a first-come, first-served basis. (To give a counter-example, a last-come, first-served system would be bad because one thread could hog the mutex if it keeps acquiring it immediately after releasing it.)
A solution is better if it avoids scheduling a thread that ends up doing no useful work. For example, systematically waking up all threads when something happens is not good enough.
What is an efficient algorithm for implementing mutexes and synchronization variables? (Note that I am not asking how to implement a spinlock! A spinlock is probably involved, but I expect answers to this question to explain how to set up wait queues and not just handwave that part.) Efficiency may vary based on the amount of contention; the kind of systems I work on tend to have low contention in practice (but must not overly drain the battery when there is contention).
(I expect answers to explain the algorithm in sufficient detail that a programmer could understand it, but a reference would be appreciated as well.)