Tigers and elephants can't drink water from a pond simultaneously, while more than one tiger or more than one elephants can drink water simultaneously

Question

Below is a question on synchronization mechanism which was asked in an interview in Indian Statistical Institute, M.Tech CS. I got hold of it from here.

There is a forest where there are tigers and elephants. There are two processes named tiger and elephant. Design a concurrency processing using semaphore, such that tigers and elephants cannot drink water from a pond simultaneously, whereas more than one tiger or more than one elephants can drink water simultaneously.

$\tag {ISI, M. Tech CS}$

Though some of my peers have tried to answer it, but I felt like trying it on my own, but after trying out on my own, I do not know whether is it flawed of not. It seems correct to me apparently, but since I am a self learner, I do not know anyone who could possibly look into my solution and give me hints to rectify the flaw in the solution (if it exists). So I thought of asking it here.

Below is my approach: [This is my second approach, my previous version can be found in the edited section]

---

Let Tiger and Elephant be integer variables initialized to 0 which stores the number of tigers and elephants drinking water respectively.

Also, T and E be two semaphores each initialized to 0, to block a tiger process or elephant process respectively on these semaphores.

Let blockedTiger and blockedElephant be integer variables to store the number of $\text{Tiger}$ and $\text{Elephant}$ processes blocked on T and E respectively.

Also let us have a binary semaphore mutex initialized to 1 which is used for mutual exclusion and to implement the synchronization.

So in terms of code we have:

//shared variables
int Tiger,Elephant;
Tiger=Elephant=0;
Semaphore T,E;
T=E=0;
int blockedTiger,blockedElephant;
blockedTiger=blockedElephant=0;
BinSemaphore mutex ;
mutex=1;

---

Next let me show the code for the $i$th $\text{Tiger}$ process.

/*i th Tiger Process*/

/**********************ENTRY SECTION***************/
P(mutex);
while(Elephant!=0)
{
    V(mutex);
    blockedTiger++;
    P(T);   //to block this Tiger process on semaphore T
    P(mutex);
}

while(--blockedTiger)
    V(T);
Tiger++;
V(mutex);

/*******************END OF ENTRY SECTION***************/

DrinkWater();

/*******************EXIT SECTION**************/
P(mutex);
Tiger--;
if(Tiger==0)
   V(E);
V(mutex);

/********************END OF EXIT SECTION****************/

---

Next let me show the code for the $j$th $\text{Elephant}$ process.

/*j th Elephant Process*/

/**********************ENTRY SECTION***************/
P(mutex);
while(Tiger!=0)
{
    V(mutex);
    blockedElephant++;
    P(E);   //to block this Elephant process on semaphore E
    P(mutex);
}

while(--blockedElephant)
    V(E);
Elephant++;
V(mutex);

/*******************END OF ENTRY SECTION***************/

DrinkWater();

/*******************EXIT SECTION**************/
P(mutex);
Elephant--;
if(Elephant==0)
   V(T);
V(mutex);

/********************END OF EXIT SECTION****************/

---

Please can anyone give me feedback as to whether it is correct or not. And if not correct, please give me hints so that I can rectify it.

Answer 1

Your approach is allowing the tiger and elephant to simultaneously enter the pond. Consider the case when there are no tigers or elephants and both of them approach the pond. The control of your program is reaching Drinkwater() for both the processes which shouldn't be allowed as per the problem statement.

Hint: Try doing the same with fewer mutexes/semaphores. Right now the way you have approached it doesn't really take advantage of the nature of a mutex as both processes are operating on different copies of it. And while constructing your solution for such problems, try pre-empting the process and switch back and forth between them to find if the violate mutual exclusion or end up in a deadlock.

Answer 2

Starvation Free Solution assuming FIFO Waiting Queue

wait(mutex);
wait(Tiger_Mutex);
tiger_count++;
if(tiger_count==1);
    wait(pond)
signal(mutex);
signal(Tiger_Mutex);
drink_water();
wait(Tiger_Mutex);
tiger_count--;
if(tiger_count==0)
    signal(pond)
signal(Tiger_Mutex);

All mutex initialized to 1

Similar code for Elephant