Virtual memory — exam-style exercises with page faults, FIFO, LRU and optimal traces and working sets (and the three faults I did not count in the mock exam)

Answer: Running a process even if only part of its pages are in main memory

With virtual memory the logical space of a process can be larger than the RAM it has: secondary storage acts as an extension of main memory and the OS moves pages between the two without the program noticing.

• T — A process can have some pages in RAM and others on disk at the same time.
• F — To start running, a process has to be fully loaded into RAM.
• T — Main memory is shared among the processes that are running.
• F — The OS always tries to give each process all the free RAM there is.
• F — It is the programmer who marks in the code which pages stay on disk.

Virtual memory exists precisely so that the process does not have to be whole in RAM. The OS shares the frames among all processes (it does not give all the RAM to one) and decides itself which pages are in and which are out; the programmer does not deal with that.

Answer: When the process references it and it is not in RAM (page fault)

On demand = a page is not loaded until it is needed. The first reference to each page causes a page fault and that is when the OS brings it from disk. In the gcc string in the article, pages 0 and 6 are never read.

Answer: Valid bit

The valid bit (v/i, or present bit): with v (1) the page is in a frame; with i (0) it is on disk and accessing it causes a page fault.

Correct order:

1. The MMU sees bit i in the page table and raises a trap
2. The OS checks the reference is valid and locates the page on disk
3. The OS takes a free frame
4. The page is read from disk into that frame
5. The entry is updated: frame number and valid bit set to v
6. The instruction that caused the fault is restarted

First the trap fires (the MMU cannot translate), the OS finds the page, puts it into a free frame, records the frame with v = 1 and runs the instruction again, which now does find the page. If there were no free frame, a victim would have to be chosen before reading.

Correct order:

1. The page fault happens
2. The OS sees there is no free frame left
3. The replacement algorithm chooses a victim page
4. If the victim has M = 1, it is written to disk
5. The victim is marked as invalid in its page table
6. The new page is read into the frame that has become free
7. The new page’s entry is updated and the instruction is restarted

The difference from the previous case is in the middle: choose a victim, save it if it is dirty and mark it as i (so its owner faults if it asks for it again). After that it goes on as before: read, update and restart.

Answer: The modified bit (M)

The hardware sets M = 1 as soon as the page is written (a “dirty page”). A clean victim (M = 0) can simply be overwritten because the disk already has the same copy; a dirty one costs one more write.

Answer: Precleaning

Precleaning: it uses idle moments so that, when a victim is needed, it is more likely to be clean and the fault costs a single disk access.

Answer: LRU · Second chance · NFU · Optimal (OPT)

Page replacement: FIFO, optimal, LRU and its approximations (second chance or clock, NRU, NFU, LFU, aging, WSClock). Be careful not to mix them up with CPU ones (FCFS, SJF, SRTF, RR) or with the fits of Topic 9.

• FIFO → The one that has been loaded in memory the longest
• Optimal → The one that will be used again the latest
• LRU → The one that has gone unused the longest
• LFU → The one with the lowest use counter

FIFO looks at arrival, LRU at last use, the optimal at next use and LFU at how many times it has been used (it evicts the least used, not the most).

Answer: It needs to know which pages will be asked for in the future

The optimal evicts the page that will be referenced again the latest, and that requires knowing the future reference string. It is used as a benchmark to measure how close a real algorithm gets.

• T — It means that, with more frames, an algorithm can give more page faults.
• T — FIFO can suffer it.
• F — LRU can suffer it if the string is long enough.
• F — The optimal algorithm suffers it with 4 frames or more.

The anomaly appears in FIFO. LRU and the optimal are stack algorithms: what they have in memory with n frames is always contained in what they would have with n + 1, so one more frame never makes things worse. In the article, FIFO goes from 9 to 10 faults when going from 3 to 4 frames.

Answer: To record on every access when each page was used (counter or stack), and that is very expensive

Exact LRU needs, on every access, to store an instant (counter) or move the page to the top of a stack. Doing it in software would be extremely slow and in hardware it is expensive: that is why approximations with the R bit are used.

Answer: R is set to 0 and the hand moves to the next one

It is FIFO with one extra question: “have you been used since last time?”. If R = 1, it is forgiven (R becomes 0) and the hand moves on; the victim is the first page it finds with R = 0.

Answer: R = 0 and M = 0

NRU groups pages into four classes by (R, M) and picks at random within the lowest non-empty class: 0 (0, 0), 1 (0, 1), 2 (1, 0), 3 (1, 1).

• NFU → A counter that adds the R bit at regular intervals
• Aging → A register that shifts and receives the R bit from the left
• LFU → A counter of the number of references
• Clock → Only the R bit and a hand that goes round the frames

NFU adds R to a counter every tick (it never forgets). Aging shifts the register to the right and puts R in from the left, so recent use weighs more. LFU counts references. The clock only needs R. Storing the exact time of each access would be exact LRU, not an approximation.

Answer: C

