GATE 2022 CS – Question 63
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 _________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 153
Explanation
**System A (contiguous allocation), 100 blocks stored; insert a new block after block 50.**
Blocks 51–100 (50 blocks) must each move one position down. Each move is one read and one write, so $50\times2=100$ accesses. Then the new block is written: 1 access.
$$n_A=100+1=101.$$
**System B (linked allocation).**
Block 50 must be found by following links from the start, which needs 50 reads. Then write the new block (pointing to old block 51): 1 access. Finally update block 50's pointer to the new block: 1 write.
$$n_B=50+1+1=52.$$
$$n_A+n_B=101+52=\mathbf{153}.$$