Write a program which implements a solution to the sleeping barber problem Detai

Question

Write a program which implements a solution to the sleeping barber problem
Details:

The sleeping barber synchronization problem is this: a barbershop consists of a waiting room with n-1 chairs, and a barber room with one chair (for a total of n chairs). There are x clients and one barber in the system. The following rules apply:
If there are no clients in his shop, the barber goes to sleep.
If a client comes in, and the barber is asleep, the client wakes the barber and gets a haircut.
If the barber is busy, and there is a chair available, the client sits and waits.
If there are no chairs available when a client arrives, he leaves.

Main program

Your main program will spawn off one barber thread and x client threads, which will shares resources (chairs) using semaphores for synchronization.

Here is the skeleton for main():

int main(int argc, char *argv[]) {
/* 1. Get command line arguments */
/* 2. Initialize semaphores */
/* 3. Create barber thread. */
/* 4. Create client threads. */
/* 5. Sleep. */
/* 6. Exit. */
}

Main will take 4 arguments:
1. The length of time the program should run.
2. The number of client threads.
3. The number of chairs in the waiting room.
4. The maximum amount of time a client can wait between attempts to get a haircut.

Essentially, we need to keep track of how many chairs are available (using a chair count and a mutex to protect it), how many clients are ready and waiting (counting semaphore), and whether the barber is ready (mutex semaphore). These are our shared variables. Name your counter numchairs and your semaphores chairs_mutex , sem_client, and sem_barber.
Initialization:
The num_chairs variable should be initialized to the value given on the command line (the number of chairs total = n).
The chairs_mutex should be initialized to 1 since no process is in its critical section initially (meaning that the first process to call wait() will succeed).
The sem_client semaphore should be initialized to 0 since there are no clients initially ready.
The sem_barber semaphore should be initialized to 0 since the barber is not ready for a customer initially.
#include <semaphore.h>
sem_t mutex;

/* create the semaphore */
sem_init(&mutex, 0, 1);

/* acquire the semaphore */
sem_wait(&mutex);

/***** critical section *****/

/* release semaphore */
sem_post(&mutex);

When creating the threads, you can use the pthread functions detailed in figure 4.9 on page 161. The function calls are pthread_attr_init(), pthread_create(), pthread_join(), and pthread_exit(). You will need to write a barber and a client function for the threads to begin execution in. We'll cover this below.

Once the main program has created all the threads, it will sleep for the number of seconds specified on the command line.

Finally, when the main program wakes back up, it should exit. All the other threads will be terminated when the parent thread exits (using exit() but not pthread_exit()).

Barber and client functions

The barber thread will wait for a client, give a haircut and repeat. The haircuts will take different amounts of time (randomly distributed). Here is a skeleton for the barber function:

void *barber(void *param) {
int worktime;

while(1) {
/* wait for a client to become available (sem_client) */
/* wait for mutex to access chair count (chair_mutex) */
/* increment number of chairs available */
/* signal to client that barber is ready to cut their hair (sem_barber) */
/* give up lock on chair count */
/* generate random number, worktime, from 1-4 seconds for length of haircut. */
/* cut hair for worktime seconds (really just call sleep()) */
}

rand() returns a pseudo-random integer value between 0 and RAND-MAX. We will use rand() to generate the barber's work time and the client's time between haircuts.
We'll use a uniform distribution between 1 and the maximum interval. You can get a number from rand() and mod it by 4 (ex. num % 4) to get a number from the set {0,1,2,3}. So you would then add 1 to get a number from the set {1,2,3,4}. In either case, you pass this number to sleep().

The client threads will see if there is a chair available, then either leave (if no chair), or wait for the barber and get a haircut, and repeat. The clients will wait different amounts of time between haircuts (randomly distributed). Here is a skeleton for the client function:

void *client(void *param) {
int waittime;

while(1) {
/* wait for mutex to access chair count (chair_mutex) */
/* if there are no chairs */
/* free mutex lock on chair count */
/* else if there are chairs */
/* decrement number of chairs available */
/* signal that a customer is ready (sem_client) */
/* free mutex lock on chair count */
/* wait for barber (sem_barber) */
/* get haircut */
/* generate random number, waittime, for length of wait until next haircut or next try. Max value from command line. */
/* sleep for waittime seconds */
}
}

Synchronization

Your code must be written so that there are no race conditions when accessing the shared variables and so that there is no deadlock. You should determine this by examining your solution and your output. You do not need to worry about starvation (although that would be interesting). Remember to initialize the mutex semaphores and to initialize the number of chairs based on the command line argument.

Output:

Main program:
When beginning execution, print a message "Main thread beginning".
When the barber thread is created, print a message "Creating barber thread with id x" where x is the thread id. The thread id is returned when you create a thread.
For each client thread created, print a message "Creating client thread with id x" where x is the thread id.
Before the call to sleep, print "Main thread sleeping for x seconds" where x is the runtime variable from the command line.
Before the main thread exits, print "Main thread exiting".

Barber thread:
Each time the barber gives a haircut, print a message "Barber: Working for y seconds" where y is the number of seconds.
Each time the barber changes the number of available chairs, print a message "Barber: Number of chairs available = y" where y is the number of chairs available.

Client threads:
Each time a client thread gets a haircut, print a message "Client: Thread x getting a haircut" where x is the thread id.
Each time a client thread leaves with no haircut, print a message "Client: Thread x leaving with no haircut" where x is the thread id.
Each time a client thread goes to sleep, print a message "Client: Thread x waiting y seconds before attempting next haircut" where x is the thread id and y is the number of seconds.
Each time a client thread changes the number of available chairs, print a message "Client: Number of chairs available = y" where y is the number of chairs available.

Run your program, first with 3 chairs and 3 clients, and then with 3 chairs and 8 clients and hand in the output.

Explanation / Answer

This is the bulk of what you need to do, you can adjust as necessary: #define _REENTRANT #include #include #include #include #include // The maximum number of customer threads. #define MAX_CUSTOMERS 25 // Function prototypes... void *customer(void *num); void *barber(void *); void randwait(int secs); // Define the semaphores. // waitingRoom Limits the # of customers allowed // to enter the waiting room at one time. sem_t waitingRoom; // barberChair ensures mutually exclusive access to // the barber chair. sem_t barberChair; // barberPillow is used to allow the barber to sleep // until a customer arrives. sem_t barberPillow; // seatBelt is used to make the customer to wait until // the barber is done cutting his/her hair. sem_t seatBelt; // Flag to stop the barber thread when all customers // have been serviced. int allDone = 0; int main(int argc, char *argv[]) { pthread_t btid; pthread_t tid[MAX_CUSTOMERS]; long RandSeed; int i, numCustomers, numChairs; int Number[MAX_CUSTOMERS]; // Check to make sure there are the right number of // command line arguments. if (argc != 4) { printf("Use: SleepBarber "); exit(-1); } // Get the command line arguments and convert them // into integers. numCustomers = atoi(argv[1]); numChairs = atoi(argv[2]); RandSeed = atol(argv[3]); // Make sure the number of threads is less than the number of // customers we can support. if (numCustomers > MAX_CUSTOMERS) { printf("The maximum number of Customers is %d. ", MAX_CUSTOMERS); exit(-1); } printf(" SleepBarber.c "); printf("A solution to the sleeping barber problem using semaphores. "); // Initialize the random number generator with a new seed. srand48(RandSeed); // Initialize the numbers array. for (i=0; i

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.