File allocation methods (contiguous, linked, indexed) in Operating Systems - Practice Problems & Coding Challenges

Challenge - 5 Problems

🧠 Conceptual

intermediate

Understanding Contiguous File Allocation

Which of the following best describes the main characteristic of contiguous file allocation?

A Files are compressed and stored in a single block to save space.

B Files are stored as linked blocks scattered anywhere on disk, with pointers connecting them.

C Files are stored in an index block that contains pointers to all file blocks, allowing random access.

D Files are stored in consecutive blocks on disk, making access fast but causing external fragmentation.

💡 Hint

Think about how the file blocks are arranged physically on the disk.

Contiguous allocation stores all file blocks next to each other on disk. This allows fast sequential access but can cause external fragmentation because free space may be split into small pieces.

📋 Factual

intermediate

Linked Allocation Characteristics

What is a key disadvantage of linked file allocation compared to contiguous allocation?

A It requires a large index block to store pointers to all file blocks.

B It has slower access time because each block contains a pointer to the next block, requiring sequential traversal.

C It causes external fragmentation due to scattered file blocks.

D It cannot handle files larger than a fixed size.

💡 Hint

Consider how the system finds the next block in linked allocation.

Linked allocation stores file blocks anywhere on disk with pointers linking them. Accessing a block requires following pointers sequentially, which slows down random access compared to contiguous allocation.

🔍 Analysis

advanced

Indexed Allocation Advantages

Why does indexed file allocation improve random access compared to linked allocation?

A Because an index block contains pointers to all file blocks, allowing direct access to any block without traversal.

B Because all file blocks are stored contiguously, making access direct.

C Because it compresses file data to reduce disk usage.

D Because it uses a linked list of blocks, reducing overhead.

💡 Hint

Think about how the system finds a specific block in indexed allocation.

Indexed allocation uses a special index block that holds pointers to all the file's blocks. This allows the system to jump directly to any block, improving random access speed compared to linked allocation.

❓ Comparison

advanced

Comparing Fragmentation in Allocation Methods

Which file allocation method is most prone to external fragmentation, and why?

A Contiguous allocation, because files require consecutive free blocks which may not be available as disk fills up.

B Linked allocation, because pointers cause blocks to scatter randomly.

C Indexed allocation, because the index block can become fragmented.

D None of the methods cause external fragmentation.

💡 Hint

Consider how each method allocates space and what happens when disk space is fragmented.

Contiguous allocation needs consecutive free blocks for a file. Over time, free space breaks into small pieces, causing external fragmentation. Linked and indexed methods do not require consecutive blocks, so they avoid this problem.

❓ Reasoning

expert

Choosing File Allocation for Large Files with Random Access

A system needs to store very large files and allow fast random access to any part of the file. Which file allocation method is best suited, and why?

A Contiguous allocation, because it stores files in consecutive blocks for fast access.

B Linked allocation, because it uses pointers to link scattered blocks, saving space.

C Indexed allocation, because it uses an index block to directly access any file block, supporting large files and fast random access.

D None of these methods support large files with random access efficiently.

💡 Hint

Think about how each method supports random access and file size limits.

Indexed allocation supports large files by using an index block that points to all file blocks. This allows direct access to any block, making random access fast even for large files. Contiguous allocation struggles with large files due to fragmentation, and linked allocation is slow for random access.

Practice

1. Which file allocation method stores all file blocks in one continuous sequence on disk?

easy

A. Hybrid allocation

B. Linked allocation

C. Indexed allocation

D. Contiguous allocation

Solution

1. Step 1: Understand file storage methods

   Contiguous allocation stores all file blocks one after another in a continuous space on disk.

2. Step 2: Compare with other methods

   Linked allocation stores blocks scattered with pointers; indexed uses an index block. Only contiguous is continuous.

3. Final Answer:

   Contiguous allocation -> Option D

4. Quick Check:

   Continuous blocks = Contiguous allocation [OK]

Hint: Continuous blocks mean contiguous allocation [OK]

Common Mistakes:

• Confusing linked allocation with contiguous
• Thinking indexed allocation stores blocks continuously
• Assuming hybrid is a standard method

2. Which of the following is the correct way to describe linked allocation?

easy

A. File blocks are stored in a continuous sequence

B. Each file block contains a pointer to the next block

C. An index block contains pointers to all file blocks

D. File blocks are stored in a fixed-size table

Solution

1. Step 1: Recall linked allocation structure

   In linked allocation, each file block stores a pointer to the next block, forming a chain.

2. Step 2: Eliminate other options

   Continuous sequence is contiguous; index block is indexed allocation; fixed-size table is unrelated.

3. Final Answer:

   Each file block contains a pointer to the next block -> Option B

4. Quick Check:

   Pointers in blocks = Linked allocation [OK]

Hint: Pointers inside blocks mean linked allocation [OK]

Common Mistakes:

• Mixing up index block with linked pointers
• Thinking linked allocation stores blocks continuously
• Confusing fixed-size table with file allocation

3. Consider a file stored using indexed allocation with an index block containing pointers to data blocks 5, 9, and 12. Which block does the system read first to access the file?

medium

A. The index block

B. Block 5

C. Block 9

D. Block 12

Solution

1. Step 1: Understand indexed allocation access

   The system first reads the index block to find pointers to all data blocks.

2. Step 2: Identify the first block read

   Before accessing data blocks 5, 9, or 12, the index block must be read to know their locations.

3. Final Answer:

   The index block -> Option A

4. Quick Check:

   Index block read first in indexed allocation [OK]

Hint: Index block is always read first in indexed allocation [OK]

Common Mistakes:

• Choosing a data block instead of the index block
• Confusing linked allocation with indexed
• Assuming direct access without index

4. A file system uses linked allocation but the file's blocks are stored non-contiguously without pointers linking them. What is the main problem here?

medium

A. File blocks are stored contiguously, causing slow access

B. File blocks are fragmented but linked correctly

C. Pointers are missing, so file blocks cannot be accessed sequentially

D. Index block is corrupted

Solution

1. Step 1: Understand linked allocation requirements

   Linked allocation requires each block to have a pointer to the next block for sequential access.

2. Step 2: Identify the problem without pointers

   Without pointers, the system cannot follow the chain, so blocks cannot be accessed in order.

3. Final Answer:

   Pointers are missing, so file blocks cannot be accessed sequentially -> Option C

4. Quick Check:

   Missing pointers break linked allocation chain [OK]

Hint: No pointers means linked allocation fails [OK]

Common Mistakes:

• Assuming fragmentation is not a problem
• Confusing contiguous storage with linked allocation
• Thinking index block is involved in linked allocation

5. A file of size 12 blocks is stored using contiguous allocation starting at block 20. If block 25 is corrupted, what is the impact on the file access?

hard

A. The entire file becomes inaccessible due to break in continuity

B. File access continues using pointers from block 25

C. Only block 25 is lost; other blocks are accessible

D. Index block redirects access around block 25

Solution

1. Step 1: Recall contiguous allocation properties

   Files are stored in continuous blocks; any corruption breaks the sequence.

2. Step 2: Analyze impact of corrupted block 25

   Since block 25 is in the middle, the file cannot be read beyond that point, making the entire file inaccessible.

3. Final Answer:

   The entire file becomes inaccessible due to break in continuity -> Option A

4. Quick Check:

   Corruption breaks contiguous file access [OK]

Hint: Contiguous files fail if any block is corrupted [OK]

Common Mistakes:

• Assuming only corrupted block is lost
• Thinking pointers or index block help in contiguous allocation
• Confusing linked or indexed allocation behavior