Internal vs External Fragmentation - Compaction & Buddy System

▶

Steps

setup

Initialize Memory and Processes

The system starts with a single free memory block of size 64 units. No processes are running or waiting yet.

💡 Initialization sets the stage for memory allocation and fragmentation tracking.

Line:

memory = [64]; allocated = []  # STEP 1

💡 Memory starts as one large free block, no fragmentation present.

insert

Allocate 10 Units to Process 1

Process 1 requests 10 units. The system finds the smallest buddy block that fits 10 units, splitting the 64-unit block into smaller buddies until a 16-unit block is allocated.

💡 Buddy system splits blocks to fit allocation requests efficiently, minimizing wasted space.

Line:

allocate(1, 10)  # STEP 2

💡 Buddy splitting reduces internal fragmentation by allocating the smallest fitting block.

insert

Allocate 20 Units to Process 2

Process 2 requests 20 units. The system splits a 32-unit buddy block to allocate a 32-unit block (smallest power of two >= 20).

💡 Buddy system rounds allocation size to nearest power of two, which can cause internal fragmentation.

Line:

allocate(2, 20)  # STEP 3

💡 Internal fragmentation occurs when allocated block is larger than requested size.

insert

Allocate 5 Units to Process 3

Process 3 requests 5 units. The system allocates an 8-unit buddy block (smallest power of two >= 5) from remaining free memory.

💡 Small allocations cause more splits, increasing fragmentation complexity.

Line:

allocate(3, 5)  # STEP 4

💡 Internal fragmentation is visible as allocated block is larger than requested size.

delete

Deallocate 20-Unit Block from Process 2

Process 2 releases its 32-unit block, creating a free block and potentially enabling buddy merging.

💡 Deallocation frees memory but can cause external fragmentation if free blocks are scattered.

Line:

deallocate(2)  # STEP 5

💡 Freed blocks may be isolated, causing external fragmentation.

shrink

Check for Buddy Merge After Deallocation

The system checks if the freed 32-unit block has a buddy free block to merge with, but no buddy is free, so no merge occurs.

💡 Buddy merging reduces external fragmentation by combining adjacent free blocks.

Line:

try_merge_buddies()  # STEP 6

💡 Merging requires both buddies to be free; partial free blocks remain fragmented.

expand

Perform Memory Compaction

The system compacts memory by moving allocated blocks together, eliminating gaps caused by freed blocks and reducing external fragmentation.

💡 Compaction rearranges memory to create larger contiguous free blocks, improving allocation efficiency.

Line:

compact_memory()  # STEP 7

💡 Compaction reduces external fragmentation but may be costly in time and CPU cycles.

shrink

Check for Buddy Merge After Compaction

After compaction, the system checks again for buddy merges. Now adjacent free blocks are buddies and merge into a larger block.

💡 Compaction enables buddy merging by placing free blocks adjacently.

Line:

try_merge_buddies()  # STEP 8

💡 Merging after compaction reduces fragmentation further, improving memory availability.

insert

Allocate 15 Units to Process 4 After Compaction

Process 4 requests 15 units. The system allocates a 16-unit buddy block from the newly merged free space.

💡 Compaction and merging enable allocation of larger blocks that were previously fragmented.

Line:

allocate(4, 15)  # STEP 9

💡 Compaction and buddy merging improve allocation success and reduce fragmentation.

reconstruct

Final Memory State and Summary

The system shows the final memory layout with allocated blocks and free blocks merged. Internal and external fragmentation are minimized by buddy system and compaction.

💡 Final state summarizes the effectiveness of the memory management techniques.

Line:

print_memory_layout()  # STEP 10

💡 Combining buddy system and compaction effectively manages fragmentation.

memory = [64]  # STEP 1
allocated = []

def allocate(pid, size):  # STEP 2,3,4,9
    # Find smallest buddy block >= size
    # Split blocks as needed
    # Allocate block to pid
    pass

def deallocate(pid):  # STEP 5
    # Free block allocated to pid
    pass

def try_merge_buddies():  # STEP 6,8
    # Check adjacent free blocks
    # Merge if buddies
    pass

def compact_memory():  # STEP 7
    # Move allocated blocks together
    # Consolidate free space
    pass

def print_memory_layout():  # STEP 10
    # Display final memory blocks
    pass

