Synchronisation Problems
Problem
Suppose we have an object called Thing which has the following method:
public void inc() {
count++;
}
countis private toThing, and is initially zero.-
Two threads, $T_1$ and $T_2$, both execute the following:
thing.inc();
Indeterminacy
Assume the inc() method does these three things within the processor:
- Loads the value of count into a register.
- Increments the value of the register back into
count. - Stores the value of the register back into
count.
The two threads could run and work perfectly most of the time, but sometimes the order of parallel operations might case a problem:
| $T_1$ | $T_2$ | count |
|---|---|---|
LOAD(0) |
0 | |
ADD(1) |
0 | |
LOAD(0) |
0 | |
ADD(1) |
0 | |
STORE(1) |
1 | |
STORE(1) |
1 |
This is called a race condition.
This is very hard to debug as the program will mostly work correctly as the issue is in-determinant.
Mutual Exclusion
Indeterminacy arises because of possible simultaneous access to a shared resource.
The variable count in the example.
The solution is to allow only one thread to access count at any one time; all others must be excluded.
When a thread/process accesses any shared resource, it is in a critical section (region).
One way to enforce mutual exclusion is via semaphores.