Memory Management

Programs expand to fill all the memory available, and then some. A laptop with 8 GB may run programs that together want 20 GB.

This unit explains how the OS divides RAM among processes, protects them from each other, and uses disk to create the illusion of more memory than exists: virtual memory.

It is rich in numerical questions (placement strategies, page replacement, address translation, effective access time), all verified here.

5.1 Basic memory management

Each level is smaller, faster and costlier per byte than the one below. The OS manages the main-memory level and its relationship with disk.

Logical versus physical address space

The logical (virtual) address is generated by the CPU; the physical address is what the memory hardware sees. The hardware memory-management unit (MMU) translates one into the other at run time.

The set of all logical addresses of a program is its logical address space; the corresponding physical addresses form the physical address space.

With simple relocation the MMU adds a relocation (base) register to every logical address and checks it against a limit register. The program only ever sees logical addresses 0 to max.

Memory management without swapping or paging: monoprogramming and fixed partitions

The simplest scheme runs one program at a time, with the OS in low memory (MS-DOS): no protection and no multiprogramming.

To run several programs, memory is divided into fixed partitions (IBM OS/MFT): a job goes into a partition large enough for it. With variable partitions (OS/MVT), the OS creates a partition of exactly the size requested.

	Fixed partitioning	Variable partitioning
Partition size	set at boot	created per process
Waste	internal fragmentation	external fragmentation
Degree of multiprogramming	limited by number of partitions	limited by memory
Overhead	simple tables	free-list management, compaction

Swapping

When memory is too small for all processes, the OS swaps a whole process out to disk (backing store) and back later. A swapped-out process's memory is reused. The transfer time dominates: swapping a 100 MB process at 100 MB/s costs about 1 s each way.

Keeping track of free memory

Bitmaps. Memory is divided into allocation units; one bit per unit says free (0) or used (1). With 4 KB units, 1 GB of RAM has 2³⁰/2¹² = 262,144 units, so the bitmap is 262,144 bits = 32 KB.

Simple, constant size, but finding a run of k free units needs a slow scan. A smaller unit means a bigger bitmap; a larger unit wastes more space inside the last unit of each process.

Linked lists. A list of segments, each marked process (P) or hole (H) with start and length. When a process ends, its entry merges with neighbouring holes (a doubly linked list makes this quick). With the list sorted by address, the algorithms below apply.

Fragmentation, coalescing and compaction

Internal fragmentation: space inside an allocated block that the process does not use (a 4,096-byte page holding 4,000 bytes wastes 96). External fragmentation: enough total free memory exists but in pieces too small to use.

The 50 % rule: with first fit, for every N allocated blocks about N/2 are lost to fragmentation. Remedies:

• Coalescing: merge adjacent free holes, done when a process ends.
• Compaction: move all processes to one end to make one large hole. It works only if relocation is dynamic (via the base register) and costs CPU and time.
• Non-contiguous allocation (paging and segmentation) avoids the problem by not requiring one contiguous block.

Relocation and protection

Two problems arise when many programs share memory: where will my program load (relocation), and how do I stop other programs touching my memory (protection).

Static relocation patches addresses at load time; dynamic relocation uses a base register at run time, and a limit register gives protection.

Paged and segmented systems use per-page or per-segment protection bits (read, write, execute).

5.2 Paging

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size. Any page can go into any free frame, so external fragmentation disappears. The OS keeps a page table per process mapping page number → frame number.

A logical address of m bits with page size 2ⁿ splits into a page number p (the top m − n bits) and an offset d (the low n bits). The physical address is frame × page size + offset.

Internal fragmentation averages half a page per process. Small pages waste less but need bigger page tables and more disk transfers; typical sizes are 4 KB to 64 KB.

Page-table size and structures

A 32-bit address space with 4 KB pages has 2²⁰ = 1,048,576 pages. At 4 bytes per entry the page table is 4 MB per process, too large to keep contiguous. Solutions:

