[OS Concepts] 10. Virtual Memory: From Demand Paging to Thrashing

Virtual Memory Concepts

Virtual memory is a technology that allows a process to execute even when it is not entirely loaded in physical memory. It provides programmers with an address space much larger than actual physical memory.

[How Virtual Memory Works]

Virtual Address Space (Process view):      Physical Memory:
+-----------+ 0xFFFF...                   +-----------+
|   Stack    |                             |   OS      |
|    |      |                             +-----------+
|    v      |                             | Page A    | <-- Virtual page 0
|           |                             +-----------+
|           |                             | Page C    | <-- Virtual page 5
|    ^      |                             +-----------+
|    |      |                             | Page D    | <-- Virtual page 2
|   Heap    |                             +-----------+
+-----------+                             | Free      |
|  Data     |                             +-----------+
+-----------+
|  Code     |                             Disk (Swap area):
+-----------+ 0x0000...                   +-----------+
                                          | Page B    | <-- Virtual page 1
Only part of 4GB virtual space            | Page E    | <-- Virtual page 3
is in physical memory                     +-----------+

The advantages of virtual memory are as follows.

Programs can be larger than physical memory
Each process's address space is isolated
Multiple processes can share pages (shared libraries, COW during fork)
Process creation is efficient

Demand Paging

Instead of loading all pages into memory when a program starts, pages are loaded only when actually needed (on demand).

[Demand Paging Concept]

Page Table:
+-------+------+
| Frame | Valid |
+-------+------+
|   3   |  v   |  <- In memory
|   -   |  i   |  <- On disk (not yet loaded)
|   7   |  v   |  <- In memory
|   -   |  i   |  <- On disk
+-------+------+

v = valid (in memory)
i = invalid (not in memory, on disk)

Page Fault

A page fault occurs when an invalid page is accessed.

[Page Fault Handling Process]

1. CPU references page table
2. Valid bit is i (invalid) -> Trap raised
      |
      v
3. OS confirms page fault
   - Invalid reference (out of address range)? -> Terminate process
   - Valid but not in memory? -> Continue
      |
      v
4. Find a free frame
      |
      v
5. Read page from disk into free frame (I/O)
      |
      v
6. When I/O completes:
   - Update page table (frame number, valid bit = v)
   - Restart process (from the instruction that caused the fault)

Demand Paging Performance

[Effective Access Time (EAT)]

p = page fault probability
ma = memory access time (200ns)
Page fault handling time = 8ms (8,000,000ns)

EAT = (1 - p) * ma + p * page fault time
    = (1 - p) * 200 + p * 8,000,000

If p = 0.001 (1 fault per 1000 accesses):
EAT = 0.999 * 200 + 0.001 * 8,000,000
    = 199.8 + 8,000
    = 8,199.8ns

40x performance degradation!

For less than 10% degradation:
220 > 200 + 7,999,800 * p
p < 0.0000025
i.e., fewer than 1 page fault per 400,000 accesses needed

Copy-on-Write (COW)

During fork(), instead of immediately copying the parent's pages, both processes share the same pages. Only when either side attempts to modify a page is that page copied.

[Copy-on-Write Operation]

Right after fork():
Parent page table:           Child page table:
Page 0 -> Frame A (COW)    Page 0 -> Frame A (COW)
Page 1 -> Frame B (COW)    Page 1 -> Frame B (COW)
Page 2 -> Frame C (COW)    Page 2 -> Frame C (COW)

When child modifies Page 1:
Parent page table:           Child page table:
Page 0 -> Frame A (COW)    Page 0 -> Frame A (COW)
Page 1 -> Frame B          Page 1 -> Frame D (copy)
Page 2 -> Frame C (COW)    Page 2 -> Frame C (COW)

Only the modified page is copied -> Eliminates unnecessary copies

// fork + exec pattern where COW is applied
#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();
    // At fork: parent's pages shared as COW

    if (pid == 0) {
        // When exec() is called, child's address space is completely replaced
        // Thanks to COW, no unnecessary page copying during fork
        execlp("ls", "ls", "-la", NULL);
    } else {
        wait(NULL);
    }

    return 0;
}

Page Replacement

When physical memory is full and a new page needs to be loaded, an existing page must be evicted (replaced) to disk.

[Page Replacement Process]

1. Locate page on disk
2. Find a free frame
   - If free frame exists, use it
   - If not, select victim page via replacement algorithm
     - If victim was modified (dirty bit), write to disk
     - If unmodified, just overwrite
3. Load new page into free frame
4. Update page table
5. Restart process

1. FIFO Page Replacement

The page that arrived first is replaced first.

[FIFO Example] 3 frames, reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Ref   7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> fault
     [7][0][ ] -> fault
     [7][0][1] -> fault
     [2][0][1] -> fault (7 replaced)
     [2][0][1] -> hit
     [2][3][1] -> fault (0 replaced)
     [2][3][0] -> fault (1 replaced)
     [4][3][0] -> fault (2 replaced)
     [4][2][0] -> fault (3 replaced)
     [4][2][3] -> fault (0 replaced)
     [0][2][3] -> fault (4 replaced)
     [0][2][3] -> hit
     [0][2][3] -> hit
     [0][1][3] -> fault (2 replaced)
     [0][1][2] -> fault (3 replaced)
     [0][1][2] -> hit
     [0][1][2] -> hit
     [7][1][2] -> fault (0 replaced)
     [7][0][2] -> fault (1 replaced)
     [7][0][1] -> fault (2 replaced)

