Synchronization Problems in Operating System

• In the implementation we need two semaphores-one to block producers when the buffer is full, another to block consumers when the buffer is empty, and a binary semaphore to guarantee mutex exclusion when the buffer is accessed. Note that the first semaphore is signaled (by a consumer) when the buffer is not full, and the second is signaled (by a producer) when the buffer is not empty.
• The semaphore for blocking producers when buffer is full must have an initial value equal to the buffer size. This is because the buffer is empty initially, we can allow the number of producers to pass through.
• Since each passing through producer causes the counter to be decreased by one, when the buffer is full, the semaphore counter becomes zero and all subsequent produce will be blocked.
• The initial value of the semaphore for blocking consumers is zero, because initially the buffer is empty and no consumer should be allowed to retrieve.
• The binary semaphore for locking the buffer should have an initial value 1, which is obvious.
• Because we have two types of processes, the producer and the consumer, we have he classes ProducerProcess and ConsumerProcess. They are very similar, except for of producer process receives one more argument. NumberofData to indicate the number data items a producer must deposit into the buffer. Here is one implementation of the same pseudocoded in C++.

 # include "ThreadClass.h"
 # define BUFFER SIZE 5 // bounded buffer size
 # define MAX NUM 20 // maximum number of producers/consumers
 # define END -1// "end of data" 
class ProducerProcess : public process 
{
public : Producer Process (int No, int numberofdata); 
private : void Processfunc (); 
int Number ; 
int NumberofData ; // number of data to produce
}; 
class ConsumerProcess : 
{
public process public : ConsumerProcess (int No); 
private : void ProcessFunc () ; 
int Number;
}

• The constructors of both process classes do not require further explanation. The processfunc( )s do have some extensions. In fact, we require the number of producers and the number of consumers to be the same. Each producer deposits some number of non-negative integers, and, after this is done, each producer deposits the end-of-data symbol END. The buffer is declared as an integer array Buffer [ ] of BUFFER _SIZE elements. Semaphore NotFull blocks producers until the buffer is not full, and semaphore NotEmpty blocks consumers untif the buffer is not empty. As mentioned earlier, semaphore NOTFULL has an initial value of BUFFER_SIZE because the buffer can receive BUFFER_SIZE integers before it becomes full. The semaphore NotEmpty has an initial value of 0 because initially the buffer is empty. The initial value for the lock semaphore BUFFERLOCK is 1, because initially we should allow one producer to access the buffer.
• For each iteration, a producer waits on semaphore NotFull until the buffer is not full. locks the buffer, generates and deposits a fandom number, unlocks the buffer, notifies the consumers that the bufer is not empty, and goes back for the next round. After the specified number of data are deposited, a producer follows the same protocol, deposits the END symbol, and then exits.
• For each consumer, it waits on semaphore NotEmpty until the buffer is not empty, locked the buffer, and retrieves a data item. If the data is not END, the consumer displays the result, unlocks the buffer and notifies the producers that the buffer is not full. Otherwise the consumer prints a message, unlocks the buffer, notifies the producers, and exits.

2. Readers and Writers Problem

Readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that no process may access the share for reading or writing while another process is in the act of writing to it. (In particular, it is allowed for two readers to access the share at the same time). A readers-writer lock is a data structure that solves one or more of the readers-writers problems.

The first readers-writers problem

Suppose we have a shared memory area with the constraints detailed above. It is possible to protect the shared data behind a mutex, in which case clearly no thread can access the data at the same time as another writer. However, this solution is suboptimal, because it is possible that a reader R, might have the lock, and then another reader R request access. It would be foolish for R, to wait until R; was done before starting its own read operation ; instead R2 should start right away. This is the motivation for the first readers-writers problems, in which the constraint is added that no reader shall be kept waiting if the share is currently opened for reading. This is also called readers-preference.

The second readers-writers problem

Suppose we have a shared memory area protected by a mutex, as above. This solution is suboptimal, because it is possible that a reader R, might have the lock, a writer W be waiting for the lock, and then a reader R, request access. It would be foolish for R, t0 jump in immediately, ahead of W ; if that happened often enough, W would starve- Instead, W should start as soon as possible. This is the motivation for the second readers writers problem, in which the constraint is added that no writer, once added to the queue shall be kept waiting longer than absolutely necessary. This is also called writers-preference.

The third readers-writers problem

In fact, the solutions implied by both problem statements result in starvation-the first readers-writers problem may starve writers in the queue, and the second readers writers problem may starve readers. Therefore, the third readers-writers problem is sometimes proposed, which adds the constraint that no thread shall be allowed to starve that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time. Solutions to the third readers-writers problem will necessarily sometimes require readers to wait even though the share is opened for reading, a sometimes require writers to wait longer than absolutely necessary.

3. Dining Philosopher Problem

