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)

Question

A database has 25,000 fixed-length records of 100 bytes (primary key 15 bytes). The data file is block-aligned so each record is fully contained within a block. The file is indexed by a primary index file, also block-aligned and ordered. Block size is 1024 bytes and a block pointer is 5 bytes. Each index entry stores the block’s anchor key (15 bytes) and a pointer (5 bytes). Binary search on an index file of $b$ blocks needs $\lceil \log_2 b \rceil$ block accesses in the worst case. Given a key, the number of block accesses required to identify the data file block that may contain the record, in the worst case, is ____________.

Answer 1

Build the worst-case allocation table directly instead of quoting the formula first.

There are 5 processes, and each one can eventually need up to 2 instances of the single resource type $R$, requesting them one at a time and only asking for the second after already holding the first.
Suppose the scheduler is adversarial and tries to create a deadlock. The most dangerous state it can engineer is one where every process has been given exactly 1 instance, its first, and is now sitting blocked, waiting for the second instance, which nobody will ever release voluntarily since nobody has finished. Building this state consumes exactly $5 \times 1 = 5$ instances.
If the system only has $k = 5$ instances total, this exact worst case is reachable: all 5 units get handed out one to each process, and now every process is stuck forever. That is a deadlock, so $k=5$ fails to guarantee deadlock freedom.
Now suppose $k = 6$. The adversary can still hand out 1 instance to each of the 5 processes, using 5 of the 6 units, but there remains 1 unit spare. That spare unit must be given to one of the waiting processes, which then has its 2 required instances, finishes, and returns both of its units to the pool. The pool now has 2 free units, which is enough to fully satisfy another waiting process, and this domino effect guarantees every process eventually finishes.
So the smallest $k$ that always avoids the fully-blocked worst case is 1 more than the worst case's total, that is $5 \times (2-1) + 1 = 6$.

Hence the minimum value of $k$ is 6.

$$\boxed{6}$$

Answer 2

Build the worst-case allocation table directly instead of quoting the formula first.

There are 5 processes, and each one can eventually need up to 2 instances of the single resource type $R$, requesting them one at a time and only asking for the second after already holding the first.
Suppose the scheduler is adversarial and tries to create a deadlock. The most dangerous state it can engineer is one where every process has been given exactly 1 instance, its first, and is now sitting blocked, waiting for the second instance, which nobody will ever release voluntarily since nobody has finished. Building this state consumes exactly $5 \times 1 = 5$ instances.
If the system only has $k = 5$ instances total, this exact worst case is reachable: all 5 units get handed out one to each process, and now every process is stuck forever. That is a deadlock, so $k=5$ fails to guarantee deadlock freedom.
Now suppose $k = 6$. The adversary can still hand out 1 instance to each of the 5 processes, using 5 of the 6 units, but there remains 1 unit spare. That spare unit must be given to one of the waiting processes, which then has its 2 required instances, finishes, and returns both of its units to the pool. The pool now has 2 free units, which is enough to fully satisfy another waiting process, and this domino effect guarantees every process eventually finishes.
So the smallest $k$ that always avoids the fully-blocked worst case is 1 more than the worst case's total, that is $5 \times (2-1) + 1 = 6$.

Hence the minimum value of $k$ is 6.

Show Hint

Correct Answer: 6

Solution and Explanation

Questions Asked in GATE CS exam