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

[가상 메모리의 동작]

가상 주소 공간 (프로세스 관점):      물리 메모리:
+-----------+ 0xFFFF...           +-----------+
|   스택     |                     |   OS      |
|    |      |                     +-----------+
|    v      |                     | 페이지 A   | <-- 가상 페이지 0
|           |                     +-----------+
|           |                     | 페이지 C   | <-- 가상 페이지 5
|    ^      |                     +-----------+
|    |      |                     | 페이지 D   | <-- 가상 페이지 2
|   힙      |                     +-----------+
+-----------+                     |   빈 공간  |
|  데이터    |                     +-----------+
+-----------+
|  코드     |                     디스크 (스왑 영역):
+-----------+ 0x0000...           +-----------+
                                  | 페이지 B   | <-- 가상 페이지 1
4GB 가상 공간 중 일부만            | 페이지 E   | <-- 가상 페이지 3
물리 메모리에 올라가 있음           +-----------+

[요구 페이징 개념]

페이지 테이블:
+-------+------+
| 프레임 | 유효  |
+-------+------+
|   3   |  v   |  <- 메모리에 있음
|   -   |  i   |  <- 디스크에 있음 (아직 로드 안 됨)
|   7   |  v   |  <- 메모리에 있음
|   -   |  i   |  <- 디스크에 있음
+-------+------+

v = valid (메모리에 있음)
i = invalid (메모리에 없음, 디스크에 있음)

[페이지 폴트 처리 과정]

1. CPU가 페이지 테이블 참조
2. 유효 비트가 i (invalid) -> 트랩 발생
      |
      v
3. OS가 페이지 폴트 확인
   - 잘못된 참조(주소 범위 밖)? -> 프로세스 종료
   - 유효하지만 메모리에 없음? -> 계속 진행
      |
      v
4. 빈 프레임 찾기
      |
      v
5. 디스크에서 페이지를 빈 프레임으로 읽기 (I/O)
      |
      v
6. I/O 완료 시:
   - 페이지 테이블 갱신 (프레임 번호, 유효 비트 = v)
   - 프로세스 재시작 (폴트를 일으킨 명령어부터)

[유효 접근 시간(EAT)]

p = 페이지 폴트 확률
ma = 메모리 접근 시간 (200ns)
페이지 폴트 처리 시간 = 8ms (8,000,000ns)

EAT = (1 - p) * ma + p * 페이지 폴트 시간
    = (1 - p) * 200 + p * 8,000,000

p = 0.001 (1000번에 1번 폴트) 이면:
EAT = 0.999 * 200 + 0.001 * 8,000,000
    = 199.8 + 8,000
    = 8,199.8ns

성능 저하 40배!

10% 이내 성능 저하를 위해서는:
220 > 200 + 7,999,800 * p
p < 0.0000025
즉, 400,000번 접근에 1번 이하의 페이지 폴트 필요

[Copy-on-Write 동작]

fork() 직후:
부모 페이지 테이블:          자식 페이지 테이블:
페이지0 -> 프레임 A (COW)   페이지0 -> 프레임 A (COW)
페이지1 -> 프레임 B (COW)   페이지1 -> 프레임 B (COW)
페이지2 -> 프레임 C (COW)   페이지2 -> 프레임 C (COW)

자식이 페이지1을 수정하면:
부모 페이지 테이블:          자식 페이지 테이블:
페이지0 -> 프레임 A (COW)   페이지0 -> 프레임 A (COW)
페이지1 -> 프레임 B         페이지1 -> 프레임 D (복사본)
페이지2 -> 프레임 C (COW)   페이지2 -> 프레임 C (COW)

수정된 페이지만 복사 -> 불필요한 복사 제거

// COW가 적용되는 fork + exec 패턴
#include <unistd.h>
#include <sys/wait.h>

int main() {
    pid_t pid = fork();
    // fork 시점: 부모의 페이지를 COW로 공유

    if (pid == 0) {
        // exec() 호출 시 자식의 주소 공간이 완전히 교체됨
        // COW 덕분에 fork에서 불필요한 페이지 복사 없음
        execlp("ls", "ls", "-la", NULL);
    } else {
        wait(NULL);
    }

    return 0;
}

[페이지 교체 과정]

1. 디스크에서 페이지 위치 확인
2. 빈 프레임 찾기
   - 빈 프레임이 있으면 사용
   - 없으면 교체 알고리즘으로 희생 페이지 선택
     - 희생 페이지가 수정되었으면(dirty bit) 디스크에 기록
     - 수정되지 않았으면 그냥 덮어쓰기
3. 새 페이지를 빈 프레임에 로드
4. 페이지 테이블 갱신
5. 프로세스 재시작

[FIFO 예시] 프레임 3개, 참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

