Operating System Tutorial

What is Operating System Evolution of Operating System Types of Operating System Functions of Operating System What is Kernel and Types of Kernel Operating System Properties Operating System Services Components of Operating System Needs of the Operating System Linux Operating System Unix Operating System Ubuntu Operating System What is DOS Operating System Difference Between Multi-programming and Multitasking What is Thread and Types of Thread Process Management Process State What is Process Scheduler and Process Queue What is Context Switching What is CPU Scheduling Scheduling Algorithm FCFS (First-come-First-Serve) Scheduling SJF (Shortest Job First) Scheduling Round-Robin CPU Scheduling Priority Based Scheduling HRRN (Highest Response Ratio Next) Scheduling Process Synchronization Lock Variable Mechanism TSL Mechanism Turn Variable Mechanism Interested Variable Mechanism What is Producer-Consumer Problem What is Semaphore in Operating System Monitors in Operating System What is Deadlock Deadlock Avoidance Strategies for Handling Deadlock Deadlock Prevention Deadlock Detection and Recovery Resource Allocation Graph Banker’s Algorithm in Operating System Fixed Partitioning and Dynamic Partitioning Partitioning Algorithms What is Paging and Segmentation What is Demand Paging What is Virtual Memory Disk Scheduling Algorithms FCFS and SSTF Disk Scheduling Algorithm SCAN and C-SCAN Disk Scheduling Algorithm Look and C-Look Disk Scheduling Algorithm File in Operating System File Access Methods in Operating System File Allocation Method Directory Structure in Operating System Difference between C-LOOK and C-SCAN Difference between Rotational Latency and Disk Assess Time Trap vs Interrupt How to implement Monitors using Semaphores N-Step-SCAN Disk Scheduling Why is it critical for the Scheduler to distinguish between I/O-bound and CPU-bound programs Difference between C-SCAN and SSTF Difference between SCAN and FCFS Difference between Seek Time and Disk Access Time Difference between SSTF and LOOK

File Allocation Methods in Operating System

File Allocation Methods

There are different kinds of methods that are used to allocate disk space. We must select the best method for the file allocation because it will directly affect the system performance and system efficiency. With the help of the allocation method, we can utilize the disk, and also files can be accessed.

There are various types of file allocations method:

  1. Contiguous allocation
  2. Extents
  3. Linked allocation
  4. Clustering
  5. FAT
  6. Indexed allocation
  7. Linked Indexed allocation
  8. Multilevel Indexed allocation
  9. Inode

There are different types of file allocation methods, but we mainly use three types of file allocation methods:

  1. Contiguous allocation
  2. Linked list allocation
  3. Indexed allocation

These methods provide quick access to the file blocks and also the utilization of disk space in an efficient manner.

Contiguous Allocation: - Contiguous allocation is one of the most used methods for allocation. Contiguous allocation means we allocate the block in such a manner, so that in the hard disk, all the blocks get the contiguous physical block.

We can see in the below figure that in the directory, we have three files. In the table, we have mentioned the starting block and the length of all the files. We can see in the table that for each file, we allocate a contiguous block.

File Allocation Methods

Example of contiguous allocation

We can see in the given diagram, that there is a file. The name of the file is ‘mail.’ The file starts from the 19th block and the length of the file is 6. So, the file occupies 6 blocks in a contiguous manner. Thus, it will hold blocks 19, 20, 21, 22, 23, 24.

File Allocation Methods

Advantages of Contiguous Allocation

The advantages of contiguous allocation are:

  1. The contiguous allocation method gives excellent read performance.
  2. Contiguous allocation is easy to implement.
  3.  The contiguous allocation method supports both types of file access methods that are sequential access and direct access.
  4. The Contiguous allocation method is fast because, in this method number of seeks is less due to the contiguous allocation of file blocks.

Disadvantages of Contiguous allocation

The disadvantages of contiguous allocation method are:

  1. In the contiguous allocation method, sometimes disk can be fragmented.
  2. In this method, it is difficult to increase the size of the file due to the availability of the contiguous memory block.

