GATE CS 2022 Q53 — File Systems

To find the total number of disk accesses, we calculate the disk reads and writes required for both allocation strategies.

1. Contiguous Allocation ($n_A$):

• The file has $100$ blocks. Inserting a new block between the $50^{\text{th}}$ and $51^{\text{th}}$ block means the new block becomes the $51^{\text{th}}$ block.
• The existing blocks from $51$ to $100$ (a total of $50$ blocks) must be shifted one position to the right.
• Shifting these $50$ blocks requires reading them from disk and writing them back to their new locations: $$\text{Reads} = 50, \quad \text{Writes} = 50$$
• We then write the new block (which is already in memory) to the disk at the $51^{\text{th}}$ position: $$\text{Writes} = 1$$
• Thus, $n_A = 50 \text{ (reads)} + 50 \text{ (writes)} + 1 \text{ (write)} = 101$.

2. Linked Allocation ($n_B$):

• To insert a block after the $50^{\text{th}}$ block, we must traverse the linked chain from the start to locate the $50^{\text{th}}$ block.
• This requires reading blocks $1$ through $50$: $$\text{Reads} = 50$$
• The pointer of the $50^{\text{th}}$ block (which points to the $51^{\text{st}}$ block) is copied to the new block's pointer in memory.
• We write the new block to disk: $$\text{Writes} = 1$$
• We update the $50^{\text{th}}$ block's pointer to point to the new block and write it back to disk: $$\text{Writes} = 1$$
• Thus, $n_B = 50 \text{ (reads)} + 1 \text{ (write for new block)} + 1 \text{ (write for } 50^{\text{th}} \text{ block)} = 52$.

Total Disk Accesses: