Transcript Part 2

Process Synchronization
(Or The “Joys” of Concurrent Programming)
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
Silberschatz, Galvin and Gagne ©2007
Overview: Process Synchronization





Background
The Critical-Section Problem
Peterson’s Solution
Semaphores
Classic Problems of Synchronization
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.2
Silberschatz, Galvin and Gagne ©2007
Background



Fact of Life 1: Concurrent access to shared data
may result in data inconsistency
Fact of Life 2: Maintaining data consistency requires
mechanisms to ensure the orderly execution of
cooperating processes
Example?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.3
Silberschatz, Galvin and Gagne ©2007
Producer- Consumer Example
Producer
Consumer
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.4
Silberschatz, Galvin and Gagne ©2007
Race Condition

count++ could be implemented as

register1 = count
register1 = register1 + 1
count = register1
count-- could be implemented as

register2 = count
register2 = register2 - 1
count = register2
Possible execution (with “count = 5” initially):
S0: producer executes register1 = count {register1 = 5}
S1: producer executes register1 = register1 + 1 {register1 = 6}
S2: consumer executes register2 = count {register2 = 5}
S3: consumer executes register2 = register2 - 1 {register2 = 4}
S4: producer executes count = register1 {count = 6 }
S5: consumer executes count = register2 {count = 4}
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.5
Silberschatz, Galvin and Gagne ©2007
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
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.6
Silberschatz, Galvin and Gagne ©2007
Critical-Section Problem
1.
2.
3.
4.
Race Condition - When there is concurrent access to
shared data and the final outcome depends upon order of
execution.
Critical Section - Section of code where shared data is
accessed.
Entry Section - Code that requests permission to enter
its critical section.
Exit Section - Code that is run after exiting the critical
section
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.7
Silberschatz, Galvin and Gagne ©2007
Structure of a Typical Process
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.8
Silberschatz, Galvin and Gagne ©2007
Peterson’s Solution





Two process solution
Assume that the LOAD and STORE instructions
are atomic; that is, cannot be interrupted.
The two processes share two variables:
 int turn;
 Boolean flag[2]
The variable turn indicates whose turn it is to
enter the critical section.
The flag array is used to indicate if a process is
ready to enter the critical section. flag[i] = true
implies that process Pi is ready!
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.9
Silberschatz, Galvin and Gagne ©2007
Algorithm for Process Pi
Legenda: j is the index of the other process.
Does this work? Why? Can it be made simpler?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.10
Silberschatz, Galvin and Gagne ©2007
Historical Aside: Dekker’s Algorithm
Why does it
work?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.11
Silberschatz, Galvin and Gagne ©2007
Aside: How Many Shared Variables?
Peterson’s mutex algorithm for two processes uses two boolean
variables and one integer variable.
How many variables does one need in order to achieve deadlockfree mutex?
Theorem (James Burns and Nancy Lynch, 1980) N binary
variables are necessary and sufficient to achieve deadlock-free
mutual exclusion amongst N processes.
Question: Is this good news?
But....one shared register is enough under timing assumptions!
See Michael Fischer’s classic algorithm.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.12
Silberschatz, Galvin and Gagne ©2007
Aside: Fischer’s Algorithm
Delay is chosen
to be larger than
the longest time it
takes to execute
an instruction.
(Simulate the
Uppaal demo
!
of Fischer’s
algorithm!)
End of
aside!
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.13
Silberschatz, Galvin and Gagne ©2007
Critical Section Using Locks
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.14
Silberschatz, Galvin and Gagne ©2007
Semaphore (Dijkstra)




Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: acquire() and release()
 Originally called P() (Proberen) and V() (Verhogen)
Can only be accessed via two indivisible (atomic) operations
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.15
Silberschatz, Galvin and Gagne ©2007
Semaphore as General Synchronization Tool


Counting semaphore – integer value can range
over an unrestricted domain
Binary semaphore – integer value can range only
between 0 and 1
 Also known as mutex locks
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.16
Silberschatz, Galvin and Gagne ©2007
Semaphore Implementation with no Busy waiting


