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 as P or down): This operation decrements the semaphore's value. If the value becomes negative, the wait() operation blocks the calling process or thread until the semaphore's value becomes greater than or equal to zero.

- signal() (also known as V or up): 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 semaphores barber_sem and customer_sem are used to coordinate the activities of the barber and customers. The mutex 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 not reflect the actual physical time.

Lamport's logical clocks are crucial in distributed systems for various purposes, such as distributed debugging, concurrent control, and ensuring consistency in distributed databases. They help establish a partial order of events in a distributed environment, even when physical clocks are not synchronized or available.

(c) Draw the Gantt Chart for the FCFS and SJF policy, considering the following set of processes that arrive at time 0, with the length of CPU time given in milliseconds. Also calculate the average waiting and average turnaround time. Process Processing time P1 13 P2 08 P3 19                              10

Ans. To create a Gantt chart for the FCFS (First-Come-First-Serve) and SJF (Shortest Job First) scheduling policies, and calculate the average waiting and average turnaround times for the given set of processes, you can follow these steps.

Processes:

- P1 with processing time 13 ms.

- P2 with processing time 8 ms.

- P3 with processing time 19 ms.

FCFS (First-Come-First-Serve):

1. Since it's FCFS, we execute the processes in the order they arrive.

SJF (Shortest Job First):

1. We'll start with the process that has the shortest processing time.

2. Execute P2 (shortest job).

3. Execute P1 (next shortest job).

4. Execute P3 (remaining job).

Now, let's calculate the average waiting time and average turnaround time for each policy.

FCFS:

- Average Waiting Time (AWT) = (0 + 13 + 21) / 3 = 11.33 ms

- Average Turnaround Time (ATAT) = [(13 - 0) + (21 - 0) + (40 - 0)] / 3 = 24.33 ms

SJF:

- Average Waiting Time (AWT) = (0 + 8 + 21) / 3 = 9.67 ms

- Average Turnaround Time (ATAT) = [(8 - 0) + (21 - 0) + (40 - 0)] / 3 = 23 ms

In this example, SJF results in a shorter average waiting time and average turnaround time compared to FCFS. SJF selects the shortest job to execute next, which can lead to better overall performance, especially when there is a mix of long and short jobs.

(d) What is segmentation? Explain with an example.                        5

Ans. Segmentation is a memory management technique used in operating systems to organize and control how memory is allocated and used by processes. In segmentation, memory is divided into different segments, each with a specific purpose or type of data. This allows for more flexible and efficient memory allocation than traditional contiguous memory allocation, which divides memory into fixed-sized partitions.

Each segment is identified by a unique segment identifier or segment number, and it can have different sizes and attributes. Segments are used to store different parts of a program, such as code, data, stack, and more, in separate logical units.

Here's an example to illustrate segmentation:

Consider a simple program with the following segments:

1. Code Segment (Segment 0): This segment stores the program's executable code. It is marked as read-only...