Consider the following snapshot of a system running π concurrent processes.β¦
2019
Consider the following snapshot of a system running π concurrent processes. Process π is holding ππ instances of a resource R, 1 β€ π β€ π. Assume that all instances of R are currently in use. Further, for all π, process π can place a request for at most ππ additional instances of R while holding the ππ instances it already has. Of the π processes, there are exactly two processes π and π such that ππ = ππ = 0. Which one of the following conditions guarantees that no other process apart from π and π can complete execution?
- A.
\(X_p + X_q < \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}\) - B.
\(X_p + X_q < \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q \}\) - C.
\(\text{Min}(X_p,X_q) \geq \text{Min} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}\) - D.
\(\text{Min}(X_p,X_q) \leq \text{Max} \{Y_k \mid 1 \leq k \leq n, k \neq p, k \neq q\}\)
Attempted by 113 students.
Show answer & explanation
Correct answer: A
Key idea: p and q will not request additional instances and so can complete and free the resources they hold.
When p and q finish they free a total of X_p + X_q instances of R.
For any other process k, that process may request up to Y_k additional instances while holding its current X_k.
To guarantee that no other process can complete, the freed resources must be strictly less than every such possible additional request; i.e., X_p + X_q < Min{Y_k | k β p,q}.
Therefore the condition X_p + X_q < Min{Y_k | 1 β€ k β€ n, k β p, k β q} guarantees that no process other than p and q can complete.
A video solution is available for this question β log in and enroll to watch it.