Linked List Allocation

The linked list allocation method overcomes the drawbacks of the contiguous allocation method. In this file allocation method, each file is treated as a linked list of disks blocks. In the linked list allocation method, it is not required that disk blocks assigned to a specific file are in the contiguous order on the disk. The directory entry comprises of a pointer for starting file block and also for the ending file block. Each disk block that is allocated or assigned to a file consists of a pointer, and that pointer point the next block of the disk, which is allocated to the same file.

Example of linked list allocation

We can see in the below figure that we have a file named ‘jeep.’ The value of the start is 9. So, we have to start the allocation from the 9th block, and blocks are allocated in a random manner. The value of the end is 25. It means the allocation is finished on the 25th block. We can see in the below figure that the block (25) comprised of -1, which means a null pointer, and it will not point to another block.

File Allocation Methods

Advantages of Linked list allocation

There are various advantages of linked list allocation:

  1. In liked list allocation, there is no external fragmentation. Due to this, we can utilize the memory better.
  2. In linked list allocation, a directory entry only comprises of the starting block address.
  3. The linked allocation method is flexible because we can quickly increase the size of the file because, in this to allocate a file, we do not require a chunk of memory in a contiguous form.

Disadvantages of Linked list Allocation

There are various disadvantages of linked list allocation:

  1. Linked list allocation does not support direct access or random access.
  2. In linked list allocation, we need to traverse each block.
  3. If the pointer in the linked list break in linked list allocation, then the file gets corrupted.
  4. In the disk block for the pointer, it needs some extra space.

Indexed Allocation

 The Indexed allocation method is another method that is used for file allocation. In the index allocation method, we have an additional block, and that block is known as the index block. For each file, there is an individual index block. In the index block, the ith entry holds the disk address of the ith file block. We can see in the below figure that the directory entry comprises of the address of the index block.

File Allocation Methods

Advantages of Index Allocation

The advantages of index allocation are:

  1. The index allocation method solves the problem of external fragmentation.
  2. Index allocation provides direct access.

Disadvantages of Index Allocation

The disadvantages of index allocation are:

  1. In index allocation, pointer overhead is more.
  2. We can lose the entire file if an index block is not correct.
  3. It is totally a wastage to create an index for a small file.

A single index block cannot hold all the pointer for files with large sizes.

To resolve this problem, there are various mechanism which we can use:

  1. Linked scheme
  2. Multilevel Index
  3. Combined Scheme
  1. Linked Scheme: - In the linked scheme, to hold the pointer, two or more than two index blocks are linked together. Each block contains the address of the next index block or a pointer.
  2. Multilevel Index: - In the multilevel index, to point the second-level index block, we use a first-level index block that in turn points to the blocks of the disk, occupied by the file. We can extend this up to 3 or more than 3 levels depending on the maximum size of the file.
  3. Combined Scheme: - In a combined scheme, there is a special block which is called an information node (Inode). The inode comprises of all the information related to the file like authority, name, size, etc. To store the disk block addresses that contain the actual file, the remaining space of inode is used. In inode, the starting pointer is used to point the direct blocks. This means the pointer comprises of the addresses of the disk blocks, which consist of the file data. To indicate the indirect blocks, the next few pointers are used. The indirect blocks are of three types, which are single indirect, double indirect, and triple indirect.

Inode

In the UNIX operating system, every file is indexed with the help of Inode. An Inode is a block that is created at the time when the file system is designed.

There are various types of information included in Inode:

  1. Attributes of the file, such as timestamp, permissions, details, ownership, etc.
  2. The total number of direct blocks that comprise of the pointer to the starting blocks.
  3. In Inode, there is a single indirect pointer. It is used to point an index block. If using direct blocks, entire file cannot be indexed, then, in that case, we use a single indirect pointer.
  4. Inode also contains a double indirect pointer. This pointer is used to point a disk block.
  5. In Inode there is another pointer, which is a triple index pointer. This pointer is also used to point a disk block.



ADVERTISEMENT
ADVERTISEMENT