참조  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> 폴트
     [7][0][ ] -> 폴트
     [7][0][1] -> 폴트
     [2][0][1] -> 폴트 (7 교체)
     [2][0][1] -> 히트
     [2][3][1] -> 폴트 (0 교체)
     [2][3][0] -> 폴트 (1 교체)
     [4][3][0] -> 폴트 (2 교체)
     [4][2][0] -> 폴트 (3 교체)
     [4][2][3] -> 폴트 (0 교체)
     [0][2][3] -> 폴트 (4 교체)
     [0][2][3] -> 히트
     [0][2][3] -> 히트
     [0][1][3] -> 폴트 (2 교체)
     [0][1][2] -> 폴트 (3 교체)
     [0][1][2] -> 히트
     [0][1][2] -> 히트
     [7][1][2] -> 폴트 (0 교체)
     [7][0][2] -> 폴트 (1 교체)
     [7][0][1] -> 폴트 (2 교체)

총 페이지 폴트: 15

[OPT 예시] 프레임 3개, 참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

참조  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> 폴트
     [7][0][ ] -> 폴트
     [7][0][1] -> 폴트
     [2][0][1] -> 폴트 (7: 가장 나중에 사용)
     [2][0][1] -> 히트
     [2][0][3] -> 폴트 (1: 가장 나중에 사용)
     [2][0][3] -> 히트
     [2][4][3] -> 폴트 (0을 곧 사용하므로 다른 것 교체)
     [2][4][3] -> 히트
     [2][4][3] -> 히트
     [2][0][3] -> 폴트
     [2][0][3] -> 히트
     [2][0][3] -> 히트
     [2][0][1] -> 폴트
     [2][0][1] -> 히트
     [2][0][1] -> 히트
     [2][0][1] -> 히트
     [7][0][1] -> 폴트
     [7][0][1] -> 히트
     [7][0][1] -> 히트

총 페이지 폴트: 9 (최적)

[LRU 예시] 프레임 3개, 참조열: 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

참조  7  0  1  2  0  3  0  4  2  3  0  3  2  1  2  0  1  7  0  1
     [7][ ][ ] -> 폴트
     [7][0][ ] -> 폴트
     [7][0][1] -> 폴트
     [2][0][1] -> 폴트 (7: 가장 오래 전 사용)
     [2][0][1] -> 히트
     [2][0][3] -> 폴트 (1: 가장 오래 전 사용)
     [2][0][3] -> 히트 (0이 최근 사용)
     [4][0][3] -> 폴트 (2: 가장 오래 전 사용)
     [4][0][2] -> 폴트 (3: 가장 오래 전 사용)
     [4][3][2] -> 폴트 (0: 가장 오래 전 사용)
     [0][3][2] -> 폴트 (4: 가장 오래 전 사용)
     [0][3][2] -> 히트
     [0][3][2] -> 히트
     [1][3][2] -> 폴트 (0: 가장 오래 전 사용)
     [1][3][2] -> 히트
     [1][0][2] -> 폴트 (3: 가장 오래 전 사용)
     [1][0][2] -> 히트
     [1][0][7] -> 폴트 (2: 가장 오래 전 사용)
     [1][0][7] -> 히트
     [1][0][7] -> 히트

총 페이지 폴트: 12

[클럭 알고리즘]

프레임들이 원형 큐를 이룸
각 프레임에 참조 비트(ref)가 있음

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

교체가 필요할 때:
1. 포인터가 가리키는 프레임 확인
2. ref=0이면: 이 페이지를 교체
3. ref=1이면: ref를 0으로 리셋하고, 포인터를 다음으로 이동
4. 2-3을 반복

동작 과정:
포인터 -> [A, ref=1]: ref=0으로 변경, 다음으로
포인터 -> [B, ref=0]: 이 페이지를 교체!

참조 비트는 하드웨어가 페이지 접근 시 자동으로 1로 설정

// 클럭 알고리즘 구현 (개념적)
#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) {
            // 교체 대상 발견
            int victim = clock_hand;
            clock_hand = (clock_hand + 1) % NUM_FRAMES;
            return victim;
        }

        // 두 번째 기회 부여: 참조 비트 초기화
        frames[clock_hand].reference_bit = 0;
        clock_hand = (clock_hand + 1) % NUM_FRAMES;
    }
}

[페이지 교체 알고리즘 비교]

알고리즘    성능      벨래디 이상   구현 비용   비고
--------   ------    ----------   --------   ----
FIFO       나쁨      O            낮음       가장 단순
OPT        최적      X            불가능     이론적 기준
LRU        좋음      X            높음       하드웨어 지원 필요
클럭       양호      X            중간       LRU 근사, 실용적

[프레임 할당 방식]

1. 균등 할당: 모든 프로세스에 동일한 수의 프레임
   100 프레임, 5 프로세스 -> 각 20 프레임

2. 비례 할당: 프로세스 크기에 비례하여 할당
   총 프레임 = 62
   P1 크기 = 10페이지 -> 10/137 * 62 = 4.5 -> 5 프레임
   P2 크기 = 127페이지 -> 127/137 * 62 = 57.5 -> 57 프레임

[스래싱 발생 과정]

