Parallel Programming in C for the Transputer
© D. Thiébaut, 1995



7
DEADLOCKS

7-1 Introductory Examples

In this chapter we tackle deadlocks. How they occur, why they occur, and how we can detect, prevent and/or recover from them. Let's take a look right away at three examples that will give you a taste of the problems we want to avoid.

Example 1

Assume the following scenario: Two tasks, Compute and Relay work in a producer/consumer application:

 void Relay(Process *P, Channel *R2C, Channel *C2R)
{
	while (1) 
	 {  
		 x = ChanInInt(C2R);
		ChanOutInt(LINK0OUT, x);  
		 x =  ChanInInt(LINK0IN);
		ChanOutInt(R2C, x);  
	}
 }

 void Compute(Process *P, Channel   *R2C,   Channel *C2R)
{  
	int x,  y;
	 while (1) 
	 {   
		x = ChanInInt(R2C);   
		y = Calculate(x);
		 ChanOutInt(C2R, y);
	  }
}

Their protocol is simple: Relay receives a number from another node through LINK0, and passes it to Compute. Compute gets it, processes it with some function Calculate not shown here, and sends the result back to Relay, which passes it on to its neighbor. R2C and C2R are two soft channels linking Relay to Compute and conversely.

Not withstanding the fact that both loops are infinite and that the tasks will never end, what other serious problem can you detect in this apparently innocuous example?

Stop reading for a while and analyze the code. Try to imagine scenarios of the interleaved execution of the two tasks. (Remember that they are both running on the same transputer.)

The problem with this simple code is that none of these two tasks will ever be able to complete the first loop of the while statements. Both are locked on a channel, trying to receive from the other task, while none of them is sending anything. Their is no chance that either one of them can complete its ChanIn operation, and therefore both tasks are dead with respect to the computation.

Example 2

Assume that we have three tasks or nodes arranged in a ring, and that they store incoming packets in buffers of size 3. Assume furthermore that all three have their buffers filled with packets whose destination is two nodes away, as shown in Figure 7-1.


Figure 7- 1: 3 nodes with full buffers. Pkti indicates a packet with Node i as destination.

Each node cannot send any of its packets since the receive buffer on the other side of the channel linking it to its neighbor is full. You might suggest that if they all three decide to send a packet to the neighbor on the right and, at the same time, receive a packet from the left neighbor, then the nodes may remove themselves from that frozen state. The only problem with this solution is that it implies that the buffer would be emptied by a ChanOut operation at the same time a ChanIn would fill it. Remember that the transfer of information on hard links is done one byte at a time, therefore requiring the ChanOut to read Byte i of the message and send it before ChanIn would fill Byte i with data just received.. In other words, the ChanIn and ChanOut functions would have to be synchronized, a feature which the transputer does not support, and any attempt at trying to implement such operation--with two parallel tasks for example--would yield unpredictable result, and the very likely destruction of the messages!

Example 3

Let's take a look at a third and final example. Two tasks act as input and output managers for a queue. The Input Manager InManager receives packets from a channel with local name InC, and enqueues the packets in a buffer. The Output Manager OutManager waits for the queue to be not empty, dequeues a packet, and sends it out on the channel with local name OutC.

Their code is shown below. We will assume that the buffer is implemented as a circular list, and that semaphores are used to protect the use of the shared variables Front and Back which define the entry and exit points of the circular buffer. FrontSem is a semaphore guarding the use of Front, and BackSem that of Back. 

void InManager(Process *P, 
					Channel *InC)
{
	while (1)
	{
		/*---wait til there's room ---*/
		while (QueueFull)
			ProcReschedule();
		/*---lock use of Front ---*/

		SemP(FrontSem);

		/*---Receive pckt in buffer ---*/
		ChanIn(InC,
				&(Buffer[Front]),
				sizeof(Buffer[0]));
		Empty = 0;
		Front = (Front+1)%MAXBUFSIZE;
		/*---lock use of Back ---*/

		SemP(BackSem);

		if (Front==Back)
		{
			Front = 0;
			Back  = 0;
			QueueEmpty = 1;
		}
		/*---release Back and Front ---*/

		SemV(FrontSem);
		SemV(BackSem);

	}
}

