Table of contents
1.
Introduction
2.
What is the Linked List Allocation method?
3.
Advantages of Linked List Allocation
4.
Disadvantages of Linked List Allocation
5.
Frequently Asked Questions
6.
What are the different methods of file allocation in the operating system?
7.
What is the difference between contiguous allocation and non-contiguous file allocation methods?
8.
 
9.
 
10.
 
11.
 
12.
 
13.
What is the difference between linked list allocation and indexed allocation methods?
14.
Conclusion
Last Updated: Mar 27, 2024

Linked List Allocation

Author Pakhi Garg
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?
Operating Systems

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.

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.

Illustration Image

 

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

Illustration Image

 

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

Illustration Image

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.

Illustration Image

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.

Illustration Image

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

 

file                   start               end

                                         14

 

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

Illustration Image

Also See, Internal and External Fragmentation

Advantages of Linked List Allocation

  1. There is no external fragmentation since all the blocks are stored non-contiguously.
  2. If the file size grows in the future, we can easily accommodate it in the disk by creating a new file block and storing it separately. We just need to update the pointer of the last block from -1 to the address of the new block.

Disadvantages of Linked List Allocation

  1. This method has a large seek time. All the file blocks are randomly distributed on the disk so, a large number of seeks are needed to access every block individually.
  2. In this method, random access to blocks is difficult. Suppose we want to access block 4, i.e. B4 of file A. So, for that, we need to traverse all the blocks before B4, i.e. B1, B2, and B3, to get to B4.
  3. There is an overhead of pointers in this method.

 

You can also read about the Multilevel Feedback Queue Scheduling.

Frequently Asked Questions

What are the different methods of file allocation in the operating system?

There are two methods of file allocation in the operating system. These are-

  1. Contiguous allocation
  2. Non-contiguous allocation

Non-contiguous allocation is further divided into two methods -

  1. Linked list allocation
  2. Indexed allocation

 

What is the difference between contiguous allocation and non-contiguous file allocation methods?

S.No Contiguous allocation Non-contiguous allocation
1. Contiguous allocation allocates consecutive blocks of the disk to the file blocks. Non-contiguous allocation allocates random blocks of the disk to the file blocks based on the disk block availability. 
2. This method executes faster. This method executes slower.
3.  This method suffers both internal and external fragmentation. This method overcomes both internal and external fragmentation.
4. Memory wastage is more. Memory wastage is less.
5. There is less overhead. There is more overhead.

 

 

 

 

 

 

 

Must Read Evolution of Operating System

What is the difference between linked list allocation and indexed allocation methods?

S.No Linked list allocation Indexed allocation
1. This method does not allow direct access to file blocks. This method allows direct access to file blocks.
2. The pointer overhead in linked list allocation is less than indexed allocation. The pointer overhead in indexed allocation is more than linked list allocation.
3. For small files, the linked list allocation would keep space of only one pointer per block. For small files, the indexed allocation would keep one entire block for the pointers which is insufficient in terms of memory utilization.

Conclusion

In this article, we went through the linked list file allocation method. We also discussed the advantages and disadvantages of this method.

Reader, don’t stop here. Start your learning journey in the operating system with Coding Ninjas by taking the OS course.

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy Learning!

Live masterclass