Chapter 7: Synchronization Examples
Operating System Concepts – 10th Edition
Silberschatz, Galvin and Gagne ©2018
Classical Problems of Synchronization
Classical problems used to test newly-proposed synchronization schemes
Bounded-Buffer Problem
Readers and Writers Problem Dining-Philosophers Problem
Operating System Concepts – 10th Edition 7.2 Silberschatz, Galvin and Gagne ©2018
Bounded-Buffer Problem
n buffers, each can hold one item
Semaphore mutex initialized to the value 1 Semaphore full initialized to the value 0
Semaphore empty initialized to the value n
Operating System Concepts – 10th Edition 7.3 Silberschatz, Galvin and Gagne ©2018
}
Bounded Buffer Problem (Cont.)
The structure of the producer process while (true) {
…
/* produce an item in next_produced */
…
wait(empty);
wait(mutex);
…
/* add next produced to the buffer */
…
signal(mutex);
signal(full);
Operating System Concepts – 10th Edition 7.4 Silberschatz, Galvin and Gagne ©2018
Bounded Buffer Problem (Cont.)
The structure of the consumer process
while (true) {
wait(full);
wait(mutex);
…
/* remove an item from buffer to next_consumed */
…
signal(mutex);
signal(empty);
…
/* consume the item in next consumed */
… }
Operating System Concepts – 10th Edition 7.5 Silberschatz, Galvin and Gagne ©2018
Readers-Writers Problem
A data set is shared among a number of concurrent processes
Readers – only read the data set; they do not perform any updates Writers – can both read and write
Problem – allow multiple readers to read at the same time
Only one single writer can access the shared data at the same time
Several variations of how readers and writers are considered – all involve some form of priorities
Shared Data Data set
Semaphore rw_mutex initialized to 1 Semaphore mutex initialized to 1
Integer read_count initialized to 0
Operating System Concepts – 10th Edition 7.6 Silberschatz, Galvin and Gagne ©2018
}
Readers-Writers Problem (Cont.)
The structure of a writer process while (true) {
wait(rw_mutex);
…
/* writing is performed */
…
signal(rw_mutex);
Operating System Concepts – 10th Edition 7.7 Silberschatz, Galvin and Gagne ©2018
Readers-Writers Problem (Cont.)
The structure of a reader process
while (true){
wait(mutex);
}
read_count++;
if (read_count == 1)
wait(rw_mutex);
signal(mutex);
…
/* reading is performed */
…
wait(mutex);
read count–;
if (read_count == 0)
signal(rw_mutex);
signal(mutex);
Operating System Concepts – 10th Edition 7.8 Silberschatz, Galvin and Gagne ©2018
Readers-Writers Problem Variations
First variation – no reader kept waiting unless writer has permission to use shared object
Second variation – once writer is ready, it performs the write ASAP
Both may have starvation leading to even more variations Problem is solved on some systems by kernel providing
reader-writer locks
Operating System Concepts – 10th Edition 7.9 Silberschatz, Galvin and Gagne ©2018
Dining-Philosophers Problem
Philosophers spend their lives alternating thinking and eating Don’t interact with their neighbors, occasionally try to pick up 2
chopsticks (one at a time) to eat from bowl
Need both to eat, then release both when done
In the case of 5 philosophers Shared data
Bowl of rice (data set)
Semaphore chopstick [5] initialized to 1
Operating System Concepts – 10th Edition 7.10 Silberschatz, Galvin and Gagne ©2018
Dining-Philosophers Problem Algorithm
Semaphore Solution
The structure of Philosopher i: while (true){
}
wait (chopstick[i] );
wait (chopStick[ (i + 1) % 5] );
/* eat for awhile */
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
/* think for awhile */
What is the problem with this algorithm?
Operating System Concepts – 10th Edition 7.11 Silberschatz, Galvin and Gagne ©2018
Monitor Solution to Dining Philosophers
monitor DiningPhilosophers
{
enum { THINKING; HUNGRY, EATING) state [5] ;
condition self [5];
void pickup (int i) {
state[i] = HUNGRY;
}
test(i);
if (state[i] != EATING) self[i].wait;
void putdown (int i) {
state[i] = THINKING;
}
// test left and right neighbors
test((i + 4) % 5);
test((i + 1) % 5);
Operating System Concepts – 10th Edition 7.12 Silberschatz, Galvin and Gagne ©2018
}
Solution to Dining Philosophers (Cont.)
void test (int i) {
if ((state[(i + 4) % 5] != EATING) &&
(state[i] == HUNGRY) &&
(state[(i + 1) % 5] != EATING) ) {
}
}
state[i] = EATING ;
self[i].signal () ;
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
Operating System Concepts – 10th Edition 7.13 Silberschatz, Galvin and Gagne ©2018
Solution to Dining Philosophers (Cont.)
Each philosopher i invokes the operations pickup() and putdown() in the following sequence:
DiningPhilosophers.pickup(i); /** EAT **/
DiningPhilosophers.putdown(i);
No deadlock, but starvation is possible
Operating System Concepts – 10th Edition 7.14 Silberschatz, Galvin and Gagne ©2018
Linux provides: Semaphores
Linux Synchronization
Linux:
Prior to kernel Version 2.6, disables interrupts to
implement short critical sections
Version 2.6 and later, fully preemptive
atomic integers
spinlocks
reader-writer versions of both
On single-cpu system, spinlocks replaced by enabling and disabling kernel preemption
Operating System Concepts – 10th Edition 7.15 Silberschatz, Galvin and Gagne ©2018
Consider the variables atomic_t counter;
int value;
Linux Synchronization
Atomic variables
atomic_t is the type for atomic integer
Operating System Concepts – 10th Edition 7.16 Silberschatz, Galvin and Gagne ©2018
POSIX API provides mutex locks
semaphores
POSIX Synchronization
condition variable
Widely used on UNIX, Linux, and macOS
Operating System Concepts – 10th Edition 7.17 Silberschatz, Galvin and Gagne ©2018
POSIX Mutex Locks
Creating and initializing the lock
Acquiring and releasing the lock
Operating System Concepts – 10th Edition 7.18 Silberschatz, Galvin and Gagne ©2018
POSIX Semaphores
POSIX provides two versions – named and unnamed.
Named semaphores can be used by unrelated processes.
Unnamed semaphores can only be used by related processes which share an address space such as children processes created by a parent process using the fork command; or threads that belong to a same process.
Operating System Concepts – 10th Edition 7.19 Silberschatz, Galvin and Gagne ©2018
POSIX Named Semaphores
Creating an initializing the semaphore:
Another process can access the semaphore by referring to its name SEM. Acquiring and releasing the semaphore:
Operating System Concepts – 10th Edition 7.20 Silberschatz, Galvin and Gagne ©2018
POSIX Unnamed Semaphores
Creating an initializing the semaphore:
Acquiring and releasing the semaphore:
Operating System Concepts – 10th Edition 7.21 Silberschatz, Galvin and Gagne ©2018
POSIX Condition Variables
Since POSIX is typically used in C/C++ and these languages do not provide a monitor, POSIX condition variables are associated with a POSIX mutex lock to provide mutual exclusion: Creating and initializing the condition variable:
Operating System Concepts – 10th Edition 7.22 Silberschatz, Galvin and Gagne ©2018
POSIX Condition Variables
The mutex lock associated with the condition variable must be locked before pthread_cond_wait() can be called. Calling pthread_cond_wait() releases the mutex lock, allowing another thread to change shared data and possibly signal the waiting thread
Example: Thread waiting for the condition a == b to become true:
Thread signaling another thread waiting on the condition variable:
Operating System Concepts – 10th Edition 7.23 Silberschatz, Galvin and Gagne ©2018
End of Chapter 7
Operating System Concepts – 10th Edition Silberschatz, Galvin and Gagne ©2018