Total page faults: 15

Belady's Anomaly: With FIFO, increasing the number of frames can actually increase page faults.

2. Optimal Page Replacement (OPT)

Replaces the page that will not be used for the longest time in the future. Theoretically optimal but impossible to implement since the future is unknown. Used as a benchmark for other algorithms.

[OPT Example] 3 frames, reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Ref   7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> fault
     [7][0][ ] -> fault
     [7][0][1] -> fault
     [2][0][1] -> fault (7: used latest in future)
     [2][0][1] -> hit
     [2][0][3] -> fault (1: used latest in future)
     [2][0][3] -> hit
     [2][4][3] -> fault (0 used soon, replace other)
     [2][4][3] -> hit
     [2][4][3] -> hit
     [2][0][3] -> fault
     [2][0][3] -> hit
     [2][0][3] -> hit
     [2][0][1] -> fault
     [2][0][1] -> hit
     [2][0][1] -> hit
     [2][0][1] -> hit
     [7][0][1] -> fault
     [7][0][1] -> hit
     [7][0][1] -> hit

Total page faults: 9 (optimal)

3. LRU Page Replacement (Least Recently Used)

Replaces the page that has not been used for the longest time. An approximation of OPT, using past information as an approximation of the future.

[LRU Example] 3 frames, reference string: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

Ref   7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> fault
     [7][0][ ] -> fault
     [7][0][1] -> fault
     [2][0][1] -> fault (7: least recently used)
     [2][0][1] -> hit
     [2][0][3] -> fault (1: least recently used)
     [2][0][3] -> hit (0 recently used)
     [4][0][3] -> fault (2: least recently used)
     [4][0][2] -> fault (3: least recently used)
     [4][3][2] -> fault (0: least recently used)
     [0][3][2] -> fault (4: least recently used)
     [0][3][2] -> hit
     [0][3][2] -> hit
     [1][3][2] -> fault (0: least recently used)
     [1][3][2] -> hit
     [1][0][2] -> fault (3: least recently used)
     [1][0][2] -> hit
     [1][0][7] -> fault (2: least recently used)
     [1][0][7] -> hit
     [1][0][7] -> hit

Total page faults: 12

LRU implementation methods.

Counter method: Record access time in each page table entry. Select the oldest one for replacement
Stack method: Move page to top of stack on access. Bottom of stack is the LRU page

Both methods require hardware support, and pure LRU implementation is costly.

4. Clock Algorithm (Second-Chance / Clock)

An approximation of LRU that uses a reference bit.

[Clock Algorithm]

Frames form a circular queue
Each frame has a reference bit (ref)

         Pointer
           |
           v
    [A, ref=1] -> [B, ref=0] -> [C, ref=1] -> [D, ref=0]
         ^                                          |
         |                                          |
         +------------------------------------------+

When replacement is needed:
1. Check frame pointed to
2. If ref=0: Replace this page
3. If ref=1: Reset ref to 0, move pointer to next
4. Repeat 2-3

Operation:
Pointer -> [A, ref=1]: Change ref to 0, move next
Pointer -> [B, ref=0]: Replace this page!

Reference bit is automatically set to 1 by hardware on page access

// Clock algorithm implementation (conceptual)
#define NUM_FRAMES 64

struct frame {
    int page_number;
    int reference_bit;
    int dirty_bit;
};

struct frame frames[NUM_FRAMES];
int clock_hand = 0;

int clock_replace() {
    while (1) {
        if (frames[clock_hand].reference_bit == 0) {
            // Found replacement target
            int victim = clock_hand;
            clock_hand = (clock_hand + 1) % NUM_FRAMES;
            return victim;
        }

        // Give second chance: reset reference bit
        frames[clock_hand].reference_bit = 0;
        clock_hand = (clock_hand + 1) % NUM_FRAMES;
    }
}

Algorithm Comparison

[Page Replacement Algorithm Comparison]

Algorithm    Perf      Belady     Impl Cost   Notes
--------    ------    --------   ---------   -----
FIFO        Poor      O          Low         Simplest
OPT         Optimal   X          Impossible  Theoretical benchmark
LRU         Good      X          High        Hardware support needed
Clock       Good      X          Medium      LRU approximation, practical

Frame Allocation

When multiple processes are running, the system must decide how many frames to allocate to each process.

Allocation Strategies

[Frame Allocation Methods]

1. Equal Allocation: Same number of frames for all processes
   100 frames, 5 processes -> 20 frames each

2. Proportional Allocation: Allocate proportional to process size
   Total frames = 62
   P1 size = 10 pages -> 10/137 * 62 = 4.5 -> 5 frames
   P2 size = 127 pages -> 127/137 * 62 = 57.5 -> 57 frames

