안동민 개발노트

가상 메모리의 핵심 아이디어는, 프로세스의 모든 페이지를 미리 메모리에 올리지 않아도 된다는 것입니다. 실제로 필요한 페이지만 메모리에 올리면 됩니다. 이것이 요구 페이징(Demand Paging)이며, 현대 OS 가상 메모리의 기반 전략입니다.

요구 페이징의 원리

왜 모든 페이지를 올리지 않는가

프로세스의 코드와 데이터를 전부 메모리에 올리면:

실행 시작이 느려집니다 (수 MB~수 GB를 디스크에서 읽어야 함).
에러 처리 코드, 드물게 실행되는 함수, 대규모 데이터 배열의 일부분 등 실제로 사용되지 않는 부분까지 메모리를 차지합니다.
동시에 실행할 수 있는 프로세스 수가 줄어듭니다.

요구 페이징은 이 문제를 해결합니다. 프로세스가 시작될 때 아무 페이지도 올리지 않을 수 있습니다(순수 요구 페이징). 프로세스가 특정 페이지에 접근하면, 그때 해당 페이지를 디스크에서 메모리로 읽어옵니다.

지역성이 동작하는 이유

이 게으른(Lazy) 전략이 효율적인 이유는 지역성의 원리(Principle of Locality) 때문입니다.

시간적 지역성: 최근 접근한 메모리 위치를 가까운 미래에 다시 접근할 확률이 높습니다. 루프 변수, 함수 내 지역 변수가 대표적입니다.

공간적 지역성: 접근한 메모리 위치 근처의 메모리를 곧 접근할 확률이 높습니다. 배열 순차 접근, 인접 명령어 실행이 대표적입니다.

이러한 지역성 덕분에, 프로세스는 어느 시점에서든 전체 주소 공간의 극히 일부만 활발하게 사용합니다. 이 활발한 부분을 워킹 셋(Working Set)이라고 합니다. 워킹 셋만 메모리에 있으면 프로세스는 거의 페이지 폴트 없이 실행됩니다.

페이지 테이블의 유효 비트

페이지 테이블 엔트리에 유효 비트(Valid Bit)가 있습니다.

유효 = 1: 해당 페이지가 물리 메모리(프레임)에 존재합니다.
유효 = 0: 해당 페이지가 디스크에 있거나 아직 할당되지 않았습니다.

페이지 폴트 처리 과정

CPU가 유효 비트 0인 페이지에 접근하면 페이지 폴트(Page Fault) 트랩이 발생합니다. 단계별 처리:

트랩 발생: CPU가 페이지 폴트 인터럽트를 발생시키고, OS의 페이지 폴트 핸들러에 제어를 넘깁니다.
주소 유효성 확인: OS가 프로세스의 주소 공간 정보(PCB, VMA 리스트)를 확인합니다. 유효 범위 밖의 접근이면 세그먼테이션 폴트로 프로세스를 종료합니다. 유효 범위 내라면 다음 단계로 진행합니다.
빈 프레임 확보: 프리 프레임 리스트에서 빈 프레임을 가져옵니다. 빈 프레임이 없으면 페이지 교체 알고리즘으로 기존 페이지를 내보냅니다(다음 절에서 설명).
디스크 I/O: 해당 페이지를 디스크(스왑 영역 또는 실행 파일)에서 빈 프레임으로 읽어옵니다. 이 I/O 동안 프로세스는 대기(block) 상태로 전환되고, CPU는 다른 프로세스를 실행합니다.
페이지 테이블 업데이트: I/O가 완료되면, 페이지 테이블 엔트리를 업데이트합니다 — 유효 비트를 1로, 프레임 번호를 기록합니다.
명령어 재실행: 페이지 폴트를 일으킨 명령어를 처음부터 다시 실행합니다. 이번에는 유효 비트가 1이므로 정상적으로 진행됩니다.

페이지 폴트의 성능 영향

페이지 폴트 처리 시간을 $t_{pf}$ , 일반 메모리 접근 시간을 $t$ , 페이지 폴트 확률을 $p$ 라고 하면:

$EAT = (1 - p) \times t + p \times t_{pf}$

$t = 100\text{ns}$ , $t_{pf} = 8\text{ms}$ (SSD 기준), $p = 0.001$ (1000번에 1번)이면:

$EAT = 0.999 \times 100 + 0.001 \times 8000000 = 99.9 + 8000 = 8099.9\text{ns}$

페이지 폴트 확률이 0.1%에 불과해도 성능이 80배 저하됩니다! 페이지 폴트율을 극도로 낮추는 것이 가상 메모리 성능의 핵심입니다.

page_fault_demo.c

#include <stdio.h>
#include <stdlib.h>
#include <sys/resource.h>

