Sleeping barber
A. First Edition
I am practicing with multi-thread.
A barber's shop have n seat for customers to be seated while waiting. One barber's seat for customer to be seated
while cutting hair and also for barber to sleep in while no customer is waiting. Customer comes and first try to
sit if there is free seat, otherwise just leaves. If barber is sleeping, customer must wake up barber. If barber
is cutting hair for some customer, the seated customers just wait in seats.
กก
I use 10 threads to represent 10 customers while there are only 5 seats in barber's shop for waiting. And for
each customer, there is one state variable associated with him, same for barber. There are two "mutex", one for
waiting seat, one for cutting hair which are all critical area. Customer comes and enter mutex of "seat" to see
if there are empty seat to sit in. If yes, he sits and begin waiting in queue of barber's turn for hair-cutting
by entering mutex of "barber". There is only one small trivial problem for the global variable "seatCount" which
is used to represent for how many waiting customers there are. It can be incremented when customer comes. And it
also can be decremented when barber finished servicing a customer. Incrementing is no problem because it is inside
of "seatMutex", however, barber doesn't enter this mutex. So, there may be some short intervals while "seatCount"
is not accurate. But does anybody really refer to this data? I don't see it at least in this simple case. So, I
just leave it there.
E.Further improvement
One of big problem is synchronization with "std cout". You see, my thread is messed up when they use "cout" for
display. I guess the reason is that I/O is extremely slow and context switch between threads is not synchronized
with output. So, I have to store all result in an array called "log". And display it only after threads terminate.
F.File listing
1. main.cpp (main)
file name: main.h
#include <windows.h>
#include <iostream>
using namespace std;
const int TotalCustNum=10;
const int SeatNum=5;
int custCount=0;
int seatCount=0;
int barIndex=TotalCustNum;
int custIndex[TotalCustNum];
int log[500];
int logCount=0;
HANDLE barbarMutex, seatMutex, display;
HANDLE customers[TotalCustNum];
//HANDLE barbar;
enum State
{Sleeping, Serving, Waiting, Leaving, Cutting};
char* stateStr[5]={"Sleeping", "Serving", "Waiting", "Leaving", "Cutting"};
State states[TotalCustNum+1];
int daemon[TotalCustNum];
int servedCount=0;
void interrupt(int i);
void initialize();
DWORD WINAPI run(void* param);
void beServed(int i);
int main()
{
initialize();
while (servedCount<20)
{
WaitForSingleObject(display, INFINITE);
for (int i=0; i<TotalCustNum; i++)
{
log[logCount++]=states[i];
}
ReleaseMutex(display);
Sleep(0);
}
for (int i=0; i<TotalCustNum; i++)
{
CloseHandle(customers[i]);
}
i=0;
while (i<logCount)
{
for (int j=0; j<TotalCustNum; j++)
{
cout<<"customer "<<j<<" is "<<stateStr[log[i++]]<<"\n";
}
cout<<"round of "<<i/TotalCustNum<<endl;
}
return 0;
}
void initialize()
{
barbarMutex=CreateMutex(NULL, false, NULL);
seatMutex=CreateMutex(NULL, false, NULL);
display=CreateMutex(NULL, false, NULL);
// barbar=CreateThread(NULL, 0, run, &barIndex, 0, NULL);
states[barIndex]=Sleeping;
for (int i=0; i<TotalCustNum; i++)
{
custIndex[i]=i;
daemon[i]= rand()%TotalCustNum;
states[i]=Leaving;
customers[i]=CreateThread(NULL, 0, run, custIndex+i, 0, NULL);
}
}
void beServed(int i)
{
WaitForSingleObject(barbarMutex, INFINITE);
if (states[barIndex]==Sleeping)
{
WaitForSingleObject(display, INFINITE);
states[barIndex]=Serving;
ReleaseMutex(display);
}
states[i]=Cutting;
Sleep(0);
//here is a little small problem, since
//seatCount might be changed at same time by newly-arrived customer,
//but it does little harm, since, barbar's state is not used by anyone
//and will be corrected when customer having hair-cut.
seatCount--;
if (seatCount==0)
{
WaitForSingleObject(display, INFINITE);
states[barIndex]=Sleeping;
ReleaseMutex(display);
}
WaitForSingleObject(display, INFINITE);
states[i]=Leaving;
ReleaseMutex(display);
servedCount++;
ReleaseMutex(barbarMutex);
}
void interrupt(int i)
{
if (daemon[i]<TotalCustNum/2)
{
Sleep(0);
}
}
DWORD WINAPI run(void* param)
{
while (servedCount<20)
{
interrupt(*((int*)param));
if (WaitForSingleObject(seatMutex, 0)==WAIT_OBJECT_0)
{
if (seatCount<SeatNum)
{
seatCount++;
WaitForSingleObject(display, INFINITE);
states[*((int*)param)]=Waiting;
ReleaseMutex(display);
ReleaseMutex(seatMutex);
beServed(*((int*)param));
}
else
{
//still Leaving
ReleaseMutex(seatMutex);
}
}
}
return servedCount;
}
The input is something like following:
Here is the result:
customer 0 is Leaving
customer 1 is Leaving
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Leaving
customer 5 is Leaving
customer 6 is Leaving
customer 7 is Leaving
customer 8 is Leaving
customer 9 is Leaving
round of 1
customer 0 is Leaving
customer 1 is Cutting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 2
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Cutting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 3
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Cutting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 4
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Cutting
customer 8 is Leaving
customer 9 is Leaving
round of 5
customer 0 is Cutting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 6
customer 0 is Leaving
customer 1 is Cutting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 7
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Cutting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 8
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Cutting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 9
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Cutting
customer 8 is Leaving
customer 9 is Leaving
round of 10
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Cutting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 11
customer 0 is Waiting
customer 1 is Cutting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 12
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Cutting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 13
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Cutting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 14
customer 0 is Waiting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Cutting
customer 8 is Leaving
customer 9 is Leaving
round of 15
customer 0 is Cutting
customer 1 is Waiting
customer 2 is Leaving
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 16
customer 0 is Leaving
customer 1 is Cutting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 17
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Cutting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 18
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Cutting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 19
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Waiting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Cutting
customer 8 is Leaving
customer 9 is Leaving
round of 20
customer 0 is Leaving
customer 1 is Waiting
customer 2 is Cutting
customer 3 is Leaving
customer 4 is Waiting
customer 5 is Leaving
customer 6 is Waiting
customer 7 is Waiting
customer 8 is Leaving
customer 9 is Leaving
round of 21
Press any key to continue