File Allocation Methods

Introduction

File allocation techniques are essentially methods for storing any file in the system's memory block. Three different types of file allocation techniques exist:

1. Contiguous Allocation
2. Linked List Allocation
3. Indexed Allocation

These techniques' major goals are to offer effective disc space utilization and quick access to file blocks.

Contiguous Allocation

According to this strategy, every file that resides in a memory block takes up a contiguous, or continuous, collection of memory blocks.

For file F1, let's say the beginning address is 1 and the number of memory blocks needed is 3. After then, it will be kept at b[1], b[2], and b[3].

Every file will contain a directory entry with the information listed below:

1. Location of the starting block
2. File space requirements in terms of memory blocks

Consider the four-file structure shown below, which includes files 1, 2, and 3.

On the storage device, each file must take up consecutive blocks of space. Contiguous refers to a continuous area.

Advantages

1. There is either very little or no disk-head motion while reading or writing the blocks since the items are stored contiguously. It takes less time to seek
2. As a result, the access time of a file has been improved.
3. To access the concurrently stored files in memory, all we need to know is the beginning index and file length.
4. The kth block for any file, starting at index I may be simply found as (i+k).

Disadvantages

1. As a result of internal and external file allocation that suffers from fragmentation, memory use may be wasteful.
2. Allocating huge size blocks might be challenging since there could not be many contiguous blocks available in the memory.
3. The issue of growing files may arise; although the original space allotted would be adequate, the file size may increase with time, as in the case of a word document when we are typing.
4. The memory block that is currently allocated could run out of space.
5. Compaction (a remedy for fragmentation) can be time-consuming and require a system to be down, which will prevent regular functioning.

Linked List Allocation

The allocation mechanism uses a linked list data structure, as the name suggests. The memory is dispersed over the available disc space rather than being continuous. In the OS, these are also known as chained file allocation techniques. Every directory entry must include a reference to the following location in the memory block where the file is stored. This is done in 3 ways

Modification 1

The following details will be included in the Directory entry:

1. Address of the next memory block
2. Address of the previous memory block

Modification 2

The following details will be included in the Directory entry:

1. address of the first memory block
2. previous memory block
3. Total blocks needed by file

To determine if the system is corrupt or not, the total block info is employed as a cross-check.

Modification 3

1. Address of the first memory block
2. The final memory block won't contain any pointers, signaling the file's conclusion.

Advantages

1. does not experience external fragmentation since adding extra scatter linked memory can handle handling larger files
2. Growth in file size is not a concern and can be managed.

Disadvantages

1. More room for a pointer
2. One pointer loss might ruin the entire file.
3. As file blocks are dispersed across the RAM, several disc seek operations may be necessary, which might impede access.
4. Direct access is not encouraged, for instance: Since the blocks are not stored consecutively, we cannot access the kth block starting at index I by performing (i+k).

Indexed Allocation

1. In the indexed allocation approach, an area known as the index block houses all of the pointers (leading to the subsequent block in the linked list).
2. Each file has a multi-level index in the file-allocation table.
3. When the entire block count "overflows" the prior index allocation, indirection blocks are inserted.
4. You receive a single index file with all block positions. The index file stores blocks in the order of access.

Example

The index block in the picture to the right is 19 and contains all of the block addresses for the file jeep.

The initial block of storage is 9, followed in order by 16, 1, 10, and 25.

An empty index block list is indicated by a negative number.

That is to say, the file isn't big enough to fill more blocks.

The blocks and pointers used in the Linked List Allocation technique were dispersed across the memory, and retrieval was accomplished by going to each block in turn. With the index allocation approach, this is resolved.

Highlights

In order to access the file for Linked Allocation, the pointers and blocks have to be located sequentially by going to each block on the disc.

Advantages

1. A reference to the kth block of the file is contained in the kth entry of the index-block.
2. An index block file containing all addresses is available.
3. It doesn't have external fragmentation problems.

Disadvantages

1. Due to the disk's dispersed memory, seek times may still be long.
2. Index file corruption might result in lost file access locations.