#operating system#Deadlock

Question

Comments

Need matrix will be as follows

pr  X  Y  Z

p0  7  4  3

p1  1  2  2

p2  6  0  0

p3  0  1  1

p4  4  3  1

now availabe are 3 3 2 .  That means we can execute p1 and p3

case1)   choose p1

now available will be 3+2   3+0   2+0 = 5 3 3

now we can execute p3 and p4

sub case i) consider p3 first

now available will be 5+2   3+1   3+1 = 7 4 4

that means we can execute all process now

p1 - p3 - remaining 3 processes = 3! = 6

sub case ii) consider p4 now i.e p1-p4- remaining

now available will be 5+0   3+0   3+2 = 5 3 5

that means we can execute p3

so available will be  5+2   3+1   5+2 = 7 4 7

now we can execute all remaining processes

p1-p4-p3- remaining 2 processes = 2! =2

So total safe sequences in case 1) = 6+2 = 8 

case 2) Now start with p3

available will be  3+2   3+1   2+1 = 5 4 3

now we can execute p1 and p4

subcase i)

select p1

available will be 5+2   4+0   3+0 = 7 4 3

that means we can execute all remaining processes

p3-p1-remaining 3 processes = 3! = 6

subcase ii)

select p4

available will be 5+0   4+0   3+2 = 5 4 5

now we can execute p1

available will be 5+2   4+0   5+0 = 7 4 5

now we can execute remaining 2 processes

p3-p4-p1-remaining 2 processes = 2! = 2

 so total safe sequences iin case 2) = 6 + 2 =8 

 

That means total safe sequence = 8+8 =16 

---

Thanks

---

P1 P4 P3 (2!) sequence is invalid. So, 14

Answer 1

Available resources : $(x,y,z) = (3,3,2)$, So, We can satisfy demand of $P_{1}$ and $P_{3}$ initially. So, Take both of these cases and finally add the safe sequences we get from these two cases:

Starting with $P_{1}$, needs can be satisfied like :

And starting with $P_{3}$ as

So, Safe sequences possible $\color{olive}{= 6 + 2 + 6 + 2 = 16}$

PS:) The only thing to note here is that once the resource availability is sufficient enought to satisfy every need we find all arrangements of remaining requests. like ($3! = 6$ ways) in above case.

Answer 2

The key point to be followed in solving this type of question is :

We select a process such that its need (demand) is satisfied by the currently available resources.

For this question hence we need to calculate the need matrix first which is given by :

Need[i][j] = Maximum[i][j] - Allocation[i][j]    .So need matrix is given by :

 A         B        C

 7        4         3

 1        2         2

 6        0         0

 0        1         1

 4        3         1

Having calculated the need matrix in order to find no of safe sequences , we need to do it carefully as by partly taking cases and partly applying combinatorics keeping in mind the requirements of safety algorithm.

We have to select a process such that the need of every resource of that process <= the available resource at that instant

So initially we have only P1 and P3 satisfying the given constraint.Hence we solve them separately :

Case 1(P3 is selected first) :

Now if P3 is selected first , then available is updated as :

available[j]  =   available[j] + allocation[3][j] where j varies from 1 to 3 since after usage a process needs to free its allocated resources , hence we are adding it to the available number of resources of each type.

So available =  [3   3    2]  +   [2    1     1]     =    [ 5     4      3]

Now considering the condition need[i][j] <=  available[j] for the next process to be selected , we have only 2 such process after P3 i.e.  P1     and      P4

Proceeding with P1 , meaning let P1 is selected after P3 , so available is now updated as :

 [5    4     3] +   [2    0    0]     =    [7   4    3]

Now we can see that we do not need to proceed further since the need of any of the 3 remaining will be satisfied from this point.At this point any of the 3 processes can be selected , after 3rd process is executed the available resources will further increase , so not a problem.

Hence no of ways from this instant if we take P1 after P3 = 3!  =   6

If we consider choosing P4 after P3 , then after updation of available resources , only P1 satisfies so P1 has to be selected and after P1 , either P0 or P2 can come.

So no of ways  here =  2 

Hence , for a) part i.e. beginning with P3  , no of safe sequences =   6 + 2  = 8

For part b) also i.e. safe sequence beginning with P1 , we will have 6 cases if we have P3 after P1 and 2 cases if we have P4 after P1 .

So no of sequences  here = 8 as well

Hence total no of safe sequences   =    8 + 8

                                                      = 16

Hence 16 is the correct answer.