Transcript ch6b

Chapter 6(b): Synchronization
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
Silberschatz, Galvin and Gagne ©2007
Module 6: Process Synchronization
Semaphores
 Types of Semaphores
 Implementing Semaphores
 Deadlock
 Monitors
 Barriers
 Classic Syncrhonization Problems
 Synchronization in Linux
 Example: semaphores in pthreads

Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.2
Silberschatz, Galvin and Gagne ©2007
Semaphore





Synchronization tool that does not require busy waiting
Semaphore S – integer variable
Two standard operations modify S: acquire() and release()
 Originally called P() and V()
 from Dutch Proberen and Verhogen (Dijkstra)
 Also called down() and up()
 And even wait() and signal()
Higher-level abstraction, less complicated
Can only be accessed via two indivisible (atomic) operations
P(S) {
while(S ≤ 0)
;
S--;
}
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
V(S) {
S++;
}
6.3
Silberschatz, Galvin and Gagne ©2007
Semaphore Types


Counting semaphore – integer value can range
over an unrestricted domain
 Used for synchronization
Binary semaphore – integer value can range only
between 0 and 1; can be simpler to implement
 Used for mutual exclusion: known as a mutex
Process i
P(S);
Critical Section
V(S);
Remainder Section
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.4
Silberschatz, Galvin and Gagne ©2007
Semaphore Implementation




Must guarantee that no two processes can execute P () /
acquire () and V () / release () on the same semaphore
at the same time
Thus, implementation of these operations becomes the
critical section problem again, where the acquire and
release code are placed inside the critical section.
 Could now have busy waiting in critical section
implementation
 But if we know we can’t acquire semaphore, should
we busy wait and burn up the CPU?
Note that applications may spend lots of time in critical
sections and therefore this is not a good solution.
We’d like a semaphore that sleeps (or at least lets
someone else run)
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.5
Silberschatz, Galvin and Gagne ©2007
Semaphore Implementation with no Busy waiting



With each semaphore there is an associated
waiting queue. Each entry in a waiting queue
has two data items:
 value (of type integer)
 pointer to next record in the list
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.
Potential queuing policies: FIFO, LIFO, undef
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.6
Silberschatz, Galvin and Gagne ©2007
Semaphore Implementation with no Busy waiting (Cont.)

Implementation of acquire():

Implementation of release():
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.7
Silberschatz, Galvin and Gagne ©2007
Producer-Consumer Problem

Bounded buffer: size ‘N’


Producer process writes data to buffer


Access entry 0… N-1, then “wrap around” to 0 again
Must not write more than ‘N’ items more than consumer “ate”
Consumer process reads data from buffer

0
Should not try to consume if there is no data
1
N-1
In
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
Out
6.8
Silberschatz, Galvin and Gagne ©2007
Solving Producer-Consumer Problem


Solving with semaphores
 We’ll use two kinds of semaphores
 We’ll use counters to track how much data is in the buffer
 One counter counts as we add data and stops the producer if
there are N objects in the buffer
 A second counter counts as we remove data and stops a
consumer if there are 0 in the buffer
 Idea: since general semaphores can count for us, we don’t need
a separate counter variable
Why do we need a second kind of semaphore?
 We’ll also need a mutex semaphore
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.9
Silberschatz, Galvin and Gagne ©2007
Producer-Consumer Problem
Shared: Semaphores mutex, empty, full;
Init: mutex = 1; /* for mutual exclusion*/
empty = N; /* number empty buf entries */
full = 0;
/* number full buf entries */
Producer
Consumer
do {
...
// produce an item in nextp
...
P(empty);
P(mutex);
...
// add nextp to buffer
...
V(mutex);
V(full);
} while (true);
do {
P(full);
P(mutex);
...
// remove item to nextc
...
V(mutex);
V(empty);
...
// consume item in nextc
...
} while (true);
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.10
Silberschatz, Galvin and Gagne ©2007
Sample Implementation of Mutexes
Implementation of user-level thread mutex lock and unlock.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.11
Silberschatz, Galvin and Gagne ©2007
Common Errors with Semaphores
Process i
Process j
Process k
Process l
P(S)
CS
P(S)
V(S)
CS
V(S)
P(S)
CS
P(S)
If (something)
return;
CS
V(S)
A typo. Process
J won’t next
respect
Whoever
calls P() will freeze up.
mutual Iexclusion
even
the other
The
bugif might
be confusing because
A typo. Process
will get stuck
Someone
to release the
follow
the rules
that
othercorrectly.
process
couldforgot
be perfectly
(forever) theprocesses
second time
it does
the
semaphore
before
The
still, once
we’ve
done
two that’s the
correct
yet
onereturning!
you’ll
P() operation.Worse
Moreover,
every
othercode,
nextyou
caller
operations
this hung
way, other
see
when
usewill
theget stuck.
process will “extra”
freeze V()
up too
when trying
processes
might getdebugger
into the CS
to look at its state!
to enter the
critical section!
inappropriately!
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.12
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 semaphores initialized to 1
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.13
Silberschatz, Galvin and Gagne ©2007
Monitors


