Process Synchronization – VII – Bounded Buffer Problem

In the previous posts, we have discussed several aspects of process synchronization, which includes discussing a solution of the bounded buffer problem. In this post, we shall discuss a solution to the bounded-buffer problem using semaphores.

THE BOUNDED-BUFFER PROBLEM

In our first post on process synchronization, we had discussed the bounded buffer problem, which is also known as the Producer – Consumer Problem. You can see this post to see what exactly the producer-consumer problem is.

We now discuss a solution to the problem (Producer-Consumer / Bounded buffer )using semaphores. 

  • Producer : Process that produces information to be consumed by the consumer
  • Consumer : Process that consumes information produced by the consumer
  • Problem Statement: Design a solution to allow both – The Producer process and the consumer process to execute concurrently.

We assume that the bounded buffer consists of n slots, with each slot capable of holding one item.

  • The bounded buffer has n slots, each capable of holding one item.
  • We use three semaphores – which have names mutex, empty and full.
    • mutex semaphore → initialized to the value 1, provides mutual exclusion for access to buffer →
    • Empty, full semphores → count the number of empty and full slots respectively. Therefore, empty initialized to n and full initialized to 0.

Let us see what the code does: 

  • The producer produces an item and stores it in the next_produced variable.
  • It then waits on the semaphore – empty. When empty becomes greater than zero, it will decrement it.
  • It then waits for the lock to become available. When the lock is available, it acquires it and proceeds with the insert operation into the slot.
  • After adding the next item produced to the bounded buffer, the producer process calls signal(mutex) to release the lock.
  • Finally, it calls signal(full) to increment the semaphore full, indicating that one item is full.

The consumer process is symmetrical to the producer process.

  • The consumer process waits on the semaphore full. When full > 0, i.e. there is at least one full slot in the bounded buffer, it decrements full because the number of occupied slots will decrease by one once the consumer consumes an item.
  • After this, the consumer acquires the lock on the buffer, i.e. it waits on mutex to become available.
  • After this, the consumer consumes the item, i.e. removes an item from buffer to next_consumed.
  • Finally, it releases the acquired lock (signal(mutex)), and then increments empty (signal(empty)).

In the next post, we shall discuss the Readers-Writers problem, which is another interesting problem involving synchronization.
Source: 1, 2