The leftmost bit is the latest tick, so the register is read as a number: A = 6, B = 9, C = 3. The one with the lowest value is evicted: C.

Answer: The reference bit · The instant of last use (U) · The time window Δ

WSClock combines the clock (circular list and R bit) with the working set: for each page it stores when it was last used (U) and compares it with the window Δ.

Answer: Locality

Locality (of reference). Thanks to it virtual memory works: at any moment a process only needs a few pages. Careful, it is not “segmentation”.

A process goes through different localities while it runs. If the current one is entirely in RAM, it will hardly have any page faults. The pages of its current locality form its working set.

The working set is the way to measure the current locality: the distinct pages referenced in the last window Δ.

Answer: No: 50 − 41 = 9 and 9 > 8

A page is in the WS if clock − U ≤ Δ. Here 50 − 41 = 9 > 8, so it has fallen outside the window.

Thrashing appears when there are chained page faults because there are not enough frames for all the processes; the system crawls because it spends its time paging.

Each process evicts pages that another (or itself) needs right away; the CPU is left waiting for the disk and its use plummets.

Answer: Suspend some process and share out its frames

With D > m thrashing is guaranteed. The way out is to lower the degree of multiprogramming (the medium-term scheduler suspends processes) until D fits.

Answer: Frames are taken away from it

PFF sets a band: above the upper limit it is given frames; below the lower one, they are taken away. If there are no frames to give, some process is suspended.

Answer: Linked structures (lists, trees) spread across memory · Interpreted languages with run-time type checking · Very large functions

Whatever breaks locality makes faults soar: jumping between linked nodes, the extra code of an interpreter or huge functions that take many pages. Contiguous data and things walked in order help.

Answer: 5

The compulsory faults (first reference to each page) cannot be avoided by anyone: here 1, 2, 3, 4 and 5 are 5 distinct pages. No algorithm, not even the optimal, goes below that.

Answer: 8

You look ahead: 6 comes back at position 1, 4 at position 2 and 8 at position 4. The victim is the one that comes back the latest: 8.

Answer: 6

LRU looks for the oldest last use: 7 < 10 < 12, so page 6 leaves.

• T — Reading a page from disk is thousands of times slower than a RAM access.
• T — With a dirty victim, serving the fault costs two disk operations.
• F — A 1 % page fault rate is barely noticeable in the effective access time.
• T — For virtual memory to go unnoticed, the fault rate has to be tiny.

With 100 ns per access and 8 ms per fault, one fault every 1,000 accesses (0.1 %) already makes memory 81 times slower; 1 % would be a disaster. That is why p has to be in the order of one per million.

Answer: Swap area

The swap area: a partition or a file on disk that the OS uses as backing for virtual memory.

Answer: That it faults a lot: its locality does not fit

If |WS| > frames given, the process cannot keep its locality inside and faults non-stop: it is the seed of thrashing. The sensible thing would be to give it at least 5 frames (or suspend it).

Trace (F = fault, · = hit, the victim in brackets):

FIFO: 0F 3F 0· 1F 4F(0) 0F(3) 3F(1) 2F(4) 0· 4F(0) 1F(3) 3F(2)

LRU: 0F 3F 0· 1F 4F(3) 0· 3F(1) 2F(4) 0· 4F(3) 1F(2) 3F(0)

Optimal: 0F 3F 0· 1F 4F(1) 0· 3· 2F(3) 0· 4· 1F(0) 3F(1)

The first replacement comes at t = 4 (page 4) with 0, 3 and 1 in memory. FIFO evicts 0 because it came in first, even though it has just been used at t = 2; LRU evicts 3, the one unused for the longest (t = 1); the optimal evicts 1, which does not come back until t = 10 (0 comes back at t = 5 and 3 at t = 6). All three have the 5 compulsory faults (pages 0, 1, 2, 3 and 4).

Fault (F) and hit (·) marks:

3 frames: F F F F F F F . . F F . → 9 faults

4 frames: F F F F . . F F F F F F → 10 faults

One more frame gives one more fault: that is Belady’s anomaly. With 4 frames, FIFO still has 2 and 6 inside at t = 6 and evicts 2 when 0 arrives, just before 2 is asked for again; with 3 frames that order of departures changes and it hits 2 and 6 at t = 7 and t = 8.

EAT = (1 − p) · 100 + p · service, all in ns (5 ms = 5,000,000 ns).

Case 1: 0.999 · 100 + 0.001 · 5,000,000 = 99.9 + 5,000 = 5,099.9 ns.

Case 2: if half of the victims are dirty, the average service is (5 + 10) / 2 = 7.5 ms: 99.9 + 7,500 = 7,599.9 ns.

Case 3: 0.999999 · 100 + 0.000001 · 5,000,000 = 99.9999 + 5 ≈ 105 ns.

Case 4: 100 + p · (5,000,000 − 100) ≤ 110 → p ≤ 10 / 4,999,900, that is, at most one fault every 499,990 accesses.

The working set is the distinct pages of the last 3 references:

