디맨드 페이징

디맨드 페이징은 프로그램 내용 중 실제로 건드리는 부분만 그때그때 디스크에서 메모리로 올리는 운영체제의 방식입니다. 프로그램을 켤 때 디스크에서 전부 읽어 오지 않으므로 시작이 빠르고 메모리도 덜 듭니다. 대가는 처음 건드리는 순간마다 프로그램이 잠깐 멈춘다는 것입니다.

상세

이 절은 먼저 디맨드 페이징이 기대는 바탕인 가상 메모리와 페이지 테이블을 풉니다. 그다음 메모리에 없는 조각을 건드렸을 때 하드웨어와 운영체제가 주고받는 순서를 따라갑니다. 이어서 메모리가 찼을 때 무슨 일이 생기고 어떤 조건에서 이 방식이 무너지는지 봅니다. 끝으로 백엔드 개발자가 메모리 숫자에서 이 방식을 마주치는 모습을 봅니다.

도서관에서 백 권짜리 전집을 빌리는 장면을 떠올리면 됩니다. 사서는 백 권을 한꺼번에 책상에 쌓아 주지 않습니다. 대출 장부에 백 권을 적어만 둡니다. 읽을 권을 찾을 때마다 그 한 권을 서고에서 꺼내 옵니다. 책상이 차면 한동안 안 펼친 권을 서고로 돌려보냅니다.

운영체제는 프로그램이 쓰는 메모리를 같은 크기의 조각으로 잘라 다룹니다. 이 조각을 페이지라고 부릅니다. 조각 단위로 다뤄야 프로그램 전체가 아니라 필요한 부분만 골라 옮길 수 있습니다.

디맨드 페이징(demand paging)은 프로그램이 어떤 페이지를 처음 건드릴 때에야 그 페이지를 물리 메모리에 올리는 방식입니다. 물리 메모리는 컴퓨터에 꽂혀 있는 메모리 칩입니다. 우리말로는 요구 페이징이라고도 부릅니다. 「요구」는 프로그램이 그 페이지를 건드려 필요를 드러낸 때를 가리킵니다.

실행 파일이 페이지 천 개 분량이어도 시작할 때 쓰는 코드가 열 페이지면 처음에는 열 페이지만 올라옵니다. 나머지는 디스크에 남아 있습니다. 프로그램이 그 코드에 닿을 때 한 페이지씩 올라옵니다.

디맨드 페이징이 없으면 운영체제는 프로그램을 켤 때 페이지 천 개를 전부 디스크에서 읽어야 합니다. 시작이 그만큼 늦어집니다. 오류 처리처럼 거의 안 도는 코드도 메모리를 차지해서 함께 띄울 수 있는 프로그램 수가 줄어듭니다.

가상 메모리가 깔아 주는 바탕

가상 메모리는 프로그램마다 자기만의 주소 공간을 보여 주는 장치입니다. 주소 공간은 한 프로그램이 쓸 수 있는 주소들의 전체 범위입니다. 그 안에서도 실제로 쓸 수 있는 것은 운영체제가 그 프로그램에 쓰라고 내준 주소 범위뿐입니다.

프로그램이 쓰는 주소는 가상 주소입니다. 이 주소가 물리 메모리의 어디에 닿는지는 따로 정해집니다. 주소와 실물 사이에 이렇게 한 겹을 끼워 두어야 「주소는 있는데 내용은 아직 메모리에 없다」는 상태를 만들 수 있습니다.

가상 주소를 물리 주소로 바꾸는 표가 페이지 테이블입니다. 물리 주소는 물리 메모리 안의 실제 위치입니다. 가상 페이지 하나마다 표에 한 줄이 있습니다. 그 줄에 이 페이지가 물리 메모리의 어느 칸에 있는지 적습니다.

페이지 하나가 들어가는 물리 메모리 쪽 칸을 페이지 프레임이라고 합니다. 줄여서 프레임이라고도 부릅니다. 프레임은 페이지와 크기가 같아서 어느 페이지든 아무 빈 프레임에나 담을 수 있습니다.

표를 읽어 주소를 바꾸는 일은 CPU(Central Processing Unit, 중앙 처리 장치) 안의 하드웨어가 합니다. 이 하드웨어를 MMU(Memory Management Unit, 메모리 관리 장치)라고 부릅니다. 표를 채우는 쪽은 운영체제입니다. 명령마다 표를 읽는 쪽은 MMU 입니다.

페이지마다 붙는 유효 비트

페이지 테이블의 줄마다 이 페이지가 지금 물리 메모리에 올라와 있는지를 나타내는 비트가 하나 있습니다. 이를 유효 비트라고 부릅니다. 1이면 올라와 있고 0이면 아직 없습니다. 아키텍처에 따라 존재 비트라고 부르기도 합니다.

