Transcript old_6 - Portland State University

CS 333
Introduction to Operating Systems
Class 6 – Monitors and Message Passing
Jonathan Walpole
Computer Science
Portland State University
1
Monitors

It is difficult to produce correct programs using
semaphores


correct ordering of up and down operations is
tricky!
Can we get the compiler to generate the
correct semaphore code for us?

what are suitable higher level abstractions for
synchronization?
2
Monitors



Collect related shared objects together in a monitor
Characteristics
 Local data variables are accessible only via the monitor’s
procedures
 Processes enter the monitor by invoking one of its
procedures
 Only one process may execute within the monitor at a
given time
Condition variables (cv)
 Wait(cv) – block on condition
 Signal(cv) – wake up process waiting on cv
3
Monitor structures
shared data
condition queues
monitor entry queue
x
y
monitor operations
initialization
code
4
Monitor example for mutual exclusion
process Producer
begin
loop
<produce char “c”>
BoundedBuffer.deposit(c)
end loop
end Producer
process Consumer
begin
loop
BoundedBuffer.remove(c)
<consume char “c”>
end loop
end Consumer
monitor: BoundedBuffer
var buffer : ...;
nextIn, nextOut :... ;
entry deposit(c: char)
begin
...
end
entry remove(var c: char)
begin
...
end
end BoundedBuffer
5
Condition variables



Condition variables allow processes to synchronize based
on some state of the monitor variables
 For example: Buffer_full in the producer/consumer
Operations wait(cv) and signal(cv) allow synchronization
within a monitor
Only one processor active at one time

what happens on a signal from A to B?
• A waits for B to leave monitor, or waits for another
condition
• B waits for A to leave monitor, or waits for another
condition

… and what happens on wait?
6
Monitor example
monitor : BoundedBuffer
var buffer
:
nextIn,nextOut
:
fullCount
:
notEmpty, notFull :
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
entry deposit(c:char)
begin
if (fullCount = n) then
wait(notFull)
end if
buffer[nextIn] := c
nextIn := nextIn+1 mod n
fullCount := fullCount+1
signal(notEmpty)
end deposit
end BoundedBuffer
entry remove(var c: char)
begin
if (fullCount = n) then
wait(notEmpty)
end if
c := buffer[nextOut]
nextOut := nextOut+1 mod n
fullCount := fullCount-1
signal(notFull)
end remove
7
Condition synchronization semantics





Signaling and signaled processes can not both
run
What if signaling process continues to run and
signals other condition variable?
What if signaled process continues to run and
signals other condition variables?
What order should processes run?
How do you avoid deadlock?
8
Condition synchronization semantics

Hoare Semantics

On signal, allow signalled process to run; upon its
exit from the monitor, signaller process continues
• Stonger guarantees
• Easier to prove correctness

Mesa Semantics (Xerox PARC)

Signal is merely a “hint”
• Requires process to check that condition is ok to
continue upon receipt of signal
9
Producer consumer with message passing
10
Barriers

Use of a barrier



processes approaching a barrier
all processes but one blocked at barrier
last process arrives, all are let through
11
Summary

Process synchronization topics




Semaphores
IPC problems
Monitors
Reading

2.3-2.4
12
Monitors

It is difficult to produce correct programs using
semaphores




correct ordering of up and down is tricky!
avoiding deadlock is tricky!
boundary conditions are tricky!
Can we get the compiler to generate the
correct semaphore code for us?

what are suitable higher level abstractions for
synchronization?
13
Monitors



Collect related shared objects together in a monitor
Encapsulation and mutual exclusion
 Local data variables are accessible only via the monitor’s
procedures
 Processes enter the monitor by invoking one of its
procedures
 Only one process may execute within the monitor at a
given time
Condition variables (cv)
 Wait(cv) – process blocked (queued) until condition holds
 Signal(cv) – signals the condition and unblocks (dequeues)
