Transcript Process Synchronization

Course Overview
Principles of Operating Systems







Introduction
Computer System
Structures
Operating System
Structures
Processes
Process Synchronization
Deadlocks
CPU Scheduling
© 2000 Franz Kurfess








Memory Management
Virtual Memory
File Management
Security
Networking
Distributed Systems
Case Studies
Conclusions
Process Synchronization 1
Chapter Overview
Process Synchronization




Motivation
Objectives
Concurrency
Synchronization Problems




Race Conditions
Critical Sections
Mutual Exclusion

Synchronization Patterns





Bounded Buffer
Readers-Writers
Dining Philosophers
Important Concepts and
Terms
Chapter Summary
Synchronization Methods



Hardware
Semaphores
Monitors
© 2000 Franz Kurfess
Process Synchronization 2
Motivation
 several
processes exist simultaneously in a system
 co-existing
processes may interfere with each other’s
execution

incorrect calculations,decrease in efficiency,deadlock
 processes
may cooperate within the same task
 the
activities of cooperating processes need to be
coordinated
 the
use of shared resources must be coordinated
 the separation of independent activities in processes
may lead to higher performance and more
convenient use
© 2000 Franz Kurfess
Process Synchronization 3
Objectives
 recognize
potential problems with the coordination
of activities for several processes (cooperation or
resource sharing)
 know how to use synchronization methods to
prevent problems
 be aware of the advantages and problems of
different synchronization methods
 be familiar with some fundamental synchronization
patterns
© 2000 Franz Kurfess
Process Synchronization 4
Process Synchronization
 the
activities of several concurrent processes are
synchronized
 access to common resources is coordinated
© 2000 Franz Kurfess
Process Synchronization 5
Importance of Synchronization
 prevention
and elimination of race conditions,
deadlocks and starvation
 serious
ramifications can occur otherwise (Therac 25)
 data
integrity/consistency
 collaboration
 efficiency
© 2000 Franz Kurfess
[Son 97]
[2] “An Investigation of the Therac-25 Accidents”
2
Process Synchronization
6
Concurrency
 several
processes are active at the same time
 between
their start and finish operations
 each process must make some progress
 multitasking,
multiprogramming
 process
multiplexing: the CPU switches between different
processes
 to the human user, these processes seem to be executed
simultaneously
 multiprocessing
 several
processes are executed simultaneously by
multiple processing elements (CPUs)
© 2000 Franz Kurfess
Process Synchronization 7
Resource Types
 shared:
several processes can utilize them
simultaneously
 exclusive: only one process at a time
 preemptible: can be taken away from a process,
given to another, and returned to the old process
 non-preemptible: one process must finish before
another can use the resource
© 2000 Franz Kurfess
Process Synchronization 8
Synchronization Problems
 race
conditions
 the
exact timing in the execution of concurrent processes
is critical
 critical
sections
 part
of a program that must be protected from interference
 usually resolved via mutual exclusion
 mutual
exclusion
 the
usage of resources by processes is restricted
 usually: only one process may use one instance of a
resource
© 2000 Franz Kurfess
Process Synchronization 9
Race Conditions
 the
final result of an activity involving shared
resources depends on the timing of processes
 caused by
 the
division of activities into several separate operations
(multitasking on a single CPU)
 simultaneous operations on shared resources in
multiprocessor systems
 race
conditions may happen only very rarely
 coincidence
of the interruption of an operation and
manipulation of shared resources by another process
 very difficult to detect and reproduce
© 2000 Franz Kurfess
Process Synchronization 10
Example Race Conditions
 procedure
for a character echo function
procedure echo;
var out, in: character;
begin
input (in, keyboard);
out := in;
output (out, display)
end.
© 2000 Franz Kurfess
[Stallings 98]
Process Synchronization 11
Example Race Conditions
processes A and B use the echo procedure
 implicitly shared variables out, in
 two
 no
