Cigarette smoker’s problem – Python code

Q. Write python code for Cigarette smoker’s problem.

Ans: Check the below Python3 code.

import threading
import random
import time

def generateRandomItems():
    item1 = random.randint(1,100)
    item2 = random.randint(1,100)
    item1 %= 3
    item2 %= 3
    if (item1 == item2):
        item2 += 1
        item2 %= 3
    itemList = [item1, item2]
    return itemList

class cigaretteSmoker:
    def __init__(self, rounds):
        self.condMutex = threading.Condition()
        self.vendorSleep = threading.Semaphore(0)
        self.rounds = rounds
        self.ingredients = ['TOBACCO', 'PAPER', 'MATCHES']
        # No item is available on table.
        self.availableItems = [False, False, False]
        self.smokerThreads = []
        self.terminate = False
        # Create three smokers threads.
        self.smokerThreads.append(threading.Thread(target=self.smokerRoutine, \
                                  name='withTobacco', args=(1, 2)))
        self.smokerThreads.append(threading.Thread(target=self.smokerRoutine, \
                                  name='withPaper', args=(0, 2)))
        self.smokerThreads.append(threading.Thread(target=self.smokerRoutine, \
                                  name='withMatches', args=(0, 1)))
        for smokers in self.smokerThreads:
            smokers.start()
        # Create vendor thread.
        self.vendorThread = threading.Thread(target=self.vendorRoutine)
        self.vendorThread.start()

    def vendorRoutine(self):
        for i in range(self.rounds):
            # Generate two random items.
            randomItems = generateRandomItems()
            self.condMutex.acquire()
            print('Vendor produced: {0} and {1}'.\
                  format(self.ingredients[randomItems[0]], \
                         self.ingredients[randomItems[1]]))
            # Make items available on table.
            self.availableItems[randomItems[0]] = True
            self.availableItems[randomItems[1]] = True
            # Announce to all smokers that items are made available on table.
            self.condMutex.notify_all()
            self.condMutex.release()
            # Go to sleep till the selected smoker is done with smoking.
            self.vendorSleep.acquire()

    def smokerRoutine(self, neededItem1, neededItem2):
        myName = threading.currentThread().getName()
        while (True):
            self.condMutex.acquire()
            # Block till the needed items are on table.
            while (False == self.availableItems[neededItem1] or
                   False == self.availableItems[neededItem2]):
                self.condMutex.wait()
            self.condMutex.release()
            # Check if it was a terminate signal.
            if (True == self.terminate):
                break
            # Pickup the items from the table.
            self.availableItems[neededItem1] = False
            self.availableItems[neededItem2] = False
            # All ingredients are with you start smoking.
            print('{0} started smoking.'.format(myName))
            self.startUnhealthyActSmoking()
            print('{0} ended smoking.'.format(myName))
            # Smoking is done, wakeup the sleeping vendor.
            self.vendorSleep.release()

    def startUnhealthyActSmoking(self):
        randomTime = random.randint(1,100)
        randomTime %= 5
        time.sleep(randomTime+1)

    def waitForCompletion(self):
        # Wait for vendor thread to end.
        self.vendorThread.join()
        # Send terminate signal to smoker threads.
        self.condMutex.acquire()
        self.terminate = True
        self.availableItems = [True, True, True]
        self.condMutex.notify_all()
        self.condMutex.release()

if __name__== "__main__":
    obj = cigaretteSmoker(3)
    obj.waitForCompletion()

Advertisements

Ordered producer consumer – Python code

Q. Write Python code for ordered producer consumer problem.

Ans: This implementation is based on the thread safe buffer queue implementation. Python 3 code for ordered producer consumer is as below.

from buffer_queue import *
import threading
import random
import time

def itemsToProduce():
    return 10

def produceItem(bufferNode, cnt, threadName):
    bufferNode.setData(str(cnt).encode('utf-8'), len(str(cnt))+1)
    randomTime = random.randint(1,100)
    randomTime %= 5
    time.sleep(randomTime+1)
    print('Thread: {0} produced item: {1}'.format(threadName, str(cnt)))

