Examples of unsynchronized access that may lead to non-deterministic outcome (based on order of access/modification, aka race conditions.)
Critical section: does critical work accessing shared modifiable resources. At any point only one program can execute in that critical section.
TestAndSet( Register, MemLocation )
*MemLoc into $Reg*MemLoc$Reg contentsvoid EnterCS (int *lock) {
/* i.e. while the CS process has set *MemLoc to 1,
* other processes trying to set access is stuck in while loop
* as TestAndSet returns 1. */
while (TestAndSet( lock ) == 1);
}
void ExitCS (int *lock) {
*lock = 0;
}
Problems: busy waiting wastes processing power.
Solution: variants of the instructions.
Variants: Compare and Exchange, Atomic Swap, Load Link/Store Conditional
Turn array. While Turn != P.turn, busy wait.
Want array. Busy wait while someone else wants the turn.
Turn and Want: Peterson’s algorithmTurn cannot be 1 and 0 at once, so only one of the while loops ends at firstTurn now indicates which process’s turn is it.
We assume that line 2 (writing to Turn in each process) is atomic.
Generalized sync mechanism.
Contains one int representing capacity,
wait() blocks if capacity $\leq 0$, otherwise decrement.
signal() increments capacity, wakes up 1 sleeping process.
Invariant for semaphore $s$:
\[s_\text{curr} = s_\text{init} + \# \text{signals executed}(s) - \# \text{waits completed}(s)\]Binary semaphores with capacity of 1.
Number of processes in critical section: $N_{CS} = \text{waits completed}(s) - \text{signals executed}(s)$
\[s_\text{curr} = \textcolor{blue}{1 - N_{CS}} \geq 0 \Rightarrow \textcolor{red}{N_{CS} \leq 1}\]No deadlock where $N_{CS} = s_\text{curr} = 0$, granted correct usage.
No starvation if fair scheduling.
How to wait for another thread to do something specific?
wait(condition) waits for condition to become true i.e. signaledsignal(condition) wakes up one sleeping processbroadcast(condition) wakes up allNote: after a thread is woken up, the condition may not hold anymore.
A collection of procedures manipulating a shared data structure, one lock must be held when accessing the shared data.
From The Little Book of Semaphores.
# Thread A
semA = 0
statement a1
signal(semA)
wait(semB)
statement a2
# Thread B
semB = 0
statement b1
signal(semB)
wait(semA)
statement b2
rendezvous // all n-1 threads block until nth thread reaches rendezvous
critical point
$n$ threads. No thread executes critical point until all have reached rendezvous.
wait(mutex)
waitingThreads += 1
if (waitingThreads == n) signal(barrier) -- (1)
signal(mutex)
wait(barrier)
signal(barrier) -- (2)
critical point
(1) Triggers first waiting thread to pass through. Now value of barrier is $-(n-2)$.
(2) You must signal(barrier) after the each thread is done waiting for the barrier, otherwise the next in queue will not be able to execute (deadlock). This pattern of wait(b), signal(b) is also called a turnstile.
How to lock the barrier again after all the threads have passed?
wait(mutex)
waitingThreads += 1
if (waitingThreads == n)
wait(t2) -- wait for nth thread to unlock 2nd turnstile
signal(t1) -- signals that the 1st turnstile is unlocked
signal(mutex)
wait(t1)
signal(t1)
critical point
wait(mutex)
waitingThreads -= 1
if (waitingThreads == 0)
wait(t1) -- wait for nth thread to unlock 1st turnstile
signal(t2) -- signals that the 2nd turnstile is unlocked
signal(mutex)
wait(t2)
signal(t2)
Two-phase barrier. Note we cannot solve this problem with a single turnstile, e.g.
If the $n$th thread passes through the CP, decrements count without interruption and then returns to the rendezvous (in a loop), and increments count again, it restores the count to $n$ and thus gets ahead of the other threads.
Shared bounded buffer of size $K$. Constraints are:
# Producers: notFull initialized to K
wait(notFull) -- (1)
wait(mutex)
buffer[in] = item
in = (in+1) % K
signal(mutex)
signal(notEmpty)
# Consumers: notEmpty initialized to 0
wait(notEmpty) -- (1)
wait(mutex)
item = buffer[out]
out = (out-1) % K
signal(mutex)
signal(notFull)
use item
(1) Note this is a rendezvous. Removes the need to check the item count in that buffer.
Example of categorical mutual exclusion. Readers don’t exclude other threads, but writers do. Constraints:
# Writers: notEmpty initialized to 1
wait(openToWriters)
/* prioritization
* wait(noWriters)
* write
* signal(noWriters)
*/
signal(openToWriters)
# Readers
wait(mutex)
readerCount += 1
if (readerCount == 1)
wait(openToWriters) -- (1)
signal(mutex)
read
/* prioritization:
* signal(noWriters)
*/
wait(mutex)
readerCount -= 1
if (readerCount == 0) signal(openToWriters)
return(mutex)
signal
(1) Prior to this step, if readerCount == 1 then wait until all writers gone (openToWriters)
openToWriters is the same immediately before and immediately after writeropenToWriters is only increased by readerCount == 0.openToWriters lock closes it off to writers (since it a mutex).Drawbacks: starvation of writer possible.
Solution: Priority to writers. (see /* prioritization */ snippets)
| Image | Specification |
|---|---|
 |
- 5 philosophers seated around a table. - 5 single chopsticks between them - To eat, one must acquire his left and right chopstick - Deadlock-free and starve-free to allow philosophers to freely eat |
Simple informal argument (for “One right-hander”. Let R be the right hander):
| Take chopsticks | Safe to eat | Put chopsticks |
|---|---|---|
 |
 |
 |