The GATE Grind

GATE 2022 CS – Question 63

Operating System · File Systems and Disk Performance · 2 marks · Numerical answer

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}.$$

More File Systems and Disk Performance questions

All File Systems and Disk Performance questions →