Dining Philosophers, Monitors, and Condition VariablesAnnouncementsFrom last time...Dining Philosophers ProblemSlide 5Slide 6Slide 7Slide 8Monitors and Condition VariablesSlide 10Slide 11Slide 12Slide 13Slide 14Monitor-based Solution to Dining PhilosophersSlide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22SemaphoresSlide 24Slide 25Slide 26Slide 27Slide 28DeadlockSlide 30Slide 31Slide 32Classic Synchronization ProblemsBounded Buffer Producer/Consumer ProblemSlide 35Slide 36Slide 37Slide 38Slide 39The Readers/Writers ProblemSlide 41Slide 42Slide 43SynchronizationCritical SectionSlide 46Slide 47Disabling InterruptsSlide 49First Try at Lock ImplementationSlide 51Slide 52Atomic Lock ManipulationSlide 54Atomic Lock ManipulationSlide 56Slide 57Slide 58Slide 59Slide 60Slide 61Slide 62Slide 63Bounded Buffer ProblemBounded Buffer Problem (2)Bounded Buffer Problem (3)Readers-Writers ProblemReaders-Writers Problem (2)Readers-Writers Problem (3)Readers-Writers Problem (4)First SolutionFirst Solution (2)Writer PrecedenceWriter Precedence (2)The Sleepy BarberSleepy Barber (aka Bounded Buffer)Cigarette Smoker’s ProblemImplementing SemaphoresImplementing Semaphores: enter() & exit()Implementing Semaphores: Test and Set InstructionUsing the TS InstructionImplementing the General SemaphoreActive vs Passive SemaphoresSlide 84Slide 85Slide 86Slide 87Slide 88Dining Philosophers, Monitors, and Condition VariablesCSCI 3753 Operating SystemsSpring 2005Prof. Rick HanAnnouncements•HW #3 is due Friday Feb. 25, a week+ from now–submitting graphic: .doc OK? - will post an answer–extra office hours Thursday 1 pm - post this•TA finished regrading some HWs that were cut off by moodle•Slides on synchronization online•PA #2 is coming, assigned around Tuesday night•Midterm is tentatively Thursday March 10•Read chapters 9 and 10From last time...•We discussed semaphores•Deadlock•Classic synchronization problems–Bounded Buffer Producer/Consumer Problem–First Readers/Writers Problem–Dining Philosophers ProblemDining Philosophers Problem•N philosophers seated around a circular table–There is one chopstick between each philosopher–A philosopher must pick up its two nearest chopsticks in order to eat–A philosopher must pick up first one chopstick, then the second one, not both at once•Devise an algorithm for allocating these limited resources (chopsticks) among several processes (philosophers) in a manner that is–deadlock-free, and–starvation-freeP1P5P4P3P2Dining Philosophers Problem•A simple algorithm for protecting access to chopsticks:–each chopstick is governed by a mutual exclusion semaphore that prevents any other philosopher from picking up the chopstick when it is already in use by another philosopher semaphore chopstick[5]; // initialized to 1–Each philosopher grabs a chopstick i by P(chopstick[i])–Each philosopher releases a chopstick i by V(chopstick[i])Dining Philosophers Problem•Pseudo code for Philosopher i:while(1) { // obtain the two chopsticks to my immediate right and left P(chopstick[i]); P(chopstick[(i+1)%N]; // eat // release both chopsticks V(chopstick[(i+1)%N]; V(chopstick[i]);}•Guarantees that no two neighbors eat simultaneously, i.e. a chopstick can only be used by one its two neighboring philosophersDining Philosophers Problem•Unfortunately, the previous “solution” can result in deadlock–each philosopher grabs its right chopstick first•causes each semaphore’s value to decrement to 0–each philosopher then tries to grab its left chopstick•each semaphore’s value is already 0, so each process will block on the left chopstick’s semaphore–These processes will never be able to resume by themselves - we have deadlock!Dining Philosophers Problem•Some deadlock-free solutions:–allow at most 4 philosophers at the same table when there are 5 resources–odd philosophers pick first left then right, while even philosophers pick first right then left–allow a philosopher to pick up chopsticks only if both are free. This requires protection of critical sections to test if both chopsticks are free before grabbing them.•we’ll see this solution next using monitors•A deadlock-free solution is not necessarily starvation-free–for now, we’ll focus on breaking deadlockMonitors and Condition Variables•semaphores can result in deadlock due to programming errors–forgot to add a P() or V(), or misordered them, or duplicated them•to reduce these errors, introduce high-level synchronization primitives, e.g. monitors with condition variables, that essentially automates insertion of P and V for you–As high-level synchronization constructs, monitors are found in high-level programming languages like Java and C#–underneath, the OS may implement monitors using semaphores and mutex locksMonitors and Condition Variables•Declare a monitor as follows (looks somewhat like a C++ class): monitor monitor_name { // shared local variables function f1(...) { ... } ... function fN(...) { ... } init_code(...) { ... } } •A monitor ensures that only 1 process/thread at a time can be active within a monitor–simplifies programming, no need to explicitly synchronize•Implicitly, the monitor defines a mutex lock semaphore mutex = 1;•Implicitly, the monitor also defines essentially mutual exclusion around each function–Each function’s critical code is surrounded as follows:function fj(...) { P(mutex) // critical code V(mutex)}•The monitor’s local variables can only be accessed by local monitor functions•Each function in the monitor can only access variables declared locally within the monitor and its parametersMonitors and Condition Variables•Example: monitor sharedcounter { int counter; function add() { counter++;} function sub() { counter--;} init() { counter=0; } }•If two processes want to access this sharedcounter monitor, then access is mutually exclusive and only one process at a time can modify the value of counter–if a write process calls sharedcounter.add(), then it has exclusive access to modifying counter until it leaves add(). No other process, e.g. a read process, can come in and call sharedcounter.sub() to decrement counter while the write process is still in the monitorMonitors and Condition Variables•In the previous sharedcounter example, a writer process may be interacting with a reader process via a bounded buffer–like the solution to the