When a process has to writes data to a file, the kernel must allocate disk blocks from the file system for direct data blocks and, sometimes, for indirect blocks. The super block of file system contains an array that is used to cache the numbers of free disk blocks in the file system.

The utility program called mkf's (make file system) arranges the data blocks of a file system in a linked list, such that each link of the list is a disk block that contains an array of free disk block numbers, and one array entry is the number of the next block of the linked list. The Figure shows an example of the linked list, in this the first block is the super block free list and all other blocks on the linked list contain more free block numbers. When the kernel wants to allocate a block from a file system (algorithm alloc), it finds the next available block in the super block list and allocates it.

Once it is done, the block cannot be reallocated until it becomes free. If the allocated block is the last available block in the super block cache, the kernel treats it as a pointer to a block that contains a list of free blocks. It reads the block, populates the super block array with the new list of block numbers, and then proceeds to use the original block number.

It allocates a buffer for the block and clears the buffer's data (zeros it). The disk block has now been assigned, and the kernel has a buffer to work with. If the file system contains no free blocks, then calling process receives an error. If a process writes a lot of data to a file, it repeatedly asks the system for blocks to store the data, but the kernel assigns only one block at a time.

The program tries to organise the original linked list of free block numbers so that block numbers distribute to a file are near each other. This helps performance, because it reduces disk seek time and latency when a process reads a file sequentially. Figure depicts block numbers in a regular pattern, probably based on the disk rotation speed.

Unfortunately, the order of block numbers on the free block linked lists breaks down with heavy use as processes write files and remove them, because block numbers enter and leave the free list at random. The kernel makes no attempt to sort block numbers on the free list.

The algorithm is for freeing a block is the reverse of the one for allocating a block. If the super block list is not full, the block number of the newly freed block is placed on the super block list. If, though, the super block list is full, the newly freed block becomes a link block; the kernel writes the super block list into the block and writes the block to disk.

After that it places the block number of the newly freed block in the super block list: That block number is the only member of the list. The figure shows a sequence of alloc and free operations, starting with one entry on the super block free list. The kernel frees block 949. It then places the block number on the free list. After it allocates a block and also removes block number 949 from the free list. At the end, it allocates a block and removes block number 109 from the free list. Because the super block free list is now empty, the kernel replenishes the list by copying in the contents of block 109, the next link on the linked list. The figure shows the full super block list and the next link block, block 211.

The algorithms for assigning and freeing nodes and disk blocks are similar in that the kernel uses the super block as a cache containing indices of free resources, block numbers, and i-node numbers. It maintains a linked list of block numbers such that every free block number in the file system appears in some element of the linked list, but it maintains no such list of free modes. There are three reasons for the different treatment.

Algorithm for Allocating Disk Block

Input : Number of File system
Output : New block buffer
{
    while(superbiock is locked)
    {
        sleep(event superblock not locked);
        remove block from superblock free list;
        if(last block is removed from free list)
        {
            lock superblock;
            read the block which is just taken from free list(algo bread);
            copy block number into superblock;
            release block buffer(algo breise);
            Unlock the superblock;
            wake up processes(event superblock not locked);
        }
        get buffer from superblock list for removing the block(algo getblk);
        zero buffer contents;
        Decrement total count of free block;
        mension the superblock as modified;
        return buffer;
}

1. The kernel can determine whether an i-node is free by inspection: If the file type field is clear, the node is free. The kernel doesn’t require other mechanism to describe free nodes. However, it cannot determine whether a block is free just by looking at it. It could not distinguish between a bit pattern that indicates the block is free and data that happened to have that bit pattern. Hence, the kernel needs an external method to identify free blocks, and traditional implementations have used a linked list.

2. Disk blocks prepare themselves to the use of linked lists: A disk block easily holds large lists of free block numbers. But i-nodes have no convenient place for bulk storage of large lists of free mode numbers.

3. Users turns to consume disk block resources more quickly than they consume i-nodes, so the apparent lag in performance when searching the disk for free i-nodes is not as critical as it would be for searching for free disk blocks.