File Allocation Methods - Contiguous, Linked, Indexed

🎯

File Allocation Methods - Contiguous, Linked, Indexed

easyOSAmazonTCSInfosys

Imagine you have a bookshelf where you want to store books either all together, linked by a string, or indexed by a catalog card. File allocation methods work similarly to organize files on disk.

💡 Beginners often confuse file allocation methods with file formats or think all files must be stored contiguously, missing the trade-offs in access speed and fragmentation.

📋

Interview Question

Explain the three primary file allocation methods: Contiguous, Linked, and Indexed. Compare their advantages and disadvantages, and describe scenarios where each is preferred.

How files are stored on disk blocksTrade-offs between access speed and fragmentationDirectory structure interaction with allocation methods

💡

Scenario & Trace

ScenarioA media editing software needs to store large video files for fast sequential access.

Using contiguous allocation, the file is stored in consecutive disk blocks → fast sequential read/write → minimal seek time → but requires large contiguous free space → fragmentation can occur over time.

ScenarioA text editor saves many small files that are frequently created and deleted.

Linked allocation stores each file as a linked list of disk blocks scattered anywhere → easy to allocate and deallocate blocks → no external fragmentation → but random access is slow as blocks must be traversed sequentially.

ScenarioAn operating system stores executable files requiring both sequential and random access.

Indexed allocation uses an index block containing pointers to all file blocks → supports efficient random access → avoids external fragmentation → but index block overhead increases with file size.

• What happens if there is no contiguous free space large enough for a file in contiguous allocation?
• How does linked allocation handle corrupted pointers in the block chain?
• What if the index block itself becomes too large to fit in a single block in indexed allocation?

⚠️

Common Mistakes

Confusing file allocation with file formats

Interviewer thinks candidate lacks basic understanding of file system internals

✅ Clarify that allocation methods describe how files are stored on disk blocks, not file content or format

Assuming all files must be stored contiguously

Interviewer doubts candidate’s grasp of fragmentation and flexibility in file systems

✅ Explain that linked and indexed methods exist to handle fragmentation and dynamic file sizes

Overlooking random access inefficiency in linked allocation

Interviewer suspects candidate missed performance trade-offs

✅ Mention that linked allocation is good for sequential access but poor for random access

Ignoring index block size limits in indexed allocation

Interviewer questions candidate’s understanding of scalability

✅ Discuss multi-level indexing or indirect blocks for large files

🧠

Basic Definition - What It Is

💡 This level covers the fundamental idea behind each allocation method without going into technical details.

Intuition

Files are stored on disk either in consecutive blocks, linked scattered blocks, or via an index pointing to blocks.

Explanation

Contiguous allocation stores all file blocks sequentially on disk, making access fast but prone to fragmentation. Linked allocation stores file blocks scattered anywhere on disk, linked by pointers, which avoids fragmentation but slows random access. Indexed allocation uses a special index block that holds pointers to all file blocks, enabling efficient random access and avoiding fragmentation but with some overhead.

Memory Hook

💡 Think of contiguous as a book on a shelf, linked as a chain of notes, and indexed as a catalog card pointing to pages.

Interview Questions

❓ What is the main advantage of contiguous allocation?

• Fast sequential access
• Simple to implement
• Requires contiguous free space

❓ Why might linked allocation be preferred for small files?

• No external fragmentation
• Easy to allocate/deallocate
• Slower random access

⏱

Depth Level

Interview Time30 seconds

Depthbasic

Covers what each method is and their primary characteristics; sufficient for quick screening.

Interview Target: Minimum floor - never go below this

Knowing only this helps pass initial rounds but lacks depth for on-site interviews.

🧠

Mechanism Depth - How It Works

💡 This level explains internal workings, trade-offs, and practical implications expected in product company interviews.

Intuition

Each allocation method balances disk space management, access speed, and fragmentation differently through its internal structure.

Explanation

