Bird
Raised Fist0
Interview Prepoperating-systemseasyAmazonMicrosoftTCSInfosys

Internal vs External Fragmentation - Compaction & Buddy System

Choose your preparation mode3 modes available
🎯
Internal vs External Fragmentation - Compaction & Buddy System
easyOSAmazonMicrosoftTCS

Imagine you have a bookshelf with many books of different sizes, but the shelves have gaps that can't fit any book properly. How do you organize the books to use space efficiently?

💡 Beginners often confuse internal and external fragmentation because both relate to wasted memory, but they arise from different causes and require different solutions.
📋
Interview Question

Explain the difference between internal and external fragmentation in memory management. How do compaction and the buddy system help mitigate these issues?

Definition and causes of internal fragmentationDefinition and causes of external fragmentationMemory compaction techniqueBuddy system allocation method
💡
Scenario & Trace
ScenarioA system allocates memory blocks to processes using first-fit allocation, and processes frequently request and release memory of varying sizes.
1. Process A requests 100KB, allocated a 128KB block → 28KB internal fragmentation. 2. Process B requests 50KB, allocated a 64KB block → 14KB internal fragmentation. 3. After several allocations and deallocations, free memory is split into small non-contiguous blocks (e.g., 20KB, 30KB, 40KB) that cannot satisfy a 60KB request → external fragmentation. 4. Compaction is performed, moving allocated blocks to one end, creating a large contiguous free block. 5. Buddy system splits memory into power-of-two blocks and merges buddies on deallocation, reducing external fragmentation.
  • What if all allocated blocks are exactly the requested size? → No internal fragmentation but external fragmentation can still occur.
  • What if the system never performs compaction? → External fragmentation worsens over time, leading to allocation failures despite sufficient total free memory.
  • What if the buddy system is used but requests are not powers of two? → Memory is rounded up, causing internal fragmentation.
⚠️
Common Mistakes
Confusing internal fragmentation with external fragmentation

Interviewer doubts your grasp of basic memory management concepts.

✅ Remember internal fragmentation is wasted space inside allocated blocks; external is wasted free space outside.

Assuming compaction eliminates all fragmentation

Interviewer sees lack of understanding of compaction limitations and overhead.

✅ Explain compaction reduces external fragmentation but is costly and does not affect internal fragmentation.

Thinking buddy system completely removes fragmentation

Interviewer questions your knowledge of buddy system trade-offs.

✅ Clarify buddy system reduces external fragmentation but can cause internal fragmentation due to block size rounding.

Ignoring the overhead of compaction and buddy system management

Interviewer suspects superficial understanding without practical insight.

✅ Mention the time and resource cost of moving memory during compaction and bookkeeping in buddy system.

🧠
Basic Definition - What It Is
💡 This level covers the fundamental differences and simple definitions you must know to answer basic interview questions.

Intuition

Internal fragmentation wastes space inside allocated blocks; external fragmentation wastes space outside allocated blocks.

Explanation

Internal fragmentation occurs when a process is allocated more memory than it actually needs, leaving unused space inside the allocated block. External fragmentation happens when free memory is split into small scattered blocks that are too small to satisfy new allocation requests, even if the total free memory is sufficient. Compaction is a technique that moves allocated blocks to create larger contiguous free memory areas, reducing external fragmentation. The buddy system is a memory allocation method that divides memory into power-of-two sized blocks and merges adjacent free blocks (buddies) to reduce fragmentation.

Memory Hook

💡 Think of internal fragmentation as leftover crumbs inside a cookie jar, and external fragmentation as cookie crumbs scattered all over the table.

Interview Questions

❓ What is the main difference between internal and external fragmentation?
  • Internal fragmentation is wasted space inside allocated blocks.
  • External fragmentation is wasted space outside allocated blocks due to scattered free memory.
⏱
Depth Level
Interview Time30 seconds
Depthbasic

Covers simple definitions and basic understanding, sufficient for screening rounds.

Interview Target: Minimum floor - never go below this

Knowing only this will help you pass initial screening but not detailed technical rounds.

🧠
Mechanism Depth - How It Works
💡 This level explains the internal workings and trade-offs, expected in product company interviews.

Intuition

Fragmentation arises from allocation granularity and memory reuse patterns; compaction and buddy system manage fragmentation by reorganizing or structuring memory.

Explanation

