Sami Faiz Qureshi Assignment # 3

2020-CE-009

ASSIGNMENT NUMBER 03

SCENARIO

Our barbershop has three chairs, three barbers, and a waiting area that can accommodate four
customers on a sofa and that has standing room for additional customers. Fire codes limit the total
number of customers in the shop to 20. A customer will not enter the shop if it is filled to capacity with
other customers. Once inside, the customer takes a seat on the sofa or stands if the sofa is filled. When
a barber is free, the customer that has been on the sofa the longest is served and, if there are any
standing customers, the one that has been in the shop the longest takes a seat on the sofa. When a
customer’s haircut is finished, any barber can accept payment, but because there is only one cash
register, payment is accepted for one customer at a time. The bar- bers divide their time among cutting
hair, accepting payment, and sleeping in their chair waiting for a customer.

Shared variables

customers = 0
mutex = Semaphore(1)
mutex2 = Semaphore(1)
sofa = Semaphore(4)
customer1 = Semaphore(0)
customer2 = Semaphore(0)
payment = Semaphore(0)
receipt = Semaphore(0)
queue1 = []
queue2 = []

Customer thread

self.sem1 = Semaphore(0)
self.sem2 = Semaphore(0)
mutex.wait()
if customers == 20:
mutex.signal()
balk()
customers += 1
queue1.append(self.sem1)

Operating System
Sami Faiz Qureshi Assignment # 3
2020-CE-009

mutex.signal()
# enterShop()
customer1.signal()
self.sem1.wait()
sofa.wait()
# sitOnSofa()
self.sem1.signal()
mutex2.wait()
queue2.append(self.sem2)
mutex2.signal()
customer2.signal()
self.sem2.wait()
sofa.signal()
# getHairCut()
mutex.wait()
# pay()
payment.signal()
receipt.wait()
customers -= 1
mutex.signal()

Barber thread

customer1.wait()
mutex.wait()
sem = queue1.pop(0)
sem.signal() sem.wait()
mutex.signal()
customer2.wait()
mutex2.wait()
sem2 = queue2.pop(0)
sem2.signal()
mutex2.signal()
# cutHair() payment.wait()
# acceptPayment() receipt.signal()

Operating System
Sami Faiz Qureshi Assignment # 3
2020-CE-009

INTRODUCTION

A semaphore is a signaling mechanism and a thread that is waiting on a semaphore can be

A semaphore uses two atomic operations, wait and signal for process synchronization.
A Semaphore is an integer variable, which can be accessed only through two operations wait()
and signal().
There are two types of semaphores: Binary Semaphores and Counting Semaphores.

LITERATURE REVIEW AND BACKGROUND

On the basis of synchronization, processes are categorized as one of the following two types:

Independent Process: The execution of one process does not affect the execution of other
processes.
Cooperative Process: A process that can affect or be affected by other processes executing in
the system.

Process synchronization problem arises in the case of Cooperative process also because
resources are shared in Cooperative processes.

BLOCK DIAGRAM

Operating System
Sami Faiz Qureshi Assignment # 3
2020-CE-009

PSEUDO CODE

Semaphore Wait Operation Signal Operation

sofa Customer waits for seat on sofa customer leaving sofa signal

barber_chair customer waits for empty barber customer waiting for sofa
chair

cust_read barber waits until a customer is in barber signal when that barbers
the chair chair is empty

finished Customer waits until his haircut is barber signal when done
complete cutting hair of this customer

leave_b_chair barber waits until customer gets up customer signals barber when
from the chair customer gets up from chair

payment cashier waits for a customer to pay customer signals cashier that
he has paid

receipt customer waits for a receipt for payment cashier signals that payment
has been accepted

coord wait for a barber resource to be free signal that a barber resource
to perform either the hair cutting or is free
cashiering function

First, note that the barber thread pulls customers from the head of queue2, which represents the sofa,
so once the barber pulls a customer, that customer is the one waiting for the longest time on the sofa.
Second, note that once a customer is pulled out of queue2, the hair cut itself does not take any time,
and the customer moves to payment. So the way it is written, customers are pulled from the queue and
moved the payment immediately. Haircut is instantaneous.
So if another customer comes and moves through the queues, the only way it can be picked is if there is
another barber and the second customer is at the head of the queue. But, if the second customer is at
the head of the queue, that means another barber already picked the first customer. So, that really
cannot happen.

Operating System
Sami Faiz Qureshi Assignment # 3
2020-CE-009

About your question regarding self.sem1: its purpose is to wake up the customer once the customer is
picked from the queue. sem1 corresponds to the queue for customers standing, sem2 corresponds to
the sofa. The customer adds the semaphore to the queue, and waits on it, so when the barber thread
picks it up, it can wake up the customer. So it can't really enforce ordering, it is there to wake up the
customer when he/she changes location. The ordering is enforced by the queue.

CONCLUSION AND LIMITATIONS

In semaphores there is no spinning, hence no waste of resources due to no busy waiting. That is because
threads intending to access the critical section are queued. And could access the priority section when
they are de-queued, which is done by the semaphore implementation itself, hence, unnecessary CPU
time is not spent on checking if a condition is satisfied to allow the thread to access the critical section.

Semaphores permit more than one thread to access the critical section, in contrast to alternative
solution of synchronization like monitors, which follow the mutual exclusion principle strictly. Hence,
semaphores allow flexible resource management.
Finally, semaphores are machine independent, as they are implemented in the machine independent
code of the microkernel services.

REFERENCE

Operating System by Silberschatz

Operating System