Contiguous allocation requires the file system to find a large enough continuous block of free space before writing a file, which can cause external fragmentation over time and complicate file growth. Linked allocation stores each file as a linked list of disk blocks, where each block contains a pointer to the next; this eliminates external fragmentation but makes random access inefficient since traversal is sequential. Indexed allocation uses an index block that contains pointers to all the file's blocks, allowing direct access to any block, which improves random access speed and avoids external fragmentation, but the index block itself can become a bottleneck for very large files, sometimes requiring multi-level indexing.

Memory Hook

💡 Imagine contiguous as a train with all carriages connected, linked as a treasure hunt with clues from one spot to the next, and indexed as a map with coordinates to each treasure spot.

Interview Questions

❓ How does fragmentation affect contiguous allocation?

• External fragmentation reduces available contiguous space
• File growth may require moving file
• Complicates allocation

❓ Explain random access performance in linked allocation.

• Sequential traversal needed
• Random access is slow
• Not suitable for files requiring frequent random reads

❓ What happens if the index block is full in indexed allocation?

• Multi-level indexing may be used
• Index block overhead increases
• Complexity in managing index blocks

⏱

Depth Level

Interview Time2-3 minutes

Depthintermediate

Demonstrates understanding of internal mechanisms, trade-offs, and practical system design considerations.

Interview Target: Target level for FAANG on-sites

Mastering this level distinguishes you from most candidates and prepares you for deeper system design discussions.

📊

Explanation Depth Levels

💡 Choose depth based on interview stage and role; deeper knowledge is needed for system design roles.

Level	Interview Time	Suitable For	Risk
Basic Definition	30s	Screening call	Too shallow for on-site interviews
Mechanism Depth	2-3 minutes	On-site interviews at product companies	Requires good understanding of trade-offs and internals

💼

Interview Strategy

💡 Use this guide to structure your explanation clearly and confidently before interviews.

How to Present

Start with a clear definition of each allocation method.Give a relatable example or analogy for each method.Explain the internal mechanism and trade-offs.Discuss edge cases and practical limitations.

Time Allocation

Definition: 30s → Example: 1min → Mechanism: 2min → Edge cases: 30s. Total ~4min

What the Interviewer Tests

Interviewer checks your conceptual clarity, ability to compare methods, and understanding of trade-offs and limitations.

Common Follow-ups

• What happens if a file needs to grow in contiguous allocation? → It may need to be moved or fragmented.
• How does the system recover from a corrupted pointer in linked allocation? → Usually via file system checks or backups.

💡 These follow-ups test your depth and ability to handle real-world file system issues.

🔍

Pattern Recognition

When to Use

Asked when discussing file systems, disk management, or storage optimization topics.

Signature Phrases

'Explain the file allocation methods''Compare contiguous and linked allocation''What happens when a file grows in contiguous allocation?'

NOT This Pattern When

Similar Problems

Practice

1. Given a disk with pending requests at tracks 10, 22, 20, 2, and 40, and the disk head currently at track 15 moving towards higher track numbers, trace the order in which SCAN will service these requests.

easy

A. 22, 20, 10, 2, 40

B. 20, 22, 40, 2, 10

C. 20, 22, 40, 10, 2

D. 10, 20, 22, 40, 2

Solution

1. Step 1: Identify head direction and requests

   Head at 15 moving up; requests: 2, 10, 20, 22, 40.

2. Step 2: SCAN moves towards higher tracks first

   It services requests in ascending order from current position: 20, 22, 40.

3. Step 3: After reaching the highest request, SCAN reverses direction

   Then it services remaining requests in descending order: 10, 2.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   20, 22, 40, 10, 2 correctly reflects SCAN's elevator movement servicing requests in one direction then reversing.

Hint: SCAN goes up servicing requests, then reverses down

Common Mistakes:

• Assuming SCAN skips requests on the return trip
• Mixing up order of requests on the return trip
• Confusing SCAN with C-SCAN which only moves in one direction

2. In a Unix-like file system, which component is primarily responsible for mapping a file name to its data blocks on disk?

easy

A. The inode, which stores metadata and pointers to data blocks

B. The data block itself, which contains the file's content and its name

C. The superblock, which manages overall file system metadata

