GATE 2022 CS Q.63: solution and answer

GATE 2022 · CSQ.63 · 2 marks · NAT

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 ______.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$n_{A} + n_{B} = 101 + 52 = 153$ .

Official answer: 153Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

File $A$ (contiguous). To open a gap after block 50, blocks 51 to 100 must each move one position towards the end: that is $100 - 50 = 50$ blocks. There are enough free blocks at the end, so block 101 is available.
Each moved block costs one read and one write, so $50 \times 2 = 100$ accesses. Move from the last block backwards, so nothing is overwritten before it has been copied.
Writing the new block (already in memory) into the gap costs 1 access. So $n_{A} = 100 + 1 = 101$ .
File $B$ (linked). There is no random access, so block 50 is reached by following pointers from the start. Reading blocks 1 to 50 costs 50 accesses (the file control block is in memory, so the first block's address is free).
Write the new block, with its pointer set to the old block 51: 1 access.
Block 50 is already in memory, so rewrite it with its pointer changed to the new block: 1 access. So $n_{B} = 50 + 1 + 1 = 52$ .
$n_{A} + n_{B} = 101 + 52 = 153$ .

KEY IDEA

Contiguous allocation must physically shift every block after the insertion point (a read and a write each), while linked allocation must walk to the insertion point and then change only two pointers.

WATCH OUT FOR

Forgetting that a shifted block costs two accesses (read and write), or forgetting to rewrite block 50 with the new pointer in the linked file.

From the GATE 2022 CS paper. Every question of this paper · Download the full paper · All 6 File systems & disks questions, with notes

GATE 2022 CS Q.63: solution and answer

Answer and solution

More File systems & disks questions