# Simulate steps
allocate(1, 10)  # STEP 2
allocate(2, 20)  # STEP 3
allocate(3, 5)   # STEP 4
deallocate(2)    # STEP 5
try_merge_buddies()  # STEP 6
compact_memory()  # STEP 7
try_merge_buddies()  # STEP 8
allocate(4, 15)  # STEP 9
print_memory_layout()  # STEP 10

📊

Internal vs External Fragmentation - Compaction & Buddy System - Watch the Algorithm Execute, Step by Step

Watching each step reveals how the algorithm manages memory dynamically, showing the impact of fragmentation and the effectiveness of compaction and buddy merging.

Ready Queue

empty

Waiting Queue

empty

🖥CPUidlet=0

Transition new → running pid:1 - allocation request

1

running

Ready Queue

empty

Waiting Queue

empty

🖥CPU1t=1

1

Transition new → running pid:2 - allocation request

1

ready

2

running

Ready Queue

1

Waiting Queue

empty

🖥CPU2t=2

1

2

Transition new → running pid:3 - allocation request

1

ready

2

ready

3

running

Ready Queue

12

Waiting Queue

empty

🖥CPU3t=3

1

2

3

Transition ready → terminated pid:2 - deallocation

1

ready

3

running

Ready Queue

1

Waiting Queue

empty

🖥CPU3t=4

1

2

3

1

ready

3

running

Ready Queue

1

Waiting Queue

empty

🖥CPU3t=5

1

2

3

1

ready

3

running

Ready Queue

1

Waiting Queue

empty

🖥CPU3t=6

1

2

3

Transition free → merged - buddy merge after compaction

1

ready

3

running

Ready Queue

1

Waiting Queue

empty

🖥CPU3t=7

1

2

3

Transition new → running pid:4 - allocation after compaction

1

ready

3

ready

4

running

Ready Queue

13

Waiting Queue

empty

🖥CPU4t=8

1

2

3

4

1

ready

3

ready

4

ready

Ready Queue

134

Waiting Queue

empty

🖥CPUidlet=9

1

2

3

4

Key Takeaways

✓ Buddy system splits memory into power-of-two blocks to reduce internal fragmentation.

This is hard to see from code alone because the splitting logic is recursive and implicit.

✓ External fragmentation occurs when free blocks are scattered and cannot be merged without compaction.

Visualizing memory layout shows gaps that code comments alone cannot convey.

✓ Compaction rearranges allocated blocks to enable buddy merging, reducing fragmentation and improving allocation success.

The dynamic movement of blocks is difficult to grasp without step-by-step visualization.

Practice

1. You are designing a web server that must handle thousands of simultaneous client requests efficiently. Which approach is most suitable to maximize resource sharing and minimize overhead?

easy

A. Use multiple threads within a single process to handle client requests concurrently

B. Use multiple processes with shared memory segments for communication

C. Use a single-threaded process with blocking I/O for all requests

D. Use multiple processes, each handling a single client request independently

Solution

1. Step 1: Understand resource sharing in threads

   Threads within the same process share memory and resources, allowing efficient communication and lower overhead compared to processes.

2. Step 2: Compare overhead of context switching

   Thread context switching is lighter than process context switching, making threads better for high concurrency.

3. Step 3: Evaluate options

   Use multiple processes, each handling a single client request independently uses processes, which have higher overhead and less efficient resource sharing. Use a single-threaded process with blocking I/O for all requests is single-threaded and blocks, limiting concurrency. Use multiple processes with shared memory segments for communication adds complexity with shared memory and still has process overhead.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Threads maximize resource sharing and minimize overhead for concurrent tasks [OK]

Hint: Threads share memory; processes isolate resources [OK]

Common Mistakes:

• Assuming processes are always better for concurrency
• Ignoring context switching overhead differences
• Believing shared memory between processes is as simple as threads

2. When a CPU switches from running one thread to another within the same process, what sequence of events occurs internally?

easy

A. The OS terminates the current thread and creates a new thread for the next task

B. The OS saves the entire process state and reloads it for the new thread

C. The OS flushes the process's memory cache and reloads it for the new thread

D. The OS saves the thread's CPU registers and stack pointer, then loads the next thread's registers and stack pointer

Solution

1. Step 1: Identify what is saved during thread context switch

   Only the CPU registers and stack pointer specific to the thread are saved and restored, since threads share the process memory space.