Global vs Local Replacement

Global Replacement: Select victim from all frames. Higher throughput but unpredictable
Local Replacement: Replace only within the process's own frames. Predictable but potentially inefficient

Thrashing

A phenomenon where a process spends more time on page replacement than actual execution.

[How Thrashing Occurs]

1. Process has insufficient frames
2. Page faults occur frequently
3. CPU utilization drops (I/O waiting)
4. OS judges "CPU is idle"
5. Increases degree of multiprogramming (adds processes)
6. Existing processes get even fewer frames
7. More page faults -> Vicious cycle!

CPU Utilization
  ^
  |        /\
  |       /  \
  |      /    \
  |     /      \------> Thrashing!
  |    /
  |   /
  +--+---+---+---+----> Degree of Multiprogramming
     1   2   3   4

Working-Set Model

The set of pages actively used by a process at a specific point in time is called the working set.

[Working Set Concept]

Reference string: ... 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 ...
                                                  |<-- window size (delta) -->|

Working set at time t1 (delta=10):
WS(t1) = pages 1, 2, 3, 4 (unique pages within window)

Working set size = number of actively used pages

[Working Set Based Frame Allocation]

Total needed frames D = sum of all processes' working set sizes

if D > available frames:
    Thrashing possible
    -> Suspend some processes (swap out)

if D <= available frames:
    Allocate frames equal to working set size for each process
    -> Prevent thrashing

Page-Fault Frequency (PFF)

A more direct method than working sets that directly monitors the page fault rate.

[PFF-based Frame Adjustment]

Page Fault Rate
  ^
  |
  |---- Upper bound ----  If rate above this: Allocate more frames
  |
  |
  |---- Lower bound ----  If rate below this: Reclaim frames
  |
  +--+---+---+---+----> Allocated Frames

Above upper bound: Allocate more frames to the process
Below lower bound: Reclaim frames from the process
No more frames to allocate: Suspend the process

Memory-Mapped Files

A technique that handles file I/O as memory access. Maps part or all of a file to a process's virtual address space.

#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <string.h>

int main() {
    // Open file
    int fd = open("data.txt", O_RDWR);
    struct stat sb;
    fstat(fd, &sb);

    // Map file to memory
    char *mapped = mmap(NULL, sb.st_size,
                        PROT_READ | PROT_WRITE,
                        MAP_SHARED, fd, 0);

    if (mapped == MAP_FAILED) {
        perror("mmap failed");
        return 1;
    }

    // Access file contents like memory
    printf("File contents: %.50s\n", mapped);

    // Writing to memory also changes the file (MAP_SHARED)
    memcpy(mapped, "Modified content", 16);

    // Sync changes to disk
    msync(mapped, sb.st_size, MS_SYNC);

    // Unmap
    munmap(mapped, sb.st_size);
    close(fd);

    return 0;
}

[Memory-Mapped File Operation]

Process Virtual Address Space:     Physical Memory:       Disk:
+------------------+              +-----------+         +-------+
|                  |              |           |         |       |
| mmap region -----|------------->| File pages|<------->| File  |
|                  |              |           |         |       |
+------------------+              +-----------+         +-------+

1. mmap() maps file to address space
2. Page fault on access -> Load from file
3. Memory write marks page as dirty
4. Periodically or on munmap, write to disk

Advantages:
- No read/write system call overhead
- Multiple processes can share the same file
- Automatically utilizes page cache

mmap as Shared Memory Between Processes

// Shared memory between processes (MAP_SHARED + MAP_ANONYMOUS)
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/wait.h>

int main() {
    // Create anonymous shared mapping
    int *shared = mmap(NULL, sizeof(int),
                       PROT_READ | PROT_WRITE,
                       MAP_SHARED | MAP_ANONYMOUS,
                       -1, 0);

    *shared = 0;

    pid_t pid = fork();

    if (pid == 0) {
        // Child process
        *shared = 42;
        printf("Child: shared = %d\n", *shared);
    } else {
        // Parent process
        wait(NULL);
        printf("Parent: shared = %d\n", *shared);
        // Output: Parent: shared = 42
        munmap(shared, sizeof(int));
    }

    return 0;
}

Summary

[Virtual Memory Key Concepts Summary]

+-------------------+--------------------+
| Demand Paging     | Load only when needed|
| COW               | Minimize copies at fork|
+-------------------+--------------------+
| FIFO              | Simple but low perf |
| OPT               | Theoretically optimal (unimplementable)|
| LRU               | Practical, good perf|
| Clock             | LRU approx, widely used|
+-------------------+--------------------+
| Thrashing         | Fault explosion from|
|                   | frame shortage      |
| Working Set       | Track active page   |
|                   | set to prevent thrashing|
+-------------------+--------------------+
| Memory-mapped File| Handle file I/O as  |
|                   | memory access       |
+-------------------+--------------------+

Virtual memory is a core technology that overcomes the limitations of physical memory and provides each process with an independent address space. Demand paging loads only necessary pages, LRU and clock algorithms perform efficient page replacement, and the working set model prevents thrashing. Memory-mapped files enable efficient file I/O and inter-process communication.