Get Even More Visitors To Your Blog, Upgrade To A Business Listing >>

Operating Systems – Deadlock Prevention with Banker’s Algorithm

In this article, you will learn about deadlock prevention method – Banker’s algorithm and Resource allocation graph. You will also learn about 4 conditions for deadlock.

Let’s start with Resource allocation graph.

Resource Allocation graph describe the deadlock more precisely. It has set of vertices V and set of edges E.

Vertices types

Vertices are divided into

P = {P1, P2, P3, . . . , Pn} set of active processes in the system.

R = { R1, R2, R3, …, Rm} set of vertices that represent the resources.

Edge types

Pi -> Rj means Pi has requested resource Ri and waiting for it is called request edge

Rj -> Pi means that the instance of resource Ri is allocated to process Pi called the assignment edge.

Resource Rj may have more than one instance.

Example: R1 R3

R2 R4

Vertices

P = {P1, P2, P3}

R = {R1, R2, R3, R4}

Instances of Resource

R1 = 1

R2 = 2

R3 = 1

R4 = 0

Edges

Request Edges: P1 -> R1, P2 -> R3

Assignment Edges: R1 -> P2, R3 -> P3, R2 -> P1, R2 -> P2

R2 -> P1 -> R1 -> P2 -> R3 -> P3 (No Cycle)

R2 -> P2 -> R3 -> P3 (No Cycle)

*A CYCLE IN THE GRAPH IS BOTH A NECESSARY but not a SUFFICIENT CONDITION FOR A DEADLOCK.

* CYCLE INVOLVE A SET OF RESOURCES WHERE EACH RESOURCE HAS ONLY ONE INSTANCE.

THEN DEADLOCK OCCURS.

R1 R3

R2 R4

P1 -> R1 -> P2 -> R3 -> P3 -> R2 -> P1 (Cycle from P1-to-P1)

P2 -> R3 -> P3 -> R2 -> P2 (Cycle from P2 –to-P2)

Methods for handling deadlock

  1. First method is to prevent deadlock
  2. Second method is to deadlock avoidance by managing system resources. This is done by giving additional information about process request and whether that request can be satisfied.
  3. Another way is to let deadlock occur and place an algorithm that recover the system from deadlock.
  4. If no algorithm as available for recovery, then the system must be restarted manually.

Deadlock Prevention

There are 4 conditions that must hold for deadlock to occur and if we prevent anyone of them from occurring then there is no deadlock.

Mutual exclusion

Non sharable resource must give mutual-exclusive right to access it for any process. Sharable resource such read-only file has no problem sharing the resource and does not need mutual-exclusive rights.

Mutual exclusive rights does not have affect on deadlock prevention.

Hold and Wait

There are two ways this can be done.

  1. First allocate all the resource to system before it executes.
  2. Second way, process can be allocated resource only when it has none and if it requires additional resource, leave the existing one.

Example:

Suppose a process copies files from DVD and then sorts them and print the result.

DVD player/writer, disk drive and printer must be allocated at the beginning itself using first approach.

In second approach, first DVD drive the given and when process finished with the DVD drive and reads all the information, it releases the DVD drive.

Next Disk drive is allocated before copying the files to the disk drive and when task is over it is released. Similarly, printer does the printing for process and process release the printer.

No Preemption

If a process fails to get all the resource it need, then it must release resource it is already holding.

It will only start when all the resources including the new one is available.

If a process is available, allocate them otherwise check if it is held by some waiting process, if yes then preempt the waiting process and allocate to the requesting process.

This technique cannot be applied to I/O devices.

Circular Wait

Allocate resource in an increasing order of enumeration. R = {R1, R2 … Rn}. Each process gets a number. We can say that there is a one-to-one function from resource to natural number.

F: R -> N, where N is set of natural numbers.

Suppose there are three resources

F (tape drive) = 1

F (disk drive) = 4

F (printer) = 10

First Process can request for any number of instance of the resource Ri and after that the process can request instance of resource Rj if and only if F (Rj) > F (Ri).

Deadlock Avoidance

Deadlock avoidance depends on additional information about how request should be requested. The system can then make decisions based on currently available resource, resource allocated to each process and future request & release of each process.

