Virtual Memory

Before we start

Why this matters

Chapter 10 · Lectures 11–12

Outline

Select a topic to jump to the slide that explains it.

1. Background
2. Virtual memory
3. Demand paging
4. Page replacement
5. Page and frame replacement algorithms
6. Counting algorithms

Background

Background

• Code needs to be in memory to execute, but entire program rarely used
  • Error code, unusual routines, large data structures
• Entire program code not needed at same time
• Consider ability to execute partially-loaded program
  • Program no longer constrained by limits of physical memory
  • Each program takes less memory while running → more programs run at the same time
    • Increased CPU utilization and throughput with no increase in response time or turnaround time
  • Less I/O needed to load or swap programs into memory → each user program runs faster

Virtual memory

Virtual memory

Demand paging

Demand paging

• Could bring entire process into memory at load time
• Or bring a page into memory only when it is needed
  • Less I/O needed, no unnecessary I/O
  • Less memory needed
  • Faster response
  • More users
• Similar to paging system with swapping (diagram on right)
• Page is needed → reference to it
  • invalid reference → abort
  • not-in-memory → bring to memory
• Lazy swapper – never swaps a page into memory unless page will be needed
  • Swapper that deals with pages is a pager

Demand paging

Demand paging (cont.)

Animated

Handling a page fault, step by step

Page replacement

What happens if there is no free frame?

• Used up by process pages
• Also in demand from the kernel, I/O buffers, etc
• How much to allocate to each?
• Page replacement – find some page in memory, but not really in use, page it out
  • Algorithm – terminate? swap out? replace the page?
  • Performance – want an algorithm which will result in minimum number of page faults
• Same page may be brought into memory several times

Page replacement

What happens if there is no free frame? (cont.)

Page replacement

Page replacement

• Prevent over-allocation of memory by modifying page-fault service routine to include page replacement
• Use modify (dirty) bit to reduce overhead of page transfers – only modified pages are written to disk
• Page replacement completes separation between logical memory and physical memory – large virtual memory can be provided on a smaller physical memory

Page replacement

Basic page replacement

1. Find the location of the desired page on disk
2. Find a free frame:
   • If there is a free frame, use it
   • If there is no free frame, use a page replacement algorithm to select a victim frame
   • Write victim frame to disk if dirty
3. Bring the desired page into the (newly) free frame; update the page and frame tables
4. Continue the process by restarting the instruction that caused the trap

Page replacement

Basic page replacement (cont.)

Page and frame replacement algorithms

Page and frame replacement algorithms

• Frame-allocation algorithm determines
  • How many frames to give each process
  • Which frames to replace
• Page-replacement algorithm
  • Want lowest page-fault rate on both first access and re-access
• Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
  • String is just page numbers, not full addresses
  • Repeated access to the same page does not cause a page fault
  • Results depend on number of frames available
• In all our examples, the reference string of referenced page numbers is

Page and frame replacement algorithms

Page and frame replacement algorithms (cont.)

FIFO

First-in-first-out (FIFO) algorithm

• Reference string: 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1
• 3 frames (3 pages can be in memory at a time per process)
• 15 page faults
• How to track ages of pages?
  • Just use a FIFO queue

FIFO

First-in-first-out (FIFO) algorithm (cont.)

FIFO illustrating Belady’s anomaly

Belady’s anomaly

• Can vary by reference string: consider 1,2,3,4,1,2,5,1,2,3,4,5
  • Adding more frames can cause more page faults!
  • Belady’s anomaly

FIFO illustrating Belady’s anomaly

Belady’s anomaly (cont.)

Optimal

Optimal algorithm

• Replace page that will not be used for longest period of time
  • 9 is optimal for the example
• How do you know this?
  • Can’t read the future
• Used for measuring how well your algorithm performs

Optimal

Optimal algorithm (cont.)

LRU

Least recently used (LRU) algorithm

