Transcript Monitors: An Operating System Structuring Concept

Monitors: An
Operating
System
Structuring
Concept
Paper by C. A. R. Hoare
Presentation by
Emerson Murphy-Hill
The Problem
• An OS’s main task is to control
access to a machine’s resources
(data, devices, time, space)
• If resources are not tightly
controlled, “chaos will ensue”
- race conditions
The Solution
• Monitors provide control by
allowing only one process to
access a critical resource at a time
– A class/module/package
– Contains procedures and data
An Abstract Monitor
name : monitor
… some local declarations
… initialize local data
procedure name(…arguments)
… do some work
… other procedures
Monitor Rules
• Any process can access any
monitor procedure at any time
• Only one process may enter a
monitor procedure
• No process may directly access a
monitor’s local variables
• A monitor may only access it’s
local variables
Things Needed to Enforce Monitor
• “wait” operation
– Forces running process to sleep
• “signal” operation
– Wakes up a sleeping process
• A condition
– Something to store who’s waiting for
a particular reason
– Implemented as a queue
A Running Example – Emerson’s Kitchen
kitchen : monitor
occupied : Boolean; occupied := false;
nonOccupied : condition;
procedure enterKitchen
if occupied then nonOccupied.wait;
occupied = true;
procedure exitKitchen
occupied = false;
nonOccupied.signal;
Monitor
Declaration
Declarations /
Initialization
Procedure
Procedure
Multiple Conditions
• Sometimes desirable to be able to wait
on multiple things
• Can be implemented with multiple
conditions
• Example: Two reasons to enter kitchen cook (remove clean dishes) or clean
(add clean dishes)
• Two reasons to wait:
– Going to cook, but no clean dishes
– Going to clean, no dirty dishes
Emerson’s Kitchen
kitchen : monitor
cleanDishes, dirtyDishes : condition;
dishes, sink : stack;
dishes := stack of 10 dishes
sink := stack of 0 dishes
procedure cook
if dishes.isEmpty then cleanDishes.wait
sink.push ( dishes.pop );
dirtyDishes.signal;
procedure cleanDish
if sink.isEmpty then dirtyDishes.wait
dishes.push (sink.pop)
cleanDishes.signal
Condition Queue
• Checking if any process is waiting
on a condition:
– “condition.queue” returns true if a
process is waiting on condition
• Example: Doing dishes only if
someone is waiting for them
Emerson’s Kitchen
kitchen : monitor
cleanDishes, dirtyDishes : condition;
dishes, sink : stack;
dishes := stack of 10 dishes
sink := stack of 0 dishes
procedure cook
if dishes.isEmpty then cleanDishes.wait
sink.push ( dishes.pop );
dirtyDishes.signal;
procedure cleanDishes
if sink.isEmpty then dirtyDishes.wait
if cleanDishes.queue
dishes.push (sink.pop);
cleanDishes.signal;
Scheduled Waits
• Gives a waiting thread a number
• Lowest number gets woken up first
(inverse priority)
• Example: People who want to
cook are prioritized:
– Highest: Me!
– Medium: Family
– Lowest: Vagrants/Friends
Emerson’s Kitchen
kitchen : monitor
cleanDishes, dirtyDishes : condition;
dishes, sink : stack;
dishes := stack of 10 dishes
sink := stack of 0 dishes
procedure cook( p : Person )
if dishes.isEmpty then
if p.isEmerson then cleanDishes.wait(1);
if p.isFamily then cleanDishes.wait(2);
if p.isFriendAndOrVagrant then cleanDishes.wait(3);
sink.push ( dishes.pop );
dirtyDishes.signal;
procedure cleanDishes
if sink.isEmpty then dirtyDishes.wait;
while(cleanDishes.queue)
dishes.push (sink.pop);
cleanDishes.signal;
Summary
• Advantages
– Data access synchronization simplified (vs.
semaphores or locks)
– Better encapsulation
• Disadvantages:
– Deadlock still possible (in monitor code)
– Programmer can still botch use of monitors
– No provision for information exchange
between machines
Other Issues Discussed
• Power of Monitors
– SemaphoreMonitor
– MonitorSemaphore
• Proof Rules
– I (b.wait) I & B
– I & B (b.signal) I
• OS Examples
–
–
–
–
–
Bounded Buffer
Alarm clock
Buffer allocation
Disk-head Scheduler
Reader/Writer
Mutual Exclusion: Implementation
Disabling Interrupts
Mutex Insertion
kitchen : monitor
kitchen : monitor
occupied : Boolean; occupied := false;
occupied : Boolean; occupied := false;
nonOccupied : condition;
nonOccupied : condition;
lock1 : lock;
procedure enterKitchen
procedure enterKitchen
disableInterrupts();
lock1.acquire();
if occupied then nonOccupied.wait;
if occupied then nonOccupied.wait;
occupied = true;
occupied = true;
enableInterrupts();
lock1.release();
procedure exitKitchen
procedure exitKitchen
disableInterrupts();
lock1.acquire();
occupied = false;
occupied = false;
nonOccupied.signal;
nonOccupied.signal;
enableInterrupts();
lock1.release();
Monitors In Context
• Multithreaded code could be
implemented with monitors
(w/language support)
• Enforcement of mutex locking
conventions
• Abstraction: deadlock can be
avoided, but of course, only if the
monitor is written correctly!
Conclusion
• Monitors are a synchronization
mechanism
• A higher level, easier to use
abstraction, better encapsulation
vs. semaphores/locks
• Monitors still suffer from various
afflictions
References
• “Monitors: An Operating System Structuring
Concept,” Hoare.
• Modern Operating Systems, Second Edition,
Tannenbaum, pp. 115-119.
• Jon Walpole, correspondence.
Questions
1.
2.
3.
4.
What is the essential implementation
difference between monitors and
semaphores?
What problems can still arise with the use of
monitors?
What is the most specialized compiler
mechanism required to implement monitors?
Generally, monitors allow us to encapsulate
mutex use and avoid the spread of mutex
across code. Can you think of a case where
this is not possible?
Possible Answers
1. Atomicity of blocked codereentrance in monitors
2. Deadlock, inconsistent use (eg,
acquire without release)
3. Mutual exclusion in monitor methods
4. When we need uninterrupted access
to 2 or more resources located in
different monitor proceedures.