D. The directory entry, which contains the file name and a pointer to the inode

Solution

1. Step 1: Understand the role of directory entries in file name resolution

   Directory entries map file names to inode numbers, acting as the bridge between human-readable names and inode metadata.

2. Step 2: Clarify inode responsibilities

   Inodes store metadata and pointers to data blocks but do not contain file names.

3. Step 3: Differentiate superblock and data blocks

   The superblock manages file system-wide metadata, not individual file mappings; data blocks store file content, not names.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Directory entries handle name-to-inode mapping [OK]

Hint: Directory entries map names -> inodes; inodes map data blocks

Common Mistakes:

• Confusing inode as containing file names
• Assuming data blocks store file names
• Believing superblock handles file name mappings

3. Trace the sequence of events when a process's CPU burst exceeds the time quantum in Round Robin scheduling. What happens immediately after the quantum expires?

easy

A. The process is preempted and placed at the end of the ready queue

B. The process continues running until it voluntarily yields the CPU

C. The process is terminated and removed from the system

D. The process is moved to the waiting queue for I/O

Solution

1. Step 1: Recall Round Robin preemption

   When a process's time quantum expires, it is preempted to ensure fairness and allow other processes CPU access.

2. Step 2: Understand queue management

   The preempted process is placed at the end of the ready queue to wait for its next turn.

3. Step 3: Analyze incorrect options

   The process continues running until it voluntarily yields the CPU contradicts RR's preemption principle. The process is terminated and removed from the system is incorrect because process termination depends on completion, not quantum expiry. The process is moved to the waiting queue for I/O is incorrect unless the process requests I/O, which is unrelated to quantum expiration.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Quantum expiry -> preempt -> enqueue at ready queue's end.

Hint: Quantum expiry means preempt and requeue

Common Mistakes:

• Thinking process runs until completion ignoring quantum
• Confusing preemption with process termination
• Assuming process moves to waiting queue without I/O

4. Which of the following is a key limitation of Peterson's algorithm that affects its practical use in modern multiprocessor systems?

medium

A. It allows unbounded waiting, leading to starvation

B. It requires busy waiting, which wastes CPU cycles

C. It depends on hardware atomic instructions to function correctly

D. It cannot guarantee mutual exclusion under any circumstances

Solution

1. Step 1: Identify Peterson's algorithm characteristics

   Peterson's algorithm uses busy waiting (spinlock), which can waste CPU resources.

2. Step 2: Analyze other options

   It cannot guarantee mutual exclusion under any circumstances is false because mutual exclusion is guaranteed. It depends on hardware atomic instructions to function correctly is incorrect since Peterson's algorithm was designed to avoid hardware atomic instructions. It allows unbounded waiting, leading to starvation is wrong because bounded waiting is guaranteed.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Busy waiting is a known practical limitation of Peterson's algorithm.

Hint: Peterson's = busy waiting, no hardware locks, bounded waiting

Common Mistakes:

• Assuming Peterson's needs hardware atomic instructions
• Confusing bounded waiting with starvation
• Believing mutual exclusion can fail

5. Which of the following statements about inodes is INCORRECT?

medium

A. Inodes store pointers to data blocks that hold the file's actual content.

B. An inode contains the file's name and its metadata such as permissions and timestamps.

C. Multiple directory entries can point to the same inode, enabling hard links.

D. Inodes are fixed-size structures that do not store file names.

Solution

1. Step 1: Clarify inode contents

   Inodes store metadata (permissions, timestamps, size) and pointers, but NOT file names.

2. Step 2: Confirm pointer role

   Inodes contain direct and indirect pointers to data blocks.

3. Step 3: Understand hard links

   Multiple directory entries can reference the same inode, enabling hard links.

4. Step 4: Recognize inode size

   Inodes are fixed-size and do not store variable-length file names.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   File names are stored in directory entries, not inodes [OK]

Hint: Inode = metadata + pointers; directory entry = file name + inode number

Common Mistakes:

• Assuming inodes store file names
• Confusing directory entries with inodes
• Believing inode size varies with file name length