Transcript ppt

Presentation Summary of “Experiences
with Processes and Monitors in Mesa”
By Burke Ellett
CS533 - Concepts of Operating Systems
1
What I will cover today …




Mesa programming language and design decisions
when adding concurrency.
Difference between Hoare’s monitors and Mesa
monitors.
Issues that caused problems during the development
of Pilot and other large processes
Benefits and drawbacks to having concurrency
implemented inside of a language construct
CS533 - Concepts of Operating Systems
2
What is Mesa?




Mesa is a strongly-typed high-level programming
language, a component of the Xerox Development
Environment. [1]
It was developed at Xerox PARC in the 1970's [1]
It was used to develop systems software for the
first personal computers and spurred the
development of the Lisa and Macintosh computers,
whose user interfaces in turn prompted the
development of Microsoft Windows. [1]
Oldest relative of Java
CS533 - Concepts of Operating Systems
3
Motivation for adding concurrency to
Mesa


The creation of Pilot which was the first operating
system developed for personal computers that would
allow for multiple processes to run concurrently
where each shared a time slice of CPU. Created
using concurrent programming as opposed to event
based programming.
Add concurrent programming to Mesa so that side
by side development of Pilot could take place.
CS533 - Concepts of Operating Systems
4
Choices for handling concurrency in a
language

Voluntary yields was an option that was rejected
o
o
o
o


Only good for single processor
Must respond to time critical events so preemption needed
anyways
Restricts programming generality, you need to know if a procedure
you call will yield the processor
Page faults would cause involuntary yields at arbitrary points in a
program
Message passing was an option that was rejected because it
was proven to be equivalent to monitors when some mild
restrictions are applied
Monitors was the final choice because it was equivalent to
message passing and worked better with the procedural
scheme of Mesa, they choose Hoare’s paper as a starting place
for thinking about concurrency in their language.
CS533 - Concepts of Operating Systems
5
Issues about adding concurrency to Mesa
so that Pilot could be developed







Program structure
Creating processes
Creating monitors
Wait in a nested monitor call
Handling exceptions
Priority scheduling
Communication with devices (like I/O)
CS533 - Concepts of Operating Systems
6
Creation of a process in Mesa


Any non-internal monitor procedure can create a new process
by the use of a new key word called FORK that is placed in
front of the procedure call
This FORK procedure call will allow the current process to work
concurrently with the new process created. It also returns a
reference to the process just created so that the parent
process can later joined an a result is returned or to detach
from it. Different then Hoare thread that must suspend
working until to the thread just created exits or yields.
P ←FORK ReadLine[Terminal];
…<concurrent computation>
buffer ← JOIN p;

Every thread can be joined at a later time unlike PThreads
where you need to specify at time of creation. Extra overhead
in Mesa thread even though in practice most Mesa
programmers will immediately detach the thread.
CS533 - Concepts of Operating Systems
7
Reasons for this syntax for creating
processes





Made a process a first class value
Method of passing and retrieving values to a new
process the same as a normal procedure
No special declaration needed for procedures that
can be invoked as separate processes, similar to
PThreads
Low cost of creating and destroying processes
allowed for number of processes to vary widely at
any time
Start the new process working at the beginning of
any procedure
CS533 - Concepts of Operating Systems
8
Creating monitors


A Mesa module (Similar to a class) contains shared data and
procedures to act on the data as well external procedures that
do not modify the data (Diff. than Hoare that has no external
procedures)
A module can be declared a monitor module which contains
three type of procedures
o
o
o


Entry (Monitor required procedures called externally)
Internal (Private procedures may be called by entry procedure)
External (Non-monitor procedures)
A lock must be obtained by a process that calls an entry
procedure and is released when the entry procedure exits.
The lock is implicit and the runtime environment handles
management of this. Therefore a Mesa monitor is an instance
of a module.
No explicit creation of a locks unlike in PThreads.
CS533 - Concepts of Operating Systems
9
Problems with this implementation




Upon entering a Entry procedure you might find you
need to wait (Like consumer/producer problem)
Exception thrown by this procedure or a subprocedure who releases the lock
Recursive entry procedures
Calling an Entry procedure of another monitormodule from inside a monitored procedure
CS533 - Concepts of Operating Systems
10
Adding the WAIT key word
WHILE NOT <OK to proceed> DO WAIT c ENDLOOP.
(Mesa and PThreads)
-versusIF NOT <OK to proceed> THEN WAIT c. (Hoare)
CS533 - Concepts of Operating Systems
11
NOTIFY key word