Structure	Idea	Use
Hierarchical (multilevel) page table	page the page table: 32 bits = 10 (outer) + 10 (inner) + 12 (offset); only the used inner tables exist	32-bit systems; x86-64 uses four levels
Hashed page table	hash the page number into a table of chains of (page, frame)	sparse address spaces > 32 bits
Inverted page table	one entry per frame (not per page), holding (process id, page); search by hash	PowerPC, UltraSPARC; with 4 GB RAM and 4 KB pages: 4 GB/4 KB = 1,048,576 entries regardless of the number of processes, but lookup needs hashing and sharing is harder
Shared pages	the page tables of two processes point to the same frame	shared code (editors, libraries), copy-on-write after fork

The translation look-aside buffer (TLB)

Every memory access would otherwise need two memory accesses (page table, then data). The TLB is a small, fast associative cache of recent (page → frame) pairs. A hit costs the TLB lookup only; a miss consults the page table in memory.

Block mapping versus direct mapping

Textbooks use these two terms loosely. In the reading used here: direct mapping keeps one table entry for every page (a page table as above): fine-grained and flexible, but the table is large.

Block mapping keeps one entry per larger block (a group of pages or a segment) and the virtual address is split into block number and displacement within the block: a much smaller table, at the price of coarser placement and wasted space inside blocks.

Huge pages (2 MB, 1 GB) and segments follow the block idea.

5.3 Virtual memory

Background

A program rarely needs all its pages at once, and often has code that runs rarely (error handlers).

Virtual memory separates logical from physical memory: a program may be larger than RAM; only the pages in use need to be resident; more programs fit in memory (better CPU utilisation).

Demand paging

Pages are loaded only when referenced (lazy swapper). Each page-table entry has a valid/present bit. A reference to a page not in memory causes a page fault:

1. The MMU traps to the OS (page-table entry invalid).
2. The OS checks that the reference was legal; if not, the process is terminated.
3. The OS finds a free frame (or chooses a victim by the replacement algorithm; if the victim is dirty, writes it back first).
4. It schedules a disk read of the page into the frame.
5. When the read completes, the page table is updated (valid = 1).
6. The faulting instruction is restarted.

Page replacement

When no frame is free, a victim page is evicted. A modify (dirty) bit avoids writing back unmodified pages. We evaluate algorithms on a reference string by counting page faults.

FIFO: evict the oldest page; simple but may evict a heavily used page. Optimal (OPT, Bélády): evict the page that will not be used for the longest time; gives the minimum faults but needs the future, so it serves as a yardstick.

LRU (least recently used): evict the page unused for the longest time, using the past as an estimate of the future; needs hardware support (counters or a stack).

Second chance (SCP): FIFO with a reference bit: if the oldest page's R = 1 it is cleared and the page is moved to the back (a second chance); if R = 0 it is evicted.

The clock algorithm implements it with a circular list and a moving hand.

Belady's anomaly

With FIFO, more frames can produce more faults. For the string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5: FIFO gives 9 faults with 3 frames but 10 with 4 frames.

LRU and OPT give 10 → 8 and 7 → 6 for the same change; they are stack algorithms, whose resident set with n frames is always a subset of that with n + 1, so they cannot suffer the anomaly.

Thrashing and the working set

If a process has too few frames, it faults constantly, replacing pages it needs again immediately: it spends more time paging than computing, and CPU utilisation collapses.

If the OS then sees low utilisation and admits more processes, things get worse.

The working-set model (Denning) keeps in memory the set of pages referenced in the last Δ references; if the sum of all working sets exceeds memory, suspend a process.

Another approach is page-fault frequency (PFF) control: add frames when the fault rate exceeds an upper bound and remove them below a lower bound.

5.4 Segmentation

Segmentation supports the programmer's view: a program is a set of logical units (main, functions, stack, symbol table, arrays), each a segment of variable length. An address is a pair ⟨segment number, offset⟩.