a process
14
Monitor structures
shared data
condition queues
monitor entry queue
x
y
monitor operations
initialization
code
15
Monitor example for mutual exclusion
process Producer
begin
loop
<produce char “c”>
BoundedBuffer.deposit(c)
end loop
end Producer
process Consumer
begin
loop
BoundedBuffer.remove(c)
<consume char “c”>
end loop
end Consumer
monitor: BoundedBuffer
var buffer : ...;
nextIn, nextOut :... ;
entry deposit(c: char)
begin
...
end
entry remove(var c: char)
begin
...
end
end BoundedBuffer
16
Monitor example with condition variables
monitor : BoundedBuffer
var buffer
:
nextIn,nextOut
:
fullCount
:
notEmpty, notFull :
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
entry deposit(c:char)
begin
if (fullCount = n) then
wait(notFull)
end if
buffer[nextIn] := c
nextIn := nextIn+1 mod n
fullCount := fullCount+1
signal(notEmpty)
end deposit
end BoundedBuffer
entry remove(var c: char)
begin
if (fullCount = n) then
wait(notEmpty)
end if
c := buffer[nextOut]
nextOut := nextOut+1 mod n
fullCount := fullCount-1
signal(notFull)
end remove
17
Monitor design choices



Condition variables introduce a problem for mutual
exclusion
 only one process active in the monitor at a time, so what
to do when a process is unblocked on signal?
 must not block holding the mutex, so what to do when a
process blocks on wait?
Should signals be stored/remembered?
 signals are not stored
 if signal occurs before wait, signal is lost!
Should condition variables count?
18
Monitor design choices



Choices when A signals a condition that unblocks B
 A waits for B to exit the monitor or blocks again
 B waits for A to exit the monitor or block
 Signal causes A to immediately exit the monitor or block
(on what condition?)
Choices when A signals a condition that unblocks B & C
 B is unblocked, but C remains blocked
 C is unblocked, but B remains blocked
Choices when A calls wait and blocks
 a new external process is allowed to enter
 but which one?
19
Common monitor semantics

Hoare semantics


On signal, allow signaled process to run; upon its
exit from the monitor, signaler process continues
Brinch Hansen semantics

signaler must immediately exit following signal
20
Message Passing

Interprocess communication



via shared memory
across machine boundaries
Message passing can be used locally or remotely
for synchronization or general communication



processes use send and receive primitives
receive can block like wait
send unblocks a process blocked on receive (like
signal unblocking a waiting process)
21
Producer consumer with message passing
22
Design Choices for Message Passing

Mailboxes


system maintains a buffer of sent, but not yet
received, messages
Rendezvous




sender and receiver must be active at the same
time
receive must be blocked before send occurs
kernel does no buffering
when does the send return?
23
Barriers

Use of a barrier



processes approaching a barrier
all processes but one blocked at barrier
last process arrives, all are let through
24
Monitors (1)
Example of a monitor
25
Monitors (2)

Outline of producer-consumer problem with monitors


only one monitor procedure active at one time
buffer has N slots
26
Monitors (3)
Solution to producer-consumer problem in Java (part 1)
27
Monitors (4)
Solution to producer-consumer problem in Java (part 2)
28
Semantics of monitors

What is the strongest statement we can make
about the state of the monitor after a waiter
wakes up?
entry deposit(c:char)
begin
if (fullCount = n) then
wait(notFull)
entry remove(var c: char)
begin
:
:
c := buffer[nextOut]
fullCount := fullCount-1
end if
signal(notFull)
:
:
end deposit
end remove
29
Synchronization problems with Mesa
P1
/* fullCount=n */
if (fullCount==n)
wait(notFull);
P2
P3
remove()
...
fullCount--;
signal(notFull);
...
/* exit monitor */
/* fullCount=n-1*/
deposit()
...
fullCount++;
...
/* exit monitor */
...
fullCount++;
30
Mesa semantics
monitor : BoundedBuffer
var buffer
:
nextIn,nextOut
:
fullCount
:
notEmpty, notFull :
array[0..n-1] of char
0..n-1 := 0
0..n
:= 0
condition
entry deposit(c:char)
begin
while (fullCount = n) then
wait(notFull)
end while
buffer[nextIn] := c
nextIn := nextIn+1 mod n
fullCount := fullCount+1
signal(notEmpty)
end deposit
end BoundedBuffer
entry remove(var c: char)
begin
while (fullCount = n) then
wait(notEmpty)
end while
c := buffer[nextOut]
nextOut := nextOut+1 mod n
fullCount := fullCount-1
signal(notFull)
end remove
31
Introduction to Operating Systems
Chapter 2 (partial)
Monitors, Reentrant Code,
Message Passing, and
Barriers
32
Introduction






