Dead Lock, Resource Allocation Graph & Safe State [PART 1]

Dead Lock

Dead lock is a situation where no process can continue due non availability of resources.

Resource allocation graph

R1 &R2  are non sharable resources

Here P1 needs R1 &R2 at the same time.But  since R2 is assigned to P2  is not possible.

Here P2 needs R1 &R2 at the same time. But  since R1 is assigned to P1 it  is not possible

So  circular wait and  hence deadlock occurs.

Resource allocation graph without dead lock

Conditions for deadlock

·        Deadlock happens if following 4 conditions occur simultanesoly

1.No mutual exclusion

2.Hold and wait

3.No preemptopn

4.circular wait

Dead lock handling

1.Dead lock prevention

      2. Dead Lock Detection

      3.Dead lock Avoidance

       4,Recovery from dead lock

Dead lock prevention

Avoid all the 4 conditions(at least one) above mentioned

.Mutual exclusion :Mutual exclusion must hold for sharable(if there is problem if accessed) resources.

Eg:Printer (a printer) can not be shared while printing a particular document.(jobs are spooled here)

Read only files (intrinsically non-sharable means data can’t be written) can be shared without any problem.

Hold and wait

 To avoid it

1.      When process  request  one  resource ,it does not hold any other resource ( to implement it all process request all other resources  before starting execution)

Eg:requests dvd,h.disk and printer(then it does not request for further resources)

Copies files from DVD to Disk,then prints,hods printer until last.

2.      An alternate protocol allows a process to request resources only when it has none.(tempraily release the present ones,and again request)

Eg  Requests dvd  and Disk ,uses (reads) DVD,releases DVD and H disk.

      Requests H disk and printer disk file is copied to printer.

No Preemption

To avoid it

1st method

·       If a process holding some resources and requests another resource that can be immediately allocated  the process must wait.

·       Then releases all the resources and these resources are added

to the list of  resources for which the process is waiting

·       The process will be restarted  only when it regains its old resources as well as new ones that it is requesting.

  2^nd method

·       If a process requests some resources, check whether they are available ,if  available  allocate them

·       If they are not available check whether they are allocated to some other process that is waiting for additional resources , preempt the allocated resources  from the process waiting for additional resources and allocate them to requesting process.

·       If resources are neither available nor held by a waiting process

The requesting process must wait.(At this time it’s resources  can be  preempted( since it is waiting)  ,if another process request them)

·       A process can be restarted only when it is allocated the new resources it is requesting and recovers any resources that were preempted  while it was waiting.

Circular  Wait

  To avoid it

·       Assign a resource or resource type a number; F:R->N

N is natural nos

Eg.

R1=1

R2=2

·       Each process can request any number of  a resource type  say  Ri

After that the process can request  instances of resource type

If F[Rj] >F[Ri].

Eg:

     1.P1 requests R1

 2. Then holds it .

3.Then p1 requests for R2 (it’s ok since F(R2)=2  >F(R1)=1)

      1.P2 requests R2

Then holds it .

3.Then p2 requests for R1 (it’s not ok since F(R1)=1  is not  >F(R2))

So circular wait will not occur.(p2….>R1 not possible)

Dead lock avoidance

·       In general, request  restrictions employed in deadlock prevention methods  leads poor device resource utilization. And leads to less through put.

·       If we  have the information how additional resources are going to be requested and released, if situation permits we can avoid  deadlock keeping the resource utilization  as maximum as possible.

For eg

 If  process p1 needs tape drive  and then one printer

 If  process p2 needs one printer(released in time for p1) then tape drive(by that time tape drive should be released by p1)

We can avoid dead lock.

Safe state

 A state is said to be safe the system can allocate resources to each process  in some order and still avoid a deadlock.