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.
💡 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.
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.
✓ 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/5)
1. Which component is primarily responsible for saving and restoring CPU registers during a context switch?
easy
A. The Interrupt Handler
B. The CPU scheduler
C. The Memory Management Unit (MMU)
D. The Process Control Block (PCB)
Solution
Step 1: Understand the role of PCB
The PCB stores the CPU register states and other process information needed to resume execution later.
Step 2: Differentiate from scheduler and interrupt handler
The scheduler decides which process runs next but does not save registers; the interrupt handler triggers context switches but does not save registers itself.
Step 3: MMU role
The MMU handles memory address translation, unrelated to register saving.
Final Answer:
Option D -> Option D
Quick Check:
PCB contains saved CPU state -> correct component for saving/restoring registers.
Hint: PCB = process snapshot including CPU registers [OK]
Common Mistakes:
Confusing scheduler with register saving
Assuming interrupt handler saves registers
Thinking MMU handles CPU state
2. What is a key limitation of the Banker's Algorithm that affects its practical use in modern operating systems?
medium
A. It requires processes to declare their maximum resource needs in advance, which is often impractical.
B. It can only handle a single resource type, limiting its applicability.
C. It always leads to deadlocks if the system is heavily loaded.
D. It preempts resources from processes, causing starvation.
Solution
Step 1: Identify Banker's Algorithm assumptions
The algorithm requires prior knowledge of maximum resource needs for each process.
Step 2: Analyze limitations
This requirement is often unrealistic in dynamic or unpredictable environments.
Step 3: Evaluate other options
B is false; Banker's Algorithm handles multiple resource types. C is false; it avoids deadlocks rather than causing them. D is false; it does not preempt resources.
Final Answer:
Option A -> Option A
Quick Check:
Pre-declaration of max needs is the main practical limitation.
Hint: Banker's Algorithm needs max resource claims upfront [OK]
Common Mistakes:
Thinking it only supports one resource type
Believing it causes deadlocks under load
Confusing it with preemptive algorithms
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
Step 1: Review privilege separation
User mode is restricted; kernel mode has full privileges.
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.
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.
Final Answer:
Option D -> Option D
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 Peterson's algorithm is used on a modern multi-core processor with weak memory ordering (e.g., relaxed memory consistency), what is a likely issue that can arise, and how can it be addressed?
hard
A. The algorithm will cause starvation because weak memory ordering breaks bounded waiting
B. The algorithm will cause deadlock because weak memory ordering delays flag updates
C. The algorithm will work correctly without modification because it uses only atomic variables
D. The algorithm may fail mutual exclusion due to instruction reordering; inserting memory barriers can fix this
Solution
Step 1: Understand weak memory ordering impact
Modern processors may reorder instructions, causing visibility issues for shared variables.
Step 2: Effect on Peterson's algorithm
Without memory barriers, the flags and turn variables may be seen out of order, breaking mutual exclusion.
Step 3: Solution
Inserting memory fences/barriers enforces ordering and visibility, preserving correctness.
Final Answer:
Option D -> Option D
Quick Check:
Memory barriers are essential on weakly ordered architectures for software synchronization.
Hint: Weak memory ordering -> need memory barriers for Peterson's correctness
Common Mistakes:
Assuming Peterson's works without modification on all hardware
5. If a system uses a multi-level page table and a TLB, how does this affect the calculation of Effective Access Time (EAT) compared to a single-level page table system?
hard
A. EAT remains the same because TLB hides all page table lookup costs
B. EAT decreases because multi-level page tables reduce page faults
C. EAT increases because page table lookup time is longer, so TLB misses are more expensive
D. EAT is unaffected by page table structure, only by TLB hit ratio
On TLB miss, page table lookup is longer, so miss penalty increases, raising EAT.
Step 3: Analyze options
A: Incorrect, TLB does not hide all page table lookup costs. B: Incorrect, multi-level page tables do not reduce page faults. C: Correct, longer page table lookup time increases EAT on misses. D: Incorrect, page table structure affects miss penalty and thus EAT.