# Mutex implementation on top of a preemptive scheduler that does not guarantee liveness

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. Compared with Mutex implementation on top of a minimalistic preemptive scheduler, there's a twist: the kernel does not guarantee thread liveness.

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.

From the kernel, I get two primitives:

• sleep(): suspend the current thread until a thread has called wake(t) where t is the current thread. If the current thread's wake-up flag is already set then sleep() returns immediately. Returning from sleep clears the wake-up flag.
• wake(t): wake thread t if it's asleep. If t isn't asleep then its wake-up flag is set and t's next call to sleep will return immediately.

Can I implement a mutex on top of these primitives?

• lock(m): if m is taken, sleep until it is free. Mark m as taken.
• unlock(m): mark m as free. If some other thread is waiting for it to become free, that thread is woken up.

Note the absence of a yield() primitive. If a thread does not go to sleep then there is no guarantee that some other thread will get any CPU time. Why? Because the scheduler assigns priorities to threads, and a low-priority thread will never run if all cores are busy running higher-priority threads. But the mutex functions must work between threads with different priorities.

If these primitives aren't enough to implement a locking mechanism, what feature can I add to the kernel to make it possible (keeping in mind that I'm trying to keep it small)? Note that I want to maintain the guarantee that high-priority threads won't be interrupted by low-priority thread if they don't take some explicit action permitting it.

• How do you want to deal with the priority inversion case? (Thread C of low priority holds a mutex, Thread A of higher priority becomes ready to run, so starts running and tries to acquire the mutex. Then make it one step more complicated: now thread B becomes ready to run while C is still in the mutex, so you've got a real priority inversion.) The most elegant choice might be to temporarily increase C's priority to that of A. (But then there needs to be a kernel primitive that does that.) Another option is to just kill C. – Wandering Logic Feb 12 '15 at 2:47
• @WanderingLogic Priority inversion is left to the higher-level design. If a high-priority thread uses a resource, it's up to the system integrator to decide whether this resource can be shared with a low-priority thread. Automatically increasing C's priority to A's would require a lot more intelligence in the kernel: I'm rather heading to a design where the kernel has no such intelligence, it doesn't know what C is blocked on. C might explicitly raise its priority while it's working with the shared resource, but the mutex library must work even if it doesn't. – Gilles 'SO- stop being evil' Feb 12 '15 at 9:13