195 views
Consider a file currently consisting of 100 blocks. Assume that the file-control block (and the index block, in the case of indexed allocation) is already in memory. In the contiguous-allocation case, assume that there is no room to grow at the beginning but there is room to grow at the end. Also assume that the block information to be added is stored in memory. Calculate how many disk I/O operations are required for contiguous, linked, and indexed (single-level) allocation strategies, if a block is removed from the middle.
| 195 views

For contiguous:

1. you would have to move 49 blocks (half the file) one block to the left, - this will take 49 read + 49 write, 98 operations total. No need to delete the block, overwriting does the same job.

1. You would have to traverse the first 50 blocks of the file sequentially to get to the location - 50 read operations
2. Read the next pointer from the block to be deleted - 1 read operation
3. Update the pointer of the previous block with the above pointer - 1 write operation. Total 52 operations.

For Indexed:

1. Simply get rid of the index entry in memory. This should take no operations.

To summarize:

1. Contiguous: 98 operations
3. Indexed: 0 operations

Note: if it was inserting instead of removing:

For contiguous:

1. you would have to move 50 blocks (half the file) one block to the right, - this will take 50 read + 50 write
2. then insert the new block in the middle. So 101 disk operations total.

1. You would have to traverse the first 50 blocks of the file sequentially - 50 read operations
2. Create the new block somewhere there is a free slot, and point its next pointer to the 51st block - 1 write operation
3. Change the pointer of the 50th block to point to the new block - 1 write operation. So 52 total operations.

For Indexed:

1. Create the new block anywhere - 1 write operation
2. Add an entry in the index block - 0 operations since it is already in memory. So total 1 operation.

To summarize:

1. Contiguous: 101 operations
3. Indexed: 1 operation
by (1.9k points)
selected by
0
@shashin,

3rd point says pointer updation in previous block you took 1 write operation.

My query is-
We have pointer to next block only, then to update pointer in previous don't we need to again traverse it?
+2

I was actually about to add a disclaimer saying 'depending on program efficiency it might go up or down by 1 operation'.

I would do it like this:

while (p->next != middle){
p = p->next;
} //should take 50 reads (or 49 depending on how you interpret 'middle')

//at this point, the block prior to the block to be deleted is in p
blockToBeDeleted = p->next; // 1 read to fetch the block to be deleted
p->next = blockToBeDeleted->next //1 write to update the previous block's next
//no need to traverse it again, since variable p already has it in memory



Implementation based questions are iffy. Hopefully this sort of stuff comes with options..

0
Yes..correct!!
0

I'm actually not convinced that the removal in case of indexed takes 0. I claimed 0 because the question stated

Assume that the file-control block (and the index block, in the case of indexed allocation) is already in memory.

It will take 0 disk operations during the delete, but it definitely has to be written back to the index block at some point.

Let's see what the solution given by the test series is, if the original poster shares it.

0
But, I too agree with ur 0 claim,as they mentioned index within memory!

Let's see what is their solution.
0
this is what the solution says.

The block is removed from the middle.

i. Contiguous: The remaining 49 blocks are moved forward and each move requires 1 read and 1 write, The total number of disk I/O operations is 98 = 2 × 49.

ii. Linked: This is the same as inserting in the middle. The number of disk I/O operations is 52.

iii. Indexed: Shifting the addresses stored in the index one position upward does not need any disk I/O operation.