1Computer Science 4500Operating Systems© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 1Operating SystemsModule 4The Producer-Consumer Problem and Solution MethodsIn This Module…The Producer-Consumer ProblemA “Solution” Using Sleep and Wakeup© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 2SemaphoresEvent CountersMonitorsMessage PassingEquivalence of the MethodsThe Producer-Consumer ProblemTwo types of processes, producers and consumers, wish to communicate.Producers have information to send to© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 3Producers have information to send to the consumers. They place the information in a bounded (limited size) buffer, where consumers can obtain it.The buffer is a shared resource; use of the buffer must be synchronized.Producer-Consumer SynchronizationObviously each access to the buffer must be done in a critical section.When the buffer is full producers cannot© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 4When the buffer is full producers cannot place any more items in it. They therefore go to sleep, to be awakened when a consumer removes an item.Likewise, consumers go to sleep when the buffer is empty, to be awaked by a consumer placing an item in the buffer.A “Solution” for Producer-ConsumerThe next two slides show a proposed solution to the producer-consumer problem using sleep and wakeup.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 5ppIn general, we may have multiple producers and multiple consumers, with appropriate synchronized access to the buffer.In this proposed solution, we will only consider one producer and one consumer.Single Producer/Consumer “Solution”void producer(void)int item;while (TRUE) {produce item(&item);© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 6produce_item(&item);if (count == N) sleep();enter_item(item);count = count + 1;if (count == 1) wakeup(consumer);}}2Single Producer/Consumer “Solution”void consumer(void) {int item;while (TRUE) {if (count == 0) sleep();© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 7if (count == 0) sleep();remove_item(&item);count = count - 1;if (count == N-1) wakeup(producer);consume_item(item);}}Single Producer/Consumer “Solution”Q.The solution, as presented, has a race condition that can result in both processes (producer and consumer) going to sleep© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 8(producer and consumer) going to sleep forever. What is it?Hint.Think about places in the producer code where the processor could be interrupted and directed to execute in the consumer, or vice versa. Considering the assembler language equivalent may help.Single Producer/Consumer “Solution”A.The variable count is shared between the producer and consumer, and access to it is thid© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 9not synchronized.The flaws in the code are apparent when you realize that it is possible for the processor to be interrupted after the test in an if statement, but before the “then” part of the statement is executed.Event Sequence Illustrating the ProblemAssume the buffer is empty, and the consumer reads count (which is zero).At that instant, a context switch occurs and the producer runs© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 10producer runs.The producer enters an item in the buffer, sets count to 1, and sends a wakeup to the consumer. Since the consumer is not sleeping, the wakeup is ignored.Another context switch occurs, and the consumer runs. Just before the last context switch it found that count was zero, so the consumer goes to sleep.Another context switch occurs, and the producer runs until it fills the buffer and goes to sleep.How to Eliminate the Race ConditionOne way to eliminate the race condition is to add a “wakeup waiting” bit. This bit would be set when a wakeup is sent to a process that isn’t sleeping. When the process next © 2008 Stanley A. Wileman, Jr. Operating Systems Slide 11pg pdecides to sleep, it first examines the wakeup waiting bit, and if set, it clears the bit and does not go to sleep.Unfortunately, this doesn’t work with more than one producer and consumer. Adding multiple “wakeup waiting” bits presents a limit that could be exceeded.SemaphoresIn 1965 Edsger Dijkstra (pronounced “dikes truh”) suggested using an integer to record the number of waiting wakeups.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 12gpA new data structure, the semaphore, was created to record the wakeup count and the set of identities of the sleeping processes.Two operations, down and up (historically called P and V) were introduced.3The Semaphore Data StructureA semaphore is a data structure that has two components:a non-negative integer count that indicates the number fitf ilblf llti d© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 13of units of a resource available for allocation, anda set containing the identification of each process waiting for a unit of the resource controlled by the semaphore.Although called a set here, the collection of processes may be ordered by a particular operating system (e.g. first in first out or priority).The Down (P) OperationThe down operation does the following:Is countgreater than zero?• Yes: decrement count and continue.© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 14• No: place current process identification in the set and sleep. When awakened, it repeats the test on count.The down operation is atomic. This means the operation will complete before any other process is allowed to manipulate the semaphore with a down or up operation.The Up (V) OperationThe up operation does the following:Increment count.If the set of waiting processes is not empty, kfh(i hd)© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 15awaken one of them (it moves to the ready state).The up operation is atomic.No process will ever block as a result of performing an up operation.As noted earlier, the selection of the process to be awaked may vary depending on the operating system implementation.Producer-Consumer with SemaphoresAssume there are “N” slots in the buffer.Three semaphores are used in the solution:empty:count(initially N) contains the number of© 2008 Stanley A. Wileman, Jr. Operating Systems Slide 16empty: count(initially N) contains the number of unused slots in the buffer; setcontains ids of producers waiting to add to the buffer.full: count (initially 0)