CS 620 UNH Computer Science Simulating the Barber Problem Project

CS 620
hw7
10/18/2023
Instructions:
1. Late policy: 1 day late: 2 points deducted; 2 days late: 5 points deducted; 3 days late: 10
points deducted; greater than 3 days: will not be graded.
2. We have provided the following files: driver.c, barber.h, makefile.
Do not modify these three files.
3. We have also provided barber.c for you to complete.
4. Submit barber.c
You may also submit a readme file. The readme file should contain any information that
would help with the grading of your assignment. For example, if your program does not run,
give details that will help us give you partial credit.
5. We will be grading on agate, so make sure that your program compiles and runs on agate.
6. MyCourses submission: If submitting readme file (in addition to barber.c) Zip using the
command:
zip barber.zip barber.c readme
Submit barber.zip or barber.c on Canvas.
7. Please do NOT touch your files after submitting. In case there is an error in your submission
file, the TA will be able to confirm the timestamp of your files.
8. I have uploaded two simple C programs AAB.c, AsB.c that list system calls relating to
semaphores, threads, time, and the random number generator.
1 The Barber Problem
Simulate the Barber problem: A Barber’s shop consists of a waiting room with x-1 waiting chairs
and 1 barber chair (where the customer who is being serviced sits). If there are no customers, the
Barber goes to sleep. If a customer arrives and all chairs are taken, then the customer leaves the
shop. If the Barber is busy serving a customer, but chairs are available, then the customer sits in
one of the free chairs. If the Barber is asleep, the customer wakes up the Barber and gets a haircut
immediately (without waiting). Write a program using semaphores to coordinate the Barber and
the customers.
The Barber program should be a time-driven simulation. The user must enter the time duration
for the simulation. The Barber’s shop must be open from the start of the simulation until the end.
Customers arrive at random time intervals. The user must enter the mean inter-arrival time of
1
customer arrivals and the mean time taken by the Barber to service a customer. The customers
either leave immediately (if there are no vacant chairs) or leave after receiving service.
The inputs to the code must be read from input file. The first line of the input file should have
the duration in seconds (integer), the second line should have the mean inter-arrival time in seconds
(integer), the third line should have the mean service time for the Barber in seconds (integer), and
the fourth line should have the number of chairs in the waiting area. For example, the input file:
30
2
4
5
the duration of program execution (in seconds) = 30, the mean inter-arrival time (in seconds)= 2,
the mean Barber service time (in seconds)= 4, the number of chairs in the waiting area= 5.
Note that for this case, the maximum number of customers in the store is 6 since the customer
who is receiving a haircut sits in the barber’s chair. So, the store can have 5 customers in the wait
area plus the customer getting the haircut. If there are no customers in the store when a customer
arrives, he goes directly to the barber’s chair and gets a haircut.
2 Some details
The sample codes shows how to do most (but not all) of the bullets below.
1. 1 thread for Barber, n threads for customers
• 1 thread needs to be created to represent the Barber, and a VARIABLE number of
threads need to be created to represent the customers.
• Note: the sample code AAB.c creates a FIXED number of threads but AsB.c creates
variable number of threads.
• possible solution: for the customer threads, initialize a large array of pthread t ∗ and
dynamically create pthread t for each new customer using malloc(sizeof(pthread t),
storing the return address in the pointer array.
• if you run out of space in the array, you can stop creating new customers.
• if you create a fixed number of customer threads and you don’t use malloc(), then you
will lose 20 points.
• when a thread exits, its space is not freed until the program exits. To free the threads
space, you need to explicitly call free().
2. 2 work functions
• 1 function to be executed by the Barber thread, and 1 function to be executed by ALL
the customer threads.
3. simulator creates threads
2
• the simulator procedure should create the Barber thread, then continuously create customer threads until the simulation time is up; finally, the simulator should wait until all
the created threads complete and exit.
• possible solution: after creating the Barber thread, the simulator could enter a while
loop that quits after the time for the program execution elapses, and in each iteration,
gets a random number for the next customer’s arrival time, and after that time has
elapsed, creates a new customer thread.
4. timing – real vs simulated
• the duration of the program execution is in REAL time, not simulated time. so if the
user enters 60 seconds , then the program should actually run for 1 minute. If the Barber
takes 4 seconds to service a given customer, then 4 seconds should actually elapse in
real time before the Barber thread is free.
5. implementing timing: we have done this part.
6. synchronization with semaphores
• consider how many semaphores needed and their initialization
• consider which variables should be atomic
• you don’t need to use an array of semaphores. If you do, that is fine, but you can write
the Barber code without an array of semaphores. If you do use an array of semaphores,
dynamically allocate space using malloc() and remember to free the space later.
7. atomic variables and condition variables
• try not to use too many atomic variables. You could pass several arguments to a thread
using struct.
• use semaphores for the synchronization between barber and customers.
• but you may use condition variables for synchronization between parent (simulator)
and customers (if needed). After the simulation time is up, the parent must still wait
for the last waiting customer to be served before exiting.
8. arrival time and service time
• note that you are entering the mean value. The random numbers generated will not
equal the mean most of the time since the distribution is not constant.
If you write a threadless program, you get a 0. If you write a program with either the barber or
customer threads missing, you lose half the credit.
3