It is difficult to produce correct
programs
using locks and semaphores!!!
Correct ordering of Up and Down operations is
tricky!
Desirable:
Language / compiler support for IPC
What are suitable high-level abstractions for
33
Monitors



Collect related, shared objects together in a
“monitor”
Characteristics:
 • Local data variables are accessible only via the
monitor’s procedures/methods
 • Threads enter the monitor by invoking one of its
procedures/methods
 • Only one thread may execute within the monitor
at a given time
“Condition Variables” (cv)
 Wait(cv) – block on condition
 Signal(cv) – wake up one thread waiting on cv
34
Monitor structures
shared data
monitor entry queue
x
condition variables
y
“entry” methods
local methods
initialization
code
35
Monitor structures
shared data
monitor entry queue
x
condition variables
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
36
Example: The “Bounded-Buffer” Monitor
Producer Thread:
while true
-- Produce char “c”
BoundedBuffer.deposit(c)
endWhile
Consumer Thread:
while true
c = BoundedBuffer.remove()
-- Consume char “c”
endWhile
monitor BoundedBuffer
var buffer: ...
nextIn, nextOut :...
entry deposit(c: char)
begin
...
end
entry remove()
begin
...
return c
end
endMonitor
37
The “BoundedBuffer” Monitor
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
...
nextOut nextIn
ABC D
0
N-1
cntFull=4
entry remove()
...
endMonitor
38
Code for the “deposit” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
if cntFull == N
notFull.Wait()
endIf
buffer[nextIn] = c
nextIn = (nextIn+1) mod N
cntFull = cntFull + 1
notEmpty.Signal()
endEntry
nextOut nextIn
ABC D
0
N-1
cntFull=4
entry remove()
...
endMonitor
39
Code for the “remove” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
...
nextOut nextIn
ABC D
0
N-1
cntFull=4
entry remove()
if cntFull == 0
notEmpty.Wait()
endIf
c = buffer[nextOut]
nextOut = (nextOut+1) mod N
cntFull = cntFull - 1
notFull.Signal()
endEntry
endMonitor
40
Condition Variables








“Condition variables allow processes to
synchronize based on some state of the
monitor variables.”
Examples from producer/consumer:
“Buffer-Full” condition
“Buffer-Empty” condition
Operations Wait(cv) and Signal(cv)
allow synchronization within the monitor
When a producer thread adds an
element...
A consumer may be sleeping
41
Condition synchronization semantics


“Only one thread can be executing in the
monitor
at any one time.”
Scenario:

Thread A is executing in the monitor.

Thread A does a Signal, waking up thread
B.

What happens now?
•
Signaling and signaled threads can not both
run!

