Courses/Computer Science/CPSC 457.F2013/Lecture Notes/Deadlock

Deadlock

This is such a fearsome topic that it deserves its own session. It has its own Chapter in MOS. It is a meta-problem: a problem that emerges out of our quest to achieve safe concurrent communication.

We will explore the issue of deadlock arising from having mechanisms for coordinating access. We will understand the conditions necessary for deadlock and considering some strategies for avoiding or fixing it.

Agenda

• Resource Graphs

• Deadlock Definition

• Conditions for Deadlock

• Strategies to Avoid Deadlock

• Strategies for Recovering from Deadlock

• Banker's Algorithm

• Livelock
  • See (MOS: 6.7.3)
  • spin-wait: no progress, but no blocking, either.
  • (Big Picture Issue / Tradeoff): convenience vs. absolute correctness

Notes

Here is a link to the slide deck for today on Deadlocks

Below are some code snippets from the program we wrote today in class tie.c

The finished product, of course, is slightly less interesting than the process undertaken to generate the code.

We need some boilerplate header files, a couple of thread variables, a couple of mutexes, and a couple of shared resources.

#include <pthread.h>
#include <stdio.h>
pthread_t job1;
pthread_t job2;
pthread_mutex_t box1_lock;
pthread_mutex_t box2_lock;
int box1 = 200;
int box2 = 100;

The main function kicks off the whole process by creating a couple of threads. It also invokes pthread_join so that the main process thread waits for its children to finish.

/**                                              
 * create two threads, ask them to modify a set of shared
 * resources
 */
int main(int argc,
         char* argv[])
{
  pthread_mutex_init(&box1_lock, NULL);
  pthread_mutex_init(&box2_lock, NULL);
  pthread_create(&job1,
                 NULL,
                 do_job,
                 NULL);
  pthread_create(&job2,
                 NULL,
                 do_some_job,
                 NULL);
  pthread_join(job1, NULL);
  pthread_join(job2, NULL);
  return 0;
}

Our first thread, job1 runs this routine after it is created via pthread_create:

void*
do_job(void* arg)
{
  int i = 0;
  pthread_mutex_lock(&box1_lock);
  for(i=0;i<2000000000;i++)
    {;}
  pthread_mutex_lock(&box2_lock);
  box2--;
  box1 = 300;
  pthread_mutex_unlock(&box1_lock);
  pthread_mutex_unlock(&box2_lock);
  fprintf(stdout,
          "do_job(): box1: %d\nbox2: %d\n",
          box1,
          box2);
  return NULL;
}

Our second thread, job2 runs this routine:

void*
do_some_job(void* arg)
{
  pthread_mutex_lock(&box2_lock);
  pthread_mutex_lock(&box1_lock);
  box1 = 400;
  box2++;
  pthread_mutex_unlock(&box2_lock);
  pthread_mutex_unlock(&box1_lock);
  fprintf(stdout,
          "do_some_job(): box1: %d\nbox2: %d\n",
          box1,
          box2);
  return NULL;
}

Note how the four deadlock conditions hold here: mutual exclusion, hold and wait, circular waiting (see order of obtaining mutexes), and no preepmtion (in the critical section).

Some sample output:

[michael@xorenduex simple]$ make
gcc -Wall -o tie tie.c -lpthread
[michael@xorenduex simple]$ ./tie
do_job(): box1: 300
box2: 99
do_some_job(): box1: 400
box2: 100
[michael@xorenduex simple]$ emacs -nw tie.c
[michael@xorenduex simple]$ make
gcc -Wall -o tie tie.c -lpthread
[michael@xorenduex simple]$ ./tie
do_some_job(): box1: 400
box2: 101
do_job(): box1: 300
box2: 100
[michael@xorenduex simple]$ emacs -nw tie.c
[michael@xorenduex simple]$ make
gcc -Wall -o tie tie.c -lpthread
[michael@xorenduex simple]$ ./tie
^C
[michael@xorenduex simple]$

Scribe Notes

• s1
• s2
• s3

Readings

• MOS: 6.2 "Introduction to Deadlocks" (NB: MOS 6.2.1 should be memorized!)
• MOS: 6.4 "Deadlock Detection and Recovery"
• MOS: 6.5 "Deadlock Avoidance"
• MOS: 6.6 "Deadlock Prevention"