---
# System prepended metadata

title: '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.