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 drive, 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 linked to each other.
With contiguous allocation, each file occupies 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/Random access are supported by the contiguous allocation. We can say that it supports random access as using Disk Block Address we can jump directly on the required location.
The disadvantage of contiguous allocation is that it is often difficult to increase the size of a file as the next contiguous block may not be free. 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. Internal fragmentation may exist in the last disk block of a file.
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 block of a file, it must start at the beginning of that file and follow the pointers until the 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. One disk block is just used to store DBAs (disk block addresses) of a file.
Every file is associated with its own index node. If a file is very large then one disk block may not be sufficient to hold all associated DBAs of that file. If a file is very small then some disk block space is wasted as DBAs are less and a single disk block could still hold more DBAs.
This method solves the problem of fragmentation as the blocks can be stored at any location.