Deadlocks

Question 1

deadlock

Answer 1

A set of processes is deadlocked if:
- Each process in the set waiting for an event
- That event can be caused only by another
process

Question 2

livelock

Answer 2

operations are being executed but no progress is made

Question 3

conditions for resource deadlocks

Answer 3

1. mutual exclusion
2. hold and wait
3. no preemption
4. circular wait condition

Question 4

mutual exclusion

Answer 4

each resource is assigned to at most one process

Question 5

hold and wait

Answer 5

processes can request a resource when holding another one

Question 6

no preemption

Answer 6

resources cannot be taken away from a process

Question 7

circular wait condition

Answer 7

chain of two or more processes must be waiting for a resource held by next process in the chain

Question 8

deadlock handling

Answer 8

1. ignore the problem
2. deadlock detection
3. deadlock avoidance
4. deadlock prevention

Question 9

ignore the problem

Answer 9

no action taken
the OS doesn’t handle deadlocks, it is up to the programmer, i.e. manual

• Also known as the ostrich algorithm
• Cost-effective solution to deadlocks
• Assumes deadlocks are rare
• Assumes cost of handling deadlocks is high
• Assumes effects of deadlocks are tolerable
• Simplest solution to manage system resources, i.e., process table, inode table, swap space, etc.

Question 10

deadlock detection

Answer 10

detect deadlock and perform recovery actions
algorithm for detection + algorithm/mechanism for recovery

• Detection
  
  • Check for cycles in the resource allocation graph
  • Track progress and time out
  • Explicit detection (e.g., OOM)
• Useful in practice when simple and efficient detection mechanisms (e.g., progress tracking or explicit detection) along with recovery actions are available

Question 11

deadlock avoidance

Answer 11

carefully allocate resources to avoid deadlocks
requires additional information about resources a process might need during its lifeitme

Question 12

deadlock prevention

Answer 12

structurally prevent any of the deadlock conditions
provides a method for ensuring at least one of the 4 conditions cannot hold

Question 13

recovery from a deadlock

Answer 13

force preemption
checkpoint-rollback
killing the offending process

Question 14

killing the offending process

Answer 14

1. abort all deadlocked processes
   ⇒ expensive, computations done so far have to be done again
2. abort one process at a time until the deadlock cycle is eliminated
   ⇒ considerable overhead, after each process is aborted a deadlock check algorithm is invoked
   abort processes whose termination will incur the minimum cost; think about:
   • what the priority of the process is
   • how long the process has computed how much longer the process will compute completing its designated task
   • resources the process is using and needs to use
   • how many processes will be terminated
   • whether the process is interactive or batch

Question 15

issues with aborting a process

Answer 15

it was modifying a file→ it leaves a file in an incorrect state

Question 16

force preemption

Answer 16

• reassign the resources so that the deadlock is resolved
• issues:
  
  • select a victim process: minimise cost
  • rollback: what to do with the victim (can’t continue execution) → roll back to some safe state and restart it from that state
    
    • hard to find a safe state → total rollback (abort and restart essentially)
  • starvation: if victim selection is based primarily on cost factors, it may be chosen every time and as a result it will never complete

Question 17

deadlock avoidance

Answer 17

• safe state: the system can allocate resources to each process (up to its maximum) in some order and still avoid a deadlock
• safe sequence: all requests will be satisfied
• not all unsafe states are deadlock

Question 18

Banker’s algorithm

Answer 18

• Customers (processes) request credits (resources)
• Banker (OS) only satisfies requests resulting in safe states
• A state is safe iff there exists a sequence of other states that allows all the customers to complete
• Maximum credit demands are known in advance
• safe state: anybody can obtain new credits and complete, then others can obtain credits and complete
• unsafe state: nobody can obtain new credits and complete
  
  • not enough resources for everyone’s max

Question 19

deadlock prevention with mutual exlusion

Answer 19

• must hold for non-shareable processes → hard to avoid
• spool everything: typically shifts the problem somewhere else
• not really an option

Question 20

deadlock prevention with hold and wait

Answer 20

• requests all resources initially (or reacquire them)
  
  • one protocol that can be used requires each process to request and be allocated to its resources before it begins execution
• instead: release current resources and the request new ones
• poor parallelism and resource utilisation, starvation is possible

Question 21

deadlock prevention with no preemption

Answer 21

• take resources away
• if a process is requesting something it releases everything → preemption
• applicable only to resources whose state can be easily saved and restored later, such as CPU registers and memory space
• N/A in many cases (e.g. printer vs. memory)

Question 22

deadlock prevention with circular wait

Answer 22

• order resources numerically
• process requests resources in an increasing order
  
  • example: P1 has R5, it then needs R4 and R3 → the requests won’t be granted (3,4 < 5)
• hard to consistently enforce in practice

Question 23

deadlock handling in practice

Answer 23

deadlock avoidance: rarely an option (hard to know a resource a priori)
deadlock prevention: adopted in particular domains
ignore the problem: last resort when nothing is available
deadlock detection: solution of choice when adequate detection (and recovery) mechanism are available

Question 24

global OOM killer

Answer 24

• resource: memory
• mechanisms: explicit detection

Question 25

soft lockup detection

Answer 25

• resource: locks
• mechanisms: progress tracking

Question 26

locking validator

Answer 26

• resource: locks
• mechanisms: cycles in the resource allocation graph

Question 27

deadlock detection on Linux

Answer 27

global OOM killer
soft lockup detection
locking validator