Internal fragmentation results from fixed-size or power-of-two block allocations where the allocated block is larger than the requested memory, causing unused space inside the block. External fragmentation occurs when free memory is divided into small, non-contiguous blocks due to variable-sized allocations and deallocations, making it impossible to allocate large contiguous blocks despite sufficient total free memory. Compaction works by relocating allocated blocks to one end of memory, consolidating free space into a large contiguous block, but it is costly due to the overhead of moving data and updating pointers. The buddy system allocates memory in power-of-two sizes and merges adjacent free blocks (buddies) when both are free, which simplifies coalescing and reduces external fragmentation but can increase internal fragmentation due to rounding up allocation sizes.

Memory Hook

💡 Imagine a parking lot where cars (processes) park in fixed-size spots (blocks). Internal fragmentation is like empty space inside a spot when a small car parks in a large spot. External fragmentation is like many small empty spots scattered around that can't fit a large truck. Compaction is like rearranging cars to one side to free a large contiguous space. The buddy system is like dividing the parking lot into fixed-size sections that can be combined or split as needed.

Interview Questions

❓ How does compaction reduce external fragmentation and what are its drawbacks?
  • Compaction moves allocated blocks to create contiguous free memory.
  • It reduces external fragmentation by consolidating free space.
  • Drawbacks include overhead of moving data and updating references.
❓ Explain how the buddy system manages fragmentation.
  • Memory is split into power-of-two blocks.
  • Adjacent free blocks (buddies) are merged to form larger blocks.
  • Simplifies allocation and deallocation, reducing external fragmentation.
  • May cause internal fragmentation due to rounding up.
⏱
Depth Level
Interview Time2-3 minutes
Depthintermediate

Demonstrates understanding of internal mechanisms and trade-offs, suitable for on-site interviews.

Interview Target: Target level for FAANG on-sites

Mastering this level distinguishes you from most candidates.

📊
Explanation Depth Levels
💡 Choose your explanation depth based on interview stage and company expectations.
LevelInterview TimeSuitable ForRisk
Basic Definition30sScreening call or initial roundsToo shallow for detailed technical interviews
Mechanism Depth2-3 minutesOn-site interviews at product companiesRequires good understanding and ability to discuss trade-offs
💼
Interview Strategy
💡 Use this guide to structure your explanation clearly and confidently before every interview.

How to Present

Start with clear definitions of internal and external fragmentation.Give a simple analogy or example to illustrate the difference.Explain how compaction works and its pros and cons.Describe the buddy system and how it manages fragmentation.Mention edge cases or trade-offs to show depth.

Time Allocation

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

What the Interviewer Tests

Your ability to distinguish similar concepts, explain mechanisms clearly, and discuss trade-offs.

Common Follow-ups

  • What happens if compaction is not performed regularly? → External fragmentation worsens, allocation failures increase.
  • How does the buddy system compare to simple first-fit or best-fit allocation? → Buddy system simplifies merging but may waste more memory internally.
💡 These follow-ups test your understanding of practical implications and comparisons.
🔍
Pattern Recognition

When to Use

Asked during memory management or OS fundamentals interviews, especially when discussing allocation strategies.

Signature Phrases

'Explain the difference between internal and external fragmentation''How does compaction help with fragmentation?''What is the buddy system and how does it work?'

NOT This Pattern When

Similar Problems

Practice

(1/5)
1. Trace the sequence of checks the Banker's Algorithm performs when a process requests additional resources. Which step occurs immediately after verifying the request does not exceed the process's declared maximum need?
easy
A. The algorithm preempts resources from other processes to fulfill the request.
B. The algorithm immediately grants the request without further checks.
C. The algorithm simulates allocation and checks if the system remains in a safe state.
D. The algorithm checks if the requested resources are currently available in the system.

Solution

  1. Step 1: Recall the Banker's Algorithm request sequence

    First, it checks if the request is within the process's maximum declared need.
  2. Step 2: Next step after need check

    The algorithm then verifies if the requested resources are available in the system's current available pool.
  3. Step 3: Subsequent steps

    If available, it simulates allocation and checks for safe state, but this occurs after availability check.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    Availability check precedes simulation to avoid unnecessary computation.
Hint: Request ≤ Need -> check availability -> simulate safe state [OK]
Common Mistakes:
  • Assuming simulation happens before availability check
  • Believing requests are granted immediately after need check
  • Thinking preemption is part of Banker's Algorithm
2. In which scenario is preemptive Shortest Job First (SJF) scheduling preferred over non-preemptive SJF?
easy
A. When new processes with shorter burst times can arrive at any time during execution
B. When fairness is not a concern and starvation is acceptable
C. When minimizing context switch overhead is the highest priority
D. When all processes arrive at the same time and have similar burst times

