Consider a computer system with multiple shared resource types, with one… — GATE CS 2021 Set 2 Q43

Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock $(L)$ . The following scheme is used to own a resource instance:

function OWNRESOURCE(Resource R)
    Acquire lock L // a global lock
    if R is available then
        Acquire R    
        Release lock L
    else
        if R is owned by another process P then     
        Terminate P, after releasing all resources owned by P    
        Acquire R    
        Restart P   
        Release lock L   
        end if   
    end if    
end function

Which of the following choice(s) about the above scheme is/are correct?

View worked solution

Answer: A;B;C

To determine which choices are correct, let us analyze the behavior of the OWNRESOURCE function and how it manages resources.

1. Deadlock Prevention (Option A)

A deadlock requires four necessary conditions: Mutual Exclusion, Hold and Wait, No Preemption, and Circular Wait.

In this scheme, when a process requests a resource $R$ that is currently held by another process $P$ , the requesting process does not wait.
Instead, it immediately terminates $P$ , forces the release of $P$ 's resources, acquires $R$ , and restarts $P$ .
Since no process ever enters a waiting state for a resource, the Hold and Wait condition is eliminated, and a Circular Wait cannot form.

Therefore, deadlocks cannot occur. Option A is correct.

2. Livelock (Option B)

A livelock occurs when two or more processes continuously change their state in response to each other without making any forward progress.

Consider two processes, $P_1$ and $P_2$ , and two resources, $R_1$ and $R_2$ .
$P_1$ acquires $R_1$ and $P_2$ acquires $R_2$ .
Now, $P_1$ requests $R_2$ . Since $R_2$ is held by $P_2$ , $P_1$ terminates $P_2$ , releases $R_2$ , acquires $R_2$ , and restarts $P_2$ .
Before $P_1$ can complete its execution, the restarted $P_2$ requests $R_1$ . Since $R_1$ is held by $P_1$ , $P_2$ terminates $P_1$ , releases all of $P_1$ 's resources (including $R_2$ ), acquires $R_1$ , and restarts $P_1$ .
This cycle of mutual termination and restart can continue indefinitely, preventing both processes from ever completing.

Therefore, the scheme may lead to livelock. Option B is correct.

3. Starvation (Option C)

Starvation occurs when a process is perpetually denied the resources or CPU time it needs to complete its execution.

As shown in the livelock scenario, a process can be repeatedly terminated and restarted by other active processes before it can finish its task.
Consequently, such a process will suffer from starvation.

Therefore, the scheme may lead to starvation. Option C is correct.

4. Mutual Exclusion (Option D)

Mutual exclusion means that a resource instance can be held by at most one process at any given time.

When a process requests an already-owned resource $R$ , the owner $P$ is terminated, and all of $P$ 's resources are released first before the requesting process acquires $R$ .
Thus, at any instant, no resource is owned by more than one process.

Therefore, mutual exclusion is not violated. Option D is incorrect.

Free practice · Your answers on this page are not saved.

GATE CS 2021 Set 2 Q43 — Deadlock

1. Deadlock Prevention (Option A)

2. Livelock (Option B)

3. Starvation (Option C)

4. Mutual Exclusion (Option D)

Related questions