Transcript ppt

CS533 Concepts of Operating Systems
Class 2a
Monitors
But first …

… catch up from last time
o
synchronization errors and Eraser
CS533 - Concepts of Operating Systems
2
Enforcing mutual exclusion

Assumptions:
o
o

Every thread sets the lock before accessing shared data!
Every thread releases the lock after it is done!
Only works if you follow these programming
conventions all the time!
Thread 1
Lock
A=2
Unlock
Thread 2
Lock
A = A+1
Unlock
Thread 3
A = A*B
CS533 - Concepts of Operating Systems
3
Solutions to misuse (or no use) of locks

Solution 1 - detection
o
o

use static or dynamic checking tools to help track down
misuses of locking primitives (synchronization bugs)
How much can you detect?
Solution 2 - prevention
o
o
have the compiler insert the synchronization primitives for
you automatically
Which errors can be prevented this way, and which can’t?
CS533 - Concepts of Operating Systems
4
Solution 1: Checking tools (class 2 cont.)

Eraser
o
o
o

A dynamic checker that uses binary re-writing techniques
Gathers an “execution history” of reads, writes and lock
acquisitions
Evaluates consistency with rules
Is it enough to simply check that some lock is held
whenever a global variable is accessed?
CS533 - Concepts of Operating Systems
5
Automated checking of conventions


Eraser doesn’t know ahead of time which locks
protect which variables
It infers which locks protect which variables using a
lock-set algorithm
o
o
o
Assume all locks are candidates for a variable ( C(v) is full)
For each access take intersection of C(v) and locks held by
thread and make these the candidate set C(v)
If C(v) becomes empty, issue warning
CS533 - Concepts of Operating Systems
6
Improving the locking discipline


The standard approach produces many false
positives that arise due to special cases:
Initialization
o

Read sharing
o

No need to lock if no thread has a reference yet
No need to lock if all threads are readers
Reader/writer locking
o
Distinguish concurrent readers from concurrent readers
and writers
CS533 - Concepts of Operating Systems
7
Improved algorithm
virgin
wr, new thread
rd, wr
First
thread
exclusive
wr
rd,
new
thread
rd
shared
Modified
(race?)
wr
shared
CS533 - Concepts of Operating Systems
8
What can’t it detect?



Deadlocks?
Races that do not manifest themselves in this
particular execution run
It can’t prove the absence of errors, it can only
show the presence of errors
CS533 - Concepts of Operating Systems
9
Solution 2: Monitors

Monitors employ two key concepts, both of which
can be automated by a compiler:
o
Encapsulation:
•
o
Local data variables are accessible only via the
monitor’s entry procedures (like methods)
Mutual exclusion:
•
The entry procedures are treated as critical sections
CS533 - Concepts of Operating Systems
10
Two kinds of synchronization

Mutual exclusion
o
o
o

Only one at a time in the critical section
Enforced via a mutex lock
Must ensure that critical section invariant holds before
releasing mutex
Condition synchronization
o
o
Wait (block) until a certain condition (stronger than the
critical section invariant) holds
Signal (unblock) waiting threads when the condition holds
CS533 - Concepts of Operating Systems
11
Invariant of a mutex

The mutex “invariant” is the condition that must be
restored before:
o

The mutex is released
Example
o
Invariant A=B
•
o
o
always holds outside the critical section
Read side critical sections depend on invariant A=B holding
for correctness of their code
Write side critical sections update A and B, temporarily
violating the invariant
•
•
Must exclude read side critical sections
Memory is immutable from the point of view of readers
CS533 - Concepts of Operating Systems
12
Condition variables


