Memory Management – Allocation, Paging, Segmentation & Replacement Strategies

1. Introduction to Memory Management

Memory management is the OS component that controls the allocation and deallocation of primary memory to processes, ensuring efficient use of the limited physical RAM while providing the illusion of a large, contiguous address space. The main objectives are:

1. Protection – isolate processes so one cannot corrupt another’s data.
2. Sharing – allow multiple processes to access common code or data.
3. Efficiency – minimize wasted memory (fragmentation) and maximize CPU utilization.

2. Memory Allocation Schemes

2.1 Fixed‑size Partitioning

• The memory is divided into a small number of fixed partitions at boot time.
• Each partition can hold exactly one process.
• Advantages: simple implementation, low overhead.
• Disadvantages: severe internal fragmentation; limited flexibility.

2.2 Variable‑size Partitioning

• Partitions are created dynamically to fit the size of incoming processes.
• Allocation strategies determine which free hole a process receives.

Worked Example – First‑Fit Allocation

Memory size = 100 KB, free holes: 20 KB, 15 KB, 30 KB, 10 KB, 25 KB.
Process P (size = 18 KB) arrives.

• Scan: first hole (20 KB) fits → allocate 18 KB, leaving a 2 KB internal fragment.
• Remaining holes: 2 KB, 15 KB, 30 KB, 10 KB, 25 KB.

2.3 Buddy System

• Memory is a power‑of‑two sized block.
• When a request arrives, the block is recursively split into halves (“buddies”) until the smallest block ≥ request size is found.
• When both buddies become free, they are coalesced.

Advantages: fast allocation/deallocation, low external fragmentation.
Disadvantages: internal fragmentation up to 50 % of the allocated block.

2.4 Slab Allocation (Kernel‑level)

• Used for objects of the same size (e.g., kernel data structures).
• Pre‑allocated caches (slabs) reduce fragmentation and allocation overhead.

3. Fragmentation

3.1 Internal Fragmentation

Occurs when allocated memory exceeds the requested size, leaving unused space inside the allocated block. Typical in fixed‑size partitions, paging, and buddy systems.

3.2 External Fragmentation

Occurs when free memory is split into many small non‑contiguous holes, none of which is large enough to satisfy a request, even though the total free memory would be sufficient.

Example from Past Exam

Memory = 100 KB, partitions: 150 KB, 200 KB, 250 KB, 100 KB, 300 KB (note: total > 100 KB, implying a typo; assume these are hole sizes after some allocations). Processes A = 175 KB, B = 125 KB.

• First‑Fit:

  • A fits into 200 KB hole → internal fragmentation = 200 − 175 = 25 KB.
  • B fits into 150 KB hole → internal fragmentation = 150 − 125 = 25 KB.

• Best‑Fit:

  • A fits into 250 KB hole → internal frag = 75 KB (worse).
  • B fits into 150 KB hole → internal frag = 25 KB.

The example illustrates how allocation policy influences internal fragmentation.

4. Paging

Paging eliminates external fragmentation by dividing both physical memory and logical address space into fixed‑size blocks called pages (logical) and frames (physical).

• Logical address = (page number, offset).
• Physical address = (frame number, offset).

4.1 Page Table

A data structure that maps page numbers to frame numbers.

Valid/Invalid bit indicates whether the page is resident in memory.

4.2 Hierarchical & Inverted Page Tables

• Hierarchical: two‑level tables reduce size for large address spaces.
• Inverted: one entry per frame, indexed by frame number; saves memory but requires hashing for lookup.

4.3 Demand Paging

Pages are loaded only when a process references them (page fault). This reduces initial load time and memory consumption.

Example – Demand Paging Fault Count

Reference string: 1, 3, 4, 2, 3, 5, 4, 3, 1, 2, 4, 6
Assume 3‑frame memory, initially empty.

Total FIFO faults = 9.

The same reference string can be traced for LRU and Clock algorithms (shown later).

5. Page Replacement Algorithms

When a page fault occurs and all frames are occupied, the OS must decide which resident page to evict.

5.1 Optimal Page Replacement (OPR)

