User Rating:  / 0

PoorBest 

Related Content: CS604 - VU Lectures, Handouts, PPT Slides, Assignments, Quizzes, Papers & Books of Operating Systems

Summary

• Monitor-based solution of the dining philosophers problem
• The deadlock problem
• Deadlock characterization
• Deadlock handling
• Deadlock prevention

Monitor-based Solution for the Dining Philosophers Problem

Let us illustrate these concepts by presenting a deadlock free solution to the dining philosophers problem. Recall that a philosopher is allowed to pick up her chopsticks only if both of them are available. To code this solution we need to distinguish among three states in which a philosopher may be. For this purpose we introduce the following data structure:

Philosopher i can set the variable state[i]=eating only if her two neighbors are not eating: (state[(i+4)%5]!=eating) and (state[(i+1)%5]!=eating).

We also need to declare five condition variables, one for each philosopher as follows.
A philosopher uses her condition variable to delay herself when she is hungry, but is unable to obtain the chopsticks she needs.

We are now in a position to describe our monitor-based solution to the diningphilosophers problem. The distribution of the chopsticks is controlled by the monitor dp; whose definition is as follows:

Each philosopher before starting to eat must invoke the pickup operation. This operation ensures that the philosopher gets to eat if none of its neighbors are eating. This may result in the suspension of the philosopher process. After the successful completion of the operation, the philosopher may eat. Following this, the philosopher invokes the putdown operation and may start to think. The putdown operation checks if a neighbor (right or left—in this order) of the leaving philosopher wants to eat. If a neighboring philosopher is hungry and neither of that philosopher’s neighbors is eating, then the leaving philosopher signals it so that she could eat. In order to use this solution, a philosopher i must invoke the operations pickup and putdown in the following sequence:

It is easy to show that this solution ensures that no two neighbors are eating simultaneously and that no deadlocks will occur. We note, however, that it is possible for a philosopher to starve to death. You should think about this problem and satisfy yourself.

The Deadlock Problem

A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set. Here’s an example:

• System has 2 tape drives.
• P1 and P2 each hold one tape drive and each needs another one.

Another deadlock situation can occur when the poor use of semaphores, as discussed in lecture 23. We reproduce that situation here. Assume that two processes, P0 and P1, need to access two semaphores, A and B, before executing their critical sections. Semaphores are initialized to 1 each. The following code snippets show how a situation can arise where P0 holds semaphore A, P1 holds semaphore B, and both wait for the other semaphore—a typical deadlock situation as shown in the figure that follows the code.

In the first solution for the dining philosophers problem, if all philosophers become hungry at the same time, they will pick up the chopsticks on their right and wait for getting the chopsticks on their left. This causes a deadlock.
Yet another example of a deadlock situation can occur on a one-way bridge, as shown below. Traffic flows only in one direction, and each section of a bridge can be viewed as a resource. If a deadlock occurs, it can be resolved if one car backs up (preempt resources and rollback). Several cars may have to be backed up if a deadlock occurs. Starvation is possible.

In the next three to four lectures, we will discuss the issue of deadlocks in computer systems in detail.

System Model

A system consists of a finite number of resources to be distributed among a finite number of cooperating processes. The resources are partitioned into several types, each of which consists of some number of identical instances. Memory space, CPU cycles, disk drive, file are examples of resource types. A system with two identical tape drives is said to have two instances of the resource type disk drive.
If a process requests an instance of a resource type, the allocation of any instance of that type will satisfy the request. If it will not, then the instances are not identical and the resource type classes have not been defined properly.
A process must request a resource before using it, and must release the resource after using it. A process may request as many resources as it requires in order to carryout its designated task. Obviously, the number of resources requested may not exceed the total number of resources available in the system. Under the normal mode of operation, a process may utilize a resource in only the following sequence:

1. Request: The process requests a needed resource. If the request cannot be granted immediately, then the requesting process must wait until it can acquire the resource.
2. Use: The process can use the resource.
3. Release: The process releases the resource.

Deadlock Characterization

The following four conditions must hold simultaneously for a deadlock to occur:

1. Mutual exclusion: At least one resource must be held in a non-sharable 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.
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, after using it a process releases a resource only voluntarily.
4. Circular wait: A set of waiting processes must exist such that P0 is waiting for a resource that is held by is waiting for a resource that is held by is waiting for a resource held by is waiting for a resource held by P0.

Resource Allocation Graphs

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 is portioned into two different types of nodes P={P0, P1… Pn}, the set of the active processes in the system, and R={R0, R1… Rn}, the set consisting of all resource types in the system. A directed edge from a process Pi to resource type Rj signifies that process Pi requested an instance of Rj and is waiting for that resource. A directed edge from Rj to Pi signifies that an instance of Rj has been allocated to Pi. We will use the following symbols in a resource allocation graph.

• Process
• Resource Type with 4 instances
• Pi requests instance of Rj
• Pi is holding an instance of Rj

The resource allocation graph shown below 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 R4

Process States

Given the definition of a resource allocation graph, it can be shown that if the graph contains no cycles, then no process is deadlocked. If the graph contains cycles then:

• If only one instance per resource type, then a deadlock exists.
• If several instances per resource type, possibility of deadlock exists.

Here is a resource allocation graph with a deadlock. There are two cycles in this graph:

No process will release an already acquired resource and the three processes will remain in the deadlock state.

The graph shown below has a cycle but there is no deadlock because processes P2 and P4 do not require further resources to complete their execution and will release the resources they are currently hold in finite time. These resources can then be allocated to P1 and P3 for them to resume their execution.

In the next lecture, we will characterize deadlocks. In other words, we will discuss the condition that must hold for a deadlock to occur. Following this we will discuss the various techniques to handle deadlocks.

• < Prev
• Next >