Chapter 5
Chapter 5
Chapter 5
• Background
• The Critical-Section Problem
• Peterson’s Solution
• Synchronization Hardware
• Mutex Locks
• Semaphores
• Classic Problems of Synchronization
• Monitors
• Synchronization Examples
• Alternative Approaches
Objectives
• To present the concept of process
synchronization.
• To introduce the critical-section problem,
whose solutions can be used to ensure the
consistency of shared data
• To present both software and hardware
solutions of the critical-section problem
• To examine several classical process-
synchronization problems
• To explore several tools that are used to
solve process synchronization problems
Background
• Processes can execute concurrently
• May be interrupted at any time, partially completing
execution
• Concurrent access to shared data may result in data
inconsistency
• Maintaining data consistency requires mechanisms to
ensure the orderly execution of cooperating processes
• Illustration of the problem:
Suppose that we wanted to provide a solution to the
consumer-producer problem that fills all the buffers.
We can do so by having an integer counter that keeps
track of the number of full buffers. Initially, counter is
set to 0. It is incremented by the producer after it
produces a new buffer and is decremented by the
consumer after it consumes a buffer.
Producer
while (true) {
/* produce an item in next produced */
register1 = counter
register1 = register1 + 1
counter = register1
register2 = counter
register2 = register2 - 1
counter = register2
do {
critical section
turn = j;
remainder section
} while (true);
Solution to Critical-Section Problem
1. Mutual Exclusion - If process Pi is executing in its critical
section, then no other processes can be executing in their
critical sections
2. Progress - If no process is executing in its critical section
and there exist some processes that wish to enter their
critical section, then the selection of the processes that
will enter the critical section next cannot be postponed
indefinitely
3. Bounded Waiting - A bound must exist on the number
of times that other processes are allowed to enter their
critical sections after a process has made a request to
enter its critical section and before that request is granted
Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes
Critical-Section Handling in OS
Two approaches depending on if kernel is
preemptive or non- preemptive
• Preemptive – allows preemption of process
when running in kernel mode
• Non-preemptive – runs until exits kernel mode,
blocks, or voluntarily yields CPU
• Essentially free of race conditions in kernel mode
Peterson’s Solution
• Good algorithmic description of solving the problem
• Two process solution
• Assume that the load and store machine-language
instructions are atomic; that is, cannot be interrupted
• The two processes share two variables:
• int turn;
• Boolean flag[2]
do {
flag[i] = true;
turn = j;
while (flag[j] && turn = = j);
critical section
flag[i] = false;
remainder section
} while (true);
Peterson’s Solution (Cont.)
• Provable that the three CS requirement are met:
1. Mutual exclusion is preserved
Pi enters CS only if:
do {
acquire lock
critical section
release lock
remainder section
} while (TRUE);
test_and_set Instruction
Definition:
boolean test_and_set (boolean *target)
{
boolean rv = *target;
*target = TRUE;
return rv:
}
1.Executed atomically
2.Returns the original value of passed parameter
3.Set the new value of passed parameter to “TRUE”.
Solution using test_and_set()
Shared Boolean variable lock, initialized to FALSE
Solution:
do {
while (test_and_set(&lock))
; /* do nothing */
/* critical section */
lock = false;
/* remainder section */
} while (true);
compare_and_swap Instruction
Definition:
int compare _and_swap(int *value, int expected, int new_value) {
int temp = *value;
if (*value == expected)
*value = new_value;
return temp;
}
1.Executed atomically
2.Returns the original value of passed parameter “value”
3.Set the variable “value” the value of the passed parameter
“new_value” but only if “value” ==“expected”. That is, the
swap takes place only under this condition.
Solution using compare_and_swap
do {
waiting[i] = true;
key = true;
while (waiting[i] && key)
key = test_and_set(&lock);
waiting[i] = false;
/* critical section */
j = (i + 1) % n;
while ((j != i) && !waiting[j])
j = (j + 1) % n;
if (j == i)
lock = false;
else
waiting[j] = false;
/* remainder section */
} while (true);
Mutex Locks
Previous solutions are complicated and generally
inaccessible to application programmers
OS designers build software tools to solve critical
section problem
Simplest is mutex lock
Protect a critical section by first acquire() a lock
then release() the lock
Boolean variable indicating if lock is available or not
Calls to acquire() and release() must be atomic
Usually implemented via hardware atomic
instructions
But this solution requires busy waiting
This lock therefore called a spinlock
acquire() and release()
• acquire() {
while (!available)
; /* busy wait */
available = false;
}
• release() {
available = true;
}
• do {
acquire lock
critical section
release lock
remainder section
} while (true);
Semaphore
• Synchronization tool that provides more sophisticated ways (than Mutex locks) for process
to synchronize their activities.
• Semaphore S – integer variable
• Can only be accessed via two indivisible (atomic) operations
• wait() and signal()
• Originally called P() and V()
wait(semaphore *S) {
S->value--;
if (S->value < 0) {
add this process to S->list;
block();
}
}
signal(semaphore *S) {
S->value++;
if (S->value <= 0) {
remove a process P from S->list;
wakeup(P);
}
}
Deadlock and Starvation
• Deadlock – two or more processes are waiting indefinitely for an
event that can be caused by only one of the waiting processes
• Let S and Q be two semaphores initialized to 1
P0 P1
wait(S); wait(Q);
wait(Q); wait(S);
... ...
signal(S); signal(Q);
signal(Q); signal(S);
do {
...
/* produce an item in next_produced */
...
wait(empty);
wait(mutex);
...
/* add next produced to the buffer */
...
signal(mutex);
signal(full);
} while (true);
Bounded Buffer Problem (Cont.)
The structure of the consumer process
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);
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
Readers-Writers Problem (Cont.)
• The structure of a writer process
do {
wait(rw_mutex);
...
/* writing is performed */
...
signal(rw_mutex);
} while (true);
Readers-Writers Problem (Cont.)
• The structure of a reader process
do {
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);
} while (true);
Readers-Writers Problem Variations
// eat
signal (chopstick[i] );
signal (chopstick[ (i + 1) % 5] );
// think
} while (TRUE);
• Deadlock handling
• Allow at most 4 philosophers to be sitting
simultaneously at the table.
• Allow a philosopher to pick up the forks
only if both are available (picking must be
done in a critical section.
• Use an asymmetric solution -- an odd-
numbered philosopher picks up first the left
chopstick and then the right chopstick. Even-
numbered philosopher picks up first the
right chopstick and then the left chopstick.
Problems with Semaphores
monitor monitor-name
{
// shared variable declarations
procedure P1 (…) { …. }
initialization_code() {
for (int i = 0; i < 5; i++)
state[i] = THINKING;
}
}
Solution to Dining Philosophers (Cont.)
DiningPhilosophers.pickup(i);
EAT
DiningPhilosophers.putdown(i);
• Variables
wait(mutex);
…
body of F;
…
if (next_count > 0)
signal(next)
else
signal(mutex);
if (x_count > 0) {
next_count++;
signal(x_sem);
wait(next);
next_count--;
}
Resuming Processes within a Monitor
R.acquire(t);
...
access the resurce;
...
R.release;
• Solaris
• Windows
• Linux
• Pthreads
Solaris Synchronization
• Implements a variety of locks to support multitasking,
multithreading (including real-time threads), and
multiprocessing
• Uses adaptive mutexes for efficiency when protecting data
from short code segments
• Starts as a standard semaphore spin-lock
• If lock held, and by a thread running on another CPU, spins
• If lock held by non-run-state thread, block and sleep waiting for signal of lock being released
• OpenMP
void update()
{
/* read/write memory */
}
OpenMP
• OpenMP is a set of compiler directives and API
that support parallel progamming.
Operating System Concepts – 9th Edition Silberschatz, Galvin and Gagne ©2013