Allocation Methods

ALLOCATION METHODS

   The main problem is how to allocate space to these files so that disk space is utilized effectively and files can be accessed quickly .

   There are there major methods of allocating disk space:

1.     Contiguous Allocation

2.     Linked Allocation

3.     Indexed Allocation

1. Contiguous Allocation

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

ü Contiguous allocation of a file is defined by the disk address and length (in block units) 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.

Disadvantages:

1.       Finding space for a new file.

v The contiguous disk space-allocation problem suffer from the problem of external fragmentation. As file are allocated and deleted, the free disk space is broken into chunks. It becomes a problem when the largest contiguous chunk is insufficient for a request; storage is fragmented into a number of holes, no one of which is large enough to store the data.

2 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 an allocated how does the creator know the size of the file to be created?

 If  we  allocate  too  little  space  to  a  file,  we  may find  that  file  cannot be extended.

The other possibility is to find a larger hole, copy the contents of the  file to  the  new space,  and  release  the  previous  space.  This  series  of actions may be repeated as long as space exists, although it can be time –consuming.  However,  in  this case, the  user never  needs  to  be  informed explicitly  about  what  is  happening ;  the system continues despite the problem, although more and more slowly. 

 Even if the total amount of space needed for a file is known in advance pre-allocation may be inefficient.

 A file that  grows  slowly  over  a  long  period  (months  or  years)  must be allocated enough space  for  its final  size,  even though  much of  that space may  be unused  for a long time the file, therefore has  a large amount of internal fragmentation.

To overcome these disadvantages:

 Use a modified contiguous allocation scheme, in which a contiguous chunk of space called as an extent is allocated initially and then, when that amount is not large enough another chunk of contiguous space an extent is added to the initial allocation.

 Internal fragmentation can still be a problem if the extents are too large, and external fragmentation can be a problem as extents of varying sizes are allocated and deallocated.

2. Linked Allocation

 Linked allocation solves all problems of contiguous allocation.

 With linked allocation, each file is a linked list of disk blocks, the disk blocksmay be scattered any where on the disk.

 The directory contains a pointer to the first and last blocks of the file. For example, a file of five blocks might start at block 9, continue at block 16, then block 1, block 10, and finally bock 25.

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

 There is no external fragmentation with linked allocation, and any free block on the free space list can be used to satisfy a request.

 The size of a file does not need to the declared when that file is created. A file can continue to grow as long as free blocks are available consequently, it is never necessary to compacts disk space.

Disadvantages:

1.                              Used effectively only for sequential access files.

· To find the ith block of a file, we must start at the beginning of that file, and follow the pointers until we get to the ith block. Each aces to a pointer requires a disk read, and sometimes a disk seek consequently, it is inefficient to support a direct- access capability for linked allocation files.

2. Space required for the pointers

·       If a pointer requires 4 bytes out of a 512-byte block, then 0.78 percent of the disk is being used for pointers, rather than for information.

·         Solution to this problem is to collect blocks into multiples, called  clusters, and to

allocate the clusters rather than blocks. For instance, the file system may define a clusters as 4 blocks, and operate on the disk in only cluster units.

3. Reliability

•Since the files are linked together by pointers scattered all over the disk hardware failure might result in picking up the wrong pointer. This error could result in linking into the free- space list or into another file. Partial solution are to use doubly linked lists or to store the file names in a relative block number in each block; however, these schemes require even more over head for each file.

File Allocation Table (FAT)

ü An important variation on the linked allocation method is the use of a file allocation table(FAT).

ü This simple but efficient method of disk- space allocation is used by the MS-DOS and OS/2 operating systems.

ü A section of disk at beginning of each partition is set aside to contain the table.

ü The table has entry for each disk block, and is indexed by block number.

ü The FAT is much as is a linked list.

ü The directory entry contains the block number the first block of the file.

ü The table entry indexed by that block number 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.

ü Allocating a new block file is a simple matter of finding the first 0 – valued table entry, and replacing the previous end of file value with the address of the new block.

ü The 0 is replaced with the end – of – file value, an illustrative example is the FAT structure for a file consisting of disk blocks 217,618, and 339.

3. Indexed Allocation

v Linked allocation solves the external – fragmentation and size- declaration problems of contiguous allocation.

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

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

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

ü The ith entry in the index block points to the ith block of the file.

ü The directory contains the address of the index block .

ü To read the ith block, we use the pointer in the ith index – block entry to find and read the desired block this scheme is similar to the paging scheme .

ü When the file is created, all pointers in the pointers in the index block are set to nil. when the ith block is first written, a block is obtained from the free space manager, and its  address is put in the ith index – block entry.

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

Disadvantages

1.Pointer Overhead

Indexed allocation does suffer from wasted space. The pointer over head of the index block is generally greater than the pointer over head of linked allocation.

2. Size of Index block

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:

Linked Scheme: An index block is normally one disk block. Thus, it can be read and written directly by itself. To allow for large files, we may link together several index blocks.

Multilevel index: A variant of the linked representation is to use a first level index block to point to a set of second – level index blocks.

Combined scheme:

o  Another alternative, used in the UFS, is to keep the first, say, 15 pointers of the index block in the file’s inode.

§   The first 12 of these pointers point to direct blocks; that is for small ( no more than 12 blocks) files do not need a separate index block

o  The next  pointer is the address of a single indirect block.

ü   The single indirect block is an index block, containing not data, but rather the addresses of blocks that do contain data.

o  Then there is a double indirect block pointer, which contains the address of a block that contain pointers to the actual data blocks. The last pointer would contain pointers to the actual data blocks.

o   The last pointer would contain the address of a triple indirect block.