30 votes 30 votes Consider the following snapshot of a system running $n$ concurrent processes. Process $i$ is holding $X_i$ instances of a resource $R$, $1 \leq i \leq n$. Assume that all instances of $R$ are currently in use. Further, for all $i$, process $i$ can place a request for at most $Y_i$ additional instances of $R$ while holding the $X_i$ instances it already has. Of the $n$ processes, there are exactly two processes $p$ and $q$ such that $Y_p = Y_q =0$. Which one of the following conditions guarantees that no other process apart from $p$ and $q$ can complete execution? $X_p + X_q < \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$ $X_p + X_q < \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$ $\text{Min}(X_p,X_q) \geq \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$ $\text{Min}(X_p,X_q) \leq \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}$ Operating System gatecse-2019 operating-system process-synchronization 2-marks + – Arjun asked Feb 7, 2019 retagged Nov 30, 2022 by Lakshman Bhaiya Arjun 12.2k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Apoorva Jain commented Feb 7, 2019 reply Follow Share A is correct 0 votes 0 votes akash.dinkar12 commented May 25, 2019 reply Follow Share https://gateoverflow.in/1844/gate2006-66 8 votes 8 votes aeaswar81 commented Aug 9, 2019 reply Follow Share It's mentioned in the question,' process i can place a request for atmost Yi additional instances' . Isn't it possible to infer that process i need not require additional resource in some cases or requires less than Yi ? 0 votes 0 votes Aalok8523 commented Jun 8, 2020 reply Follow Share @Arjun sir, please add "Resource-allocation" tag on this question instead of "process-synchronization" tag. 1 votes 1 votes Please log in or register to add a comment.
40 votes 40 votes The process $P$, holds $X_p$ resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds. The process $Q$, holds $X_q$ resources currently and it doesn't request any new resources. Therefore after some time, it will completes it's execution and release the resources which it holds. Total available resources after completion of $P$ and $Q = X_p + X_q$. If these resources can not satisfy any process new requests, then no process will be able to completes it's execution. $X_p + X_q < \text{ Min}\{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \} \implies$ delivers that no process going to completes except $P$ and $Q$. Answer is (A) Shaik Masthan answered Feb 7, 2019 edited May 11, 2019 by Krithiga2101 Shaik Masthan comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments prithatiti commented Jun 22, 2022 reply Follow Share @Shaik Masthan, Very beautiful explanation. Thank You...!!! 1 votes 1 votes Abhrajyoti00 commented Feb 3, 2023 reply Follow Share Conclusion: Max available resource $X_p + X_q$ must not be able to solve minimum resource requirement → $\text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}$ 1 votes 1 votes diptanshu malviya commented Dec 9, 2023 reply Follow Share Conclusion : Suppose all the X instances is Holding by the process ,and it requesting the Yi instances . Given already that all Xi is given to the process , It must that Process p and Process Q also get the xp instances and xq instances . Then it not requesting other process of yp and yq ,Soon it will release the Xp and X q Now after it release , We must sure that it should minimum then need of the Any Yi request then it will surely deadlock other wise it Sum of the Xp + xq is releasing the Yi request then we cannot it considered to be deadlock. 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes Process P and Q doesn't need any additional instances of resource R thus they can complete their execution and release the instances. Also initially there are no available instances of resource R. Thus after P and Q completes total available instances become $X_p + X_q$ If no more processes can complete their execution then the minimum requirement of all processes should be > ($X_p + X_q$) Thus Ans A) $X_p + X_q$ < min ( $Y_k, \forall \ k, k \neq P, k \neq Q$) Tuhin Dutta answered Feb 11, 2019 edited Mar 30, 2019 by Tuhin Dutta Tuhin Dutta comment Share Follow See all 4 Comments See all 4 4 Comments reply srestha commented Mar 29, 2019 reply Follow Share Why not C)? 0 votes 0 votes Tuhin Dutta commented Mar 29, 2019 reply Follow Share Because the question asks for $no\ other\ process\ apart\ from\ p\ and\ q\ can\ complete\ execution$ and so if we select option C) it is possible that processes which require fewer resources than what is currently held by P or Q then once P or Q completes execution other processes will also be able to complete their execution. $Y_k$ < $X_p$ or $X_q$ for any k = 1 to n, implies some k processes can complete their execution once P or Q completes which is NOT asked in the question. 4 votes 4 votes srestha commented Mar 29, 2019 reply Follow Share See $Y$ is additional resource, not the direct resource itself So, when a process requires additional resource and $X_{P}+X_{Q}$ less than additional resource That means that process couldn't complete execution. So, it will be deadlock condition. But is all process other than $P,Q$ need additional resource? Because according to question $P_{3}$ already has $3$ resource and it needs $0$ to $3$ additional resource right? 0 votes 0 votes Tuhin Dutta commented Mar 30, 2019 reply Follow Share Yes it will be in an unsafe state and might possibly a deadlock situation. Now coming to your questions 1. Because according to question $P_3$ already has 3 resources and it needs 0 to 3 additional resource right? $Process\ i\ is\ holding\ X_i\ instances\ of\ a\ resource\ R,\ 1≤i≤n$ The above statement can be written as "Process 0 is holding $X_0$ instances of a resource R, Process 1 is holding $X_1$ instances of resource R and so on. See here they have not specified any value so $X_i$ is any value for every $P_i$. . Similarly this statement "$process\ i\ can\ place\ a\ request\ for\ at\ most\ Y_i\ additional\ instances\ of\ R\ while\ holding\ the\ X_i\ instances\ it\ already\ has.$" - also doesn't specify any value for the additional resources. It just denotes $Y_0,Y_1,Y_2\ and\ so\ on$. 2. "But is all process other than P,Q need additional resource?" Also this line clearly says that other than processes P and Q rest all require additional resources. $"Of\ the\ n\ processes,\ there\ are\ exactly\ two\ processes\ p\ and\ q\ such\ that\ $ $Y_p=Y_q=\ 0"$ 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes {P1, P2, ..., Pn} Pi holds Xi instances. Pi can request additional Yi instances. Given two process p & q such that their additional requests are zero. Yp = Yq = 0 {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} means that out of 'n' processes, we are left with (n-2) process (except p&q), i.e., Yk indicates additional request of all the processes (n-2) except p & q. For p & q to complete first, accordingly Xp + Xq < Min {Yk} Option A is correct. There are exactly two process p and q which do not need any additional instances of resources. So, p and q will complete their execution and will release Xp and Xq instances of resources. Now to guarantee that no other process apart from p and q can complete execution, the no. of instances of resources available must be less than the minimum no. of instances of resources required by any other process, i.e., Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q} For example, given by @srestha in one of the comment P1,P2,P3,P1,P2,P3 Now, P1 holding 1 instance of resource R P2 holding 2 instances of resource R P3 holding 3 instances of resource R And R totally has 6 resources Now P1 need some additional instances and P2,P3,P2,P3 do'not need any additional instances of R , So, after releasing 5 instances of R is free. Now P1 must need a minimum more than 5 instances So, A air1ankit answered Apr 4, 2019 air1ankit comment Share Follow See all 0 reply Please log in or register to add a comment.
2 votes 2 votes Xi → Holding resources for process pi, Yi → Additional resources for process pi. As process p and q doesn’t require any additional resources, it completes its execution and available resources are (Xp + Xq) There are (n – 2) process pi (1< i < n, i ≠ p, q) with their requirements as Yi (1 < i < n, i ≠ p, q). In order to not execute process pi, no instance of Yi should be satisfied with (Xp + Xq) resources, i.e., minimum of Yi instances should be greater than (Xp + Xq). So, option (A) is correct. Madhab answered Sep 28, 2019 Madhab comment Share Follow See all 0 reply Please log in or register to add a comment.