Outline V22.
0202-001 Computer Systems Organization II (Honors)
(Introductory Operating Systems)
Process synchronization
Classical synchronization problems
Mutual exclusion, Sequencing, Producer consumer, Readers-writers, Dining philosophers
Announcements
Lab 2 due Feb 25th, demos on Feb 27th, 28th
Defer extra credit part (priority scheduler) to Lab 3
Lecture 7 Classical Synchronization Problems February 20, 2002
A larger synchronization problem: (if time permits) Language support for synchronization
Critical regions Monitors Message passing
[ Silberschatz/Galvin/Gagne: Sections 7.5 7.8]
2/20/2002 2
(Review) Classical Synchronization Problems
1. Mutual Exclusion 2. Sequencing 3. Bounded Buffer (also referred to as the Producer-Consumer problem) 4. Readers-Writers: Multiple processes access a shared data object X
any number of readers can access X at the same time no writer can access it at the same time as a reader or another writer variations:
reader-priority: a reader must not wait for a writer writer-priority: a writer must not wait for a reader
Mutual Exclusion and Sequencing Using Semaphores
Mutual exclusion: Semaphore initialized to 1
P(S); CRITICAL SECTION V(S);
Sequencing: Semaphore initialized to 0
process 1 process 2 B(); V(S);
5. Dining Philosophers
5 philosophers, 5 chopsticks
to eat requires two chopsticks
P(S); A();
philosophers alternate between thinking and eating issues: deadlock, starvation, fairness OS examples: simultaneous use of multiple resources
2/20/2002 3 2/20/2002 4
Bounded-buffer Using Semaphores
Three semaphores
mutex: provide mutual exclusion between processes (initial value = 1) empty: count the number of empty slots (initial value = N) full: count the number of full slots (initial value = 0) Producer(s):
repeat // produce item in nextp P( empty ); P( mutex ); // add nextp to buffer V( mutex ); V( full ); until false;
Readers-Writers Using Semaphores
To allow multiple readers, synchronize only the first/last reader with writers Reader(s) Writer(s)
Consumer(s):
repeat P( full ); P( mutex ); // remove item to nextc V( mutex ); V( empty ); // consume item in nextc until false;
5
P(x); rcount := rcount + 1; if (rcount == 1) then P(wsem); V(x); P(wsem); WRITE V(wsem);
stream of readers can starve writers
READ
P(x); rcount := rcount - 1; if (rcount == 0) then V(wsem);
V(x);
can release either waiting readers or writers
2/20/2002
2/20/2002
Readers-Writers Using Semaphores: Writer-Priority
Have a writer block out subsequent readers (same as readers block out writers) Reader
readers can queue up
P(rsem); preventing a waiting P(x); writer from setting rsem rcount := rcount + 1; if (rcount == 1) then P(wsem); V(x); V(rsem); READ P(y); wcount := wcount + 1; if (wcount == 1) then P(rsem); V(y); P(wsem); WRITE V(wsem); P(y); wcount := wcount - 1; if (wcount == 0) then V(rsem);
V(y);
Readers-Writers Using Semaphores: Writer-Priority (2)
Reader
P(z); P(rsem); P(x); rcount := rcount + 1; if (rcount == 1) then P(wsem); V(x); V(rsem); V(z); READ
Writer
Writer
P(y); wcount := wcount + 1; if (wcount == 1) then P(rsem); V(y); P(wsem); WRITE V(wsem); P(y); wcount := wcount - 1; if (wcount == 0) then V(rsem);
V(y);
P(x); rcount := rcount - 1; if (rcount == 0) then V(wsem);
V(x);
P(x); rcount := rcount - 1; if (rcount == 0) then V(wsem);
V(x);
2/20/2002
2/20/2002
Dining Philosophers Using Semaphores
Philosopheri
P( chopstick[i] ); P( chopstick[i+1 mod 5] ); EAT V( chopstick[i] ); V( chopstick[i+1 mod 5] ); THINK
Dining Philosophers Using Semaphores - 2
mod 5)
Philosopher(j=i+1
P( chopstick[j] ); P( chopstick[j+1 mod 5] ); EAT V( chopstick[j] ); V( chopstick[j+1 mod 5] ); THINK
Philosopher(even
P( chopstick[i] ); P( chopstick[i+1 mod 5] ); EAT V( chopstick[i] ); V( chopstick[i+1 mod 5] ); THINK
i)
Philosopher(odd
i)
P( chopstick[i+1] mod 5 ); P( chopstick[i] ); EAT V( chopstick[i+1] mod 5 ); V( chopstick[i] ); THINK
Deadlock
a set of processes is in a deadlock state when every process in the set is waiting for an event that can be caused only by another process in the set details in Lectures 10 and 11.
2/20/2002 9
Alternate solutions
allow at most 4 philosophers to sit simultaneously at the table allow a philosopher to pick up chopsticks only if both are available
All of these solutions suffer from the possibility of starvation!
2/20/2002 10
A Larger Example: A Barbershop Problem
Example taken from
Operating Systems: Internals and Design Principles, 3rd Edition William Stallings, Prentice Hall, 1998
A Barbershop Problem (contd)
Entrance
Shop and sofa capacity
max_capacity (initial value = 20) sofa (initial value = 4)
Barber chair capacity
barber_chair (initial value = 3)
The problem: Orchestrating activities in a barbershop
3 chairs, 3 barbers, 1 cash register, waiting area: 4 customers on a sofa, plus additional standing room Fire codes limit total number of customers to 20 at a time A customer
Will not enter the shop if it is filled to capacity Takes a seat on the sofa, or stands if sofa is filled When a barber is free, the customer waiting longest on sofa is served The customer standing the longest takes up seat on the sofa When a customers haircut is finished, any barber can accept payment but because of the single cash register, only one payment is accepted at a time Barbers divide their time between cutting hair, accepting payment, and sleeping
Standing Room
Ensuring customers are in barber chair
cust_ready (initial value = 0)
barber waits for customer
finished (initial value = 0)
Sofa customer waits for haircut to finish
leave_b_chair (initial value = 0)
barber waits for chair to empty Barber chairs
Cash register
Paying and receiving
payment (initial value = 0)
cashier waits for customer to pay
Exit
receipt (initial value = 0)
customer waits for cashier to ack
11 2/20/2002
Coordinating barber functions
coord (initial value = 0)
wait for a barber resource to free up
12
2/20/2002
A Barbershop Problem (contd.)
Shop and sofa capacity
max_capacity (: = 20) sofa (: = 4)
A Barbershop Problem (contd.): Mutual Exclusion
Barber
P( cust_ready ); P( coord ); // cut hair V( coord ); V( finished ); // wait for customer to leave P( leave_b_chair ); // tell next customer to hop on V( barber_chair ); Shop and sofa capacity
max_capacity (: = 20) sofa (: = 4)
Customer
P( max_capacity ); // enter shop P( sofa ); // sit on sofa P( barber_chair ); // get up from sofa V( sofa ); // sit in barber chair V( cust_ready ); P( finished ); // leave barber chair V( leave_b_chair ); // pay V( payment ); P( receipt ); // exit shop V( max_capacity );
Customer
P( max_capacity ); // enter shop P( sofa ); // sit on sofa P( barber_chair ); // get up from sofa V( sofa ); // sit in barber chair V( cust_ready ); P( finished ); // leave barber chair V( leave_b_chair ); // pay V( payment ); P( receipt ); // exit shop V( max_capacity );
Barber
P( cust_ready ); P( coord ); // cut hair V( coord ); V( finished ); // wait for customer to leave P( leave_b_chair ); // tell next customer to hop on V( barber_chair );
Barber chair capacity
barber_chair (: = 3)
Barber chair capacity
barber_chair (: = 3)
Ensuring customers are in barber chair
cust_ready (: = 0) finished (: = 0) leave_b_chair (: = 0)
Ensuring customers are in barber chair
cust_ready (: = 0) finished (: = 0) leave_b_chair (: = 0)
Paying and receiving
payment (: = 0) receipt (:= 0)
Cashier
P( payment ); P( coord ); // accept payment V( coord ); V( receipt );
13
Paying and receiving
payment (: = 0) receipt (:= 0)
Cashier
P( payment ); P( coord ); // accept payment V( coord ); V( receipt );
14
Coordinating barber functions
coord (:= 0)
Coordinating barber functions
coord (:= 0)
2/20/2002
2/20/2002
A Barbershop Problem (contd.): Bounded Buffer
Shop and sofa capacity
max_capacity (: = 20) sofa (: = 4)
A Barbershop Problem (contd.): Sequencing
Shop and sofa capacity
max_capacity (: = 20) sofa (: = 4)
Customer
P( max_capacity ); // enter shop P( sofa ); // sit on sofa P( barber_chair ); // get up from sofa V( sofa ); // sit in barber chair V( cust_ready ); P( finished ); // leave barber chair V( leave_b_chair ); // pay V( payment ); P( receipt ); // exit shop V( max_capacity );
Barber
P( cust_ready ); P( coord ); // cut hair V( coord ); V( finished ); // wait for customer to leave P( leave_b_chair ); // tell next customer to hop on V( barber_chair );
Customer
P( max_capacity ); // enter shop P( sofa ); // sit on sofa P( barber_chair ); 4 // get up from sofa V( sofa ); // sit in barber chair V( cust_ready ); P( finished ); // leave barber chair V( leave_b_chair ); // pay V( payment ); P( receipt ); // exit shop V( max_capacity );
1
Barber
P( cust_ready ); P( coord ); // cut hair V( coord ); V( finished );
3
Barber chair capacity
barber_chair (: = 3)
Barber chair capacity
barber_chair (: = 3)
Ensuring customers are in barber chair
cust_ready (: = 0) finished (: = 0) leave_b_chair (: = 0)
Ensuring customers are in barber chair
cust_ready (: = 0) finished (: = 0) leave_b_chair (: = 0)
// wait for customer to leave P( leave_b_chair ); // tell next customer to hop on V( barber_chair );
Paying and receiving
payment (: = 0) receipt (:= 0)
Cashier
P( payment ); P( coord ); // accept payment V( coord ); V( receipt );
15
Paying and receiving
payment (: = 0) receipt (:= 0)
Cashier
P( payment ); P( coord ); // accept payment V( coord ); V( receipt );
16
Coordinating barber functions
coord (:= 0)
Coordinating barber functions
coord (:= 0)
2/20/2002
2/20/2002
A Barbershop Problem (contd.)
Some problems with the current solution
since all customers are waiting on the same semaphore (finished), the one who started earliest is released when a barber does V( finished)
even if the haircut is not done
Outline
Announcements
Lab 2 due Feb 25th, demos on Feb 27th, 28th
Defer extra credit part (priority scheduler) to Lab 3
similar problem with the cashier and the pay and receipt semaphores
cashier may accept money from one customer and release another
Process synchronization
Classical synchronization problems
Mutual exclusion, Sequencing, Producer consumer, Readers-writers, Dining philosophers
a customer needs to wait on the sofa even if a barber chair is free
All of these can be solved using additional semaphores
A larger synchronization problem (if time permits) Language support for synchronization
Critical regions Monitors Message passing
[ Silberschatz/Galvin/Gagne: Sections 7.5 7.8]
2/20/2002 17 2/20/2002 18
Limitations of Semaphores
No abstraction and modularity
a process that uses a semaphore has to know which other processes use the semaphore, and how these processes use the semaphore a process cannot be written in isolation why?
Limitations of Semaphores (contd.)
Very easy to write incorrect code
changing the order of P and V
can violate mutual exclusion requirements
V( mutex ); CODE; P( mutex ); instead of P( mutex ); CODE; V( mutex );
Consider sequencing between three processes
P1, P2, P3, P1, P2, P3,
P1 P( sem1 ); // do stuff V( sem2 ); P2 P( sem2 ); // do stuff V( sem3 ); P3 P( sem3 ); // do stuff V( sem1 );
can cause deadlock
P( seq ); instead of V( seq );
similar problems with omission
What happens if there are only two processes? What happens if you want to use this solution for four processes?
2/20/2002 19
Extremely difficult to verify programs for correctness Need for still higher-level synchronization abstractions!
2/20/2002 20
Language Support
Helps simplify expression of synchronization
more convenient more secure less buggy
Conditional Critical Regions
A high-level language declaration
informally, it can be used to specify that while a statement S is being executed, no more than one process can access a distinguished variable v notation
var v: shared t; region v when B do S; v is shared and of type t
can only be accessed within a region statement
We shall examine two fundamental constructs
conditional critical regions monitors
These constructs can be found in several concurrent languages
Communicating Sequential Processes (CSP) critical regions Concurrent Pascal monitors object-oriented languages: Modula-2, Concurrent C, Java Ada83, Ada95
B is a Boolean expression S is a statement
can be a compound statement
Semantics
A process is guaranteed mutually exclusive access to the region v Checking of B and entry into the region happens atomically
21 2/20/2002 22
2/20/2002
Conditional Critical Regions: Benefits
Bounded-buffer producer/consumer
var buffer : shared record pool: array [0..n-1] of item; count, in, out: integer; end; Producer: region buffer when count < n do begin pool[in] := nextp; in := (in + 1) mod n; count := count + 1; end; Consumer: region buffer when count > 0 do begin nextc := pool[out]; out := (out + 1) mod n; count := count - 1; end;
Conditional Critical Regions: Implementation
var mutex: semaphore; P( mutex ); while not B do begin try-and-enter; end; S; leave-critical-region; var delay: semaphore; var count: integer; count++ ; V( mutex ); P( delay ); // check condition if ( not B ) if ( count > 1 ) // release another V( delay ); P( delay ); else V( mutex ); P( delay ); else count-- ; var first, second: semaphore; var fcount, scount: integer; fcount++ ; if ( scount > 0 ) V( second ); else V( mutex ); P( first ); fcount-- ; scount++ ; if ( fcount > 0 ) V( first ); else V( second ); P( second ); scount-- ;
Guards against simple errors associated with semaphores
e.g., changing the order of P and V operations, or forgetting to put one of them
Division of responsibility
the developer does not have to program the semaphore or alternate synchronization explicitly the compiler ``automatically'' plugs in the synchronization code using predefined libraries once done carefully, reduces likelihood of mistakes in designing the delicate synchronization code
if ( count > 0 ) then V( delay ); else V( mutex ); 2/20/2002
if ( fcount > 0 ) V( first ); else if ( scount > 0 ) V( second ); else V( mutex );
2/20/2002
23
24
Next Lecture (February 25th)
Language support for synchronization (contd)
Monitors Message passing
CPU Scheduling Reading
Silberschatz/Galvin/Gagne: Chapter 6
2/20/2002
25