Mesa ==== What is the setting? What kind of system? Single-user machine, one address space Custom CPU (or at least microcode), language, run-time system, OS all developed together What are goals of system? 1. Local concurrent programming 2. Global resource sharing 3. Replacing interrupts Why not non-preemptive scheduler, like old UNIX kernels Even if implementation uniprocessor, didn't want interface to enforce this Still no solution for concurrency of interrupts Restricts programming in critical sections, since can't sleep In fact, error-prone if called procedure sleeps (might need monitor like mechanism anyway to guard against this) Non-preemptive semantics force CPU to be idle during page faults What is Mesa's interface for creating a concurrent process? - Take any function: res <- fn (args) - Invoke with fork: p <- FORK fn (args) - Get result with join: res <- JOIN p Note that because this is done in the language, can enforce types fn: PROCEDURE [Device] Returns [Line] p: PROCESS Returns [Line] I.e., A process is a first-class value Note that the system allows this with any function (except monitor-internal) What does "Detach[p]" do? Informs system no one will JOIN p, so free all resources when p exits What if you join p after detaching it? Like using C pointer p after calling free (p) -- undefined On p.5: "while any procedure suitable for forking can also be called sequentially, the converse is not true" -- Why? Mesa has exceptions like C++ or java, can catch, otherwise propagated up If no one catches an exception, enter the debugger Can't propagate up across a fork, so exceptions in forked procs fatal What is a monitor? An object in which methods don't execute concurrently. 3 types of method ENTRY procedures - don't execute if one is already executing INTERNAL procedures - can only be called from ENTRY procedure PUBLIC procedures - can't touch the shared data Like a java class where every method is synchronized, private, or static I.e.,, must hold some low-level spinlock to execute non-public methods Idea: Always ensure abstraction invariants hold when leaving methods What happens when exception thrown from within monitor? Propagates back up as usual, but keeps internal spinlock! (after all, invariant won't necessarily hold at point of exception) Can work around by catching, resetting invariant, then RETURN WITH ERROR Note special UNWIND exception occurs when a call stack "abandoned" Useful for restoring invariants after arbitrary exceptions Can synchronize with CONDITION variables WAIT cond - sleep and allow another ENTRY procedure to be invoked i.e., releases the internal spinlock of the current monitor NOTIFY cond - cause (at least) one WAIT (if any) to return & reacquire lock BROADCAST cond - cause all WAITs to return Timeout - can associate a timeout value with CONDITION variable Abort p - causes process p to return from any wait with Aborted exception What are monitored objects? Allows you to stick a spinlock in any object, not just a module How would you implement a semaphore? int sem; CONDITION non_zero; P () { while (!sem) WAIT (non_zero); sem--; } V () { sem++; NOTIFY (non_zero); } Go over example on p. 7. What is the bug? Suppose availableStorage = 0, and two processes Allocate 10 bytes Someone Frees 10,000 bytes, but only one WAITer is awakened NOTIFY should be BROADCAST Can you get deadlock with monitors? How? - Two entry procedures of same monitor waiting for each other's notify Maybe a buggy bi-directional pipe when both write buffers fill - Mutually recursive monitors: monitor M calls N, and N calls M Fix: Impose partial ordering on monitors. Can this be checked at compile time? No (p. 8) Because procedure variables (function pointers) make calling pattern impossible to determine without actually running the program - M calls N, N WAITs, can only be notified when invoked through M N might be storage allocator from paper, used only by monitor M What's a Hoare monitor, and how does it differ from Mesa? Can SIGNAL a condition variable Waiter runs immediately, signaler runs as soon as waiter leaves monitor Allows you to transfer between waiter/signaler with different invariant Requires signaling be perfectly reliable (no spurious wakeups) Imposes rigid scheduling requirements Mesa is allowed to generate spurious wakeups Means in practice always check condition/wait in a loop BROADCAST is always correct where you have NOTIFY, but less efficient Converse is not the case In retrospect, Mesa's approach is probably better: p. 11: "the low-level scheduling mechanism provided by the monitor locks should not be used to implement high-level scheduling decisions." How do monitors replace interrupts? Just WAIT on device, and have it notify driver when event happens WHILE (buffered_packets == 0) WAIT (packet_cond); process_next_packet (); Then device also NOTIFYs packet_cond Since device is not "in monitor", this is a "naked NOTIFY" What if NOTIFY right before WAIT? Oops, could improperly sleep! Solution: "wakeup-waiting" switch - what's this? Single bit per process. 0 means WAIT acts as usual 1 means WAIT turns bit back to 0 but never goes to sleep So device must set wakeup-waiting bit, then NOTIFY driver (another example of while allowing spurious wakeups is convenient) p. 13: "the ordering implied by the assignment of priorities can be subverted by monitors" - how? - P1, P2, P3 (lowest, middle, highest priority) - P1 runnable and in monitor M, P2 runnable, P3 wants to enter M - System will run highest-priority runnable process, namely P2 Solutions? Temporarily bump P1 to highest priority of any process that ever enters M Mesa actually assigns infinite priority by disabling interrupts ... works okay unless a page fault occurs Alternatively, structure app so only adjacent prio procs share monitor A process can be on one of a number of queues? What are these? Ready queue - processes that can be run Monitor lock queue - per monitor, all procs waiting to enter Condition variable queue - per cond var., list of WAITers Fault queue - non-runnable processes What do we think of the approach? Did they meet goals? 1. Yes. Probably chose good mechanisms non-Hoare Condition variables are widely used today PThreads popular (next class), but Java adopted more monitor-like approach 2. Okay at the time--not much detail as to what happened in practice. Today we would probably want more protection between unrelated processes. 3. Maybe. They sort of cheated on this one. Also not clear how this would work with modern hardware