• There are three typical file allocation methods:

  • Contiguous Allocation

  • Linked 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.

File Allocation Table

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.

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.

• File blocks are chained into a linked-list.

• The directory entry has pointers to the first and the last file blocks.

• Append is difficult to do without last pointer.

Advantages:

• File size does not have to be specified.

• No external fragmentation.

Disadvantages:

• It does sequential access efficiently and is not for direct access.

• Each block contains a pointer, wasting space.

• Blocks scatter everywhere and a large number of disks seek may be necessary.

Indexed Allocation:

• 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.

• The indexed allocation suffers from wasted space. The index block may not be fully used (i.e., internal fragmentation).

• The number of entries of an index table determines the size of a file. To overcome this problem, we can have multiple index blocks and chain them into a linked list.

• We can also have multiple index blocks, but make them a tree just like the indexed access method.

• Another alternative is that we can have a combination of both.