CS 604 Assignment no 3 Solution fall 2021
Please carefully read the following instructions before attempting the assignment.
RULES FOR MARKING:
It should be clear that your assignment would not get any credit if:
- The assignment is submitted after the due date.
- The submitted assignment does not open or the file is corrupt.
- Strict action will be taken if the submitted solution is copied from any other student or the internet.
OBJECTIVE
- Safety Algorithm
- Deadlock Avoidance.
- To learn and understand Banker’s Algorithm.
Question No. 1 15 Marks
Let us suppose a system with 5 processes P0 to P4 and four resource types R0 to R3. R0 has 9 instances, R1 has 3 instances, R2 has 2 instances, R3 has 2 instances. Let us consider that at time T= 0, the system has the following state.
|
Processes |
Allocation |
Max |
Available |
||||||||||
|
Resource Types |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
|
|
P0 |
3 |
1 |
1 |
0 |
5 |
2 |
1 |
0 |
2 |
1 |
0 |
0 |
|
|
P1 |
2 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
|
|
|
|
|
|
P2 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
|
|
|
|
|
|
P3 |
2 |
1 |
0 |
0 |
3 |
2 |
1 |
1 |
|
|
|
|
|
|
P4 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
2 |
|
|
|
|
|
a) Calculate
the Need Matrix for each process (P0 to P4) from the information given in the
table.
Solution
|
Processes |
Allocation |
Max |
Available |
|||||||||
|
Resource Types |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
|
P0 |
3 |
1 |
1 |
0 |
5 |
2 |
1 |
0 |
2 |
1 |
0 |
0 |
|
P1 |
2 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
P2 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
0 |
1 |
1 |
0 |
|
P3 |
2 |
1 |
0 |
0 |
3 |
2 |
1 |
1 |
1 |
1 |
1 |
1 |
|
P4 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
2 |
2 |
0 |
0 |
1 |
a) Use
the safety algorithm to find out that either the system is in a safe state or
not. Write down the complete available Matrix (work matrix).
SOLUTION
|
Processes |
Allocation |
Max |
Available |
|||||||||
|
Resource Types |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
|
P0 |
3 |
1 |
1 |
0 |
5 |
2 |
1 |
0 |
2 |
1 |
0 |
0 |
|
P1 |
2 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
5 |
2 |
1 |
0 |
|
P2 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
7 |
2 |
1 |
0 |
|
P3 |
2 |
1 |
0 |
0 |
3 |
2 |
1 |
1 |
|
|
|
|
|
P4 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
2 |
|
|
|
|
Safe;
|
Processes |
Allocation |
Max |
Available |
|||||||||
|
Resource Types |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
|
P0 |
3 |
1 |
1 |
0 |
5 |
2 |
1 |
0 |
2 |
1 |
0 |
0 |
|
P1 |
2 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
5 |
2 |
1 |
0 |
|
P2 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
7 |
2 |
1 |
0 |
|
P3 |
2 |
1 |
0 |
0 |
3 |
2 |
1 |
1 |
7 |
2 |
2 |
1 |
|
P4 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
2 |
|
|
|
|
Safe;
|
Processes |
Allocation |
Max |
Available |
|||||||||
|
Resource Types |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
R0 |
R1 |
R2 |
R3 |
|
P0 |
3 |
1 |
1 |
0 |
5 |
2 |
1 |
0 |
2 |
1 |
0 |
0 |
|
P1 |
2 |
0 |
0 |
0 |
2 |
1 |
0 |
1 |
5 |
2 |
1 |
0 |
|
P2 |
0 |
0 |
1 |
1 |
0 |
1 |
2 |
1 |
7 |
2 |
1 |
0 |
|
P3 |
2 |
1 |
0 |
0 |
3 |
2 |
1 |
1 |
7 |
2 |
2 |
0 |
|
P4 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
2 |
9 |
3 |
2 |
2 |
|
|
|
|
|
|
|
|
|
|
9 |
3 |
2 |
2 |
Safe:P0,P1,P2,P3,P4>
a) If
the system is in a safe state then write down the safe sequence and if the
system is not in a safe state then give a reason to support your answer.
Answer
That
sequence< P0,P1,P2,P3,P4> satisfies safety requirements