디맨드 페이징에서는 프로그램을 막 시작했을 때 거의 모든 줄의 유효 비트가 0입니다. 운영체제는 그 대신 각 페이지의 내용이 디스크 어디에 있는지를 따로 기억해 둡니다. 아래 그림은 프로그램이 조금 돈 뒤의 모습입니다.

flowchart TD
    subgraph V["가상 주소 공간"]
        P0["페이지 0 · 유효 1"]
        P1["페이지 1 · 유효 0"]
        P2["페이지 2 · 유효 1"]
        P3["페이지 3 · 유효 0"]
    end
    subgraph M["물리 메모리"]
        F5["프레임 5"]
        F9["프레임 9"]
    end
    subgraph D["디스크"]
        X1["페이지 1 내용"]
        X3["페이지 3 내용"]
    end
    P0 --> F5
    P2 --> F9
    P1 -.-> X1
    P3 -.-> X3

페이지 0과 2는 한 번 건드려져서 프레임 5와 9에 올라와 있습니다. 페이지 1과 3은 아직 아무도 안 건드려서 내용이 디스크에만 있습니다. 실선은 페이지 테이블이 가리키는 프레임입니다. 점선은 운영체제가 따로 기억해 둔 디스크 위치입니다.

없는 페이지를 건드릴 때 나는 페이지 폴트

유효 비트가 0인 페이지를 건드리면 MMU 는 주소를 바꾸지 못합니다. MMU 는 그 명령을 멈추고 운영체제를 부릅니다. 이 사건을 페이지 폴트라고 합니다. 폴트(fault)는 하드웨어가 명령을 끝내지 못하고 운영체제에 처리를 넘기는 예외의 한 종류입니다.

이름에 「폴트」가 붙었지만 디맨드 페이징에서 페이지 폴트는 고장이 아닙니다. 운영체제에게 지금 이 페이지를 올리라고 알리는 신호입니다. 정상 동작의 일부입니다.

sequenceDiagram
    participant P as 프로그램
    participant M as MMU
    participant O as 운영체제
    participant D as 디스크
    P->>M: 페이지 1 의 주소를 읽는다
    Note over M: 유효 비트가 0 이다
    M->>O: 페이지 폴트
    Note over O: 내준 범위 안의 주소인지 확인한다
    O->>D: 페이지 1 내용을 읽는다
    D-->>O: 내용
    Note over O: 빈 프레임에 담고 표를 고친다
    O-->>P: 멈춘 명령을 다시 실행한다
    P->>M: 같은 주소를 다시 읽는다
    M-->>P: 값

운영체제는 맨 먼저 그 주소가 자기가 그 프로그램에 내준 범위 안인지 봅니다. 범위 밖이면 올릴 내용이 처음부터 없습니다. 그때는 프로그램을 끝냅니다. 개발자는 이것을 세그멘테이션 폴트로 만납니다.

범위 안이면 빈 프레임을 하나 고르고 디스크에서 페이지 내용을 읽어 담습니다. 그다음 페이지 테이블의 줄에 그 프레임 번호를 적고 유효 비트를 1로 바꿉니다. 마지막으로 멈췄던 명령을 처음부터 다시 실행합니다.

이번에는 페이지가 올라와 있으므로 같은 명령이 성공합니다. 프로그램 쪽에서 보면 명령 하나가 오래 걸렸을 뿐입니다. 페이지를 올리는 일은 프로그램 코드가 모르는 채로 끝납니다.

디스크를 읽는 동안 CPU 가 노는 것도 아닙니다. 운영체제는 폴트를 낸 프로그램을 기다리게 두고 다른 프로그램을 돌립니다. 이렇게 CPU 를 다른 프로그램에 넘기는 일을 문맥 교환이라고 합니다.

디스크에서 읽을 것이 없는 페이지

모든 페이지가 디스크에서 오는 것은 아닙니다. 힙이나 스택처럼 프로그램이 돌면서 운영체제에게서 새로 받은 메모리는 처음부터 내용이 없습니다. 이런 페이지는 처음 건드릴 때 0으로 채운 빈 프레임을 붙입니다.

0으로 채우는 까닭은 그 프레임을 앞서 다른 프로그램이 썼을 수 있어서입니다. 남이 남긴 데이터가 새 프로그램에 보이면 안 됩니다.

그래서 메모리를 받기만 하고 안 건드리면 물리 메모리를 차지하지 않습니다. 운영체제는 이 성질을 믿고 물리 메모리보다 많은 양을 내주기도 합니다. 이를 메모리 오버커밋이라고 합니다.

