Memory Management

Memory Management

1. Definition and Need

Memory management is the OS function that allocates, protects, shares and reclaims main memory (RAM) among processes, giving each process its own address space. It answers four questions:

1. Where in RAM does a process go? (allocation)
2. How do we stop one process from writing into another's memory? (protection)
3. How can processes share code and data safely? (sharing)
4. What happens when total demand exceeds physical RAM? (virtual memory)

Without it, every program would have to know physical addresses, one buggy program could destroy another, and the machine could run only one program at a time.

2. Logical vs Physical Address

• Logical (virtual) address — generated by the CPU as the program runs; the program is written entirely in terms of these.
• Physical address — the actual address on the memory bus.
• The Memory Management Unit (MMU) translates one to the other at run time, usually with base and limit registers (or page tables):

A reference beyond the limit traps to the OS — this is how memory protection is enforced on every single access, at hardware speed.

3. Contiguous Allocation

Fixed (static) partitioning — memory is divided into fixed-size partitions at boot; each partition holds one process.

• Simple, but wastes space inside a partition when a process is smaller (internal fragmentation) and limits the number of processes and maximum program size.

Variable (dynamic) partitioning — partitions are created to fit the process exactly.

• No internal waste, but as processes come and go, memory develops unusable gaps (external fragmentation); these can be reduced by compaction (shifting processes together — expensive, and impossible with run-time binding unless relocation hardware exists).

Placement algorithms for choosing a free hole: first fit (first hole big enough), best fit (smallest sufficient hole), worst fit (largest hole), next fit.

Worked example — holes of 100K, 500K, 200K, 300K, 600K; requests 212K, 417K, 112K, 426K:

Request	First fit	Best fit
212K	500K hole → 288K left	300K hole → 88K left
417K	600K hole → 183K left	500K hole → 83K left
112K	288K hole → 176K left	200K hole → 88K left
426K	cannot fit (no hole ≥ 426K)	600K hole → 174K left

First fit is fastest; best fit leaves the smallest leftover holes but must search the whole list; worst fit leaves the largest leftover holes but quickly produces unusable fragments.

4. Paging

Paging removes external fragmentation by dividing logical memory into fixed-size pages and physical memory into frames of the same size; any page can go into any free frame.

• The page table of each process maps page number → frame number; a page-table base register points to it.
• Address translation: a logical address is split into (page number p, offset d); frame = pageTable[p]; physical address = frame × page size + d.
• Because every access would need two memory reads (page table, then data), a TLB (Translation Lookaside Buffer) caches recent translations.
• Effective Access Time: EAT = h × (TLB time + memory time) + (1 − h) × (TLB time + 2 × memory time).
  Numerical: h = 0.98, TLB = 10 ns, memory = 100 ns → EAT = 0.98 × 110 + 0.02 × 210 = 107.8 + 4.2 = 112 ns (versus 200 ns without a TLB).
• Internal fragmentation remains only in the last page of a process (at most page size − 1 bytes).

5. Segmentation

Segmentation divides a program along logical units — code, data, stack, functions, arrays — each with a name, a base and a limit.

Aspect	Paging	Segmentation
Division	Fixed-size pages, invisible to the programmer	Variable-size logical segments, visible
Fragmentation	Internal (last page)	External (between segments)
Table	Page table (page → frame)	Segment table (segment → base, limit)
Advantage	No external fragmentation, simple allocation	Matches program structure, easy sharing and protection
Address	page number + offset	segment number + offset

Segmentation with paging (used by x86) combines both: a segment is divided into pages, so the segment provides the logical view and paging provides efficient physical allocation.

6. Virtual Memory

Virtual memory lets a process execute even when it is only partially in RAM: pages are loaded on demand, and the rest stay on disk in the swap area.

Steps when the CPU accesses a page that is not in memory (page fault):

 1. MMU raises a page-fault trap
 2. OS checks the address; if invalid → terminate the process (segmentation fault)
 3. OS finds a free frame, or selects a victim page and writes it back if dirty
 4. OS reads the required page from swap/disk into the frame
 5. Page table is updated (present bit, frame number)
 6. The faulting instruction is RESTARTED — the process never notices

Replacement algorithms (choose which page to evict): FIFO (may show Belady's anomaly — more frames, more faults), LRU (good, needs reference history), Optimal/OPT (theoretical best, needs the future). Standard example — reference string 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1 with 3 frames: FIFO = 15 faults, LRU = 12, OPT = 9.

Cost of a page fault: EAT = (1 − p) × memory time + p × fault service time.
With p = 0.001, memory = 200 ns, fault service = 8 ms → EAT = 0.999 × 200 + 0.001 × 8,000,000 ≈ 8199.8 ns — a fault rate of only 0.1% makes the machine 40× slower, which is why fault rates must stay below about 0.00001.
Thrashing — the machine spends more time paging than executing because too many processes compete for too few frames; corrected by the working-set model or page-fault-frequency control.

7. Fragmentation Summary

Term	Meaning	Occurs in	Cure
Internal fragmentation	Allocated block is bigger than needed; waste inside	Fixed partitions, last page	Smaller blocks/pages
External fragmentation	Free memory exists, but scattered in unusable holes	Variable partitions, segments	Compaction, paging

8. Exam Points

• Explain contiguous allocation: fixed vs variable partitioning, with the placement algorithms — 5-7 marks, frequent.
• Numerical: apply first fit / best fit / worst fit to a given set of holes and requests — 5 marks.
• Explain paging with address translation and compute effective access time with a TLB — 5-7 marks, very frequent.
• Differentiate paging and segmentation; explain segmentation with paging — 5 marks, almost certain.
• What is virtual memory? Explain demand paging and the page-fault handling steps — 5-7 marks.
• Compare FIFO, LRU and Optimal page replacement; numerical on a reference string — 5 marks.
• Define internal and external fragmentation with the remedy for each — 3-5 marks.
• What is thrashing and how is it controlled? — 3 marks.