Is it possible to perform mutual exclusion of threads without OS support?

Question

I suppose you could adapt distributed mutual exclusion algorithms (Ricart/Agrawala, etc), but aside from these more exotic approaches, are you required to use primitives provided by the OS in order to achieve mutual exclusion?

For example, in C# you would use something like lock:

lock (myobject)
{
    // Do something
}

Lock then uses a condition variable provided by the operating system (I think?). From everything I've read about monitors, they all rely on certain sections of the monitor implementation being executed atomically. And the only way (that I can think of) to guarantee that is if the kernel explicitly made it so. Is this right?

Answer 1

there are software solutions for mutual exclusion using only shared memory.

The major gotcha when implementing these is that the order of loads and stores of the shared variables is very important and the compiler/optimizer may not tinker with them at all, most languages have a volatile keyword for fields that will ensure this is true. Also the aforementioned loads and stores must be atomic (no garbage values may occur possible when multiple thread access the variables).

Answer 2

You need a single compare and swap type instruction or load link/store conditional instruction pair which can alter the contents of a piece of storage depending on the contents of that storage. Generally speaking high level languages do not support this construct -- mostly because it varies wildly depending on hardware instruction set.

If you code in C and know your hardware architecture you could roll your own mutex library but it would be impossible in a higher level language.

Answer 3

Spin locks implemented with atomics can be used for mutual exclusion but they are used usually on lower levels. The thing is - thread is abstraction provided by operating system. Thus OS is the best place to control thread execution (create, start, stop, suspend).