Memory Management: Allocation, Fragmentation, Paging & Swapping

TAKEAWAYS:

• Memory management ensures efficient use of RAM and secondary storage by allocating, deallocating, and protecting memory.
• Fragmentation (internal/external) reduces usable memory; compaction and paging mitigate it.
• Allocation strategies (first-fit, best-fit, worst-fit) trade speed for efficiency.
• Virtual memory uses disk as an extension of RAM via paging/swapping, enabling larger programs.
• TLB (Translation Lookaside Buffer) speeds up address translation in paging.
• Memory-mapped I/O simplifies device communication by treating hardware as memory.

1. Introduction to Memory Management

Memory management is the core function of an OS that allocates, deallocates, and protects memory for processes. It ensures:

• Efficiency: Maximizes RAM usage.
• Isolation: Prevents processes from interfering.
• Performance: Minimizes fragmentation and latency.

Key Concepts

• Physical Memory: RAM (volatile, fast).
• Virtual Memory: Logical address space (managed by OS, may use disk).
• Memory Allocation: Assigning memory blocks to processes.
• Memory Protection: Preventing unauthorized access.

2. Memory Allocation Strategies

When a process requests memory, the OS uses one of these strategies:

First-Fit

• Allocates the first available block large enough to hold the request.
• Simple but may lead to external fragmentation.

Best-Fit

• Allocates the smallest suitable block.
• Reduces fragmentation but slower due to searching all blocks.

Worst-Fit

• Allocates the largest available block.
• Wastes memory but minimizes fragmentation.

Comparison Table

3. Fragmentation

Fragmentation occurs when free memory is split into small, unusable chunks.

Types

• Internal Fragmentation: Allocated block is larger than needed (e.g., 10KB block for 5KB process).
• External Fragmentation: Free blocks are too small or scattered (e.g., 3KB + 2KB free blocks but no 5KB block available).

Solutions

• Compaction: Rearranges memory to consolidate free blocks (requires moving processes).
• Paging: Divides memory into fixed-size blocks (pages) to eliminate external fragmentation.

4. Paging

Paging divides physical memory and logical memory into fixed-size blocks called pages (e.g., 4KB).

How Paging Works

1. Logical Address: Generated by CPU (e.g., 12345).
2. Page Table: Maps logical pages to physical frames.
3. Physical Address: Computed as frame_number * page_size + offset.

Example

• Page size = 4KB, frame size = 4KB.
• Logical address 12345 → Page number = 12345 / 4096 = 3, offset = 12345 % 4096 = 12345.
• If page 3 maps to frame 7, physical address = 7 * 4096 + 12345 = 40967.

Visualization

Logical Address (16-bit) | Page Number (12-bit) | Offset (4-bit)
       12345             |         3           |     12345

Mermaid Diagram:

5. TLB (Translation Lookaside Buffer)

• A hardware cache that speeds up page table lookups.
• Stores recently used page table entries (PTEs).
• Reduces time from O(1) (TLB hit) to O(N) (page table lookup).

Example

• If TLB has page 3 → frame 7, the CPU gets the physical address in 1 cycle.
• Without TLB, it must scan the page table (slower).

6. Segmentation

Unlike paging, segmentation divides memory into variable-sized segments (e.g., code, data, stack).

Advantages

• Logical grouping (e.g., separate code and data).
• Simpler for large programs.

Disadvantages

• External fragmentation (unlike paging).
• Requires compaction.

7. Virtual Memory

Virtual memory extends RAM using disk storage (swap space). Key techniques:

• Swapping: Entire process moved to disk.
• Paging: Only active pages kept in RAM.

Why Use Virtual Memory?

• Run larger programs than physical RAM.
• Isolate processes (prevent crashes from affecting others).

Address Translation in Paging

1. CPU generates logical address.
2. Page table maps to physical frame.
3. TLB speeds up the lookup.

Mermaid Diagram:

sequenceDiagram
    participant CPU
    participant PageTable
    participant TLB
    participant Memory
    CPU->>TLB: "Check if page 3 is cached"
    alt TLB Hit
        TLB-->>CPU: "Frame 7"
    else TLB Miss
        CPU->>PageTable: "Lookup page 3"
        PageTable-->>CPU: "Frame 7"
        TLB->>TLB: "Cache frame 7"
    end
    CPU->>Memory: "Access frame 7, offset 12345"

8. Memory-Mapped I/O

Instead of using special I/O instructions, devices are treated as memory locations.

How It Works

• OS maps device registers to memory addresses.
• CPU reads/writes to these addresses to control devices.

Example

• A USB port might be mapped to 0xFFFF0000.
• Writing 0x55 to this address enables the USB controller.

9. Real-World Examples

1. eSewa/Khalti (Payment Gateways)

• Idea: Virtual Memory allows handling thousands of transactions simultaneously.
• How: The OS uses paging to swap inactive transactions to disk, freeing RAM for active users.
• Worked Example: During a festival sale, eSewa’s server uses virtual memory to manage 10,000+ concurrent users without crashing.

2. Daraz (E-commerce)

• Idea: Memory Allocation ensures smooth order processing.
• How: Daraz’s backend uses best-fit allocation to assign memory to orders, reducing fragmentation during peak hours (e.g., Dashain sales).
• Worked Example: A 5MB order request gets allocated the smallest available block (e.g., 6MB) to avoid wasting memory.

3. NTC/Ncell (Telecom)

• Idea: Paging optimizes call handling.
• How: When a user makes a call, the OS pages in only the necessary call-handling code, freeing RAM for other users.
• Worked Example: During a network outage, Ncell’s servers use paging to swap inactive call data to disk, ensuring active calls stay connected.

10. Exam Tip

• Calculations: Expect questions on bitmap size (e.g., 2GB disk with 2KB blocks → 2GB / 2KB = 1M blocks → 1MB bitmap).
• Diagrams: Always draw page table lookups and TLB flowcharts for full marks.
• Comparisons: Know pros/cons of first-fit vs. best-fit (e.g., best-fit reduces fragmentation but is slower).
• Real-World Tie: Link concepts to apps (e.g., "How does WhatsApp use virtual memory to handle group chats?").
• Short Answers: Memorize:
  • Internal vs. external fragmentation.
  • Paging vs. segmentation.
  • TLB’s role in speeding up address translation.

11. Worked Example: Bitmap-Based Free Space

Question: A 2GB hard disk has a 2KB block size. Calculate the size of the bitmap for free space management.

Solution:

1. Total blocks = 2GB / 2KB = 1,048,576 blocks.
2. Each block needs 1 bit in the bitmap.
3. Bitmap size = 1,048,576 bits = 128KB.

Mermaid Diagram:

graph TD
    A["2GB Disk"] -->|"Divide by 2KB"| B["1,048,576 Blocks"]
    B --> C["Bitmap: 1 bit per block"]
    C --> D["128KB Bitmap: 1,048,576 bits"]
    D --> E["Example: Block 1000 = 1 (allocated), Block 2000 = 0 (free)"]

12. Visuals

1. Physical vs. Virtual Memory

(Shows how logical addresses map to physical frames with a page table.)

2. TLB vs. Page Table Lookup

(Illustrates TLB hit/miss scenarios.)

3. External Fragmentation

(Shows scattered free blocks of 2KB, 3KB, 1KB.)

13. Key Formulas

14. Common Mistakes to Avoid

• Confusing paging and segmentation: Paging uses fixed sizes; segmentation uses variable segments.
• Ignoring TLB: Always mention TLB in address translation questions.
• Wrong bitmap calculation: Remember 1 bit per block, not per byte.
• Overlooking fragmentation: External fragmentation is a key exam topic.