def consumeItem(bufferNode):
    data = bufferNode.getData()
    print('Consumer thread consumed item: {0}'.format(data.decode()))

class orderedProducerConsumer:
    def __init__(self, length):
        # Initialize empty queue
        self.emptyQueue = bufferQueue(length)
        # Initialize filled dictionary
        self.filledDictionary = {}
        self.producerCount = 0
        self.mutex = threading.Lock()
        self.condMutex = threading.Condition()

    def producerRoutine(self):
        myName = threading.currentThread().getName()
        while (True):
            self.mutex.acquire()
            self.producerCount += 1
            if (itemsToProduce() < self.producerCount):
                self.mutex.release()
                return
            cnt = self.producerCount
            self.mutex.release()
            # Get an empty buffer
            bufferNode = self.emptyQueue.dequeueBuffer()
            # Produce data for sequence: cnt
            produceItem(bufferNode, cnt, myName)
            # Put produced buffer on filled dictionary
            self.condMutex.acquire()
            self.filledDictionary[cnt] = bufferNode
            # Inform consumer buffer for seq: cnt is ready
            self.condMutex.notify()
            self.condMutex.release()

    def consumerRoutine(self):
        for i in range(1, itemsToProduce()+1):
            self.condMutex.acquire()
            # Block till buffer of expected seq is not produced
            while (i not in self.filledDictionary):
                self.condMutex.wait()
            bufferNode = self.filledDictionary[i]
            del self.filledDictionary[i]
            self.condMutex.release()
            consumeItem(bufferNode)
            # Put back consumed buffer in empty queue
            self.emptyQueue.enqueueBuffer(bufferNode)

if __name__== "__main__":
    opcObject = orderedProducerConsumer(3)
    threads = []
    for i in range(5):
        t = threading.Thread(target=opcObject.producerRoutine, name='p_'+str(i))
        threads.append(t)

    t = threading.Thread(target=opcObject.consumerRoutine)
    threads.append(t)

    for thread in threads:
        thread.start()

    for thread in threads:
        thread.join()

Unordered producer consumer – Python code

Q. Write Python code for unordered producer consumer.

Ans: This implementation is based on the thread safe buffer queue implementation.

The Python3 code for unordered producer consumer:

from buffer_queue import *
import threading
import random
import time

def itemsToProduce():
    return 10

def produceItem(bufferNode, cnt, threadName):
    bufferNode.setData(str(cnt).encode('utf-8'), len(str(cnt))+1)
    randomTime = random.randint(1,100)
    randomTime %= 5
    time.sleep(randomTime+1)
    print('Thread: {0} produced item: {1}'.format(threadName, str(cnt)))

def consumeItem(bufferNode, threadName):
    data = bufferNode.getData()
    randomTime = random.randint(1,100)
    randomTime %= 5
    time.sleep(randomTime+1)
    print('Thread: {0} consumed item: {1}'.format(threadName, data.decode()))

class unorderedProducerConsumer:
    def __init__(self, length):
        self.emptyQueue = bufferQueue(length)
        self.filledQueue = bufferQueue(0)
        self.producerCount = 0
        self.consumerCount = 0
        self.mutex = threading.Lock()

    def producerRoutine(self):
        myName = threading.currentThread().getName()
        while (True):
            self.mutex.acquire()
            self.producerCount += 1
            if (itemsToProduce() < self.producerCount):
                self.mutex.release()
                return
            cnt = self.producerCount
            self.mutex.release()
            # Get the buffer from empty queue
            bufferNode = self.emptyQueue.dequeueBuffer()
            # Produce data
            produceItem(bufferNode, cnt, myName)
            # Add the buffer to filled queue
            self.filledQueue.enqueueBuffer(bufferNode)

    def consumerRoutine(self):
        myName = threading.currentThread().getName()
        while (True):
            self.mutex.acquire()
            self.consumerCount += 1
            if (itemsToProduce() < self.consumerCount):
                self.mutex.release()
                return
            self.mutex.release()
            # Get the buffer from filled queue
            bufferNode = self.filledQueue.dequeueBuffer()
            # Consume buffer
            consumeItem(bufferNode, myName)
            # Add the buffer to empty queue
            self.emptyQueue.enqueueBuffer(bufferNode)