When one process establishes a condition for which
some other process may be waiting it notifies the
corresponding condition variable
It is like a hint to a single waiting process to resume
at some convenient time, not a guarantee that the
condition waiting on will be true (Different the
Hoare)
Alternatives to NOTIFY are TIMEOUT, ABORT,
BROADCAST
CS533 - Concepts of Operating Systems
12
Hoare Semantics for condition variable
wakeup [4]
CS533 - Concepts of Operating Systems
13
Mesa Semantics for conditional variable
wakeup [4]
CS533 - Concepts of Operating Systems
14
Implementation of processes and
monitors


Split between compiler, runtime package, underlying
machine
A process is represented by stack of procedure
activation records (frames) plus a small description
called a process state
o
o
Frames are stored on the heap and a frame handler is
invoked if a fault occurs
Process state is stored in fixed table which consists of four
types of queues
•
•
•
•
Ready queue
Monitor lock queue
Condition variable queue
Fault queue
CS533 - Concepts of Operating Systems
15
The queues




Queue cells point to the tail process state in a
circular link list of process states
The queue is priority sorted and within each priority
group a FIFO algorithm is used to decide the next
running process
A process not held in the ready queue could be
passed to the processor through software
instructions or a trap vector center in the case of a
page fault
The Process module of the Mesa runtime package
handles all of this including notification of processes
waiting on a time interval
CS533 - Concepts of Operating Systems
16
Priority Scheduling can Cause Blocking


The paper example of possible blocking caused by priority scheduling
(same as last week)
P1, P2, and P3 are processes with priority same
as
subscript, with monitor M.
1. P1 enters M
2. P1 is preempted by P2
3. P2 is preempted by P3
4. P3 tries to enter monitor and waits for lock
5. P2 runs again and effectively prevents P3 from running
contrary to priorities
Mesa uses priority scheduling but assigns each monitor the priority of
the highest priority process which ever enters that monitor to ensure
the CPU priority scheduling discipline imposed by some application,
thus preventing blocking in example above.
CS533 - Concepts of Operating Systems
17
Handle I/O interrupts for condition
variables

Since I/O device does not wait on a monitor it
notifies the condition handler when it needs
attention. This is called a “Naked Notify” and can
lead to a race conditions
o
o
If a process inside the “while not <condition> do wait” loop
and has checked the condition and is preparing to wait at
the same time the interrupt occurs then the notify could
become lost and the process may not wake again.
Fixed with wakeup-waiting switch in condition variable
(binary semaphore)
CS533 - Concepts of Operating Systems
18
Compiler changes


New key words
More static checking to find frequent errors like
the use of wait in an external procedure (external
procedures have no knowledge of locks that are
held)
CS533 - Concepts of Operating Systems
19
Performance issues


The only major performance issue was the FORKJOIN construct which resulted in over 10 times the
amount of time ticks as any other construct or the
same time as 1100 simple instructions
The cause was the implementation of this in
software, but since it is not in popular use they left
it there
CS533 - Concepts of Operating Systems
20
Problems encountered with Mesa
implementation of concurrency


The lack of mutual exclusion in handling of
interrupts (Bugs caused in timing races between I/O
and handlers
The interaction of concurrency and exception
handling makes programming hard
CS533 - Concepts of Operating Systems
21
Implement concurrency in language or not


Main advantages is the programmer has direct
guidelines for the syntax and behavior of the
threads, the program should work the same from
computer platform to computer platform so more
portable, far easier to use a standard package
Main disadvantages are that the programmer loses
the ability to take advantage of hardware, by having
built in concurrency you lose flexibility of
interleaving different libraries that handle
concurrency favorable to your particular problem
CS533 - Concepts of Operating Systems
22
Contributions to community



Though neither Mesa or Pilot ever took off it was
the launching point of both the modern personal
computer and the ideas behind the use of virtual
machines like Java
Tied up many loose ends in concurrent programming
and got them implemented into one package
Helped define basic implementations of a modern OS
CS533 - Concepts of Operating Systems
23
References
1.
2.
3.
4.
http://www.apearson.f2s.com/mesacourse10.html A
website about the Mesa programming language, and
its history.
“Monitors: An Operating System Structuring
Concept” by C.A.R Hoare,The Queen's University of
Belfast
“Pilot: An Operating System for a Personal
Computer” by David D. Redell, Yogen K. Dalal,
Thomas R. Horsley, Hugh C. Lauer, William C.
Lynch,Paul R. McJones, Hal G. Murray, and Stephen
C. Purcell, Xerox Business Systems
Duke University
Architecture
class 24
CS533Systems
- Concepts ofand
Operating
Systems
slides