Memory Management: Allocation, Swapping, Paging, Segmentation & Performance

TAKEAWAYS:

• Memory management allocates and deallocates memory to processes efficiently using contiguous, paging, or segmentation techniques.
• Allocation strategies (first-fit, best-fit, worst-fit) differ in speed and fragmentation trade-offs.
• Swapping temporarily moves processes to disk when RAM is full, but increases I/O overhead.
• Page replacement algorithms (FIFO, LRU, Optimal) minimize page faults but require different hardware support.
• Memory protection uses hardware (base/bound registers, page tables) to prevent unauthorized access.
• Performance metrics like hit ratio and page fault rate determine system efficiency.

---

Core Concepts: What is Memory Management?

Memory management is the OS’s job of allocating and deallocating memory to processes while ensuring efficient use, protection, and performance. It handles:

• Physical memory (RAM): Limited and shared among processes.
• Logical memory (virtual address space): Each process sees its own continuous memory.
• Backing store (disk): Used when RAM is full (swapping).

Why is it critical?

Without memory management:

• Processes would overwrite each other’s memory (crashes).
• RAM would fragment (wasted space).
• The system would run out of memory quickly.

---

1. Memory Allocation Techniques

Three main methods to allocate memory to processes:

A. Contiguous Memory Allocation

Processes are allocated contiguous blocks of memory. Three sub-techniques:

1. Single Partitioning: Only one process runs at a time (batch systems).
2. Fixed Partitioning: Memory divided into fixed-size blocks (wastage if process size ≠ block size).
3. Dynamic Partitioning: Memory divided into variable-sized blocks (better fit but external fragmentation).

How it works (Fixed Partitioning Example)

• Example: A system with 100 MB RAM divided into:
  • Block 1: 30 MB (Process A)
  • Block 2: 40 MB (Process B)
  • Block 3: 30 MB (unused)
• Problem: If Process C needs 25 MB, it cannot fit in Block 3 (wastage).

Allocation Strategies (Dynamic Partitioning)

Worked Example (First-Fit Allocation)

• Initial Memory: [100 MB free]
• Processes:
  1. P1 (20 MB) → Allocated at 0–19 MB.
  2. P2 (30 MB) → Allocated at 20–49 MB.
  3. P3 (15 MB) → Allocated at 50–64 MB.
  4. P4 (40 MB) → Cannot fit (only 36 MB free at 65–99 MB).
• Result: External fragmentation (free blocks: 65–99 MB).

---

2. Paging

Divides physical memory into fixed-size blocks (frames) and logical memory into fixed-size blocks (pages).

• No external fragmentation (since all blocks are fixed-size).
• Internal fragmentation may occur (wasted space in last page).

How Paging Works

```mermaid
graph LR
    A["Process Logical Memory"] -->|Page 0| B["Page Table"]
    A -->|Page 1| B
    A -->|Page 2| B
    B -->|Frame 3| C["Physical Memory (Frames)"]
    B -->|Frame 7| C
    B -->|Frame 12| C

• Page Table: Maps logical pages to physical frames.
• Page Table Entry (PTE): Contains:
  • Frame number (where the page is stored).
  • Valid bit (1 = in RAM, 0 = on disk).
  • Protection bits (read/write/execute).
  • Reference bit (used by replacement algorithms).

Page Table Example

Worked Example (Page Fault)

1. Process accesses Page 2.
2. Valid bit = 0 → Page fault (page not in RAM).
3. OS loads Page 2 from disk (swap space) into a free frame (e.g., Frame 5).
4. Update Page Table: Frame # = 5, Valid bit = 1.
5. Restart the instruction.

---

3. Segmentation

Divides memory into variable-sized segments (e.g., code, data, stack).

• No internal fragmentation (segments fit exactly).
• External fragmentation still occurs.

How Segmentation Works

```mermaid
graph TD
    A["Process"] --> B["Code Segment"]
    A --> C["Data Segment"]
    A --> D["Stack Segment"]
    B -->|Base Address| E["Physical Memory"]
    C -->|Base Address| E
    D -->|Base Address| E

