Operating System Design/File Systems/Allocation
The main idea behind allocation is effective utilization of file space and fast access of the files. There are three types of allocation:
- contiguous allocation
- linked allocation
- indexed allocation
In addition to storing the actual file data on the disk, the file system also stores metadata about the files: the name of each file, when it was last edited, exactly where it is on the disk, and what parts of the disk are "free". Free areas are not currently in use by the file data or the metadata, and so available for storing new files. (The places where this metadata is stored are often called "inodes", "chunks", "file allocation tables", etc.)
To keep track of the free space, the file system maintains a free-space list which tracks all the disk blocks which are free. To create a file, the required space is reserved for the file and the corresponding space is removed from the free list.
With contiguous allocation, each file has to occupy contiguous blocks on the disk. The location of a file is defined by the disk address of the first block and its length. Both sequential access and direct access are supported by the contiguous allocation. The disadvantage of contiguous allocation is that it is often difficult to find free space for a new file. Moreover, one is often not sure of the space required while creating a new file. The various methods adopted to find space for a new file suffer from external fragmentation.
In linked allocation, each file is a linked list of disk blocks. The directory contains a pointer to the first and (optionally the last) block of the file. For example, a file of 5 blocks which starts at block 4, might continue at block 7, then block 16, block 10, and finally block 27. Each block contains a pointer to the next block and the last block contains a NIL pointer. The value -1 may be used for NIL to differentiate it from block 0.
With linked allocation, each directory entry has a pointer to the first disk block of the file. This pointer is initialized to nil (the end-of-list pointer value) to signify an empty file. A write to a file removes the first free block and writes to that block. This new block is then linked to the end of the file. To read a file, the pointers are just followed from block to block.
There is no external fragmentation with linked allocation. Any free block can be used to satisfy a request. Notice also that there is no need to declare the size of a file when that file is created. A file can continue to grow as long as there are free blocks. Linked allocation, does have disadvantages, however. The major problem is that it is inefficient to support direct-access; it is effective only for sequential-access files. To find the ith block of a file, it must start at the beginning of that file and follow the pointers until the ith block is reached. Note that each access to a pointer requires a disk read.
Linked allocation does not support random access of files, since each block can only be found from the previous. Indexed allocation solves this problem by bringing all the pointers together into an index block. This type of allocation will have a pointer which has the address of all the blocks of a file. This method solves the problem of fragmentation as the blocks can be stored in any location.