Lecture 10OutlineReaders/Writers Problem 1Readers/Writers Problem 2Readers/Writers Problem 3Readers/Writers Problem 4Readers/Writers Problem 5Readers/Writers Problem 6Readers/Writers Problem 7Readers/Writers Problem 8Readers/Writers Problem 9Dining Philosophers Problem 1Dining Philosophers Problem 2Dining Philosophers Problem 3Dining Philosophers Problem 4Monitors 1Monitors 2Condition Variables 1Condition Variables 2Condition Variables 3Monitor Issues 1Monitor Issues 2Wednesday, February 2 CS 470 Operating Systems - Lecture 10 1Lecture 10Reminder: Process Management Project and Homework 2 are due today.Thread Synchronization Project and Homework 3 posted to course webpage.Questions?Wednesday, February 2 CS 470 Operating Systems - Lecture 10 2OutlineReaders/Writers problemDining Philosophers problemMonitorsWednesday, February 2 CS 470 Operating Systems - Lecture 10 3Readers/Writers ProblemSome resources allow concurrent access at some times and no concurrent access at other times. For example, if all accesses to a file are reads, we can allow all accesses to happen without synchronization. If some of the accesses are writes, then we need to synchronize them with respect to the reads and other writes, so that readers do not see inconsistent data.Wednesday, February 2 CS 470 Operating Systems - Lecture 10 4Readers/Writers ProblemThis is called the Readers/Writers problem and has many variants involving who has priority. For example,Readers cannot be kept waiting unless a writer is already accessing the resourceWriters cannot be kept waiting, so no new readers are allowed when a writer is ready.Both variants can lead to starvation. Other variants are more complex to handle this.Wednesday, February 2 CS 470 Operating Systems - Lecture 10 5Readers/Writers ProblemConsider a solution to the first variant.The Writer processes are simple. Since they need exclusive access, use a mutex semaphore.shared semaphore write_mutex = 11. Loop 1.1. wait(write_mutex) 1.2. Write object 1.3. signal(write_mutex) 1.4. RSWednesday, February 2 CS 470 Operating Systems - Lecture 10 6Readers/Writers ProblemThe Reader processes are more complex. Synchronization must allow a reader access when there are only readers accessing, but prevent reader access when a writer is accessing.Start with basic read loop with no synch:1. Loop 1.1. 1.2. Read object 1.3. 1.4. RSWednesday, February 2 CS 470 Operating Systems - Lecture 10 7Readers/Writers ProblemFirst, we need to keep track of the number of readers currently accessing the resource. Each reader will increment a counter before it accesses and decrements after it access.shared int read_count = 01. Loop 1.1. Increment read_count 1.2. Read object 1.3. Decrement read_count 1.4. RSWednesday, February 2 CS 470 Operating Systems - Lecture 10 8Readers/Writers ProblemAs before, we need to protect modifications to the counter, so add a mutex semaphore.shared semaphore read_mutex = 11. Loop 1.1. wait (read_mutex) Increment read_count signal (read_mutex) 1.2. Read object 1.3. wait (read_mutex) Decrement read_count signal (read_mutex) 1.4. RSWednesday, February 2 CS 470 Operating Systems - Lecture 10 9Readers/Writers ProblemFinally, we need to synch the readers with the writers. Somewhere a reader must wait on write_mutex, but not all of them. Question is when does this need to happen?Likewise, somewhere a reader must signal on write_mutex, but not all of them. Question is when does this need to happen?Wednesday, February 2 CS 470 Operating Systems - Lecture 10 10Readers/Writers ProblemFinal solution:1. Loop 1.1. wait (read_mutex) Increment read_count if read_count = 1 // first reader wait (write_mutex) // check for writer signal (read_mutex) 1.2. Read object 1.3. wait (read_mutex) Decrement read_count if read_count = 0 // last reader signal (write_mutex) // inform writers signal (read_mutex) 1.4. RSWednesday, February 2 CS 470 Operating Systems - Lecture 10 11Readers/Writers ProblemWhen there are already readers in the CS, other readers just increment read_count and go directly into the CS without regard to writers.If there is a writer in the CS, the first reader waits on write_mutex, while all subsequent readers wait on read_mutex. If there is no writer, the first reader aquires the write_mutex and the last reader to finish releases it.Might want to consider who to do the second variant where writers have priority.Wednesday, February 2 CS 470 Operating Systems - Lecture 10 12Dining Philosophers ProblemSome problems require access to multiple resources at the same time. For example, to print, need access to the file and to the printer.This idea is generalized into the Dining Philosophers problem. In this problem, there are 5 philosophers (P0...P4) sitting around a table. In the middle of the table is a bowl of rice. A philosopher spends his time alternating between eating (CS) and thinking (RS).Wednesday, February 2 CS 470 Operating Systems - Lecture 10 13Dining Philosophers ProblemBetween each philosopher there is one chopstick. In order to eat, a philosopher must obtain the two chopsticks closest to him. When he is done, he puts them back on table.P0P4P1P3P2RICEC0C4C3C2C1Wednesday, February 2 CS 470 Operating Systems - Lecture 10 14Dining Philosophers ProblemObviously, a chopstick can be used by only one philosopher at a time; can use mutex semaphore for each one. For philosopher process Pi:shared semaphore chopstick[5] = {1, 1, 1, 1, 1}1. Loop 1.1. wait (chopstick[ i ]) // left wait (chopstick[(i+1)%5]) // right 1.2. Eat (CS) 1.3. signal (chopstick[ i ]) signal (chopstick[(i+1)%5]) 1.4. Think (RS)Wednesday, February 2 CS 470 Operating Systems - Lecture 10 15Dining Philosophers ProblemThis solution ensures ME of chopstick use, but can cause deadlock. How?What are some possible remedies? Do any of them prevent starvation as well?We will look at general deadlock remedies in next chapter.Wednesday, February 2 CS 470 Operating Systems - Lecture 10 16MonitorsSemaphores work well, but are fragile with respect to correct usage. "Simple" mistakes like forgetting a signal or wait, or doing them in the wrong order, etc., can cause havoc.Once again, bump up the level of abstraction. It would be nice to just say "these are things that need to have synchronized access" and have it just happen.One