**REMZI class** =============== Hoare Semantic: --------------- - When signal/notify, immediately wake a waiting thread - Hence, *transfer lock implicitly* - Cons: + restrain the scheduler + hard to implement, why? if have 2 conditional variables, need to make sure we wake up the correct thread + more context switch Mesa Semantics: --------------- - Signal: just a hint (something might have changed) - waking process must recheck the state - from system point: it is OK to wake up a waiting thread at random point because the condition is recheck - waking process (return from wait) must reacquire the lock Covering Condition: ------------------- Notifier can just notify the covering condition, and waiter check for the exact condition ... Say: free (20) and there are 2 wait: wait (100) and wait (10) In this case, wait (100) cannot make it. Solution: use broadcast: something has change, waiter wake up and check for exact condition .. Naked Notify: ------------- - devices and processes have some shared data structure for: + commands + return status (and even data) - when devices need attention (say done a job, or there is a packet arrive) its NOTIFY (hey I need attention) WITHOUT holding a lock. Why? + slow + "there is a serous problem with any kind of mutual exclusion between two processes which run on processors of substantially different speeds: The faster process may have to wait for the slower one. The worst-case response time of the faster process therefore cannot be less than the time the slower one needs to finish its critical section" - Hence, called naked Notify - Note: update to commands need to be atomic==> leverage the load/store mem instruction for atomicity - RACE problem, and notify can be lost. How? + since NOTIFY is just a hint + a process in the monitor, find to be FALSE, about to WAIT (of course, in this case, process is holding monitor lock) + now, device does a naked NOTIFY, it does not need to acquire lock + The WAIT then be done, and the NOTIFY is lost - Note: this never happens if device requires to hold lock before doing NOTIFY - Solution: + add a binary state to conditional variable. + whenever there is a naked notify, that bit is turned on + WAIT then check for that state before do a really wait + update to this state need to be atomic + this is similar to binary-semaphore Implementation: --------------- Queues: ------- - ready queue: contains processes ready to run - monitor lock queue (1 per monitor): processes attempting to enter monitor - conditional variable queue (1 per conditional variable): processes waiting on a cv - Fault queue: A fault can make a process temporarily unable to run; such a process is moved from the ready queue to a fault queue, and a fault-handling process is notified Thread is on exactly one of these queue (see my class note) Example: in class, produce, consumer, say 2 consumer, 1 proceducer Ready Monitor lock Empty Fill c1,p,c2 p,c2 c1 // c1 get run first, has the lock // wait on fill, release the lock p c2 c1 // p runs, get interrupt, c2 run // try to enter monitor by acquire // the lock, but fails, since c1 is // holding the lock p,c1 c2 // p run, notify fill, c1 finish c2,p,c1 // c2 get the lock, get run p,c1 c2 // c2 wait on fill and so on. Note: - queues are sorted by process priority - simple priority scheduler, preemptive **MESA MONITOR** ================ Design choice ------------- 1) interprocess communication: - shared mem (i.e, monitor) vs. message passing - Mesa chose shared memory because + easier (with the help of PL). + It is obvious because MESA programming structure is the procedure. 2) nonpreemptive scheduler vs. preemptive mechanism Mutual exclusion can be easily implemented with a nonpreemptive scheduler. If a process only yields the processor voluntarily (at yield points), ME is ensured between yield points. However, MESA monitor choose preemptive support because: + not work in multiprocessor + the author don't want to change the semantic of the program, i.e, they don't want to insert a yield in a random place in the program code (????) + preemptive is needed because processor must respond to time-critical events (e.g, I/O interrupts). Of course, non preemptive still works, but much slowly + non-preemption restricts programming generality (HOW ???) For example, in critical sections, a procedure that happens to yield the processor cannot be called. + use of non-preemption forbids multiprogramming across page-fault. (why? because the program has to yield, otherwise reduce performance, but if it yield may be it still holds a lock, hence) 3) Not use semaphore but rather monitor: Because semaphores exert too little structuring discipline on concurrent program *The Basic: Monitor* --------------------- When processes interact by sharing data, proper synchronization is needed. A proper vehicle for this kind of interaction is one which unifies: - Synchronization - Shared data - body of code which performs the accesses That is the monitor. Monitor contains shared data, some condition variables, and monitor procedures used to accessed shared data. Data is protected by a monitor, and can only be accessed within the body of a monitor procedure. There are two kinds of monitor procedures: - Entry procedures, which can be called from outside - Internal procedures, which can only be called from inside the monitors The RULE: at most one process is executing a monitor procedure at a time. If a process is in the monitor (i.e executing a monitor procedure), other processes which call an entry procedure need to wait (and will be delayed) --> this provide mutual exclusion In Mesa, monitor is implemented as a module, with three kinds of procedures: - entry - internal - external (can be called from anywhere, but implemented based on entry and internal procedures) The first two are monitor procedures and execute with the monitor lock held *Semantics of Nested Monitor call* ---------------------------------- In general, a monitor contains some condition variables on which processes want to wait on. The WAIT releases the monitor lock, which is reacquired when the waiting process reenters the monitor. If WAIT is done in an internal procedure, it still releases the lock. However, if the monitor calls some other outside procedures, the lock is not releases, even if the other procedure is in (or calls) another monitor and end ups doing a wait. ---> This is a potential threat of deadlock Example: if we have 2 monitor M1 and M2. Process P1 call M1.foo(), which in turn call M2.bar(). A WAIT is done in side M2.bar(), then M1 lock is not released (P1 still holds it). >>> Question: why is that? > Short answer: for performance reason. > Long answer: the monitor always maintains an invariant I which is always true of its shared data, except when some process is executing in the monitor. Whenever control leaves the monitor, I must be established. Hence, before doing a WAIT, I has to be re-established. ==> I can be assumed at the start of an entry procedure and after a each WAIT. Now, if we release the lock whenever we make an outside call from inside a monitor, I must be established (other wise, other processes entering the monitor will see that the invariant I is false) ==> this is cumbersome >>> Exception: (UNWIND) If an entry procedure generates an exception, the exception handler from within the monitor will be called, which mean that the handler still have the lock. Hence, if the handler happens to call that monitor, there will be a deadlock. ==> SOLUTION: make the an entry procedure to restore to invariant, release the lock, return with error, and then generate an exception *Dead lock* ------------ Three ways for deadlock occurs in Mesa monitor: 1) Single process to deadlock with itself - recursive entry procedure - exception handler for an entry procedure happens to call that monitor 2) Cyclic calling between two monitors. Say M1 call M2.bar(), and M2 calls M1.foo(), each will wait for the other to release the monitor lock 3) M calls N (M still hold its lock), N then waits for a condition which can only occur when another process enter N through M and makes the condition true. In this case, M is locked, and N is unlocked (because it wait) >> SOLUTION: break M into two part: monitor M' and ordinary module O which implement the abstraction defined by M, and calls M' for access to shared data. The call on N must be done from O rather than from within M' *Condition Variables Semantic* ------------------------------- 1) HOARE monitor - HOARE semantic requires that a process waiting on a condition variable must run IMMEDIATELY when another process signals that condition variable, and that the signaling process in turn runs as soon as the waiter leaves the monitor. - The impact: + this is difficult to implement, + require extra context switch, + also place a limit on OS scheduling policy - VERIFICATION: there are two invariants in HOARE monitor, the invariant for the monitor B (i.e for the shared data), and the invariant for the condition variable. Hence after a waiter resumes and continue execution or before the signaling of the condition variable, I and B are true. Therefore, the RULES are I {b.wait} I & B I & B {b.signal} I (why not I & B? because B can be make false again) 2) MESA Monitor: different from Hoare semantic - Semantic: when a process establishes a condition on which other process may be waiting, it notifies the corresponding condition variable. For a waiter, NOTIFY is like a *hint*, this causes the waiter to be executed some time in the future. There is no guarantee that a waiter executes right after a notify. Hence, after a notify and before the execution of a waiter, other processes may enter the monitor, making the condition (on which the waiter wait on) may not be true. Therefore, the waiter need to reevaluate the condition each time it resumes, if the conditions is false, it simply waits again. This is totally different from Hoare semantic. And only the monitor invariant can be assumes after a wait. Hence the RULES for MESA monitor: I {b.wait} I (need to recheck to B condition) I & B {b.signal} I (The monitor invariant must be established before a return from an entry procedure or wait. It can be assume at the start of an entry procedure or just after a wait) In Mesa, the proper pattern of waiting code should be: - While NOT Do Wait End loop While in Hoare, just simple check: If Not then wait ==> Hence in mesa monitor, simpler, no extra context switch, does not violate with OS scheduling rules Another reason for MESA to treat a NOTIFY as a hint is that many applications do not trouble the exact condition needed by a waiter has been established. Instead, they choose a cheap predicate which implies the exact condition, and it it the job of the waiter to determine whether the exact condition holds. THE CONSEQUENCE, since NOTIFY is treated as hint, is is more flexible to determine the way a process resuming from a wait: 1) Time out 2) Abort 3) BroadCast: (this appear in qual once), instead of doing a NOTIFY to a condition, a process can do a BROADCAST, which causes ALL waiting processes (on that condition) to resume. This is true, since NOTIFY is just a hint, not a guarantee. Each waiting process need to reevaluate the condition *Naked Notify* -------------- with devices (I/O), it is not possible for a device to wait on a monitor lock, (because it is slow) hence, whenever a device need an attention, it simply NOTIFY a condition variable to wake up a waiting process. --> call Naked, because device does not have to acquire monitor lock. - Share data structure here is: a single - word for passing commands to the device and returning status information. - (implemented as ) as a single word atomic Problem: RACE A process inside the monitor finds to be false, and is about to WAIT, and before it actually waits, the device updates the shared data and does its NOTIFY. The WAIT will then be done, and the NOTIFY from the device will be lost. ==> SOLUTION: wakeup-waiting switch (what is this???) So, in this case, they use cheap synchronization (binary semaphore) rather than the expansive mechanism (monitor conditional variables) What happens if a device would wait on and acquire monitor lock *Priority Inversion* --------------------- suppose P1 > P2 > P3 P3 enters monitor M (P3 hold the lock) P3 is preempted by P2 P2 is preempted by P1 P1 tries to enter the monitor and it has to wait (for the lock which P3 held) P2 runs again --> we have priority inversion problem (Note that if there are only P1 and P3 it is ok, because P1 has to wait for P3) Solution: 1) Priority inheritance, process that holds the lock has highest priority (we can implement this as: associate with each monitor the priority of the highest-priority process which ever enters that monitor, hence the process holding the lock will temporarily have priority as high as that of the monitor) --> this solution is complex 2) Disabling interrupt on entry to monitor --> this does not work with page fault (in other words, this give the process the highest priority). Problem with disable interrupt: Although this is simple, it has some problem: 1) we need to trust the process. There is no guarantee that when disabling the lock, the process on entry a procedure will return correctly or it will loop endlessly 2) does not work with multiprocessor 3) does not work with Virtual Memory, i.e, the system can not work with a page fault 4) in some modern processors, code for marks and unmarks interrupts tend to be slow, compared to normal instruction.