Post Test - Deadlock Detection Algorithm

1. Which strategy might be employed to resolve deadlocks detected by an operating system?

Avoidance by proactively managing resources.

Prevention by never allowing processes to request resources.

Resource preemption by forcibly releasing resources from processes.

Ignoring deadlocks and allowing processes to remain blocked indefinitely.

Explanation:

Correct Answer: C
Resource preemption is one of the primary strategies for deadlock recovery. When a deadlock is detected, the system can forcibly take resources away from some processes and allocate them to others to break the circular wait condition. This may require rolling back the preempted processes to a safe state. Other recovery methods include process termination, but preemption is often preferred as it's less drastic than killing processes.

2. Consider a system which have 'n' number of processes and 'm' number of resource types. The time complexity of the safety algorithm, which checks whether a system is in safe state or not, is of the order of:

O(mn)

O(m²n²)

O(m²n)

O(mn²)

Explanation:

Correct Answer: D
The safety algorithm (Banker's Algorithm) has a time complexity of O(mn²). This is because for each of the n processes, we need to check if it can be satisfied by comparing its need with available resources (O(m) operation), and in the worst case, we might need to do this for all n processes in each iteration. Since we might need up to n iterations to find a safe sequence, the total complexity becomes O(mn²).

3. Which condition must be met for the Banker's Algorithm to grant a resource request?

The request must be less than or equal to the available resources

The request must be less than or equal to the process's maximum claim

The resulting state after allocation must be safe

All of the above

Explanation:

Correct Answer: D
All three conditions must be satisfied for the Banker's Algorithm to grant a resource request: (1) The request must not exceed available resources, (2) The request must not exceed the process's declared maximum need, and (3) After granting the request, the system must remain in a safe state. Only when all these conditions are met simultaneously can the request be safely granted without risking deadlock.

4. Consider a system having "n" resources of same type. These resources are shared by 3 processes, A, B, C. These have peak demands of 3, 4, and 6 respectively. For what value of "n" deadlock won't occur

15

9

10

11

Explanation:

Correct Answer: D
To avoid deadlock, we need at least (sum of max demands - number of processes + 1) resources. With processes having peak demands of 3, 4, and 6, the sum is 13. Using the formula: 13 - 3 + 1 = 11 resources. With 11 resources, at least one process can always complete its execution, preventing deadlock. With fewer resources, all processes might get stuck waiting for additional resources.

5. In which situation will the Banker's Algorithm deny a resource request?

If the request is greater than the process's maximum claim

If the resources requested are not available

If granting the request would result in an unsafe state

If the system is overloaded with processes

Explanation:

Correct Answer: C
The Banker's Algorithm will deny a resource request if granting it would result in an unsafe state, even if the other conditions are met. An unsafe state is one where there's no guarantee that all processes can complete. The algorithm performs a safety check by simulating the allocation and determining if a safe sequence exists. If no safe sequence can be found, the request is denied to prevent potential deadlock.