Seong-lae ChoTwo different paths could end up waiting for each other to release a Semaphore .
Deadlock problem - A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set
- Has a set of processes
- Has a set of resources
- deadlocks can occur across machines (between I/O processes)
Paradigm of resource usage by process →
ex. - semaphores A and B, initialized to 1
- P1 and P2 each hold one tape drive and each needs another one
Deadlock problem is important in special purpose OS
Bridge Crossing
- it can be resolved if one car backs up - preempt resources and rollback
- Several cars may have to be backed up(kill process) if a deadlock occurs
- Starvation is possible
Kill process need restart process - Why?
Resource Allocation Graph
Model tuple of the state of a computer system as a directed graph
Request edge : process to resource (not to special one resource set itself)
Allocation edge : resource to process
“Necessary” Conditions for a Deadlock
Deadlock can arise if the following four conditions hold simultaneously - at the same time
- Mutual exclusion : only one process at a timfe can use a resource.
- Hold and wait : a process holding at least one resource is waiting to acquire additional resources held by other processes.
- No preemption : a resource can be released only voluntarily by the process holding it.
- Circular wait : a cycle in the resource allocation graph
So we will not make this conditions simultaneously by Handling Deadlocks
theorem 2 is only enable sufficient condition
Method 1: Deadlock Prevention
Ensure that one of the four deadlock conditions never occur ← make one false among 4 (not about information, policy and data structure change)
1 → make shareable share
make mutual exclusive available resources to not exclusively is impossible → Must hold for non-shareable resources
2 → No wait or No hold (resources utilization become low, starvation possible)
Guarantee that whenever a process requests a resource, it does not hold any other resources
Require process to request and be allocated “all” its resources before it begins execution, or allow process to request resources only when the process has “none”.
3 → become preemptive (stop while processing)
If a process that is holding some resources requests another resource that cannot be immediately allocated to it, then all resources currently being held are released
Preempted resources are added to the list of available resources
Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting
Can be applied to resources whose state can be easily saved and restored later : e.g. CPU registers, memory, …
4 → remove cycle (if no resources can be substituted → Theorem 2) most used method
Impose a total ordering of all resource types, and require that each process requests resources in order of enumeration
Method 2: Deadlock Avoidance
Avoid deadlock by run-time checking and allocation of resources - check before allocate (never enter an unsafe state)
Requires that the system has some additional a priori information and algorithm
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
The deadlock-avoidance algorithm dynamically examines the “resource-allocation state” to ensure that there can never be a circular-wait condition
- Safe State : System is in safe state if there exists a safe sequence of all processes
requests resource → decide immediate allocation leaves the system in a “safe” state
Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes
Then How can we do that by what algorithm?
if resource is single instance → use resource allocation graph and check cycle
if resource is multiple instance →
Method 3: Deadlock Detection and Recovery
Let the system deadlock and then deal with it (No a priori information, algorithm exist)
Detection Algorithm
Request: an n x m matrix indicates the current request of each process (Replace Need with Request matrix) - it is safety algorithm in banker's algorithm
usually each process is not assumed to have knowledge in its maximum use
Then how often we will invoke algorithm - have no answer
Recovery from Deadlock
Methods of recovery
- Process terminate - lose all process, not easy to recover process done
- resource preemption
- Selecting a victim, rollback, starvation is an issue
if resource is multiple instance → Detection algorithm like banker's algorithm
caution of starvation → aging
need to kill cause process → re-deadlock
Rollback - 최소한 싸이클이 없어질 만큼의 프로세스는 죽여야 한다.
wait for 그래프는 어떤 프로세스가 어떤 리소스를 wait하고 있는가만 체크한다. 싸이클이 발생했으면 데드락이 발생 한 것이다.
if resource is single instance → check wait-for graph 주깆거
Method 4: No policy
Ignore the problem and pretend that deadlocks never occur in the system → just reboot
Used by most operating systems, including UNIX and Windows ← too much overhead