restrictions on modifications of the variables
Process A
.
input (in, keyboard)
.
out := in;
output (out, display)
.
.
© 2000 Franz Kurfess
Process A
.
input (in, keyboard)
out := in;
.
output (out, display)
.
[Stallings 98]
Process Synchronization 12
Example Race Conditions
 problem
value of the shared variable in depends on the
exact timing between the two processes
 undesired results (the same value is echoed by both
processes)
 the
 solution
 control
access to shared resources
 here: protect shared variables by allowing only one
process at a time in the procedure echo
 echo is an example for a critical section
© 2000 Franz Kurfess
Process Synchronization 13
Handling of Race Conditions
 guarantee
the correct sequence of execution
through process synchronization mechanisms
 relies
on the correct use of these mechanisms by the
processes
 delay
the execution of one process
 improper,
but frequently used “hack”, often depending on
hardware specifics like processor speed
© 2000 Franz Kurfess
Process Synchronization 14
Critical Sections
 several
processes cooperate on a task by sharing
resources
 a critical section is a segment of code in which a
process utilizes some shared resources, and no
other process may interfere
 execution
of critical sections must be mutually exclusive in
time
 there may be different critical sections for different sets of
shared resources
a
protocol us required to guarantee that only one
process is in the critical section
© 2000 Franz Kurfess
Process Synchronization 15
Critical Section Diagram
repeat
other code
entry section
critical section
exit section
other code
until false;
© 2000 Franz Kurfess
Process Synchronization 16
Critical Section Requirements
 solutions
 mutual

for the critical section problem must satisfy
exclusion
if one process is executing in its critical section, then no other
processes can execute in their critical sections
 progress

processes wishing to enter their critical sections must come to a
decision eventually
 bounded

waiting
after a process has made a request to enter its critical section, only
a finite number of other processes may go first
 assumptions
 processes
execute at non-zero speed
 no assumptions on their relative speed
© 2000 Franz Kurfess
Process Synchronization 17
Two-Process Solutions
 critical
section problem with only two processes
 shared
Boolean or integer variables for synchronization
 Algorithm
 turn
1
variable to switch between the two processes
 Algorithm
2
 flag
variable for each process to indicate that it wants to
enter its critical section
 Algorithm
3
 combination
© 2000 Franz Kurfess
of the above two
Process Synchronization 18
Algorithm 1
 processes
P0 and P1 share a common variable
turn initialized to 0 or 1.
 if turn = 0 then process P0 enters critical section
 if turn = 1 then process P1 enters critical section
© 2000 Franz Kurfess
Process Synchronization 19
Diagram of Algorithm 1
repeat
other code
while turn <> i do no-op;
critical section
turn := j;
other code
until false;
© 2000 Franz Kurfess
Process Synchronization 20
Evaluation Algorithm 1
 Requirements
 mutual

satisfied?
exclusion
yes, only one process is allowed in its critical section
 progress

no, requires strict alternation
 bounded

waiting
yes, exactly one waiting period is required
© 2000 Franz Kurfess
Process Synchronization 21
Algorithm 2
array flag of two elements
flag[0] and flag[1]
indicates if a process wants to enter its critical
section
 an
flag[i] is true, then Pi is ready to enter its critical
section
 elements of the array flag are initialized to false
 if
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
30
Process Synchronization 22
Diagram of Algorithm 2
repeat
other code
flag[i] := true
while flag[j] do no-op;
critical section
flag[i] := false;
other code
until false;
© 2000 Franz Kurfess
Process Synchronization 23
Problems with Algorithm 2
What happens if P0 sets flag[0] to
true and P1 sets flag[1] to true before they
get into their while statement?
 Answer: Infinite loop within while statements
 Problem:
 depends
too much on the exact timing of the two
processes
 not very likely, but may happen
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
32
Process Synchronization 24
Evaluation Algorithm 2
 Requirements
 mutual

satisfied?
exclusion
yes, only one process is allowed in its critical section
 progress


no, endless loop in the entry sections possible if both processes
set their flags simultaneously
switching the order of the two instructions in the entry section is
not a solution, it will lead to mutual exclusion problems
 bounded

