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:

1. contiguous allocation
2. linked allocation
3. 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.

Contiguous allocations

The contiguous allocation method requires each file to occupy a set of contiguous address on the disk. Disk addresses define a linear ordering on the disk. When a file has to be stored on a disk, system search for contiguous set of blocks as required by the file size i.e. system waits till it finds required number of memory blocks in sequence. When space is available system stores the file in the disk and makes an entry in the directory.

The directory entry for a file with contiguous allocation contains

1. Address of starting block
2. Length of the allocation block

With this ordering, accessing block b+1 after block b normally requires no head movement. Contiguous allocation of a file is defined by the disk address and the length of the first block. If the file is n blocks long, and starts at location b, then it occupies blocks b, b+1, b+2, …, b+n-1. The directory entry for each file indicates the address of the starting block and the length of the area allocated for this file.

Linked allocation

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.

Example of a file which has been allocated disk space using linked allocation method.

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 that there is no need to declare the size of a file when that file is created either. 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 $i^{th}$ block of a file, it must start at the beginning of that file and follow the pointers until the $i^{th}$ block is reached. Note that each access to a pointer requires a disk read.

Indexed allocation

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.

a file allocated disk space using Indexed allocation Method

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.