Internal vs External Fragmentation - Compaction & Buddy System

🎯

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.

Level	Interview Time	Suitable For	Risk
Basic Definition	30s	Screening call or initial rounds	Too shallow for detailed technical interviews
Mechanism Depth	2-3 minutes	On-site interviews at product companies	Requires 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. When a file grows beyond the capacity of direct block pointers in its inode, what sequence of steps occurs to locate the additional data blocks?

easy

A. The file system uses single indirect pointers to reference blocks that contain further direct block pointers.

B. The inode immediately switches to double indirect pointers, skipping single indirect pointers.

C. The file system allocates new direct pointers dynamically within the inode structure.

D. The inode stores the entire file content directly once direct pointers are exhausted.

Solution

1. Step 1: Recall inode pointer hierarchy

   Inodes have a fixed number of direct pointers, followed by single, double, and triple indirect pointers for larger files.

2. Step 2: Understand pointer escalation

   When direct pointers are full, the file system uses single indirect pointers, which point to blocks containing more direct pointers.

3. Step 3: Eliminate incorrect escalations

   The inode does not skip levels; it uses single indirect before double indirect pointers.

4. Step 4: Clarify inode content storage

   Inodes never store file content directly; they only store metadata and pointers.

5. Final Answer:

   Option A -> Option A

6. Quick Check:

   Single indirect pointers extend data block addressing after direct pointers [OK]

Hint: Direct -> Single Indirect -> Double Indirect pointer escalation

Common Mistakes:

• Skipping pointer levels (double indirect before single indirect)
• Assuming inode can dynamically add direct pointers
• Thinking inode stores file content directly

2. 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

3. 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

4. If the time quantum is set equal to the longest CPU burst among all processes in Round Robin scheduling, what is the expected impact on turnaround time and fairness?

hard

A. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts

B. Turnaround time approaches that of First-Come-First-Serve scheduling, but fairness among processes decreases

C. Fairness remains the same but turnaround time increases due to longer waiting times

D. Turnaround time decreases significantly and fairness improves due to fewer context switches

Solution

1. Step 1: Understand quantum equal to longest burst

   Setting quantum to longest burst means processes run mostly to completion without preemption.

2. Step 2: Compare to FCFS

   This behavior mimics FCFS, where processes run in arrival order without interruption.

3. Step 3: Analyze fairness and turnaround

   Fairness decreases because shorter processes wait longer, losing RR's time-sharing benefit. Turnaround time approaches FCFS values.

4. Step 4: Evaluate incorrect options

   Turnaround time decreases significantly and fairness improves due to fewer context switches is wrong because fewer context switches do not improve fairness. Fairness remains the same but turnaround time increases due to longer waiting times is wrong as fairness changes. Both turnaround time and fairness improve because processes get longer uninterrupted CPU bursts is wrong because fairness does not improve.

5. Final Answer:

   Option B -> Option B

6. Quick Check:

   Quantum = longest burst -> RR ≈ FCFS -> fairness ↓, turnaround ~ FCFS.

Hint: Quantum = longest burst -> RR behaves like FCFS

Common Mistakes:

• Assuming fairness always improves with larger quantum
• Believing fewer context switches always reduce turnaround
• Ignoring that RR degenerates to FCFS with large quantum

5. If a system uses preemptive SJF scheduling but the burst times of processes are not known in advance and must be estimated, which challenge is most likely to affect scheduling accuracy?

hard

A. Incorrect burst time estimates can cause frequent unnecessary preemptions

B. The scheduler will always pick the wrong process due to estimation errors

C. Non-preemptive scheduling must be used instead to avoid errors

D. Starvation is eliminated because estimates prevent preemption

Solution

1. Step 1: Understand burst time estimation impact

   Estimations can be inaccurate, causing the scheduler to preempt based on wrong assumptions.

2. Step 2: Analyze consequences

   Frequent unnecessary preemptions increase overhead and reduce efficiency.

3. Step 3: Why other options are incorrect

   B: Scheduler won't always pick wrong process; estimates can be close.
   C: Non-preemptive scheduling is a design choice, not forced by estimation.
   D: Starvation is not eliminated by estimates; it depends on scheduling policy.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Estimation errors cause scheduling inefficiency via unnecessary preemptions.

Hint: Bad burst time estimates cause too many preemptions in preemptive SJF [OK]

Common Mistakes:

• Assuming estimates always cause wrong scheduling
• Believing estimation removes starvation