# 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

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.

• You should use counting semaphores instead of counter variables.
– user16034
Commented Aug 1, 2022 at 12:29

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.

• Thanks for your insight. Sorry for the flaw in my previous code. I have tried correcting it. Please can you have a look and rectify me once again. Actually OS book by Galvin, gives solutions to standard synchronization of problems and most of the exercises I have done till date on synchronization, were ones, which asked to say the nature of the synchronization issue (if at all) present in the synchronization code given in the question.But I do not have experience on writing synchronization constructs for unseen problems. And more necessarily how to think about writing them. The thought process Commented Mar 4, 2022 at 6:48
• I think the while(--blockedElephant) and its counterpart would result in an underflow. I suggest you try on paper the synchronisation process without trying to code it first as coding is just a means for implementation, the idea and problem solving is the real deal. You might wanna analyze how the solutions to readers-writers problem, the sleeping-barber problem and the producer-consumer problem work as this shows some degree of similarity to them. Commented Mar 4, 2022 at 11:55
• Underflow? I did not get the meaning in this context. Could you give an example of the "underflow" situation? [The other synchronisation problems which you mentioned are quite easy in the sense, that either there is a bound (sleeping barber or producer consumer) or there is only one writer allowed or may readers are allowed (reader writer problem).. this only one writer allowed makes the things easier...] I am unable to think as simply as the solution to these problems which you mentioned. Some way or the other I am unable to proceed... Commented Mar 4, 2022 at 16:22

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