Transcript ppt

CS533 Concepts of Operating Systems
Class 3
Monitors
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
2
Solutions to misuse (or no use) of locks


Solution 1: use static or dynamic checking tools to
help track down misuses of locking primitives
(synchronization bugs)
Solution 2: have the compiler insert the
synchronization primitives for you automatically
CS533 - Concepts of Operating Systems
3
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
4
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
5
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
6
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
7
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
8
Two kinds of synchronization

Mutual exclusion
o

Only one at a time in the critical section
Condition synchronization
o
o
Wait until a certain condition holds
Signal waiting threads when the condition holds
CS533 - Concepts of Operating Systems
9
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
10
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
CS533 - Concepts of Operating Systems
11
Implementing mutual exclusion for monitors

How can we implement mutual exclusion for monitor
procedures?
o
Will spinning locks work?
CS533 - Concepts of Operating Systems
12
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
13
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
14
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:
o
Disable interrupts during monitor procedures
CS533 - Concepts of Operating Systems
15
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
16
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
17
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
18
Implementing condition variables

Wait
o
o
o
Add process to queue of processes waiting on this condition
Suspend process
Release monitor’s mutual exclusion
•
•

Reenable interrupts
Wake up / schedule next process trying to enter monitor
Signal
o
o
o
Wake up / schedule first process waiting on this condition
Release monitor’s mutual exclusion?
Suspend yourself
•
On what? … and how do you ever wake up again?
CS533 - Concepts of Operating Systems
19
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
20
Building monitors from binary semaphores

See example in paper
CS533 - Concepts of Operating Systems
21
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
22
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
23
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
24