Classic Problems of Synchronization:
Following are the classic problems of synchronization in operating system:
1. Bounded-Buffer Producer-Consumer Problem:
Suppose there are producer and consumer processes. Producer produces objects, which consumer uses for something. There is one Buffer object used to pass objects from producers to consumers. A Buffer is used to store production of producer.
The problem is to allow producers and consumers to access the Buffer while ensuring the following:
1. The shared Buffer should not be accessed by these processes simultaneously.
2. Consumers do not try to remove objects from Buffer when it is empty.
3. Producers do not try to add objects to the Buffer when it is full.
When condition 3 is dropped (the -Buffer can have infinite capacity), the problem is called the unbounded-buffer problem, or sometimes just the producer-consumer problem.
Producer process
while(l)
{
produce an item in nextp;
wait (empty);
wait(mutex);
add nextp to buffer
signal (mutex);
signal (full);
}
Constfmer process
while(l)
{
wait(full);
wait( mutex);
remove an item from buffer to nextc
signal( mutex);
signal( empty);
consume the item in nextc;
}
How it Works?
Here, buffer is the data structure for storing the production of producer process, mutex is a semaphore for providing mutual exclusion and is initialized to 1. Two semaphores empty and full are used to represent the number of full and empty buffers. The semaphore empty is initialized to n and full to 0.
- The producer puts data in the buffer.
- The buffer holds only n items.
- The consumer gets data from the buffer.
- The producer works only if the buffer is not full.
- The consumer works only if the buffer is not empty.
2. Readers-Writers Problem:
In this problem, a number of concurrent processes require access to some object (such as a file.) Some processes extract information from the object and are called readers. Some processes change or insert information in the object and are called writers. The Bernstein condition states that many readers may access the object concurrently, but if a writer is accessing the object, no other processes (readers or writers) may access the object.
There are two possible policies for doing this:
First Readers-Writers Problem: Readers have priority over writers. It means that unless a writer has permission to access the object, any reader requesting access to object will get it. This may result in a writer waiting indefinitely to access the object.
Second Readers-Writers Problem: Writers have priority over readers. It means that when a writer wishes to access the object, only readers, which have already obtained permission to access the object, are allowed to complete their access. Any readers that request access after the writer has done so must wait until the writer is done. This may result in readers waiting indefinitely to access the object.
There are two concerns:
- Enforce the Bernstein conditions among the processes.
- Enforce the appropriate policy of whether the readers or the writers have priority.
A typical example of this occurs with databases, when several processes are accessing data. Some will want only to read the data, others to change it. The database must implement some mechanism that solves the readers-writers problem.
Shared Data
semaphore mutex = 1;
semaphore wrt = 1;
int readcount = 0;
Writer Process
wait(wrt);
writing is performed
signal (wrt);
Reader Process
wait (mutex);
readcount = readcount + 1;
if (readcount ==1)
wait (wrt); signal (mutex);
reading is performed wait(mutex);
readcount = readcount - 1;
if (readcount == 0)
signal (wrt);
signal (mutex);
3. The Dining Philosophers Problem:
There are five philosophers seated around a dining table, with a plate of food in front of each one. On the table between each pair of philosophers there is a single chopstick.
A philosopher needs to pick up both the left and right chopstick in order to eat. If either is in use by another philosopher, he must wait. The problem is to find a way to synchronize access to the chopsticks to make sure that every philosopher gets a chance to eat.
One solution is to control access to each chopstick with a separate semaphore. When a philosopher wants to pick up a chopslick, it performs P operation on the corresponding semaphore. When chopstick is put back on table, V is performed on the semaphore. Suppose the philosophers are numbered 0-4 and semaphores are also numbered from 0 to 4. For philosopher i, the left chopstick is chopstick i and the right chopstick is chopstick [(i+1)%5].
Shared Data
semaphore chopstick[5];
Philosopher i:
while(1)
{
wait (chopstick[i]);
wait (chopstick[i+1 % 5]);
eat;
signal (chopstick [1]);
signal (chopstick [i+1 % 5]);
think;
}V