1. 프로세스에 프레임이 부족
2. 페이지 폴트 빈번 발생
3. CPU 이용률 저하 (I/O 대기)
4. OS가 "CPU가 놀고 있다"고 판단
5. 다중 프로그래밍 정도 증가 (프로세스 추가)
6. 기존 프로세스의 프레임이 더 줄어듦
7. 더 많은 페이지 폴트 -> 악순환!

CPU 이용률
  ^
  |        /\
  |       /  \
  |      /    \
  |     /      \------> 스래싱!
  |    /
  |   /
  +--+---+---+---+----> 다중 프로그래밍 정도
     1   2   3   4

[워킹 셋 개념]

참조열: ... 2 6 1 5 7 7 7 7 5 1 6 2 3 4 1 2 3 4 4 4 3 ...
                                            |<-- 윈도우 크기 (delta) -->|

시점 t1의 워킹 셋(delta=10):
WS(t1) = 페이지 1, 2, 3, 4 (윈도우 내 고유 페이지)

워킹 셋 크기 = 활발히 사용 중인 페이지 수

[워킹 셋 기반 프레임 할당]

총 필요 프레임 D = 모든 프로세스의 워킹 셋 크기 합

if D > 가용 프레임 수:
    스래싱 발생 가능
    -> 일부 프로세스를 일시 중단(swap out)

if D <= 가용 프레임 수:
    각 프로세스에 워킹 셋 크기만큼 프레임 할당
    -> 스래싱 방지

[PFF 기반 프레임 조절]

페이지 폴트율
  ^
  |
  |---- 상한선 ----  폴트율이 이 위면: 프레임 추가 할당
  |
  |
  |---- 하한선 ----  폴트율이 이 아래면: 프레임 회수
  |
  +--+---+---+---+----> 할당된 프레임 수

상한선 초과: 프로세스에 프레임을 더 할당
하한선 미달: 프로세스에서 프레임을 회수
추가 할당할 프레임이 없으면: 프로세스 일시 중단

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

int main() {
    // 파일 열기
    int fd = open("data.txt", O_RDWR);
    struct stat sb;
    fstat(fd, &sb);

    // 파일을 메모리에 매핑
    char *mapped = mmap(NULL, sb.st_size,
                        PROT_READ | PROT_WRITE,
                        MAP_SHARED, fd, 0);

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

    // 파일 내용을 메모리처럼 접근
    printf("파일 내용: %.50s\n", mapped);

    // 메모리에 쓰면 파일도 변경됨 (MAP_SHARED)
    memcpy(mapped, "수정된 내용", 15);

    // 변경 사항을 디스크에 동기화
    msync(mapped, sb.st_size, MS_SYNC);

    // 매핑 해제
    munmap(mapped, sb.st_size);
    close(fd);

    return 0;
}

[메모리 매핑 파일 동작]

프로세스 가상 주소 공간:       물리 메모리:         디스크:
+------------------+         +-----------+       +-------+
|                  |         |           |       |       |
| mmap 영역 -------|-------->| 파일 페이지 |<----->| 파일  |
|                  |         |           |       |       |
+------------------+         +-----------+       +-------+

1. mmap()으로 파일을 주소 공간에 매핑
2. 해당 영역 접근 시 페이지 폴트 -> 파일에서 로드
3. 메모리 쓰기 시 dirty 페이지 표시
4. 주기적으로 또는 munmap 시 디스크에 기록

장점:
- read/write 시스템 콜 오버헤드 없음
- 여러 프로세스가 같은 파일을 공유 가능
- 페이지 캐시를 자동으로 활용

// 프로세스 간 공유 메모리 (MAP_SHARED + MAP_ANONYMOUS)
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <sys/wait.h>

int main() {
    // 익명 공유 매핑 생성
    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) {
        // 자식 프로세스
        *shared = 42;
        printf("자식: shared = %d\n", *shared);
    } else {
        // 부모 프로세스
        wait(NULL);
        printf("부모: shared = %d\n", *shared);
        // 출력: 부모: shared = 42
        munmap(shared, sizeof(int));
    }

    return 0;
}

[가상 메모리 핵심 개념 요약]

+-------------------+--------------------+
| 요구 페이징        | 필요할 때만 로드     |
| COW               | fork 시 복사 최소화  |
+-------------------+--------------------+
| FIFO              | 단순하지만 성능 낮음  |
| OPT               | 이론적 최적 (구현 불가)|
| LRU               | 실용적이고 성능 좋음  |
| 클럭              | LRU 근사, 대부분 사용 |
+-------------------+--------------------+
| 스래싱             | 프레임 부족으로 폴트  |
|                   | 폭증하는 현상        |
| 워킹 셋           | 활발한 페이지 집합    |
|                   | 추적으로 스래싱 방지  |
+-------------------+--------------------+
| 메모리 매핑 파일    | 파일 I/O를 메모리    |
|                   | 접근으로 처리        |
+-------------------+--------------------+