Question:
Consider a system consisting of \(k\) instances of a resource \(R\), being shared by 5 processes. Assume that each process requires a maximum of two instances of resource \(R\) and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.The minimum value of \(k\) for the system to be deadlock-free is __________. (answer in integer)
Consider a system consisting of \(k\) instances of a resource \(R\), being shared by 5 processes. Assume that each process requires a maximum of two instances of resource \(R\) and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.
The minimum value of \(k\) for the system to be deadlock-free is __________. (answer in integer)
Show Hint
Use the standard deadlock-free bound for a single resource type, \(k \ge p(m-1)+1\), where \(p\) is the number of processes and \(m\) is the maximum instances each process may need; here \(p=5\) and \(m=2\).
Updated On: Jul 22, 2026
Show Solution
Verified By Collegedunia
Correct Answer: 6
Solution and Explanation
Step 1: Identify the general result this question is built on.
For a system with a single resource type having \(k\) instances shared among \(p\) processes, where each process needs a maximum of \(m\) instances and requests or releases only one instance at a time, the system is guaranteed to be deadlock-free for every possible interleaving of requests exactly when \(k \ge p(m-1) + 1\).
Step 2: Understand why this bound is necessary.
Consider the worst case where every one of the \(p\) processes has already been granted \(m-1\) instances and is now blocked, waiting for its final, \(m\)-th instance. If the total number of instances is exactly \(k = p(m-1)\), this fully blocked configuration can actually be reached, since it uses up all \(k\) instances with \(m-1\) going to each process, and once every process is stuck waiting for one more unit that never becomes free, the system is deadlocked with no process able to proceed.
Step 3: Understand why the bound is sufficient.
If instead \(k = p(m-1) + 1\), then even if every process tries to hold \(m-1\) instances at once, that only consumes \(p(m-1)\) instances out of the \(k\) available, leaving at least 1 instance still free. That spare instance can always be handed to some waiting process, letting it reach its full requirement of \(m\) instances, finish its work, and release all \(m\) instances it was holding back to the pool. Those newly released instances are then enough to push the next process over its own threshold, and this chain continues until every process eventually completes, so the system can never get permanently stuck.
Step 4: Substitute the given values.
Here there are \(p = 5\) processes and each needs a maximum of \(m = 2\) instances. So the minimum deadlock-free value is \(k = 5(2-1) + 1 = 5(1) + 1 = 6\).
Step 5: Sanity check with \(k = 5\).
With only 5 instances, all 5 processes could each be granted exactly 1 instance, using up every available unit, and every process would then be blocked waiting for a second instance that can never be freed by anyone else. This is a genuine deadlock, confirming that \(k = 5\) is not enough and \(k = 6\) really is the smallest value that keeps the system deadlock-free.
\[ \boxed{6} \]For a system with a single resource type having \(k\) instances shared among \(p\) processes, where each process needs a maximum of \(m\) instances and requests or releases only one instance at a time, the system is guaranteed to be deadlock-free for every possible interleaving of requests exactly when \(k \ge p(m-1) + 1\).
Step 2: Understand why this bound is necessary.
Consider the worst case where every one of the \(p\) processes has already been granted \(m-1\) instances and is now blocked, waiting for its final, \(m\)-th instance. If the total number of instances is exactly \(k = p(m-1)\), this fully blocked configuration can actually be reached, since it uses up all \(k\) instances with \(m-1\) going to each process, and once every process is stuck waiting for one more unit that never becomes free, the system is deadlocked with no process able to proceed.
Step 3: Understand why the bound is sufficient.
If instead \(k = p(m-1) + 1\), then even if every process tries to hold \(m-1\) instances at once, that only consumes \(p(m-1)\) instances out of the \(k\) available, leaving at least 1 instance still free. That spare instance can always be handed to some waiting process, letting it reach its full requirement of \(m\) instances, finish its work, and release all \(m\) instances it was holding back to the pool. Those newly released instances are then enough to push the next process over its own threshold, and this chain continues until every process eventually completes, so the system can never get permanently stuck.
Step 4: Substitute the given values.
Here there are \(p = 5\) processes and each needs a maximum of \(m = 2\) instances. So the minimum deadlock-free value is \(k = 5(2-1) + 1 = 5(1) + 1 = 6\).
Step 5: Sanity check with \(k = 5\).
With only 5 instances, all 5 processes could each be granted exactly 1 instance, using up every available unit, and every process would then be blocked waiting for a second instance that can never be freed by anyone else. This is a genuine deadlock, confirming that \(k = 5\) is not enough and \(k = 6\) really is the smallest value that keeps the system deadlock-free.
Was this answer helpful?
0
0
Top GATE CS Operating System Questions
- Processes \( P_1, P_2, P_3, P_4 \) arrive in that order at times 0, 1, 2, and 8 milliseconds respectively, and have execution times of 10, 13, 6, and 9 milliseconds respectively. Shortest Remaining Time First (SRTF) algorithm is used as the CPU scheduling policy. Ignore context switching times. Which ONE of the following correctly gives the average turnaround time of the four processes in milliseconds?
- With respect to deadlocks in an operating system, which of the following statements is/are FALSE?
- Consider a hard disk with a rotational speed of 15000 rpm. The time to move the read/write head from a track to its adjacent track is 1 millisecond. Initially, the head is on track 0. The number of sectors per track is 400. The sector size is 1024 bytes. It is necessary to transfer data from 10 randomly located sectors in each of the following tracks in the order: 5, 12 and 7. The total time for the data transfer (in milliseconds) from the hard disk is _________. (rounded off to one decimal place)
- Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.
int main () { int i; for (i = 0; i < 3; i++){ if (fork() == 0){ continue; } break; } printf("Hello!"); return 0; }The total number of times that the printf statement gets executed is ________. - Consider a CPU that has to execute two types of processes. The first type, Actuators (A), requires a CPU burst of 6 seconds. The second type, Controllers (C), requires a CPU burst of 8 seconds. A new process of type A arrives at time \(t = 10, 20, 30, 40,\) and \(50\) (in seconds). Similarly, a new process of type C arrives at time \(t = 11, 22, 33, 44,\) and \(55\) (in seconds). The CPU scheduling policy is First Come First Serve (FCFS). The first process of type A starts running at \(t = 10\) seconds. The average waiting time (in seconds) for the 10 processes is ___________.(Rounded off to one decimal place)
View More Questions
Top GATE CS Questions
- Which of the following sequences when stored in an array at locations A[1],..., A[10] forms a max-heap?
- The Lucas sequence Ln is defined by the recurrence relation: Ln = Ln−1 + Ln−2, for n ≥ 3, with L1 = 1 and L2 = 3. Which one of the options given is TRUE?
- Which of the following fields of IP header is/are always modified by any router before it forwards to IP Packet ?
- Which one of the following CIDR profix exactly represent the range of IP addresses 10.12.2.0 to 10.12.3.255?
- Consider an ethernet segment whose transmission is \(10^8\) bits per second. Maximum segment length \(500\ m\), speed of the provocation media velocity is \(2 × 10^8\) meter per second. What is the minimum frame size in bits ?
View More Questions