Please enable JavaScript.
Coggle requires JavaScript to display documents.
Deadlocks, Deadlocks - Coggle Diagram
Deadlocks
System Model
A thread may utilize a resource in
only the following sequence:
1. Request. The thread requests the resource. If the request cannot be granted immediately (for example, if a mutex lock is currently held by another thread),then the requesting thread must wait until it can acquire the resource.
2. Use. The thread can operate on the resource (for example, if the resource is a mutex lock, the thread can access its critical section).
- Release. The thread releases the resource.
:check:A set of threads is in a deadlocked state when every thread in the set is waiting for an event that can be caused only by another thread in the set.
-
-
Deadlock Prevention
:red_flag:Mutual Exclusion--at least one resource must
be nonsharable. Sharable resources do not require mutually exclusive access and thus cannot be involved in a deadlock
:red_flag:Hold and Wait--To ensure that the hold-and-wait condition never occurs in the system,we must
guarantee that, whenever a thread requests a resource, it does not hold any other resources
:red_flag:No Preemption--If a thread is holding some resources and requests another resource that cannot be immediately allocated to it (that is, the thread must wait), then all resources the thread is currently holding are preempted
:red_flag:Circular Wait--to impose a total ordering of
all resource types and to require that each thread requests resources in an increasing order of enumeration
-
Deadlocks
Deadlock Avoidance
A deadlock avoidance algorithm dynamically examines the resource-allocation state to ensure that a circular-wait condition can never exist. The resource-allocation
state is defined by the number of available and allocated resources and the maximum demands of the threads
Safe State
:check:A state is safe if the system can allocate resources to each thread (up to its
maximum) in some order and still avoid a deadlock.More formally, a system is in a safe state only if there exists a safe sequence.
:check:A safe state is not a deadlocked state. Conversely, a deadlocked state is an unsafe state.Not all unsafe states are deadlocks.An unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe (and deadlocked) states
-
Banker's Algorithm
:check:The resource-allocation-graph algorithm is not applicable to a resource allocation system with multiple instances of each resource type ,applicable to such a system but is less efficient than the resource-allocation graph scheme
:pencil2:When a new thread enters the system, it must declare the maximum number
of instances of each resource type that it may need
:pencil2:When a user requests a
set of resources, the system must determine whether the allocation of these resources will leave the system in a safe state.If it will, the resources are allocated;
otherwise, the thread must wait until some other thread releases enough resources.
-
-
Resource-Request Algorithm
- If Request[i] ≤ Need[i], go to step 2. Otherwise, raise an error condition, since the thread has exceeded its maximum claim
- If Request[i]≤ Available, go to step 3. Otherwise, Ti must wait, since the
resources are not available.
3.Available = Available–Request[i]
Allocation[i] = Allocation[i] + Request[i]
-