Deadlock Characteristics



Rating - 3/5
469 views

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

These Topics Are Also In Your Syllabus Deadlock Characteristics
1 Types of Operating Systems - Batch operating system, Time-sharing systems, Distributed OS, Network OS, Real Time OS link
2 Application I/o Interface link
You May Find Something Very Interesting Here. Deadlock Characteristics link
3 Transforming I/O Requests to Hardware Operations link
4 streams link
5 I/O performance link

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 7.1.

 

DEADLOCK WITH MUTEX LOCKS

Lets see how deadlock can occur in a multithreaded Pthread program using mutex locks. The pthread_mutex_init() function initiallizes 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 mutex , the call to X.pthread_mutx_lock() blocks the thread untill the owner of the mutex lock invokes pthread_mutex_unlock().

       Two mutex locks are created in the following code example :

These Topics Are Also In Your Syllabus Deadlock Characteristics
1 Types of Operating Systems - Batch operating system, Time-sharing systems, Distributed OS, Network OS, Real Time OS link
2 Deadlock prevention link
You May Find Something Very Interesting Here. Deadlock Characteristics link
3 Deadlock Avoidance link
4 Deadlock Recovery link
5 Stable Storage Implementation link

/* Create and initialize the mutex locks */

pthread_mutex_t first_mutex;

pthread_mutex_t first_mutex;

pthread_mutex_init(&firxt_mutex,NULL);

pthread_mutex_init(&second_mutex,NULL);

Deadlock Characteristics

Deadlock Characteristics

     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 

Deadlock Characteristics

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.

These Topics Are Also In Your Syllabus Deadlock Characteristics
1 Types of Operating Systems - Batch operating system, Time-sharing systems, Distributed OS, Network OS, Real Time OS link
2 operating system structure link
You May Find Something Very Interesting Here. Deadlock Characteristics link
3 System calls link
4 Computer System organization link
5 Operating System Generation link

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 {P$, Pi, ..., Pn\ of waiting processes must exist such that P-0 is waiting for a resource held by P\, P\ is waiting for a resource held by Pi, •••, P.,--i is waiting for a resource held by Pn, and P,, 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.

• The sets P, R, and £: o P={PhP2/P?,} o R= {/?!, RZ,R3, R;} o £ = {p, _> Ru P2 _> R3/ R, _> p2f R2 _> P2/ R2 _> p.,, R3 -> P3 } * 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

Deadlock Characteristics

These Topics Are Also In Your Syllabus Deadlock Characteristics
1 Types of Operating Systems - Batch operating system, Time-sharing systems, Distributed OS, Network OS, Real Time OS link
2 System Model link
You May Find Something Very Interesting Here. Deadlock Characteristics link
3 Deadlock Characteristics link
4 Atomicity link
5 Kernel Modules link

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:

Deadlock Characteristics

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

Deadlock CharacteristicsDeadlock Characteristics


Rating - 3/5
484 views

Advertisements