The Deadlock Problem

A deadlock situation occurs when multiple tasks try to access the same resources in such a way that they prevent each other from running. The following is a simple example:

 

REXIS_MUTEX *mutex1, *mutex2;

 

void task1(unsigned arg0)

      {

      while (1)

            {

            REXIS_MutexLock(mutex1);

            REXIS_MutexLock(mutex2);

            … // processing

            REXIS_MutexUnlock(mutex2);

            REXIS_MutexUnlock(mutex1);

            }

      }

 

void task2(unsigned arg0)

      {

      while (1)

            {

            REXIS_MutexLock(mutex2);

            REXIS_MutexLock(mutex1);

            … // processing

            REXIS_MutexUnlock(mutex1);

            REXIS_MutexUnlock(mutex2);

            }          

      }

 

Consider a race condition where task1 obtains the lock on mutex1 but before it can lock mutex2, scheduling occurs so that task2 runs and obtains the lock on mutex2. If this happens, then neither task can continue to run, as each is waiting for a resource locked by the other task. This is known as deadlock.

 

Deadlocks can happen more unexpectedly. To explain, deadlock can best be viewed as a dependency graph. That is, if task A needs a resource that is currently held by another task task B, then it is said that task A depends on task B.

 

A deadlock is formed if the dependencies form a loop. For example, in the previous code sample, under the race condition mentioned, task1 depends on task2, but so does task2 depend on task1. Therefore, a loop is formed and neither task can run.

 

Using the graph terminology can easily show more complicated forms of deadlock. For example, if task A depends on task B and task B depends on task C, and so on, and then eventually a task depends back onto task A. The dependencies form a loop and creates a deadlock, and none of the tasks can run.

 

There is no general solution available to prevent deadlocks in the kernel. The firmware writer must design the system carefully so that deadlocks will not happen.