waiting
yes, a process sets flag in the exit section such that the other
can continue
© 2000 Franz Kurfess
Process Synchronization 25
Algorithm 3
 combination
of algorithms 1 & 2
 designed to meet all three mutual exclusion
requirements
 processes share two Boolean variables
 turn
 the
array flag
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
33
Process Synchronization 26
Diagram of Algorithm 3
repeat
other code
flag[i] := true;
turn := j;
while (flag[j] and turn = j)
do no-op;
critical section
flag[i] := false;
other code
until false;
© 2000 Franz Kurfess
Process Synchronization 27
Algorithm 3 - Visualization
Process i
flag[i]:= true
turn := j
executing ‘no-op’ until
the expression
(flag[j]
and turn = j)
becomes false
Process j
flag[j]:= true
turn := i
the expression
(flag[i]
and turn = i)
is false
enters critical section
flag[j] := false
enters critical section
flag[i] := false
© 2000 Franz Kurfess
Process Synchronization 28
Analysis of Algorithm 3
a
process Pi can enter its critical section only if
= false (the other process doesn’t want to
enter its critical section), or
 turn = i (the other process wants to enter its critical
section, but set the turn variable to process Pi )
 flag[j]
two processes cannot be both in their while
loops because turn can either be true or
false, but not both
 in its exit section, a process resets its flag variable,
thus permitting the other process entry
 the
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
36
Process Synchronization 29
Evaluation Algorithm 3
 Requirements
 mutual

satisfied?
exclusion
yes
 progress

yes
 bounded

waiting
yes
 algorithm
3 is a satisfactory solution for the twoprocess critical section problem
 how can this algorithm be extended to n processes?
© 2000 Franz Kurfess
Process Synchronization 30
Multiple-Process Critical Section
 critical
section problem with n processes
 one solution utilizes the “bakery algorithm”
 customers
pick a number when they enter the store, and
are served according to the value of their numbers
 each
process calculates a number when it wants to
enter the critical section
 based
 process
on the maximum number already assigned
with the lowest number gets served first
 If
two processes have the same number, then the process
with the lower process id gets served first
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
37
Process Synchronization 31
Bakery Algorithm
 designed
with distributed systems in mind
 relies on two arrays of variables
 choosing:

indicates that a process is calculating its number
 number:


array[0..n-1] of Boolean
array[0..n-1] of integer
used as identifier for processes
under certain circumstances, two processes may have the same
number (if they arrive at the same time)
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
38
Process Synchronization 32
Code Bakery Algorithm
repeat
choosing[i] := true;
number[i] := max(number[0],number[1],...,number[n-1]) + 1;
choosing[i] := false;
for j := 0 to n - 1
do begin
while choosing[j] do no-op;
while number[j] <> 0
and (number[j],j) < (number[i],i) do no-op;
end;
critical section
number[i] := 0;
other code
until false;
© 2000 Franz Kurfess
40
Process Synchronization 33
Mutual Exclusion
 requires
that only one process performs operations
on shared resources
 if two processes attempt to access a shared
resource simultaneously, one will have to wait
 necessary for the protection of critical sections
© 2000 Franz Kurfess
Process Synchronization 34
Handling Mutual Exclusion
 protect
access to resources through synchronization
mechanisms
 implicit synchronization for many cases through the
use of system calls
 not
sufficient, since many system calls are reentrant
© 2000 Franz Kurfess
Process Synchronization 35
Implementing Mutual Exclusion
 hardware
 special
instructions
 OS
 data
structures and operations provided by the OS, e.g.
via system calls
 programming
 constructs
language
at the language level (e.g. rendezvous in Ada)
 application
 application
 all
programmer must take care of it
solutions usually involve critical sections
© 2000 Franz Kurfess
Process Synchronization 36
H/W Mutual Exclusion
 special
machine instructions that do two steps
indivisibly
 test_and_set:
test a value; if it is false set it to true,
else leave it as false
 exchange: swap the values of two variables
