GATE - 2019 | Consider the following snapshot of a system running n concurrent processes. Process i

Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use
Posted on 02-02-2022

GATE - 2019 [Operating System]

Question:

Consider the following snapshot of a system running n concurrent processes. Process i is holding Xi instances of a resource R, 1 ≤ i ≤ n. Assume that all instances of R are currently in use. Further, for all i, process i can place a request for at most Yi additional instances of R while holding the Xi instances it already has. Of the n processes, there are exactly two processes p and q such that Yp = Yq = 0. Which one of the following conditions guarantees that no other process apart from p and q can complete execution?

A

Min (Xp, Xq) ≥ Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

B

Xp + Xq < Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

C

Min (Xp, Xq) ≤ Max {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

D

Xp + Xq < Min {Yk | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

 

Solution 1:

{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 D 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}

--------------------------------------------------------------------

Solution 2:

 

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).

 

       

Thank You
  1. GATE - 2019 | Consider three concurrent processes P1, P2 and P3 as shown below
  2. GATE - 2019 | The following C program is executed on a Unix/Linux system:
  3. GATE - 2019 | Assume that in a certain computer, the virtual addresses are 64 bits long
  4. GATE - 2019 | Consider the following four processes with arrival times (in milliseconds)
  5. GATE - 2019 | The index node (inode) of a Unix-like file system has 12 direct, one single-indirect

Download App for Free PDF Download

GovtVacancy.Net Android App: Download

government vacancy govt job sarkari naukri android application google play store https://play.google.com/store/apps/details?id=xyz.appmaker.juptmh