[OS]Deadlock Resolution

Deadlock

• Blocked / Asleep state
• Deadlock state
• Deadlock vs Starvation

Classification by preemptive availability

• Preemptible resources
  • Processor, memory
• Non-preemptible resources
  • disk drive

Classification by allocation unit

• Total allocation resources
  • Processor, disk drive
• Partitioned allocation resources
  • Moemory

Classification based on concurrent use

• Exclusive allocation resources
  • Processor, memory, disk drive
• Shared allocation resource
  • Program(sw), shared data

Classification based on reusability

• SR(Serially-reusable Resources)
  • Processor, memory, disk drive, program
• CR (Consumable Resources)
  • signal, message

Deadlock Model

• Graph Model
• State Transition Model

Graph Model

• Node
• Edge

State Transition Model

• State

Deadlock Occurrence Conditions

• Exclusive use of resources
• Non-preemptible resources
• Hold and wait (Partial allocation)
• Circular wait

Deadlock solution

• Deadlock prevention methods
• Deadlock avoidance method
• Deadlock detection and deadlock recovery methods

Deadlock Prevention

• Remove one of the four deadlock occurrence requirements
  • Exclusive use of resources
  • Non-preemptible resources
  • Hold and wait (Partial allocation)
  • Circular wait
• Low device utilization
• Reduced system throughput
• Not practical

Deadlock Avoidance

• Safe state
  • Safe sequence exists
• Unsafe state
• High overhead
• Low resource utilization
• Not practical

Deadlock Detection

• Resource Allocation Graph(RAG)
  • Directed, bipartite Graph

Deadlock Detection Method

• Graph reduction
  • Completely reduced
  • Irreducible

Deadlock Recovery

• deadlock recovery methods
  • Process termination
  • Resource preemption

Process termination

• Termination cost model
  • Termination cost
    • Precess priority
    • Process type
    • Accumulated execution time of the process
    • Remaining time of the process
    • Accounting cost
    • Etc.

Resource preemption

• Preemption cost model
• Minimum cost recovery method
  • O(r)

---

Reference

Deadlock Resolution