Classical Problems of Synchronization and Monitors in OS

Classical Problems of Synchronization and Monitors in OS

In this tutorial, you will learn about the main classical problems of synchronization and monitors in OS in detail with an explanation. We will also discuss

Bounded Buffer Problem
Dining Philosopher’s Problem
Dining Philosopher’s Solution using Monitors
Implementation of the solution in Python
Implementing a Monitor using Semaphores
Resuming Processes Within a Monitor

1. Bounded Buffer Problem

• The bounded buffer problem is a classic problem in operating system design and concurrent programming. It is also known as the producer-consumer problem. The problem involves two types of processes, producers, and consumers, which share a fixed-size buffer.
• The goal of producers is to produce data and store it in the buffer, while the consumers’ task is to retrieve data from the buffer and process it. The problem arises when producers and consumers run concurrently and access the buffer simultaneously, which may lead to race conditions and synchronization issues.
• To solve the bounded buffer problem, synchronization mechanisms such as semaphores, mutexes, and condition variables are used. One common solution to the problem is to use a counting semaphore to keep track of the number of available slots in the buffer.
• When a producer wants to produce data, it first waits on the counting semaphore. If there are available slots in the buffer, the producer can write to the buffer, and the semaphore is decremented. If the buffer is full, the producer is blocked until a consumer consumes some data and the semaphore is incremented.
• Similarly, when a consumer wants to consume data, it waits on the counting semaphore. If there is data in the buffer, the consumer can read it, and the semaphore is incremented. If the buffer is empty, the consumer is blocked until a producer produces some data and the semaphore is decremented.
• By using these synchronization mechanisms, we can ensure that producers and consumers access the buffer in a mutually exclusive manner and avoid race conditions and synchronization issues.

2. Dining Philosopher’s Problem

The Dining Philosophers Problem is a classic synchronization problem in computer science and operating systems. The problem was first presented by Edsger Dijkstra in 1965.

The problem is as follows: there are five philosophers sitting at a round table. Each philosopher has a plate of spaghetti in front of them, and a fork on each side of their plate. The philosophers alternate between thinking and eating. In order to eat, a philosopher must have both forks next to them. However, only one fork can be picked up at a time, and a philosopher cannot start eating until they have both forks.

The problem arises when all of the philosophers pick up their left fork at the same time, and then all try to pick up their right fork at the same time. This results in a deadlock, where no philosopher can start eating.

The Dining Philosophers Problem can be solved using various synchronization techniques, such as semaphores or mutexes. One solution involves using a global resource, such as a waiter, to arbitrate access to the forks. Another solution involves allowing only a certain number of philosophers to pick up their left fork at the same time, thus avoiding the deadlock.

The Dining Philosophers Problem is a fundamental problem in concurrent programming and illustrates the importance of synchronization and deadlock avoidance in operating systems

Dining Philosopher’s Solution using Monitors

One solution to this problem is to use a monitor, which is a language construct that provides mutual exclusion and condition synchronization. Here is how the solution using monitors works:

1. Create a monitor with the following procedures:
   • pickup_forks(int i): This procedure is called by philosopher i when they want to eat. The monitor checks if both forks are available (i.e., not held by any philosopher), and if so, marks them as held by philosopher i. If not, the philosopher is put to sleep until the forks are available.
   • return_forks(int i): This procedure is called by philosopher i when they are finished eating. The monitor marks both forks as available, and wakes up any philosophers that were waiting for either fork.
2. Initialize an array of forks of size n, where forks[i] represents the fork to the left of philosopher i.
3. Initialize an array of philosophers of size n, where philosophers[i] represents philosopher i.
4. For each philosopher i, create a separate thread that repeatedly executes the following loop:
   • Think for a random amount of time.
   • Call pickup_forks(i) to pick up both forks.
   • Eat for a random amount of time.
   • Call return_forks(i) to return both forks.

Here is the implementation of the solution in Python:

import threading
import time
import random


class DiningPhilosophers:
def __init__(self, n):
self.forks = [threading.Lock() for _ in range(n)]
self.condition = threading.Condition()

def pickup_forks(self, i):
left = i
right = (i + 1) % len(self.forks)
with self.condition:
while not self.forks[left].acquire(blocking=False) or not self.forks[right].acquire(blocking=False):
self.condition.wait()

