Transcript ppt

CS533 Concepts of Operating Systems
Class 3
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

Only one at a time in the critical section
Condition synchronization
o
o
Wait (block) until a certain condition holds
Signal (unblock) waiting threads when the condition holds
CS533 - Concepts of Operating Systems
11
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
12
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
CS533 - Concepts of Operating Systems
13
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
Will spinning locks work?
CS533 - Concepts of Operating Systems
14
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
15
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 have atomic instructions?
CS533 - Concepts of Operating Systems
16
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 have atomic instructions?
Idea 1 (assuming uniprocessor):
o
Disable interrupts during monitor procedures
CS533 - Concepts of Operating Systems
17
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
18
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
19
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
20
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
21
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
22
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
23
Building monitors from binary semaphores

See example in paper
CS533 - Concepts of Operating Systems
24
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
25
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
26
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
27
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
28
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
29
Comparison with thread primitives

How do Hoare’s monitors compare to the use of
mutexes and condition variables described by
Birrell?
CS533 - Concepts of Operating Systems
30
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
31
Reader/writer locking



Writers exclude readers and writers
Readers exclude writers but not readers
Example (page 15, Birrell)
o
o
o
o

Move signal/broadcast call after release of mutex?
o

Good use of broadcast in ReleaseExclusive()
Results in “spurious wake-ups”
… and “spurious lock conflicts”
How could you use signal instead?
Advantages? Disadvantages?
Can we avoid writer starvation?
CS533 - Concepts of Operating Systems
32