本文共 6340 字,大约阅读时间需要 21 分钟。
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set.
System resources are utilized in the following way:
For a deadlock to occur, each of the following four conditions must hold
request edge – directed edge Pi -->Rj
assignment edge – directed edge Rj --> Pi
Resource Allocation Graph With A Deadlock:
Resource Allocation Graph With A Cycle But No Deadlock:
If graph contains no cycles --> no deadlock.
If graph contains a cycle -->if only one instance per resource type, then deadlock.
if several instances per resource type, possibility of deadlock.
Prevention: Ensure one of the four conditions fails. 确保四个条件之一不满足
Avoidance: The OS needs more information so that it can determine if the current request can be satisfied or delayed.
Some sharable resources must be accessed exclusively which means we cannot deny the mutual exclusion condition. 不容易实现
No process can hold some resources and then request for other resources
–>
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
example: To break the circular waiting condition, we can order all resource types
A process can only request resources higher than the resource types it holds
A process must release some higher order resources to request a lower order resource
Requires that the system has some additional a priori information available
system must decide if immediate allocation leaves the system in a safe state
System is in safe state if there exists a safe sequence of all processes
Sequence <P1, P2, …, Pn> is safe if for each Pi, the resources that Pi can still request can be satisfied by currently available resources + resources held by all the Pj, with j<i.
If a system is in safe state --> no deadlocks
If a system is in unsafe state --> possibility of deadlock
Avoidance --> ensure that a system will never enter an unsafe state
Claim edge Pi --> Rj indicated that process Pi may request resource Rj; represented by a dashed line(虚线)
Resources must be claimed apriori in the system.资源的需求边一定要预先提出
Let n = number of processes, and m = number of resources types
Available: Vector of length m. If available [j] = k, there are k instances of resource type Rj available
Max: n x m matrix. If Max [i,j] = k, then process Pi may request at most k instances of resource type Rj.
Allocation: n x m matrix. If Allocation[i,j] = k then Pi is currently allocated k instances of Rj
Need: n x m matrix. If Need[i,j] = k, then Pi may need k more instances of Rj to complete its task.
Need=Max - Allocation
Safety Algorithm
Resource-Request Algorithm for Process Pi
Request = request vector for process Pi. If Requesti[j] = k then process Pi wants k instances of resource type Rj.
If Requesti <= Needi go to step 2. Otherwise, raise error condition, since process has exceeded its maximum claim.
If Requesti <= Available, go to step 3. Otherwise Pi must wait, since resources are not available
Pretend to allocate requested resources to Pi by modifying the state as follows:
Available = Available - Requesti;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti;
If safe -> the resources are allocated to Pi.
If unsafe -> Pi must wait, and the old resource-allocation state is restored
Detection Algorithm
Let Work and Finish be vectors of length m and n, respectively Initialize:
(a) Work = Available
(b)For i = 1,2, …, n, if Allocationi != 0, then Finish[i] = false;otherwise, Finish[i] = true
Find an index i such that both:
(a)Finish[i] == false
(b)Requesti Work
If no such i exists, go to step 4.
Work = Work + Allocationi
Finish[i] = true
go to step 2.
If Finish[i] == false, for some i, 1 <= i <= n, then the system is in deadlock state. Moreover, if Finish[i] == false, then Pi is deadlocked.
Algorithm requires an order of O(m x n2) operations to detect whether the system is in deadlocked state.
we may not be able to tell which of the many deadlocked processes “caused” the deadlock
Recovery from Deadlock: Process Termination
死锁的检测和恢复代价都很大,在大多数现有的操作系统中都忽视死锁
转载地址:http://wmgwi.baihongyu.com/