Deadlock

This post was migrated from Tistory. You can find the original here.

Deadlock

Conditions for occurrence

• Mutual exclusion - A resource can only be used by one process at a time.
• Hold and wait - A process holds a resource while requesting additional resources.
• No preemption - A resource that is currently held cannot be taken away by another process.
• Circular wait - The resources being held and waited on form a circular chain.

Solutions

• Prevention - Negate any of the conditions above except mutual exclusion
  * Release the currently held resource before requesting a new one
  * Allow competition for resources that are already held
  * Prevent circular chains by fully processing one process’s requests before moving on to the next

• Avoidance - Design the algorithm carefully so that a deadlock never occurs in the first place (a less strict restriction than prevention)
  * Banker’s algorithm

• Detection and recovery - Use an algorithm to detect and resolve a deadlock after it happens.
  * Resource allocation graph (detection)
  * Killing processes (recovery) - Kill processes one by one to break the deadlock. A victim must be chosen, and this can lead to starvation.
  * Resource preemption (recovery) - Preempt (take away) resources allocated to a process and reassign them to other processes until the deadlock is resolved.

References

https://chanhuiseok.github.io/posts/cs-2/**

[[운영체제] 데드락(Deadlock, 교착 상태)이란?

컴퓨터/IT/알고리즘 정리 블로그

chanhuiseok.github.io](https://chanhuiseok.github.io/posts/cs-2/)