Understanding Virtual Memory and Page Replacement Algorithms
Associative Memory in TLB Implementation
How can the associative memory device needed for a Translation Lookaside Buffer (TLB) be implemented in hardware, and what are the implications of such a design for expandability?
An associative memory essentially compares a key to the contents of multiple registers simultaneously. For each register, there must be a set of comparators that compare each bit in the register contents to the key being searched for. The number of gates (or transistors) needed to implement such a device is a linear function of the number of registers, so expanding the design gets expensive linearly.
Page Table Entries Calculation
A machine has 48-bit virtual addresses and 32-bit physical addresses. Pages are 8 KB. How many entries are needed for the page table?
With 8-KB pages and a 48-bit virtual address space, the number of virtual pages is 248 / 213, which is 235 (about 34 billion).
Page Replacement Algorithms and Repetitive Reference Streams
Suppose that the virtual page reference stream contains repetitions of long sequences of page references followed occasionally by a random page reference. For example, the sequence: 0, 1, … ,511, 431, 0, 1, … , 511, 332, 0, 1, … consists of repetitions of the sequence 0, 1, … , 511 followed by a random reference to pages 431 and 332.
Ineffectiveness of Standard Algorithms
(a) Why won’t the standard replacement algorithms (Least Recently Used (LRU), First-In, First-Out (FIFO), Clock) be effective in handling this workload for a page allocation that is less than the sequence length?
Alternative Page Replacement Approach
(b) If this program were allocated 500 page frames, describe a page replacement approach that would perform much better than the LRU, FIFO, or Clock algorithms.
Answers
(a) Every reference will page fault unless the number of page frames is 512, the length of the entire sequence.
(b) If there are 500 frames, map pages 0–498 to fixed frames and vary only one frame.
Page Faults with FIFO and LRU
If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string “0 1 7 2 3 2 7 1 0 3”, if the four frames are initially empty? Now repeat this problem for LRU.
FIFO yields six page faults; LRU yields seven. [Note: You will need to show in detail ‘how’ as demonstrated in class]
Second Chance Page Removal
Consider the page sequence of Fig. Suppose that the R bits for the pages B through A are 11011011, respectively. Which page will second chance remove?
The first page with a 0 bit will be chosen, in this case D.
WSClock Algorithm and Page Removal
In the WSClock algorithm of Fig, the hand points to a page with R = 0. If τ = 400, will this page be removed? What about if τ = 1000?
The age of the page is (2204-1213) = 991. If τ = 400, it is definitely out of the working set and was not recently referenced so it will be evicted. The τ = 1000 situation is different. Now the page falls within the working set (barely), so it is not removed.
Program Loading Time from Disk
How long does it take to load a 64-KB program from a disk whose average seek time is 10 msec, whose average rotation time is 10 msec, and whose tracks hold 32 KB?
- (a) for a 2-KB page size?
- (b) for a 4-KB page size?
The seek plus rotational latency is 20 msec. For 2-KB pages, the transfer time is 1.25 msec, for a total of 21.25 msec. Loading 32 of these pages will take 680 msec. For 4-KB pages, the transfer time is doubled to 2.5 msec, so the total time per page is 22.50 msec. Loading 16 of these pages takes 360 msec. (The transfer time for a 2KB page is 1.25 msec. How? It is calculated as: we see, it can transfer a track of 32KB data in 20 msec => thus can transfer 2KB in => 2 x (20/32) = 1.25 msec. And, 4KB => 4 x (20/32) => 2.5msec. )