Deadlocks
Last updated
Last updated
Four requirements for occurrence of Deadlock:
Mutual exclusion: Only one thread at a time can use a resource.
Hold and wait: Thread holding at least one resource is waiting to acquire additional resources held by other threads
No preemption: Resources are released only voluntarily by the thread holding the resource, after thread is finished with it
Circular wait: Having a circle doesn't mean that a dead lock exists.
Infinite resources: Include enough resources so that no one ever runs out of resources.
No Sharing of resources (totally independent threads): Not very realistic
Don’t allow waiting
Make all threads request everything they’ll need at the beginning
Force all threads to request resources in a particular order preventing any cyclic use of resources
Given Matrices:
Request Matrix Q
Allocation Matrix A
Resource Vector
Available Vector
Mark each process that has a row in the Allocation Matrix of all zeros.
Initialize a temporary vector W to equal the Available vector.
Find an index i such that process i is currently unmarked and the ith row of Q is less than or equal to W. If no such row is found, terminate the algorithm.
If such a row is found, mark process i and add (the process continues and finally releases the resources it holds) the corresponding row of the allocation matrix to W. Return to Step 3.
Marks mean granting the requests. We perform marks on the request matrix.
The core of this algorithm is to determine whether, given the current situation of requests, we can find a sequence of allocations to make. If there's no requests, the system is not deadlocked even if it is in unsafe state.
There are several candidate strategies for determining when to detect deadlocks.：
To check every time a resource request is made (certain to detect deadlocks as early as possible, but potentially expensive in terms of CPU time)
To check only when the CPU utilization has below some threshold (if enough processes are deadlocked, there will be few runnable processes)
Roll back the actions of deadlocked threads
Two approaches to avoid deadlock:
Process Initailization Denial
Resource Allocation Denial
Advantages
It is not necessary to preempt or roll back processes (as in deadlock detection)
It is less restrictive than deadlock prevention
Disadvantages:
Maximum resource requirement must be stated in advance
Processes under consideration must be independent; no synchronization requirements
There must be a fixed number of resources to allocate
No process may exit while holding resources
Safe state: there is at least one sequence that does not result in deadlock.
Unsafe state: a state that is not safe.
We can make sure that the system is always in a safe state to avoid deadlock. For a resource allocation request, we assume that the resource is granted and examine the state of the system after allocation. If the new state is unsafe, then we deny the request.
When a process makes a request for a set of resources, assume that the request is granted. Update the system state accordingly. Then determine whether the result is a safe state. If safe, grant the request; otherwise, block the process until it is safe to grant the request.
An unsafe state is not necessarily a deadlock.
Consider a system with 12 tape drives with:
This is an unsafe state. But we're not in a deadlock. There's only 4 free drives, so, for example, if P0 does request an additional 5, and P2 does request an additional 1, we will deadlock, but it hasn't happened yet. And P0 might not request any more drives, but might instead free up the drives it already has. The Max need is over all possible executions of the program, and this might not be one of the executions where we need all 10 drives in P0.
To check every minutes
A process can start only if