if __name__== "__main__":
    upcObject = unorderedProducerConsumer(3)
    threads = []
    for i in range(5):
        t = threading.Thread(target=upcObject.producerRoutine, name='p_'+str(i))
        threads.append(t)

    for i in range(5):
        t = threading.Thread(target=upcObject.consumerRoutine, name='c_'+str(i))
        threads.append(t)

    for thread in threads:
        thread.start()

    for thread in threads:
        thread.join()

Thread safe Buffer Queue – Python code

Q. Implement Thread safe Buffer Queue in Python.

Ans: Check out below Python3 code.

Thread safe buffer queue using condition variable.

from ctypes import *
import threading
import random
import time

class buffer:
    def __init__(self, bufferLength=0, nextNode=None):
        if (0 == bufferLength):
            bufferLength = 1024
        self.data = bytes(bufferLength)
        self.next = nextNode
        self.bufferLength = bufferLength

    def getData(self):
        return self.data[:self.dataLength]

    def setData(self, data, dataLength):
        memmove(self.data, data, dataLength)
        self.dataLength = dataLength

    def getNext(self):
        return self.next

    def setNext(self, nextNode):
        self.next = nextNode

class bufferQueue:
    def __init__(self, length):
        self.head = None
        self.condMutex = threading.Condition()
        for i in range(length):
            newNode = buffer()
            newNode.setNext(self.head)
            self.head = newNode

    def enqueueBuffer(self, node):
        # Get the exclusive access of the buffer queue.
        self.condMutex.acquire()
        node.setNext(self.head)
        self.head = node
        # Notify any blocking thread that buffer is available.
        self.condMutex.notify()
        # Give up the exclusive access of the buffer queue.
        self.condMutex.release()

    def dequeueBuffer(self):
        # Get the exclusive access of the buffer queue.
        self.condMutex.acquire()
        # Block till buffer queue is empty.
        while (None == self.head):
            self.condMutex.wait()
        node = self.head
        self.head = node.getNext()
        # Give up the exclusive access of the buffer queue.
        self.condMutex.release()
        node.setNext(None)
        return node

def testBufferQueue(myQueue):
    myName = threading.currentThread().getName()
    for i in range(5):
        randomTime = random.randint(1,100)
        randomTime %= 5
        time.sleep(randomTime+1)
        print ('{0} requesting buffer from queue.'.format(myName))
        node = myQueue.dequeueBuffer()
        print ('{0} recieved buffer from queue.'.format(myName))
        time.sleep(randomTime+1)
        print ('{0} returning buffer to queue.'.format(myName))
        myQueue.enqueueBuffer(node)


if __name__== "__main__":
    myQueue = bufferQueue(1)
    t1 = threading.Thread(target=testBufferQueue, name='Thread1',args=(myQueue,))
    t2 = threading.Thread(target=testBufferQueue, name='Thread2',args=(myQueue,))

    t1.start()
    t2.start()
    t1.join()
    t2.join()

Thread safe buffer queue using semaphore.

class bufferQueue:
    def __init__(self, length):
        self.head = None
        self.semBuffer = threading.Semaphore(length)
        self.mutex = threading.Lock()
        for i in range(length):
            newNode = buffer()
            newNode.setNext(self.head)
            self.head = newNode

    def enqueueBuffer(self, node):
        # Get the exclusive access of the buffer queue.
        self.mutex.acquire()
        node.setNext(self.head)
        self.head = node
        # Give up the exclusive access of the buffer queue.
        self.mutex.release()
        # Release one buffer slot.
        self.semBuffer.release()

    def dequeueBuffer(self):
        # Consume one buffer slot.
        self.semBuffer.acquire()
        # Get the exclusive access of the buffer queue.
        self.mutex.acquire()
        node = self.head
        self.head = node.getNext()
        # Give up the exclusive access of the buffer queue.
        self.mutex.release()
        node.setNext(None)
        return node

Old Bridge – Python code

Q. Write the python code to solve the Old Bridge problem.

Ans: Check out below Python3 code.

import threading
import random
import time

class oldBridge (threading.Thread):
    s_lockBridge = None
    s_traffic = [None, None]
    s_mutex = [None, None]
    s_cars = [0, 0]
    s_entry = ['left', 'right']

    @staticmethod
    def initBridge():
        # Initialize bridge lock.
        oldBridge.s_lockBridge = threading.Semaphore(1)
        for i in range(2):
            # Max 3 cars in either direction.
            oldBridge.s_traffic[i] = threading.Semaphore(3)
            oldBridge.s_mutex[i] = threading.Lock()
            # Cars in either direction initially are zero.
            oldBridge.s_cars[i] = 0

    def __init__(self, car, direction):
        if (None == oldBridge.s_lockBridge):
            oldBridge.initBridge()
        threading.Thread.__init__(self)
        self.carNumber = car
        self.direction = direction

    def run(self):
        self.arriveBridge();
        self.drive();
        self.exitBridge();

    def arriveBridge(self):
        print ("Arriving car: {0} from direction: {1}".format(self.carNumber, oldBridge.s_entry[self.direction]));
        oldBridge.s_mutex[self.direction].acquire()
        if (0 == oldBridge.s_cars[self.direction]):
            # If you are the 1st car on your direction
            # Acquire exclusive lock on bridge.
            oldBridge.s_lockBridge.acquire()
        oldBridge.s_cars[self.direction] += 1
        oldBridge.s_mutex[self.direction].release()
        # Consume one slot for cars in same direction.
        oldBridge.s_traffic[self.direction].acquire()

    def drive(self):
        print ("Crossing car: {0} from direction: {1}".format(self.carNumber, oldBridge.s_entry[self.direction]));
        # Get random time to cross bridge.
        driveTime = random.randint(1,100)
        driveTime %= 3
        time.sleep(driveTime)

    def exitBridge(self):
        print ("Departing car: {0} from direction: {1}".format(self.carNumber, oldBridge.s_entry[self.direction]));
        oldBridge.s_mutex[self.direction].acquire()
        oldBridge.s_cars[self.direction] -= 1
        if (0 == oldBridge.s_cars[self.direction]):
            # If you are the last car on your direction
            # Give up exclusive access on bridge.
            oldBridge.s_lockBridge.release()
        oldBridge.s_mutex[self.direction].release()
        # Free up one slot for cars in same direction.
        oldBridge.s_traffic[self.direction].release()

if __name__== "__main__":
    threads = []
    for car in range(10):
        direction = random.randint(1,101)
        direction %= 2
        newcar = oldBridge(car, direction)
        threads.append(newcar)
        newcar.start()

    for thread in threads:
        thread.join()

Old Bridge

Q. An old bridge has only one lane and can only hold at most 3 cars at a time without risking collapse. Create a solution that controls traffic so that at any given time, there are at most 3 cars on the bridge, and all of them are going the same direction. A car calls ArriveBridge when it arrives at the bridge and wants to go in the specified direction (0 or 1); ArriveBridge should not return until the car is allowed to get on the bridge. A car calls ExitBridge when it gets off the bridge, potentially allowing other cars to get on. Don’t worry about starving cars trying to go in one direction; just make sure cars are always on the bridge when they can be.
Source: https://inst.eecs.berkeley.edu/~cs162/sp13/hand-outs/synch-problems.html

Ans: The car routine is as below:
1. If you’re the first car going in your direction, lock the bridge exclusively, blocking any traffic from the opposite side. If opposite side traffic is on sleep till end of opposite side traffic and then acquire exclusive lock on bridge.
2. Refrain from starting your journey if already there are three cars on the bridge at that time. Block till there is a room on the bridge to accommodate your car.
3. Drive on the bridge.
4. Exit the bridge. If there are any cars waiting to cross the bridge in same direction allow one of them to drive on the bridge. If you are the last car going in your direction give up the exclusive lock on the bridge and allow traffic from other side.

#define LEFT_SIDE 0
#define RIGHT_SIDE 1

class OldBridge {
public:
    OldBridge();
    ~OldBridge();
    void
    crossBridge(
        IN byte direction
        );

private:
    int m_cars[2];
    Semaphore *m_traffic[2];
    Mutex *m_mutex[2];
    Semaphore *m_lockBridge;

