Bounded Buffer Problem in OS With Example

The following classical problem of synchronisation are used to test virtually every new proposed synchronisation algorithm.

  • Bounded-Buffer Problem
  • Readers-Writers Problem
  • Dining-Philosophers Problem

Bounded Buffer Problem in OS

Bounded Buffer Problem in OS is a generalisation of the producer-consumer problem wherein access is controlled to a shared group of buffers of a limited size.

Problem Statement:

There is a buffer of n slots and each slot is capable of storing one unit of data. There are two processes running, producer and consumer, which are operating on the buffer.

Tutorialwing operating system Producer Consumer Problem

Producer Consumer Problem

In this solution, the two counting semaphores full and empty keep track of the current number of full and empty buffer respectively (and initialised to 0 and N respectively). The binary semaphore (i.e. Mutex) controls access to the Critical Section. The producer and consumer processes are identical – one can think of the producer as producing full buffers, and the consumer producing empty buffers.

The structure of producer process:

  // produce an item in nextp Wait (empty);
  Wait (Mutex);
  // add the item to the buffer
  Signal (Mutex); 
  Signal (full);
} while (True);

Producer first waits until there is at least one empty slot. Then, it decrements the empty semaphore. It is because there will now be one less empty slot. Since the producer is going to insert data in one of those slots. After performing the operation, the value of full is incremented because producer just filled the slot in the buffer.

The structure of consumer process:

Do {
  Wait (full);
  Wait (Mutex);
  //remove an item from buffer to next
  Signal (Mutex); 
  Signal (empty);
  // consume the item in next
} while (true);

The consumer waits until there is at least one full slot in the buffer. Then, it decrements the full semaphore because the number of occupied slots will be decreased by one. After the consumer completes its operation, the consumer completes the removal operation. Finally, the empty semaphore is initialized by 1. It is because the consumer has just removed data from an occupied slot. Now, slot is empty.

That’s end of tutorial on Bounded Buffer Problem in OS.

Leave a Reply