42
Condition synchronization semantics
• Option 1: Hoare Semantics
• What happens when a Signal is performed?
•
The signaling thread (A) is suspended.
•
The signaled thread (B) wakes up and runs
immediately.
•
B can assume the condition is now
true/satisfied
•
• • Stronger guarantees
• • Easier to prove correctness
• When B leaves monitor, then A can run.
•
After B leaves monitor...
•
A might resume execution immediately
•
... or maybe another thread (C) will slip
in!
43
Condition synchronization semantics
• Option 2: MESA Semantics (Xerox PARC)
• What happens when a Signal is performed?
•
• The signaling thread (A) continues.
•
• The signaled thread (B) waits.
•
When A leaves monitor, then B runs.
• Issue: What happens when B waits?
•
When A leaves the monitor,
•
can some other thread (C) slip in
first?
•
(Can some other thread (C) run
•
after A signals, but before B runs?)
• • A signal is more like a hint.
• • Requires B to recheck the state of the
monitor variables
•
to see if it can proceed or must wait some
44
Code for the “deposit” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
if cntFull == N
notFull.Wait()
endIf
buffer[nextIn] = c
nextIn = (nextIn+1) mod N
cntFull = cntFull + 1
notEmpty.Signal()
endEntry
Hoare Semantics
entry remove()
...
endMonitor
45
Code for the “deposit” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
while cntFull == N
notFull.Wait()
endWhile
buffer[nextIn] = c
nextIn = (nextIn+1) mod N
cntFull = cntFull + 1
notEmpty.Signal()
endEntry
MESA Semantics
entry remove()
...
endMonitor
46
Code for the “remove” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
...
entry remove()
if cntFull == 0
notEmpty.Wait()
endIf
c = buffer[nextOut]
nextOut = (nextOut+1) mod N
cntFull = cntFull - 1
notFull.Signal()
endEntry
Hoare Semantics
endMonitor
47
Code for the “remove” entry routine
monitor BoundedBuffer
var buffer: array[n] of char
nextIn, nextOut: int = 0
cntFull: int = 0
notEmpty: Condition
notFull: Condition
entry deposit(c: char)
...
entry remove()
while cntFull == 0
notEmpty.Wait()
endWhile
c = buffer[nextOut]
nextOut = (nextOut+1) mod N
cntFull = cntFull - 1
notFull.Signal()
endEntry
MESA Semantics
endMonitor
48
“Hoare Semantics”
• What happens when a Signal is performed?
•
The signaling thread (A) is suspended.
•
The signaled thread (B) wakes up and runs
immediately.
•
B can assume the condition is now
true/satisfied
• From the original Hoare Paper:
• “No other thread can intervene [and enter the
monitor] between the signal and the continuation
of exactly one waiting thread.”
• “If more than one thread is waiting on a
condition, we postulate that the signal operation
will reactivate the longest waiting thread. This
gives a simple neutral queuing discipline which
ensures that every waiting thread will eventually
49
Implementing Hoare Semantics










Implementation?
Thread A holds the monitor lock.
Thread A issues a Signal.
Thread B will be moved back to the ready
queue.
Thread A must be suspended...
Possession of the monitor lock must be
passed
from A to B.
When B finishes and gets ready to return...
The lock can be released.
Thread A must re-aquire the lock.
50
Implementing Hoare Semantics







Problem:
“Possession of the monitor lock must be
passed
from A to B.”
Each mutex remembers which thread holds
it.
My version of Mutex:
Any attempt by thread B to release
the monitor
lock will cause an error
message.
51
Implementing Hoare Semantics






Recommendation:
Do not modify the methods that I am
supplying.
(Future code I release will use them)
Create new classes:
MonitorLock -- similar to Mutex
HoareCondition -- similar to Condition

52
Implementing Hoare Semantics










Scenario:
Thread B does a Wait.
Thread A executes a Signal.
Thread B wakes up, executes, and returns.
Last thing B does: Unlock the monitor lock.
Problem: What happens next?
Thread A is waiting for B to finish.
It is trying to reaquire the monitor
lock.
What about thread C?
Also trying to acquire lock, and
53
Implementing Hoare Semantics










Things are getting complex.
Simply ending monitor entry methods with
monLock.Unlock()
will no longer work.
Implementation Ideas:
Need a special thing called a “MonitorLock”.
Consider a thread like A to be “urgent”.
Thread C is not “urgent”.
Consider 2 wait lists associated with each
MonitorLock
• UrgentlyWaitingThreads
54
Brinch-Hansen Semantics

Hoare Semantics



On signal, allow signaled process to run.
Upon its exit from the monitor, signaler process
continues.
Brinch-Hansen Semantics



Signaler must immediately exit following
any invocation of signal.
(Implementation of is easier.)
55
Reentrant Code

A function/method is said to be “reentrant”
if...

“A function that has been invoked may be
invoked again
before the first invocation has returned,
and will still work correctly.”

Recursive routines are reentrant.




In the context of multi-programming...
A reentrant function can be executed
56
Reentrant Code

Consider this function...

var count: int = 0

function GetUnique () returns
int





count = count + 1
return count
endFunction
What if it is executed by different threads?
57
Reentrant Code

Consider this function...

var count: int = 0

