Split View: [운영체제] 10. 가상 메모리: 요구 페이징부터 스래싱까지

[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                     +-----------+

[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 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)

[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 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 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

[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

[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)

[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

[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;
    }
}

[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 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

[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 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

[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

#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

// 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;
}

[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       |
+-------------------+--------------------+