Mutex locks allow threads to synchronize before
accessing the data
Condition variables allow communication among
cooperating threads
o
o
Used in conjunction with a mutex lock
Allows a thread in a critical section to wait for a condition
to become true or signal that a condition is true
Acquire mutex lock (enter critical section)
…
Block until condition becomes true (frees mutex lock)
…
Free mutex lock (leave critical section)
CS533 - Concepts of Operating Systems
13
Logical view of monitor structures
shared data
condition variables
monitor entry queue
x
y
Local to monitor
(Each has an associated
list of waiting threads)
“entry” methods
local methods
List of threads
waiting to
enter the monitor
Can be called from
outside the monitor.
Only one active at
any moment.
initialization
code
CS533 - Concepts of Operating Systems
14
Monitors in Practice

Can be implemented directly by the programmer
o
o

Can be supported via library primitives
o
o

Essentially just a programming convention
Hoare presents the basic idea behind this
Programmers must follow a convention in their use
Pthreads is an example of this
Can be part of a programming language and
supported directly by the compiler
o
o
o
Compiler inserts code to acquire and release monitor lock
Reduces programming errors
Mesa is a move toward this
CS533 - Concepts of Operating Systems
15
Library example: Pthread condition variables

pthread_cond_wait (condition,mutex)
o
o

pthread_cond_signal (condition)
o

Releases “mutex” and blocks until “condition” is signaled
Note: must say which mutex you are associated with
Signals “condition” which wakes up a thread blocked on
“condition”
pthread_cond_broadcast (condition)
o
Signals “condition” and wakes up all threads blocked on
“condition”
CS533 - Concepts of Operating Systems
16
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
CS533 - Concepts of Operating Systems
17
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
Will spinning locks work?
CS533 - Concepts of Operating Systems
18
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
o
Will spinning locks work?
Will yielding locks work?
CS533 - Concepts of Operating Systems
19
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
o
o
Will spinning locks work?
Will yielding locks work?
What if we don’t want active waiting?
CS533 - Concepts of Operating Systems
20
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
o
o

Will spinning locks work?
Will yielding locks work?
What if we don’t want active waiting?
Idea 1 (assuming uniprocessor):
o
Disable interrupts during monitor procedures
CS533 - Concepts of Operating Systems
21
A Simple Example

Goal: to build a blocking mutex lock using monitors
o

Monitor procedures are “acquire” and “release”
Demonstrate use of interrupt disabling on a
uniprocessor to implement mutual exclusion within
the monitor procedures
CS533 - Concepts of Operating Systems
22
Using monitors to build a blocking mutex
Blocking_mutex:monitor
Begin
busy:boolean;
nonbusy:condition;
busy:=false;
Procedure acquire()
Begin
if busy then nonbusy.wait;
busy:=true;
End
Procedure release()
Begin
busy:=false;
nonbusy.signal
End;
End Blocking_mutex;
// initial value
CS533 - Concepts of Operating Systems
23
Using monitors to build a blocking mutex
Blocking_mutex:monitor
Begin
busy:boolean;
nonbusy:condition;
Busy:=false;
Procedure acquire()
Begin
if busy then nonbusy.wait;
busy:=true;
End
Procedure release()
Begin
busy:=false;
nonbusy.signal
End;
End Blocking_mutex;
// initial value
<----- disable interrupts
<----- enable interrupts
<----- disable interrupts
<----- enable interrupts
CS533 - Concepts of Operating Systems
24
Using monitors to build a blocking mutex
Blocking_mutex:monitor
Begin
busy:boolean;
nonbusy:condition;
Busy:=false;
Procedure acquire()
Begin
if busy then nonbusy.wait;
busy:=true;
End
Procedure release()
Begin
busy:=false;
nonbusy.signal
End;
End Blocking_mutex;
// initial value
----- disable interrupts
<----- ????
----- enable interrupts
----- disable interrupts
<----- ????
----- enable interrupts
CS533 - Concepts of Operating Systems
25
Implementing condition variables

Wait
o
o
o
Add process to queue of processes waiting on this condition
Suspend process
Release monitor’s mutual exclusion
•
•

Wake up / schedule next process trying to enter monitor
Reenable interrupts?
Signal
o
o
o
Wake up / schedule first process waiting on this condition
Release monitor’s mutual exclusion by enabling interrupts?
Suspend yourself
•
On what? … and how do you ever wake up again?
CS533 - Concepts of Operating Systems
26
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
o
o