A high-level language
abstraction that
provides a convenient
and effective
mechanism for
process
synchronization
Only one process
may be active within
the monitor at a time
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.14
Silberschatz, Galvin and Gagne ©2007
Schematic view of a Monitor



Can think of a monitor
as one big lock for a
set of operations/
methods
In other words, a
language
implementation of
mutexes
What are the
advantages and
disadvantages of this
approach?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.15
Silberschatz, Galvin and Gagne ©2007
Producer-Consumer with Monitors
An outline of the
producer-consumer
problem with
monitors. Only one
monitor procedure
at a time is active.
The buffer has N
slots.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.16
Silberschatz, Galvin and Gagne ©2007
Producer-Consumer with Monitors (2)
An outline of the
producer-consumer
problem with
monitors. Only one
monitor procedure
at a time is active.
The buffer has N
slots.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.17
Silberschatz, Galvin and Gagne ©2007
Condition Variables




Condition x, y;
Two operations on a condition variable:
 wait () – a process that invokes the operation is
suspended.
 signal () / notify() – resumes one of processes (if
any) that invoked wait ()
Subtleties between condition variables and semaphores:
 Semaphores have memory: V() will increment the
semaphore, even if no one has called P()
 Condition variables do not: if no one is waiting for a
signal() / notify(), it is not saved
Condition variables in monitors:
 Calling wait() releases the monitor
 Returning from wait() re-acquires the monitor
 Does signal() release the monitor?
 Who runs after a signal() is called?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.18
Silberschatz, Galvin and Gagne ©2007
Monitor with Condition Variables
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.19
Silberschatz, Galvin and Gagne ©2007
Java Synchronization





Java provides synchronization at the language-level.
Each Java object has an associated lock.
This lock is acquired by invoking a synchronized
method.
This lock is released when exiting the synchronized
method.
Threads waiting to acquire the object lock are placed
in the associated entry set for the object lock.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.20
Silberschatz, Galvin and Gagne ©2007
Java Synchronization
Synchronized insert() and remove() methods
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.21
Silberschatz, Galvin and Gagne ©2007
Java Synchronization wait/notify()


When a thread invokes wait():
1. The thread releases the object lock;
2. The state of the thread is set to Blocked;
3. The thread is placed in the wait set for the object.
When a thread invokes notify():
1. An arbitrary thread T from the wait set is selected;
2. T is moved from the wait to the entry set;
3. The state of T is set to Runnable.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.22
Silberschatz, Galvin and Gagne ©2007
Java Synchronization



The call to notify() selects an arbitrary thread
from the wait set. It is possible the selected
thread is in fact not waiting upon the condition
for which it was notified.
The call notifyAll() selects all threads in the
wait set and moves them to the entry set.
In general, notifyAll() is a more conservative
strategy than notify().
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.23
Silberschatz, Galvin and Gagne ©2007
Barriers
Use of a barrier. (a) Processes approaching a barrier. (b) All
processes but one blocked at the barrier. (c) When the last
process arrives at the barrier, all of them are let through.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.24
Silberschatz, Galvin and Gagne ©2007
Classical Problems of Synchronization



Bounded-Buffer/Producer-Consumer Problem
Readers and Writers Problem
Dining-Philosophers Problem
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.25
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem



Courtois et al 1971
Models access to a database
 A reader is a thread that needs to look at the database but won’t change
it.
 A writer is a thread that modifies the database
Example: making an airline reservation
 When you browse to look at flight schedules the web site is acting as a
reader on your behalf
 When you reserve a seat, the web site has to write into the database to
make the reservation
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.26
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Problem


Many threads share an object in memory
 Some write to it, some only read it
 Only one writer can be active at a time
 Any number of readers can be active simultaneously
Key insight: generalizes the critical section concept

One issue we need to settle, to clarify problem statement.
 Suppose that a writer is active and a mixture of readers and writers now
shows up. Who should get in next?
 Or suppose that a writer is waiting and an endless of stream of readers
keeps showing up. Is it fair for them to become active?

We’ll favor a kind of back-and-forth form of fairness:
 Once a reader is waiting, readers will get in next.
 If a writer is waiting, one writer will get in next.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.27
Silberschatz, Galvin and Gagne ©2007
Readers-Writers
Shared variables: Semaphore mutex, wrl;
integer rcount;
Init: mutex = 1, wrl = 1, rcount = 0;
Writer
do {
P(wrl);
...
/*writing is performed*/
...
V(wrl);
} while(TRUE);
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.28
Reader
do {
P(mutex);
rcount++;
if (rcount == 1)
P(wrl);
V(mutex);
...
/*reading is performed*/
...
P(mutex);
rcount--;
if (rcount == 0)
V(wrl);
V(mutex);
} while(TRUE);
Silberschatz, Galvin and Gagne ©2007
Readers-Writers Notes





