Go Back

A Quick Abstract:

1. Contiguous File Allocation:

Working:

Each file occupies a contiguous block of storage space on the disk.

Allocation is straightforward, and accessing the file is efficient.

File size is known in advance.

Advantages:

Simple and efficient for sequential access.

Minimal overhead in terms of storage management.

Disadvantages:

Fragmentation issues, both internal and external.

Difficulty in accommodating growing or shrinking file sizes.

2. Linked File Allocation:

Working:

Files are linked together using pointers.

Each file is a linked list of disk blocks.

Dynamic in nature and can accommodate varying file sizes.

Advantages:

Flexibility in file size changes.

No external fragmentation.

Disadvantages:

Overhead of storing and managing pointers.

Access time is longer due to traversal of pointers.

3. Indexed File Allocation:

Working:

Each file has an index block containing pointers to the actual data blocks.

The index block acts as a table of contents for the file.

Efficient for both sequential and direct access.

Advantages:

Efficient for random access.

Minimal wasted space and fragmentation.

Disadvantages:

Overhead of maintaining an index.

Limited by the size of the index block.

4. Example Scenario:

Consider a file "myfile.txt" with a size of 600 KB.

Contiguous Allocation:

Allocate a contiguous block of 600 KB on the disk.

Linked Allocation:

Divide the file into linked blocks, each pointing to the next.

Block 1 → Block 2 → ... → Block n.

Indexed Allocation:

Create an index block pointing to individual data blocks.

5. Conclusion:

Each file allocation method has its strengths and weaknesses. Contiguous allocation is simple but suffers from fragmentation. Linked allocation is flexible but comes with the overhead of managing pointers. Indexed allocation is efficient for random access but requires an index block.

Notes From The Slides:

Allocation Methods - Contiguous

An allocation method refers to how disk blocks are allocated for files:
Contiguous allocation – each file occupies set of contiguous blocks

Best performance in most cases
Simple – only starting location (block #) and length (number of blocks) are required
Problems include finding space for file, knowing file size, external fragmentation, need for compaction off-line (downtime) or on-line

Contiguous Allocation

Mapping from logical to physical

Block to be accessed = Q + starting address

Displacement into block = R

Allocation Methods - Linked

Linked allocation – each file a linked list of blocks

File ends at nil pointer
No external fragmentation
Each block contains pointer to next block
No compaction, external fragmentation
Free space management system called when new block needed
Improve efficiency by clustering blocks into groups but increases internal fragmentation
Reliability can be a problem
Locating a block can take many I/Os and disk seeks

Each file is a linked list of disk blocks: blocks may be scattered anywhere on the disk

Mapping

Block to be accessed is the Qth block in the linked chain of blocks representing the file.

Displacement into block = R + 1

Linked Allocation

File-Allocation Table

Allocation Methods - Indexed

Indexed allocation

Each file has its own index block(s) of pointers to its data blocks

Logical view

Example of Indexed Allocation