The Resource Request Algorithm

Test 3, the safety algorithm on the pretended state:

Everybody finishes, so the state is safe and the request is granted. A safe sequence is P1, P3, P0, P2, P4.

Request two: P4 asks for 3 3 0, and waits because nothing is available

This is asked in the state after request one, where Available is 2 3 0.

Test 1. Request 3 3 0 against P4's Need of 4 3 1: within its maximum.

Test 2. Request 3 3 0 against Available 2 3 0: 3 is more than 2 in resource A. So the resources are not there and P4 waits.

The safety algorithm is never reached. There is nothing to test: you cannot give away what you do not have.

Request three: P0 asks for 0 2 0, and waits although the resources are free

Also in the state after request one, where Available is 2 3 0.

Test 1. Request 0 2 0 against P0's Need of 7 4 3: within its maximum.

Test 2. Request 0 2 0 against Available 2 3 0: 0 is at most 2, 2 is at most 3, 0 is at most 0. Everything asked for is available.

Pretend to grant it. Available becomes 2 1 0. P0's Allocation becomes 0 3 0, and P0's Need becomes 7 2 3.

Test 3, the safety algorithm:

No process can finish, so the state is unsafe, the pretended grant is undone, and P0 waits.

Read that again: two units of B were sitting there unheld and P0 was refused them. Nothing was wrong, nobody was deadlocked, and the request was legal. It was refused because after granting it there would have been no order at all in which the five processes could be finished, and from that point a perfectly legal sequence of later requests would have deadlocked the system.

That is the banker's algorithm doing the only thing it does, and it is the answer to "what is the disadvantage of deadlock avoidance": resources go unused and processes wait when they need not have, because the guarantee is worth more than the utilisation.

And a fourth: P0 asks for 8 0 0

Test 1. Request 8 0 0 against P0's Need of 7 4 3: 8 is more than 7. P0 has asked for more than it declared it would ever need.

This is an error and not a wait. The process broke the declaration the whole algorithm rests on, so nothing can be guaranteed about it and the system raises an error. A student who answers "it waits" has missed the point of test 1.

The three outcomes, side by side

What it does not mean

A refusal is not a deadlock. The process waits, and it will be granted the request later, when somebody releases something and the state can take it.

The pretended grant is not a grant. If the safety test fails, every one of the three lines in step 3 is undone. A question that asks for the state after a refused request wants the original state.

Test 2 failing does not mean the system is short of resources overall. It means they are held right now.

The algorithm does not choose which process to serve. It answers yes or no to one request. Which waiting process is tried next is a scheduling decision outside it.

Quick revision

• Request[i] is what process i wants now. Three tests, in order.
• Test 1: Request greater than Need is an error: the process exceeded its declared

maximum.

• Test 2: Request greater than Available means it waits: the resources are not there.
• Test 3: pretend to grant it, with Available minus Request, Allocation plus Request

and Need minus Request, then run the safety algorithm. Unsafe means undo it and wait.

• Granting reduces Need as well as raising Allocation. Forgetting that makes every later

check wrong.

• Worked on the standard state: P1 asking 1 0 2 is granted; P4 asking 3 3 0 waits because A is

short; P0 asking 0 2 0 waits although both units of B are free, because the resulting state is unsafe; P0 asking 8 0 0 is an error.

• The third case is the whole point of avoidance, and the lost utilisation is what the guarantee

costs.

Test yourself

1. State the three tests of the resource request algorithm. Request greater than Need is an

error; Request greater than Available means the process waits; otherwise pretend to grant it and run the safety algorithm, granting only if the resulting state is safe.

1. What three quantities change when a request is pretended? Available falls by the request,

the process's Allocation rises by it, and the process's Need falls by it.

1. What happens if a process asks for more than its declared maximum? It is an error, not a

wait: the process has broken the declaration the algorithm depends on and is reported or killed.

1. P0 asks for 0 2 0, two units of B are free, and the request is refused. Why? Because after

granting it no process's Need would be within the remaining Available, so no order could finish them all: the state would be unsafe, and a legal sequence of later requests could then deadlock the system.

1. What is the state after a request is refused by the safety test? Exactly what it was

before. The pretended grant is undone in all three quantities.

1. When is the safety algorithm not run at all? When test 1 or test 2 fails: an error needs

no safety check, and resources that are not available cannot be granted.

1. What is the disadvantage of avoidance that this chapter demonstrates? Resources sit unused

and processes wait when they need not have. The guarantee is paid for in utilisation.