• Definition: Replace the page whose next reference is farthest in the future.
• Why “best”: Guarantees the minimum possible page faults for a given reference string.
• Practicality: Requires future knowledge → impossible to implement; used only for benchmarking.

5.2 Least Recently Used (LRU)

• Definition: Replace the page that has not been used for the longest time.
• Implementation: Counter per page, stack, or hardware “reference bits”.
• Pros/Cons: Near‑optimal performance, but hardware support or high overhead is needed.

5.3 Clock (Second‑Chance)

• Definition: Approximation of LRU using a circular list and a single reference bit per frame.
• Algorithm:
  1. Pointer (hand) scans frames.
  2. If reference bit = 0 → replace.
  3. If reference bit = 1 → set to 0 and advance hand (give a second chance).

5.4 Comparative Table

5.5 Worked Calculation – OPR, LRU, Clock

Reference string (same as above): 1 3 4 2 3 5 4 3 1 2 4 6, 3 frames.

OPR

We look ahead each step to decide which page will be used farthest later.

OPR faults = 9 (same as FIFO in this particular string, but often lower).

LRU (using stack order: most recent on top)

LRU faults = 10.

Clock (reference bits start 0)

Assume hand starts at frame 0.

Clock faults = 11 (higher than LRU because of limited reference‑bit information).

5.6 Why OPR Is “Best but Not Practically Feasible”

• Optimality Proof: For any reference string, OPR yields the minimum possible page faults because it always discards the page whose next use is farthest away.
• Impracticality: The algorithm requires knowledge of future references, which no real system possesses. It can only be used in simulators or for theoretical comparison.

6. Virtual Memory

Virtual memory extends the apparent size of RAM by using secondary storage (disk) to hold pages that are not currently needed.

• Paging + Swapping: When a page fault occurs and no free frame exists, a victim page is written to disk (swap space) and the needed page is read in.
• Working‑Set Model: The set of pages referenced in the last $\Delta$ time units. Keeping the working set resident prevents thrashing.

6.1 Thrashing

Occurs when the system spends most of its time swapping pages rather than executing user code. Indicators:

• High page‑fault rate.
• Low CPU utilization despite many processes.

Control measures:

• Reduce degree of multiprogramming.
• Increase RAM.
• Use locality‑aware scheduling.

7. Memory Management in Linux (Brief Overview)

• Paging: 4 KB pages (default) with a two‑level page table (pgd → pte).
• Swap: Dedicated swap partition/file; swapon/swapoff commands.
• OOM Killer: Terminates processes when memory is exhausted.
• /proc/meminfo provides real‑time statistics.

8. Worked Example – CPU Utilization in Multiprogramming

Question: Compute CPU utilization when 6 processes are in memory, each spends 60 % of its time waiting for I/O.

Formula:
$$U=1-p^n$$
where $p$ = probability a process is waiting (0.60), $n$ = number of processes (6).

$$U=1-0.60^6=1-0.046656\approx 0.9533(\text{or }95.3\%)$$

Thus, with six processes, CPU utilization rises to about 95 %, illustrating the benefit of multiprogramming over monoprogramming (which would be only 40 % utilization).

9. Summary of Key Concepts

10. Frequently Asked Exam Questions

1. Define internal and external fragmentation. Provide a numeric example.
2. Explain the difference between multiprogramming and monoprogramming and compute CPU utilization for given parameters.
3. Why is OPR optimal? Why can’t it be used in real systems?
4. Given a reference string and a fixed number of frames, calculate page faults for OPR, LRU, and Clock.
5. Compare First‑Fit, Best‑Fit, and Worst‑Fit allocation strategies in a table.

11. Exam Tip

• Memorize formulas: CPU utilization $U=1-p^n$ and working‑set size concepts.
• Practice trace tables: Write down frames, reference bits, and page‑fault counts step‑by‑step; examiners love clear, ordered traces.
• Know the “why”: For OPR, be ready to explain the optimality proof in one sentence (“it evicts the page whose next reference is farthest in the future”).
• Fragmentation: When asked to differentiate, list cause, where it appears, and how each allocation scheme mitigates it.
• Time‑management: Allocate ~2 minutes per sub‑question in a 20‑minute paper; use the comparison tables you prepared to answer quickly.

---