Files are usually stored on secondary storage devices such as disk. These files are then called back when needed. As part of their implementation, files must be stored in the hard disk. This has to be done in such a way that the disk space is utilized effectively and the files can be accessed quickly.

There are three methods of file allocation:

Contiguous allocation

Linked allocation

Indexed allocation

1. Contiguous Allocation:

a. Contiguous allocation requires that each file occupy a set of contiguous blocks on the disk. The word contiguous means continuous

b. Because of contiguous allocation, there is minimal or no disk-head movement which reading/writing the blocks of the file.

c. The seek time is minimal over here. Consequently, access time of a file and the I/O performance is greatly improved.

d. To access a file, there we only need to know the starting location and length of the file which are stored in the directory as shown in the figure.

e. It has certain problems associated with it:

• Finding the space for a new file (usually done with First fit and Best Fit Algorithms)

• Problem of external fragmentation. It occurs whenever free space is broken into tiny chunks.

• Compaction (which is a solution for fragmentation) can take up lot of time and may need system to be down, wherein normal operation will not be permitted.

• Determining space to be allocated for file, especially if it needs to grow. (For e.g. the size of a Word file grows on increasing as new data is typed in)

Advantage:

• Contiguous allocation is easy to implement.

Disadvantage:

• It can be considered as a form of dynamic memory allocation, and external fragmentation may occur and compaction may be needed.

• It is difficult to estimate the file size. The size of a file may grow at run time and may be larger than the specified number of allocated blocks. In this case, the OS must move the blocks in order to provide mode space. In some systems, this is simply an error.

2. Linked Allocation:

With the linked allocation approach, disk blocks of a file are chained together with a linked-list. The directory entry of a file contains a pointer to the first block and a pointer to the last block.

To create a file, we create a new directory entry and the pointers are initialized to nil. When a write occurs, a new disk block is allocated and chained to the end of the list.

a. This method solves the problems associated with contiguous allocation.

b. Here the blocks of a single file can be scattered anywhere on the disk. The reason because the entire file is implemented as a Linked List.

c. Here every file is an element of Linked List (similar to concept of Linked List in Data Structures).

d. The directory maintained by the OS contains a pointer to the first and the last blocks of a file.

e. Each block of a file contains a pointer to the next block after it in the list.

f. For creating a new file, we need to just create a new entry in the directory and not to search for sufficient space as in contiguous.

g. The free space management system allocates space to a block for writing and is then appended to the end of the List.

h. To Read a file, we need to follow the pointers from each block.

i. Advantages include no external fragmentation, size of file need not be declared at start, a file can grow as long as free blocks are available on disk.

j. Disadvantages: It works perfectly for Sequential access only, space needs to be allocated in block for pointers, error in pointer links can lead to Invalid read.

3. Indexed allocation:

Indexed Allocation With the contiguous allocation method, a user must indicate the file size before creating the file.Then, the operating system searches the disk to find contiguous disk blocks for the file.

The directory entry is easy. It contains the initial disk address of this file and the number of disk blocks.Therefore, if the initial address is b and the number of blocks is n, the file will occupy blocks b, b+1, b+2, …,b+n-1.

Each file has an index block that is an array of disk block addresses. The i-th entry in the index block points to the i-th block of the file. A file’s directory entry contains a pointer to its index.

Hence, the index block of an indexed allocation plays the same role as the page table. Index allocation supports both sequential and direct access without external fragmentation.

a. In indexed allocation method, all the pointers (pointing to the next block in the Linked list) are gathered together into one location known as Index Block.

b. In the earlier method (i.e. Linked Allocation) the pointers along with the blocks were scattered across the disk and needed to be retrieved in order by visiting each block for access the file.

c. This problem gets eliminated here.

d. Each file has an index block of its own, which is an array of disk-block addresses.

e. The kth entry of the index-block is a pointer to the kth block of the file.

f. When a file is created initially, all pointers in the index block are set to null value. As new blocks are written, the pointers are modified accordingly.

g. Indexed allocation supports direct access and does not suffer from any external fragmentation.

h. Indexed allocation suffers from the problem of wasted space. E.g. if a file is made up of two blocks only, then a huge amount of space will be wasted.