The segment table has for each segment a base and a limit; if offset ≥ limit the hardware traps.

Segmentation has no internal fragmentation, makes sharing and protection natural (a code segment is read-only and executable), but suffers external fragmentation and needs compaction.

Segmentation with paging (Intel x86 in 32-bit mode, MULTICS) combines the two: the logical address goes through the segment table to give a linear address, which is then paged.

Each segment has its own page table, so a segment need not be contiguous, and the external fragmentation of pure segmentation disappears.

	Paging	Segmentation
Unit	fixed-size page (invisible to programmer)	variable-size segment (logical, visible)
Fragmentation	internal	external
Address	one number (split by hardware)	two numbers: segment and offset
Sharing/protection	per page, harder to match logical units	per segment, natural

5.5 Seeing the ideas: memory, swap space and the page table

Memory management is mostly arithmetic on addresses, so the figures below are drawn from computed numbers.

The plate shows the physical memory that the OS manages, a hard-disk platter that holds swap space for pages pushed out of RAM, and the page table that connects the two.

The figures then show the three placement strategies, address translation with a page table and TLB, the page-replacement traces and Belady's anomaly.

(a) RAM module = frames

(b) Disk platter = swap space

(c) Page table for 4 KB pages

5.5.1 Eight advantages of virtual memory

1. Programs larger than RAM can run. Only the pages in use must be in memory; the rest stay on disk. A 4 GB program can run on a laptop with 2 GB RAM. The programmer does not have to cut the program into overlays.
2. More programs at the same time. Because each program needs only part of its pages in RAM, more processes fit in memory. The degree of multiprogramming and CPU use rise. A lab PC in a Nepali college can keep a browser, an IDE and a PDF reader open together.
3. Protection between processes. Each process has its own page table, so it cannot name another process's memory. A bug or a virus in one program cannot read or overwrite the pages of another. This is basic to any phone that holds banking apps.
4. No external fragmentation. Pages and frames have the same size, so any free frame can hold any page. Memory is not wasted in odd-sized holes. Only a little internal fragmentation remains in the last page.
5. Simple programming model. Every program sees one large, continuous address space starting at zero. The compiler and linker need not know where the program will lie in RAM. The same executable runs on a 4 GB and an 8 GB machine.
6. Sharing of code and data. Several processes can map the same frames, for example the C library or a read-only program file. Fifty copies of a browser tab share one copy of the code. This saves memory and makes fork cheap through copy-on-write.
7. Faster start-up. With demand paging a program starts as soon as its first page is loaded. The rest is brought in only when needed. A large application opens in seconds instead of waiting for the whole file.
8. Efficient use of memory. Pages that are never used, such as error-handling code, never occupy RAM. Pages that have not been used for a long time are moved to disk and the freed frames serve active programs. The OS keeps the most useful pages in the fastest memory.

Formula and fact sheet

• Physical address = frame × page size + offset; page = ⌊LA / page size⌋; offset = LA mod page size.
• Page-table entries = address space / page size. Two-level 32-bit/4 KB: 10 + 10 + 12 bits.
• Inverted page table entries = RAM / page size.
• EAT with TLB = h(t + m) + (1 − h)(t + 2m). Demand paging: EAT = (1 − p)·m + p·(fault time).
• FIFO: Belady's anomaly possible. OPT is minimum; LRU and OPT are stack algorithms.
• Bitmap size = memory / allocation unit bits.

Chapter summary

• The MMU maps logical to physical addresses; base and limit registers give relocation and protection.
• Contiguous allocation suffers fragmentation; fit strategies, coalescing and compaction mitigate it.
• Paging removes external fragmentation; page tables are made practical by multilevel, hashed and inverted structures and the TLB.
• Demand paging loads pages on first use; page faults are costly, so the replacement policy matters. OPT is a lower bound, LRU approximates it, FIFO is simple but anomalous.
• Thrashing results when working sets do not fit; segmentation offers a programmer's view and combines with paging.

