Chapter 5 Process Synchronization¶
5.1 Background¶
Recall producer–consumer problem. We modify it as follows:
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|
Suppose counter == 5
initially. After executing counter++
in producer or counter--
in consumer. The value of counter
may be $4$, $5$, or $6$!
$$ \begin{array}{lllll} T_0: producer & \text{execute} & register_1 = \text{counter} & \{register_1 = 5\} \\ T_1: producer & \text{execute} & register_1 = register_1 + 1 & \{register_1 = 6\} \\ T_2: consumer & \text{execute} & register_2 = \text{counter} & \{register_2 = 5\} \\ T_3: consumer & \text{execute} & register_2 = register_2 - 1 & \{register_2 = 4\} \\ T_4: producer & \text{execute} & \text{counter} = register_1 & \{counter = 6\} \\ T_5: consumer & \text{execute} & \text{counter} = register_2 & \{counter = 4\} \end{array} $$
Race condition
Several processes access and manipulate the same data concurrently and the outcome of the execution depends on the particular order in which the access takes place.
We need to ensure that only one process at a time can be manipulating the variable counter
.
5.2 The Critical-Section Problem¶
Critical section
In which the process may be changing common variables, updating a table, writing a file, and so on.
1 2 3 4 5 6 |
|
A solution to the critical-section problem must satisfy:
- Mutual exclusion
- Progress. Cannot be postponed indefinitely.
- Bounded waiting
Two general approches are used to handle critical sections:
- Preemptive kernels
- Nonpreemptive kernels
Why anyone favor a preemptive kernel over a nonpreemptive one?
- Responsive.
- More suitable for real-time programming.
5.3 Peterson's Solution¶
Peterson's solution is restricted to two processes that alternate execution between their critical sections and remainder sections. The processes are named $P_i$ and $P_j$.
Shared data items:
1 2 |
|
1 2 3 4 5 6 7 8 9 |
|
If both processes try to enter at the same time, turn
will be set to both $i$ and $j$ at roughly the same time. Only one of these assignments will last.
Proof
- Mutual exclusion is preserved.
- The progress requirement is satisfied.
-
The bounded-waiting requirement is met.
Suppose $P_i$ execute $turn = j$ first, then $P_j$ execute $turn = i$. In this assumption, $P_i$ will enter its critical section first and $P_j$ will be stucked in the
while (flag[i] && turn == i)
(remember that herei
should be thinked asj
in the code!). After $P_i$ entering exit section, there are two possibilities:- $P_i$ sets
flag[i] = false
, then $P_j$ enters its critical section. - After $P_i$ setting
flag[i] = false
, it immediately setsflag[i] = true
again, consequently, it'll setturn = j
, thus $P_j$ still can enter its critical section.
- $P_i$ sets
Bakery Algorithm¶
- Originally designed for distrubuted systems
- Processes which are ready to enter their critical section must take a number and wait till the number becomes the lowest.
1 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
- An observation: If $P_i$ is in its critical section, and $P_k (k \ne i)$ , then $(number[i], i) < (number[k], k)$.
Proof
- Mutual exclusion: Only the process holds the lowest number can enter the critical section. For each process, when that process doens't get its number, the original process will be stucked in the first while-loop. After that process getting its number, we still need to compare their $numbers$ and $indices$.
- Progress requirement: The processes won't be forever postponed.
- Bounded-waiting: Assume that a process holds the biggest number, it should wait other processes in the second while-loop. But after all other process entering their exit section and again entering their entry section, they'll get a bigger number, thus the process won't wait forever.
5.4 Synchronization Hardware¶
Disaple interrupt $\to$ No preemption:
- Infeasible in multiprocessor environment.
- Potential impacts on interrupt-driven system clocks.
Atomic
Modern computer allow us either to test and modify the content of a word or to swap the contents of two words atomically—that is, as one uninterruptible.
Although following algorithms satisfy the mutual-exclusion requirement, they don't satisfy the bounded-waiting requirement.
1 2 3 4 5 6 |
|
1 2 3 4 5 6 7 |
|
The first process executing while (test_and_set(&lock))
will set the address value of lock
to true
and get the return value rv = false
, thus it won't be stucked in the while-loop and it can enter its critical section.
- Mutual exclusion: OK
- Progress requirement: OK
-
Bounded-waiting: FAIL
Assume there is only one CPU, after $P_i$ entering its critical section, $P_j$ will be stucked in the while-loop. After $P_i$ exiting its critical section, there are two possibilities:
- $P_i$ sets
lock = false
, the CPU context switch to $P_j$, thus $P_j$ can enters its critical section. - After $P_i$ setting
lock = false
, the CPU still executes the code of $P_i$, thus $P_i$ enters its critical section again, so $P_j$ may wait forever.
- $P_i$ sets
1 2 3 4 5 |
|
1 2 3 4 5 6 7 8 9 |
|
- Mutual exclusion: OK
- Progress requirement: OK
- Bounded-waiting: FAIL (the reason is like above)
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 |
|
Following algorithms satisfies all the critical-section requirements.
1 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 |
|
Assume lock
is initialized to false
.
- Mutual exclusion: If many processes set their
waiting[i] = true
, after the first process executekey = test_and_set(&lock)
,key
will be set tofalse
andlock
will be set totrue
. Therefore, other processes will be stucked inwhile (waiting[i] && key)
since theirkey
will be set totrue
aftertest_and_set(&lock)
(lock
is nowtrue
). - Progress requirement: Only the process first run
test_and_set
can enter its critical section. - Bounded-waiting: Wait at most $n - 1$ times.
Mutex Locks¶
A high-level software solution to provide protect critical sections with mutual exclusion.
- Atomic execution of
acquire()
andrelease()
. - Spinlock:
- pros: No context switch for multiprocessor systems.
- cons: Busy waiting.
1 2 3 4 |
|
1 2 3 |
|
1 2 3 4 5 6 |
|
Spinlock
The process "spins" while waiting for the lock to become available.
5.6 Semaphores¶
A high-level solution for more complex problems.
- A variable
S
only accessible by two atomic operations - Spinlock
1 2 3 4 |
|
1 2 3 |
|
5.6.1 Semaphore Usage¶
-
Critical sections:
1 2 3 4 5 6
do { wait(mutex); /* critical section */ signal(mutex); /* remainder section */ } while (true);
-
Precedence enforcement:
-
$P_1$:
1 2
S1; signal(synch);
-
$P_2$:
1 2
wait(synch); S2;
-
5.6.2 Semaphore Implementation¶
It's not good for single CPU. Even if it's implemented in a multi-CPU environment, the locks should be held for a short time.
We can implement the Semaphores with block waiting:
1 2 3 4 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 |
|
$|S.value|$ = # of waiting processes if $S.value < 0$.
Bounded-waiting can be satisfied by FIFO queue but may be unsatisfied by priority queue.
5.6.3 Deadlocks and Starvation¶
Deadlock
A set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set.
$$ \begin{array}{cc} P_0 & P_1 \\ wait(S); & wait(Q); \\ wait(Q); & wait(S); \\ \vdots & \vdots \\ signal(S); & signal(Q); \\ signal(Q); & signal(S); \\ \end{array} $$
Deadlock may happen (assume $S = 1$ and $Q = 1$:
- $P_0$ calls $wait(S)$
- $P_1$ calls $wait(Q)$
- $P_1$ calls $wait(S)$
- $P_0$ calls $wait(Q)$
Starvation (Indefinite blocking)
A situation in which processes wait indefinitely within the semaphore.
e.g. priority queue, stack (LIFO).
5.6.4 Priority Inversion¶
Priority Inversion
A higher-priority task is blocked by a lower-priority task due to some resource access conflict.
Binary Semaphore¶
We can implement counting semaphores by binary semaphores. ($S_1 = 1$, $S_2 = 0$ and $S_3 = 1$)
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 |
|
- Is
wait(S3)
necessary? - Can we change the order of
signal(S1)
andwait(S2)
? - There are lots of implementation details.
5.7 Classic Problems of Synchronization¶
5.7.1 The Bounded-Buffer Problem¶
1 2 3 4 |
|
-
Producer:
1 2 3 4 5 6 7 8 9 10 11
do { /* produce an item in next_produced */ wait(empty); wait(mutex); /* add next_produced to the buffer */ signal(mutex); signal(full); } while (true);
-
Consumer:
1 2 3 4 5 6 7 8 9 10 11
do { wait(full); wait(mutex); /* remove an item from buffer to next_consumed */ signal(mutex); signal(empty); /* consume the item in next_consumed */ } while (true);
5.7.2 The Readers–Writers Problem¶
-
The basic assumption:
- Readers: shared locks
- Writers: exclusive locks
-
The first reader-writers problem
- No readers will be kept waiting unless a writer has already obtained permission to use the shared object $\to$ potential hazard to writers!
-
The second reader-writers problem
- One a writer is ready, it performs its write asap $\to$ potential hazard to readers.
1 2 3 |
|
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
5.7.3 The Dining-Philosophers Problem¶
- Each philosopher must pick up one chopstick beside him/her at a time.
- When two chopsticks are picked up, the philosopher can eat.
1 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
Critical Regions¶
- Region $v$ when $C$ (condition) do $S$ (statements)
- Variable $v$ — shared among processes and only accessible in the region.
1 2 3 4 |
|
-
Producer:
1 2 3 4 5 6
region buffer when (count < n) { pool[in] = next_produced; in = (in + 1) % n; count++; }
-
Consumer:
1 2 3 4 5 6
region buffer when (count > 0) { next_consumed = pool[out]; out = (out + 1) % n; count--; }
5.8 Monitors¶
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
5.8.1 Monitor Usage¶
An abstract data type—or ADT—encapsulates data with a set of functions to operate on that data that are independent of any specific implementation of the ADT.
The monitor construct ensures that only one process at a time is active within the monitor.
A programmer who needs to write a tailor-made synchronization scheme can define one or more variables of type $condition$:
1 |
|
The only operations that can be invoked on a condition variable are wait()
and signal()
. The operation
1 |
|
means that the process invoking this operation is suspended until another process invokes
1 |
|
Condition variables (of a monitor) vs. signal operation (of binary semaphore)
The x.signal()
operation resumes exactly one suspended process. If no process is suspended, then the signal()
operation has no effect; that is, the state of x
is the same as if the operation had never been executed. Contrast this operation with the signal()
operation associated with semaphores, which always affects the state of the semaphore.
Suppose that, when the x.signal()
operation is invoked by a process P
, there exists a suspended process Q
associated with condition x
. Clearly, if the suspended process Q
is allowed to resume its execution, the signaling process P
must wait. Two possibilities exist:
-
Signal and wait:
P
either waits untilQ
leaves the monitor or waits for another condition. -
Signal and continue:
Q
either waits untilP
leaves the monitor or waits for another condition.
5.8.2 Dining-Philosophers Solution Using Monitors¶
1 2 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
|
-
$P_i$:
1 2 3 4 5
DiningPhilosophers.pickup(i); /* eat */ DiningPhilosophers.putdown(i);
No deadlock, but starvation could occur!
5.8.3 Implementing a Monitor Using Semaphores¶
- Semaphores
mutex
: to protect the monitornext
: being initialized to zero, on which processes may suspend themselvesnext_count
Each external function F
is replaced by
1 2 3 4 5 6 7 8 |
|
For each condition x
, we introduce a semaphore x_sem
and an integer variable x_count
, both initialized to $0$.
-
x.wait()
1 2 3 4 5 6 7
x_count++; if (next_count > 0) signal(next); else signal(mutex); wait(x_sem); x_count--;
-
x.signal()
1 2 3 4 5 6
if (x_count > 0) { /* If there's somebody being waiting */ next_count++; signal(x_sem); wait(next); next_count--; }
5.8.4 Resuming Processes within a Monitor¶
-
conditional-wait:
1
x.wait(c);
where $c$ is a priority number. When
x.signal()
is executed, the process with the smallest priority number is resumed next.
Consider the ResourceAllocator
monitor, which controls the allocation of a single resource among competing processes.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
-
A process that needs to access the resource in question must observe the following sequence:
1 2 3 4 5
R.acquire(t); /* access the resource */ R.release();
The monitor concept cannot guarantee that the preceding access sequence will be observed. In particular, the following problems can occur:
-
A process might access a resource without first gaining access permission to the resource.
-
A process might never release a resource once it has been granted access to the resource.
-
A process might attempt to release a resource that it never requested.
-
A process might request the same resource twice (without first releasing the resource).
5.9 Synchronization Examples¶
5.9.1 Synchronization in Windows¶
-
General Mechanism
- Spin-locking for short code segments in a multiprocessor platform.
- Interrupt disabling when the kernel accesses global variables in a uniprocessor platform.
-
Dispatcher Object
- State: signaled or non-signaled
- Mutex: select one process from its waiting queue to the ready queue.
- Critical-section object — user-mode mutex
- Events: like condition variables
- Timers: select all waiting processes
5.9.2 Synchronization in Linux¶
Preemptive kernel after version 2.6.
-
Atomic integer
1 2 3 4
atomic_t counter; ... atomic_set(&counter, 5); atomic_add(10, &counter);
-
Semaphores for long code segments. Mutex locks for the kernel code.
- Sping-locking for short code segments in a multiprocessor platform.
- Preeption disabling and enabling in a uniprocessor platform.
preempt_disable()
andpreempt_enable()
preempt_count
for each task in the system
5.9.3 Synchronization in Solaris¶
- Semaphores and condition variables
- Adaptive mutex
- spin-locking if the lock-holding thread is running; otherwise, blocking is used
- Readers-writers locks
- expensive in implementations
- Turnstile
- A queue structure containing threads blocked on a lock
- Priotity inversion $\to$ priority inheritance protocol for kernel threads
5.9.4 Pthreads Synchronization¶
- General Mechanism
- Mutex locks: mutual exclusion
- condition variables: monitor
- Read-write locks
5.10 Alternative Approaches¶
5.10.1 Transactional Memory¶
Memory transaction
A sequence of memory read-write operations that are atomic.
Committed or being roleld back:
1 2 3 4 5 |
|
- Advantages:
- No deadlock
- Identification of potentially concurrently executing statements in atomic blocks
- Implementations:
- Software transaction memory
- Code is inserted by the compiler.
- Hardware transactional memory
- Hardware cache hierarchies and cache coherency protocols are used.
- Software transaction memory
5.10.2 OpenMP¶
- A set of compiler directives and an API
- The critical-section compiler directive behaves like a binary semaphore or mutex.
1 2 3 4 5 |
|
- pros: easy to use
- cons: identification of protected code and potentials of deadlocks