Operating System (2140702)

Contiguous Allocation

• The simplest allocation scheme is to store each file as a contiguous run of disk block.
• Here the first 40 disk blocks are shown, starting with block 0 on the left. Initially, the disk was empty.

Advantages of Contiguous Allocation

• First it is simple to implement because keeping track of where a file’s blocks are is reduced to remembering two numbers: The disk address of the first block and the number of blocks in the file.
• Second, the read performance is excellent because the entire file can be read from the disk in a single operation. Only one seek is needed (to the first block), so data comes in at the full bandwidth of the disk.
• Thus contiguous allocation is simple to implement and has high performance.

Drawbacks of Contiguous Allocation

• Over the course of time, the disk becomes fragmented.
• Initially, fragmentation is not a problem, since each new file can be written at the end of the disk, following the previous one.
• However, eventually the disk will fill up and it will become necessary to either compact the disk, which is expensive, or to reuse the free space in the holes.
• Reusing the space requires maintaining a list of hole.
• However, when a new file is to be created, it is necessary to know its final size in order to choose a hole of the correct size to place it in.

There is one situation in which continuous allocation is feasible and in fact, widely used: on CD-ROMs. Here all the file sizes are known in advance and will never change during use of CD-ROM file system.

---

Linked List Allocation

• Another method for storing files is to keep each one as a linked list of the disk blocks.
• The first word of each block is used as a pointer to the next one. The rest of the block is for data.
• Unlike contiguous allocation, every disk block can be used in this method. No space is lost to disk fragmentation.
• It is sufficient for a directory entry to store only disk address of the first block, rest can be found starting there.

Drawbacks of Linked List Allocation

• Although reading a file sequentially is straightforward, random access is extremely slow. To get to block n, the operating system has to start at the beginning and read the n-1 blocks prior to it, one at a time.
• The amount of data storage in a block is no longer a power of two because the pointer takes up a few bytes. While having an unusual size is less efficient because many programs read and write in blocks whose size is a power of two.
• With the first few bytes of each block occupied to a pointer to the next block, reads of the full block size require acquiring and concatenating information from two disk blocks, which generates extra overhead due to the copying.