Software-based locks

* All lock implementations in modern operating systems use hardware support in the form of atomic instructions (like test-and-set, compare-and-swap, and so on). However, before we had hardware support for locking in the form of these instructions, several algorithms were developed to achieve mutual exclusion purely by software means.

* A popular algorithm for software locking is Peterson's algorithm. Such algorithms no longer work correctly on modern multicore systems, but are still useful to understand the concept of mutual exclusion. Below is an intuitive way of understanding Peterson algorithm.

* Suppose two threads (self and other) are trying to acquire a lock. Consider the following version of the locking algorithm.

Acquire:
flag[self] = true;
while(flag[other] == true); //busy wait

Release: flag[self] = false;

This algorithm works fine when execution of both threads does not overlap.

* Now, consider another locking algorithm.

Acquire: 
turn = other;
while(turn == other); //busy wait

This algorithm works fine when execution of both threads overlaps.

* So we get a complete algorithm (that works both when executions overlap and don't) by putting the above two together.

Acquire:
flag[self] = true;
turn = other;
while(flag[other] == true && turn == other); //busy wait

Release:
flag[self] = false;

* Peterson's algorithm works correctly only if all the writes to flags and turn happen atomically and in the same order. Modern multicore systems reorder stores, and this algorithm is not meant to work correctly in such cases. Modern systems use locks based on atomic hardware instructions to implement locks.