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

2. In a system where multiple threads need to access a limited number of identical resources concurrently, which synchronization primitive is most appropriate to control access?

easy

A. Mutex, because it ensures exclusive ownership and prevents simultaneous access

B. Spinlock, because it busy-waits until the resource is free

C. Binary semaphore, because it allows only one thread at a time

D. Counting semaphore, because it can track and limit access to multiple identical resources

Solution

1. Step 1: Understand resource sharing scenario

   Multiple identical resources mean more than one thread can access simultaneously but limited by resource count.

2. Step 2: Evaluate synchronization primitives

   Mutex and binary semaphore allow only one thread at a time, unsuitable for multiple identical resources.

3. Step 3: Counting semaphore suitability

   Counting semaphore maintains a count of available resources, allowing multiple threads up to the count.

4. Step 4: Spinlock consideration

   Spinlocks are low-level and busy-wait, not ideal for managing multiple identical resources efficiently.

5. Final Answer:

   Option D -> Option D

6. Quick Check:

   Counting semaphore matches the scenario of multiple identical resources.

Hint: Counting semaphore counts resources; mutex/binary semaphore allow only one.

Common Mistakes:

• Confusing mutex with counting semaphore for multiple resources
• Assuming binary semaphore can handle multiple identical resources
• Believing spinlocks are suitable for resource counting

3. Which component is responsible for switching the CPU from user mode to kernel mode when a system call is invoked?

easy

A. The user-level application itself triggers the mode switch directly

B. The CPU hardware via a software interrupt or trap mechanism

C. The operating system scheduler decides when to switch modes

D. The device driver initiates the mode switch

Solution

1. Step 1: Understand system call invocation

   System calls are invoked by user programs to request kernel services. This requires a mode switch from user to kernel mode.

2. Step 2: Role of CPU hardware

   The CPU provides a mechanism (trap or software interrupt) that safely switches the mode and transfers control to the OS kernel.

3. Step 3: Why other options are incorrect

   The user-level application itself triggers the mode switch directly is wrong because user applications cannot directly change CPU mode for protection reasons. The operating system scheduler decides when to switch modes is incorrect because the scheduler manages process execution but does not trigger mode switches on system calls. The device driver initiates the mode switch is wrong because device drivers run in kernel mode and do not initiate mode switches from user mode.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   System call -> trap -> CPU switches mode -> kernel handles request [OK]

Hint: CPU hardware trap triggers mode switch on system call

Common Mistakes:

• Thinking user code can directly switch CPU mode
• Confusing scheduler role with mode switching
• Believing device drivers initiate user-to-kernel transitions

4. What is the primary trade-off when choosing a very small time quantum in Round Robin scheduling?

medium

A. Processes with longer CPU bursts get more CPU time per cycle

B. Longer average turnaround time due to processes waiting longer in the queue

C. Reduced fairness among processes with different burst lengths

D. Increased context switching overhead leading to reduced CPU efficiency

Solution

1. Step 1: Understand impact of small quantum

   A very small quantum causes frequent context switches, which consume CPU cycles and reduce efficiency.

2. Step 2: Analyze other options

   Longer average turnaround time due to processes waiting longer in the queue is incorrect because smaller quantum generally reduces waiting time for short processes. Processes with longer CPU bursts get more CPU time per cycle is false; small quantum limits CPU time per cycle for long bursts. Reduced fairness among processes with different burst lengths is incorrect because smaller quantum improves fairness.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Small quantum -> more context switches -> overhead ↑ -> efficiency ↓.

Hint: Small quantum -> high context switch overhead

Common Mistakes:

• Assuming smaller quantum always improves turnaround time
• Believing small quantum favors longer processes
• Confusing fairness impact with quantum size

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