void OutManager(Process *P, 
					Channel *OutC)
{
	while (1)
	{
		/*---wait til there's a pckt---*/
		while (QueueEmpty)
			ProcReschedule();
		/*---lock use of Back ---*/

		SemP(BackSem);

		/*---Send out pckt ---*/
		ChanOut(OutC, 
			&(Buffer[Back]),
			sizeof(Buffer[0]);
		Full = 0;
		Back = (Back+1)%MAXBUFSIZE;
		/*---lock use of Front ---*/

		SemP(FrontSem);

		if (Back==Front)
		{
			Front = 0;
			Back  = 0;
			QueueFull  = 1;
		}
		/*---release Back and Front ---*/

		SemV(FrontSem);
		SemV(BackSem);

	}
}

You probably will have guessed by now that we will have found a way to make this code misbehave. Can you find the conditions under which the above code will not operate properly and lock the two managers in an endless inactive state? Stop reading and imagine a scenario where to two tasks, for some reason, start one after the other. The buffer is neither full nor empty, and a packet is ready to be received on InC...

Let's see if you have guessed right. The problem with the two managers is that if, by any chance, their execution is interleaved so that the second one to start goes through its first semaphore lock (SemP) before the first task has reached its second lock, then there is no way that either task can finish.

To see why this is so, let's take a look at the simplified scenario below where we have listed in chronological order the different actions taken by the two managers, along with which of the two variables, Front or Back, is locked:

.
InManagerOutManager Comments Locked
variable
SemP(FrontSem  InManager just locked Front Front
   Task switch InManager goes idle and OutManager starts Front
 SemP(BackSem);OutManger just locked Back Front,, Back
 SemP(FrontSem)OutManager progresses and attempts to lock Front as well But Front is already locked and OutManager is forced to go inactive Front, Back
SemP(BackSem);   InManager awakens and continues by attempting to lock Back. But Back is already locked by OutManager, forcing InManager to go inactiveFront, Back
   Both tasks are inactive and will never be able to return to the active stateFront, Back

Table 7- 1: Scenario under which InManager and OutManager block.

These three examples illustrate important conditions that may occur while a parallel program is running, and that will result in deadlocks. This subject is important enough that we are dedicating it a whole chapter. In it we will investigate deadlocks, examples of circumstances when they occur, and we will look at methods for detecting and preventing them.

In same cases the answer will be simple, in other cases, sophisticated solutions may be required. In the case of the third example we just saw, following a simple rule stating that tasks should relinquish all locked variables when an attempt to lock an additional one fails will be sufficient to prevent deadlocks. For Example 2, however, a new communication structure and protocol for sending packets will be required. Let's get the easy cases out of the way first.

7-2 Deadlocks on Shared Resources

A general definition for deadlocks is given by Kröger [KROG91] and applies to shared-resources deadlocks as well as communication deadlocks:

Definition

A number of processing units which are directly or indirectly waiting for each other and whose waiting is endless regardless of any communication which might subsequently be initiated are said to be in a deadlock.

7-3 How likely is a deadlock?

Example 3 dealing with the Input and Output Managers is an example of code that has the propensity to deadlock on accessing shared-resources. This does not mean that the code will deadlock for certain, but that there is a non zero probability for it to do so.

Can we estimate this probability?

Looking at the scenario laid out in Table 7-1, we see that the problem occurs because a task switch takes place between the SemP(FrontSem) and SemP(BackSem) statements issued by InManager which started first. (We could have made the same arguments using the SemP(BackSem) and SemP(FrontSem) issued by OutManager.) This is one component of the probability we are trying to evaluate. The other component is the probability that OutManager becomes active before InManager resumes, and that it starts precisely after the release of Front and Back--at the end of its while loop--and just before the lock of Back. 

Pr[deadlock]   =  Pr[InManager swapped out between locks]                       
               * Pr[OutManager starts before first lock] * Pr[InManager starts first]

Running a simple program on a 20 MHz T805 where InManager is artificially fed single chars on the InC channel from a parallel task shows that this time can be as short as 11 s, or roughly 0.5% of the quantum size. Therefore InManager has a 0.5% chance to experience a quantum swap at the wrong time. A timing of the OutManager code reveals that approximately 2 s are necessary for it to go from the bottom of the while loop to the first SemP statement, while the whole loop--assuming that there is an artificial sink at the end of the soft channel--takes about 22 s to execute. This yield a 10.5% probability for OutManager to start at the wrong time. This does not take into account the possibility that the loop containing the ProcReschedule() may be executed several times, in which case we are missing the (negligible) overhead of that function's call, but not the several quanta of non-activity that result. These do not affect the probability, since we are interested in execution times while the task is active.

This is an interesting point. Since tasks are swapped in a round robin fashion, the fact that InManager and OutManager might be two out of three active tasks, or two out of 100, does not change their relationship in terms of execution in time. InManager will be run first, say, then later on OutManager, then InManager again, and so on. The fact that several quanta may be used between their respective instanciations is ineffectual, since we are interested only in the actual time they start and stop relative to the quantum swap.

So our approximation of the probability for a deadlock to occur when InManager and OutManager are used in their current form is the product:

Pr[deadlock] = 0.005 * 0.105 * 0.5 0.03%

The 0.5 term accounts for our assumption that both tasks are equally likely to start first. Hence there are 3 chances in 10,000 that the node that is running the InManager and OutManager tasks may experience a deadlock. The actual rate of deadlock may be quite different and will depend on the program using these queue managers, and on the timing of the tasks absorbing and feeding packets from/to the queue mangers. But, for lack of more precise information about the program and its components, we can estimate that every time our InManager is swapped out after doing some work, there is a 0.03 percent chance that deadlock will occur.

No wonder parallel programs will often run perfectly for a while and then suddenly crash for no apparent reason!





[Previous] [HOME] [NEXT]