Operating System:Allocation methods

November 5th, 2011 by admin | No Comments | Filed in File systems, Operating Systems

Contiguous allocation:

In this method the files occupy a set of contiguous blocks on the disk. Ie the parts of a file are stored as a continuous block in the disk, files parts are not fragmented around the disk. One advantage of using this method is that disk movements are reduced since the next block we have to get is the just near to the current block. The directory entry for this system has the address of the starting block and the length of the area allocated for this file. Consider an example a file starts at location b and has a length of n blocks. The blocks occupied by the file will be b,b+1,b+2….. b+n-1. The summary is a that file are stored as a full unit at once.

This method has the problem of external fragmentation. Since space is continuously taken and freed there generates a lot small holes which is inappropriate for most of the files. The freed spaces all together make a large amount but since they are not in contiguous fashion they cannot be used and the spaces are wasted. So to tackle this problem we have to defragment it which is a very time consuming process and during defragmentation the system is unavailable for any purposes.

Linked allocation

In linked allocation the directory only contains the pointer to the first and last blocks of the file. All the intermediate blocks are linked together, each block has a pointer to the next block. While traversing a file these pointer are used for finding the next file. One advantage of using this method is that there is no external fragmentation, and any free space any where on the disk can be used. The file size can also grow as long as there is free space available.

To denote a empty file the pointer in the directory is initiated to nil, and field size is also left to zero.

This method only supports sequential access and direct access cannot be allowed in this. ie to find 5th block of a file we cannot go directly to the 5th block, but we have to traverse from the first block onwards. But imagine a situation in which one block is damaged and the next block cannot be found out !! the entire file will be lost. A solution to this problem is to use doubly linked list or to store the file name and relative block number in each block.
Another disadvantage is that a small amount of space is lost in every block to store the pointer to the next block. A solution to this problem is to group the blocks into clusters. A cluster is addressed not the individual block, this lead to saving of the space used by the pointers. But internal fragmentation is also high because if a cluster is half fill it leads to a lots of blocks not filled.

An important alteration to the linked allocation is the FAT system. A space in each partition is reserved to contain the table. It has entry for each block and is indexed by the block number. Like linked allocation FAT is also used as a linked list. The directory entry contain the pointer to first block. Table entry indexed by that block number has the pointer to the next block. This chain ends when a block with a table entry value end of file is met. Adding a new block to a file is simple
First we search for a table entry which has a end of file value.
The first entry found is altered and the end of file value is replaced by the pointer to the newly added block.

Indexed allocation:

The directory contain the address of a structure called the index block. It is the index box which has all the pointer to the blocks a file has. To read the 5th block we use the 5th index block entry in the index box. At first when a file is created all the index block entries are nil. Suppose we are writing at the ith block , its address is found out and entered into the index block as the ith index block entry.

External fragmentation is reduced highly here. But a lot of space is wasted to store the index block and the directory and also a lot of over head is there for processing the index block.Some times the space required by the index block cannot be determined early or some times the space alloted is too small. So we need some mechanism to go around this .

Linked scheme:

For large files the required index block could be very large, in this we use mutiple index block and the last entry in a index block is used to link to other index block.

Multilevel Index:

Multiple levels of index blocks are used . One level is used to point to the next level, the last level points to the actual block.

Combined scheme:

In combined scheme some of the first pointer point to direct blocks. After that set of pointers the next pointer point to single indirect pointer .The next one point double indirect pointer , the third one point to triple indirect pointer.

Tags: , , , , , , , ,