Barber Problem Solution in C++

The barber shop simulation is a good problem to practice multi-threading concepts. Here is the problem, which we need to simulate. Barber shop consists of a waiting room with 'n' chairs, and a barber room with one barber chair

1. If there are no customers to be served the barber goes to sleep.
2. If a customer enters the barber shop and all the chairs are occupied then customer leaves shop.
3. If barber is busy but chairs are available then customer sits in one of the free chairs.
4. If barber is asleep the customer wakes up barber.

Here is one solution to the barber problem using Windows threading primitives. Essential classes that we need:

• Barber This class runs in a different thread. It calls BarberShop.GetNextCustomer to get an available customer.
• Customer
• BarberShop This is where all the business logic resides. The two main routines are GetNextCustomer, which picks up the next available customer from the queue or blocks on m_BarberSleepEvt if no customers. The NeedsHaircut routine adds a customer to the end of the queue of waiting customers if the queue has empty spaces. If not, it simply ignores the request. If the queue was empty before adding, then it means that the barber thread was waiting on the event and it releases the event after adding the customer.
• Thread This is a utility class that can be used to start/stop threads. Simply derive your class from this class after overriding the virtual run method and then call the Start routine.

The entire solution is in 2 files. I compiled the code using Borland's command line C++ compiler (free).

---

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

---

BarberShopSimulation.cpp

#include <iostream>
#include <windows.h>
#include "BarberShopSimulation.h"

// For random sleep
#include <stdio.h>javascript:void(0)
#include <stdlib.h>
#include <time.h>

// =================================================
//      Thread
// =================================================
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!\n";
}

// =================================================
//      Barber
// =================================================
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 << "...\n";
        ::Sleep( 600 );
        std::cout << " finished\n";
    }
}


// =================================================
//      BarberShop
// =================================================

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!\n";
            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!\n";
                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!\n";
        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..\n";
        ::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;
}



// ====================================================
//    Application
// ====================================================
int main(int, char **)
{
    std::cout << "Hello, everyone. I am now running barber shop simulation\n";

    BarberShop aShop;
    for(int i=0; i < 1000; i++)
    {
        std::auto_ptr aCust( new Customer(i));
        std::cout << "adding customer # " << i << " to shop\n";
        aShop.NeedsHaircut( aCust );
        ::srand(time(NULL));
        int aCount = ::rand()%100 + 10;
        ::Sleep( 700 ); //aCount );
    }
    ::Sleep(10000);
}