Sleeping Barber-Algorithmus (mit mehreren Friseuren)

Question

Die Sleeping Barber Problem ist ein klassisches Synchronisationsproblem, das viele von Ihnen vielleicht vertraut sind oder zumindest gehört haben.

Es basiert auf der Prämisse, dass ein Friseur (ein Thread) schläft, wenn es keine Kunden (jeder Kunde ist ein Thread) im Wartezimmer (die eine Semaphore ist). Wenn jemand da ist, schneidet er sich die Haare (symbolisiert etwas Verarbeitung) und der Kunde geht. Wenn dann niemand im Warteraum ist, geht der Barbier schlafen. Wenn ein anderer Kunde ankommt, muss er den Friseur aufwecken.

---

Ich habe eine Umsetzung dieser mit dem folgenden Grundidee

_{(obwohl der eigentliche Code ist in C, schrieb ich die folgende Pseudo-Code für die Syntax ohne viel Sorgfalt für Gründe des Problem understading, nur sem_wait und sem_post für glattere Lesung mit)}

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's 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 
     } 
    } 
} 

Allerdings, jetzt, dass ich dieses Problem mit mehreren Friseuren implementieren werde, blieb mein Kopf stecken. Ich ging auf Wikipedia, um zu sehen, ob ich etwas dagegen finden konnte, aber das einzige, was ich fand, da war dieser

Ein Mehrbett Barbiere Problem die zusätzliche Komplexität zu koordinieren mehrere Barbiere unter den wartenden Kunden hat.

und ich konnte dies von mir nicht herausfinden .

Welche Änderungen müsste ich in meinem Code vornehmen? Wo würde ich hier einen zusätzlichen Semaphor brauchen?

_{sem_wait() sperrt die Semaphore. sem_post() entriegelt es
Haftungsausschluss: Obwohl ich dies in programmers.stackexchange aswell gefragt haben, habe ich nicht eine gewünschte Antwort und meine Frage bleibt noch erreicht haben.}

Answer 1

Der Code, wie geschrieben, verwaltet eine beliebige Anzahl von Friseuren ohne zusätzliche Semaphoren. Starten Sie einfach einen Barbier {} - Thread für jeden Barbier im Shop. Das Problem, auf das in der Wikipedia-Anmerkung verwiesen wird, ist folgendes: Nur weil Sie M Friseure im Zustand "Friseur schneidet Haare" und M Kunden im Zustand "Kunde hat Haare schneiden" haben, gibt es keine Garantie, dass irgendein Friseur nicht ist 't versuchen, mehr als einen Kunden zu schneiden, oder dass ein Kunde nicht mehrere Friseure in seinen Haaren hat.

Mit anderen Worten, sobald die richtige Anzahl von Kunden in den Schneideraum zugelassen worden ist, wie passen die Barbiere und Kunden zusammen?Sie können nicht mehr sagen "Friseur schneidet Haare" und "Kunde hat Haare schneiden"; Sie müssen sagen "Friseur schneidet Haare von Kunde C" und "Kunde hat Haare schneiden von Friseur 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's PID to cut that custmer's hair 
// a customer uses a barber's 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's 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) 
} 

Answer 2

Dieser Code wird von mir mit leichten Modifikationen aus dem Algorithmus von Breveleri definiert geschrieben, die sehr effizient das Multiple Schlaf Barber Problem simuliert. Ich hatte es zu Simulationszwecken für meine Betriebssystemzuweisung geschrieben. Ich würde gerne einige Vorschläge von Ihrer Seite bekommen. Ich verwende "declarations.h", "SleepingBarber.c" und ein "Makefile" für eine bessere Codierungsstruktur.

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's 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 
} 

Make-Datei

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