File Allocation Strategies

Key Terms and Concepts

• Seek Time: The time it takes for the read/write head of a disk drive to move to the track where the data to be read or written is located.
• Disk Head: The component of a disk drive that reads and writes data to the disk platter. It is mounted on an arm that moves it across the disk surface.
• Internal Fragmentation: Occurs when allocated memory may have some unused space due to the fixed size of memory allocation units.
• External Fragmentation: Happens when free memory is scattered in small blocks across the storage, making it difficult to allocate contiguous blocks of memory.
• Random Access: Allows data to be read or written in any order, making it very fast. Used for primary storage where speed is crucial.
• Direct Access: Refers to the ability to access data directly without sequentially searching through other data.
• File Control Block (FCB): A data structure used by file systems to store information about a file.
• File Allocation Table (FAT): A legacy file system architecture used in various operating systems, including MS-DOS and Windows.

A. Contiguous File Allocation

Contiguous file allocation is a straightforward method where files are allocated consecutive blocks of disk space. It's one of the simplest techniques used in file systems.

• Purpose: Simplifies file access and management. Ideal for files that are accessed sequentially.
• Seek Time: Typically very low for sequential access since data blocks are stored consecutively.

Advantages

• Very easy to implement
• Minimum amount of seek time
• Minimal disk head movement
• Faster memory access

Disadvantages

• File size must be initialized at creation
• Size cannot increase after initialization
• Possible internal or external fragmentation

Applications: Suitable for systems where file sizes are known in advance and do not change often, such as read-only media (e.g., CD-ROMs, DVD-ROMs). Effective in real-time systems where fast access time is critical.

B. Indexed File Allocation

The indexed file allocation is similar to linked file allocation but uses an index block to store all pointers together, making retrieval easier and more efficient.

• Purpose: Combines benefits of contiguous and linked allocation by using an index block to manage pointers.
• Seek Time: Moderate seek times as initial seek is needed to access the index block, followed by seeks to individual data blocks.

Advantages

• Reduces possibilities of external fragmentation
• Direct access to blocks rather than sequential

Disadvantages

• More pointer overhead
• If index block is lost, entire file becomes inaccessible
• Single index block may not accommodate all pointers for large files

Applications: Suitable for systems requiring efficient random access to file blocks, such as database systems. Ideal for file systems where file sizes vary greatly and frequent updates occur.

C. Linked File Allocation

The Linked file allocation overcomes the drawback of contiguous file allocation by storing files in a scattered manner with pointers linking the blocks together.

• Purpose: Allows files to grow dynamically without requiring contiguous disk space. Suitable for systems where file sizes vary and are modified frequently.
• Seek Time: Higher seek times for both sequential and random access due to the need to follow pointers from one block to the next.

Advantages

• No external fragmentation
• Directory entry needs only starting block address
• More flexible than contiguous allocation

Disadvantages

• Does not support random or direct access
• If pointers are corrupted, disk blocks are affected
• Extra space required for pointers in each block

Applications: Suitable for file systems with high flexibility requirements and where file sizes change frequently, such as general-purpose operating systems. Useful in systems where sequential access is more common than random access.