Deadlock

Wikipedia · Deadlock · CC BY-SA 4.0

Deadlock occurs when a set of processes each hold a resource and wait for another resource held by a different process in the set. Nobody can proceed. The system is stuck.

Four necessary conditions

Deadlock requires all four of these simultaneously. Break any one, and deadlock cannot occur.

Mutual exclusion: at least one resource is non-shareable
Hold and wait: a process holds one resource while waiting for another
No preemption: resources cannot be forcibly taken away
Circular wait: a cycle of processes, each waiting for the next

Resource allocation graph

A directed graph where processes and resources are nodes. An edge from a process to a resource means "waiting for." An edge from a resource to a process means "held by." A cycle in this graph indicates deadlock (for single-instance resources).

Scheme

; Deadlock detection: find a cycle in the wait-for graph
; Graph represented as adjacency list: ((node . (neighbors ...)) ...)

(define (has-cycle? graph)
  (define visited '())
  (define in-stack '())

  (define (dfs node)
    (cond
      ((member node in-stack) #t)       ; cycle found!
      ((member node visited) #f)        ; already explored
      (else
        (set! visited (cons node visited))
        (set! in-stack (cons node in-stack))
        (let ((neighbors (cond ((assoc node graph) => cdr) (else '()))))
          (let ((result (any-true? (map dfs neighbors))))
            (set! in-stack (cdr in-stack))
            result)))))

  (define (any-true? lst)
    (cond ((null? lst) #f)
          ((car lst) #t)
          (else (any-true? (cdr lst)))))

  (any-true? (map (lambda (entry) (dfs (car entry))) graph)))

; No deadlock: P1 waits for P2, P2 waits for P3
(define no-cycle '((P1 P2) (P2 P3) (P3)))
(display "P1->P2->P3: cycle? ") (display (has-cycle? no-cycle)) (newline)

; Deadlock: P1->P2->P3->P1
(define cycle-graph '((P1 P2) (P2 P3) (P3 P1)))
(display "P1->P2->P3->P1: cycle? ") (display (has-cycle? cycle-graph))

; Deadlock detection: find a cycle in the wait-for graph
; Graph represented as adjacency list: ((node . (neighbors ...)) ...)

(define (has-cycle? graph)
  (define visited '())
  (define in-stack '())

(define (dfs node)
    (cond
      ((member node in-stack) #t)       ; cycle found!
      ((member node visited) #f)        ; already explored
      (else
        (set! visited (cons node visited))
        (set! in-stack (cons node in-stack))
        (let ((neighbors (cond ((assoc node graph) => cdr) (else '()))))
          (let ((result (any-true? (map dfs neighbors))))
            (set! in-stack (cdr in-stack))
            result)))))

(define (any-true? lst)
    (cond ((null? lst) #f)
          ((car lst) #t)
          (else (any-true? (cdr lst)))))

(any-true? (map (lambda (entry) (dfs (car entry))) graph)))

; No deadlock: P1 waits for P2, P2 waits for P3
(define no-cycle '((P1 P2) (P2 P3) (P3)))
(display "P1->P2->P3: cycle? ") (display (has-cycle? no-cycle)) (newline)

; Deadlock: P1->P2->P3->P1
(define cycle-graph '((P1 P2) (P2 P3) (P3 P1)))
(display "P1->P2->P3->P1: cycle? ") (display (has-cycle? cycle-graph))

Prevention

Break one of the four conditions. Impose a total ordering on resources (break circular wait). Require processes to request all resources at once (break hold-and-wait). Allow preemption of resources.

Avoidance: Banker's algorithm

Dijkstra's Banker's algorithm checks whether granting a request leaves the system in a safe state: one where there exists a sequence in which all processes can finish. If not, the request is denied. The cost is knowing maximum resource needs in advance.

Scheme

; Banker's algorithm: is the state safe?
; available: list of available resources per type
; max-need: matrix of max needs
; allocation: matrix of current allocation

(define (safe-state? available max-need allocation)
  (let* ((n (length allocation))
         (need (map (lambda (m a) (map - m a)) max-need allocation))
         (work (list->vector available))
         (finish (make-vector n #f)))

    (define (find-runnable need-list idx)
      (cond
        ((>= idx n) #f)
        ((vector-ref finish idx) (find-runnable need-list (+ idx 1)))
        ((for-all? <= (list-ref need-list idx) (vector->list work))
         idx)
        (else (find-runnable need-list (+ idx 1)))))

    (define (for-all? pred a b)
      (cond ((null? a) #t)
            ((pred (car a) (car b)) (for-all? pred (cdr a) (cdr b)))
            (else #f)))

    (define (run-sequence need-list count order)
      (if (= count n)
          (begin (display "Safe sequence: ") (display (reverse order)) #t)
          (let ((i (find-runnable need-list 0)))
            (if (not i)
                #f
                (begin
                  (let ((alloc (list-ref allocation i)))
                    (for-each (lambda (j v)
                      (vector-set! work j (+ (vector-ref work j) v)))
                      (iota (length alloc)) alloc))
                  (vector-set! finish i #t)
                  (run-sequence need-list (+ count 1) (cons i order)))))))

    (define (iota n) (if (= n 0) '() (append (iota (- n 1)) (list (- n 1)))))

    (run-sequence need 0 '())))

; Example: 3 processes, 1 resource type
(display (safe-state? '(3) '((7) (4) (6)) '((1) (2) (3))))

; Banker's algorithm: is the state safe?
; available: list of available resources per type
; max-need: matrix of max needs
; allocation: matrix of current allocation

(define (safe-state? available max-need allocation)
  (let* ((n (length allocation))
         (need (map (lambda (m a) (map - m a)) max-need allocation))
         (work (list->vector available))
         (finish (make-vector n #f)))

(define (find-runnable need-list idx)
      (cond
        ((>= idx n) #f)
        ((vector-ref finish idx) (find-runnable need-list (+ idx 1)))
        ((for-all? <= (list-ref need-list idx) (vector->list work))
         idx)
        (else (find-runnable need-list (+ idx 1)))))

(define (for-all? pred a b)
      (cond ((null? a) #t)
            ((pred (car a) (car b)) (for-all? pred (cdr a) (cdr b)))
            (else #f)))

(define (run-sequence need-list count order)
      (if (= count n)
          (begin (display "Safe sequence: ") (display (reverse order)) #t)
          (let ((i (find-runnable need-list 0)))
            (if (not i)
                #f
                (begin
                  (let ((alloc (list-ref allocation i)))
                    (for-each (lambda (j v)
                      (vector-set! work j (+ (vector-ref work j) v)))
                      (iota (length alloc)) alloc))
                  (vector-set! finish i #t)
                  (run-sequence need-list (+ count 1) (cons i order)))))))

(define (iota n) (if (= n 0) '() (append (iota (- n 1)) (list (- n 1)))))

(run-sequence need 0 '())))

; Example: 3 processes, 1 resource type
(display (safe-state? '(3) '((7) (4) (6)) '((1) (2) (3))))

Neighbors

🔢 Graphs — deadlock detection is cycle detection in a directed graph
♟ Game Theory Ch.12 — prisoner's dilemma: deadlock is the game-theoretic outcome where rational self-interest (holding resources) leads to mutual destruction
⚙ Algorithms Ch.6 — graph cycle detection: deadlock detection is cycle detection in the resource allocation digraph

Foundations (Wikipedia)

← Synchronization by june.kim Memory Management →