빈 프레임이 없을 때의 페이지 교체

물리 메모리가 다 차 있으면 새 페이지를 담을 프레임이 없습니다. 운영체제는 올라와 있던 페이지 하나를 골라 내보내고 그 프레임을 씁니다. 무엇을 내보낼지 고르는 규칙을 페이지 교체 알고리즘이라고 합니다.

흔히 기준으로 삼는 것은 LRU(Least Recently Used, 가장 오래전에 쓴 것)입니다. 가장 오래 안 쓴 페이지를 내보냅니다. 다만 정확히 따르려면 메모리를 건드릴 때마다 순서를 기록해야 해서 비쌉니다. 실제 운영체제는 대개 LRU 에 가까운 결과를 싸게 내는 방식을 씁니다.

내보낼 때 할 일은 그 페이지가 올라온 뒤 고쳐졌는지에 달려 있습니다. 고쳐졌는지는 페이지 테이블 줄의 더티 비트가 알려 줍니다. 프로그램이 그 페이지에 한 번이라도 쓰면 하드웨어가 이 비트를 1로 바꿉니다.

안 고친 페이지는 버리기만 하면 됩니다. 실행 파일의 코드처럼 원본이 디스크에 남아 있어서 다시 읽으면 되기 때문입니다. 고친 페이지는 버리면 바뀐 내용을 잃습니다. 그래서 디스크의 스왑 영역에 먼저 써 둡니다. 스왑 영역은 내보낸 페이지를 담아 두려고 디스크에 따로 떼어 둔 공간입니다.

내보낸 페이지는 표에서 유효 비트가 다시 0이 됩니다. 프로그램이 그 페이지를 또 건드리면 페이지 폴트가 나고 앞의 순서로 다시 올라옵니다. 페이지를 이렇게 디스크와 메모리 사이에서 오르내리게 하는 일을 스와핑이라고 부릅니다.

stateDiagram-v2
    state "아직 안 올라옴" as N
    state "올라옴 · 안 고침" as C
    state "올라옴 · 고침" as W
    [*] --> N
    N --> C: 페이지 폴트로 올린다
    C --> W: 프로그램이 쓴다
    C --> N: 내보낸다 · 버리기만 한다
    W --> N: 내보낸다 · 스왑 영역에 쓴다

페이지 하나는 이 세 상태를 오갑니다. 안 올라온 페이지는 폴트로 올라옵니다. 쓰기를 한 번 받으면 고친 상태가 됩니다. 내보낼 때는 고쳤는지에 따라 버리거나 스왑 영역에 쓴 뒤 다시 안 올라온 상태로 돌아갑니다.

이 방식이 버티는 까닭인 참조 지역성

페이지 폴트 한 번은 비쌉니다. 디스크를 기다리는 폴트는 메모리를 한 번 읽는 것보다 몇 자릿수 느립니다. 그런데도 디맨드 페이징이 쓸 만한 까닭은 프로그램이 메모리를 고르게 쓰지 않기 때문입니다.

프로그램은 짧은 시간 동안 좁은 범위의 주소를 되풀이해 씁니다. 반복문은 같은 코드를 여러 번 돕니다. 배열은 붙어 있는 주소를 차례로 읽습니다. 이 성질을 참조 지역성이라고 합니다.

그래서 폴트는 프로그램이 시작하거나 새 일을 맡을 때 몰리고 곧 잦아듭니다. 한동안 자주 쓰는 페이지 묶음을 워킹 셋이라고 부릅니다. 워킹 셋이 메모리에 다 올라오면 폴트는 드물어집니다.

무너지는 조건인 스래싱

돌고 있는 프로그램들의 워킹 셋을 합친 크기가 물리 메모리보다 크면 일이 꼬입니다. 한 페이지를 올리려고 내보낸 페이지를 곧바로 다른 프로그램이 다시 찾습니다. 폴트가 다음 폴트를 부릅니다.

이 상태를 스래싱이라고 합니다. 디스크는 쉴 새 없이 돌지만 CPU 는 거의 놉니다. 프로그램들이 모두 디스크를 기다리느라 앞으로 거의 못 나아갑니다.

풀려면 워킹 셋의 합을 줄여야 합니다. 프로그램 몇 개를 멈추거나 메모리를 늘립니다. 메모리가 끝내 모자라면 운영체제가 돌고 있는 프로그램을 골라 강제로 끝내기도 합니다. 리눅스의 OOM 킬러(Out Of Memory killer, 메모리 부족 때 돌고 있는 프로그램을 끝내는 장치)가 그 예입니다.

미리 올려 두는 선택