Practice

1. Differentiate logical and physical addresses. What does the MMU do?
2. Explain internal and external fragmentation. Which does paging cause?
3. Holes of 150, 350, 100, 600, 250 KB (in order). Place 210, 130, 480, 90 KB by first fit, best fit and worst fit.
4. A bitmap tracks 2 GB of memory with 8 KB allocation units. How big is it?
5. Page size 2 KB; page table 0→6, 1→2, 2→8, 3→1. Translate logical address 5,300.
6. A system with 32-bit addresses uses 8 KB pages and 4-byte entries. Size of a single-level page table?
7. TLB lookup 10 ns, memory 80 ns, hit ratio 90 %. Find EAT.
8. Memory access 100 ns, page-fault service 10 ms, fault rate 1 in 10,000. Find EAT.
9. Reference string 1, 2, 3, 2, 4, 1, 5, 2, 1, 2, 3, 4 with 3 frames: count faults for FIFO, LRU and OPT.
10. Demonstrate Belady's anomaly for FIFO using 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 with 3 and 4 frames.
11. What is thrashing? How do the working-set and PFF methods control it?
12. Segment table (base, limit): 0 → (500, 200), 1 → (1500, 300). Translate ⟨1, 250⟩ and ⟨0, 250⟩.

Answers and worked solutions

1. The CPU generates logical (virtual) addresses; the memory hardware uses physical addresses. The MMU translates each logical address at run time (adding a base register, or via page/segment tables), and traps illegal ones.

2. Internal: unused space inside an allocated unit (last page). External: enough total free space but in non-adjacent holes. Paging causes only internal fragmentation (average half a page per process).

3. Partitions 1–5 = 150, 350, 100, 600, 250. First fit: 210 → partition 2 (140 left); 130 → partition 1 (20 left); 480 → partition 4 (120 left); 90 → partition 2 (50 left). Best fit: 210 → partition 5 (40 left); 130 → partition 1 (20 left); 480 → partition 4 (120 left); 90 → partition 3 (10 left). Worst fit: 210 → partition 4 (390 left); 130 → partition 4 (260 left); 480 cannot be placed (the largest hole is now 350); 90 → partition 2 (260 left). First fit and best fit place all four requests; worst fit fails on the 480 KB request.

4. 2 GB / 8 KB = 2³¹/2¹³ = 2¹⁸ = 262,144 units, so 262,144 bits = 32 KB.

5. Page = ⌊5,300 / 2,048⌋ = 2; offset = 5,300 − 4,096 = 1,204. Frame 8, so physical = 8 × 2,048 + 1,204 = 17,588.

6. Pages = 2³²/2¹³ = 2¹⁹ = 524,288; × 4 B = 2,097,152 B = 2 MB.

7. Hit = 10 + 80 = 90; miss = 10 + 80 + 80 = 170. EAT = 0.9 × 90 + 0.1 × 170 = 81 + 17 = 98 ns.

8. EAT = (1 − 0.0001) × 100 + 0.0001 × 10,000,000 = 99.99 + 1,000 = 1,099.99 ns ≈ 1,100 ns.

9. FIFO: 9 faults. LRU: 9 faults. OPT: 7 faults (counted and verified with bca/tools/check_os.py). Draw the frame table as in the 20-reference example and mark each fault.

10. FIFO with 3 frames: 9 faults; with 4 frames: 10 faults. More frames, more faults.

11. Thrashing: a process spends more time paging than executing because it lacks enough frames for its working set. Working set: keep pages used in the last Δ references and suspend processes if the sum exceeds memory. PFF: raise or lower a process's frames to keep its fault rate between limits.

12. ⟨1, 250⟩: 250 < 300, physical 1500 + 250 = 1750. ⟨0, 250⟩: 250 ≥ 200: trap (addressing error).

