Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
| (26 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 (i% 2==0) { | + | if (<math>i<n</math>) request <math>R_i</math> ; |
| − | + | if (<math>i+2<n</math>)request <math>R_{i+2}</math> ; | |
| − | + | } | |
| − | } | + | else { |
| − | 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> ; | |
| − | + | } | |
| − | } | + | </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: <math> if (i% 2==0) {
if (i<n) request Ri ; if (i+2<n)request Ri+2 ;
} else {
if (i<n) request Rn-i ; if (i+2<n) request Rn-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, Rn-i and Rn-i-2 will be even and there is possibility of deadlock.