• This classical problem consists of five philosophers who are seated around a table on which are placed five plates of chowmen and five forks each lying between two forks.

• While the philosopher think, they ignore the chowmen and do not require a fork. When a philosopher decides to eat, he must obtain two forks, one from the left of the plate and one from the right of plate. To make the analogy fit the behavior of sequential processes, assume a philosopher can pick up only a single fork at one time. After consuming food, the philosopher replaces the forks and resumes thinking. A philosopher cannot eat while the dining philosopher is eating, since forks are a shared resource.
• The luncheon goes nicely as long as no two adjacent philosopher decide to eat at the same time. However, in case two adjacent philosophers attempt to eat simultaneously a lot of problems arise since a fork is to be shared between two philosophers. It may happen that one of them get hold of the forks and the other may never get the chance to eat. This problem is referred to as dining philosopher problem.

One of the solutions using the semaphores is presented below:

philosopher int P[5];
While (TRUE)
{
   ......!?!?!.....  /*Thinking*/
  P (fork) [j]) ; /* Pick up left fork * /
  P (fork [i + 1] mod 5); /* Pick up right fork * / 
  eat ();
  V (fork [i + 1] mod 5);
  V (fork [i];
}
}
Philosopher 4 () 
{
  While (TRUE) 
  {
   ..../* Thinking * /
    P (fork [0]) ; / * Pick up right fork */
    P (fork [4]); / * Pick up left fork */
    eat ();
    V (fork [4])
    V (fork [0]);
  }
}
     Semaphore fork [5] = {1,1, 1, 1, 1};
   fork (philosopher), 1, 0);
   fork (philosopher), 1, 1); 
   fork (philosopher), 1, 2);
   fork (philosopher), 1, 3);
   fork (philosopher), 4, 0);

4. Sleeping Barber Problem

• Sleeping barber problem is a classic inter-process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are customers, resting when there are none and doing so in an orderly manner. The barber and his customers represent aforementioned processes.
• The analogy is based upon a hypothetical barber shop with one barber, one barber chair, and a number of chairs for waiting customers. When there are no customers, the barber sits in his chair and sleeps. As soon as a customer arrives, he either awakens the barber or, if the barber is cutting someone else’s hair, sits down in one of the vacant chairs. If all of the chairs are occupied, the newly arrived customer simply leaves.

• The most common solution involves using three semaphores : one for any waiting customers, one for the barber (to see if he is idle), and a mutex. When a customer arrives, he attempts to acquire the mutex, and waits until he has succeeded. The customer then checks to see if there is an empty chair for him (either one in the waiting room or the barber chair), and if none of these are empty, leaves. Otherwise the customer takes a seat thus reducing the number available (a critical section). The customer then signals the barber to awaken through his semaphore, and the mutex is released to allow other customers (or the barber) the ability to acquire it. If the barber is not free, the customer then waits. The barber sits in a perpetual waiting loop, being awakened by any waiting customers. Once he is awoken, he signals the waiting customers through their semaphore, allowing them to get their hair cut one at a time.
• Not implementing a proper solution can lead to the usual inter-process communication problems of starvation and deadlock. For example, the barber could end up waiting on a customer and a customer waiting on the barber, resulting in deadlock. Alternatively, customers may not decide to approach the barber in an orderly manner, leading to process starvation as some customers never get the chance for a hair cut even though they have been waiting.
• This problem involves only one barber, and it is therefore also called the single sleeping barber problem. A multiple sleeping barbers problem is similar in the nature of implementation and pitfalls, but has the additional complexity of coordinating several barbers among the waiting customers.

Here is one implementation of the suggested solution :

Function p () means acquire
Function v () means release
+Semaphore Customers
+Semaphore Barber
+Semaphore accessSeats (mutex)
+int NumberOffreeSeats 
The Barber (Process) : 
While (true) /*runs in an infinite loop * / 
Customers.p () /* tries to acquire a customer - if none is available he goes to sleep */
 AccessSeats.p () /* at this time he has been awaken - want to modify the number of available seats */ 
NumberofFreeSeats ++ /* one chair gets free */
 Barber.v() /* the barber is ready to cut */ 
Access Seats.v () /* we don't need the lock on the chairs anymore */ 
/****/
 /*here the barber is cutting hair*/ 
/****/ 
}
The Customer (Process); 
While (not cut) /* as long as the customer is not cut */
} 
accessSeats.p () /* tries to get access to the chairs */ 
if NumberOfFree Seats>0 /* if there are any free seats */ 
{
Number of FreeSeats /* sitting down on a chair */ 
Customers.v () /* notify the barber, who's waiting that there is a customer */
accessSeats.v () /* don't need to lock the chairs anymore */
Barber.p () /* now it's this customers turn but wait if the barber is busy */ notCut = false
}
else / * there are no free seats */ 
accessSeats.v () /* but don't forget to release the lock on the seats */