With each semaphore there is an associated
waiting queue and a value (of type integer).
Two operations:
 block – place the process invoking the
operation on the appropriate waiting queue.
 wakeup – remove one of processes in the
waiting queue and place it in the ready
queue.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.17
Silberschatz, Galvin and Gagne ©2007
Semaphore Implementation with no Busy waiting (Cont.)

Implementation of acquire():

Implementation of release():
So, is the world of concurrency nice
and easy?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.18
Silberschatz, Galvin and Gagne ©2007
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 binary semaphores.
P0
P1
S.acquire();
Q.acquire();
Q.acquire();
S.acquire();
.
.
.
.
.
.
S.release();
Q.release();
Q.release();
S.release();
Starvation – indefinite blocking. A process may never be removed
from the semaphore queue in which it is suspended.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.19
Silberschatz, Galvin and Gagne ©2007
Classical Problems of Synchronization



Bounded-Buffer Problem
Readers and Writers Problem
Dining-Philosophers Problem
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.20
Silberschatz, Galvin and Gagne ©2007
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 with Java – 7th Edition, Nov 15, 2006
6.21
Silberschatz, Galvin and Gagne ©2007
Bounded-Buffer Problem
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.22
Silberschatz, Galvin and Gagne ©2007
Bounded-Buffer Problem
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.23
Silberschatz, Galvin and Gagne ©2007
Bounded Buffer Problem (Cont.)

The structure of the producer process
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.24
Silberschatz, Galvin and Gagne ©2007
Bounded Buffer Problem (Cont.)

The structure of the consumer process
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.25
Silberschatz, Galvin and Gagne ©2007
Bounded Buffer Problem (Cont.)

The Factory
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.26
Silberschatz, Galvin and Gagne ©2007
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 writer can access the shared data at the same
time.

Shared Data




Data set
Semaphore mutex initialized to 1. (Ensures mutex when readerCount
is updated.)
Semaphore db initialized to 1. (Mutex for writers, and prevents writers
from entering if db is being read.)
Integer readerCount initialized to 0.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.27
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem
Interface for read-write locks
How would you implement acquireReadLock and
releaseReadLock?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.28
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem
Methods called by writers.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.29
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem

The structure of a writer process
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.30
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem

The structure of a reader process
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.31
Silberschatz, Galvin and Gagne ©2007
Dining-Philosophers Problem (Dijkstra)

Shared data
 Bowl of rice (data set)

Semaphore chopStick [5] initialized to 1
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.32
Silberschatz, Galvin and Gagne ©2007
Dining-Philosophers Problem (Cont.)

The structure of Philosopher i:
Does this work?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.33
Silberschatz, Galvin and Gagne ©2007
Problems with Semaphores

Correct use of semaphore operations:



mutex.acquire() …. mutex.release()
mutex.wait() … mutex.wait()
Omitting of mutex.wait () or mutex.release()
(or both)
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.34
Silberschatz, Galvin and Gagne ©2007
Monitors (Brinch-Hansen, Hoare)


A high-level abstraction that provides a
convenient and effective mechanism for
process synchronization
Key property: Only one process may be active
within the monitor at a time
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.35
Silberschatz, Galvin and Gagne ©2007
Syntax of a Monitor
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.36
Silberschatz, Galvin and Gagne ©2007
Schematic view of a Monitor
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.37
Silberschatz, Galvin and Gagne ©2007
Condition Variables


Condition x, y;
Two operations on a condition variable:
 x.wait () – a process that invokes the
operation is suspended.
 x.signal () – resumes one of the
processes (if any) that invoked x.wait ()
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.38
Silberschatz, Galvin and Gagne ©2007
Monitor with Condition Variables
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.39
Silberschatz, Galvin and Gagne ©2007
Solution to Dining Philosophers
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.40
Silberschatz, Galvin and Gagne ©2007
Solution to Dining Philosophers (cont)

Each philosopher invokes the operations takeForks(i)
and returnForks(i) in the following sequence:
dp.takeForks (i)
EAT
dp.returnForks (i)
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.41
Silberschatz, Galvin and Gagne ©2007