Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Synchronization Problems
2.1.
Bound-Buffer Problem
2.2.
Code Example
3.
Sleeping Barber Problem
3.1.
Code Example
4.
Dining Philosophers Problem
4.1.
Code Example
5.
Readers and Writers Problem
5.1.
Code Example
6.
Frequently Asked Questions
6.1.
Why is synchronization important in operating systems?
6.2.
How do semaphores solve synchronization problems?
6.3.
What is deadlock, and how is it related to these problems?
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Classical Problems of Synchronization in OS

Author Rahul Singh
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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.

Classical Problems of Synchronization in OS

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. 

Bound-Buffer Problem

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

Sleeping Barber Problem

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.

Dining Philosophers Problem

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.

Readers and Writers Problem

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.

Conclusion

Understanding classical synchronization problems in OS is pivotal for students venturing into software development & system design. These problems illustrate how to manage shared resources efficiently & effectively, a core aspect of modern computing. By mastering these concepts, students can design more robust & efficient systems.

You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSADBMSCompetitive ProgrammingPythonJavaJavaScript, etc. 

Also, check out some of the Guided Paths on topics such as Data Structure and AlgorithmsCompetitive ProgrammingOperating SystemsComputer Networks, DBMSSystem Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.

Previous article
Time Sharing Operating System
Next article
Translation Lookaside Buffer (TLB) in OS
Live masterclass