Model answers (5 and 10 marks)

Q1. Differentiate between paging and segmentation. (5 marks)

Paging divides logical memory into fixed-size pages and physical memory into frames of the same size. The OS keeps a page table for each process that maps a page number to a frame number.

The division is made by the hardware and is invisible to the programmer.

A logical address is a pair (page number p, offset d); the physical address is frame x page size + d. Paging removes external fragmentation, though the last page of a process wastes some space (internal fragmentation).

Segmentation divides the program into variable-size segments that match its logical units: main code, functions, stack, heap and data. A logical address is (segment number s, offset d).

The segment table holds a base and a limit for each segment; the address is valid only if d is less than the limit.

It matches the programmer's view and supports sharing and protection per segment, but variable sizes cause external fragmentation.

Point	Paging	Segmentation
Unit size	fixed	variable
Visible to programmer	no	yes
Table	page table (frame number)	segment table (base, limit)
Fragmentation	internal	external
Sharing and protection	per page, less natural	per segment, natural

Modern systems such as x86-64 Linux use paging, sometimes combined with segmentation.

Q2. Explain first fit, best fit and worst fit with an example. (5 marks)

When a process is loaded into variable-size partitions, the OS must choose a free hole. First fit scans the free list and takes the first hole that is large enough; it is fast.

Best fit searches the whole list and takes the smallest hole that is large enough; it leaves the smallest leftover but creates many tiny useless holes.

Worst fit takes the largest hole so that the leftover is big enough to be useful, but it quickly breaks up the large holes.

Example (Figure 5.1). Holes of 100, 500, 200, 300 and 600 KB receive requests of 212, 417, 112 and 426 KB in this order.

Algorithm	212	417	112	426
First fit	500	600	500 (288 left)	waits
Best fit	300	500	200	600
Worst fit	600	500	600 (388 left)	waits

Best fit places all four processes, while first fit and worst fit leave the last process waiting. Both leave external fragmentation: free space exists in total but not in one piece. It can be reduced by compaction, moving processes together, or removed by paging.

Q3. What is virtual memory? Explain demand paging and the effect of page faults. (10 marks)

Introduction. Virtual memory is a technique that lets a process run although only part of it is in physical memory. The programmer sees a large address space; the OS and hardware keep the active pages in RAM and the others in swap space on disk (Plate 5.1).

Demand paging. A page is brought into memory only when it is first used. Each page-table entry has a valid bit. If the bit is 1 the page is in memory. If it is 0, the access causes a page fault, a trap to the OS.

Steps of a page fault:

1. The CPU raises a trap and the OS checks that the address is legal; if not, the process is terminated.
2. The OS finds a free frame; if there is none, a page-replacement algorithm chooses a victim (written back to disk if its dirty bit is set).
3. The OS starts a disk read of the needed page into the frame.
4. When the read finishes, the page table is updated (frame number, valid bit = 1).
5. The faulting instruction is restarted and now succeeds.

Performance. With fault probability p, memory access time 200 ns and page-fault service time 8 ms, the effective access time is EAT = (1 - p) x 200 + p x 8,000,000 ns.

For p = 1/1000, EAT = 199.8 + 8000 = 8199.8 ns, about 41 times slower than 200 ns. To keep slowdown under 10 percent, p must be below about 1 in 400,000. A low fault rate therefore matters greatly.

Thrashing. If a process has too few frames, it faults continually, spending more time paging than computing, and CPU use collapses. The remedy is to give each process its working set of frames or to reduce the number of processes.

Item	Meaning
Valid bit	page in memory or not
Dirty bit	page modified, must be written back
Page fault	access to a page not in memory
Thrashing	excessive paging, low CPU use

Conclusion. Virtual memory gives large address spaces, protection and sharing, at the cost of page faults, which are kept rare by good replacement and enough frames.

Q4. Apply FIFO, LRU and optimal page replacement to the 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. Compare the number of page faults and explain Belady's anomaly. (10 marks)