function GetUnique () returns
int





count = count + 1
return count
endFunction
What if it is executed by different threads?
The results may be incorrect!
58
Reentrant Code








When is code “reentrant”?
Assumption:
A multi-threaded program
Some variables are
“local” -- to the
function/method/routine
“global” -- sometimes called “static”
Access to local variables?
A new stack frame is created for each
invocation.
59
Making this Function Reentrant

var count: int = 0
myLock: Mutex

function GetUnique () returns

int







var i: int
myLock.Lock()
count = count + 1
i = count
myLock.Unlock()
return i
endFunction
60
Message Passing

Interprocess Communication


• via shared memory
• across machine boundaries

Message passing can be used locally or remotely
Can be used for...
synchronization, or
general communication

Processes use Send and Receive primitives






• Receive can block (like Waiting on a Semaphore)
• Send unblocks a process blocked on Receive
(Just as a Signal unblocks a Waiting process)
61
Producer-Consumer with Message Passing










Idea:
After producing, the producer sends the
data to consumer in a message.
The system buffers messages.
The producer can out-run the
consumer.
The messages will be kept in order.
After consuming the data,
the consumer sends back an “empty”
message.
A fixed number of messages (N=100)
The messages circulate back and forth.
62
Producer-Consumer with Message
Passing
const N = 100
var em: char
for i = 1 to N
Send (producer, &em)
endFor
-- Size of message buffer
-- Get things started by
-sending N empty messages
thread consumer
var c, em: char
while true
Receive(producer, &c)
Send(producer, &em)
// Consume char...
endWhile
end
-- Wait for a char
-- Send empty message back
63
Producer-Consumer with Message
Passing
thread producer
var c, em: char
while true
// Produce char c...
Receive(consumer, &em)
Send(consumer, &c)
endWhile
end
-- Wait for an empty msg
-- Send c to consumer
64
Design Choices for Message Passing

Option 1: “Mailboxes”




System maintains a buffer of sent, but not yet
received, messages.
Must specify the size of the mailbox ahead of time.
Sender will be blocked if buffer is full.
Receiver will be blocked if the buffer is empty.
65
Design Choices for Message Passing

Option 1: “Mailboxes”








System maintains a buffer of sent, but not yet
received, messages.
Must specify the size of the mailbox ahead of time.
Sender will be blocked if buffer is full.
Receiver will be blocked if the buffer is empty.
Option 2: The kernel does no buffering
If Send happens first, the sending thread
blocks.
If Receiver happens first, the receiving
thread blocks.
“Rendezvous”
66
Barriers



• Processes approaching a barrier
• All processes but one blocked at barrier
• Last process arrives; all are let through
67
Monitors: An Operating System Structuring
Concept
Paper by: C. A. R. Hoare
Presented by: Sabrina Brick
68
Why monitors?

Concurrency has always been an OS issue



Resource allocation is necessary among competing
processes
Timer interrupts
Existing synchronization mechanisms
(semaphores, locks) are subject to hard-tofind, subtle bugs.
69
What is a monitor?


A collection of data and procedures
Mutual exclusion



allows controlled acquisition and release of critical
resources
single anonymous lock automatically acquired and
released at entry and exit
Data encapsulation

monitor procedures are “entry points” for accessing
data
70
Monitors: a language construct




Monitors are a programming language construct
anonymous lock issues handled by compiler and
OS
detection of invalid accesses to critical sections
happens at compile time
process of detection can be automated by
compiler by scanning the text of the program
71
An Abstract Monitor
name: monitor
…local declarations
…initialize local data
proc1 (…parameters)
…statement list
proc2 (…parameters)
…statement list
proc3 (…parameters)
…statement list
72
Rules to Follow with Monitors





Any process can call a monitor procedure at any
time
But only one process can be inside a monitor at
any time (mutual exclusion)
No process can directly access a monitor’s local
variables (data encapsulation)
A monitor may only access its local variables
Why? Race conditions could occur! “Chaos will
ensue”!
73
Enforcing the Rules

“wait” operation


“signal” operation


current process is put to sleep
wakes up a sleeping process
condition variables


