Free space management in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Free Space Bitmaps

In free space management, a bitmap is used to track free and used blocks on a disk. If a disk has 1024 blocks and the bitmap shows 1000001110 (from left to right) for the first 10 blocks, which blocks are free?

A Blocks 2, 3, 4, 9 are free

B Blocks 1, 6, 7, 8 are free

C Blocks 0, 5, 6, 7 are free

D Blocks 0, 1, 2, 3 are free

💡 Hint

Remember, in a bitmap, 0 usually means free and 1 means used.

The bitmap 1000001110 means block 0 is used (1), block 1 is free (0), block 2 is free (0), block 3 is free (0), block 4 is free (0), block 5 is free (0), block 6 is used (1), block 7 is used (1), block 8 is used (1), block 9 is free (0). So free blocks are 1, 2, 3, 4, 5, 9. Among the options, only A correctly identifies free blocks 2, 3, 4, and 9. All blocks listed in A are free, whereas other options include used blocks.

📋 Factual

intermediate

Free Space Linked List Characteristics

Which of the following is a disadvantage of using a linked list to manage free disk space?

A It provides constant time access to any free block

B It avoids external fragmentation

C It requires extra space to store pointers

D It is simple to implement and update

💡 Hint

Think about what extra information must be stored in a linked list node.

A linked list requires storing pointers (addresses) along with each free block to link to the next free block. This extra space overhead is a disadvantage. It does not provide constant time access (A is false), it is simple to implement (C is true, so not a disadvantage), and it does not inherently avoid external fragmentation (D is false).

🔍 Analysis

advanced

Comparing Free Space Management Methods

Consider three free space management methods: bit vector, linked list, and grouping. Which method is most efficient in terms of speed when allocating a large number of contiguous blocks?

A Grouping, because it stores addresses of free blocks in groups reducing overhead

B Bit vector, because it allows quick scanning for contiguous free blocks

C Linked list, because it stores exact addresses of free blocks

D All methods have equal speed for large contiguous allocations

💡 Hint

Think about how each method tracks free blocks and how easy it is to find contiguous free space.

Bit vectors allow scanning bits to find contiguous free blocks quickly. Linked lists store individual free blocks and may require traversing many nodes. Grouping reduces overhead but still requires searching groups. Thus, bit vectors are fastest for large contiguous allocations.

❓ Reasoning

advanced

Effect of External Fragmentation on Free Space Management

Which free space management method is most affected by external fragmentation, and why?

A Linked list, because it stores free blocks individually leading to scattered free spaces

B Bit vector, because it cannot represent free blocks accurately

C Grouping, because it merges all free blocks into one large block

D None of the methods are affected by external fragmentation

💡 Hint

Consider how each method handles scattered free blocks.

Linked lists store free blocks individually, so free space can become scattered and fragmented, making it harder to allocate large contiguous blocks. Bit vectors and grouping can better represent free space patterns. Therefore, linked lists are most affected by external fragmentation.

❓ Comparison

expert

Choosing Free Space Management for Large Disks

A system administrator must choose a free space management method for a very large disk with millions of blocks. Which method is best suited to minimize memory usage while maintaining reasonable allocation speed?

A Linked list, because it uses minimal memory by storing only free block addresses

B Bit vector, because it uses fixed memory proportional to disk size

C Contiguous allocation, because it avoids free space management altogether

D Grouping, because it reduces pointer overhead by storing free blocks in groups

💡 Hint

Think about trade-offs between memory usage and speed for very large disks.

Linked lists use minimal memory but can be slow for allocation. Bit vectors use memory proportional to disk size, which is large for millions of blocks. Grouping reduces pointer overhead by storing free blocks in groups, balancing memory use and speed. Contiguous allocation is a file allocation method, not a free space management method.

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