test_and_set
while (test_and_set(lock))
do no-op;
critical section
lock := false;
exchange
key := true
repeat
exchange(lock, key)
until (key = false);
critical section
lock := false;
© 2000 Franz Kurfess
Process Synchronization 37
Characteristics
 hardware-based
mutual exclusion
 advantages
 can
be used by a single- or multi-processor systems (with
shared memory)
 simple, easy to verify
 supports multiple critical sections
 disadvantages
 often
busy waiting is used
 starvation is possible
 deadlock is possible (especially with priorities)
© 2000 Franz Kurfess
Process Synchronization 38
Disabling Interrupts
 interrupts
are disabled during the time period when
mutual exclusion is required
 without interrupts no process switching can occur
 somewhat dangerous: one process can hold up the
whole system
 endless
loop
 waiting for resources
 used
in special-purpose systems with limited
hardware
© 2000 Franz Kurfess
Process Synchronization 39
OS Mutual Exclusion
 mechanisms
to handle mutual exclusion are
provided by the operating system
 semaphores,
mutexes, monitors, rendezvous, etc.
 available
to user processes via system calls
 provided in most modern OSs
© 2000 Franz Kurfess
Process Synchronization 40
Programming Language
Mutual Exclusion
 mutual
exclusion mechanisms are built into the
programming language
 rendezvous
 often
in Ada, monitors in Pascal/Modula
relies implicitly on OS mechanisms
© 2000 Franz Kurfess
Process Synchronization 41
Application Mutual Exclusion
 implemented
by the application programmer
 difficult to do right
 frequently practically impossible to test sufficiently
 very inefficient
 usually
© 2000 Franz Kurfess
relies on busy waiting
Process Synchronization 42
Dangers of Mutual Exclusion
 solutions
to the mutual exclusion problem
may lead to
 starvation
 deadlock
 inefficiency
© 2000 Franz Kurfess
Process Synchronization 43
Starvation
 indefinite
postponement of a process
 a process never gets a resource because the
resource is allocated to other processes
 higher
priority
 consequence of scheduling algorithm
 frequent
solution: aging
 the
longer a process waits for a resource, the higher its
priority until it eventually has the highest priority among
the competing processes
© 2000 Franz Kurfess
Process Synchronization 44
Deadlock
 several
processes are waiting for an event that
never occurs because it only can be caused by one
of the waiting processes
 example:
process A waits for process B, and process B
waits for process A
 in
real life, deadlock is usually resolved by applying
politeness or common sense;
processes don’t have common sense, they stick to
their programs
© 2000 Franz Kurfess
Process Synchronization 45
Example Deadlocks
 studying
students: both students need the textbook
and the course notes to study, but there is only one
copy of each
 consider the following situation:






Student A
get coursenotes
get textbook
study
release textbook
release coursenotes
© 2000 Franz Kurfess
Student B
get textbook
get coursenotes
study
release coursenotes
release textbook
Process Synchronization 46
Synchronization Methods
 hardware
 semaphores
 monitors
© 2000 Franz Kurfess
Process Synchronization 47
Hardware
on special instructions like test_and_set,
exchange
 based
 often
in combination with interrupts
 sometimes used as basis for OS synchronization
mechanisms
© 2000 Franz Kurfess
Process Synchronization 48
Semaphores
 used
to solve synchronization problems among n
processes
 fundamental
synchronization tool used in many operating
systems
 integer
variable that can be accessed only via two
atomic operations
 wait
 signal
 frequently
 mutex
[Son 97]
© 2000 Franz Kurfess
used for mutual exclusion
as special semaphore
[Silberschatz & Galvin, 1998]
2
Process Synchronization 49
Semaphore Usage - Example
 goal:
force P2 to execute after P1
 common semaphore synch to synchronize the
operations of the two concurrent processes
 wait,
signal utilized to delay P2 until P1 is done
 synch initialized to 0
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
5
Process Synchronization 50
Example Semaphore
P1
process 1 statements
signal(synch);
done executing
P2
since synch = 0,
must stay idle until
signal from P1
wait(synch);
received signal from P1
process 2 statements
© 2000 Franz Kurfess
6
Process Synchronization 51
Semaphore mutex
repeat
other code
wait(mutex);
critical section
signal(mutex);
other code
until false;
© 2000 Franz Kurfess
Process Synchronization 52
Busy Waiting
 if