Rules. FIFO replaces the page that has been in memory longest. LRU replaces the page not used for the longest time in the past.

OPT replaces the page that will not be used for the longest time in the future; it needs knowledge of the future, so it is used only as a benchmark. In the tables F means a page fault.

FIFO

Ref	7	0	1	2	0	3	0	4	2	3
F1	7	7	7	2	2	2	2	4	4	4
F2	-	0	0	0	0	3	3	3	2	2
F3	-	-	1	1	1	1	0	0	0	3
Fault	F	F	F	F	-	F	F	F	F	F

Ref	0	3	2	1	2	0	1	7	0	1
F1	0	0	0	0	0	0	0	7	7	7
F2	2	2	2	1	1	1	1	1	0	0
F3	3	3	3	3	2	2	2	2	2	1
Fault	F	-	-	F	F	-	-	F	F	F

LRU

Ref	7	0	1	2	0	3	0	4	2	3
F1	7	7	7	2	2	2	2	4	4	4
F2	-	0	0	0	0	0	0	0	0	3
F3	-	-	1	1	1	3	3	3	2	2
Fault	F	F	F	F	-	F	-	F	F	F

Ref	0	3	2	1	2	0	1	7	0	1
F1	0	0	0	1	1	1	1	1	1	1
F2	3	3	3	3	3	0	0	0	0	0
F3	2	2	2	2	2	2	2	7	7	7
Fault	F	-	-	F	-	F	-	F	-	-

OPT

Ref	7	0	1	2	0	3	0	4	2	3
F1	7	7	7	2	2	2	2	2	2	2
F2	-	0	0	0	0	0	0	4	4	4
F3	-	-	1	1	1	3	3	3	3	3
Fault	F	F	F	F	-	F	-	F	-	-

Ref	0	3	2	1	2	0	1	7	0	1
F1	2	2	2	2	2	2	2	7	7	7
F2	0	0	0	0	0	0	0	0	0	0
F3	3	3	3	1	1	1	1	1	1	1
Fault	F	-	-	F	-	-	-	F	-	-

Algorithm	Page faults (of 20)	Hit ratio
FIFO	15	25 percent
LRU	12	40 percent
OPT	9	55 percent

Belady's anomaly. One expects more frames to give fewer faults. With FIFO this is not always true. For the string 1 2 3 4 1 2 5 1 2 3 4 5, FIFO has 9 faults with 3 frames and 10 faults with 4 frames (Figure 5.4).

LRU and OPT are stack algorithms, which never show the anomaly.

Conclusion. OPT is best (9 faults), LRU is close (12) and FIFO is worst (15). Real systems use approximations of LRU, such as the reference-bit and clock algorithms.

Q5. A system has a page size of 4 KB. Explain address translation in paging and calculate the physical address of logical address 13000 if page 3 is in frame 7. Find the effective access time with a TLB. (5 marks)

Translation. The logical address is split into page number p = address / page size and offset d = address mod page size. The page table gives the frame number f for page p, and the physical address is f x page size + d.

Calculation. Page size = 4096 bytes. For 13000: p = 13000 / 4096 = 3 (integer part) and d = 13000 - 3 x 4096 = 13000 - 12288 = 712. Page 3 is in frame 7, so the physical address = 7 x 4096 + 712 = 28672 + 712 = 29384.

Effect of the TLB. Reading the page table in memory costs one extra access for every reference. The TLB keeps recent page-table entries in fast hardware. With a TLB search time of 20 ns, memory access of 100 ns and a hit ratio of 90 percent (Figure 5.2):

• hit: 20 + 100 = 120 ns;
• miss: 20 + 100 (page table) + 100 (data) = 220 ns;
• EAT = 0.9 x 120 + 0.1 x 220 = 108 + 22 = 130 ns.

Without a TLB every access takes 200 ns, so the TLB gives a saving of 35 percent.