Each process must give prior information on maximum resource of each type it needs. The system then uses deadlock-avoidance algorithms and checks the resource allocation state to check that a circular wait never occur.

Safe State

A state is safe if the system can allocate resource to each process and still (to its maximum) in some order and still avoid deadlock. There exists a safe sequence.

Suppose there is sequence of processes P = {P1, P2, P3, … Pn} is a safe sequence for current allocation state if for each process, Pi request for resource can be satisfied by currently available resources plus resources held by Pj, where j

If the resource for Pi is not available, then it must wait till all Pj have finished. Once resource is obtained Pi can execute and terminate and release all the resources.

Then Pi+1th process compete for the resources and so on. If such a safe state does not exist then system is said to be in unsafe state.

Unsafe state does not mean a deadlock state but it may lead to a deadlock state.

Deadlock-avoidance algorithm makes sure that resource is allocated to process only when it leaves the system in safe state. Otherwise it has to wait.

Resource-Allocation-Graph Algorithm

A new edge is introduced in the resource allocation graph called the Claim edge. Pi -> Rj means that it is a claim edge and shown as a dashed line in resource allocation graph.

A claim edge shows “Future requests” or “Future Assignments” and converted to request edge and assignment edge respectively.

The request is granted only if converting request edge to a assignment edge does not lead to formation of a cycle in the graph, if allocation to Pi will form a cycle that will lead the system to an unsafe state, then the process Pi must wait till the resource is available.

Example:

P = {P1, P2}

R = {R1, R2}

CLAIM EDGE CONVERT TO REQUEST EDGE CONVERT TO ASSIGNMENT EDGE
P1 -> R1 YES YES
P2 -> R2 YES YES
P1 -> R2 NO ( Make a cycle) NO
P2 -> R1 YES NO (P1 using R1)

R1 R1 R1

R2 R2

Banker’s Algorithm

The algorithm works like a bank hence the name. Any new process must declare the maximum number of instance of each resource type that it need. It must not exceed the total resource.

Before allocating the system must make sure that after allocation it is not leaving the system in unsafe state.

The data structures used in bankers algorithm where n is number of process and m is the number of resource types is as follows,

  1. Available – number of available resource of each type of length m. Available[j] = k means k instance of resource Rj.
  2. Max – It is n x m matrix for maximum number instance of resources required by the process. Max[i][j] = k means Pi process requires k instance of resource Rj.
  3. Allocation – it is also n x m matrix for number of resources of each type allocated to each process. Allocation [i] [j] = k means process Pi is allocated k instances of resources of Rj.
  4. Need – it is n x m matrix that remaining need for each process. Need[i] [k] = k means that the process Pi need k instance of resource type Rj to finish it’s tasks.

Need[i] [j] = Max[i] [j] – Allocation[i] [j]

Banker’s Algorithm Procedure

If X and Y are two vectors, then X

Conversely, Y

Allocation (i) means resource currently allocated to process Pi and need (i) means additional resource required by process Pi.

Safety Algorithm

  1. Let Work and Finish be two vectors of length m and n respectively. Initialize Work = Available and Finish[i] = false for I = 0, 1, 2, . . . , n-1.
  2. Find an index ‘i’ such that
  3. Finish[i] = false
  4. Need(i)

If no such ‘i’ exists then go to step 4.

  1. Work = Work + Allocation (i)

Finish[i] = true

Go to step 2

  1. If Finish[i] = true for all i then the system is in safe state.

Order of the above algorithm is O (mn2).

Resource-Request Algorithm

This algorithm determines whether the request can be safely granted.

Request (i) is a request vector for process Pi. If Request (i) [j] = k, then process Pi wants k instance of resource R[j]. When a request for resource is made, following action take place

  1. If Request (i) ≤ Need (i), go to step 2, otherwise raise error because process has exceeded its maximum claim.
  2. If Request (i) ≤ Available, go to step 3. Otherwise Pi must wait, since the resources are not available.
  3. Let system pretend that it has allocated the resources to Pi as follows

Available = Available – Request (i)

Allocation (i) = Allocation (i) + Request (i)

Need (i) = Need (i) – Request (i)