P2 has to wait for P1, P2 loops continuously until
P1 is done
 Most mutual exclusion solutions result in “busy
waiting”
 Solution: P2 blocks itself; “wakes up” via wakeup
operation
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
8
Process Synchronization 53
Analysis
 each
semaphore has an integer value and a list of
associated processes
 when a process blocks itself on a semaphore, it is
added to a queue of waiting processes
 The signal operation on a semaphore removes a
process from the queue and wakes the process up
© 2000 Franz Kurfess
Process Synchronization 54
Declaration and Operations
type semaphore = record
value: integer;
L: list of process;
end;
wait(S): S.value := S.value - 1;
if S.value < 0
then begin -- add this process to S.L;
block;
end;
signal(S): S.value := S.value + 1;
if S.value < = 0
then begin -- remove next process from S.L;
wakeup(P);
end;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 55
Critical Sections and Semaphores
 operations
on semaphores must be atomic:
 we
must ensure that no two processes can execute wait
and signal on the same semaphore at the same time
 uni-processor
system
 hardware
support such that transactions are atomic
 utilize interrupts during the time wait and signal are
executing
 multiprocessor
system
 hardware
support is expensive for multiple CPUs
 employ software algorithms if hardware instructions are
not available
© 2000 Franz Kurfess
Process Synchronization 56
Deadlock with Semaphores
 semaphores
must be used with care:
P0
P1
wait(S);
wait(Q);
wait(Q);
wait(S);
P0 is waiting for P1 to execute signal(Q)
P1 is waiting for P0 to execute signal(S)
Both processes are in a deadlock!
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 57
Binary Semaphores
 Binary
semaphores - semaphores in which their
integer values can only be either 0 or 1
 used
by 2 or more processes to ensure only one can enter
critical section
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
16
Process Synchronization 58
Example Semaphores
 Three
processes all share a resource on which
 one
draws an A
 one draws a B
 one draws a C
 Implement
a form of synchronization so that A B C
appears in this sequence
Process A
Process B
Process C
think();
draw_A();
think();
draw_B();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 59
Example Semaphores
no semaphores
A
B
think();
draw_A();
think();
draw_B();
?
C
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 60
Example Semaphores
no semaphores
A
B
think();
draw_A();
think();
draw_B();
C
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 61
Example Semaphores
no semaphores
A
B
think();
draw_A();
think();
draw_B();
A
C
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 62
Example Semaphores
no semaphores
A
B
think();
draw_A();
think();
draw_B();
C
C
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 63
Example Semaphores
no semaphores
A
B
think();
draw_A();
think();
draw_B();
B
C
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 64
Example Semaphores
Semaphore b = 0, c = 0;
Process A
Process B
Process C
think();
draw_A();
b.signal();
b.wait();
think();
draw_B();
c.signal();
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 65
Example Semaphores
Semaphore
A
think();
draw_A();
b.signal();
b = 0,
c = 0;
B
b.wait();
think();
draw_B();
c.signal();
C
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 66
Example Semaphores
Semaphore
A
think();
draw_A();
b.signal();
b = -1,
c = -1;
B
b.wait();
think();
draw_B();
c.signal();
C
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 67
Example Semaphores
Semaphore
A
think();
draw_A();
b.signal();
b = 0,
c = -1;
A
B
b.wait();
think();
draw_B();
c.signal();
C
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 68
Example Semaphores
Semaphore
A
think();
draw_A();
b.signal();
b = 0,
c = 0;
B
B
b.wait();
think();
draw_B();
c.signal();
C
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 69
Example Semaphores
Semaphore
A
think();
draw_A();
b.signal();
b = 0,
c = 0;
C
B
b.wait();
think();
draw_B();
c.signal();
C
c.wait();
think();
draw_C();
© 2000 Franz Kurfess
Process Synchronization 70
Monitors
a
high level synchronization construct
 programmer
