Detailed
COS3721
Summary
,Note: This document contains detailed explanations on
each section followed by worked out exam questions.
Banker’s
algorithm
Know how to explain the steps of these two algorithms:
Explanation:
, 1. Create Work and Finish vectors. Initialize all Finish entries to false and Work to
Available. The Finish table represents processes that have finished executed.
2. Search for processes that needs fewer resources than those available. (i.e. Need
<=Work). If there is no such process, go to step 4, else go to step 3.
3. For each process found in step 2 update the Work by adding current Work to the
process’ Allocation. Set Finish entry of the process to true. Go to step 2.
4. If the whole Finish vector has true entries then system is in a safe state.
Explanation
1. Check if request is smaller or equal than the Need vector of the specified process
(say process i). If it is go to step 2, otherwise the request cannot be granted
immediately.
2. Check if request is smaller or equal than the Available vector of the process i. If it is
go to step 3, otherwise the request cannot be granted immediately.
Think: I need you to be available
3. Then have the system pretend to have allocated the requested resources to process i
by modifying the following of this process:
-Update Available by subtracting it with request
-Update Allocation by adding the request to it
-Update the Need by subtracting request from it THINK AAN -+-
Then use this resulting resource-allocation state with the banker’s algorithm to
check if it is in a safe state. If it is, then the resources can be granted immediately. If
it isn’t then resources can’t be granted immediately.
,Exams
2019-06 Question
3.1)
Need = Max – Allocation
Need
A B C D
P0 2 2 1 1
P1 2 1 3 1
, P2 0 2 1 3
P3 0 1 1 2
P4 2 2 3 3
3.2)
Need
A B C D
P0 2 2 1 1
P1 2 1 3 1
P2 0 2 1 3
P3 0 1 1 2
P4 2 2 3 3
Work = Available = (3,3,2,1)
Finish = (0,0,0,0,0)
Search for processes that needs fewer resources than those available. (i.e. Need <=Work)
P0:
Can execute since Need <= Available. Assume it completed its execution:
Finish = (1,0,0,0,0).
Work = Allocation(P0) + work (previous work)
=2001+3321
Work = 5 3 2 2
P1:
Cannot execute since Need(P1) <= Work is false
P2:
Cannot execute since Need(P2) <= Work is false
P3:
Can execute since Need(P3) <= Work. Assume it completed its execution:
Finish = (1, 0, 0, 1, 0)
Work
6634 <- Previous Work + Allocation(P3)
P4:
Can execute since Need(P4) <= Work. Assume it completed its execution:
Finish = (1, 0, 0, 1, 1)
,Work
7 10 6 6 <- Previous Work + Allocation(P4)
Now we start from the top again seeing if the other processes can execute:
P1:
Can execute since Need <= Work. Assume it completed its execution:
Finish= (1, 1, 0, 1, 1)
Work
10 11 8 7
P2:
Can execute occur since Need <= Work. Assume it completed its execution:
Finish = (1, 1, 1, 1, 1)
Work
12 12 8 10
System is in a safe state since everything in Finish is T.
The safe sequence: <P0, P3, P4, P1, P2>
3.3)
Check request <= P4’s Need.
(0,0,2,0) <= (2,2,3,3) is true.
Next we check that request <= Available
(0,0,2,0) <= (3,3,2,1) is true.
If these are not true then request cannot be granter immediately.
When these 2 tests past we pretend request has been fulfilled which will result in the following
state.( Thus REQUEST + ALLOCATION & NEED – REQUEST of P4 (next 1 that hasn’t have AVAILABLE).
AND you go AVAILABLE – REQUEST.)
,Now determine if this system state is in safe state:
P0:
Available = Work = (3, 3, 0, 1)
Cannot execute since Need <= Work is false (i.e. 2 2 1 1 <= 3 3 0 1 is false)
P1:
Cannot execute since Need <= Work is false (i.e. 2 2 1 1 <= 3 3 0 1 is false)
P2:
Cannot execute since Need <= Work is false (i.e. 0 2 1 3 <= 3 3 0 1 is false)
Both P3 and P4 Cannot execute since Need <= Work because C’s work value is 0 and it is less than
both P3’s and P4’s Need C values.
Resources can’t be granted immediately, since system is not in a safe state. P4 will have to wait.
2018-10 Question:
,4.1)
Need = Max – Allocation
4.2)
1. Check if request is smaller or equal than the Need vector of the specified process
(say process i). If it is go to step 2, otherwise the request cannot be granted
immediately.
2. Check if request is smaller or equal than the Available vector of the process i. If it is
go to step 3, otherwise the request cannot be granted immediately.
3. Then have the system pretend to have allocated the requested resources to process i
by modifying the following of this process:
i. -Update Available by subtracting it with request
ii. -Update Allocation by adding the request to it
iii. -Update the Need by subtracting request from it
THINK AAN -+-
Then use this resulting resource-allocation state with the banker’s algorithm to
check if it is in a safe state. If it is, then the resources can be granted immediately. If
it isn’t then resources can’t be granted immediately.
,4.3)
Request <= Need(P3) is true. i.e. (0, 2, 0, 1) <= (2, 4, 0, 2) is true
Request <= Available is true, i.e. (0, 2, 0, 1) <= (5, 2, 2, 3) is true.
Pretend to have the allocated the request resource to process P3. Thus the resulting
resource allocation state would be as follows:
Now apply Banker’s algorithm to see if this system is in a safe state.
Work = Available = (5, 0, 2, 1)
Finish= (0, 0, 0, 0, 0)
Search for processes that needs fewer resources than those available. (i.e. Need <=Work)
P0:
Cannot execute since Need <= work is false, i.e. (2, 1, 0 ,3) <= (5, 0 ,2, 1) is false
P1:
Can execute since Need <= work
Work = Work + Allocation
= (5,0,2,1) + (2,2,1,0) = (7,2,3,1)
P2:
Can execute since Need <= work
Work = (10, 3, 5, 2)
P3:
Cannot execute since Need <= work is false.
Now we start from the top again seeing if the other processes can execute:
P0:
Cannot execute since Need <= work is false.
P3:
, Cannot execute since we have not added to the work, thus Need <= work will still be false.
Thus, we will never reach a safe state which means that the resource won’t be able to be
allocated immediately. P3 needs to wait for the request.
2018-06 Question:
5.1)
Need = Max - Allocation
Need
A B C D
P0 2 1 0 3
P1 1 0 0 1
P2 0 2 0 0
P3 4 1 0 2
5.2)
Work = Available = (5,2,2,3)
Finish= (0,0,0,0)
Search for processes that needs fewer resources than those available:
P0:
Can execute since Need<=Work, i.e. (2,1,0,3) <= (5,2,2,3)
Work = Work + Allocation = (5,2,2,3) + (3,0,1,4) = (8,2,3,7)
Finish= (1,0,0,0)
P1:
Can execute since Need<=Work
COS3721
Summary
,Note: This document contains detailed explanations on
each section followed by worked out exam questions.
Banker’s
algorithm
Know how to explain the steps of these two algorithms:
Explanation:
, 1. Create Work and Finish vectors. Initialize all Finish entries to false and Work to
Available. The Finish table represents processes that have finished executed.
2. Search for processes that needs fewer resources than those available. (i.e. Need
<=Work). If there is no such process, go to step 4, else go to step 3.
3. For each process found in step 2 update the Work by adding current Work to the
process’ Allocation. Set Finish entry of the process to true. Go to step 2.
4. If the whole Finish vector has true entries then system is in a safe state.
Explanation
1. Check if request is smaller or equal than the Need vector of the specified process
(say process i). If it is go to step 2, otherwise the request cannot be granted
immediately.
2. Check if request is smaller or equal than the Available vector of the process i. If it is
go to step 3, otherwise the request cannot be granted immediately.
Think: I need you to be available
3. Then have the system pretend to have allocated the requested resources to process i
by modifying the following of this process:
-Update Available by subtracting it with request
-Update Allocation by adding the request to it
-Update the Need by subtracting request from it THINK AAN -+-
Then use this resulting resource-allocation state with the banker’s algorithm to
check if it is in a safe state. If it is, then the resources can be granted immediately. If
it isn’t then resources can’t be granted immediately.
,Exams
2019-06 Question
3.1)
Need = Max – Allocation
Need
A B C D
P0 2 2 1 1
P1 2 1 3 1
, P2 0 2 1 3
P3 0 1 1 2
P4 2 2 3 3
3.2)
Need
A B C D
P0 2 2 1 1
P1 2 1 3 1
P2 0 2 1 3
P3 0 1 1 2
P4 2 2 3 3
Work = Available = (3,3,2,1)
Finish = (0,0,0,0,0)
Search for processes that needs fewer resources than those available. (i.e. Need <=Work)
P0:
Can execute since Need <= Available. Assume it completed its execution:
Finish = (1,0,0,0,0).
Work = Allocation(P0) + work (previous work)
=2001+3321
Work = 5 3 2 2
P1:
Cannot execute since Need(P1) <= Work is false
P2:
Cannot execute since Need(P2) <= Work is false
P3:
Can execute since Need(P3) <= Work. Assume it completed its execution:
Finish = (1, 0, 0, 1, 0)
Work
6634 <- Previous Work + Allocation(P3)
P4:
Can execute since Need(P4) <= Work. Assume it completed its execution:
Finish = (1, 0, 0, 1, 1)
,Work
7 10 6 6 <- Previous Work + Allocation(P4)
Now we start from the top again seeing if the other processes can execute:
P1:
Can execute since Need <= Work. Assume it completed its execution:
Finish= (1, 1, 0, 1, 1)
Work
10 11 8 7
P2:
Can execute occur since Need <= Work. Assume it completed its execution:
Finish = (1, 1, 1, 1, 1)
Work
12 12 8 10
System is in a safe state since everything in Finish is T.
The safe sequence: <P0, P3, P4, P1, P2>
3.3)
Check request <= P4’s Need.
(0,0,2,0) <= (2,2,3,3) is true.
Next we check that request <= Available
(0,0,2,0) <= (3,3,2,1) is true.
If these are not true then request cannot be granter immediately.
When these 2 tests past we pretend request has been fulfilled which will result in the following
state.( Thus REQUEST + ALLOCATION & NEED – REQUEST of P4 (next 1 that hasn’t have AVAILABLE).
AND you go AVAILABLE – REQUEST.)
,Now determine if this system state is in safe state:
P0:
Available = Work = (3, 3, 0, 1)
Cannot execute since Need <= Work is false (i.e. 2 2 1 1 <= 3 3 0 1 is false)
P1:
Cannot execute since Need <= Work is false (i.e. 2 2 1 1 <= 3 3 0 1 is false)
P2:
Cannot execute since Need <= Work is false (i.e. 0 2 1 3 <= 3 3 0 1 is false)
Both P3 and P4 Cannot execute since Need <= Work because C’s work value is 0 and it is less than
both P3’s and P4’s Need C values.
Resources can’t be granted immediately, since system is not in a safe state. P4 will have to wait.
2018-10 Question:
,4.1)
Need = Max – Allocation
4.2)
1. Check if request is smaller or equal than the Need vector of the specified process
(say process i). If it is go to step 2, otherwise the request cannot be granted
immediately.
2. Check if request is smaller or equal than the Available vector of the process i. If it is
go to step 3, otherwise the request cannot be granted immediately.
3. Then have the system pretend to have allocated the requested resources to process i
by modifying the following of this process:
i. -Update Available by subtracting it with request
ii. -Update Allocation by adding the request to it
iii. -Update the Need by subtracting request from it
THINK AAN -+-
Then use this resulting resource-allocation state with the banker’s algorithm to
check if it is in a safe state. If it is, then the resources can be granted immediately. If
it isn’t then resources can’t be granted immediately.
,4.3)
Request <= Need(P3) is true. i.e. (0, 2, 0, 1) <= (2, 4, 0, 2) is true
Request <= Available is true, i.e. (0, 2, 0, 1) <= (5, 2, 2, 3) is true.
Pretend to have the allocated the request resource to process P3. Thus the resulting
resource allocation state would be as follows:
Now apply Banker’s algorithm to see if this system is in a safe state.
Work = Available = (5, 0, 2, 1)
Finish= (0, 0, 0, 0, 0)
Search for processes that needs fewer resources than those available. (i.e. Need <=Work)
P0:
Cannot execute since Need <= work is false, i.e. (2, 1, 0 ,3) <= (5, 0 ,2, 1) is false
P1:
Can execute since Need <= work
Work = Work + Allocation
= (5,0,2,1) + (2,2,1,0) = (7,2,3,1)
P2:
Can execute since Need <= work
Work = (10, 3, 5, 2)
P3:
Cannot execute since Need <= work is false.
Now we start from the top again seeing if the other processes can execute:
P0:
Cannot execute since Need <= work is false.
P3:
, Cannot execute since we have not added to the work, thus Need <= work will still be false.
Thus, we will never reach a safe state which means that the resource won’t be able to be
allocated immediately. P3 needs to wait for the request.
2018-06 Question:
5.1)
Need = Max - Allocation
Need
A B C D
P0 2 1 0 3
P1 1 0 0 1
P2 0 2 0 0
P3 4 1 0 2
5.2)
Work = Available = (5,2,2,3)
Finish= (0,0,0,0)
Search for processes that needs fewer resources than those available:
P0:
Can execute since Need<=Work, i.e. (2,1,0,3) <= (5,2,2,3)
Work = Work + Allocation = (5,2,2,3) + (3,0,1,4) = (8,2,3,7)
Finish= (1,0,0,0)
P1:
Can execute since Need<=Work
