How to be solve banker algorithm?example
I m providing you this from my college notes
Banker's Algorithm
* multiple instances of resource types IMPLIES cannot use resource-allocation graph
* banks do not allocate cash unless they can satisfy customer needs when a new process enters the system
* declare in advance maximum need for each resource type
* cannot exceed the total resources of that type
* later, processes make actual request for some resources
* if the the allocation leaves system in safe state grant the resources
* otherwise, suspend process until other processes release enough resources
Banker: Data Structures define MAXN 10 /* maximum number of processes */
#define MAXM 10 /* maximum number of resource types */
int Available[MAXM]; /* Available[j] = current # of unused resource j */
int Max[MAXN][MAXM]; /* Max[i][j] = max demand of i for resource j */
int Allocation[MAXN][MAXM]; /* Allocation[i][j] = i's current allocation of j*/
int Need[MAXN][MAXM]; /* Need[i][j] = i's potential for more j */
/* Need[i][j] = Max[i][j] - Allocation[i][j] */
Notation:
X <= Y iff X[i] <= Y[i] for all i
(0,3,2,1) is less than (1,7,3,2)
(1,7,3,2) is NOT less than (0,8,2,1)
Each row of Allocation and Need are vectors: Allocation_i and Need_i
Banker: Example
Initially:
Available
A B C
10 5 7
Later Snapshot:
Max - Allocation = Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 3 3 2
P1 3 2 2 2 0 0 1 2 2
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
Banker: Safety Algorithm
* consider some sequence of processes
* if the first process has Need less than Available
* it can run until done
* then release all of its allocated resources
* allocation is increased for next process
* if the second process has Need less than Available
* ...
* then all of the processes will be able to run eventually
* IMPLIES system is in a safe state
Banker: Safety Algorithm
STEP 1: initialize
Work := Available;
for i = 1,2,...,n
Finish[i] = false
STEP 2: find i such that both
a. Finish[i] is false
b. Need_i <= Work
if no such i, goto STEP 4
STEP 3:
Work := Work + Allocation_i
Finish[i] = true
goto STEP 2
STEP 4:
if Finish[i] = true for all i, system is in safe state
Banker: Safety Example
Using the previous example, P1,P3,P4,P2,P0 satisfies criteria.
Max - Allocation = Need <= Work Available
A B C A B C A B C A B C
P1 3 2 2 2 0 0 1 2 2 3 3 2 3 3 2
P3 2 2 2 2 1 1 0 1 1 5 3 2
P4 4 3 3 0 0 2 4 3 1 7 4 3
P2 9 0 2 3 0 2 6 0 0 7 4 5
P0 7 5 3 0 1 0 7 4 3 10 4 7
10 5 7<<< initial system
Banker: Resource-Request Algorithm
STEP 0: P_i makes Request_i for resources, say (1,0,2)
STEP 1: if Request_i <= Need_i
goto STEP 2
else ERROR
STEP 2: if Request_i <= Available
goto STEP 3
else suspend P_i
STEP 3: pretend to allocate requested resources
Available := Available - Request_i
Allocation_i := Allocation_i + Request_i;
Need_i := Need_i - Request_i
STEP 4: if pretend state is SAFE
then do a real allocation and P_i proceeds
else
restore the original state and suspend P_i
Banker: Resource-Request Algorithm [129]
Say P1 requests (1,0,2)
Compare to Need_1: (1,0,2) <= (1,2,2)
Compare to Available: (1,0,2) <= (3 3 2)
Pretend to allocate resources:
Max - Allocation = Need Available
A B C A B C A B C A B C
P0 7 5 3 0 1 0 7 4 3 2 3 0<<<
P1 3 2 2 3 0 2<<< 0 2 0<<<
P2 9 0 2 3 0 2 6 0 0
P3 2 2 2 2 1 1 0 1 1
P4 4 3 3 0 0 2 4 3 1
Is this safe? Yes: P1, P3, P4, P0, P2
Can P4 get (3,3,0)? No, (3,3,0) > (2,3,0) Available
Can P0 get (0,2,0)? (0,2,0) < (2,3,0) Available
Pretend: Available goes to (2,1,0)
Thanks And Regards
×