Chapter 3: Term-End June 2011

Solved Paper

Q 1.(a) What is a semaphore? Give solution to sleeping barber problem with the help of semaphore.                                                                              10

Ans. A semaphore is a synchronization mechanism in computer science and operating systems that is used to control access to a common resource in a concurrent or multi-threaded environment. Semaphores are typically implemented as an integer value that can be accessed and modified using two fundamental operations:

- wait() (also known asP ordown): This operation decrements the semaphore's value. If the value becomes negative, thewait() operation blocks the calling process or thread until the semaphore's value becomes greater than or equal to zero.

- signal() (also known asV orup): This operation increments the semaphore's value. If there are any processes or threads blocked on the semaphore, it allows one of them to continue execution.

The Sleeping Barber Problem is a classic synchronization problem that can be solved using semaphores. The problem is described as follows:

Problem Statement: There is a barbershop with a barber and a waiting room with a finite number of chairs. Customers arrive at the barbershop, and if the barber is free, they get a haircut. If the barber is busy, they either wait in the waiting room if there are empty chairs or leave if the waiting room is full.

Here's a solution to the Sleeping Barber Problem using semaphores:

from threading import Thread, Semaphore

# Initialize semaphores

barber_sem = Semaphore(0) # Semaphore for the barber

customer_sem = Semaphore(0) # Semaphore for customers

mutex = Semaphore(1) # Mutex for protecting shared variables

# Shared variables

num_chairs = 5 # Number of chairs in the waiting room

num_customers = 20 # Number of customers

def barber():

while True:

customer_sem.acquire() # Wait for a customer to arrive

mutex.acquire()

num_chairs += 1 # Free up a chair in the waiting room

mutex.release()

barber_sem.release() # Signal that the barber is ready to cut hair

# Cut hair

def customer(customer_id):

mutex.acquire()

if num_chairs> 0:

num_chairs -= 1 # Occupy a chair in the waiting room

customer_sem.release() # Signal that a customer has arrived

mutex.release()

barber_sem.acquire() # Wait for the barber to cut hair

# Get a haircut

else:

mutex.release()

# Leave because there are no empty chairs

if __name__ =="__main__":

barber_thread = Thread(target=barber)

barber_thread.start()

customer_threads = []

for i in range(num_customers):

customer_thread = Thread(target=customer, args=(i,))

customer_threads.append(customer_thread)

customer_thread.start()

barber_thread.join()

for customer_thread in customer_threads:

customer_thread.join()

In this solution, the semaphoresbarber_sem andcustomer_sem are used to coordinate the activities of the barber and customers. Themutex semaphore is used to protect shared variables like the number of chairs. The barber waits for customers and customers wait for the barber using these semaphores, ensuring proper synchronization and avoiding race conditions.

(b) Explain physical and logical clocks. Explain Lamport's scheme of ordering of events.             10

Ans.Physical Clocks: Physical clocks are time-keeping devices that are based on physical processes and provide an absolute notion of time. They are typically realized using hardware components, such as oscillators or crystals, and are used to measure time in a real-world sense. Examples of physical clocks include wall clocks, wristwatches, and system clocks on computer hardware. These clocks are influenced by factors like temperature and other physical characteristics, and they may not always be perfectly synchronized across different devices.

Logical Clocks: Logical clocks, on the other hand, are a concept used in distributed systems and operating systems to order events in a way that is meaningful for the system, regardless of physical time. Logical clocks do not rely on the real-time clock of the system and instead provide a partial order of events in a distributed system, allowing processes to establish causal relationships among events.

Lamport's Scheme of Ordering of Events: Leslie Lamport's logical clock, known as the Lamport timestamp, is a widely used scheme to establish a partial order of events in a distributed system. Lamport timestamps assign a unique timestamp to each event, which allows processes to determine the relative ordering of events, even in the absence of a global clock.

The Lamport timestamp is defined as follows:

1. Each process maintains a local counter.

2. Whenever an event occurs at a process, it increments its local counter.

3. When a process sends a message, it includes its current timestamp (local counter) in the message.

4. When a process receives a message, it updates its own local counter to be greater than the maximum of its current local counter and the timestamp received in the message.

5. Events at different processes are considered to be ordered based on their Lamport timestamps. If event A's timestamp is less than event B's timestamp, A happened before B.

Lamport's scheme ensures that events are causally ordered. If event B's timestamp is greater than event A's timestamp, it is known that event B is causally dependent on event A. However, it's important to note that Lamport timestamps do not necessarily represent real-time values and may no