If the resulting resource-allocation state is in safe state, the transaction is completed and process Pi gets the resource. If not then Pi must wait and old resource-allocation state is restored.

Example:

P = {P0, P1, P2, P3, P4}

R = {A, B, C}

Instances of Resources

A = 10, B = 5, C = 7

At t0 time following snapshot of system is captured.

Allocation Maximum Available
A B C A B C A B C
P0 0 1 0 7 5 3 7 5 5
P1 2 0 0 3 2 2 5 3 2
P2 3 0 2 9 0 2 10 5 7
P3 2 1 1 2 2 2 7 4 3
P4 0 0 2 4 3 3 7 4 5

We know that Need (i) = Max (i) – Allocation (i)

NEED Matrix
A B C
P0 7 4 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1

Check if the System is in Safe State

Iteration 1

Step 1: Need (i)

Need (0) > Available => (7, 4, 3) > (3, 3, 2)

Need (1) (1, 2, 2)

Step 2: Work = Work + Allocation (i)

Work = (3, 3, 2) + (2, 0, 0) = (5, 3, 2)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1}

Iteration 2

Step 1: Need (i)

Need (2) > Available => (6, 0, 0) > (5, 3, 2)

Need (3) (0, 1, 1)

Step 2: Work = Work + Allocation (i)

Work = (5, 3, 2) + (2, 1, 1) = (7, 4, 3)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3}

Iteration 3

Step 1: Need (i)

Need (4) (4, 3, 1)

Step 2: Work = Work + Allocation (i)

Work = (7, 4, 3) + (0, 0, 2) = (7, 4, 5)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4}

Iteration 4

Step 1: Need (i)

Need (0) (7, 4, 3)

Step 2: Work = Work + Allocation (i)

Work = (7, 4, 5) + (0, 1, 0) = (7, 5, 5)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4, P0}

Iteration 4

Step 1: Need (i)

Need (2) (6, 0, 0)

Step 2: Work = Work + Allocation (i)

Work = (7, 5, 5) + (3, 0, 2) = (10, 5, 7)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4, P0, P2}

Handling a Request

Suppose process P1 requested resource (1, 0, 2) which is less than the available resources (3, 3, 2).

Request (i) (1, 0, 2)

The system will pretend that the resource is allocated successfully, but will run the Safety Algorithm demonstrated above and verify if whether allocation to Pi will leave the system in UNSAFE state.

Example:

Suppose P0 requested for (0, 2, 0), then we find that Request (0) . Adjust the following

Available= Available – Request;;

Allocation; =Allocation +Request;;

Need; =Need- Request;

Allocation Maximum Available
A B C A B C A B C
P0 0 3 0 7 5 3 3,7 1,5 2,5
P1 2 0 0 3 2 2 5 1 2
P2 3 0 2 9 0 2
P3 2 1 1 2 2 2 7 2 3
P4 0 0 2 4 3 3 7 2 5

We then run the Safety Algorithm

NEED Matrix
A B C
P0 7 2 3
P1 1 2 2
P2 6 0 0
P3 0 1 1
P4 4 3 1

Iteration 2

Step 1: Need (i)

Need (2) > Available => (6, 0, 0) > (5, 1, 2)

Need (3) (0, 1, 1)

Step 2: Work = Work + Allocation (i)

Work = (5, 1, 2) + (2, 1, 1) = (7, 2, 3)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3}

Iteration 1

Step 1: Need (i)

Need (0) > Available => (7, 2, 3) > (3, 1, 2)

Need (1) (1, 2, 2)

Step 2: Work = Work + Allocation (i)

Work = (3, 1, 2) + (2, 0, 0) = (5, 1, 2)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1}

Iteration 3

Step 1: Need (i)

Need (4) > Available => (4, 3, 1)

Step 2: Work = Work + Allocation (i)

Step 3: Add P1 to Safety Sequence

Safety sequence = {P1, P3, P4 = not safe}

The post Operating Systems – Deadlock Prevention with Banker’s Algorithm appeared first on NotesForMSc.



This post first appeared on Notesformsc, please read the originial post: here

Share the post

Operating Systems – Deadlock Prevention with Banker’s Algorithm

×

Subscribe to Notesformsc

Get updates delivered right to your inbox!

Thank you for your subscription

×