Modern computers run programs whose total size is far bigger than the RAM fitted. Learn how paging and segmentation divide up memory, how a page table turns a logical address into a physical one, how virtual memory uses the disk as an extension of RAM, how pages are chosen for replacement, and why too much swapping causes disk thrashing.
In paging, a process is divided into fixed-size pages and RAM into page frames of the same size; a page table maps each page to a frame, so a process need not be stored contiguously. In segmentation, a process is divided into variable-size logical segments (e.g. code, data, stack) recorded in a segment table. Virtual memory uses secondary storage as if it were RAM: pages not currently needed are kept on disk and swapped in when used, causing a page fault. A page replacement algorithm chooses which page to swap out. If pages are swapped in and out so often that little useful processing is done, the system suffers disk thrashing.
Fig. 1: a page table maps each page of a process to a frame in RAM, or records that the page is on disk
Section 01
Paging and segmentation.
Both schemes let the OS place a process in memory in pieces, so memory can be shared efficiently between many processes.
Paging
Segmentation
Division
physical division into fixed-size pages (e.g. 4 KiB)
logical division into variable-size segments that match the program's structure (a procedure, an array, the stack)
Memory side
RAM divided into frames the same size as a page
each segment is placed in a block of RAM of exactly its size
Table
page table: page number → frame number
segment table: segment number → base address and length (limit)
Address
page number + offset
segment number + offset (checked against the segment length)
Wasted space
internal fragmentation: the last page of a process is usually partly empty
external fragmentation: gaps of free memory between segments that may be too small to use
Visible to the programmer?
no: pages are invisible, set by the OS and hardware
yes: segments correspond to logical parts of the program
Worked example Logical to physical address
Pages are 4096 bytes. A process uses logical address 9300. Using the page table in Fig. 1 (page 2 is in frame 5), find the physical address.
Page number = 9300 DIV 4096 = 2 (because 2 × 4096 = 8192 and 3 × 4096 = 12288 is too big).
Offset = 9300 MOD 4096 = 9300 − 8192 = 1108.
Look up page 2 in the page table: it is in frame 5.
Answer: Physical address 21588. The offset is unchanged; only the page number is replaced by the frame number.
Examiner trap
Do not say segments and pages are both fixed size. Pages are fixed size and a physical division; segments are variable size and a logical division.
Section 02
Virtual memory and thrashing.
A process rarely needs all its pages at once. Virtual memory keeps only the pages in use in RAM and the rest on secondary storage.
How it works: each process has a large virtual (logical) address space. The page table records, for each page, whether it is in RAM (and which frame) or on disk.
Page fault: when a process uses a page that is not in RAM, an interrupt passes control to the OS, which loads the page from disk into a free frame (or swaps out another page first), updates the page table and restarts the instruction.
Benefits: programs larger than physical RAM can run; more processes can be held at once, improving multi-tasking; RAM is used only for pages actually in use.
Drawbacks: disk access is thousands of times slower than RAM, so each page fault costs time; disk space is needed for the swap area.
Disk thrashing: if there are too many processes, or a process keeps using more pages than fit in its frames, a page is swapped out and then needed again almost at once. The OS spends more time moving pages between RAM and disk than executing processes, the disk is constantly busy, and performance collapses (with a magnetic disk the heads also wear).
Reducing thrashing: add more RAM, run fewer processes, or use a better page replacement algorithm.
Examiner trap
Thrashing is not just "using virtual memory". It is when swapping becomes so frequent that the processor spends most of its time waiting for pages, so little useful work is done.
Stage 1 · Learn
Check what the sim just showed you
Four quick checks. Each correct answer earns XP and records this skill on your profile.
Quick check+10 XP
What is a page frame?
Quick check+10 XP
Which is true of segmentation but not paging?
Quick check+10 XP
What happens on a page fault?
Quick check+10 XP
Which page does LRU replace?
Section 03
Which page goes out?
When a page fault happens and every frame is full, the OS must choose a victim page to swap out. Common algorithms: first in first out (FIFO) replaces the page that has been in RAM longest; least recently used (LRU) replaces the page that has not been used for the longest time; least frequently used (LFU) replaces the page used the fewest times. The ideal (optimal) choice is the page that will not be needed for the longest time, but that needs knowledge of the future. A page that has been changed (a dirty page) must be written back to disk before its frame is reused.
Requests 1, 2, 3, 1, 4, 1, 5, 2, 1, 4 with three frames. FIFO (F = page fault):
Request
1
2
3
1
4
1
5
2
1
4
Frame 1
1
1
1
1
4
4
4
2
2
2
Frame 2
2
2
2
2
1
1
1
1
4
Frame 3
3
3
3
3
5
5
5
5
Fault?
F
F
F
F
F
F
F
F
The same requests with LRU:
Request
1
2
3
1
4
1
5
2
1
4
Frame 1
1
1
1
1
1
1
1
1
1
1
Frame 2
2
2
2
4
4
4
2
2
2
Frame 3
3
3
3
3
5
5
5
4
Fault?
F
F
F
F
F
F
F
Worked example Why LRU wins here
Explain each replacement in the two traces above and compare the number of page faults.
The first three requests fill the empty frames: 3 faults for both algorithms. Request 4 (1) is a hit.
FIFO, request 4: page 1 was loaded first, so 1 is replaced by 4, even though 1 was just used. The next request is 1, so it faults again and replaces 2 (now the oldest).
FIFO continues: 5 replaces 3, 2 replaces 4, 1 is a hit, 4 replaces 1 (loaded at request 6, now the oldest). Total: 8 faults.
LRU, request 4: the least recently used page is 2 (used at request 2), so 4 replaces 2 and page 1 stays. Request 6 (1) is a hit.
LRU continues: 5 replaces 3, 2 replaces 4, 1 is a hit, 4 replaces 5 (least recently used of 1, 2, 5). Total: 7 faults.
Answer: FIFO 8 page faults, LRU 7. LRU keeps the heavily used page 1 in memory; FIFO throws it out just because it arrived first.
Your turn
Give one drawback of LRU compared with FIFO.
LRU needs extra overhead: the OS must record when each page was last used (a time stamp or counter updated on every access) and search for the oldest, whereas FIFO only needs a queue of load order.
Stage 2 · Exam
Exam-style questions
Unlocks once the four checks above are done. Worth more XP, written to A Level Paper 3 and Paper 4 standard.
Finish the four checks above to unlock the exam questions
Exam style+20 XP
Pages are 1024 bytes. Which page and offset hold logical address 3100?
Exam style+20 XP
Which best describes disk thrashing?
Exam style+20 XP
Which change is most likely to reduce disk thrashing?
Exam style+20 XP
Why can virtual memory let a 6 GiB program run on a computer with 4 GiB of RAM?
Skill unlocked
Paging, segmentation and virtual memory, mapped.
This skill is now recorded on your profile. Keep the chain going.