    void
    arriveBridge(
        IN byte direction
        );
    void
    exitBridge(
        IN byte direction
        );
    void
    drive();
};

OldBridge::OldBridge()
{
    for (int i=0; i<2; i++) {
        // Cars in either direction initially are zero.
        m_cars[i] = 0;
        // Max 3 cars in either direction.
        m_traffic[i] = new Semaphore(3);
        m_mutex[i] = new Mutex();
    }
    m_lockBridge = new Semaphore(1);
}

void
OldBridge::crossBridge(
    IN byte direction
    )
{
    arriveBridge(direction);
    drive();
    exitBridge(direction);
}

void
OldBridge::arriveBridge(
    IN byte direction
    )
{
    m_mutex[direction]->lock();
        if (0 == m_cars[direction]) {
            // If you are the 1st car on your direction
            // Acquire exclusive lock on bridge.
            m_lockBridge->wait();
        }
        m_cars[direction]++;
    m_mutex[direction]->unlock();

    // Consume one slot for cars in same direction.
    m_traffic[direction]->wait();
}

void
OldBridge::exitBridge(
    IN byte direction
    )
{
    m_mutex[direction]->lock();
        m_cars[direction]--;
        if (0 == m_cars[direction]) {
            // If you are the last car on your direction
            // Give up exclusive access on bridge.
            m_lockBridge->post();
        }
    m_mutex[direction]->unlock();

    // Free up one slot for cars in same direction.
    m_traffic[direction]->post();
}

Building H2O

Q. There are two kinds of threads, oxygen and hydrogen. In order to assemble these threads into water molecules, we have to create a barrier that makes each thread wait until a complete molecule is ready to proceed. As each thread passes the barrier, it should invoke bond. You must guarantee that all the threads from one molecule invoke bond before any of the threads from the next molecule do. We don’t have to worry about matching the threads up explicitly; that is, the threads do not necessarily know which other threads they are paired up with. Write the synchronization routine to simulate the behavior.

Ans:

The barrier routine:
1. Allow only one oxygen thread to participate.
2. Allow two hydrogen threads to participate.
3. Wait till three required threads are available.
4. Wakeup the three threads and inform them quorum for H2O molecule is ready and ask them to proceed with bond() creation.
5. Wait till the bond creation is complete.
6. Continue to create next H2O molecule. Goto step 1.

The Oxygen thread routine:
1. Wait till next H2O molecule creation is kicked off.
2. Wait till the quorum for H2O molecule is complete.
3. Kick off bond() creation for molecule H2O.
4. Inform the barrier that bond() creation has been kicked off.

The Hydrogen thread routine is similar to the Oxygen routine.

The pseudocode for the building H2O is like below:

class H2O {
public:
    H2O();
    ~H2O();
    void
    oxygenRoutine();
    void
    hydrogenRoutine();
    void
    barrierRoutine();

private:
    void
    createMolecule();

    Semaphore *m_oxygen;
    Semaphore *m_hydrogen;
    Semaphore *m_molecule;
    Semaphore *m_bond;
    ConditionMutex *m_barrier;
    bool m_quorumComplete;
};

H2O::H2O()
{
    m_oxygen = new Semaphore(0);
    m_hydrogen = new Semaphore(0);
    m_molecule = new Semaphore(0);
    m_bond = new Semaphore(0);
    m_barrier = new ConditionMutex();
    m_quorumComplete = false;
}

void
H2O::barrierRoutine()
{
    while (true) {
        // Quorum for next H2O is not complete.
        m_quorumComplete = false;
        // Allow one oxygen atom to participate.
        m_oxygen->post();
        // Allow two hydogen atoms to participate.
        m_hydrogen->post();
        m_hydrogen->post();
        // Wait till quorum for H2O is complete.
        // i.e. one oxygen atom &
        // two hydrogen atoms are ready.
        for (int i=0; i<3; i++) {
            m_molecule->wait();
        }
        // All three atoms are available.
        // Inform the atoms they can run bond().
        m_barrier->lock();
            m_quorumComplete = true;
            m_barrier->broadcast();
        m_barrier->unlock();
        // Wait till all atoms run the bond().
        for (int i=0; i<3; i++) {
            m_bond->wait();
        }
    }
}

