Classical Problems of Synchronization in OS

Introduction

Synchronization in operating systems (OS) is a critical concept, pivotal for maintaining harmony among multiple processes. This technique ensures that shared resources are accessed in an orderly manner, preventing conflicts & ensuring efficiency. Grasping this concept is essential for students delving into the intricacies of OS design & functionality.

In this article, we will learn about different synchronization problems in operating systems. 

Synchronization Problems

Bound-Buffer Problem

In computing, the Bound-Buffer problem is a classical synchronization challenge. It's about managing data in a buffer that has limited capacity. Picture a scenario where multiple processes are either putting data into the buffer (producers) or taking data out (consumers). The crux is to ensure that a producer doesn’t add data to a full buffer, & a consumer doesn’t try to remove data from an empty one. 

This problem is critical because it mirrors real-world scenarios in OS where resource allocation needs to be managed efficiently.

Code Example

import threading
import time
buffer = []
MAX_ITEMS = 10
semaphore = threading.Semaphore()
def producer():
    global buffer
    while True:
        semaphore.acquire()
        if len(buffer) < MAX_ITEMS:
            item = "Data"
            buffer.append(item)
            print(f"Produced {item}")
        semaphore.release()
        time.sleep(1)

def consumer():
    global buffer
    while True:
        semaphore.acquire()
        if buffer:
            item = buffer.pop(0)
            print(f"Consumed {item}")
        semaphore.release()
        time.sleep(1)

p_thread = threading.Thread(target=producer)
c_thread = threading.Thread(target=consumer)

p_thread.start()
c_thread.start()

In this Python example, we use threading & a semaphore to manage the buffer. The producer adds an item if the buffer isn’t full, & the consumer removes an item if the buffer isn’t empty. The semaphore acts as a lock, ensuring that only one operation occurs at a time.

Sleeping Barber Problem

The Sleeping Barber problem is another fascinating synchronization scenario. It simulates a barber shop with one barber, a barber chair, & a waiting room with several chairs. The challenge arises when the barber must sleep if there are no customers & be woken up as soon as a customer arrives. Conversely, if the waiting room is full, customers must leave. This problem teaches the nuances of process synchronization & resource allocation in operating systems.

Code Example

import threading
import random
import time
waiting_chairs = 5
waiting_room = []
barber_ready = threading.Semaphore(0)
customer_ready = threading.Semaphore(0)
mutex = threading.Lock()

def barber():
    while True:
        customer_ready.acquire()
        mutex.acquire()
        print("Barber is cutting hair")
        waiting_room.pop(0)
        mutex.release()
        barber_ready.release()
        time.sleep(random.uniform(0.5, 2))

def customer():
    mutex.acquire()
    if len(waiting_room) < waiting_chairs:
        waiting_room.append("Customer")
        print(f"Customer sitting in waiting room. Waiting customers: {len(waiting_room)}")
        customer_ready.release()
        mutex.release()
        barber_ready.acquire()
    else:
        print("Waiting room full, customer leaving")
        mutex.release()

for _ in range(10):
    threading.Thread(target=customer).start()
    time.sleep(random.uniform(0.1, 1))

threading.Thread(target=barber).start()

In this Python script, semaphores & a mutex lock manage the interactions between the barber & customers. The barber waits for a customer to be ready (customer_ready), & a customer waits for the barber (barber_ready). Mutex ensures that modifications to the waiting room are thread-safe.

Dining Philosophers Problem

The Dining Philosophers problem is a classic example used to illustrate synchronization issues in an OS. It involves a circular table with five philosophers, who do nothing but think and eat. Between each philosopher, there is a fork. A philosopher needs both forks to eat, leading to a potential deadlock if each philosopher picks up the fork on their left simultaneously.

Code Example

import threading
class Philosopher(threading.Thread):
    def __init__(self, index, fork_on_left, fork_on_right):
        threading.Thread.__init__(self)
        self.index = index
        self.fork_on_left = fork_on_left
        self.fork_on_right = fork_on_right

    def run(self):
        while True:
            self.think()
            self.eat()
    def think(self):
        print(f"Philosopher {self.index} is thinking.")
    
    def eat(self):
        fork1, fork2 = self.fork_on_left, self.fork_on_right
        with fork1:
            with fork2:
                print(f"Philosopher {self.index} is eating.")

forks = [threading.Lock() for _ in range(5)]
philosophers = [Philosopher(i, forks[i%5], forks[(i+1)%5]) for i in range(5)]

for p in philosophers:
    p.start()

 

This Python code models the dining philosophers. Each philosopher is a thread, alternating between thinking & eating. Forks are represented by locks. Philosophers must acquire locks on both their left & right forks to eat, preventing deadlock by always acquiring the lower-numbered fork first.

Readers and Writers Problem

The Readers and Writers problem addresses a situation where a shared resource (like a database) is accessed by multiple processes. The challenge is ensuring that while this resource can be read by multiple readers simultaneously, writers require exclusive access. This problem is crucial in understanding how OS manages concurrent access to shared resources.

Code Example

import threading
import time
class Database:
    def __init__(self):
        self.readers = 0
        self.resource = threading.Lock()
        self.access_to_readers = threading.Lock()
    def read(self, reader_id):
        with self.access_to_readers:
            self.readers += 1
            if self.readers == 1:
                self.resource.acquire()
        print(f"Reader {reader_id} is reading")
        time.sleep(1)
        with self.access_to_readers:
            self.readers -= 1
            if self.readers == 0:
                self.resource.release()
    def write(self, writer_id):
        print(f"Writer {writer_id} is waiting to write")
        self.resource.acquire()
        print(f"Writer {writer_id} is writing")
        time.sleep(2)
        self.resource.release()
database = Database()
def reader(id):
    while True:
        database.read(id)
def writer(id):
    while True:
        database.write(id)
for i in range(5):
    threading.Thread(target=reader, args=(i,)).start()
    threading.Thread(target=writer, args=(i,)).start()

In this Python example, the Database class uses locks to manage access. The readers counter tracks the number of active readers. If a reader is reading, writers must wait. Writers obtain exclusive access with resource.acquire() before writing.

Frequently Asked Questions

Why is synchronization important in operating systems?

Synchronization in OS ensures that processes operate smoothly without interfering with each other's operations, especially when accessing shared resources.

How do semaphores solve synchronization problems?

Semaphores act as signaling mechanisms, letting processes notify each other regarding the availability or unavailability of a resource, thus preventing conflicts.

What is deadlock, and how is it related to these problems?

Deadlock occurs when two or more processes are unable to proceed as each waits for the other to release a resource. It's a critical concern in synchronization problems, where resource allocation is key.