Experience With Processes and Monitors in MesaI. Experience With Processes and Monitors in Mesa1Advanced Topics in Computer Systems, CS262AProf. Eric Brewer9/21/09Experience With Processes and Monitors in MesaI. Experience With Processes and Monitors in MesaFocus of this paper: light-weight processes (threads in today’s terminology) and how they synchronizewith each other.History: o 2nd system; followed the Alto.o planned to build a large system using many programmers. (Some thoughts aboutcommercializing.)o advent of things like server machines and networking introduced applications that areheavy users of concurrency.Chose to build a single address space system:o single user system, so protection not an issue. (Safety was to come from the language.)o wanted global resource sharing.Large system, many programmers, many applications:o Module-based programming with information hiding.Since they were starting “from scratch”, they could integrate the hardware, the runtime software, and thelanguage with each other.Programming model for inter-process communication: shared memory (monitors) vs. message passing.o Needham & Lauer claimed the two models are duals of each other.o Chose shared memory model because they thought they could fit it into Mesa as alanguage construct more naturally.How to synchronize processes?o Non-preemptive scheduler: tends to yield very delicate systems. Why?• Have to know whether or not a yield might be called for every procedure you call. Violates information hiding.• Prohibits multiprocessor systems.• Need a separate preemptive mechanism for I/O anyway.• Can’t do multiprogramming across page faults.o Simple locking (e.g. semaphores): too little structuring discipline, e.g. no guarantee thatlocks will be released on every code path; wanted something that could be integratedinto a Mesa language construct.Lecture 192o Chose preemptive scheduling of light-weight processes and monitors.Light-weight processes:o easy forking and synchronizationo shared address spaceo fast performance for creation, switching, and synchronization; low storage overhead.Monitors:o monitor lock (for synchronization)• tied to module structure of the language: makes it clear what’s being monitored.• language automatically acquires and releases the lock.o tied to a particular invariant, which helps users think about the programo condition variable (for scheduling)o Dangling references similar to those of pointers. There are also language-basedsolutions that would prohibit these kinds of errors, such as do-across, which is just aparallel control structure. It eliminates dangling processes because the syntax definesthe point of the fork and the join.o Monitors (and Mesa in particular) led to several aspects of Java. Java’s synchronizedobjects are the object-oriented programming version on monitors, and they are a bettersolution than monitored records. (Each instance has its own lock rather than just eachelement of an array.)Changes made to design and implementation issues encountered:o 3 types of procedures in a monitor module:• entry (acquires and releases lock).• internal (no locking done): can’t be called from outside the module.• external (no locking done): externally callable. Why is this useful?- allows grouping of related things into a module.- allows doing some of the work outside the monitor lock.- allows controlled release and reacquisition of monitor lock.oNotify semantics:• Cede lock to waking process: too many context switches. Why would this approach be desirable? (Waiting process knows the condition it was waiting on is guaranteed to hold.)Monitors Java Synchronized Objectsexternal publicinternal private synchronizedentry public synchronized3Lecture 19• Notifier keeps lock, waking process gets put a front of monitor queue. Doesn’t work in the presence of priorities.• Notifier keeps lock, wakes process with no guarantees => waking process must recheck its condition.What other kinds of notification does this approach enable?Timeouts, broadcasts, aborts.o Abort: a nice request to abort -- allows the target process to reach a wait or monitor exit,and then it voluntarily aborts. No need to re-establish the invariant -- as compared tojust killing the process outright!o Deadlocks: Wait only releases the lock of the current monitor, not any nested callingmonitors. This is a general problem with modular systems and synchronization:synchronization requires global knowledge about locks, which violates the informationhiding paradigm of modular programming. Why is monitor deadlock less onerous thanthe yield problem for non-preemptive schedulers?• Want to generally insert as many yields as possible to provide increased concurrency; only use locks when you want to synchronize.• Yield bugs are difficult to find (symptoms may appear far after the bogus yield)o Basic deadlock rule: no recursion, direct or mutualo Lock granularity: introduced monitored records so that the same monitor code couldhandle multiple instances of something in parallel.o Interrupts: interrupt handler can’t block waiting to acquire a monitor lock.• Introduced naked notifies: notifies done without holding the monitor lock.• Had to worry about a timing race: the notify could occur between a monitor’s condition check and its call on Wait. This a “time of check to time of use” (toctou, pronounced “tock-too”) bug -- the condition of the test no longer applies at the time of use. In particular, the sequence: 1) check for waiters == false, 2) naked notify, 3) go to sleep is a toctou bug. Added a wakeup-waiting flag to condition variables; naked notify sets the wakeup waiting flag if the target is awake, and before that process goes to sleep it checks this bit, and if set, resets it, and stays awake to check for notifies again.• What happens in general with a message handlers that needs to acquire a lock? (use the interrupt to queue the task, and then acquire locks in a process context instead)o Priority Inversion• high-priority processes may block on lower-priority processes• a solution: temporarily increase the priority of the holder of the monitor to that of the highest priority blocked process (somewhat tricky -- what happens when that high-priority process finishes with the monitor? You have to know the priority of the next highest ⇒ keep them sorted or scan the list on exit)• The Mars rover stalled due to this kind of bug and had to be debugged and