All geek questions in one place

Sleeping Hairdresser Algorithm (with multiple hairdressers)

The sleeping hairdresser problem is a classic synchronization problem that many of you may be familiar with, or at least heard about.

This is based on the premise that the hairdresser (thread) sleeps when there are no clients (each client is a thread) in the waiting room (which is a semaphore). If there is someone, he cuts the hair (symbolizing some processing), and the customer leaves. If then there is nobody in the waiting room, the hairdresser will fall asleep. When another client arrives, he must wake up with a hairdresser.

I made an implementation of this using the following basic idea

(although the actual code is in C , I wrote the following pseudocode without much attention to the syntax for understanding the problem, using only sem_wait and sem_post 1 for smoother reading)

 Semaphore Customers = 0; Semaphore Barber = 0; Mutex accessSeats = 1; int NumberOfFreeSeats = N; Barber { while(1) { sem_wait(Customers); // waits for a customer (sleeps) sem_wait(accessSeats); // mutex to protect the number of available seats NumberOfFreeSeats++; // a chair gets free sem_post(Barber); // bring customer for haircut sem_post(accessSeats); // release the mutex on the chair // barber is cutting hair } } Customer { while(1) { sem_wait(accessSeats); // protects seats so only 1 thread tries to sit in a chair if that the case if(NumberOfFreeSeats > 0) { NumberOfFreeSeats--; // sitting down sem_post(Customers); // notify the barber sem_post(accessSeats); // release the lock sem_wait(Barber); // wait in the waiting room if barber is busy // customer is having hair cut } else { sem_post(accessSeats); // release the lock // customer leaves } } }

However, now, when I will implement this problem with several hairdressers, my head is stuck. I went to Wikipedia to find out if I can find something, but the only thing I found there is

The problem of multiple sleeping barriers has the added difficulty of coordinating several hairdressers among expecting clients.

and I could not figure it out on my own 2 .

What changes do I need to make in my code? Where do I need an extra semaphore here?

1 sem_wait() blocks the semaphore. sem_post() opens it
2 Disclaimer: although I asked this at programers.stackexchange , I did not reach the desired answer, and my question still persists.

+6
source share
2 answers

The written code will manage any number of hairdressers without any additional semaphores. Just run Barber {} for every hairdresser in the store.

The problem mentioned in the Wikipedia comment is this: just because you have M hairdressers in the “hairdresser cuts hair” state and M clients in the “client has a haircut” state, there is no guarantee that some hairdresser is not " t try to fix more than one client, or that some client does not have several hairdressing salons in his hair.

In other words, once the correct number of clients was allowed to enter the cutting room, how did hairdressers and clients mate? You can no longer say that “the hairdresser cuts the hair” and “the client has a haircut”; you must say that "the hairdresser cuts the hair of client C" and "the client has a haircut from hairdresser B".

 // Assumptions about the meaning of 'haircut': // each thread has a unique PID // each thread can get its own PID via system.info.PID // a barber uses a customer PID to cut that custmer hair // a customer uses a barber PID to get his hair cut by that barber // Assumptions about the operating environment: // a semaphore releases threads in the order that they were queued Semaphore Customers = 0; Semaphore Barbers = 0; Mutex AccessSeats = 1; int NumberOfFreeSeats = N; int SeatPocket[N]; // (or 'PID SeatPocket[N];' if PID is a data type) int SitHereNext = 0; int ServeMeNext = 0; // main program must start a copy of this thread for each barber in the shop Barber { int mynext, C; while(1) { sem_wait(Barbers); // join queue of sleeping barbers sem_wait(AccessSeats); // mutex to protect seat changes ServeMeNext = (ServeMeNext++) mod N; // select next customer mynext = ServeMeNext; C = SeatPocket[mynext]; // get selected customer PID SeatPocket[mynext] = system.info.PID; // leave own PID for customer sem_post(AccessSeats); // release the seat change mutex sem_post(Customers); // wake up selected customer // // barber is cutting hair of customer 'C' // } } // main program must start a copy of this thread at random intervals // to represent the arrival of a continual stream of customers Customer { int myseat, B; sem_wait(AccessSeats); // mutex to protect seat changes if(NumberOfFreeSeats > 0) { NumberOfFreeSeats--; // sit down in one of the seats SitHereNext = (SitHereNext++) mod N; myseat = SitHereNext; SeatPocket[myseat] = system.info.PID; sem_post(AccessSeats); // release the seat change mutex sem_post(Barbers); // wake up one barber sem_wait(Customers); // join queue of sleeping customers sem_wait(AccessSeats); // mutex to protect seat changes B = SeatPocket[myseat]; // barber replaced my PID with his own NumberOfFreeSeats++; // stand up sem_post(AccessSeats); // release the seat change mutex // // customer is having hair cut by barber 'B' // } else { sem_post(AccessSeats); // release the seat change mutex // customer leaves without haircut } system.thread.exit; // (or signal main program to kill this thread) }
+2
source

This code was written by me with minor changes in the algorithm defined by Breveleri, which quite effectively imitates the problem of Multiple Sleeping Hairdresser . I wrote this for simulation purposes for my OS Destination. I would like to receive suggestions from you. I use "declarations.h", "SleepingBarber.c" and "makefile" for a better coding structure.

declaration.h

 #include <unistd.h> //Provides API for POSIX(or UNIX) OS for system calls #include <stdio.h> //Standard I/O Routines #include <stdlib.h> //For exit() and rand() #include <pthread.h> //Threading APIs #include <semaphore.h> //Semaphore APIs #define MAX_CHAIRS 10 //No. of chairs in waiting room #define CUT_TIME 1 //Hair Cutting Time 1 second #define NUM_BARB 2 //No. of barbers #define MAX_CUST 30 //Maximum no. of customers for simulation sem_t customers; //Semaphore sem_t barbers; //Semaphore sem_t mutex; //Semaphore for providing mutially exclusive access int numberOfFreeSeats = MAX_CHAIRS; //Counter for Vacant seats in waiting room int seatPocket[MAX_CHAIRS]; //To exchange pid between customer and barber int sitHereNext = 0; //Index for next legitimate seat int serveMeNext = 0; //Index to choose a candidate for cutting hair static int count = 0; //Counter of No. of customers void barberThread(void *tmp); //Thread Function void customerThread(void *tmp); //Thread Function void wait(); //Randomized delay function

SleepingBarber.c

 #include "declarations.h" int main() { pthread_t barber[NUM_BARB],customer[MAX_CUST]; //Thread declaration int i,status=0; /*Semaphore initialization*/ sem_init(&customers,0,0); sem_init(&barbers,0,0); sem_init(&mutex,0,1); /*Barber thread initialization*/ printf("!!Barber Shop Opens!!\n"); for(i=0;i<NUM_BARB;i++) //Creation of 2 Barber Threads { status=pthread_create(&barber[i],NULL,(void *)barberThread,(void*)&i); sleep(1); if(status!=0) perror("No Barber Present... Sorry!!\n"); } /*Customer thread initialization*/ for(i=0;i<MAX_CUST;i++) //Creation of Customer Threads { status=pthread_create(&customer[i],NULL,(void *)customerThread,(void*)&i); wait(); //Create customers in random interval if(status!=0) perror("No Customers Yet!!!\n"); } for(i=0;i<MAX_CUST;i++) //Waiting till all customers are dealt with pthread_join(customer[i],NULL); printf("!!Barber Shop Closes!!\n"); exit(EXIT_SUCCESS); //Exit abandoning infinite loop of barber thread } void customerThread(void *tmp) /*Customer Process*/ { int mySeat, B; sem_wait(&mutex); //Lock mutex to protect seat changes count++; //Arrival of customer printf("Customer-%d[Id:%d] Entered Shop. ",count,pthread_self()); if(numberOfFreeSeats > 0) { --numberOfFreeSeats; //Sit on chairs on waiting room printf("Customer-%d Sits In Waiting Room.\n",count); sitHereNext = (++sitHereNext) % MAX_CHAIRS; //Choose a vacant chair to sit mySeat = sitHereNext; seatPocket[mySeat] = count; sem_post(&mutex); //Release the seat change mutex sem_post(&barbers); //Wake up one barber sem_wait(&customers); //Join queue of sleeping customers sem_wait(&mutex); //Lock mutex to protect seat changes B = seatPocket[mySeat]; //Barber replaces customer PID with his own PID numberOfFreeSeats++; //Stand Up and Go to Barber Room sem_post(&mutex); //Release the seat change mutex /*Customer is having hair cut by barber 'B'*/ } else { sem_post(&mutex); //Release the mutex and customer leaves without haircut printf("Customer-%d Finds No Seat & Leaves.\n",count); } pthread_exit(0); } void barberThread(void *tmp) /*Barber Process*/ { int index = *(int *)(tmp); int myNext, C; printf("Barber-%d[Id:%d] Joins Shop. ",index,pthread_self()); while(1) /*Infinite loop*/ { printf("Barber-%d Gone To Sleep.\n",index); sem_wait(&barbers); //Join queue of sleeping barbers sem_wait(&mutex); //Lock mutex to protect seat changes serveMeNext = (++serveMeNext) % MAX_CHAIRS; //Select next customer myNext = serveMeNext; C = seatPocket[myNext]; //Get selected customer PID seatPocket[myNext] = pthread_self(); //Leave own PID for customer sem_post(&mutex); sem_post(&customers); //Call selected customer /*Barber is cutting hair of customer 'C'*/ printf("Barber-%d Wakes Up & Is Cutting Hair Of Customer-%d.\n",index,C); sleep(CUT_TIME); printf("Barber-%d Finishes. ",index); } } void wait() /*Generates random number between 50000 to 250000*/ { int x = rand() % (250000 - 50000 + 1) + 50000; srand(time(NULL)); usleep(x); //usleep halts execution in specified miliseconds }

Makefile

 all: SleepingBarber SleepingBarber: SleepingBarber.o gcc -pthread -o SleepingBarber SleepingBarber.o SleepingBarber.o: SleepingBarber.c declarations.h gcc -c SleepingBarber.c clean: rm -f *.o SleepingBarber
+2
source

Source: https://habr.com/ru/post/957074/

More articles:


All Articles