Operating System Free Space and File Allocation Methods

Free Space Management in OS

Free Space Management is a technique used by the operating system to keep track of unused disk blocks. It helps the file system allocate space to new files and deallocate space when files are deleted.

Objective: To efficiently manage and utilize available disk space.

Need for Free Space Management

• To identify free disk blocks quickly.
• To allocate storage space for new files.
• To reclaim space when files are deleted.
• To improve disk utilization and system performance.

Methods of Free Space Management

1. Bit Vector (Bitmap) Method

In this method, each disk block is represented by a bit.

• 0 → Free block
• 1 → Allocated block

Example

Here, blocks 1, 4, 5, and 7 are free.

Advantages

• Easy to find contiguous free blocks.
• Simple implementation.

Disadvantages

• Requires extra memory for large disks.

2. Linked List Method

All free disk blocks are linked together.

Diagram

Free List: 100 → 200 → 350 → 420 → 500 → NULL

Each free block contains a pointer to the next free block.

Advantages

• No large bitmap required.
• Easy insertion and deletion.

Disadvantages

• Difficult to find contiguous free blocks.
• Traversal can be slow.

3. Grouping Method

The first free block stores addresses of several free blocks.

Diagram

Block 100: [200, 250, 300, 350, 400] → Next Group

Advantages

• Faster than linked list.
• Multiple free blocks can be obtained at once.

Disadvantages

• More complex implementation.

4. Counting Method

Used when several contiguous blocks are free. Instead of storing each block number, the system stores:

• Starting block address
• Number of consecutive free blocks

Example

(Start Block, Count): (100, 5), (250, 10), (500, 8)

Advantages

• Saves memory.
• Efficient when free blocks occur in groups.

Disadvantages

• Less effective if free blocks are scattered.

Comparison of Free Space Methods

File Allocation Methods

File allocation methods are used by the operating system to store files on secondary storage devices such as hard disks. They determine how disk blocks are allocated to files and how data is accessed.

1. Contiguous Allocation

In contiguous allocation, all blocks of a file are stored in consecutive disk locations.

Example

File A (5 Blocks): 100, 101, 102, 103, 104

Advantages

• Simple implementation.
• Fast sequential and random access.
• Low seek time.

Disadvantages

• External fragmentation occurs.
• File size must be known in advance.
• Difficult to expand files.

2. Linked Allocation

In linked allocation, file blocks can be stored anywhere on the disk. Each block contains a pointer to the next block.

Advantages

• No external fragmentation.
• Files can grow easily.
• Efficient space utilization.

Disadvantages

• Random access is slow.
• Pointer overhead in every block.
• Data loss risk if a pointer is corrupted.

3. Indexed Allocation

In indexed allocation, each file has a separate index block containing addresses of all file blocks.

Advantages

• Supports direct/random access.
• No external fragmentation.
• Easy file expansion.

Disadvantages

• Requires extra space for index blocks.
• Wastage of space for small files.

Comparison of Allocation Methods

Conclusion

Contiguous allocation provides fast access but suffers from fragmentation. Linked allocation eliminates fragmentation and allows easy file growth but has slow random access. Indexed allocation overcomes most limitations by using an index block and is widely used in modern operating systems.