• Segment Table: Maps segment name to (base, limit).
• Example: A process has:
  • Code (10 KB), Data (5 KB), Stack (3 KB).
  • Segment Table:

    Segment	Base	Limit
    Code	1000	10
    Data	2000	5
    Stack	3000	3

Worked Example (Segmentation Fault)

• Process tries to access address 3010 (Stack segment limit = 3003).
• Hardware checks: 3010 > 3003 → Segmentation fault (access violation).

---

4. Paging vs. Segmentation

Hybrid Approach: Paged Segmentation (used in some OS like Solaris).

• Segments divided into pages.
• Combines logical grouping (segments) + efficient allocation (pages).

---

5. Page Replacement Algorithms

When a page fault occurs and no free frames exist, the OS must replace an existing page. Common algorithms:

A. First-In-First-Out (FIFO)

• Replaces the oldest page in memory.
• Problem: May replace a page that will be used soon (Belady’s Anomaly).

Example:

• Frames: [1, 2, 3]
• Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Page Faults: 9 (high).

B. Least Recently Used (LRU)

• Replaces the page not used for the longest time.
• Requires hardware support (reference bits + clock algorithm).

Example:

• Frames: [1, 2, 3]
• Page Reference String: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
• Page Faults: 7 (better than FIFO).

C. Optimal (OPT)

• Replaces the page that will not be used for the longest time in the future.
• Theoretical (cannot implement in practice).

Example:

• Same string → Page Faults: 4 (best possible).

D. Clock (Approximation of LRU)

• Uses a circular list + reference bit.
• Steps:
  1. Scan pages in a circular order.
  2. Replace the first page with reference bit = 0.
  3. Set all reference bits to 0 after scan.

Worked Example (Clock Algorithm)