void
H2O::oxygenRoutine()
{
    // Wait till previous H2O molecule is complete.
    m_oxygen->wait();
    // One oxygen atom is ready to participate.
    // Call the molecule creation process.
    createMolecule();
}

void
H2O::hydrogenRoutine()
{
    // Wait till previous H2O molecule is complete.
    m_hydrogen->wait();
    // One hydrogen atom is ready to participate.
    // Call the molecule creation process.
    createMolecule();
}

void
H2O::createMolecule()
{
    // Inform barrier out of three, one item is ready.
    m_barrier->post();
    // Wait till the quorum for H2O molecule is complete.
    m_barrier->lock();
        while (false == m_quorumComplete) {
            m_barrier->wait();
        }
    m_barrier->unlock();
    // Quorum for H2O is complete. Call the bond().
    bond();
    // Inform barrier bond has been invoked by you.
    m_bond->post();
}

Synchronisation for multithreaded programming

This is a small book explaining “Synchronisation for multithreaded programming”.

I learned theoretical aspects of synchronisation from the book: Unix Network Programming: Interprocess Communications – Vol.2: W. Richard Stevens
I got great hands on experience with synchronisation for multithreaded programming under K.K. George ‘s guidance.

This book covers following topics:

1. Synchronisation primitives: mutex, condition variable, semaphore

2. Thread safe Buffer Queue
    2.1 Python code – Thread safe Buffer Queue

3. Unordered producer consumer
    3.1 Python code – Unordered producer consumer

4. Ordered producer consumer
    4.1 Python code – Ordered producer consumer

5. Reader – Writer lock: Readers preference

6. Reader – Writer lock: Writers preference

7. Reader – Writer lock: Non starving

8. FIFO Mutex / Strict ordered Reader – Writer lock

9. Task Scheduler

10. Cigarette smoker’s problem
    10.1 Python code – Cigarette smoker’s problem

11. Sleeping barbers problem

12. Dinning philosopher’s problem

13. Building H2O

14. Old Bridge
    14.1 Python code – Old Bridge

Stay tuned to this page. I’ll keep on adding new pages as and when I come across interesting problems.

Dinning philosopher’s problem

Q. In 1965 Dijkstra formulated the Dinning philosopher’s problem.
Five philosophers are seated around a round table. Each philosopher has a plate of spaghetti. Philosopher needs two forks to eat it. Between each plate is fork. The life of philosopher consists of alternate periods of eating and thinking. When philosopher is hungry she tries to acquire left and right fork, one at a time, in either order. If successful in acquiring two forks, she eats for a while, then puts down the fork and continues to think. Program the routine for the dinning philosophers.

Ans: Andrew Tanenbaum’s Modern Operating System has a great solution for the dinning philosophers problem. The below code is using Tanenbaum’s solution.

The resource picking order can not solve the problem. Picking left fork first, then right fork to start eating will never work. If all the philosophers pick up their left fork no one will be able to pick up the their right fork. Adding random delay in the fork picking order will also not guarantee the deadlock avoidance.

The only solution that will work is a philosopher will not pickup any fork till both the left & right hand forks are available (i.e. neither neighbour is eating at the same time.)

The philosopher’s routine is:
0. Each philosopher will have state associated with her. The state is referred by the neighbours to find out what the philosopher is doing.
1. Spend time thinking. State of the philosopher is THINKING.
2. Philosopher becomes hungry, state of the philosopher is HUNGRY.
3. Check if you can pickup the left fork and right fork. (i.e. make sure left neighbour & right neighbour’s state is not EATING.) If either of fork is not available block till they become available.
4. When both forks are available change state to EATING, pickup the forks and start eating.
5. When your eating is done. Put down the left fork, check if your left neighbour is blocked for the fork you’re putting down, if she is wake her up to start eating. Then put down the right fork, check if your right neighbour is blocked for the fork you’re putting down, if she is wake her up to start eating.
6. Goto step 1.

