GATE CS 2021 Set 2 Q.53 (CS Q.43): Deadlock Prevention, Avoidance and Detection

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?

The scheme ensures that deadlocks will not occur.

The scheme may lead to live-lock.

The scheme may lead to starvation.

The scheme violates the mutual exclusion property.

Official answer and solution

Official answer: A, B and C
From: Official GATE 2021 answer key

Solution

Analyze the resource preemption policy in OWNRESOURCE against the Coffman conditions for deadlock, livelock, starvation, and mutual exclusion.

Examine the OWNRESOURCE(Resource R) function:

If resource $R$ is unavailable and currently held by another process $P$ , the requesting process forcibly terminates $P$ , releases all resources owned by $P$ , acquires $R$ , and restarts $P$ .

Analyze the properties:

Deadlock (Statement A): Deadlock requires four simultaneous conditions (mutual exclusion, hold and wait, no preemption, and circular wait). In this scheme, whenever a resource is needed, preemption is forced by terminating the holder. Thus, the 'no preemption' and 'hold and wait' conditions cannot be sustained, preventing deadlock from ever forming. Statement A is correct.

Livelock (Statement B): Consider two processes, $P_1$ holding $R_1$ and requesting $R_2$ , while $P_2$ holds $R_2$ and requests $R_1$ . $P_1$ could terminate and restart $P_2$ , then $P_2$ upon restart could terminate and restart $P_1$ . Both processes actively execute and consume CPU cycles repeatedly aborting and restarting each other without making forward progress. This is the definition of livelock. Statement B is correct.

Starvation (Statement C): A process could be repeatedly preempted, terminated, and restarted whenever a competing process requests its resource, perpetually denying it completion. Statement C is correct.

Mutual Exclusion (Statement D): At any given moment, only one process acquires and holds $R$ because acquisition is guarded by global lock $L$ and granted only after $P$ is terminated and all its resources are released. Mutual exclusion is preserved, not violated. Statement D is incorrect.

Final answer

A, B, C

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2021 Computer Science and Information Technology - Session 2 (CS2)
Question: 53 of 65, printed as CS Q.43
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source