Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (22 intermediate revisions by the same user not shown) | |||
| Line 1: | Line 1: | ||
A system has <math>n</math> resources <math>R_0 ,..., R_n-1</math> , and <math>k</math> processes <math>P_0 ,.....P_{k-1}</math> . The implementation of the resource | A system has <math>n</math> resources <math>R_0 ,..., R_n-1</math> , and <math>k</math> processes <math>P_0 ,.....P_{k-1}</math> . The implementation of the resource | ||
request logic of each process <math>P_i</math> . is as follows: | request logic of each process <math>P_i</math> . is as follows: | ||
| − | + | <span class="nocode" style="color:#48484c">if (<math>i\% 2==0</math>) { | |
| − | if (<math>i% 2==0</math>) { | ||
if (<math>i<n</math>) request <math>R_i</math> ; | if (<math>i<n</math>) request <math>R_i</math> ; | ||
if (<math>i+2<n</math>)request <math>R_{i+2}</math> ; | if (<math>i+2<n</math>)request <math>R_{i+2}</math> ; | ||
| Line 10: | Line 9: | ||
if (<math>i+2<n</math>) request <math>R_{n-i-2}</math> ; | if (<math>i+2<n</math>) request <math>R_{n-i-2}</math> ; | ||
} | } | ||
| − | + | </span> | |
In which one of the following situations is a deadlock possible? | In which one of the following situations is a deadlock possible? | ||
| Line 22: | Line 21: | ||
(D) n = 41,k = 19 | (D) n = 41,k = 19 | ||
| − | === | + | ==={{Template:Author|Arjun Suresh|{{arjunweb}} }}=== |
| − | From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered | + | From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered processes share no more than 1 resource. Now, if we make sure that all odd numbered processes take odd numbered resources without a cycle, then deadlock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, <math>R_{n-i}</math> and <math>R_{n-i-2}</math> will be even and there is possibility of deadlock, when two processes requests the same <math>R_i</math> and <math>R_j</math>. So, only <math>B</math> and <math>D</math> are the possible answers. |
| − | |||
| − | |||
| − | |||
| − | |||
| − | {{ | + | Now, in <math>D</math>, we can see that <math>P_0</math> requests <math>R_0</math> and <math>R_2</math>, <math>P_2</math> requests <math>R_2</math> and <math>R_4</math>, so on until, <math>P_{18}</math> requests <math>R_{18}</math> and <math>R_{20}</math>. At the same time <math>P_1</math> requests <math>R_{40}</math> and <math>R_{38}</math>, <math>P_3</math> requests <math>R_{38}</math> and <math>R_{36}</math>, so on until, <math>P_{19}</math> requests <math>R_{22}</math> and <math>R_{20}</math>. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle of dependencies which means, no deadlock is possible. |
| + | But for <math>B</math>, <math>P_8</math> requests <math>R_8</math> and <math>R_{10}</math> and <math>P_{11}</math> also requests <math>R_{10}</math> and <math>R_8</math>. Hence, a deadlock is possible. (Suppose <math>P_8</math> comes first and occupies <math>R_8</math>. Then <math>P_{11}</math> comes and occupies <math>R_{10}</math>. Now, if <math>P_8</math> requests <math>R_{10}</math> and <math>P_{11}</math> requests <math>R_8</math>, there will be deadlock) | ||
| + | {{Template:FBD}} | ||
| − | |||
| − | |||
[[Category:GATE2010]] | [[Category:GATE2010]] | ||
| − | [[Category: | + | [[Category: OS questions from GATE]] |
A system has <math>n</math> resources <math>R_0 ,..., R_n-1</math> , and <math>k</math> processes <math>P_0 ,.....P_{k-1}</math> . The implementation of the resource request logic of each process <math>P_i</math> . is as follows:
GATECSEif (<math>i\% 2==0</math>) {
if (<math>i<n</math>) request <math>R_i</math> ;
if (<math>i+2<n</math>)request <math>R_{i+2}</math> ;
}
else {
if (<math>i<n</math>) request <math>R_{n-i}</math> ;
if (<math>i+2<n</math>) request <math>R_{n-i-2}</math> ;
}
In which one of the following situations is a deadlock possible?
(A) n = 40,k = 26
(B) n = 21,k = 12
(C) n = 20,k = 10
(D) n = 41,k = 19
From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered processes share no more than 1 resource. Now, if we make sure that all odd numbered processes take odd numbered resources without a cycle, then deadlock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, <math>R_{n-i}</math> and <math>R_{n-i-2}</math> will be even and there is possibility of deadlock, when two processes requests the same <math>R_i</math> and <math>R_j</math>. So, only <math>B</math> and <math>D</math> are the possible answers.
Now, in <math>D</math>, we can see that <math>P_0</math> requests <math>R_0</math> and <math>R_2</math>, <math>P_2</math> requests <math>R_2</math> and <math>R_4</math>, so on until, <math>P_{18}</math> requests <math>R_{18}</math> and <math>R_{20}</math>. At the same time <math>P_1</math> requests <math>R_{40}</math> and <math>R_{38}</math>, <math>P_3</math> requests <math>R_{38}</math> and <math>R_{36}</math>, so on until, <math>P_{19}</math> requests <math>R_{22}</math> and <math>R_{20}</math>. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle of dependencies which means, no deadlock is possible.
But for <math>B</math>, <math>P_8</math> requests <math>R_8</math> and <math>R_{10}</math> and <math>P_{11}</math> also requests <math>R_{10}</math> and <math>R_8</math>. Hence, a deadlock is possible. (Suppose <math>P_8</math> comes first and occupies <math>R_8</math>. Then <math>P_{11}</math> comes and occupies <math>R_{10}</math>. Now, if <math>P_8</math> requests <math>R_{10}</math> and <math>P_{11}</math> requests <math>R_8</math>, there will be deadlock)
A system has <math>n</math> resources <math>R_0 ,..., R_n-1</math> , and <math>k</math> processes <math>P_0 ,.....P_{k-1}</math> . The implementation of the resource request logic of each process <math>P_i</math> . is as follows:
if (<math>i% 2==0</math>) {
if (<math>i<n</math>) request <math>R_i</math> ;
if (<math>i+2<n</math>)request <math>R_{i+2}</math> ;
}
else {
if (<math>i<n</math>) request <math>R_{n-i}</math> ;
if (<math>i+2<n</math>) request <math>R_{n-i-2}</math> ;
}
In which one of the following situations is a deadlock possible?
(A) n = 40,k = 26
(B) n = 21,k = 12
(C) n = 20,k = 10
(D) n = 41,k = 19
From the resource allocation logic, it's clear that even numbered processes are taking even numbered resources and all even numbered resources are taken by 2 processes. Now, if we make sure that all odd numbered processes take odd numbered resources, then dead lock cannot occur. The "else" case of the resource allocation logic, is trying to do that. But, if n is odd, <math>R_{n-i}</math> and <math>R_{n-i-2}</math> will be even and there is possibility of deadlock. So, only <math>B</math> and <math>D</math> are the possible answers.
Now, in D, we can see that P_0 requests R_0 and R_2, P_2 requests R_2 and R_4 and so on until, P_18 requests R_18 and R_20. At the same time P_1 requests R_40 and R_38, so on until P_19 requests R_22 and R_20. i.e.; there are no two processes requesting the same two resources and hence there can't be a cycle (of length two) of dependencies and hence no deadlock is possible.
But for B, P_8 requests R_8 and R_10 and P_11 also requests R_10 and R_8. Hence, a deadlock is possible.