int main() {
    struct rusage before, after;
    getrusage(RUSAGE_SELF, &before);

    /* 대량 메모리 할당 및 접근 — 페이지 폴트 유발 */
    size_t size = 100 * 1024 * 1024;  /* 100MB */
    char *buf = malloc(size);
    for (size_t i = 0; i < size; i += 4096) {
        buf[i] = 1;  /* 각 페이지의 첫 바이트에 접근 */
    }

    getrusage(RUSAGE_SELF, &after);
    long minor = after.ru_minflt - before.ru_minflt;
    long major = after.ru_majflt - before.ru_majflt;
    printf("Minor page faults: %ld\n", minor);  /* ~25600 */
    printf("Major page faults: %ld\n", major);   /* 0 (메모리 충분시) */

    free(buf);
    return 0;
}

Minor page fault: 디스크 I/O 없이 해결되는 페이지 폴트. 예: 0으로 초기화된 빈 프레임을 할당하거나, 이미 메모리에 있는 공유 페이지를 매핑.

Major page fault: 디스크에서 페이지를 읽어야 하는 페이지 폴트. 수 밀리초 소요. 성능에 심각한 영향.

Copy-on-Write

fork() 시스템 콜로 자식 프로세스를 만들면, 부모의 전체 주소 공간을 복사해야 합니다. 4GB 주소 공간을 복사하면 엄청난 시간과 메모리가 소요됩니다.

Copy-on-Write(COW)는 이 문제를 우아하게 해결합니다.

fork() 직후: 부모와 자식이 같은 물리 페이지를 공유합니다.
공유된 페이지는 읽기 전용으로 표시됩니다.
둘 중 하나가 페이지에 쓰기를 시도하면, 보호 위반 트랩이 발생합니다.
OS가 해당 페이지만 복사(Copy)하고, 쓰기를 허용합니다.
수정이 발생한 페이지만 복사되므로 불필요한 복사를 완전히 피합니다.

cow_example.c

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>

int main() {
    int *data = malloc(sizeof(int));
    *data = 100;

    pid_t pid = fork();
    /* fork 직후: parent와 child가 data 페이지를 공유 (COW)
       data가 있는 물리 프레임은 하나, 양쪽 페이지 테이블이 같은
       프레임을 가리킴. 읽기 전용으로 표시됨. */

    if (pid == 0) {
        /* 자식: 쓰기 시도 → 보호 위반 트랩 → OS가 페이지 복사 */
        *data = 200;
        printf("Child: %d\n", *data);  /* 200 (복사된 페이지) */
        free(data);
        _exit(0);
    } else {
        wait(NULL);
        printf("Parent: %d\n", *data);  /* 100 (원본 유지) */
        free(data);
    }
    return 0;
}

많은 프로세스가 fork() 후 바로 exec()를 호출하여 새 프로그램을 실행합니다. exec()는 주소 공간을 완전히 교체하므로, COW 덕분에 fork()에서 복사된 페이지가 제로입니다.

Linux에서는 fork() 대안으로 COW를 개선한 vfork() 도 있습니다. vfork()는 부모를 일시 중단하고 자식이 부모의 주소 공간을 직접 사용합니다. exec() 직전까지만 사용하므로 페이지 테이블 복사조차 필요 없습니다.

빈 프레임이 없다면 — 페이지 교체의 필요성

물리 메모리가 가득 차서 빈 프레임이 없는 상태에서 페이지 폴트가 발생하면, 기존에 메모리에 있던 페이지 중 하나를 내보내야(Evict) 합니다.

내보내는 페이지가 수정되었다면(더티 비트 = 1), 디스크에 써야 하므로 추가 I/O가 발생합니다(Page out). 수정되지 않은 깨끗한 페이지(더티 비트 = 0)는 디스크에 이미 원본이 있으므로, 그냥 프레임을 반환하면 됩니다. 따라서 더티 비트의 값에 따라 페이지 교체의 비용이 크게 달라집니다.

어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘이며, 이것이 가상 메모리 성능의 핵심입니다. 잘못된 페이지를 내보내면 곧바로 다시 필요해져서 또 페이지 폴트가 발생합니다.

메모리 매핑 파일 (Memory-Mapped Files)

페이지 폴트 메커니즘의 응용으로, 메모리 매핑 파일이 있습니다. mmap() 시스템 콜로 파일을 프로세스의 주소 공간에 직접 매핑합니다. 파일의 내용이 메모리처럼 접근 가능해지며, 실제 데이터는 페이지 폴트를 통해 자동으로 로드됩니다.

mmap_example.c

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

int main() {
    int fd = open("data.bin", O_RDONLY);
    /* 파일을 메모리에 매핑 */
    char *mapped = mmap(NULL, 4096, PROT_READ, MAP_PRIVATE, fd, 0);
    close(fd);

    /* 메모리처럼 접근 — 첫 접근 시 page fault → OS가 파일에서 읽음 */
    printf("첫 번째 바이트: %c\n", mapped[0]);

    munmap(mapped, 4096);
    return 0;
}

다음 절에서 다양한 페이지 교체 알고리즘과 그 성능 비교를 살펴보겠습니다.

요구 페이징과 페이지 폴트