CS 332 s20 — Deadlock

Table of Contents

1 Video Lecture

Please watch the video lecture: It contains sections on

  1. the Sora (0:00)
  2. Introduction (0:43)
  3. Dining Philosophers (1:24)
  4. Definitions (4:04)
  5. Deadlock by Mutually Recursive Locking (7:03)
  6. Deadlock by Nested Waiting (7:49)
  7. Doesn’t Have to be Locks: Deadlock by Full Buffer (8:45)
  8. Necessary Conditions for Deadlock (9:43)
  9. Preventing Deadlock (11:28)
  10. Limited Resources? Provide Enough Resources (13:16)
  11. Eliminate Wait While Holding (16:06)
  12. Motivating Example for Predicting the Future (22:21)
  13. Deadlock-able System Has Three States (23:57)
  14. Avoiding Deadlock: Predict the Future (25:49)
  15. Banker’s Algorithm (28:51)
  16. Recovering From Deadlock (31:50)
  17. Detecting Deadlock (38:27)
  18. Reading: Dining Philosophers and Deadlock (42:31)
  19. end notes (43:19)

The Panopto viewer has table of contents entries for each slide (https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=c93b749d-4c59-4e10-98c4-abb801236c09). You can access the lecture slides here.

2 Banker's Algorithm Pseudocode

An example of the Banker's Algorithm in the context of a generic Resource Manager class. Here is the state of the system, where we track (i) the current allocation of each resource to each thread, (ii) the maximum allocatino possible for each thread, and (iii) the current set of available, unallocated resources: 

class ResourceMgr{
  private:
    Lock lock;
    CV cv;
    int r;          // Number of resources
    int t;          // Number of threads
    int avail[];    // avail[i]: instances of resource i available
    int max[][];    // max[i][j]: max of resource i needed by thread j
    int alloc[][];  // alloc[i][j]: current allocation of resource i to thread j
  ...
}

The code for processing a resource request: 

// Invariant: the system is in a safe state.
ResourceMgr::Request(int resourceID, int threadID) {
    lock.Acquire();
    assert(isSafe());
    while (!wouldBeSafe(resourceID, threadID)) {
        cv.Wait(&lock);
    }
    alloc[resourceID][threadID]++;
    avail[resourceID]--;
    assert(isSafe());
    lock.Release();
}

isSafe() and wouldBeSafe() are the key to preventing deadlock: 

// A state is safe iff there exists a safe sequence of grants that are sufficient 
// to allow all threads to eventually receive their maximum resource needs.

bool
ResourceMgr::isSafe() {
    int j;
    int toBeAvail[] = copy avail[];
    int need[][] = max[][] - alloc[][];  // need[i][j] is initialized to 
                                         // max[i][j] - alloc[i][j]
    bool finish[] = [false, false, false, ...]; // finish[j] is true
                                         // if thread j is guaranteed to finish

    while (true) {
        j = any threadID such that:
             (finish[j] == false) && forall i: need[i][j] <= toBeAvail[i];
        if (no such j exists) {
            if (forall j: finish[j] == true) {
                return true;
            } else {
                return false;
            }
        } else {  // Thread j will eventually finish and return its 
                  // current allocation to the pool.
            finish[j] = true;
            forall i:  toBeAvail[i] = toBeAvail[i] + alloc[i][j];
        }
    }
}

// Hypothetically grant request and see if resulting state is safe.

bool 
ResourceMgr::wouldBeSafe(int resourceID, int threadID) {  
    bool result = false;       

    avail[resourceID]--;
    alloc[resourceID][threadID]++;
    if (isSafe()) {
        result = true;
    }
    avail[resourceID]++;
    alloc[resourceID][threadID]--;
    return result;
}

3 Coffman et al.'s Test for Deadlock

// A state is safe iff there exists a safe sequence of grants that would allow 
// all threads to eventually receive their maximum resource needs.
//
// avail[] holds free resource count 
// alloc[][] holds current allocation
// request[][] holds currently-blocked requests
bool
ResourceMgr::isDeadlocked() {
    int j;
    int toBeAvail[] = copy avail[];
    bool finish[] = [false, false, false, ...]; // finish[j] is true if thread 
                                                // j is guaranteed to finish

    while(true) {
        j = any threadID such that (finish[j] == false) && 
                                (forall i: request[i][j] <= toBeAvail[i]);
        if (no such j exists) {
            if (forall j: finish[j] == true) {
                return false;
            } else {
                return true;
            }
        } else {
            // Thread j *may* eventually finish and 
            // return its current allocation to the pool.
            finish[j] = true;
            forall i: toBeAvail[i] = toBeAvail[i] + alloc[i][j];
        }
    }
}

4 Reading: Dining Philosophers and Deadlock

Read OSTEP section 31.6, (p. 401-404) on the dining philosophers problem and OSTEP section 32.3, (p. 413–422) about deadlock. The former discusses the problem in the context of semaphores, and the latter gives a good overview of the conditions needed for deadlock and some possible solutions including a lock-free approach not covered in the video.

5 Homework

  1. Finish your lab 3 design docs by tonight! I'll be setting up private Slack channels for each peer review group later today. You should post your design doc there no later than tomorrow.
  2. Work through the homework questions in OSTEP chapter 32 to explore the code for different approaches for avoiding deadlock. Download the code here: http://pages.cs.wisc.edu/~remzi/OSTEP/Homework/HW-Threads-RealDeadlock.tgz