The Producer – Consumer Problem exists in multiprogramming systems as a program being ran may use two separate interdependent processes in it's operation, a Producer and a Consumer.
The Producer generates output which is then consumed by the Consumer process. As these are two separate processes, they are independent of one another, and so may operate a different speeds. If the consumer process is faster than the producing process, then it will have wait until the data it needs is produced by the producer, and vice versa.
The solution to this difference in speed is to create temporary storage where the shared data can be stored until the other is ready to use it. This temporary storage is called a Buffer. The buffer has a finite size. The consumer cannot consume data (aka Messages) faster than they are produced, the producer cannot produce more messages than can be held within the buffer. If data is produced faster than than it is consumed, the size of the buffer increases, if the consumer is faster than the producer, the size of the buffer decreases. All messages placed into the buffer are of an equal size.
An example of the problem:
int BufferSize = 10;
int BufferItems = 0;
Producer()
{
while(TRUE)
produce item();
if (BufferItems == BufferSize)
{
sleep();
}
enter item();
++BufferItems;
if(BufferItems == 1)
{
start(Consumer);
}
Consumer()
{
while(TRUE)
if(BufferItems == 0)
{
sleep();
}
remove item();
--BufferItems;
if(BufferItems == BufferSize)
{
start (Producer);
}
consume Item();
}
The scenario which causes the problem to occur is that if the consumer process reads the BufferItems variable when it is at 0 and attempts to Sleep(), if when attempting to sleep it is interrupted before entering the Sleep() process by the Producer. Which increases the BufferItems variable (adds a new item to the buffer), the Producer will again try to start the Consumer process. Because the Consumer was still awake when this occurred, the second Start is then lost, which the Producer is unaware of, the Consumer will still perform the first RemoveItem(), but now the BufferItems variable will hold the value 0, despite the Producer producing two items, and since the Consumer only operates when BufferItems is at 1, it will never again remove an item from the buffer.
The interrupting producer is now waiting for the consumer, and the consumer, which missed the second producer's action, is now waiting for the consumer.
This situation is called a Race Condition. A Race Condition is where two processes are both waiting for one another and so results in Dead Lock. Dead Lock is when two resources (Semaphores) are each waiting for the other to perform their respective tasks. Semaphores are classed by the operating system as resources, and Wait and Signal operations claim and release use of these resources. In the example above, the Dead Lock has occurred as the producer resource is waiting for the consumer resource, and the consumer resource is waiting for the producer resource. The producer interrupted the consumer at 'just the wrong time'.
Since resources cannot be shared, once a semaphore, which acts like a guard to the resource, allows access to a resource, the semaphore blocks all other processes from using it until the current process has finished using it and releases it, allowing it's use by other processes.
Where I described the producer interrupting the consumer at 'just the wrong time' is what's called the Critical Section. By allowing both the producer and the consumer into the critical section 'at the same time' the miscommunication was able to occur.
By using Semaphores, Mutual Exclusion can be achieved and prevent this multiple accessing of a non-shareable resource's critical section. Mutual Exclusion prevents more than one process accessing the Critical Section at a time.
An example of the solution:
int SemMax = 10;
typedef int semaphore;
semaphore remaining = SemMax;
semaphore InUse = 0;
Producer()
{
int Message;
while (TRUE)
{
produce Message (Message);
wait (remaining)
enter Message (Message);
signal (InUse);
}
}
Consumer()
{
int Message;
while (TRUE)
{
wait (InUse);
remove Message (Message);
signal (remaining);
consume Message (Message);
}
}
The function of the semaphores initial values:
In this solution the semaphore is controlled by the two Wait and Signal operations. A Signal increases the semaphore's value by 1 and Wait decreases it's value by 1. A semaphore is a non-negative integer, and so will never decrease in value less than 0. The signal operation (+1) replaces the previous examples Start call. A wait operation (-1) upon a zero valued semaphore will cause the InUse semaphore to have it's requested task blocked and stored if there is room left (less than 10 in this example) until another process uses the signal operation, increasing it's value to greater than zero, so allowing it to run. SemMax represents the highest number of requests the semaphore can store and InUse represents the current number of requests stored. The Wait and Signal operations have replaced the previous examples BufferItems variable.
When the program starts, nothing will have been produced by the Producer(), and so the buffer will be empty. Because of this a number of producers can be allowed to run to fill it up (assuming the producer is fast enough compared to the consumer). The SemMax value is therefore used to initialise the Remaining value. Each completed Consumer() process will decrease the Remaining counter by 1, and when the buffer is full, Remaining will become 0, blocking any further Producer() operations. InUse is initialised to 0 because when the program starts, and the buffer is empty, the Consumer() process needs to be blocked as there has been nothing produced for it to use.
This is the book I would recommend for anyone wishing to gain an understanding of the basic fundamentals of operating systems.
The subjects contained within are explained much more clearly than the other books I have read on the same subject. Whilst it may not go into as much depth as other books, I found it was this book which provided me a good solid understanding in an easy to understand way.
Copyright 2009, BinarySoldier.net. All rights reserved. | Privacy Policy