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.