OS: Homework #7

# OS: Homework #7 ##### 于凡奇 18307130182 $~$ 1. **Suppose that a system is in an unsafe state. Show that it is possible for the processes to complete their execution without entering a deadlocked state.** ***[Answer]*** ![](https://i.imgur.com/GVV9tms.png) In the diagram above, P~1~ could acquire R~1~ from P~2~ and P~3~ could acquire R~2~ from P~4~ resulting in no deadlocks. 2. **a) What are the arguments for installing the deadlock-avoidance algorithm?** ***[Answer]*** - Save time for the systems programmer: no more manual terminations and reruns. - No jobs are corrupted, as some jobs may fail permanently if terminated halfway or cannot be run repeatedly. - Fully automatic job running could be possible. - May actually reduce turnaround time as the systems programmer can not always arrive soon enough to handle the deadlocks(e.g. during the week-long National Day Holidays). **b) What are the arguments against installing the deadlock-avoidance algorithm?** ***[Answer]*** - Save time for the machine and more jobs could be run in the extra available time. - Save electricity as the machine's running time reduces. - Jobs are finished more quickly. 3. **Consider the following snapshot of a system:** ```cpp Allocation Max Available A B C D A B C D A B C D P0 2 0 0 1 4 2 1 2 3 3 2 1 P1 3 1 2 1 5 2 5 2 P2 2 1 0 3 2 3 1 6 P3 1 3 1 2 1 4 2 4 P4 1 4 3 2 3 6 6 5 ``` Answer the following questions using the banker’s algorithm: **a) Illustrate that the system is in a safe state by demonstrating an order in which the processes may complete.** ***[Answer]*** A possible completing sequence $\{P_0, P_3, P_1, P_4, P_2\}$ is described as follows: I. $P_0$ completes as $Max[P_0] - Allocation[P_0] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P1 3 1 2 1 5 2 5 2 5 3 2 2 P2 2 1 0 3 2 3 1 6 P3 1 3 1 2 1 4 2 4 P4 1 4 3 2 3 6 6 5 ``` II. $P_3$ completes as $Max[P_3] - Allocation[P_3] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P1 3 1 2 1 5 2 5 2 6 6 3 4 P2 2 1 0 3 2 3 1 6 P4 1 4 3 2 3 6 6 5 ``` III. $P_1$ completes as $Max[P_1] - Allocation[P_1] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P2 2 1 0 3 2 3 1 6 9 7 5 5 P4 1 4 3 2 3 6 6 5 ``` IV. $P_4$ completes as $Max[P_4] - Allocation[P_4] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P2 2 1 0 3 2 3 1 6 10 11 8 7 ``` V. At last $P_2$ can complete. **b) If a request from process P1 arrives for (1, 1, 0, 0), can the request be granted immediately?** ***[Answer]*** The request can be grant immediately as the system is still in a safe state. The completing sequence $\{P_0, P_3, P_1, P_4, P_2\}$ is still possible. ***[Proof]*** Let the request be grant immediately: ```cpp Allocation Max Available A B C D A B C D A B C D P0 2 0 0 1 4 2 1 2 2 2 2 1 P1 4 2 2 1 5 2 5 2 P2 2 1 0 3 2 3 1 6 P3 1 3 1 2 1 4 2 4 P4 1 4 3 2 3 6 6 5 ``` I. $P_0$ completes as $Max[P_0] - Allocation[P_0] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P1 4 2 2 1 5 2 5 2 4 2 2 2 P2 2 1 0 3 2 3 1 6 P3 1 3 1 2 1 4 2 4 P4 1 4 3 2 3 6 6 5 ``` II. $P_3$ completes as $Max[P_3] - Allocation[P_3] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P1 4 2 2 1 5 2 5 2 5 5 3 4 P2 2 1 0 3 2 3 1 6 P4 1 4 3 2 3 6 6 5 ``` III. $P_1$ completes as $Max[P_1] - Allocation[P_1] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P2 2 1 0 3 2 3 1 6 9 7 5 5 P4 1 4 3 2 3 6 6 5 ``` IV. $P_4$ completes as $Max[P_4] - Allocation[P_4] \leq Available$: ```cpp Allocation Max Available A B C D A B C D A B C D P2 2 1 0 3 2 3 1 6 10 11 8 7 ``` V. At last $P_2$ can complete. **c) If a request from process P4 arrives for (0, 0, 2, 0), can the request be granted immediately?** ***[Answer]*** The request can **NOT** be grant immediately. ***[Proof]*** Let the request be grant immediately: ```cpp Allocation Max Available A B C D A B C D A B C D P0 2 0 0 1 4 2 1 2 3 3 0 1 P1 3 1 2 1 5 2 5 2 P2 2 1 0 3 2 3 1 6 P3 1 3 1 2 1 4 2 4 P4 1 4 5 2 3 6 6 5 ``` As $Available[C] = 0$ and $min\{ Max[P_i][C] - Allocation[P_i][C] \} > 0$, no process can be guaranteed completion. Thus the system will enter an unsafe state.