-> Some inter-process communication primitives cause the calling process to be blocked instead of wasting CPU time when they are not allowed to enter their critical regions.
-> One of the simplest pair is the sleep and wakeup.
-> Sleep is a system call that causes the caller to block, that is, be suspended until another process wakes it up.
-> The wakeup call has one parameter, the process to be awakened.
-> Alternatively, both sleep and wakeup each have one parameter, a memory address used to match up sleep with wakeup.
-> As an example of how these primitives can be used, let us consider the producer-consumer problem (also known as the bounded-buffer problem).
-> Two processes share a common, fixed size buffer.
-> One of them, the producer, puts information into the buffer, and
the other one, the consumer, takes it out.
-> Trouble arises when the producer wants to put a new item in the buffer, but buffer is already full.
-> The solution for the producer is to go to sleep whenever the buffer is full.
-> When the consumer removes one or more items from the buffer and vacant slots will be available, consumer awakens the producer.
-> Similarly, if the consumer wants to remove an item from the buffer and sees that the buffer is empty, it goes to sleep until the producer puts something in the buffer and wakes it up.
-> This approach sounds simple enough, but it leads to the same kinds of race conditions we saw earlier with the spooler directory.
-> To keep track of the number of items in the buffer, we will need a variable, count.
-> Buffer can hold maximum N data items. The producer first check the value of count, if it is N then producer will go to sleep.
-> If count is less than N, then the producer will add an item and increment count.
-> The consumer’s code is similar: first test count to see if it is 0.
-> If it is, go to sleep, if it is nonzero, remove an item and decrement the counter.
-> Each of the processes also tests to see if the other should be awakened, and if so, wakes it up.
-> The code for both producer and consumer is shown below
-> The race condition can occur in producer consumer example because access to count is unconstrained.
-> The following situation could possibly occur.
-> The buffer is empty and the consumer has just count to see if it is 0.
-> At that instant, the scheduler decides to stop running the consumer temporarily and start running the producer.
-> The producer inserts an item in the buffer, increments count, and notices that it is now 1. Reasoning that count was just 0, and thus the consumer must be sleeping, the producer calls wakeup to wake the consumer up.
-> Unfortunately, the consumer is not yet logically asleep, so the wakeup signal is lost.
-> When the consumer next runs, it will test the value of count it previously read, find it to be 0, and go to sleep. Sooner or later the producer will fill up the buffer and also go to sleep. Both will sleep forever.
-> The essence of the problem here is that a wakeup sent to a process that is not (yet) sleeping is lost.
-> The simpler solution to lost wake up signal is to add wakeup waiting bit.
-> When a wakeup is sent to a process that is still awake, this bit is set.
-> Later, when the process tries to go to sleep, if the wakeup waiting bit is on, it will be turned off, but the process will stay awake.
-> The wakeup waiting bit is a piggy bank for wakeup signals.
-> But with three or more processes one wakeup waiting bit is insufficient. So, the problem of race condition will be still there.
Post a Comment