Free space management in Operating Systems - Time & Space Complexity

Time Complexity: Free space management

O(n)

Understanding Time Complexity

When managing free space in an operating system, it's important to know how the time to find or update free space changes as the disk size grows.

We want to understand how the system's work increases when handling more free blocks.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple free space search using a bitmap
for (int i = 0; i < total_blocks; i++) {
  if (bitmap[i] == 0) { // block is free
    allocate_block(i);
    break;
  }
}
    

This code scans a bitmap to find the first free block and allocates it.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop scanning the bitmap array to find a free block.
• How many times: Up to the total number of blocks on the disk.

How Execution Grows With Input

As the number of blocks increases, the time to find a free block grows roughly in proportion.

Input Size (n)	Approx. Operations
10	Up to 10 checks
100	Up to 100 checks
1000	Up to 1000 checks

Pattern observation: The work grows linearly as the number of blocks increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a free block grows directly with the number of blocks on the disk.

Common Mistake

[X] Wrong: "Finding a free block always takes the same time no matter how big the disk is."

[OK] Correct: Because the search may need to check many blocks, the time depends on how many blocks there are and where the free block is located.

Interview Connect

Understanding how free space management scales helps you reason about system efficiency and design better storage solutions.

Self-Check

"What if we used a linked list to track free blocks instead of scanning a bitmap? How would the time complexity change?"

Practice

1. What is the main purpose of free space management in an operating system?

easy

A. To manage user permissions for files

B. To speed up the CPU processing

C. To keep track of which parts of storage are free or used

D. To control network connections

Solution

1. Step 1: Understand the role of free space management

   Free space management is about tracking storage space availability.

2. Step 2: Identify the correct purpose

   It helps the system know which storage parts are free or occupied.

3. Final Answer:

   To keep track of which parts of storage are free or used -> Option C

4. Quick Check:

   Free space management = tracking free/used storage [OK]

Hint: Remember: free space management tracks storage availability [OK]

Common Mistakes:

• Confusing free space management with file permissions
• Thinking it manages CPU or network tasks
• Assuming it deletes files automatically

2. Which of the following is a common method used for free space management?

easy

A. Linked list

B. Binary search tree

C. Hash table

D. Stack

Solution

1. Step 1: Recall common free space management methods

   Common methods include bitmaps and linked lists to track free blocks.

2. Step 2: Identify the correct method

   Linked lists are widely used to keep track of free space blocks.

3. Final Answer:

   Linked list -> Option A

4. Quick Check:

   Common method = linked list [OK]

Hint: Linked lists or bitmaps track free space blocks [OK]

Common Mistakes:

• Choosing data structures not typically used for free space
• Confusing stacks or trees with free space tracking
• Assuming hash tables are used for free space management

3. Consider a bitmap representing free space where 1 means free and 0 means used: 10110010. Which blocks are free?

medium

A. Blocks 0, 2, 3, and 7

B. Blocks 0, 2, 3, and 6

C. Blocks 1, 3, 4, and 7

D. Blocks 1, 2, 5, and 6

Solution

1. Step 1: Understand bitmap indexing

   Bitmap bits index blocks starting at 0 from left to right: bit 0 = block 0.

2. Step 2: Identify bits with value 1

   Bitmap: 1(0),0(1),1(2),1(3),0(4),0(5),1(6),0(7). Blocks with 1 are 0, 2, 3, and 6.

3. Step 3: Verify bit 7

   Bit 7 is 0, so block 7 is used, not free.

4. Final Answer:

   Blocks 0, 2, 3, and 6 -> Option B

5. Quick Check:

   Bits 1 = free blocks 0,2,3,6 [OK]

Hint: Index bits from 0 left to right; 1 means free [OK]

Common Mistakes:

• Starting index from 1 instead of 0
• Mixing up bit positions and block numbers
• Confusing 0 and 1 meanings in bitmap

4. A linked list is used to track free blocks, but it sometimes skips some free blocks. What is the likely problem?

medium

A. The CPU cache is corrupted

B. The disk is full and no free blocks exist

C. The file system does not support linked lists

D. The linked list pointers are not updated correctly after allocation

Solution

1. Step 1: Understand linked list free space tracking

   Linked lists track free blocks by pointers linking them in order.

2. Step 2: Identify cause of skipping blocks

   If pointers are not updated after allocation or freeing, some free blocks may be skipped.

3. Final Answer:

   The linked list pointers are not updated correctly after allocation -> Option D

4. Quick Check:

   Incorrect pointer updates cause skipped free blocks [OK]

Hint: Check pointer updates after allocation to avoid skipping [OK]

Common Mistakes:

• Assuming disk is full without checking pointers
• Blaming file system support instead of pointer errors
• Confusing hardware issues with software pointer bugs

5. You have a disk with 100 blocks and a bitmap for free space. If the bitmap has 20 bits set to 1, what is the best way to allocate 5 new blocks efficiently?

hard

A. Scan the bitmap from start and pick the first 5 free blocks

B. Randomly pick any 5 blocks without checking bitmap

C. Allocate blocks only at the end of the disk

D. Delete existing files to free space first

Solution

1. Step 1: Understand bitmap allocation

   Bitmap shows which blocks are free (1) or used (0).

2. Step 2: Efficient allocation method

   Scanning bitmap from start to find first 5 free blocks is efficient and safe.

3. Final Answer:

   Scan the bitmap from start and pick the first 5 free blocks -> Option A

4. Quick Check:

   Scan bitmap for free blocks to allocate efficiently [OK]

Hint: Scan bitmap sequentially to find free blocks quickly [OK]

Common Mistakes:

• Picking blocks randomly without checking free status
• Assuming only end blocks can be allocated
• Deleting files unnecessarily before allocation