May have different reasons for “waiting” or
“signaling”
Processes waiting on a particular condition enter its
queue
74
Sabrina’s Car: a running example
car: monitor
occupied: Boolean; occupied := false;
nonOccupied: condition;
procedure enterCar()
if occupied then nonOccupied.wait;
occupied = true;
procedure exitCar()
occupied = false;
nonOccupied.signal;
monitor declaration
local variables / initializations
procedure
procedure
What possible problem exists?
75
The Possible Problem

As discussed in Birrell’s paper (last class):

First process:


•
•
•
Completes it’s work with critical section
Signals a process waiting on “nonOccupied”
Starts to release the monitor when…
•
•
•
Is awakened by first process
Tries an “entry point” into the monitor
First process isn’t finished releasing it so it blocks again!
Second process:
This can’t happen with Hoare’s approach:

Signal must be the last operation in a monitor.

Signal and monitor exit are a combined operation.
76
Multiple Conditions



Sometimes it is necessary to be able to wait on
multiple things
Can be implemented with multiple conditions
Example: 2 reasons to enter car



drive (empties tank)
fill up car
Two reasons to wait:


Going to gas station but tank is already full
Going to drive but tank is (almost) empty
77
Sabrina’s Car: a running example
car: monitor
emptyTank, fullTank: condition;
tank: stack; tank := stack of 10 gallons;
procedure driveCar()
if tank.isAlmostEmpty then fullTank.wait;
tank.pop();
gallon
emptyTank.signal;
procedure fillCar()
if tank.isFull then emptyTank.wait;
tank.push(gallons.pop);
supply
fullTank.signal;
//10 gallon tank
//filled in increments of a gallon
//consume gas in increments of a
//assume gas station “stack” has infinite
78
Condition Queue

Might want to check if any process is waiting on
a condition


The “condition queue” returns true if a process is
waiting on a condition
Example: filling the tank only if someone is
waiting to drive the car.
79
Sabrina’s Car: a running example
car: monitor
emtpyTank, fullTank: condition;
tank: stack; tank := stack of 10 gallons; //10 gallon tank
//filled in increments of a gallon
procedure driveCar()
if tank.isAlmostEmpty then fullTank.wait;
tank.pop();
//consume gas in increments of a
gallon
emptyTank.signal;
procedure fillCar()
if tank.isFull then emptyTank.wait;
if fullTank.queue
fullTank
tank.push(gallons.pop);
supply
fullTank.signal;
//returns true if a process is waiting on
//assume gas station “stack” has infinite
80
Priority: Scheduled Waits



A waiting process is given a number
The process with the lowest number gets woken
up first
Example: People who want to drive my car are
prioritized:



Highest: Me!
Medium: Family
Lowest: Friends/Others
81
Sabrina’s Car: a running example
car: monitor
emtpyTank, fullTank: condition;
tank: stack; tank := stack of 10 gallons;
//10 gallon tank
//filled in increments of a gallon
procedure driveCar(p: person)
if tank.isAlmostEmpty then
if p.isSabrina then fullTank.wait(1);
if p.isFamily then fullTank.wait(2);
if p.isFriendorOther then fullTank.wait(3);
tank.pop();
gallon
emptyTank.signal;
procedure fillCar()
if tank.isFull then emptyTank.wait;
if fullTank.queue
tank.push(gallons.pop);
fullTank.signal;
//consume gas in increments of a
//assume gas station has infinite supply
82
Other issues

Power of Monitors


Monitor->semaphore and vice versa
Proof rules


I {b.wait} I&B
I&B {b.signal} I
I : the invariant
B : the condition that a process waiting on b wants
to be true before its woken up
b : the condition variable
83
Lots of Great Examples

OS Examples:





Bounded Buffer
Alarm clock
Disk head scheduler
Reader/writer
Buffer Allocation
84
Monitors and Granularity

Monitors are designed for course-grained
locking




