----------------------------------------------------------------------
Assignment 7
Sample solution
----------------------------------------------------------------------
--9.1--
Given:
total = A B C D alloc = A B C D max = A B C D
3 14 12 12 P 0 0 1 2 P 0 0 1 2
Q 1 0 0 0 Q 1 7 5 0
R 1 3 5 4 R 2 3 5 6
S 0 6 3 2 S 0 6 5 2
T 0 0 1 4 T 0 6 5 6
The column-wise sum of 'alloc' shows how many instances of each
resource type are currently allocated. Subtracting this from the
'total' tuple is the amount of currently available resource instances
by resource type.
avail
=
total - sum { alloc X | X is a process }
=
A B C D
1 5 2 0
Subtraction of the currently allocated resources from the maximum
demand matrix gives the amount of resources a process may require to
perform its task.
need
=
max - alloc
=
A B C D
P 0 0 0 0
Q 0 7 5 0
R 1 0 0 2
S 0 0 2 0
T 0 6 4 2
Now we run the Banker's Algorithm.
finish[P,Q,R,S,T] := [False,False,False,False,False]
work := avail = A B C D
1 5 2 0
This is sufficient to finish process P, since
work <= need P = A B C D
0 0 0 0
hence we proceed with
finish[P] := True
work := work + alloc P = A B C D
1 5 3 2
This is sufficient to finish process R, since
work <= need R = A B C D
1 0 0 2
hence we proceed with
finish[R] := True
work := work + alloc R = A B C D
2 8 8 6
and with abbreviated notation we continue as follows
value of work:
A B C D
2 8 8 6 -- sufficient to finish Q
3 8 8 6 -- sufficient to finish S
3 14 11 8 -- sufficient to finish T
3 14 12 12 -- all processes finished
The system is in a safe state: A safe sequence is (P,R,Q,S,T).
--9.2--
Process Q issues the request
req = A B C D
0 4 2 0
This is within the limits specified by 'max', since
req <= need Q = A B C D
0 7 5 0
and the requested resources are available, since
req <= avail = A B C D
1 5 2 0
So we continue pretending that the request was granted, checking for
a safe state:
avail' := avail - req = A B C D
1 1 0 0
need' Q := need Q - req = A B C D
0 3 3 0
alloc' Q := alloc Q + req = A B C D
1 4 2 0
leading to the matrices
need' = A B C D alloc' = A B C D
P 0 0 0 0 P 0 0 1 2
Q 0 3 3 0 Q 1 4 2 0
R 1 0 0 2 R 1 3 5 4
S 0 0 2 0 S 0 6 3 2
T 0 6 4 2 T 0 0 1 4
Now we run the Banker's Algorithm.
value of work:
A B C D
1 1 0 0 -- set from avail'
1 1 1 2 -- finished P
2 4 6 6 -- finished R
3 8 8 6 -- finished Q
3 14 11 8 -- finished S
3 14 12 12 -- finished T
The system remains in a safe state: A safe sequence is (P,R,Q,S,T).
The request shall be granted immediately.
--10--
1.
If a new resource type is added this will not have any effect since
'max' is 0 for all processes regarding the new resource.
If a new instance of an existing resource type is added, 'avail' is
increased. 'avail' is only used as upper bound in the algorithm, hence
only more processes may finish, hence no deadlock will be introduced.
2.
Let 'E' be the resource to be removed. If
avail E = 0
holds, all instances are used and the resource cannot be removed
without killing one of the allocating processes.
If a safe sequence exists that never uses the resource to be removed,
i.e., 'work E > 0' all the time, removing is safe. Otherwise it is
not.
3.
As in (2): If a safe sequence exists that never uses the additionally
required resource, this is safe. Otherwise it is not.
4.
Decreasing 'max' below the current value of 'alloc' invalidates the
datastructures.
In case of a valid decrease of 'max', the process will only need less
resources to finish, hence 'need' decreases, hence only more processes
may finish, hence no deadlock will be introduced.
5.
If the system was in a safe state, a safe sequence of process
execution was available. After that all resources are free. If these
are sufficient to fulfill the new process' demands, it can be executed
subsequently. Then the system is in a safe state, otherwise it would
not be able to satisfy the new process anyway.
6.
Safe, since the resources owned by this process will be freed, and
'avail' is increased.
----------------------------------------------------------------------