이론 그대로의 디맨드 페이징은 폴트가 난 페이지 하나만 올립니다. 운영체제는 대개 그 둘레의 페이지까지 함께 읽어 옵니다. 참조 지역성 때문에 붙은 주소를 곧 쓸 가능성이 높아서입니다. 이렇게 앞질러 읽는 것을 선반입이라고 합니다.

반대편 끝은 시작할 때 전부 올리는 방식입니다. 첫 요청부터 응답이 고르게 빨라야 하는 프로그램은 시작 무렵에 쓸 메모리를 일부러 한 번씩 건드려 두기도 합니다. 폴트를 요청 처리 중이 아니라 시작 때 미리 치르는 것입니다.

백엔드에서 보이는 메모리 숫자 둘

실행 중인 프로그램을 프로세스라고 합니다. 프로세스 모니터는 대개 프로세스마다 메모리를 두 숫자로 보여 줍니다. 하나는 그 프로세스가 받은 가상 주소 공간의 크기인 가상 크기입니다. 다른 하나는 그중 지금 물리 메모리에 올라와 있는 크기인 상주 크기입니다.

상주 크기의 정식 이름은 상주 집합 크기(RSS, Resident Set Size)입니다. 디맨드 페이징 때문에 두 숫자는 크게 벌어질 수 있습니다. 받기만 하고 안 건드린 메모리는 가상 크기에만 잡힙니다.

아래 C 코드는 메모리 1GiB 를 받은 뒤 조금씩 건드립니다. 1GiB(기비바이트)는 2의 30제곱 바이트입니다. 코드의 1 << 30 이 그 값입니다. 오른쪽 주석은 그 줄을 마친 뒤 상주 집합 크기가 얼마나 늘었는지입니다.

char *p = malloc(1 << 30);  // 거의 0
p[0] = 1;                   // 한 페이지
memset(p, 1, 1 << 30);      // 약 1GiB

malloc 은 주소 공간만 받아 오므로 상주 크기가 거의 안 늡니다. 첫 바이트에 쓰면 그 바이트가 든 페이지 하나만 올라옵니다. memset 이 1GiB 전부에 쓰고 나서야 상주 크기가 1GiB 가까이 늡니다.

그래서 가상 크기가 크다는 것만으로 메모리가 모자란 것은 아닙니다. 메모리 압박을 볼 때는 상주 크기와 페이지 폴트 수를 함께 봅니다.

같은 원리를 쓰는 기능

메모리 매핑은 파일을 주소 공간에 붙여 두고 메모리처럼 읽게 하는 기능입니다. 파일 전체를 미리 읽어 두지 않습니다. 프로그램이 건드린 부분만 페이지 폴트로 디스크에서 올라옵니다.

로더도 같은 원리를 씁니다. 로더는 프로그램을 켤 때 실행 파일을 메모리에 붙여 시작시키는 운영체제 부분입니다. 실행 파일을 통째로 읽지 않고 주소 공간에 붙여만 둡니다. 코드는 처음 실행될 때 한 페이지씩 올라옵니다.

쓰기 시 복사도 페이지 폴트에 일을 미룹니다. 프로세스를 복제하면 부모와 자식이 같은 메모리 내용을 가져야 합니다. 운영체제는 이때 당장 복사하지 않고 두 프로세스가 같은 프레임을 함께 보게 둡니다.

어느 한쪽이 쓰려는 순간 폴트가 납니다. 그때 그 페이지 하나만 복사합니다. 끝까지 아무도 안 쓴 페이지는 한 번도 복사되지 않습니다.

관련 항목

이것이 기대는 메모리 구조

가상 메모리 · 가상 주소 · 물리 메모리 · 주소 공간 · 페이지 · 페이지 프레임 · 페이지 테이블 · MMU · TLB

이것이 거치는 처리 단계

페이지 폴트 · 유효 비트 · 더티 비트 · 페이지 교체 · LRU · 스왑 영역 · 스와핑 · 문맥 교환

이것의 효율을 가르는 성질과 지표

참조 지역성 · 워킹 셋 · 상주 집합 크기 · 메이저 페이지 폴트 · 마이너 페이지 폴트

이것에서 터지는 오류와 장애

스래싱 · 세그멘테이션 폴트 · OOM 킬러 · 메모리 부족

이것과 같은 미루기 원리를 쓰는 기법

지연 로딩 · 지연 평가 · 쓰기 시 복사 · 메모리 매핑 · 메모리 오버커밋

이것을 대신하거나 보태는 적재 방식

선반입 · 사전 페이징 · 오버레이 · 메모리 잠금

이것을 맡아 굴리는 소프트웨어

운영체제 · 커널 · 로더 · 실행 파일 · 메모리 할당기