OS File Allocation Methods: Contiguous, Linked and Indexed Allocation

 

v FILE ALLOCATION METHODS:

 

1.    Contiguous Allocation:

o   The contiguous allocation method requires each file to occupy a set of contiguous blocks on the disk.

 

o   Disk address defines a linear ordering on the disc. With this ordering assuming that only one job is accessing the disk assessing block b+1  after block ‘b’ normally requires no head movement.

 

o   When head movement is needed it is only one track.  So the number of disc seeks required for assessing contiguously allocated files is minimal as is seek time when seek is finally needed.

 

o   The IBM VM/CMS OS uses contiguous allocation because it provides such good performance.

 

o   Contiguous allocation of a file is defined by the disc address and length of the first block.

 

o   If the file is ‘n’ blocks long  and starts at location ‘b’,  then it occupies blocks b,b+1,b+2,...,b+n-1.

 

o   The directory entry for each file indicates the address of the starting block and length of the area allocated for this file.

(Contiguous allocation of disk space)

o   Contiguous allocation has some problems however. One difficulty is finding a space for new file.

 

o   Simulations have shown that both first fit and a best fit are more efficient than worst fit in terms of both time and storage utilization.  Neither first fit nor best fit is clearly based in terms of storage utilization but first fit is generally faster.

 

o   The algorithms suffer from the problem of external fragmentation.  As files are allocated and deleted the free disk space is broken into little pieces.

 

o   External fragmentation exists whenever free space is broken into chunks. It becomes a problem when the largest contiguous chunk is insufficient for a request; storage is recommended into number of holes, no one of which is large enough to store the data.

 

o   Another problem with contiguous allocation is determining how much space is needed for a file.  When the file is created, the total amount of space it will need must be found and allocated.  If we allocate too little space to a file, we may find that the file cannot be extended.

 

o   Even if the total amount of space needed for a file is known in advance, pre-allocation maybe inefficient.  A file that grows slowly over a long period must be allocated a space for its final size even though much on that space may be induced for a long time. The file therefore has a large amount of internal fragmentation.

 

o   To minimize drawbacks some use a modified contiguous allocation scheme in which a contiguous chunk of space is allocated initially and then when that amount is not large enough another chunk of continuous space, an extent, is added to the initial allocation.

2.    Linked Allocation:

o   Linked allocation solves all problems of contiguous allocation. With linked allocation a file is a linked list of disc blocks, the disk blocks may be scattered anywhere on the disc.

 

o   The directory contains a pointer to the first and last blocks of the file.

 

o   Each block contains a pointer to the next block.  These pointers are not made available to the user.

 

o   To create a new file, we simply create a new entry in the directory.

 

o   With linked allocation, each directory entry has a pointer to the first disc block of the file.  This pointer is initialized to nil to signify an empty file. The size field is also set to 0.

 

o   Write to the file causes every block to be found by the free space management system and this new block is then written to and is linked to the end of the file.

 

o   To read a file, we simply read blocks by following the pointers from block to block. There is no external fragmentation with linked allocation and any free block on the free space list can be used to satisfy a request.

 

o   The size of a file does not need to be declared when that file is created.  A file can continue to grow as long as free blocks are available.

 

o   The major problem is that it can be used effectively only for sequential access files.

 

o   To find the ‘i^th’ block of a file, we must start at the beginning of that file and follow the pointers until we get to the ‘i^th’ block.

 

o   Each access to a pointer requires a disk read and sometimes a disk seek.  Consequently it is inefficient to support a direct access capability for a linked allocation files.

 

o   The usual solution to this problem is to collect blocks into multiples called clusters and allocate the clusters rather than blocks.  This method allows the logical to physical block mapping to remain simple but improve disk throughput and decreases the space needed for a block allocation and free list management.

o   Yet another problem of linked allocation is reliability.  Since the files are linked together by pointers scattered all over the disc consider what would happen if a pointer were lost or damaged.

 

o   Partial solutions are to use doubly linked list or to store the filename and relative block number in each block; however these schemes require even more overhead for each file.

 

o   An important variation on the linked allocation method is the use of file allocation table (FAT).  This simple but efficient method of disk space allocation is used by MS DOS and OS/2 operating systems.

 

o   A section of disc at the beginning of each partition is set aside to contain the table.  The table has one entry for each disk block and is indexed by block number.  The FAT is used much as is a linked list.  The directory entry contains the block number of the first block of the file.  The table entry indexed by that block number then contains the block number of the next block in the file.  This chain continues until the last block which has a special end of file value as the table entry.  Unused blocks are indicated by a 0 table value.

(Linked allocation of disk space)

3.    Indexed Allocation:

o   Linked allocation solves the external fragmentation and size declaration problems of contiguous allocation.

 

o   However in the absence of a FAT, linked allocation cannot support efficient direct access since the pointers to the blocks are scattered with the blocks themselves all over the disk and need to be retrieved in order.

 

o   Indexed allocation solves this problem by bringing all the pointers together into one location:  the index block.

o   Each file has its own index block which is an array of disk block addresses. The ‘i^th’ entry in the index block points to the ‘i^th’ block of the file. The directory contains the addresses of the index block.

(Indexed allocation of disk space)

o   To read the i^th block, we use the pointer in the i^th index block entry to find and read the desired block.

 

o   When the file is created, all pointers in the index block are set to nil.  When the i^th block is first written, a block is obtained from the free space manager, and its address is put in the i^th index block entry.

 

o   Indexed allocation supports direct access without suffering from external fragmentation because any free block on the disk may satisfy a request for more space.

 

o   Indexed allocation does suffering from wasted space.  The pointer overhead of the index block is generally greater than the pointer overhead of linked allocation.

 

o   If the index block is too small, however it will not be able to hold enough pointers for a large file and a mechanism will have to be available to deal with this issue.