The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chai

Question

The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and a barber room with one barber chair. If there are no customers to be served, the barber goes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but the chairs are occupied, then the customer leaves the shop. If the barber is busy 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. Write a C++ program using threads to coordinate the barber and the the customer.

Explanation / Answer

The entire solution is in 2 files.

File: BarberShopSimulation.h

#ifndef _BARBER_SHOP_SIMULATION_H
#define _BARBER_SHOP_SIMULATION_H

#define NUM_WAITING_CHAIRS 5

class Barber;
class Customer;
class BarberShop;

class Thread
{

HANDLE m_ThreadHandle;
bool m_Terminate;
DWORD m_ThreadID;
static DWORD _ThreadProc(void *);

public:

Thread();

virtual ~Thread();

void Start();

void Stop() {m_Terminate = true;}

bool KeepRunning() {return !m_Terminate;}

DWORD GetThreadID() const {return m_ThreadID;}

virtual DWORD run() = 0;

};

class Barber : public Thread

{
BarberShop & m_Shop;

public:
Barber( BarberShop & inShop);

~Barber();

DWORD run();

};

// Dummy class
class Customer
{
int m_ID;

public:

Customer(int inID) : m_ID(inID)
{    }

int GetID() const {return m_ID;}

Customer(const Customer & inCust): m_ID( inCust.m_ID )
{    }

};

std::ostream & operator << (std::ostream & os, const Customer & inCust)
{
os << inCust.GetID() ;
return os;
}

class BarberShop
{
std::auto_ptr m_Barber;

HANDLE m_BarberSleepEvt;

HANDLE m_Mutex;

int m_Head, m_Tail;

std::auto_ptr m_WaitingCustomers[ NUM_WAITING_CHAIRS];

inline incr(int& inValue)
{
++inValue;
if(inValue >= NUM_WAITING_CHAIRS )
inValue = 0;
}

public:

BarberShop();

~BarberShop() {}

void GetNextCusomer( std::auto_ptr & outCust);

void NeedsHaircut( std::auto_ptr& inCust);

};

#endif // _BARBER_SHOP_SIMULATION_H

File: BarberShopSimulation.cpp

#include <iostream>
#include <windows.h>
#include “BarberShopSimulation.h”

// For random sleep
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

Thread::Thread() : m_ThreadHandle(NULL), m_Terminate(false)
{
}

Thread::~Thread()
{
if( m_ThreadHandle != NULL )
{
::TerminateThread( m_ThreadHandle, 0 );
m_ThreadHandle = NULL;
}
}

DWORD Thread::_ThreadProc(void *ap)
{
Thread *r = (Thread *)ap;
return r->run();
}

void Thread::Start()
{

m_ThreadHandle = ::CreateThread(

NULL,      // default security attributes
0,          // default stack size
(LPTHREAD_START_ROUTINE) _ThreadProc,
this,       // no thread function arguments
0,          // default creation flags
&m_ThreadID); // receive thread identifier

if( m_ThreadHandle == NULL )

std::cout << “Could not create a thread! ”;

}

Barber:: Barber( BarberShop & inShop) : m_Shop(inShop)
{ }

Barber::~Barber() { }

DWORD Barber::run()

{
std::cout << “Barber::run…”;
while(1)
{
std::auto_ptr aCust;
m_Shop.GetNextCusomer( aCust );
if( !aCust.get() )
{
std::cout << “Barber Error: Customer is null ?? terminating…”;
return 1;
}

std::cout << “Barber is now cutting hair for customer ” << *aCust << “… ”;
::Sleep( 600 );
std::cout << ” finished ”;
}
}

BarberShop::BarberShop()
:m_BarberSleepEvt(NULL),
m_Mutex(NULL),

m_Head(0),
m_Tail(0)

{

m_BarberSleepEvt = ::CreateEvent( NULL, FALSE, FALSE, NULL);

m_Mutex = ::CreateMutex( NULL, FALSE, NULL );

std::auto_ptr aBarb( new Barber(*this) );

m_Barber = aBarb;

m_Barber->Start();

}

void BarberShop::GetNextCusomer( std::auto_ptr & outCust)
{
DWORD aResult;
do
{
aResult = ::WaitForSingleObject( m_Mutex, INFINITE );
if( aResult != WAIT_OBJECT_0 )
{
std::cout << “BarberShop::GetNextCusomer. Error while waiting for mutex! ”;
return;
}

// If the queue is empty, go to sleep. When a customer arrives, we will be woken up
if( m_Head == m_Tail)
{
::ReleaseMutex( m_Mutex );

aResult = ::WaitForSingleObject( m_BarberSleepEvt, INFINITE );

if( aResult != WAIT_OBJECT_0 )
{
std::cout << “BarberShop::GetNextCusomer. Error while waiting for event! ”;
return;
}
}
else
{
// There are some waiting customers. Get the one from the head
outCust = m_WaitingCustomers[m_Head];
incr( m_Head );
::ReleaseMutex( m_Mutex );
return;
}
}
while(1);
}

void BarberShop::NeedsHaircut( std::auto_ptr & inCust)
{
DWORD aResult;
int aNextPos;
bool aQueueWasEmpty;

// Get the mutex…
aResult = ::WaitForSingleObject( m_Mutex, INFINITE );
if( aResult != WAIT_OBJECT_0 )
{
std::cout << “BarberShop::GetNextCusomer. Error while waiting for mutex! ”;
return;
}
// Check if the queue was empty. If the queue was empty, then we need to signal the
// sleeping barber that there is a waiting customer
aQueueWasEmpty = m_Tail == m_Head;
aNextPos = m_Tail;
incr(aNextPos );
if( aNextPos == m_Head )
{
std::cout << “BarberShop::NeedsHaircut. Cant accept customer ” << *inCust << ” as Queue is full.. ”;
::ReleaseMutex( m_Mutex );
return;
}

// queue is not full. Add the customer to the tail
m_WaitingCustomers[ m_Tail ] = inCust;
m_Tail = aNextPos;
::ReleaseMutex( m_Mutex );
if( aQueueWasEmpty )
{
::SetEvent(m_BarberSleepEvt);
}

return;
}

int main(int, char **)
{

std::cout << “Hello, everyone. I am now running barber shop simulation ”;

BarberShop aShop;

for(int i=0; i < 1000; i++)
{
std::auto_ptr aCust( new Customer(i));

std::cout << “adding customer # ” << i << ” to shop ”;

aShop.NeedsHaircut( aCust );

::srand(time(NULL));

int aCount = ::rand()%100 + 10;

::Sleep( 700 ); //aCount );
}

::Sleep(10000);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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