11.1

Given a file with 100 blocks, how many disk I/O operations do the following procedures require for the various allocation strategies. This solution assumes that in contiguous allocation the length of the file (in blocks) and the pointer to the first block is stored in memory. This assumes that the linked allocation method has a pointer to the first, a pointer to the last block, and the length of the file are stored in memory and each block only has a pointer to the next block and not a pointer to the previous block. It assumes that in indexed allocation the index is completely in memory.

We will also be ignoring the cost of manipulating the free blocks list. However, if we were to take this into account for each add, it would cost the same as a remove from the beginning with linked allocation method (1 operation) and each remove would be the same as the cost of adding to the beginning of the with the linked allocation (1 operation). This is assuming that the free blocks list is actually implemented as a linked list with pointers to the first block in memory.

  1. The block is added at the beginning.
    contiguous allocation
    201. Each block must be shifted over to the next block. This involved one read and one write per block. Then the new block must be written.
    linked allocation
    1. Just write the new block making it point to the next block. Update the first block pointer in memory.
    indexed allocation
    1. Just write the new block and update the index in memory.

  2. The block is added to the middle.
    contiguous allocation
    101. 50 blocks (the second half) must be shifted over one block and the new block must be written. As before, the shift takes one read operation and one write operation.
    linked allocation
    52. I must read 50 blocks to find the middle. Then I must write my new block somewhere with the next block pointing to the block after the 50th block. Then I must write the 50th block to point to this new block.
    indexed allocation
    1. Just write the new block and update the index in memory.

  3. The block is added at the end
    contiguous allocation
    1. Just write the new block.
    linked allocation
    3 (assuming that in order to modify the a block's next block pointer, I must first read the whole block in, then write the whole block out just with that pointer changed). First I read the last block as given by the last block pointer, then I write my new block, then I write the last block back modifying its next block pointer to point to my new block, then I update my last block pointer in memory.
    indexed allocation
    1. Just write the new block and update the index in memory.

  4. The block is removed from the beginning.
    contiguous allocation
    0. Just point the first block pointer to the second block.
    linked allocation
    1. Read in the first block to get the second block's pointer and then set the first block pointer to point to the second block.
    indexed allocation
    0. Just remove the block from the index in memory.

  5. The block is removed from the middle.
    contiguous allocation
    98. Assuming that we are removing the 51st block, we will have to move 49 blocks one block over this takes a read and a write operation each.
    linked allocation
    52. It takes 51 reads to find the pointer to the 52nd block, then we need to update the 50th block's next block pointer with this value.
    indexed allocation
    0. Just remove the block from the index in memory.

  6. The block is removed from the end.
    contiguous allocation
    0. Just update the length information stored in memory.
    linked allocation
    99 or 100. We need to update the last block pointer with the second to last block and the only way to get the second to last block is to read the preceding 99 blocks. Then we probably want to mark the 99th block (the new last block) as having a null pointer and this would give the 100th operation. We save the new last block in our last block pointer in memory.
    indexed allocation
    0. Just remove the block from the index in memory.

11.2

  1. If a pointer to the free blocks list is lost and a backup copy is not stored on disk, then the free blocks list can be reconstructed by garbage collecting around the file system. All used blocks on a file system are linked to from the root directory. Anything not used is free.

  2. One scheme to insure that a pointer is never lost due to a memory failure is to keep the ``valid'' copy of that pointer on disk in a designated place. Note that a secondary copy of this pointer could be in memory. This pointer could still be lost or corrupted is the system crashes in the middle of an operation that manipulates the free blocks list. Typically when systems crash in the middle of a disk operation they spend a long time at boot time checking and restoring the file system to a consistent state.

    If any of you run Linux boxes, you know that if the system gets powered down before the disk drives are unmounted, then e2fsck gets run on the disks on boot to correct any inconsistencies.