Types of Resources

• preemptable resources: can be forcibly taken away from a process without negative effects
• non-preemptable resources: can not be taken away from a process without negative effects

Deadlock

• a set of processes deadlocked <=> each process waiting for event, only another process can cause
• for an deadlock to be possible both must be met
  1. mutual exclusion: each resource assigned to exactly one process or available
  2. hold and wait: processes holding resources can request additional resources
  3. non pre-emption: granted resources cannot be forcibly taken
  4. circular wait condition: circular list of porcesses each waiting for a resource held by next member in chain

Deadlock Modelling

Approaches for Handling Deadlocks

Ignoring

• if deadlocks are relatively rare possible solution
• deadlocks may resolve themselves

Deadlock Detection

One Resource per Type

• Inspect graph for deadlocks
  • DFS through resource graph

Multiple Resources per Type

• administer the following:
  • exist-resource vector $\vec{e}$: storing total number for each resource class
  • available-resource vector $\vec{a}$: storing number of available resources for each resource class
  • allocation matrix $C$: entry $c_{ij}$ specifies number of resources of class j, process i holds
  • request matrix $R$: entry $r_{ij}$ specifies how many resources of class j process i needs
• simulation:
  • search for unmarked process, e.g., row in R. If each entry in the row is smaller or equal to $\vec{a}$ -> all resources the process needs are available -> the proccess would finish after theoretical allocation
    • add i-th row if C to $\vec{a}$, so signal, that these resources would be available after this process runs
    • mark this process
  • continue untill no process to mark can be found -> terminate algorithm
• all unmarked processes would be in a deadlock

Recovery from Deadlocks

Pre-emption

• take resources away from current owner to allocate it differently
• (-) not all processes take this gracefully

Kill Process

• keep killing processes in the circular wait cycle until cycle is broken
• kill processes not in the circular wait cycle, if the freed resources would un-deadlock the circle

Rollback

• processes record checkpoints periodically
  • process can be restarted from checkpoint
• deadlock happens:
  • process who hold needed resource -> process roled back to state where it did not hold this resource
• (-) work lost
• (-) repetition could have side effects

Deadlock Avoidance

• systems decides wheter granting resource is safe
• a state is safe <=> $\exist$ scheduling order: every process completes even if all processes request all their needed resources immediately

Banker's Algorithm

• checks whether granting resource would lead to unsafe state
• only grant request if resulting state is safe
• simulation:
  • search for unmarked process, e.g., row in R. If each entry in the row is smaller or equal to $\vec{a}$ -> all resources the process needs are available -> the proccess would finish after theoretical allocation
    • assume this process requests all his needed resources, it will finish
    • add i-th row if C to $\vec{a}$, so signal, that these resources are available after the process runs
    • mark this process as terminated
  • continue untill no process to mark can be found -> terminate algorithm
• all unmarked processes would be in a deadlock
• if there are no unmarked processes the system is in a safe state

Difficulties with Deadloc Avoidance

• processes rarely know their resource needs in advance
• number of processes not fixed
• resources may vansish

Guarantee Conditions for Deadlocks are not met in the first place

Mutual Exclusion

• no process has exclusive access to resource

Hold and Wait

• prevent processes from holding resources while waiting for different resources
  • request all needed resources at one time
• (-) resource needs must be know bevorehand
• (-) possible inefficiencies

No-Pre-Emption

• take resource focibly away
• (-) difficult for some resources
• possible by resource virtualization
  • (-) not possible for all resources

Circular Wait

• impose constraints on processes' resource use
  • each process may only hold 1 resource at 1 time
  • (-) simultaneous access maybe neccessary
• resource request must be made in numerical order
  • -> no circles in allocation graph

Two-Phase Locking

• First Phase: Process request all resources needed for completion
• Second Phase: release resources as they are no longer needed ?
• (-) does not work on all systems

Communication Deadlocks

• Two processes send messages to each other
  • $A$ sends request message $M$, blocks until receiving confirmation from $B$
  • $B$ blocked until it receives requst from $A$
  • $M$ gets lost -> $A$ & $B$ blocked for ever
• solution: timeouts

Livelock

• two processes $A$ & $B$ acquire one resource and wait for the other, which they dont get. Then they release their acquired resource and try again
• $A$ & $B$ do this synchronously -> always prevent each other from completion

Starvation

• resource allocation policy always overgoes process $A$ for some reason
• solution: first-come-first serve does not have this issue