• Use past knowledge rather than future
• Replace page that has not been used in the most amount of time
• Associate time of last use with each page
• 12 faults – better than FIFO but worse than OPT
• Generally good algorithm and frequently used
• But how to implement?

LRU

Least recently used (LRU) algorithm (cont.)

LRU

LRU algorithm (cont.)

• Counter implementation
  • Every page entry has a counter; every time page is referenced through this entry, copy the clock into the counter
  • When a page needs to be changed, look at the counters to find smallest value
    • Search through table needed
• Stack implementation
  • Keep a stack of page numbers in a double link form:
  • Page referenced:
    • move it to the top
    • requires 6 pointers to be changed
  • But each update more expensive
  • No search for replacement

LRU

LRU algorithm (cont.)

Code and output

Counting page faults in C

#include <stdio.h>

int ref[] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
int n = sizeof ref / sizeof ref[0];

int faults(int frames, int lru)
{
    int f[8], last[8], used = 0, next = 0, count = 0;
    for (int t = 0; t < n; t++) {
        int hit = -1;
        for (int i = 0; i < used; i++) if (f[i] == ref[t]) hit = i;

Code and output

Counting page faults in C (cont.)

        if (hit >= 0) { last[hit] = t; continue; }   /* page already in memory */
        count++;                                     /* page fault */
        int v;
        if (used < frames) v = used++;               /* a free frame */
        else if (!lru) { v = next; next = (next + 1) % frames; }   /* FIFO: oldest */
        else { v = 0; for (int i = 1; i < used; i++) if (last[i] < last[v]) v = i; } /* LRU */
        f[v] = ref[t]; last[v] = t;
    }
    return count;
}

int main(void)
{

Code and output

Counting page faults in C (cont.)

    printf("reference string of %d pages, 3 frames\n", n);
    printf("FIFO: %d page faults\n", faults(3, 0));
    printf("LRU : %d page faults\n", faults(3, 1));
    return 0;
}

$ gcc replace.c -o replace -pthread && ./replace
reference string of 20 pages, 3 frames
FIFO: 15 page faults
LRU : 12 page faults

The same 20-reference string as the slides: 15 faults for FIFO and 12 for LRU with 3 frames.

LRU approximation

LRU approximation algorithms

• LRU needs special hardware and still slow
• Reference bit
  • With each page associate a bit, initially = 0
  • When page is referenced bit set to 1
  • Replace any with reference bit = 0 (if one exists)
    • We do not know the order, however
• Second-chance algorithm
  • Generally FIFO, plus hardware-provided reference bit
  • Clock replacement
  • If page to be replaced has
    • Reference bit = 0 → replace it
    • reference bit = 1 then:
      • set reference bit 0, leave page in memory
      • replace next page, subject to same rules

LRU approximation

LRU approximation algorithms (cont.)

Interactive

Second chance on the example

LRU approximation

Enhanced second-chance algorithm

Improve algorithm by using reference bit and modify bit (if available) in concert. Take ordered pair (reference, modify):

• When page replacement called for, use the clock scheme but use the four classes; replace page in lowest non-empty class
  • Might need to search circular queue several times

Counting algorithms

Counting algorithms

Interactive · all algorithms

Page-replacement simulator

Worked example 1 of 2

Worked example 1

Worked example 2 of 2

Worked example 2

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

Check yourself

Quiz

Resources

Further learning

Free material to go deeper. Links open in a new tab.

Summary · End of Chapter 10

Summary

• Virtual memory lets a process run with only part of it in memory, so logical memory can exceed physical memory.
• Demand paging loads a page only on reference; a reference to a non-resident page causes a page fault.
• With no free frame, a victim page is chosen; the dirty bit avoids writing clean pages back.
• Algorithms are compared by counting faults on a reference string: FIFO 15, OPT 9, LRU 12 on the class example with 3 frames.
• FIFO can show Belady’s anomaly; LRU and OPT are stack algorithms and cannot.
• LRU is approximated with reference bits: second chance (clock), enhanced second chance with (reference, modify) classes; LFU and MFU count references.