Test: CPU & I/O Scheduling- 3 - Computer Science Engineering (CSE) MCQ

Since both p and q don’t need additional resources, they both can finish and release Xp + Xq resources without asking for any additional resource. If the resources released by p and q are sufficient for another process waiting for Yk resources, then system is not approaching deadlock.

In the extreme condition, all processes acquire Si-1 resources and need 1 more resource. So following condition must be true to make sure that deadlock never occurs.

< m The above expression can be written as following.

< (m + n)

Option B is answer

No. of resources, n = 21
No. of processes, k = 12

Processes {P0, P1....P11}  make the following Resource requests:
{R0, R20, R2, R18, R4, R16, R6, R14, R8, R12, R10, R10}

For example P0 will request R0 (0%2 is = 0 and 0< n=21). 

Similarly, P10 will request R10.

P11 will request R10 as n - i = 21 - 11 = 10.

As different processes are requesting the same resource, deadlock
may occur. 

Option A can cause deadlock. Imagine a situation process X has acquired a, process Y has acquired b and process Z has acquired c and d. There is circular wait now. Option C can also cause deadlock. Imagine a situation process X has acquired b, process Y has acquired c and process Z has acquired a. There is circular wait now. Option D can also cause deadlock. Imagine a situation process X has acquired a and b, process Y has acquired c. X and Y circularly waiting for each other.

Consider option A) for example here all 3 processes are concurrent so X will get semaphore a, Y will get b and Z will get c, now X is blocked for b, Y is blocked for c, Z gets d and blocked for a. Thus it will lead to deadlock. Similarly one can figure out that for B) completion order is Z,X then Y. 

Deadlock Prevention: Deadlocks can be prevented by preventing at least one of the four required conditions:

1. Mutual Exclusion – not required for sharable resources; must hold for non-sharable resources.

2. Hold and Wait – must guarantee that whenever a process requests a resource, it does not hold any other resources. Require process to request and be allocated all its sources before it begins execution, or allow process to request resources only when the process has none. Low resource utilization; starvation possible. Restrain the ways request can be made.

3. No Pre-emption – If a process that is holding some resources requests another resource that cannot be immediately allocated to it, and then all resources currently being held are released. Pre-empted resources are added to the list of resources for which the process is waiting. Process will be restarted only when it can regain its old resources, as well as the new ones that it is requesting.

4. Circular Wait – impose a total ordering of all resource types, and require that each process requests resources in an increasing order of enumeration. Deadlock Avoidance: When a scheduler sees that starting a process or granting resource requests may lead to future deadlocks, then that process is just not started or the request is not granted. The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition. Resource-allocation state is defined by the number of available and allocated resources, and the maximum demands of the processes.

Choice of the question:

(A) In deadlock prevention, the request for resources is always granted if the resulting state is safe. false, Deadlock prevention scheme handles deadlock by making sure that one of the four necessary conditions don't occur. In deadlock prevention, the request for a resource may not be granted even if the resulting state is safe.

(B) In deadlock avoidance, the request for resources is always granted if the result state is safe. true, As in Deadlock avoidance, if resultant state is safe than request for resource is granted as being in a safe state, it can hold other resources now.

(C) Deadlock avoidance is less restrictive than deadlock prevention. true, As in Deadlock prevention, request for a resource may not be granted even if the resulting state is safe. but in deadlock avoidance, request for a resource is granted if the resulting state is safe.

(D) Deadlock avoidance requires knowledge of resource requirements a priori true, deadlock avoidance checks any chance of deadlock means even if the system is in safe state, it checks that after allocating requested resource, the system is not in deadlocked state. So deadlock avoidance requires knowledge of resource requirements a priori.

We can apply the following Deadlock Detection algorithm and see that there is no process waiting indefinitely for a resource.

If 6 resources are there then it may be possible that all three process have 2 resources and waiting for 1 more resource. Therefore, all of them will have to wait indefinitely. If 7 resources are there, then atleast one must have 3 resources so deadlock can never occur.

Deadlock refers to a specific condition when two or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources. Solution: Necessary condition to guarantee no deadlock which means without satisfying this condition, no deadlock is possible. Both the process p and q have no additional requirement; they both can be finished releasing Xp + Xq resources without asking for any additional resource. Using this, we can finish one more process only if condition B is satisfied. If the resources released by p and q are sufficient for another process waiting for Yk resources, then system is not approaching deadlock. i.e Xp+Xq > min (Yk) where k != p and k != q Note: Option B just ensured that the system can proceed from the current state. It does not guarantee that there won’t be a deadlock before all processes are finished.

You can easily see a deadlock in a situation where..
P[0] has acquired m[0] and waiting for m[1]
P[1] has acquired m[1] and waiting for m[2]
P[2] has acquired m[2] and waiting for m[3]
P[3] has acquired m[3] and waiting for m[0]

If Ist is followed, then hold and wait will never happen. II, III and IV are similar. If any of these is followed, cyclic wait will not be possible.

It seems to be wrong question in GATE exam. Below seems to be the worst case situation. In below situation P1 and P2 can continue as they have 2 resources each
P1 --> 2
P2 --> 2
P3 --> 1
P4 --> 1 

Mutual exclusion  is satisfied:
All other processes j started before i must have value (i.e. t[j]) less than the value of process i (i.e. t[i])  as function pMax() return a integer not smaller  than any of its arguments. So if anyone out of the processes j have positive value will be executing in its critical section as long as the condition t[j] > 0 && t[j] <= t[i] within while will persist. And when  this j process comes out of its critical section, it sets t[j] = 0;  and next process will be selected in for loop.
So when i process reaches to its critical section none of the  processes j which started earlier before process i  is in its critical section. This ensure that only one process is executing its critical section at a time. 

Deadlock and progress are  not satisfied:  
while (t[j] != 0 && t[j] <=t[i]); because of this condition deadlock is possible when value of j process becomes equals to the value of process i (i.e t[j] == t[i]).  because of the deadlock progess is also not possible (i.e. Progess == no deadlock) as no one process is able to make progress by stoping other process. 

Bounded waiting is also not satisfied: 
In this case both deadlock and bounded waiting to be arising from the same reason as if t[j] == t[i] is possible then starvation is possible means infinite waiting.

Initially we have semaphore value = 10 Now we have to perform 6 p operation means when we perform one p operation it decreases the semaphore values to one. So after performing 6 p operation we get, semaphore values = 10 - 6 = 4 and now we have to perform 4 v operation means when we perform one V operation it increases the semaphore values to one. So after performing 4 v operation we get, semaphore values = 4 + 4 = 8. Option (B) is correct.

Say P₁ starts first and executes statement 1, after that system context switches to P₂ (before executing statement 2), and it enters inside if statement, since the flag is still false. So now both processes are in critical section!! so (i) is true.. (ii) is false By no way it happens that flag is true and no process' are inside the if clause, if someone enters the critical section, it will definitely make flag = false. So no deadlock.

Total process = 3 and each require 2 units of resource. If we give 1 resource to 1 process then total resource = 1 + 1 + 1 = 3 but in this case deadlock will definitely occur because each process hold 1 unit resource and waiting for another resource so if we increase 1 more resource (3+1=4) then deadlocks will ever arise (i.e., when process 1 complete their execution then it free 2 resource and this 2 resource will used by another process.). Option (B) is correct.