System model Necessary condition of Deadlock ?

System model Necessary condition of Deadlock  

  System Model:-

·  A  system consist of a finite number of resources to  be  distributed  among a  number of  competing processes.  The resources are portioned into several types.

·  The limited resource is divided into different parts , having different needs of  process.

·   Resource categories may include memory, printers,   CPU's, open files, tape drives, CD-ROM'S, etc.


    Sequence  of  process :-  Request , Use ,  Release

    Request -User does request  for required resource  by request  action. For example the system calls open( ) , malloc( ) , new(), and request( ).


     Use - The process uses the resource, e.g. prints to the printer or reads from the file.

    Release - The process relinquishes the resource. so that it becomes available for other processes. For example, close( ) , free( ), delete( ), and release( ).


Necessary  condition of deadlock

A deadlock situation can arise if the following four condition hold simultaneously in a system.

·       Mutual exclusion:-At least one resource must be held in a non-shareable 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.

System model, Necessary condition of Deadlock , condition for deadlock

·       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. In order to ensure that the hold & wait conditions never hold in the system we must guarantee that whenever a process requests a resource it does not hold any other resource.

·       No preemption:- Once a process is holding a resource , then that resource cannot be taken away from that process until the process voluntarily releases it.

System model, Necessary condition of Deadlock , condition for deadlock

·       Circular wait: - In order to ensure that the circular wait condition never holds we may impose a total ordering of all resource type. That is we assign to each resource type a unique integer number which allows us to compare and whether one precedes another in our ordering. A set of processes { P0, P1, P2, . . ., Pn } must exist such that every P(i)      is waiting for a resource Ri , which is held by process P(i+1). Since process P(i+1) is holding resource Ri while requesting R(i+1) then the condition will be [ F(Ri)<F(Ri+1) ] for all values of i.

Resource allocation graph

Deadlock can also be understood 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 edge E. The  set of vertices V divided into two different types of  nodes:

P ={P1,P2 - - - - Pn } - the set consisting of all the active processes in the      system and

R ={R1-- - - - - -Rn} – the set consisting of a resource type in the system.


·   Request edge :- Define that Pi  request  an  instance  resource type  Rj and  is  currently waiting for  that  resource.   Pi → Rj

·   Assignment edge :- An instance of resource Rj  is allocated to process Pi. In  a resource allocation graph we represent.  Rj → Pi

In resource allocation graph :

1. Process is represented by a Circle.

2. Resource is represented by a Rectangle.

3. Instance  is represented by a def. within the rectangle.


Note that a request edge can be converted into an assignment edge by reversing the direction of the arc when the request is granted.

1.  If a resource-allocation graph contains no cycles, then the system is not deadlocked. ( When looking for cycles, remember that these are directed graphs. )

Method for handling deadlocks :-

·       Generally speaking there are three ways of handling deadlocks:

1.     Deadlock prevention or avoidance - Do not allow the system to get into a deadlocked state.

2.     Deadlock detection and recovery - Abort a process or preempt some resources when deadlocks are detected.

3.     Ignore the problem all together - If deadlocks only occur once a year or so, it may be better to simply let them happen and reboot as necessary than to incur the constant overhead and system performance penalties associated with deadlock prevention or detection. This is the approach that both Windows and UNIX take.

·       In order to avoid deadlocks, the system must have additional information about all processes. In particular, the system must know what resources a process will or may request in the future. ( Ranging from a simple worst-case maximum to a complete resource request and release plan for each process, depending on the particular algorithm. )


·    Deadlock detection is fairly straightforward, but deadlock recovery requires either aborting processes or preempting resources, neither of which is an attractive alternative.

·    If deadlocks are neither prevented nor detected, then when a deadlock occurs the system will gradually slow down, as more and more processes become stuck waiting for resources currently held by the deadlock and by other waiting processes. Unfortunately this slowdown can be indistinguishable from a general system slowdown when a real-time process has heavy computing needs.

Post a Comment