Example: locking an entire data structure rather
than its individual components.
Is this an appropriate solution for all cases?
Why or why not?
What problems arise when the granularity is too
coarse? What about the opposite case?
85
Monitors: implementation issues
Disabling Interrupts
Using a lock
car: monitor
occupied: Boolean; occupied := false;
nonOccupied: condition;
car: monitor
occupied: Boolean; occupied := false;
nonOccupied: condition;
//lock1: lock;
procedure enterCar()
//disableInterrupts();
if occupied then nonOccupied.wait;
occupied = true;
//enableInterrupts();
procedure enterCar()
//lock1.acquire();
if occupied then nonOccupied.wait;
occupied = true;
//lock1.release();
procedure exitCar()
//disableInterrupts();
occupied = false;
nonOccupied.signal;
//enableInterrupts();
procedure exitCar()
//lock1.acquire();
occupied = false;
nonOccupied.signal;
//lock1.release();
“Yellow code” inserted into binary by compiler
Which is the better approach? Why?
//lock1.acquire()
//disableInterrupts();
//lockVar = 1;
//enableInterrupts();
86
What problems do monitors solve?






Mutual exclusion
Encapsulation of data
Compiler can automatically scan program text for some
types of synchronization bugs
Synchronization of shared data access simplified vs.
semaphores and locks
Good for problems that require course granularity
Invariants are guaranteed after waits

Theoretically, a process that waits on a condition doesn’t
have to retest the condition when it is awakened.
87
What remains problematic?





No way to check dynamically allocated shared
data
Signals are as error prone as with other
synchronization mechanisms
Deadlock can still happen in monitor code
Programmer can still screw up
Monitors are available in very few languages
88
Conclusions




Monitors are a synchronization mechanism
A higher level, easier to use abstraction,
better encapsulation than semaphores, etc.
Monitors still suffer from various problems
Let’s take a look at working model that
addresses some of those issues! (Suzanne’s
presentation)
89
References





Jon Walpole
“Monitors: An Operating Systems Structuring
Concept” Hoare.
Modern Operating Systems, Second Edition.
Tannenbaum, pp. 115-119.
Emerson Murphy-Hill presentation from CS533,
Winter 2005
http://en.wikipedia.org/wiki/C._A._R._Hoare
90
Experience with Processes and Monitors in Mesa
B. W. Lampson
Xerox Palo Alto Research Center
D. D. Redell
Xerox Business Systems
Communications of the ACM v.23, n.2, Feb.1980, pp. 105-117
91
Design Goals



Local concurrent programming
Global resource sharing
Replacing interrupts
92
Concurrent Programming using
Monitors in Mesa






Interactions with process creation and
destruction
How to define WAIT
Priority scheduling
Semantics of nested monitor calls
Handling timeouts, aborts, and other exceptions
Monitoring large numbers of small objects
93
Signaling in Monitors
J. H. Howard
2nd Intl. Conf. of Software Engr, Oct.1976

SU signal & urgent wait






Brinch Hansen’75
return from monitor immediately after signaling
Concurrent PASCAL
SW signal & wait


signaler to “urgent” queue & resumes after
signaled process runs
SR signal & return

Hoare’74
signaled immediate access
signaler to monitor’s entry queue
Howard’76
SC signal & continue