Idea 1:
o

Will spinning locks work?
Will yielding locks work?
What if we don’t have atomic instructions?
Disable interrupts during monitor procedures
Idea 2:
o
Use binary semaphores
CS533 - Concepts of Operating Systems
27
Building monitors from binary semaphores

Dijkstra had invented semaphores a few years
before
o

They could be used for a blocking mutex lock in the
construction of monitors
See example in the Hoare paper
CS533 - Concepts of Operating Systems
28
Bounded buffer solution with monitors
process Producer
begin
loop
<produce char “c”>
BoundedBuffer.append(c)
end loop
end Producer
process Consumer
begin
loop
BoundedBuffer.remove(c)
<consume char “c”>
end loop
end Consumer
BoundedBuffer: monitor
var buffer : ...;
nextIn, nextOut :... ;
procedure append (c: char)
begin
...
end
procedure remove (var c: char)
begin
...
end
end BoundedBuffer
CS533 - Concepts of Operating Systems
29
Bounded buffer solution with monitors
BoundedBuffer: monitor
var buffer
nextIn,nextOut
Count
nonEmpty, nonFull
:
:
:
:
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
procedure append(c:char)
begin
if (Count = n) then
wait(nonFull)
end if
buffer[nextIn] := c
nextIn := nextIn+1 mod n
Count := Count+1
signal(nonEmpty)
end append
procedure remove(var c: char)
begin
if (Count = n) then
wait(nonEmpty)
end if
c := buffer[nextOut]
nextOut := nextOut+1 mod n
Count := Count-1
signal(nonFull)
end remove
end BoundedBuffer
CS533 - Concepts of Operating Systems
30
Alarm clock example
AlarmClock: monitor
Begin
now: integer;
wakeup: condition;
now := 0;
Procedure wakeme(n: integer);
Begin
alarmsetting: integer;
alarmsetting := now + n;
While now < alarmsetting do wakeup.wait (alarmsetting);
wakeup.signal;
End;
Procedure tick;
Begin
now := now + 1;
wakeup.signal;
End;
End AlarmClock;
CS533 - Concepts of Operating Systems
31
Semantics of condition variables




How many blocked threads should be woken on a
signal?
Which blocked thread should be woken on a signal?
In what order should newly awoken threads acquire
the mutex?
Should the signaler immediately free the mutex?
o
o

If so, what if it has more work to do?
If not, how can the signaled process continue?
What if signal is called before the first wait?
CS533 - Concepts of Operating Systems
32
Subtle race conditions


Why does wait on a condition variable need to
“atomically” unlock the mutex and block the thread?
Why does the thread need to re-lock the mutex
when it wakes up from wait?
o
Can it assume that the condition it waited on now holds?
CS533 - Concepts of Operating Systems
33
Different Monitor Semantics

How do the semantics of Hoare’s monitors compare
to those of:
o
o
o
the mutexes and condition variables described by Birrell?
Pthreads mutexes and condition variables?
MESA monitors?
CS533 - Concepts of Operating Systems
34
Hoare vs. MESA Semantics for Wait
CS533 - Concepts of Operating Systems
35
Hoare semantics

What happens when a Signal is performed?
o
o

Result:
o
o
o

signaling thread (A) is suspended
signaled thread (B) wakes up and runs immediately
B can assume the condition on which it waited now holds
Hoare semantics give strong guarantees
Easier to prove correctness
When B leaves monitor, A can run.
•
Depending on how B resumes A it might resume execution
immediately or after some other process
CS533 - Concepts of Operating Systems
36
MESA Semantics

What happens when a Signal is performed?
o
o
o

Issue: What happens while B is waiting?
o
o

