# Operating System HW5

* B04901110
* 林冠宇

## 7.1

* a.
* The resources in this example are intersections.
* Each line of traffic represents an instance which needs resources.

1. Mutual exclusion:

* An intersection can only be occupied by one line of traffic

2. hold and wait

* If an intersection is occupied by one line of traffic, another line of traffic which needs to pass that intersection can do nothing but wait.
* If the waiting line of traffic already occupied an intersection, it can't release the intersection that is occupied. That is, the line of traffic can only go in a single direction and cannot reverse.

3. circular wait

* In the above figure, each line of traffic is waiting another line of traffic; hence circular wait happens.

4. no preemption

* If an intersection is occupied by a line of traffic, the intersection can't be retracted to allow others to use.

* b.

1. Set a traffic man at the center of the figure.

2. The traffic man mantains a table which records which intersection belongs to which line of traffic

3. If a line of traffic is going to occupy and then pass an intersection, it has to inform the traffic man to claim all the intersections it's going to use beforehand.

4. Only when the traffic man say yes can this line of traffic start to move. Otherwise, it waits.

5. If a requested intersection is already claimed, the traffic man then rejects the request.

* In this case, "Hold & wait" won't happen and hence prevent the deadlock from happening.

## 7.8

* Since each process needs at most m resources, there must involve more than one process in a deadlock.

* Proof by contradiction

* ni >= 1 for all i because:
* mi >= 1 ( condition a. )
* if ai = mi, then deadlock hasn't happened yet since Pi may release more resources
* ai > mi won't happen because each request involves only one resource
* therefore, combining (ai < mi), (mi >= 1), we get ni = mi - ai >= 1

* Hence, due to the contradiction, the assumption "deadlock exist" is wrong. That is, there would be no deadlock in this case.

## 7.13

* a. the system is in a safe state and P0 -> P3 -> P1 -> P4 -> P2 is an order in which the processes may complete

* b. There exist a safe sequence if the request is granted. Therefore, the request can be granted immediately

* c. There doesn't exist a safe sequence if the request is granted. Therefore, the request should not be granted immediately.