def return_forks(self, i):
left = i
right = (i + 1) % len(self.forks)
with self.condition:
self.forks[left].release()
self.forks[right].release()
self.condition.notify_all()


def philosopher(i, dp):
while True:
print(f"Philosopher {i} is thinking")
time.sleep(random.uniform(0, 1))
print(f"Philosopher {i} is hungry")
dp.pickup_forks(i)
print(f"Philosopher {i} is eating")
time.sleep(random.uniform(0, 1))
dp.return_forks(i)

 

if __name__ == '__main__':
n = 5
dp = DiningPhilosophers(n)
threads = []
for i in range(n):
t = threading.Thread(target=philosopher, args=(i, dp))
t.start()
threads.append(t)
for t in threads:
t.join()

Implementing a Monitor using Semaphores

A monitor is a synchronization construct that allows multiple threads to have a mutual exclusion on a shared resource. Semaphores are a commonly used synchronization primitive for implementing monitors. Here’s an example implementation of a monitor using semaphores in Python:

from threading import Semaphore

class Monitor:
def __init__(self):
self.mutex = Semaphore(1) # binary semaphore for mutual exclusion
self.empty = Semaphore(0) # semaphore for empty condition
self.full = Semaphore(1) # semaphore for full condition
self.buffer = None # shared resource


def produce(self, data):
self.full.acquire() # wait until buffer is not full
self.mutex.acquire() # acquire mutual exclusion
self.buffer = data # produce data
self.mutex.release() # release mutual exclusion
self.empty.release() # signal that buffer is not empty

 

def consume(self):
self.empty.acquire() # wait until buffer is not empty
self.mutex.acquire() # acquire mutual exclusion
data = self.buffer # consume data
self.buffer = None # reset buffer
self.mutex.release() # release mutual exclusion
self.full.release() # signal that buffer is not full
return data

In this example, the Monitor class has three semaphores and a shared resource called the buffer. The mutex semaphore ensures that only one thread can access the buffer at a time, while the empty and full semaphores implement the empty and full conditions, respectively.

The producing method waits until the buffer is not full (full.acquire()) and then acquires mutual exclusion (mutex.acquire()) to produce the data and update the buffer. Once the data is produced and the buffer is updated, mutual exclusion is released (mutex.release()) and the empty semaphore is signaled (empty.release()) to indicate that the buffer is not empty.

The consume method waits until the buffer is not empty (empty.acquire()) and then acquires mutual exclusion (mutex.acquire()) to consume the data from the buffer. Once the data is consumed and the buffer is reset, mutual exclusion is released (mutex.release()) and the full semaphore is signaled (full.release()) to indicate that the buffer is not full. The method returns the consumed data.

This implementation ensures that the produce and consume methods are executed atomically and that the buffer is not accessed by multiple threads simultaneously.

Resuming Processes Within a Monitor

A monitor is a synchronization construct that allows multiple threads to coordinate their access to shared resources. Typically, a monitor provides mutual exclusion and condition variables for thread synchronization.

When a thread enters a monitor, it acquires the monitor’s lock, which prevents other threads from entering the monitor until the lock is released. If a thread needs to wait for a condition to become true, it can release the lock and wait on a condition variable. When another thread signals or broadcasts the condition variable, the waiting thread is awakened and reacquires the lock before resuming execution.

To resume a process within a monitor, the following steps should be followed:

1. Acquire the monitor’s lock: The thread that wants to resume the process should acquire the monitor’s lock before making any changes to the shared data structures.
2. Check if the process is in a wait state: If the process is waiting for a condition to become true, it will be blocked on a condition variable. The thread should check if the process is in a wait state by examining the state of the relevant condition variable.
3. Signal or broadcast the condition variable: If the process is waiting on a condition variable, the thread should signal or broadcast the variable to wake up the waiting process. Signaling wakes up one thread that is waiting on the condition variable, while broadcasting wakes up all threads that are waiting on the variable.
4. Release the monitor’s lock: After signaling or broadcasting the condition variable, the thread should release the monitor’s lock to allow other threads to enter the monitor and access the shared data structures.
5. Resume the process: The awakened process will reacquire the monitor’s lock and resume execution from the point where it was blocked.

It is important to note that resuming a process within a monitor requires careful coordination between threads to prevent race conditions and other synchronization errors. Therefore, it is recommended to use monitor constructs provided by a high-level language or operating system rather than implementing monitors from scratch.