WS(t = 2) = {2, 5} → |WS| = 2; D = 2 + 6 = 8 ≤ 8

WS(t = 4) = {2, 5, 7} → |WS| = 3; D = 3 + 6 = 9 > 8

WS(t = 7) = {1, 3, 5} → |WS| = 3; D = 3 + 6 = 9 > 8

WS(t = 11) = {1, 3, 5} → |WS| = 3; D = 3 + 6 = 9 > 8

At t = 2 page 5 repeats in the window (5, 2, 5) and only counts once: they fit. At the other instants D = 9 > 8: not everyone fits and there is thrashing.

A page is in the WS if clock − U ≤ Δ:

A: 60 − 55 = 5 ≤ 10 → inside

B: 60 − 49 = 11 > 10 → outside

C: 60 − 50 = 10 ≤ 10 → inside

D: 60 − 38 = 22 > 10 → outside

E: 60 − 60 = 0 ≤ 10 → inside

C is right on the edge (10 ≤ 10) and does count. B and D are the victim candidates in WSClock.

Model answer:

Virtual memory is the technique that lets a process run even though it is not entirely in main memory: secondary storage (the swap area on disk) acts as an extension of RAM and the OS moves pages between the two transparently to the programmer. That way the logical space of a process can be larger than physical RAM and more processes fit in memory at once.

Demand paging is the usual way to achieve it: a page is not read from disk until the process references it. The page table has a valid bit; if it is i, the MMU raises a trap (page fault) and the OS brings the page in at that moment. Pages that are never used are never loaded.

What is gained: a higher degree of multiprogramming, faster start-up and programs bigger than RAM. The price: each page fault costs milliseconds (thousands of times more than a RAM access), so the fault rate has to be very low, and a replacement algorithm is needed when there are no free frames left.

The key is to separate the two ideas: virtual memory is the goal (not having to fit whole) and demand paging is the mechanism (loading on first use).

Model answer:

1) The process references a page whose entry has the valid bit set to i; the MMU cannot translate and raises a trap to the kernel. 2) The OS checks that the address is legal and locates the page in the swap area. 3) As there are no free frames, the replacement algorithm chooses a victim. 4) If the victim has the modified bit set to 1, it is written to disk; if it is 0, the copy on disk is still valid and nothing is written. 5) The victim is marked as invalid in its owner’s page table. 6) The new page is read into the freed frame. 7) Its entry is updated (frame number and valid bit set to v) and the instruction that faulted is restarted.

The valid bit says whether the page is in RAM (it is the one that causes the fault). The reference bit is set to 1 by the hardware on every access and is used by the LRU approximations (clock, NRU, aging) to know what has been used recently. The modified bit says whether the page was written: a dirty victim costs two disk operations and a clean one, one, which is why algorithms prefer clean ones and the OS does precleaning.

Order matters: the victim is saved (if dirty) before the new page is read into its frame, and the instruction is restarted at the end, not continued.

Model answer:

FIFO evicts the page that has been in memory the longest: it is easy (a queue) but it ignores use, so it can evict a heavily used page. The optimal evicts the one that will be referenced again the latest: it gives the minimum possible number of faults, but it needs to know the future and only serves as a benchmark. LRU evicts the one that has gone unused the longest: it relies on locality (the recent past predicts the near future) and gets close to the optimal, but implementing it exactly requires recording something on every access (counters or a stack).

Belady’s anomaly is that giving a process more frames increases the number of faults. It happens to FIFO; LRU and the optimal are stack algorithms (what is there with n frames is contained in what would be there with n + 1) and do not suffer it.

The clock (second chance) is FIFO plus the reference bit. The frames form a circular list and a hand goes round them:

while true: if R[hand] == 1 then R[hand] = 0 and hand = next; otherwise victim = hand, hand = next and stop

A page used since the last pass escapes once; if it is still unused, it goes on the next round. That way it resembles LRU using a single bit per page.

A numerical example helps a lot: with gcc’s string from the article and 3 frames, FIFO gives 11 faults, LRU 9 and the optimal 7.

Model answer:

Locality is the tendency of a process to concentrate its accesses, for a while, on a few pages of code and data (a loop, a function, a data structure). The working set WS(t, Δ) is the set of distinct pages referenced in the last Δ references: a way of measuring the current locality. With a last-use field U, a page is in the WS if clock − U ≤ Δ.

Thrashing happens when processes do not have enough frames for their working set: each fault evicts a page that will be needed right away, faults chain together, everyone waits for the disk and CPU use collapses. It usually appears when the degree of multiprogramming rises too much: if the sum of the |WS| of all processes (D) exceeds the available frames, thrashing is certain.

To avoid it, the OS can use the working set model (give each process at least |WS| frames and suspend processes if D does not fit) or the page fault frequency (PFF): if a process’s fault rate goes above an upper limit it is given frames, if it drops below a lower limit some are taken away and, if there are no frames to give, some process is suspended.

The key is the chain: locality → working set → if it does not fit, thrashing. With that, the solutions follow on their own.