Awesome q2a theme
0 votes
32 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.
ago in Operating System by (20 points) | 32 views

1 Answer

+1 vote
Best answer

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.

For Linked:

  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
  2. Linked: 52 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.

For Linked:

  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
  2. Linked: 52 operations
  3. Indexed: 1 operation
ago by (1.2k points)
selected ago by
0
@shashin,

In case of linked (removing),

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?
+1

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.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Jan 2020
  1. shashin

    1163 Points

  2. Vimal Patel

    307 Points

  3. Deepakk Poonia (Dee)

    305 Points

  4. Debapaul

    237 Points

  5. Satbir

    192 Points

  6. SuvasishDutta

    137 Points

  7. Pratyush Priyam Kuan

    118 Points

  8. tp21

    108 Points

  9. DukeThunders

    96 Points

  10. pranay562

    95 Points

Monthly Top User and those within 60% of his/her points will get a share of monthly revenue of GO subject to a minimum payout of Rs. 500. Current monthly budget for Top Users is Rs. 75.
2,989 questions
1,509 answers
8,936 comments
89,814 users