Introduction to Deadlock
What deadlock is?
Deadlock is a state where one or more process are blocked, all waiting in some event that never occur.
To illustrate a deadlock state, consider a system with three tape drives. Suppose that there ate three processes, each holding one of these tape drives. Of each process now requests another tape drive and the three processes will be on a deadlock state.
How can deadlock be handled by an operating system?
Deadlock can be handled in a number of ways by an operating system:
i) It can be ignored
ii) It can be prevented by denying one of the above necessary conditions..
iii) It can be avoided
iv) Or it can be detected and recovered from.
What do understood by a resource?
A resource ca be hardware device (e.g., a tape drive memory) or a piece of information (e.g., a locked record in a database). A computer will normally have many different resources that can be as acquired. For some resources, several identical instances may be available, such as three tape drives.
What are the various types of resources an OS manages?
Resources come in the following types:
i) Preemptible Resources:
Resources the OS remove from a process (before it is completed) and give to another process.
ii) Non-preemptible Resources:
Resources must hold from when they are allocated t o when they are released.
iii) Shared Resources:
A resource which may be used by many processes simultaneously.
iv) Dedicated Resources:
A resource that belongs to one process only. In general, deadlock involves non-preemptive resources.
The sequence of events required to use a resource:
Under the normal mode of operation, the sequence of events required to use a resource is:
i) Request: If the request can not be immediately granted (for example, the resource is being used by another process), then the requesting process must process until it can acquire the resource.
ii) Use: The process can operate on the resource (for example, if the resource is a line printer, the process can print on the printer).
iii) The process releases the resource.
Resource allocation graph.
Deadlock can be described more precisely in terms of a directed graph called a system resource allocation graph. This consist of a pair = (V,E), where V is a set of vertices and E is set of edges.
The set of vertices id partitioned into two types P= {p1,p2, …,pn}, the consisting of all the process in the system, and R= {r1, r2,…rm}, the set consisting of all resource type in the system.
Safe state
A safe state is one which it can be determined that the system ca allocate resources to each process( up to its maximum) in some order (for all pending requests )and still avoid deadlock. A safe state is not a deadlock state.
Unsafe state
A deadlock is an unsafe state. Not all unsafe states are deadlocks but an unsafe state may lead to a deadlock. As long as the state is safe, the operating system can avoid unsafe (deadlock) states. Process that are holding resources in an unsafe state may subsequently release them rather than ask for more; the system would transition from an unsafe state back into a safe state.
Describe safety algorithm.
Ans:
1. Let work and Finish be vectors of length m and n, respectively, Initialize Work: = Available and Finish [i] := false for i = 1,2,..,n.
2. Find an I such that :
a. Finish[i] = false, and
b. Needi ≤ Work
If no such i exists, go to step 4.
3. Work : = Work + Allocation,
Finish [i] : = true
Go to step 2.
4. If finish [i] = true for all i, then the system is in a safe state.
Unit: 04 Lesson: 04 : Deadlock Recovery
a) List the factors for choosing the process.
Ans: Many factors are related to determine which process is chosen:
i) Priority of the process.
ii) Computing time.
iii) Number and type of resources used by process.
iv) Number of extra resources for completion.
v) Number of process involved in the deadlock.
Comments
Post a Comment