If there is a writer
 First reader blocks on wrl
 Other readers block on mutex
Once a reader is active, all readers get to go through
 Trick question: Which reader gets in first?
The last reader to exit signals a writer
 If no writer, then readers can continue
If readers and writers waiting on wrl, and writer exits
 Who gets to go in first?
Why doesn’t a writer need to use mutex?
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.29
Silberschatz, Galvin and Gagne ©2007
Does this work as we hoped?




If readers are active, no writer can enter
 The writers wait doing a P(wrl)
While writer is active, nobody can enter
 Any other reader or writer will wait
But back-and-forth switching is buggy:
 Any number of readers can enter in a row
 Readers can “starve” writers
With semaphores, building a solution that has the desired back-andforth behavior is really, really tricky!
 We recommend that you try, but not too hard…
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.30
Silberschatz, Galvin and Gagne ©2007
Dining-Philosophers Problem

Shared data




Bowl of rice (data set), 5 philosophers, 5 chopsticks
Each philosopher alternates between thinking and eating
Each philosopher needs 2 chopsticks to eat
Semaphore chopStick [5] initialized to 1
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.31
Silberschatz, Galvin and Gagne ©2007
Dining-Philosophers Solution

Philosopher i:
do {
P(chopstick[i])
P(chopstick[(i+1) % 5])
…
eat
…
V(chopstick[i]);
V(chopstick[(i+1) % 5]);
…
think
…
} while (1);
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.32
Silberschatz, Galvin and Gagne ©2007
One Possible Solution



Introduce state variable
 enum {thinking, hungry, eating}
Philosopher i can set the variable state[i] only if
neighbors not eating:
 (state[(i+4)%5] != eating) and
 (state[(i+1)%5] != eating)
Also, need to declare semaphore self, where philosopher
i can delay itself.
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.33
Silberschatz, Galvin and Gagne ©2007
One Possible Solution
Shared: int state[5], semaphore s[5], semaphore mutex;
Init: mutex = 1; s[i] = 0, state[i] = thinking, for all i=0 .. 4;
take_chopstick(i) {
P(mutex);
Philosopher i
state[i] = hungry;
test(i);
do {
V(mutex);
take_chopstick(i);
P(s[i]);
eat();
put_chopstick(i); }
think();
put_chopstick(i) {
} while(true);
P(mutex);
state[i] = thinking;
test((i+1)%N);
test((i-1+N)%N);
V(mutex);
}
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.34
test(i) {
if(state[i] == hungry
&& state[(i+1)%N] != eating
&& state[(i-1+N)%N != eating)
{
state[i] = eating;
V(s[i]);
}
Silberschatz, Galvin and Gagne ©2007
Synchronization Examples




Solaris
Windows XP
Linux
Pthreads
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.35
Silberschatz, Galvin and Gagne ©2007
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
Uses condition variables and readers-writers locks
when longer sections of code need access to data
Uses turnstiles to order the list of threads waiting to
acquire either an adaptive mutex or reader-writer
lock
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.36
Silberschatz, Galvin and Gagne ©2007
Windows XP Synchronization




Uses interrupt masks to protect access to global
resources on uniprocessor systems
Uses spinlocks on multiprocessor systems
Also provides dispatcher objects which may act
as either mutexes and semaphores
Dispatcher objects may also provide events
 An event acts much like a condition variable
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.37
Silberschatz, Galvin and Gagne ©2007
Linux Synchronization


Linux:
 disables interrupts to implement short
critical sections (on uniprocessors)
Linux provides:
 semaphores
 spin locks
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.38
Silberschatz, Galvin and Gagne ©2007
Pthreads Synchronization



Pthreads API is OS-independent
It provides:
 mutex locks
 condition variables
Non-portable extensions
include:
 read-write locks
 spin locks
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.39
Silberschatz, Galvin and Gagne ©2007
Mutexes in Pthreads (1)
Some of the Pthreads calls relating to mutexes.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.40
Silberschatz, Galvin and Gagne ©2007
Mutexes in Pthreads (2)
Some of the Pthreads calls relating to condition variables.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.41
Silberschatz, Galvin and Gagne ©2007
Mutexes in Pthreads (3)
Using pthreads to solve the producer-consumer problem.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.42
Silberschatz, Galvin and Gagne ©2007
Mutexes in Pthreads (4)
Using pthreads to solve the producer-consumer problem.
...
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.43
Silberschatz, Galvin and Gagne ©2007
Mutexes in Pthreads (5)
Using threads to solve the producer-consumer problem.
Example from Tanenbaum, Modern Operating Systems 3 e, (c) 2008 Prentice-Hall, Inc. All rights reserved. 0-13-6006639
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
6.44
Silberschatz, Galvin and Gagne ©2007
End of Chapter 6 (b)
Operating System Concepts with Java – 7th Edition, Nov 15, 2006
Silberschatz, Galvin and Gagne ©2007