signaler’s view of monitor state not corrupted
requires explicit recording of signals pending
Problems SU & SW: signalers might wait & restart unnecessarily
SR simplest but may be inadequate & SC complex
94
Excerpt of Tanenbaum’s
Example of Hoare Semantic
Monitor ProducerConsumer
condition full, empty; integer count;
procedure insert (item; integer);
begin
if count = N then wait (full);
insert_item (item);
count := count + 1;
if count = 1 then signal (empty);
end;
Modification for Mesa Semantic
while not count = N do wait (full)
Hoare semantic
Signaling thread suspends on urgent
Mesa semantic
Signaling thread continues
Signaled thread wakes & runs
immediately
Signaled thread rechecks condition
because order not guaranteed
First thread regains possession of
monitor when second completes
Avoid context switch
95
StorageAllocator: MONITOR = BEGIN
availableStorage: INTEGER:
moreAvailable: CONDITION:
Allocate: ENTRY PROCEDURE [size: INTEGER
RETURNS [p: POINTER] = BEGIN
UNTIL availableStorage >= size
DO WAIT moreAvailable ENDLOOP;
p <- <remove chunk of size words & update availableStorage>
END;
Free: ENTRY PROCEDURE [p: POINTER, Size: INTEGER] = BEGIN
<put back chunk of size words & update availableStorage>;
NOTIFY moreAvailable END;
Expand:PUBLIC PROCEDURE [pOld: POINTER, size: INTEGER]
RETURNS [pNew: POINTER] = BEGIN
pNew <- Allocate[size];
<copy contents from old block to new block>;
Free[pOld] END;
END.
96
Mutual exclusion



Asynchronous processes must not Allocate
and Free simultaneously
→ use entry
procedures
Monitor lock not needed during copy in
Expand → use external procedure
Structure the monitor computations only
when lock is already held
→ use internal procedure
97
Define WAIT



If caller waits in entry procedure, it
releases the lock
If wait in internal procedure, the lock is
released
If monitor calls procedure outside the
monitor, the lock is not released
98
Invariant





Always true, except when process is executing in
the monitor
On entry, invariant assumed to hold
Invariant established before control leaves monitor
Monitor procedure must establish invariant before
WAIT
Consider exception handler called from entry
procedure
99
Causes of
Pair-wise Deadlock



2 processes WAIT in a single
monitor
Cyclic calling between 2 monitors →
impose a partial order
Two level data abstraction
100
Two level data abstraction
Example: Monitor M calls N and waits for C
requires process to enter N through M to set C → DEADLOCK
Divide M into monitor M’ and interface O to call N
101
Monitored Objects





Collection of shared data objects
Multiple instances of monitor
Duplication of program linking and code
swapping
Monitored record
To access a file, pass as parameter to
effectively create a separate monitor for
each object (read-only, no aliasing)
102
Abandon computation




UNWIND exception to allow clean-up by any
active procedure
If procedure to be abandoned is an entry
procedure, must restore invariant and release lock
Programmer provides handler or experiences
deadlock
Compare to Java exception handling
103
Condition variables




Process establishes a condition for which another
process waits
NOTIFY is a hint that waiting process will resume
and reacquire the monitor lock
No guarantee about another process interceding
Waiter must reevaluate when it resumes
WHILE NOT <OK to proceed> DO WAIT c ENDLOOP
Hoare IF NOT <OK to proceed> THEN WAIT c
Mesa
104
Verification rules





Simpler and more localized
Invariant established before return from entry
procedure or a WAIT
Invariant assumed at start of entry procedure
and just after a WAIT
Waiter explicitly tests
Notify condition may be more general (low cost
to wake a process)
105
NOTIFY alternatives




Timeout with interval
Abort
Broadcast
I/O device communication


device cannot wait on monitor lock
notify condition variable to wake interrupt
handler
106
Priorities


Ordering implied by assignment of
priorities can be subverted by
monitors
Associate with each monitor the
priority of the highest priority
process that ever enters the monitor
(Modula disables interrupts, but this fails with page fault.)
107
Example of subverted priority
Process P1 enters monitor M, P2 preempts, P3 preempts
P3 tries to enter monitor and waits for lock
P1
enter
preempt P1
P2
M
preempt P2
P3
P2 runs again, effectively keeps P3 from running, undermining the priorities.
108
Processor
Process states (pcbs) in queues
sorted by priority
Ready queue
 Monitor lock queue
Condition variable queue
 Fault queue


Queue cell
process state
head
process state
----
process state
tail
109
Implementation

Compiler – flags errors




WAIT in external procedure
direct call from external to internal
procedure
Runtime – process creation and
destruction
Machine – process scheduling and
monitor entry/exit
110
Performance
111
Validation of Mesa Semantic

Operating system



Database



Interrupt handling lack of mutual exclusion
Interaction of concurrency and exception
Single monitor and single condition variable
Array of representative states
Network communication


Router monitor
Network driver monitor
112
Closing comparison
113
Implementation
114





Monitor – low level mechanism
Starvation addressed by high level scheduling
Simpler & localized verification rules
Signaled process checks specific condition
More general condition for notify
Questions
• Should signal be the last operation of a
monitor procedure?
• How is exception handling addressed?
115