Question

Consider two file 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 the 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

Hint:

In contiguous allocation, shifting data to insert a block can require accessing multiple blocks, whereas in linked allocation, only the necessary block links need to be updated.

Answer 1

Correct Answer: 153

To evaluate the total number of operations ($n_A + n_B$) for inserting a block into a file, we can utilize a cost-of-access analysis for different file allocation methods. In both cases, we calculate the disk operations (reads and writes) required to modify the existing file structure.

Analysis of File System A (Contiguous Allocation) 

Contiguous allocation requires all file data to occupy a single, continuous set of blocks. Inserting a new block into the middle of such a file necessitates shifting subsequent data to maintain continuity.

Mechanism for insertion at position 51:

• Shifting existing data: To vacate position 51, every block from index 51 to 100 must move forward by one. This involves 50 individual blocks.
• Operation per shift: Each of the 50 blocks must be read from its current location and written to its new location (1 Read + 1 Write).
• Insertion: The new block is then written into the now-empty position 51.

Calculation for $n_A$:

$n_A = (50 \text{ blocks} \times 2 \text{ operations/block}) + 1 \text{ final write}$ $n_A = 100 + 1 = \mathbf{101}$

---

Analysis of File System B (Linked Allocation)

Linked allocation uses pointers within each block to identify the next block in the sequence. To insert a block, we only need to modify the link between two existing blocks.

Mechanism for insertion between block 50 and 51:

• Traversal: To find block 50, the system must read through the chain starting from the head. This requires 50 sequential reads.
• Creating the new block: The new block is written to an available location on disk with its pointer set to address block 51 (1 Write).
• Updating the link: Block 50 must be rewritten so that its pointer now addresses the new block instead of block 51 (1 Write).

Calculation for $n_B$:

$n_B = 50 \text{ reads} + 1 \text{ write (new block)} + 1 \text{ write (block 50 update)}$ $n_B = 50 + 2 = \mathbf{52}$

---

Final Summation:

Total operations = $n_A + n_B$

Total operations = $101 + 52 = \mathbf{153}$

Final Answer:

The value of $n_A + n_B$ is 153.