Bird
Raised Fist0
Interview Prepoperating-systemseasyAmazonMicrosoftTCSInfosys

Internal vs External Fragmentation - Compaction & Buddy System

Choose your preparation mode3 modes available
▶
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.
📊
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.
Step 1/10
·Active fill★Answer cell
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/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

  1. Step 1: Understand the role of PCB

    The PCB stores the CPU register states and other process information needed to resume execution later.
  2. 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.
  3. Step 3: MMU role

    The MMU handles memory address translation, unrelated to register saving.
  4. Final Answer:

    Option D -> Option D
  5. 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

  1. Step 1: Identify Banker's Algorithm assumptions

    The algorithm requires prior knowledge of maximum resource needs for each process.
  2. Step 2: Analyze limitations

    This requirement is often unrealistic in dynamic or unpredictable environments.
  3. 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.
  4. Final Answer:

    Option A -> Option A
  5. 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

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

  1. Step 1: Understand weak memory ordering impact

    Modern processors may reorder instructions, causing visibility issues for shared variables.
  2. Step 2: Effect on Peterson's algorithm

    Without memory barriers, the flags and turn variables may be seen out of order, breaking mutual exclusion.
  3. Step 3: Solution

    Inserting memory fences/barriers enforces ordering and visibility, preserving correctness.
  4. Final Answer:

    Option D -> Option D
  5. 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
  • Confusing deadlock with visibility delays
  • Believing atomic variables alone guarantee correctness
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

Solution

  1. Step 1: Understand multi-level page tables

    Multi-level page tables require multiple memory accesses per lookup, increasing page table access time.
  2. Step 2: Impact on EAT

    On TLB miss, page table lookup is longer, so miss penalty increases, raising EAT.
  3. 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.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Longer page table lookup -> higher miss penalty -> higher EAT.
Hint: Multi-level page tables -> longer lookup -> higher EAT on TLB miss [OK]
Common Mistakes:
  • Assuming TLB hides all page table lookup costs
  • Confusing page fault rate with page table lookup time
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