- defined operators
 access
to internal data structures only via special
procedures
 provides a software solution to synchronization
problems
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
2
Process Synchronization 71
Properties of Monitors
 ensures
that only one process at a time can be
active within the monitor
 programming language construct
 monitor
procedures treated differently by the compiler
 compiler
and OS are responsible for mutual
exclusion, not the programmer
 less
prone to errors than semaphores
 somewhat
© 2000 Franz Kurfess
limited in its simple form
Process Synchronization 72
Monitor Diagram
shared data
...
entry queue
operations
initialization
code
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 73
Monitor Syntax - 1
type monitor - name = monitor
variable declarations
procedure entry P1 (...);
begin ... end;
procedure entry P2 (...);
begin ... end;
.
.
procedure entry Pn (...);
begin ... end;
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
5
Process Synchronization 74
Monitor Syntax - 2
begin
initialization code;
end.
{ The representation of a monitor type cannot be used
directly by various processes }
{ This supports local variable usage }
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
6
Process Synchronization 75
A Problem with Monitors
 Problem:
need a way for processes to block
themselves when they cannot proceed
 Solution: condition variables
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
7
Process Synchronization 76
Condition Variables
 variable
that can be used with two operations:
 x.wait
suspends the process until it is invoked by
another process, and
 x.signal releases exactly one process from the
affiliated waiting queue
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
8
Process Synchronization 77
Monitor Diagram
shared data
x
y
z
condition variable queues
...
entry queue
operations
initialization
code
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 78
Monitor Drawbacks
 only
usable in a few programming languages
 solves mutual exclusion problem only for CPUs that
all have access to common memory; not designed
for distributed systems
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
23
Process Synchronization 79
Synchronization Patterns
 bounded
buffer
 readers-writers
 dining philosophers
© 2000 Franz Kurfess
Process Synchronization 80
Bounded Buffer
 also
known as the “consumer-producer” problem
 two processes (one producer, one consumer) share
a common, fixed-size buffer
 producer places information into the buffer
 consumer takes it out
© 2000 Franz Kurfess
Process Synchronization 81
Diagram
Producer:
16
46
27
67
Consumer:
16
© 2000 Franz Kurfess
Process Synchronization 82
Problem Producer-Consumer
 the
producer wants to place a new item into the
buffer, but the buffer is already full
 consumer wants to consume an item, but the buffer
is empty
 Solution: producer/consumer goes to sleep, wakes
up when the consumer has emptied one or more
items, or when the producer has produced items
 vice-versa
© 2000 Franz Kurfess
(if buffer is empty, consumer goes to sleep)
Process Synchronization 83
Implications
 Race
conditions may occur
 wakeup
call might be lost
 producer will eventually fill buffer and then go to sleep
 consumer will also sleep
 both will sleep forever
© 2000 Franz Kurfess
Process Synchronization 84
Solution Techniques
 Semaphores
 Event
Counters
 Monitors
 Message-Passing
© 2000 Franz Kurfess
Process Synchronization 86
Semaphore Solution
Producer Process
repeat
...
-- produce an item in nextp
...
wait(empty);
wait(mutex);
...
-- add nextp to buffer
...
signal(mutex);
signal(full);
until false;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 87
Semaphore Solution
Consumer Process
repeat
wait(full);
wait(mutex);
...
-- remove an item from buffer to nextc
...
signal(mutex);
signal(empty);
...
-- consume the item in nextc
...
until false;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 88
Semaphore Solution
Producer Process
Consumer Process
-- produce an item in nextp
wait(empty);
wait(mutex);
-- add nextp to buffer
signal(mutex);
signal(full);
producer done!
© 2000 Franz Kurfess
wait(full);
wait(mutex);
-- remove an item from
buffer to nextc
signal(mutex);
signal(empty);
-- consume the item in nextc
consumer done!
[Son 97]
Process Synchronization 89
Readers-Writers
 concurrent
processes share a file, record, or other
resources
 some may read only (readers), some may write
