The shape of the lesson
By the end of the lesson, learners can
- Paging and segmentation: Both schemes let the OS place a process in memory in pieces, so memory can be shared efficiently between many processes.
- Virtual memory and thrashing: A process rarely needs all its pages at once.
- Which page goes out?: When a page fault happens and every frame is full, the OS must choose a victim page to swap out.
- Paging: fixed-size pages into frames; page table; page number + offset.
- Segmentation: variable-size logical segments; segment table with base and length.
- Virtual memory: disk used as RAM; page fault loads a page; thrashing when swapping dominates.
- Replacement: FIFO = oldest loaded; LRU = longest since last use. Trace frame by frame and count faults.
One picture every idea returns to
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.
Forty-five minutes, phase by phase
| Time | Phase | What happens in the room | Grouping |
|---|---|---|---|
| 0 to 5 min | Hook: predict | Open with the question in the title, More memory than you have.. Modern computers run programs whose total size is far bigger than the RAM fitted. Put the figure on the board: it is the one picture every idea in the lesson returns to. | Whole class, then pairs |
| 5 to 13 min | Teach and check: Paging and segmentation | Both schemes let the OS place a process in memory in pieces, so memory can be shared efficiently between many processes. Model the worked example Logical to physical address on the board, one line at a time. | Whole class, then pairs |
| 13 to 21 min | Teach and check: Virtual memory and thrashing | A process rarely needs all its pages at once. | Pairs |
| 21 to 30 min | Teach and check: Which page goes out? | When a page fault happens and every frame is full, the OS must choose a victim page to swap out. Model the worked example Why LRU wins here on the board, one line at a time. Your turn: Give one drawback of LRU compared with FIFO. | Rally Coach |
| 30 to 36 min | Check | The four Stage 1 questions from the student lesson, answered on mini whiteboards or by show of fingers. Re-teach the one most get wrong. | Individual, then whole class |
| 36 to 43 min | Plenary | The exam-style questions from Stage 2, one at a time: thirty seconds alone, then a random call. The feedback lines in the key give the examiner's wording. | Individual, random call |
| 43 to 45 min | Exit and homework | Set the worksheet below (6 questions, 21 marks). Learners self-assess against the objectives before they leave. | Individual |
Protect the parts that carry the learning
The sequence carries about fifty minutes of material, so the lab is driven by one student while the class predicts rather than explored freely. Times are a guide.
Protected: the check at 30 minutes. It is the only individual read on whether the key idea landed, and it is not cut.
Cut first if the build overruns: the last check in Which page goes out?, never the check or the plenary.
In a 60 minute block: run worksheet questions 1 to 3 in class as a Rally Coach set and model both the hardest worked example and its check live.
Rally Coach
Pairs share one worksheet. One partner solves the first question aloud while the other coaches, checking each line and offering a prompt rather than the answer; they swap roles for the next question.
The full structure, with its variations and the other twelve, is on the cooperative-learning page.
What to head off, and how
| Trap learners fall into | Teaching move that pre-empts it |
|---|---|
| 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. |
| 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. |
Paging, segmentation and virtual memory: worksheet
6 questions, 21 marks. Written in the style of the papers; no past paper question is reproduced.
Explain the differences between paging and segmentation.
A computer uses pages of 4096 bytes. Page 3 of a process is stored in frame 6. Calculate the physical address of logical address 13000, showing your working.
A process has three page frames, initially empty. It requests pages in this order: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3. Using FIFO page replacement, show the contents of the frames after each request and state the number of page faults.
Repeat the trace in the previous question using least recently used (LRU) replacement and state the number of page faults.
Explain how disk thrashing can occur in a system that uses virtual memory, and its effect.
Discuss whether FIFO or LRU is the better page replacement algorithm.
Answer key and marking notes
- Pages are a fixed size; segments are variable sizes.
- Paging is a physical division of memory; segmentation is a logical division that matches the structure of the program (e.g. procedures, data).
- A page address is a page number and offset mapped through a page table to a frame; a segment address is a segment number and offset, using a segment table holding a base address and length.
- Paging can cause internal fragmentation (part-empty last page); segmentation can cause external fragmentation (gaps between segments).
- Page number = 13000 DIV 4096 = 3.
- Offset = 13000 MOD 4096 = 13000 − 12288 = 712.
- Physical address = 6 × 4096 + 712 = 24576 + 712 = 25288.
- 7, 0, 1 fill the frames (3 faults); 2 replaces 7 (oldest); 0 is a hit.
- 3 replaces 0; 0 replaces 1; 4 replaces 2.
- 2 replaces 3; 3 replaces 0. Final frames: 4, 2, 3.
- Total: 9 page faults (only the request for 0 at position 5 is a hit).
- 7, 0, 1 fill the frames; 2 replaces 7; 0 is a hit; 3 replaces 1 (least recently used of 2, 0, 1).
- 0 is a hit; 4 replaces 2; 2 replaces 3; 3 replaces 0. Final frames: 4, 3, 2 (frame 1 holds 4, frame 2 holds 3, frame 3 holds 2).
- Total: 8 page faults (two hits, both for page 0).
- Too many processes, or processes needing more pages than they have frames, so RAM is over-committed.
- A page is swapped out to disk and then needed again almost immediately, causing another page fault.
- Pages are continually swapped between RAM and disk.
- The processor spends most of its time waiting for page transfers, so very little useful processing is done and performance drops sharply.
- FIFO is simple: it only needs a queue of the order pages were loaded.
- But FIFO may remove a page that is heavily used just because it was loaded early, causing extra page faults.
- LRU usually gives fewer page faults because recently used pages are likely to be used again, but it has more overhead, as the time of every access must be recorded and searched.
6 multiple-choice questions on this lesson
From the topic question bank. Assign them in the app for a marked score in your gradebook, or run the topic as a class game.
Which statement correctly compares paging and segmentation?
- APages are a fixed-size physical division; segments are variable-size logical divisions of the program
- BPages are variable-size logical divisions; segments are a fixed-size physical division of memory
- CPages and segments are both fixed in size, but segments are stored on disk and pages in RAM
- DPaging divides a program by its procedures, while segmentation divides RAM into equal frames
Pages are 2048 bytes. Page 2 of a process is held in frame 7. What is the physical address of logical address 5000?
- A15240
- B14336
- C19336
- D17288
A process has three page frames, initially empty. It requests pages 4, 7, 4, 1, 7, 3, 4, 7, 1, 3. How many page faults occur with first in first out (FIFO) replacement?
- A8
- B7
- C5
- D10
Which situation is disk thrashing?
- APages are swapped out and needed again almost at once, so the processor spends most of its time waiting for page transfers
- BA program larger than RAM runs because only the pages it is using are kept in memory
- CA page fault occurs the first time each page of a newly loaded program is used
- DThe page table is kept on disk instead of in RAM, so every address must be read from the disk
The same process (three frames, initially empty) requests pages 4, 7, 4, 1, 7, 3, 4, 7, 1, 3. How many page faults occur with least recently used (LRU) replacement?
- A7
- B8
- C5
- D6
A process uses segmentation with this segment table. Which logical address (segment, offset) would be rejected as invalid?
| Segment | Base address | Length (bytes) |
|---|---|---|
| 0 | 2000 | 800 |
| 1 | 5200 | 1200 |
| 2 | 7000 | 1500 |
- A(1, 1300)
- B(2, 1200)
- C(0, 799)
- D(1, 0)
Quiz key
Paging cuts a process into equal pages that fit equal frames in RAM, ignoring what the code does; segmentation splits it into logical parts such as a procedure, the data or the stack, so segment sizes vary. The second option swaps the two definitions. Segments are not fixed size and both pages and segments can be in RAM or swapped out. Dividing by procedures is segmentation, and equal frames belong to paging.
Page = 5000 DIV 2048 = 2 and offset = 5000 MOD 2048 = 5000 − 4096 = 904. Physical address = 7 × 2048 + 904 = 14336 + 904 = 15240. 14336 is only the start of frame 7, with the offset forgotten. 19336 adds the whole logical address to the frame start instead of just the offset. 17288 uses 5000 − 2048 = 2952 as the offset, subtracting only one page instead of two.
4, 7, then 4 is a hit, 1 fills the third frame (3 faults); 7 is a hit; 3 replaces 4 (oldest); 4 replaces 7; 7 replaces 1; 1 replaces 3; 3 replaces 4. Faults: 3 + 5 = 8, with only two hits. 7 is the LRU result for the same requests, 5 is the optimal (look-ahead) result, and 10 counts every request as a fault, ignoring the hits.
Thrashing is excessive swapping: RAM is over-committed, so a page is swapped out and then needed again almost immediately, and little useful processing happens. Running a program bigger than RAM is the normal benefit of virtual memory. A few page faults as a program starts are expected and are not thrashing. Thrashing is not about where the page table is stored.
4, 7, 1 fill the frames (3 faults; 4 and 7 are hits). 3 replaces 4 (last used at request 3); 4 replaces 1 (last used at request 4, while 7 was used at 5 and 3 at 6); 7 is a hit; 1 replaces 3; 3 replaces 4. Faults: 3 + 4 = 7. 8 is the FIFO count, which replaces 7 instead of 1 at request 7 and so faults again on the next request. 5 is the optimal algorithm, which needs to know future requests. 6 misses one of the replacements.
Segment 1 is only 1200 bytes long, so an offset of 1300 lies outside it and the address is rejected (it would otherwise reach into memory that belongs to something else). (2, 1200) is inside a 1500-byte segment and maps to 7000 + 1200 = 8200. (0, 799) is the last byte of segment 0, at 2799. (1, 0) is the first byte of segment 1, at 5200.
Slides for this lesson
A projectable deck for every pack is on the way. Until then, present the student lesson full screen: its sections, figure and lab tabs follow the same order as the plan above.