Solution

  1. Step 1: Understand preemptive SJF behavior

    Preemptive SJF allows the CPU to switch to a newly arrived process if it has a shorter burst time than the currently running process.
  2. Step 2: Analyze scenarios

    If new processes with shorter burst times can arrive anytime, preemptive SJF ensures the CPU always runs the shortest job next, improving average waiting time.
  3. Step 3: Why other options are incorrect

    A: If all processes arrive simultaneously with similar burst times, preemptive advantage is minimal.
    B: Starvation is a concern in preemptive SJF, so it's not chosen when fairness is ignored.
    C: Preemptive SJF increases context switches, so it's not preferred when minimizing overhead.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Preemptive SJF is best when shorter jobs can arrive anytime, requiring immediate preemption.
Hint: Preemptive SJF shines when shorter jobs arrive unpredictably [OK]
Common Mistakes:
  • Assuming preemptive SJF always reduces overhead
  • Believing preemptive SJF is best when all jobs arrive simultaneously
3. Which of the following statements about user mode and kernel mode is INCORRECT?
medium
A. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation.
B. Kernel mode has unrestricted access to all hardware and memory.
C. User mode code cannot directly access kernel memory for protection reasons.
D. System calls execute entirely in user mode without switching to kernel mode.

Solution

  1. Step 1: Review privilege separation

    User mode is restricted; kernel mode has full privileges.
  2. Step 2: Validate each statement

    User mode code cannot directly access kernel memory for protection reasons. is true; user mode cannot access kernel memory. Kernel mode has unrestricted access to all hardware and memory. is true; kernel mode has full access. Mode switches are triggered by traps or interrupts to ensure controlled privilege escalation. is true; traps/interrupts cause mode switches.
  3. Step 3: Identify incorrect statement

    System calls execute entirely in user mode without switching to kernel mode. is false; system calls require switching to kernel mode to execute privileged operations.
  4. Final Answer:

    Option D -> Option D
  5. Quick Check:

    System calls always involve mode switch to kernel [OK]
Hint: System calls require kernel mode execution
Common Mistakes:
  • Believing system calls run entirely in user mode
  • Confusing hardware interrupts with system calls
  • Assuming user mode can access kernel memory
4. If a system enforces a strict ordering of resource acquisition to prevent circular wait, which of the following is a potential drawback that an interviewer might probe?
hard
A. Processes may experience increased waiting time due to forced ordering, reducing concurrency.
B. The system can still deadlock due to hold and wait despite ordering.
C. No preemption condition is violated by enforcing ordering.
D. Mutual exclusion is no longer required when ordering is enforced.

Solution

  1. Step 1: Understand resource ordering

    Ordering resources prevents circular wait by forcing processes to request resources in a global order.
  2. Step 2: Identify drawbacks

    Strict ordering can cause processes to wait longer than necessary, reducing concurrency and system throughput.
  3. Step 3: Analyze other options

    The system can still deadlock due to hold and wait despite ordering is incorrect because ordering eliminates circular wait, thus preventing deadlock from that condition. No preemption condition is violated by enforcing ordering is false; ordering does not violate no preemption. Mutual exclusion is no longer required when ordering is enforced is false; mutual exclusion is still required for non-shareable resources.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Ordering trades off concurrency for deadlock prevention.
Hint: Ordering resources prevents circular wait but can reduce concurrency [OK]
Common Mistakes:
  • Believing ordering removes all deadlock conditions
  • Confusing ordering with preemption
  • Assuming mutual exclusion is eliminated by ordering
5. If a process in the Waiting state is waiting for multiple I/O events simultaneously, how does the five-state model handle this scenario, and what is a key limitation of the model in this context?
hard
A. The process moves to Ready state after the first I/O event completes, ignoring others, which can cause errors
B. The process remains in Waiting until all I/O events complete; the model does not distinguish multiple waits, limiting concurrency handling
C. The process splits into multiple processes for each I/O event, which the model explicitly supports
D. The process moves to Running state and polls each I/O event, which the model assumes

Solution

  1. Step 1: Understand Waiting state semantics

    Waiting means blocked until the awaited event(s) complete.
  2. Step 2: Multiple I/O waits in five-state model

    The model treats Waiting as a single state without differentiating multiple simultaneous waits.
  3. Step 3: Limitation

    This means the process stays in Waiting until all I/O events complete, limiting fine-grained concurrency.
  4. Final Answer:

    Option B -> Option B
  5. Quick Check:

    Five-state model does not handle multiple simultaneous waits distinctly [OK]
Hint: Waiting state is a single block; multiple waits are not distinguished [OK]
Common Mistakes:
  • Assuming process moves to Ready after any I/O completes
  • Believing process can split into multiple processes automatically
  • Thinking process polls I/O events while Running
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard