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

Step 1: Analyze File System A (Contiguous Allocation)

In contiguous allocation, all blocks must be stored consecutively on disk.

Process when inserting a block in the middle:

To insert a new block at position 51, we must shift all blocks from position 51 to 100 forward by one position:

1. Push block 100 → position 101 (1 read + 1 write = 2 accesses)
2. Push block 99 → position 100 (1 read + 1 write = 2 accesses)
3. Continue this process...
4. Push block 51 → position 52 (1 read + 1 write = 2 accesses)
5. Now position 51 is empty
6. Write the new block to position 51 (1 write = 1 access)

Calculation:

$$n_A = 50 \text{ blocks to shift} \times 2 \text{ accesses per block} + 1 \text{ write for new block}$$

$$n_A = 50 \text{ reads} + 50 \text{ writes} + 1 \text{ write}$$

$$n_A = 101 \text{ operations}$$

Step 2: Analyze File System B (Linked Allocation)

In linked allocation, each block contains a pointer to the next block in the chain.

Process when inserting a block in the middle:

To insert a new block between block 50 and block 51:

1. Access blocks 1 to 50: We need to traverse the linked list from the beginning to reach block 50 = 50 read operations
2. Read block 50: To get its current next pointer (pointing to block 51) = 1 read operation (included in the 50 reads above)
3. Write the new block: Write the new block with a pointer to block 51 = 1 write operation
4. Update block 50: Modify block 50's pointer to point to the new block instead of block 51 = 1 write operation

Calculation:

$$n_B = 50 \text{ reads (to traverse to block 50)} + 1 \text{ write (new block)} + 1 \text{ write (update block 50)}$$

$$n_B = 50 + 1 + 1 = 52 \text{ operations}$$

Step 3: Calculate Total Operations

$$n_A + n_B = 101 + 52 = 153$$

Answer

The value of $n_A + n_B$ is 153.