Transcript Monitors: An Operating System Structuring Concept

Monitors: An Operating
System Structuring Concept
Paper by: C. A. R. Hoare
Presented by: Sabrina Brick
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.
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
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
An Abstract Monitor
name: monitor
…local declarations
…initialize local data
proc1 (…parameters)
…statement list
proc2 (…parameters)
…statement list
proc3 (…parameters)
…statement list
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”!
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
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;
What possible problem exists?
monitor declaration
local variables / initializations
procedure
procedure
The Possible Problem

As discussed in Birrell’s paper (last class):

First process:




Second 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!
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.
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
Sabrina’s Car: a running example
car: monitor
emptyTank, 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;
tank.push(gallons.pop);
fullTank.signal;
//assume gas station “stack” has infinite supply
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.
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
tank.push(gallons.pop);
fullTank.signal;
//returns true if a process is waiting on fullTank
//assume gas station “stack” has infinite supply
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
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();
//consume gas in increments of a gallon
emptyTank.signal;
procedure fillCar()
if tank.isFull then emptyTank.wait;
if fullTank.queue
tank.push(gallons.pop);
fullTank.signal;
//assume gas station has infinite supply
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
Lots of Great Examples

OS Examples:





Bounded Buffer
Alarm clock
Disk head scheduler
Reader/writer
Buffer Allocation
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?
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();
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.
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
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)
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