#define N 5
#define LEFT(i) (i-1)%N
#define RIGHT(i) (i+1)%N
#define THINKING 0
#define HUNGRY 1
#define EATING 2

class DinningPhilosopher {
public:
    DinningPhilosopher();
    ~DinningPhilosopher();
    void
    philosopherRoutine(
        IN byte i
        );

private:
    byte m_state[N];
    Semaphore *m_sem[N];
    Mutex *m_mutex;

    void
    takeForks(
        IN byte i
        );

    void
    putForks(
        IN byte i
        );

    void
    testForkAvailability(
        IN byte i
        );
};

DinningPhilosopher::DinningPhilosopher()
{
    // All philosopher's are thinking initially.
    for (int i=0; i<N; i++) {
        m_state[i] = THINKING;
    }
    for (int i=0; i<N; i++) {
        m_sem[i] = new Semaphore(0);
    }
    m_mutex = new Mutex();
}

// N threads will be spawned, one for each philosopher.
// Argument i is philosopher id between (0,N)
void
DinningPhilosopher::philosopherRoutine(
    IN byte i
    )
{
    while(true) {
        continueThinking();
        takeForks(i);
        continueEating();
        putForks(i);
    }
}

void
DinningPhilosopher::takeForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're HUNGRY.
        m_state[i] = HUNGRY;
        // Test if left fork & right forks are available.
        // If available announce neighbours you're EATING.
        // so they don't pick up forks you already claimed.
        testForkAvailability(i);
    m_mutex->unlock();
    // If you are not yet EATING,
    // block till required forks are available.
    // Section A.
    m_sem[i]->wait();
}

void
DinningPhilosopher::testForkAvailability(
    IN byte i
    )
{
    // Note that m_mutex was locked before calling this function
    // Thread has exclusive access to execute this function.
    if (m_state[LEFT(i)] != EATING && // your left fork is available
        m_state[RIGHT(i)] != EATING && // your right fork is available
        m_state[i] == HUNGRY // and you want to start eating.
        ) {
        // Announce neighbours you started eating.
        m_state[i] = EATING;
        // Fork availability is passed.
        // Make sure you're not blocked at "Section A"
        // in function takeForks()
        m_sem[i]->post();
    }
}

void
DinningPhilosopher::putForks(
    IN byte i
    )
{
    m_mutex->lock();
        // Announce to neighbours you're done EATING.
        m_state[i] = THINKING;
        // Put down the left fork,
        // If your left neighbour is blocked at "Section A"
        // of function takeForks().
        // Allow him to unblock to start eating.
        testAvailability(LEFT(i));
        // Put down the right fork.
        testAvailability(RIGHT(i));
    m_mutex->unlock();
}

Sleeping barbers problem

Q. Sleeping barber is a classical synchornization problem.
The barber shop has one barber, one cutting chair and n chairs for waiting customers. If there are no customers barber fall asleep. When customer arrives he has to wakeup the sleeping barber. If additional customer arrives while barber is busy cutting hair, they sit down if there are empty chair or they leave the shop. The problem is to program the customer and barber routine. This standard problem has many solutions available.
Now lets make the problem bit hard by adding multiple barbers. There are m barbers and m cutting chairs in the shop. With all the above constraints design the customer and barber routine.

Ans: There are m barbers and n waiting chairs. Divide the waiting chairs into emptyChairs queue and occupiedChairs queue. There are m barbers, create m threads to run the barber routine. Every customer visiting the barber shop run the customer routine. Initially all the n waiting chairs are in emptyChairs queue.

Customer routine:
1. Check if emptyChairs queue is empty. If empty leave the barber shop. Else grab a chair from emptyChairs queue.
2. Add the grabbed chair into occupiedChairs queue and send the wakeup call to a barber.
3. Sleep till one barber is allotted to cut your hair.
4. After barber is allotted to you, leave the occupied chair and push the chair to emptyChairs queue.
5. Inform the allotted barber that you are ready for hair cut.
6. Wait till the hair cut is done.
7. Leave the barber shop.

