Linked Allocation

• The second method for storing files is to keep each one as a linked list of disk blocks, as shown in Fig. 8.

  Figure 8: Storing a file as a linked list of disk blocks.

  
• Linked allocation solves all problems of contiguous allocation. With linked allocation, each file is a linked list of disk blocks;
  • The disk blocks may be scattered anywhere on the disk.
  • The directory contains a pointer to the first and last blocks of the file.
  • For example, a file of five blocks might start at block 9 and continue at block 16, then block 1, then block 10, and finally block 25 (see Fig. 9 ).

  Figure 9: Linked allocation of disk space.

  
• To create a new file, we simply create a new entry in the directory. The pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. The size field is also set to O.
• A write to the file causes the free-space management system to find a free block, and this new block is written to and is linked to the end of the file.
• To read a file, we simply read blocks by following the pointers from block to block.
• There is no external fragmentation with linked allocation, and any free block on the free-space list can be used to satisfy a request. No space is lost to disk fragmentation (except for internal fragmentation in the last block).
• The size of a file need not be declared when that file is created. A file can continue to grow as long as free blocks are available.
• Consequently, it is never necessary to compact disk space.
• The major problem is that it can be used effectively only for sequential- access files.
  • To find the $i^{th}$ block of a file, we must start at the beginning of that file and follow the pointers until we get to the $i^{th}$ block.
  • Each access to a pointer requires a disk read, and some require a disk seek.
• Consequently, it is inefficient to support a direct-access capability for linked-allocation files.
• Another disadvantage is the space required for the pointers.
  • If a pointer requires 4 bytes out of a 512-byte block, then 0.78 percent of the disk is being used for pointers, rather than for information.
• The usual solution to this problem is to collect blocks into multiples, called clusters, and to allocate clusters rather than blocks.
  • For instance, the file system may define a cluster as four blocks and operate on the disk only in cluster units.
  • Pointers then use a much smaller percentage of the file's disk space.
  • Improves disk throughput (because fewer disk-head seeks are required) and decreases the space needed for block allocation and free-list management.
  • The cost of this approach is an increase in internal fragmentation, because more space is wasted when a cluster is partially full than when a block is partially full.
• Yet another problem of linked allocation is reliability.
  • Recall that the files are linked together by pointers scattered all over the disk, and consider what would happen if a pointer were lost or damaged.
  • A bug in the OS software or a disk hardware failure might result in picking up the wrong pointer.
• An important variation on linked allocation is the use of a file-allocation table (FAT). This simple but efficient method of disk-space allocation is used by the MS-DOS and OS/2 OSs.
  • A section of disk at the beginning of each volume is set aside to contain the table.
  • The table has one entry for each disk block and is indexed by block number.
  • The FAT is used in much the same way as a linked list. The directory entry contains the block number of the first block of the file.
  • The table entry indexed by that block number contains the block number of the next block in the file.
  • This chain continues until the last block, which has a special end-of-file value as the table entry.
• Unused blocks are indicated by a 0 table value. Allocating a new block to a file is a simple matter of finding the first O-valued table entry and replacing the previous end-of-file value with the address of the new block.
• An illustrative example is the FAT structure shown in Fig. 10 for a file consisting of disk blocks 217, 618, and 339.

  Figure 10: File allocation table.

  
• The FAT allocation scheme can result in a significant number of disk head seeks, unless the FAT is cached.
• The primary disadvantage of this method is that the entire table must be in memory all the time to make it work.
  • With a 20-GB disk and a 1-KB block size, the table needs 20 million entries.
  • Each entry has to be a minimum of 3 bytes. For speed in lookup, they should be 4 bytes.
  • Thus the table will take up 60 MB or 80 MB of main memory all the time.