(writers)
 two concurrent reads have no adverse effects
 problems if
 concurrent
reads and writes
 multiple writes
© 2000 Franz Kurfess
Process Synchronization 90
Readers-Writers Diagram
P1
{read}
P2
{read}
P1
{read}
P2
{write}
File
File
No problem
Problem!
© 2000 Franz Kurfess
[Son 97]
Process Synchronization 91
Nature of Problem
 race
conditions may occur if the resource is modified
by two processes simultaneously
 Solution: mutual exclusion techniques
 may
result in starvation, deadlock
97]Kurfess
© 2000[Son
Franz
[Silberschatz & Galvin, 1998]
4
Process Synchronization
92
Solution via Semaphores
 two
semaphores are used
 mutex,
 readers
have priority over writers
 writers
 mutual
rc - counter
must wait until readers are done
exclusion is accomplished
97]Kurfess
© 2000[Son
Franz
[4] "Modern Operating Systems"
7
Process Synchronization
93
Another Solution via Semaphores
Reader Process:
wait(mutex);
readcount := readcount + 1;
Writer Process:
if readcount = 1
wait(wrt);
then wait(wrt);
...
signal(mutex);
-- writing is performed
...
...
-- reading is performed
signal(wrt);
...
wait(mutex);
readcount := readcount - 1;
if readcount = 0
then signal(wrt);
signal(mutex);
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 94
Dining Philosophers
 five
philosophers sit at a round table - thinking and
eating
 each philosopher has one chopstick
 five
a
chopsticks total
philosopher needs two chopsticks to eat
 philosophers
 no
must share chopsticks to eat
interaction occurs while thinking
© 2000 Franz Kurfess
Process Synchronization 95
Diagram
P1
P2
P5
P3
P4
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
3
Process Synchronization 96
Nature of Problem
 Problem:
 starvation

a philosopher may never get the two chopsticks necessary to eat
 deadlocks

two neighboring philosophers may try to eat at same time
 Solution:
 utilize
semaphores to prevent deadlocks and/or starvation
[Son 97]
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
4
Process Synchronization 97
Faulty Solution
var chopstick: array [0..4] of semaphore;
repeat
wait(chopstick[i]);
wait(chopstick[i + 1 mod 5]);
...
-- eat
...
signal(chopstick[i]);
signal(chopstick[i + 1 mod 5]);
...
-- think
...
until false;
© 2000 Franz Kurfess
[Silberschatz & Galvin, 1998]
Process Synchronization 98
Analysis of Previous Solution
 Each
chopstick is represented by a semaphore
 Advantages

guarantees that no two neighbors will attempt to eat at the
same time
 Problems

possibility of creating a deadlock

if all philosophers try to eat at same time
© 2000 Franz Kurfess
Process Synchronization 99
Outline of a Correct Solution
 One
semaphore per philosopher
 must solve deadlock and starvation problem
 deadlock solution:
a
philosopher is allowed to pick up chopsticks only if both
are available
 this requires careful coordination (e.g. critical sections)
 does not automatically resolve starvation
[Son 97]
© 2000 Franz Kurfess
[4] "Modern Operating Systems"
12
Process Synchronization 100
Important Concepts and Terms














binary semaphore
bounded buffer problem
bounded waiting
concurrency
condition variable
consumer
exchange instruction
integer semaphore
critical section
deadlock
dining philosophers
monitor
mutex
mutual exclusion
© 2000 Franz Kurfess














producer
progress
protected variable
race condition
readers
remote procedure call
rendezvous
semaphore
signal operation
starvation
synchronization
test-and-set instruction
wait operation
writers
Process Synchronization 101
Chapter Summary
 the
synchronization of processes is one of the key
problems in operating systems
 cooperation
between processes
 sharing of resources
 synchronization
applies to threads as well
 race conditions, critical sections, and mutual
exclusion must be resolved
 hardware, OS, programming language, and
application program solutions are available
 often
trade-off between efficiency, safety, ease of use
© 2000 Franz Kurfess
Process Synchronization 102