2. Step 2: Understand process state remains unchanged

   The process's memory and resources remain intact; no need to save or reload the entire process state.

3. Step 3: Evaluate options

   The OS saves the entire process state and reloads it for the new thread incorrectly saves the entire process state. The OS flushes the process's memory cache and reloads it for the new thread incorrectly flushes memory cache. The OS terminates the current thread and creates a new thread for the next task incorrectly terminates and recreates threads.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Thread context switch saves/restores thread-specific CPU state only [OK]

Hint: Thread switch saves CPU registers, not whole process state [OK]

Common Mistakes:

• Confusing process context switch with thread context switch
• Assuming memory cache must be flushed on thread switch
• Believing threads are terminated and recreated on each switch

3. Why is aging used as a technique to prevent starvation, and what is a potential downside of applying aging aggressively?

medium

A. Aging increases priority of waiting processes to prevent starvation but can cause priority inversion if overused.

B. Aging decreases priority of high-priority processes to prevent deadlock but may cause livelock.

C. Aging randomly changes priorities to balance load but can lead to starvation of critical processes.

D. Aging forces processes to release resources periodically but increases overhead significantly.

Solution

1. Step 1: Understand aging purpose

   Aging gradually increases the priority of waiting processes to ensure they eventually get CPU time, preventing starvation.

2. Step 2: Identify downside

   Over-aggressive aging can cause priority inversion, where lower-priority processes gain higher priority than intended, disrupting scheduling fairness.

3. Step 3: Analyze options

   Aging increases priority of waiting processes to prevent starvation but can cause priority inversion if overused correctly states aging's purpose and downside. Aging decreases priority of high-priority processes to prevent deadlock but may cause livelock incorrectly associates aging with deadlock prevention and livelock. Aging randomly changes priorities to balance load but can lead to starvation of critical processes misrepresents aging as random priority changes. Aging forces processes to release resources periodically but increases overhead significantly confuses aging with resource release policies.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Aging = priority boost to prevent starvation, risk of priority inversion.

Hint: Aging = priority boost to avoid starvation, watch for inversion

Common Mistakes:

• Confusing aging with deadlock prevention
• Thinking aging randomly changes priorities

4. Which of the following statements about thrashing and the working set model is INCORRECT?

medium

A. Thrashing occurs when the sum of all processes' working sets exceeds total available frames

B. The working set model dynamically adjusts the number of frames allocated to each process based on recent page usage

C. Increasing the total number of processes always reduces thrashing by distributing memory pressure

D. Load control can be used alongside the working set model to prevent thrashing by limiting the number of active processes

Solution

1. Step 1: Analyze each statement

   A is correct: thrashing happens when total working sets exceed memory.
   B is correct: working set model adjusts frames dynamically.
   C is incorrect: increasing processes usually increases memory pressure, worsening thrashing.
   D is correct: load control limits active processes to prevent thrashing.

2. Final Answer:

   Option C -> Option C

3. Quick Check:

   More processes usually increase thrashing risk, not reduce it.

Hint: More processes -> more memory pressure -> more thrashing

Common Mistakes:

• Believing more processes reduce thrashing
• Confusing load control with working set adjustments
• Ignoring total memory constraints

5. If a system uses the working set model but still experiences thrashing under heavy load, which advanced technique should be applied next to mitigate thrashing?

hard

A. Increase the working set window size to capture more pages per process

B. Implement load control to reduce the number of active processes competing for frames

C. Disable page replacement algorithms to avoid unnecessary page faults

D. Assign a fixed number of frames to each process regardless of working set size

Solution

1. Step 1: Understand why thrashing persists despite working set model

   Even with working set allocation, total demand may exceed physical memory.

2. Step 2: Analyze options

   A is incorrect because increasing window size may increase working set size, worsening thrashing.
   B is correct because load control reduces active processes, lowering total memory demand.
   C is incorrect because disabling page replacement is not feasible and increases faults.
   D is incorrect because fixed allocation ignores dynamic working sets, risking thrashing.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Load control is the next step after working set model to prevent thrashing under overload.

Hint: Load control = reduce active processes to fit memory

Common Mistakes:

• Thinking increasing working set window helps
• Believing disabling page replacement reduces faults
• Assuming fixed frame allocation solves thrashing