Barber routine:
1. Sleep till there is a chair in the occupiedChairs queue.
2. Remove a chair from occupiedChairs queue. (i.e. select a customer for hair cut).
3. Inform the selected customer that you’re ready for the hair cut.
4. Sleep till the customer leaves his occupied chair and is ready for hair cut.
5. Cut the hair.
6. Inform the customer that hair cut is done.
7. Go to step 1.

#define WAITING_CHAIRS 16
#define NUMBER_OF_BARBERS 4

struct waitingChair {
    int allotedBarber;
    Semaphore *customerWait;

    waitingChair()
    {
        // No barber is alloted initially.
        allottedBarber = -1;
        customerWait = new Semaphore(0);
    }
};

struct cuttingChair {
    // customer's head to cut hair.
    void *customerHead;
    Semaphore *startHairCut;
    Semaphore *endHairCut;

    cuttingChair()
    {
        customerHead = NULL;
        startHairCut = new Semaphore(0);
        endHairCut = new Semaphore(0);
    }
};

class SleepingBarbers {
public:
    SleepingBarbers();
    ~SleepingBarbers();
    void
    customerRoutine();
    void
    barberRoutine(
        IN int barberId
        );

private:
    queue m_emptyChairs;
    queue m_occupiedChairs;
    cuttingChair m_baberChairs[NUMBER_OF_BARBERS];
    Mutex *m_emptyChairMutex;
    ConditionMutex *m_occupiedChairCondMutex;
};

SleepingBarbers::SleepingBarbers()
{
    for (int i=0; i<WAITING_CHAIRS; i++) {
        m_emptyChairs.push(new waitingChair());
    }
    m_emptyChairMutex = new Mutex();
    m_occupiedChairCondMutex = new ConditionMutex();
}

void
SleepingBarbers::customerRoutine()
{
    m_emptyChairMutex->lock();
        // Check if there is empty chair available.
        if (m_emptyChairs.empty()) {
            // Leave the shop, before leaving unlock the mutex.
            m_emptyChairMutex->unlock();
            return;
        }
        // Grab an empty chair.
        waitingChair *myChair = m_emptyChairs.front();
        m_emptyChairs.pop();
    m_emptyChairMutex->unlock();

    // Announce barbers that you have grabbed a chair.
    m_occupiedChairCondMutex->lock();
        m_occupiedChairs.push(myChair);
        // wakeup sleeping barber (if any).
        m_occupiedChairCondMutex->signal();
    m_occupiedChairCondMutex->unlock();

    // Go to sleep, till one barber is assigned to you.
    myChair->customerWait->wait();

    // A barber is ready to cut your hair.
    // Find out the barber assigned to you.
    int myBarber = myChair->allottedBarber;

    // Empty your occupied chair.
    m_emptyChairMutex->lock();
        myChair->allottedBarber = -1;
        m_emptyChairs.push(myChair);
    m_emptyChairMutex->unlock();

    // Make your head available for the barber.
    m_baberChairs[myBarber].customerHead = makeYourHeadAvilable();

    // Request the barber to start hair cut.
    m_baberChairs[myBarber].startHairCut->post();

    // Wait till the barber is done with your hair cut.
    m_baberChairs[myBarber].endHairCut->wait();
}

// m threads are initialized to run this routine.
void
SleepingBarbers::barberRoutine(
    IN int barberId
    )
{
    while (true) {
        m_occupiedChairCondMutex->lock();
            // Sleep till customer is available for haircut.
            while (m_occupiedChairs.empty()) {
                m_occupiedChairCondMutex->wait();
            }
            waitingChair *nextCustomer = m_occupiedChairs.front();
            m_occupiedChairs.pop();
        m_occupiedChairCondMutex->unlock();

        // Inform customer that you are ready to cut hair.
        nextCustomer->allottedBarber = barberId;
        nextCustomer->customerWait->post();

        // Wait till customer is ready for hair cut.
        m_baberChairs[barberId].startHairCut->wait();

        // Perform hair cut.
        performHarCut(m_baberChairs[barberId].customerHead);

        // Inform the customer hair cut is done.
        m_baberChairs[barberId].endHairCut->post();
    }
}