SiIberschatz, GaIvin and Gagne 2009

Operating System Concepts - 8

th
Edition,
Chapter 6: Process
Synchronization
6.2
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
ModuIe 6: Process Synchronization
Background
The Critical-Section Problem
Peterson's Solution
Synchronization Hardware
Semaphores
6.3
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Objectives
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
6.4
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Background
Concurrent access to shared data may result in data
inconsistency
Maintaining data consistency requires mechanisms to
ensure the orderly execution of cooperating processes
6.5
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
The CriticaI-Section ProbIem
3 processes
each has a segment of code called criticaI section in which it may
change common var's, updating tables or lists, writing a file, ..
The goal : if one process is executing in its critical section,
no other process to be allowed to enter its critical section
Each process must request permission to enter $
this is implemented in entry section
6.6
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
The CriticaI-Section ProbIem
do
entry section
critical section
exit section
remainder section
while T E
6.
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
SoIution to CriticaI-Section ProbIem
. Mutual Exclusion - f process P
i
is executing in its critical section, then no
other processes can be executing in their critical sections
2. Progress - f 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 aiting - 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
6.8
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Peterson's SoIution
Two process solution
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 P
i
is ready!
t can not be guaranteed to work properly machine architecture
6.9
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
do
flag i T E
turn j
while flag j turn j
critical section
flag i F LSE
remainder section
while T E
Igorithm for Process P
i
6. 0
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Peterson's SoIution Satisfies equirements
. Mutual Exclusion Only process P
i
is executing in its critical section
P
j
can not enter its critical section
2. Progress - f no process is executing in its critical section and there exist
a process that wishes to enter its critical section flag , and turn can have
only one value or j then that process will enter the critical section next
and cannot be postponed indefinitely
3. Bounded aiting - Once a process is allowed to enter its C.S.
it will reset its flag F LSE in exit allowing the process 2 if ready
to enter its C.S. and p can't enter its C.S. until p 2 enters its C.S.
because p changed turn 2
6.
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Synchronization Hardware
ny solution to criticaI section probIem requires a simple tool
or a Iock
Modern computers provide special hardware instructions that allow
us to test and modify the content of a word atomically i.e. as a one
uninterrupted unit
Test ndSet lock and Semaphores are two examples of H tools
6. 2
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Test ndSet nstruction
efinition:
boolean Test ndSet boolean target
boolean rv target
target T E
return rv:
6. 3
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
SoIution using Test ndSet
Shared boolean variable lock., initialized to false.
Solution:
do
while Test ndSet lock
do nothing
critical section
lock F LSE
remainder section
while T E
6. 4
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Semaphores
Previous solution may be complicated to implement
Semaphore S integer variable accessed only through two standard
atomic operations : wait and signal
Less complicated
Can only be accessed via two indivisible atomic operations
wait S
while S
no-op
S--
signal S
S
6. 5
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Semaphores
Counting semaphore integer value can range over an unrestricted domain
counting semaphore can be used to control access
to shared resources, initialized to of resources
Binary semaphore integer value can range only between and ,
can be simpler to implement
lso known as mutex locks
Provides mutual exclusion
Semaphore mutex initialized to
do
wait mutex
Critical Section
signal mutex
remainder section
while T E
6. 6
SiIberschatz, GaIvin and Gagne 2009
Operating System Concepts - 8
th
Edition
Semaphores to Sync processes
Concurrently running processes P
,
P
2
executing statement S

first then S
2
int synch initialized to
S
signal synch P
wait synch
S
2
P
2