```mermaid
stateDiagram-v2
    [*] --> NeedFrame
    NeedFrame --> CheckReferenceBit: Is ref bit = 1?
    CheckReferenceBit -->|Yes| MoveToNext: Move to next page
    MoveToNext --> CheckReferenceBit
    CheckReferenceBit -->|No| ReplacePage: Replace this page
    ReplacePage --> [*]

• Example:
  • Frames: [1 (ref=1), 2 (ref=0), 3 (ref=1)]
  • Scan starts at Page 1 → ref=1 → move to Page 2 → ref=0 → replace Page 2.

---

6. Thrashing

• Problem: Excessive page faults due to insufficient frames.
• Symptoms:
  • CPU spends more time swapping than executing.
  • Performance degrades (high page fault rate).
• Solution: Working Set Model (allocate frames based on a process’s active pages).

Real-World Analogy (Nepalese Traffic)

• Imagine Kathmandu traffic where:
  • Pages = Cars.
  • Frames = Parking slots.
  • Thrashing = Too many cars waiting (high congestion).
  • Solution = More parking slots (like adding RAM).

---

7. Memory Protection & Sharing

A. Protection Mechanisms

• Base and Limit Registers (for segmentation):
  • Base: Starting address of segment.
  • Limit: Size of segment.
  • Check: If logical address > limit → access violation.
• Page Tables:
  • Protection bits (R/W/X) in PTE.
  • Example: A page marked R/O cannot be modified.

B. Memory Sharing

• Shared Pages: Multiple processes use the same physical page (e.g., shared libraries in Linux).
• Example:
  • Khalti App shares the same libc.so across all users.
  • Saves memory (only one copy in RAM).

---

8. Swapping

• Temporary removal of a process from RAM to disk (swap space).
• Types:
  1. Swap-in: Load process from disk to RAM.
  2. Swap-out: Move process from RAM to disk.
• Overhead: High I/O cost (disk is slower than RAM).

Real-World Example (Daraz Order Processing)

• Imagine Daraz’s order queue:
  • RAM = Fast servers (handling active orders).
  • Disk = Backup queue (old orders moved to disk).
  • If too many orders arrive → swap-out inactive orders to disk.

---

9. Performance Metrics

Example Calculation:

• Page References: 1000
• Page Faults: 50
• Hit Ratio = (1000 – 50)/1000 = 95% (good).
• Page Fault Rate = 50/1000 = 0.05 faults/1000 (low).

---

In the Real World

1. eSewa (Nepal) – Memory Management in Mobile Apps

• Idea Used: Paging + Caching
• How:
  • eSewa app loads only critical pages (login, payment) into RAM.
  • Other pages (history, settings) are paged in/out as needed.
  • Caching: Frequently used data (e.g., recent transactions) stays in RAM.
• Result: Faster response even on low-end phones.

2. Ncell’s Billing System – Database Memory Management

• Idea Used: Segmentation + Shared Memory
• How:
  • Segments:
    • Billing Segment (handles payments).
    • Customer Data Segment (stores profiles).
    • Audit Log Segment (records transactions).
  • Shared Memory: Multiple billing servers access the same customer database (reduces redundancy).
• Result: Efficient memory use, faster updates.

3. Pathao’s Ride-Matching Algorithm – Thrashing Avoidance

• Idea Used: Working Set Model
• How:
  • Active Riders/Drivers: Kept in RAM (high priority).
  • Inactive Users: Moved to disk (swap space).
  • If too many users → increase RAM allocation (like adding more servers).
• Result: Prevents system slowdowns during peak hours (e.g., 7–9 PM).

---

Exam Tip

What Examiners Look For

1. Diagrams: Always draw page tables, segment tables, or memory allocation when asked.

   • Example Question: "Show how paging works with a page table."
   • Your Answer: Draw a page table mapping + explain page fault handling.

2. Comparisons: Know paging vs. segmentation trade-offs (fragmentation, protection).

   • Example Question: "Why does Linux use paging?"
   • Your Answer:

     "Linux uses paging because:

     • Avoids external fragmentation (fixed-size pages).
     • Supports virtual memory (swap space).
     • Easier memory protection (per-page permissions)."

3. Calculations: Practice page fault rate, hit ratio, and replacement algorithm traces.

   • Example Question: "Calculate page faults for FIFO with reference string 1,2,3,4,1,2,5."
   • Your Answer:

     "Frames: 3 Steps:

     1. Load 1, 2, 3 → 3 faults.
     2. 4 → replace 1 → 4 faults.
     3. 1 → replace 2 → 5 faults.
     4. 2 → replace 3 → 6 faults.
     5. 5 → replace 4 → 7 faults. Total = 7 faults."

4. Real-World Links: Relate concepts to Nepalese apps (eSewa, Khalti) or systems (NTC, NEPSE).

   • Example Question: "How does memory management apply to NEPSE’s trading system?"
   • Your Answer:

     "NEPSE’s system uses:

     • Paging to load active trades into RAM.
     • Swapping for historical data (moved to disk).
     • Shared memory for multiple traders accessing the same stock data."

5. Shortcuts for Full Marks:

   • For allocation strategies: Always mention speed vs. fragmentation trade-off.
   • For replacement algorithms: Compare FIFO (simple), LRU (better), OPT (theoretical).
   • For protection: Mention hardware (MMU) + software (page tables).

---

Common Mistakes to Avoid

❌ Assuming all algorithms are equally good → OPT is theoretical; FIFO can thrash. ❌ Ignoring hardware support → LRU needs reference bits; segmentation needs base/limit registers. ❌ Mixing paging and segmentation → Paging = fixed-size, segmentation = variable-size. ❌ Forgetting external/internal fragmentation → Contiguous = external; paging = internal. ❌ Not drawing diagrams → Examiners expect visuals for memory layouts.

---

Quick Revision Table