Synchronizing Threaded Programs
We continued to discuss the synchronization issues that occur in threaded programs (as well as in processes that vie for resources or otherwise cooperate in some fashion).
Mutual Exclusion
What Doesn't Work
Suppose we wanted to guard some part of a program against multiple threads being able to execute it simultaneously. We could try the follwoing:
int lock = 0;
...
while lock == 1
{}
lock = 1
// protected code goes here
lock = 0
The idea here is that we are intending to protect the code (in the comment // protected code goes here) to keep more than one thread from being able to execute it an any one time. The idea looks good. Variable lock is checked by each thread desiring access to the protected code. If lock is 1 (locked), this means that some other thread is inside the protected code and therefore that the current thread desiring access should not proceed. So that thread just waits in its while loop. If the thread inside the protected code leaves, it sets lock to 0. Thus, the waiting thread can proceed.
This all sounds good, but when we turn to our mental model of the IFE cycle, we see that this solution does not guarantee mutually exclusive access to the protected code. Why? Because the above is written in a high level language. When the compiler translates this into machine language, it will look something like this:
// while lock == 1
label 1 compareEqual lock, #1
branchFalse label 2
branch label 1// lock = 1
label 2 move #1, lock// protected code goes here
// lock = 0
move #0, lock
Notice that a clock interrupt could occur for thread 1 in the IFE cycle between the instruction with label 1 and the branchTrue instruction. It could be that the value in lock is 0, so the compare bit in the PSW register will be set to FALSE at the point of interrupt. In processing the interrupt for thread 1, the OS will save the PC, PSW, and all other registers of the processor into the thread control block of thread 1. Now, if thread 2 executes, it will also reach the instruction of label 1. At that point the lock variable is still 0, because thread 1 got interrupted before it could set lock to 1. Thread 2 will thus proceed into the protected code. If it gets interrupted while inside the protected code, then thread 1, when it gets to run again, will have all of its saved registers restored, including the PSW. So it will then execute the "branchFalse to label 2" and proceed to label 2 (because the compare bit in the PSW has the value FALSE as it did when thread 1 was interrupted) and move on into the protected code. Thus, two threads will be in the protected code simultaneously, which means that mutual exclusion has been violated.
Notice that the exact same thing can occur if both threads are actually executing in parallel on two different cores.
How to Fix it
There are software solutions, such as Peterson's algorithm, but these are inefficient and difficult to understand. They are also no longer needed, because both hardware and OS's have been enhanced to provide solutions to the problem.
TestAndSet Instruction
The computer engineers created special instructions for the processors they were designing to help with this problem. One is the TestAndSet instruction, which can test a lock variable to see whether it is locked, and if it isn't, set it to the lock value all in one execution step that has no chance of being interrupted.
Semaphores
See the book description of semaphores. A semaphore is a high-level language feature that can serve for synchroninzation purposes (whereas the testandset instruction is a machine language level instruction. Semaphores can be implemented using the testandset instruction. They can also be implemented by way of OS calls (i.e., supervisor calls) if the OS can manage semaphores. This works because an OS can turn off interrupts while it is processing some code and thus can keep the action of checking or setting a semaphore from being executed simultaneously by more than one thread or process from happening.
Avoiding Busy Loops
We would like to avoid the busy loop of the example code given above. Good implementations of semaphores accomplish this by causing a thread that accesses a semaphore to be placed in a blocked state by the OS if the semaphore value is not greater than zero when the semaphore is checked upon entry to a synchronized resource.
Higher Level Constructs
The testandset instruction represents a low-level-hardware approach to helping manage synchronization. The semaphore is a low level software approach that may be built on OS support for semaphores and/or the testandset instruction. Semaphores can be used to implement even higher level support structures, such as monitors, which are similar to Java's "synchronized" classes and methods. Each successively higher level construct makes it easier for the programmer to write synchronized code.