Monitor in Process Synchronization, Dining Philosophers problem, and solution using Monitors.

Semaphore and Monitor are used to allow 2 or more processes to access shared data in mutual exclusion. Both of them are used in different scenarios to achieve process synchronization. Besides being synchronization tools, they are quite different from each other. Semaphore is an integer variable in signaling mechanism. On the other hand, monitor is an abstract data type which allows only one process to be active at a time. In this paper, I will talk about monitors, one of the famous synchronization problem “Dining Philosophers”, and give solution to that problem using monitors in C.

Best way to describe monitors, is to concentrate on differences in structures with Semaphore. Consider the scenario where we have a shared data and 2 different process where both of them want to access data. Using semaphores, we will have an integer variable which works as a condition variable (whether it is binary semaphore or counting integer does not matter). Processes access semaphore and the process which meet the condition gets the access to the shared resource.

Now, let’s look at structure of Monitor. You can consider the monitor as a module or package which contains shared data, conditional variable, and procedures which operate on shared data. In case of semaphores, semaphore and shared data were separate units where they are in same module in monitors. Note that procedures in monitors and processes outside of the monitors are not the same. Processes outside of the monitor first access to the procedures of the monitor. Those procedures whether grant an access or not to the shared resources. For sure, only one process or thread can enter the monitor.

In this place, a question arises, “What happens to processes that are blocked?”. In the case of n processes trying to enter the monitor, only one(actually at most one) will get the access, remaining n-1 will be put on queue. If new processes are born, they will also be pushed to the queue.

In the example below, we have a monitor ‘account’, double ‘balance’ and procedure ‘withdraw’. Procedure takes amount as a parameter, subtract from balance and returns balance. Suppose we have 3 threads T1, T2, and T3. T1 enters the monitor and before it exits monitor, T2 and T3 try to enter monitor, get blocked and are put to queue. After T1 exits the monitor, thread in the head of the queue will enter to the monitor.

Conditional Variable provides synchronization inside the monitor. If a process wants to sleep inside the monitor or it allows a waiting process to continue, in that case conditional variables are used in monitors. Two operations can be performed on conditional variables: wait and signal.

wait() : Process performing wait operation on any condition variable are suspended. The suspended processes are placed in block queue of that condition variable.

signal() : When a process performs signal operation on condition variable, one of the blocked processes is given chance.

Monitors have the advantage of making parallel programming easier and less error prone than using techniques such as semaphore.

Now, it is time to describe our Dining Philosophers problem. For this purpose, I am referring to Wikipedia’s definition.

“Five silent philosophers sit at a round table with bowls of spaghetti. Forks are placed between each pair of adjacent philosophers. Each philosopher must alternately think and eat. However, a philosopher can only eat spaghetti when they have both left and right forks. Each fork can be held by only one philosopher and so a philosopher can use the fork only if it is not being used by another philosopher. After an individual philosopher finishes eating, they need to put down both forks so that the forks become available to others. A philosopher can only take the fork on their right or the one on their left as they become available and they cannot start eating before getting both forks.”

The problem is how to design a discipline of behavior (a concurrent algorithm) such that no philosopher will starve.

Let’s start with putting philosophers to the states. In total, we have 3 states:

THINKING — When philosopher doesn’t want to eat spaghetti (outside of the critical section).

HUNGRY — When philosopher wants to eat spaghetti (wants to enter the critical section).

EATING — When philosopher has got both the forks and eating spaghetti (has entered the critical section).

init() : Initially all 5 philosophers are in THINKING state.

PickUp() : If any thinking philosopher decides to eat, he moves to HUNGRY state. And calls TryToEat() function. If philosopher is not successful to eat, he calls wait() (move to blocked queue).

TryToEat() : In this function, a philosopher who wants to eat checks his neighbors whether forks are available or not., in other words, whether neighbor philosophers are in EATING state or not.

PutDown() : This is where EATING philosopher exits monitor and move to THINKING state. After leaving forks, it checks his both neighbors. If they are hungry and their one other neighbor isn’t in EATING state, he signal() them and offer to eat.

It is easy to show that this solution ensures that no two neighbors are eating simultaneously, and no deadlocks will occur. In this article, a synchronization tool “Monitor” is explained, and differentiated from another tool “Semaphore”. Furthermore, famous synchronization problem “Dining Philosophers” are described and solution to it using monitor is provided.