GATE CS 2022 Q.63: File Systems, I/O and Disk Scheduling

Consider two files systems A and B, that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50th and 51st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are $n_A$ and $n_B$ , respectively, then the value of $n_A + n_B$ is_________.

Your answer

Official answer and solution

Official answer: 153
From: Official GATE 2022 answer key

Solution

Calculate the disk read and write accesses required to insert a block in contiguous allocation versus linked allocation.

A file contains 100 blocks, and a new block is inserted between the 50th and 51st blocks.

In Contiguous Allocation (System A):
- The first 50 blocks remain in place.
- Blocks 51 through 100 (50 blocks) must be shifted backward by one position.
- Shifting each of these 50 blocks requires 1 disk read and 1 disk write: $50 + 50 = 100$ accesses.
- Writing the new block into position 51 requires 1 disk write.
- Total disk accesses for A: $n_A = 50\text{ (reads)} + 50\text{ (writes)} + 1\text{ (write)} = 101$ .
In Linked Allocation (System B):
- Pointers are stored within each block.
- To reach the 50th block, we must traverse the linked chain from block 1 to block 50: 50 disk reads.
- Once block 50 is in memory, its pointer is updated to point to the new block, and the new block is set to point to block 51.
- Writing the new block to disk requires 1 disk write.
- Writing the modified block 50 back to disk requires 1 disk write.
- Total disk accesses for B: $n_B = 50\text{ (reads)} + 1\text{ (write for new block)} + 1\text{ (write for block 50)} = 52$ .
Sum of accesses:
$n_A + n_B = 101 + 52 = 153$

Final answer

153

Common trap

Forgetting that block 50 in linked allocation must be written back to disk after updating its next-block pointer.

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

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 63 of 65
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