COMP 2432 Operating Systems Tutorial 11 Solution
1. Safety of Resource Allocation State.
We first compute the Need array for each process on the resources. For (a), total number of resources = (10 3 6).
(a) Allocation Max Need ABCAABCBC
Copyright By PowCoder代写 加微信 powcoder
P0 2 1 0 5 3 3 3 2 3
P1 1 2 0 3 2 2 2 0 2
P2 2 0 1 6 3 5 4 3 4
P3 2 0 1 2 2 2 0 2 1
P4 0 0 2 2 3 6 2 3 4
The state is an unsafe state.
Start from Work = (3 0 2).
P1 canfinish,Work=(302)+(120)=(422).P3 canfinish,Work=(422)+(201)=(623). P0 can finish, Work = (8 3 3). Only P0, P1 and P3 could finish and it is not a safe state.
For (b), total number of resources = (11 3 7).
(b) Allocation Max Need
P0 2 2 0 3 2 2 1 0 2
P1 2 0 0 3 2 3 1 2 3
P2 1 0 2 5 1 2 4 1 0
P3 2 1 1 2 2 2 0 1 1
P4 1 0 2 2 3 3 1 3 1
The state is a safe state.
A possible safe sequence is
Start from Work = (3 0 2).
P0 canfinish,Work=(302)+(220)=(522).P2 canfinish,Work=(522)+(102)=(624).
P1 can finish, Work = (8 2 4). P3 can finish, Work = (10 3 5).
P4 can finish, Work = (11 3 7). So all processes could finish and it is a safe state.
Now Work = total number of resources (11 3 7) initially (as a checking step).
Other safe sequences include
With the revised maximum demand for (a), total number of resources remains to be (10 3 6). (a)(ii) Allocation Max Need
P0 2 1 0 5 3 3 3 2 3
P1 1 2 0 3 2 2 2 0 2
P2 2 0 1 6 3 5 4 3 4
P3 2 0 1 2 2 2 0 2 1
P4 0 0 2 2 3 5 2 3 3
Now, the state becomes a safe state. A possible safe sequence is
Start from Work = (3 0 2).
P1 canfinish,Work=(302)+(120)=(422).P3 canfinish,Work=(422)+(201)=(623).
P0 can finish, Work = (8 3 3). P4 can finish, Work = (8 3 5).
P2 can finish, Work = (10 3 6). So all processes could finish and it is a safe state. Note that this is the unique safe sequence in this case.
With the revised maximum demand for (b), total number of resources remains to be (11 3 7). (b)(ii) Allocation Max Need
P0 2 2 0 3 2 2 1 0 2
P1 2 0 0 3 2 3 1 2 3
P2 1 0 2 5 1 2 4 1 0
P3 2 1 1 2 3 4 0 2 3
P4 1 0 2 2 3 3 1 3 1
The state is still a safe state. A possible safe sequence is
2. Deadlock Avoidance.
For (a), total number of resources = (10 3 10). There are sufficient resources for the request. Pretend that the request by P3 is granted. Avail = (1 0 4).
(a) Allocation Max Need ABCAABCBC
P0 2 1 0 5 3 3 3 2 3
P1 1 0 0 3 1 2 2 1 2
P2 2 0 2 4 3 2 2 3 0
P3 4 1 2 4 1 2 0 0 0
P4 0 1 2 2 2 3 2 1 1
The resultant state is a safe state. A possible safe sequence is
Start from Work = (1 0 4).
P3 canfinish,Work=(104)+(412)=(516).P1 canfinish,Work=(516)+(100)= (616).
P4 can finish, Work = (6 2 8). P0 can finish, Work = (8 3 8).
P2 can finish, Work = (10 3 10). So all processes could finish. Thus, the request can be granted.
There are three more possible safe sequences:
For (b), total number of resources = (12 3 10). There are sufficient resources for the request. Pretend that the request by P4 is granted. Avail = (0 0 3).
(b) Allocation Max Need ABCAABCBC
P0 2 1 0 6 2 3 4 1 3
P1 3 1 0 3 1 2 0 0 2
P2 2 1 1 3 1 5 1 0 4
P3 1 0 2 2 2 2 1 2 0
P4 4 0 4 4 3 6 0 3 2
StartfromWork=(003).P1 canfinishandWork=(003)+(310)=(313).Now,nootherprocesscouldfinish in the worst scenario as Work is not sufficient. The resultant state is an unsafe state, since only P1 could finish. Thus, the request cannot be granted.
There is no safe sequence, i.e., the count is zero.
When the requesting process in (a) is not P3, but Px where x 3. the request cannot be granted. This is because pretending that Reqx has been granted, regardless of the value of x, all the 4 resultant states are unsafe. You should proceed to verify this statement by repeating the steps in (a). In fact, if the request is raised by P2, the request should be directly rejected, since the total request on resource C exceeds the maximum demand declared by P2.
When the requesting process in (b) is P0 instead of P4, the request could be granted. Total number of resources = (12 3 10). There are sufficient resources for the request by P0. Pretend that the request is granted. Avail = (0 0 3).
(b)(ii) Allocation Max Need ABCAABCBC
P0 5 1 2 6 2 3
P1 3 1 0 3 1 2
P2 2 1 1 3 1 5
P3 1 0 2 2 2 2
P4 1 0 2 4 3 6
The resultant state after the pretended resource allocation remains safe. A possible safe sequence is
Start from Work = (0 0 3).
P1 can finish, Work = (3 1 3). P0 can finish, Work = (8 2 5).
0 0 2 1 0 4 1 2 0 3 3 4
P2 can finish, Work = (10 3 6). P3 can finish, Work = (11 3 8).
P4 can finish, Work = (12 3 10). So all processes could finish. Thus, the request can be granted.
There are two more possible safe sequences:
3. Deadlock Detection.
For (a), total number of resources = (8 3 5). The state is not a deadlocked state. A possible completion sequence is
Start from Work = (1 0 0).
P3 canfinish,Work=(100)+(211)=(311).P2 canfinish,Work=(311)+(202)=(513).
P0 can finish, Work = (7 2 3). P4 can finish, Work = (7 3 5).
P1 can finish, Work = (8 3 5). So all processes could finish successfully and there is no deadlock.
There are five more possible completion sequences:
For (b), total number of resources = (8 3 5). The state is deadlocked. StartingfromWork=(101).P3 canfinishandWork=(101)+(100)=(201).
Now, no other process can finish.
Thus, only P3 can finish and all other processes, i.e., P0, P1, P2, and P4 are involved in the deadlock. There is no completion sequence, i.e., the count is zero.
If the available resource A is now broken in (a), total number of resources = (7 3 5). Luckily, the state is still not a deadlocked state. A possible completion sequence is
Start from Work = (0 0 0).
P3 canfinish,Work=(000)+(211)=(211).P2 canfinish,Work=(211)+(202)=(413).
P0 can finish, Work = (6 2 3). P4 can finish, Work = (6 3 5).
P1 can finish, Work = (7 3 5). So all processes could finish successfully and there is no deadlock.
There are five more possible completion sequences:
If an instance of resource B is now repaired in (b), total number of resources = (8 4 5). The state is not a deadlocked state. A possible completion sequence is
Start from Work = (1 1 1).
P3 canfinish,Work=(111)+(100)=(211).P2 canfinish,Work=(211)+(012)=(223).
P0 can finish, Work = (4 3 3). P4 can finish, Work = (6 4 4).
P1 can finish, Work = (8 4 5). So all processes could finish successfully and there is no deadlock.
There are two more possible completion sequences:
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com