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

1 Answer

+2 votes
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
by (1.9k points)
selected 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?
+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.
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
Top Users 2020 Aug 10 - 16
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    315 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    128 Points

  5. toxicdesire

    53 Points

  6. shashankrustagi2021

    15 Points

  7. Nilabja Sarkar

    12 Points

  8. Mellophi

    11 Points

  9. premu

    10 Points

  10. phaneendrababu

    9 Points

Weekly Top User (excluding moderators) will get free access to GATE Overflow Test Series for GATE 2021
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
Top Users Aug 2020
  1. Arkaprava

    560 Points

  2. jayeshasawa001

    320 Points

  3. SarathBaswa

    288 Points

  4. Ashutosh777

    204 Points

  5. Mellophi

    161 Points

  6. toxicdesire

    53 Points

  7. anurag sharma

    49 Points

  8. shashankrustagi2021

    25 Points

  9. premu

    16 Points

  10. Shaik Masthan

    16 Points

7,792 questions
2,046 answers
11,376 comments
95,121 users