GATE2010 q46 - Revision history

Arjun Suresh at 12:01, 15 July 2014

2014-07-15T12:01:55Z

Arjun Suresh at 22:52, 13 July 2014

2014-07-13T22:52:20Z

Arjun Suresh at 07:13, 15 April 2014

2014-04-15T07:13:55Z

Arjun Suresh at 13:46, 14 April 2014

2014-04-14T13:46:36Z

Arjun Suresh: /* Solution */

2014-01-15T22:09:54Z

‎Solution

Arjun Suresh: /* Solution */

2014-01-15T22:09:04Z

‎Solution

Arjun Suresh: /* Solution */

2014-01-15T22:06:54Z

‎Solution

Arjun Suresh: /* Solution */

2013-12-31T18:46:56Z

‎Solution

Arjun Suresh at 18:45, 31 December 2013

2013-12-31T18:45:32Z

Arjun Suresh: /* Solution */

2013-12-31T18:44:02Z

‎Solution

← Older revision		Revision as of 12:01, 15 July 2014
Line 32:		Line 32:

	[[Category:GATE2010]]		[[Category:GATE2010]]
−	[[Category: OS questions]]	+	[[Category: OS questions from GATE]]

@@ Line 30: / Line 30: @@
 {{Template:FBD}}
-[[Category:Operating Systems]]
 [[Category:GATE2010]]
 [[Category: OS questions]]

@@ Line 32: / Line 32: @@
 [[Category:Operating Systems]]
 [[Category:GATE2010]]
-[[Category: Previous year GATE questions]]
+[[Category: OS questions]]

@@ Line 21: / Line 21: @@
 (D) n = 41,k = 19
-===Solution===
+==={{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 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.

@@ Line 24: / Line 24: @@
 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> and 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.
+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)

@@ Line 22: / Line 22: @@
 ===Solution===
-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 and share no more than 1 resource 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.
+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> and 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>, 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 and hence no deadlock is possible.

@@ 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
 request logic of each process <math>P_i</math> . is as follows:
-  <span class="nocode" style="color:#48484c">if (<math>i% 2==0</math>) {
+  <span class="nocode" style="color:#48484c">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> ;