Enforcing Mutual Exclusion Monitors and Message PassingMutual Exclusion Requirements Mutually exclusive access to critical section Progress. If no process is executing in its critical section and there exist some processes that wish to enter their critical section, then the selection of the processes that will enter the critical section next cannot be postponed indefinitely. Bounded Waiting. A bound must exist on the # of times that other processes are allowed to enter their critical sections after a process has requested to enter its critical section and before that request is granted. Assume each process executes at a nonzero speed  No assumption concerning relative speed of n processes.2Enforcing Mutual Exclusionfuntion(){<non-critical section>enter_critical_section();<critical section>exit_critical_section();<remainder section>}3Four different approaches Hardware support Software-defined approaches Support from the OS  Support from the programming language4Programming Language Sync. Construct Semaphores are error prone Hard to detect timing errors Obscure code (widely separated synchronization pairs) A monitor is a higher level (programming language) synchronization construct Semantics Only 1 process at a time can be active in a monitor A monitor variable can only be accessed within the monitor Signaling between processes is done through condition variables in a monitor 5Monitor High-level synchronization construct that allows the safe sharing of an abstract data type among concurrent processes.monitor monitor-name {shared variable declarationscondition variable declarationsprocedure body P1 (…) { . . . }procedure body P2 (…) { . . . } procedure body Pn (…) { . . . } { initialization code }}6Monitors To allow a process to wait within the monitor, a condition variable must be declared, ascondition x, y; Condition variable can only be used with the operations wait and signal. The operationx.wait();means that the process invoking this operation is blocked until another process invokesx.signal(); The x.signal operation resumes exactly one blocked process. If no process is blocked, then the signal operation has no effect. It is lost.7Schematic View of a Monitor8Monitor With Condition Variables9Monitor summary Programming language construct that guaranteesmutual exclusion A software module that consists of procedures, an initialization routine and local data.  Local data are accessible only by the procedures of the monitor. A process can enter a monitor by invoking one of its procedures. Only one process may be executing in the monitor at any time.  Other processes that would like to invoke a monitor procedure will be blocked.10Mutual Exclusion Mutual exclusion is guaranteed and automatic: only one process allowed in the monitor place the shared data structure in a monitor.11Classical Synchronization Problems  Bounded-Buffer Problem Readers and Writers Problem Dining-Philosophers Problem12Readers/Writers problem Many readers Many writers Any number of readers can be allowed to read simultaneously While a writer is writing, no others can write. No readers should read either.13Monitors – Readers/Writers problemMonitor ReaderWriter;/* The following can only be accessed by monitor functions. */int readers = 0; boolean writelock = false;Condition canWrite;Condition canRead;14Reader(){ Writer(){15while(true){beginRead();Read();endRead();}}while(true){beginWrite();Write();endWrite();}}The Reader: Hoare’s model16void beginRead(){if(writeLock || queue(canWrite)){cwait(canRead);}readers++;csignal(canRead);}void endRead(){readers--;if(readers == 0){csignal(canWrite);}}The Writer: Hoare’s model17void beginWrite(){if(readers > 0 || writeLock){cwait(canWrite);}writeLock = true;}void endWrite(){writeLock = false;if(queue(canRead)csignal(canRead);else if (queue(canWrite))csignal(canWrite);}Hoare’s model Hoare’s model requires that a process  signals at the end of the procedure and leaves the monitor. If signal() is not the last operation, then the process making the signal must block and instead of being placed on any of the conditions queues or the entry queue, will be placed in the urgent queue. The signal will wake the first process in the queue for that condition. If no process is waiting, the signal is lost.1819Disadvantages of Hoare’s model If the process that signaled is not done with the monitor, then unnecessary process switches: One to block the process One to resume it Process scheduling must be very strictly enforced.  A process from the corresponding condition queue must be scheduled immediately Scheduler must ensure that no other process enters monitor before activation Reason: condition under which process was activated could change20Reader 1:void beginRead(){if(writeLock || queue(canWrite)){cwait(canRead);}readers++;signal(canRead);}Writer 1:void endWrite(){writeLock = false;if(queue(canRead)csignal(canRead);else if (queue(canWrite))csignal(canWrite);}Writer 2:void beginWrite(){if(readers > 0 || writeLock){cwait(canWrite);}writeLock = true;}21Reader 1 is blocked on canRead.Writer 1 signals canRead.Reader 1 is un-blocked and is ready, but is not immediately scheduled.Writer 2 is scheduled – sets writeLock to true and is ready to write - IS WRITING when timed out.Reader 1 gets scheduled to run – Will increment “readers”, signals to any waiting readers and then PROCEED TO READ.Lampson and Redell modification cnotify() instead of csignal():  Process will notify the first process waiting on condition.  Notified process need not be scheduled immediately  Notifying process need not quit or block. Code must change, such that any process that has to continue will check the condition again.22Reader : Lampson and Redell’s model23void beginRead(){while(writeLock || queue(canWrite)){cwait(canRead);}readers++;cnotify(canRead);}void endRead(){readers--;if(readers == 0){cnotify(canWrite);}}Writer: Lampson and Redell’s model24void beginWrite(){while(readers > 0 || writeLock){cwait(canWrite);}writeLock = true;}void endWrite(){writeLock = false;if(queue(canRead)cnotify(canRead);else if (queue(canWrite))cnotify(canWrite);}Modification allows cbroadcast() cbroadcast(c) – Wake all processes that are waiting on a condition. Example, if n processes are waiting on space in memory.  If “j”