the signaling thread (A) continues.
the signaled thread (B) waits.
when A leaves monitor, then B runs.
can another thread (C) run after A signals, but before B
runs?
Can A subsequently invalidate the condition on which B
was waiting?
In MESA semantics a signal is more like a hint
o
Requires B to recheck the state of the monitor variables
(the invariant) to see if it can proceed or must wait again
CS533 - Concepts of Operating Systems
37
Bounded buffer with Hoare monitors
BoundedBuffer: monitor
var buffer
nextIn,nextOut
Count
nonEmpty, nonFull
:
:
:
:
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
procedure append(c:char)
begin
if (Count = n) then
wait(nonFull)
end if
buffer[nextIn] := c
nextIn := nextIn+1 mod n
Count := Count+1
signal(nonEmpty)
end append
procedure remove(var c: char)
begin
if (Count = n) then
wait(nonEmpty)
end if
c := buffer[nextOut]
nextOut := nextOut+1 mod n
Count := Count-1
signal(nonFull)
end remove
end BoundedBuffer
CS533 - Concepts of Operating Systems
38
Bounded buffer with MESA monitors
BoundedBuffer: monitor
var buffer
nextIn,nextOut
Count
nonEmpty, nonFull
:
:
:
:
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
procedure append(c:char)
begin
while (Count = n) then
wait(nonFull)
end while
buffer[nextIn] := c
nextIn := nextIn+1 mod n
Count := Count+1
signal(nonEmpty)
end append
procedure remove(var c: char)
begin
while (Count = n) then
wait(nonEmpty)
end while
c := buffer[nextOut]
nextOut := nextOut+1 mod n
Count := Count-1
signal(nonFull)
end remove
end BoundedBuffer
CS533 - Concepts of Operating Systems
39
Subtle Problems with Monitors


Many subtle problems arise with the use of monitors
in real-world systems
There are several different solutions to some of
these problems
o
o
MESA monitor semantics differ from Hoare monitors
Many current implementations differ in subtle ways from
both MESA and Hoare monitors
CS533 - Concepts of Operating Systems
40
Deadlock

You can still deadlock via access to a monitor mutex
o

If two or more monitors invoke each other’s entry
procedures
Deadlock can also occur with condition variables
o
See nested monitor problem (p. 20) of Birrell’s tutorial
CS533 - Concepts of Operating Systems
41
Deadlock (nested monitor problem)
Procedure Get();
BEGIN
LOCK a DO
LOCK b DO
WHILE NOT ready DO wait(b,c) END;
END;
END;
END Get;
Procedure Give();
BEGIN
LOCK a DO
LOCK b DO
ready := TRUE; signal(c);
END;
END;
END Give;
CS533 - Concepts of Operating Systems
42
Deadlock

Deadlock is not good, but why is it better to have a
deadlock than a race?
CS533 - Concepts of Operating Systems
43
Priority Inversion


Occurs in priority scheduling
Starvation of high priority threads
Low priority thread C locks M
Medium priority thread B pre-empts C
High priority thread A preempts B then blocks on M
B resumes and enters long computation
Result:
C never runs so can’t unlock M, therefore A never runs
Solution? – priority inheritance
- synchronization-aware scheduling
- threads temporarily acquire the highest priority of any
thread waiting for them
CS533 - Concepts of Operating Systems
44
Dangers of blocking in a critical section



Blocking while holding M prevents progress of other
threads that need M
Blocking on another mutex may lead to deadlock
Why not release the mutex before blocking?
o
o
o
Must restore the mutex invariant
Must reacquire the mutex on return!
Things may have changed while you were gone …
CS533 - Concepts of Operating Systems
45
Spurious wake-ups and lock conflicts

Reader-writer locking example (page 15, Birrell)
o
o
o
o
o
o

Writers exclude readers and writers
Readers exclude writers but not readers
Good use of broadcast in ReleaseExclusive()
Results in “spurious wake-ups”
… and “spurious lock conflicts”
How could you use signal instead?
Move signal/broadcast call after release of mutex?
o
Advantages? Disadvantages?
CS533 - Concepts of Operating Systems
46