View source for 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 [http://www.cpsc.ucalgary.ca/~locasto/teaching/2013/CPSC457-Fall/talks/deadlock.pdf slide deck for today on Deadlocks]

Below are some code snippets from the program we wrote today in class [http://www.cpsc.ucalgary.ca/~locasto/teaching/2013/CPSC457-Fall/code/tie.c 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 ==
* [[Courses/Computer_Science/CPSC_457.F2013/Lecture_Notes/Scribe1#November_1:_Deadlock | 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"