Linked List Allocation

Introduction

Generally, files are stored in secondary storage devices such as hard disks. So to manage the space of hard disks efficiently and store the files fastly the Operating System uses file allocation methods. 

The file system divides the file logically into multiple blocks. These blocks now need to be stored in a secondary storage device such as a hard disk. The hard disk contains multiple sectors or physical blocks in which the data actually reside. Now the file system will decide where to store these blocks of a file in the sectors of the hard disk using file allocation methods.

In this article, we will study the Linked List Allocation method.

What is the Linked List Allocation method?

The linked list allocation method comes under non-contiguous file allocation methods. This method is basically used to overcome the drawback of the contiguous file allocation method.

First, let’s get a quick recap of the drawback of the contiguous file allocation method.

Drawbacks of contiguous file allocation

1. It causes external fragmentation.
2. If an existing file grows in size, we can’t store it contiguously.

Now, to understand linked list allocation, we consider file A. This file A is divided into five blocks named B1, B2, B3, B4, and B5.

The secondary memory, i.e. the hard disk, is divided into disk blocks or sectors. 

We will store the first block of file A,i.e. B1, on disk block 2.

Similarly, we will store block B2 at disk block 7, block B3 at disk block 9, block B4 at disk block 11 and block B5 at disk block 14.

Note: The blocks of a file are allotted disk blocks based on the availability of disk blocks. 

Since we are doing linked list allocation, a pointer is maintained along with the data, which stores the address of the following file block. So, disk block 2 will contain a pointer to disk block 7, disk block 7 will contain a pointer to disk block 9, disk block 9 will contain a pointer to disk block 11, disk block 11 will contain a pointer to disk block 14 and disk block 14 will contain a pointer -1 (since it is the last block). Thus, in the hard disk, a disk block contains two things - data of the file (block) and a pointer that points to the next block's address.

Now you must be thinking that we have decided the disk blocks to be allotted to the blocks of the file but what if we want this file in future? How will the operating system find the file for us?

Well, the operating system maintains a directory in which it stores the name of the file, its starting block, and its ending block. All these values are initialized to nil. As soon as a file is saved, the operating system finds an empty block in the hard disk and allows it to the file block. The directory structure for file A will be- 

Directory

Hence, the below figure shows how the blocks of the file will get allocated in the disk block:

“Also See, Internal and External Fragmentation“