Deadlock Characteristics
Deadlock Characterization
In a deadlock, processes never finish executing, and system resources are tied up, preventing other jobs from starting. Before we discuss the various methods for dealing with the deadlock problem, we look more closely at features that characterize deadlocks.
Necessary Conditions
A deadlock situation can arise if the following four conditions hold simultaneously in a system:
1. Mutual exclusion
At least one resource must be held in a nonsharable mode; that is, only one process at a time can use the resource. If another process requests that resource, the requesting process must be delayed until the resource has been released.
DEADLOCK WITH MUTEX LOCKS
Let's see how deadlock can :occur in a multithreaded Pthread program using mutex locks. The pthread_mutex_init() function initializes an unlocked mutex. Mutex locks are acquired ;and released using pthread_mutex_lock() and pthread_mutex_unlock() respectively. If a thread attempts to acquire a locked niutex the call to X pthread_mutex_lock() blocks the thready until the owner of the rnutex lock invokes pthread_mutex_unlock().
Two mutex lock are created uaing following code example.
/* create and initialize mutex locks */
pthread_mutex_t first_mutex
pthread_mutex_t second_mutex
pthread_mutex_init(firxt_mutex,null)
pthread_mutex_init(second_mutex,null)
Next, two threads—thread-one and thread-two are created, and both tliese threads have access to both mutex locks,thread-one and thread-two run in the functions do_work_one() and do_work_two(), respectively as shown in Figure
In this example, thread one attempts to acquire the mutex locks in the order (1) first_mutex (2) second_mutex, while thread_two attempts to acquire the mutex locks: in the order (1) second _mutex (2) first_mutex. Deadlock is possible, If thread_one
2. Hold and wait.
A process must be holding at least one resource and waiting to acquire additional resources that are currently being held by other processes.
3. No preemption.
Resources cannot be preempted.; that is, a resource can be released only voluntarily by the process holding it, after that process has completed its task.
4. Circular wait.
A set {P0, P1, ..., Pn} of waiting processes must exist such that P0 is waiting for a resource held by P1, P1 is waiting for a resource held by Pi,……., P(i-1) is waiting for a resource held by Pn. We emphasize that all four conditions must hold for a deadlock to occur. The circular-wait condition implies the hold-and-wait condition, so the four conditions are not completely independent.
Resource-Allocation Graph
Deadlocks can be described more precisely in terms of a directed graph called a system resource-allocation graph. This graph consists of a set of vertices V and a set of edges E. The set of vertices V is partitioned into two different types of nodes: P - {Pi, Pi,,.., P,,\, the set consisting of all the active processes in the system, and R = {R[, R?, •••/ Rm}, the set consisting of all resource types in the system. A directed edge from process P- to resource type Rj is denoted by P; -> R ,•; it signifies that process P, has requested an instance of resource type R, and is currently waiting for that resource. A directed edge from resource type Rj to process P- is denoted by Rj -»• P,; it signifies that an instance of resource type Rj has been allocated to process P;. A directed edge P, —> Rj is called a request edge; a directed edge Rj -* P; is called an assignment edge. Pictorially, we represent each process P, as a circle and each resource type Ri as a rectangle. Since resource type Rj may have more than one instance, we represent each such instance as a dot within the rectangle. Note that a request edge points to only the rectangle R;, whereas an assignment edge must also designate one of the dots in the rectangle. When process P, requests an instance of resource type Rj, a request edge is inserted in the resource-allocation graph. When this request can be fulfilled, the request edge is instantaneously transformed to an assignment edge. When the process no longer needs access to the resource, it releases the resource; as a result, the assignment edge is deleted. The resource-allocation graph shown in Figure 7.2 depicts the following situation.
Resource instances:
- One instance of resource type R1
- Two instances of resource type R2
- One instance of resource type R3
- Three instances of resource type Ri
The graph contains no cycles, then no process in the system is deadlocked. If the graph does contain a cycle, then a deadlock may exist. If each resource type has exactly one instance, then a cycle implies that a deadlock has occurred. If the cycle involves only a set of resource types, each of which has only a single instance, then a deadlock has occurred. Each process involved in the cycle is deadlocked. In this case, a cycle in the graph is both a necessary and a sufficient condition for the existence of deadlock. If each resource type has several instances, then a cycle does not necessarily imply that a deadlock has occurred. In this case, a cycle in the graph is a necessary but not a sufficient condition for the existence of deadlock. To illustrate this concept, we return to the resource-allocation graph depicted in Figure 7.2.
Suppose that process P3 requests an instance of resource type RT. Since no resource instance is currently available, a request edge P3 —>• R2 is added to the graph (Figure 7.3). At this point, two minimal cycles exist in the svstem:
Processes P\, P2, and P3 are deadlocked. Process P2 is waiting for the resource R3, which is held by process P3. Process P3 is waiting for either process P\ or
Frequently Asked Questions
Recommended Posts:
- Operating System Concepts ( Multi tasking, multi programming, multi-user, Multi-threading )
- Different Types of Operating Systems
- Batch Operating Systems
- Time sharing operating systems
- Distributed Operating Systems
- Network Operating System
- Real Time operating System
- Various Operating system services
- Architectures of Operating System
- Monolithic architecture - operating system
- Layered Architecture of Operating System
- Microkernel Architecture of operating system
- Hybrid Architecture of Operating System
- System Programs and Calls
- Process Management - Process concept