가상 메모리

가상 메모리는 물리 메모리 크기의 한계를 넘기 위한 기법이다. 예를 들어 100MB 메모리에서 200MB짜리 프로세스를 실행할 수 있게 해 준다. 프로세스의 주소 공간 전체를 올리지 않고 당장 필요한 부분만 메모리에 두고, 나머지는 디스크(backing store, swap area)에 둔다. 대부분의 시스템이 페이징을 쓰므로 여기서도 페이징을 전제로 정리한다. 페이징의 기본 구조는 메모리 관리를, 주소 변환을 실행하는 하드웨어 쪽은 캐시 메모리와 MMU를 참고한다.

가상 메모리가 성립하는 조건

그래서 가상 메모리는 물리 메모리보다 큰 프로그램을 돌리는 것 말고도 여러 이점을 준다. 프로세스마다 0번지부터 시작하는 독립 주소 공간이라 서로를 건드리지 못하고(격리), 여러 페이지 테이블이 같은 프레임을 가리켜 라이브러리·공유 메모리를 나눠 쓰고(공유), malloc한 메모리도 처음 쓸 때에야 프레임을 붙인다(지연 할당).

요구 페이징 (Demand Paging)

프로그램이 실행될 때 모든 페이지를 올리는 대신, 페이지가 요청될 때(demand) 비로소 메모리에 올린다. 프로그램에서 실제로 자주 쓰이는 부분은 매우 제한적이다. 좋은 소프트웨어일수록 예외 처리 같은 방어 코드가 많고, 이런 코드는 거의 실행되지 않는다.

덕분에 I/O와 물리 메모리 사용량이 줄고, 자주 쓰는 정보만 올라가 응답이 빨라지며, 더 많은 프로세스를 동시에 올릴 수 있다.

극단적으로 아무 페이지도 올리지 않은 채 실행부터 시작하는 방식을 순수 요구 페이징(pure demand paging)이라고 한다. 첫 명령어부터 페이지 폴트가 연달아 나다가, 필요한 페이지가 어느 정도 올라오면 폴트 빈도가 떨어진다.

물리 메모리는 한정되어 있으므로 요구 페이징이 안정적으로 돌려면 운영체제가 두 가지를 정해야 한다. 메모리가 찼을 때 어떤 페이지를 내보낼지(페이지 교체)와 프로세스마다 프레임을 몇 개 줄지(프레임 할당)다.

valid / invalid 비트

페이지 테이블의 각 엔트리에는 valid/invalid 비트가 있다.

• 처음에는 모든 엔트리가 invalid로 초기화된다(사용하지 않는 페이지도 엔트리는 만들어진다).
• invalid의 의미: ① 프로그램이 사용하지 않는 주소 영역이거나 ② 페이지가 물리 메모리에 없음(backing store에 있음)
• 페이지가 메모리에 올라오면 엔트리에 프레임 번호를 기록하고 valid로 바꾼다.
• 주소 변환 시 invalid 비트가 세트되어 있으면 페이지 폴트(page fault) 가 발생한다.

페이지 폴트 처리

invalid 페이지에 접근하면 주소 변환 하드웨어(MMU)가 page fault trap을 발생시키고, CPU 제어권이 운영체제로 넘어가 page fault handler가 실행된다.

1. 잘못된 요청(없는 주소, 접근 권한 위반)이면 프로세스를 강제 종료(abort)한다.
2. 정상 요청인데 빈 프레임이 없으면, 메모리에서 페이지 하나를 빼앗는다(페이지 교체).
3. 빈 프레임에 해당 페이지를 디스크에서 읽어 온다. 디스크 I/O는 매우 느리므로
   • 그동안 이 프로세스는 CPU를 반납하고 blocked 된다(다른 프로세스가 CPU 사용).
   • 읽기가 끝나면 페이지 테이블 엔트리에 프레임 번호를 기록하고 valid로 바꾼다.
   • 프로세스를 ready 큐에 넣는다.
4. 프로세스가 다시 CPU를 받으면, 중단되었던 명령어를 처음부터 다시 실행한다.

페이지 폴트와 실효 접근 시간

페이지 폴트율을 p(0 ≤ p ≤ 1)라 하면 메모리 접근 한 번의 실효 접근 시간(EAT)은 다음과 같다.

EAT = (1 − p) × 메모리 접근 시간 + p × 페이지 폴트 처리 시간

폴트 처리 시간에는 트랩, 디스크에서 페이지 읽기, 페이지 테이블 갱신, 명령어 재실행이 모두 들어가고 디스크 읽기가 압도적이다. 메모리 접근 200ns, 폴트 처리 8ms라면 EAT = 200 + p × 7,999,800 (ns)이다. 1,000번에 한 번만 폴트가 나도 EAT가 약 8.2μs로 40배 느려지고, 성능 저하를 10% 안(220ns)으로 묶으려면 폴트를 약 40만 번에 한 번 아래로 줄여야 한다. 폴트율을 낮추는 교체 알고리즘과 프레임 할당이 중요한 이유다.

페이지 교체 (Page Replacement)

빈 프레임이 없을 때 어떤 페이지를 쫓아낼지(victim) 정한다. 곧바로 다시 쓰이지 않을 페이지를 내보내는 것이 좋다. 같은 페이지가 여러 번 쫓겨났다 들어올 수도 있다.

1. victim을 고른다. victim이 메모리에 올라온 뒤 내용이 바뀌었다면 디스크(backing store)에 기록한 뒤 내보내고, 바뀌지 않았다면 그냥 버린다.
2. 쫓겨난 페이지의 엔트리를 invalid로 바꾼다.
3. 새 페이지를 그 프레임에 올리고, 엔트리에 프레임 번호와 valid를 기록한다.

교체 알고리즘의 목표는 페이지 폴트 비율 최소화다. 시간 순서대로 참조된 페이지 번호를 나열한 참조열(reference string) 에 대해 페이지 폴트가 몇 번 나는지로 평가한다. 예: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

참조열에서는 연달아 같은 페이지를 참조한 것은 하나로 줄인다. 첫 참조에서 폴트가 났더라도 바로 다음 참조 때는 이미 올라와 있어 폴트가 날 수 없기 때문이다. CPU가 2 2 2 3 5 5 5 3 3 7 순으로 참조했다면 참조열은 2 3 5 3 7이다.

같은 참조열을 세 알고리즘에 넣어 보면 순위가 그대로 드러난다. 프레임 3개, 참조열 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1(20회)이면 다음과 같다.

Belady's anomaly는 앞의 참조열 1 2 3 4 1 2 5 1 2 3 4 5에서 바로 재현된다. FIFO는 프레임 3개일 때 폴트 9번, 4개일 때 10번이다. 같은 참조열에서 LRU는 10번 → 8번, OPT는 7번 → 6번으로 프레임이 늘면 폴트가 줄어든다. LRU·OPT처럼 프레임 n개일 때 메모리에 있는 페이지 집합이 n+1개일 때의 부분집합이 되는 알고리즘(스택 알고리즘)에는 이 이상 현상이 생기지 않는다.

LRU의 근거와 구현, 약점

LRU는 시간 지역성, 즉 최근에 쓴 것을 곧 다시 쓴다는 성질에 기댄다. 가까운 과거를 가까운 미래의 예측으로 쓰므로, 미래를 보는 OPT에 실용적으로 가장 가깝다.

모든 참조를 소프트웨어가 보는 곳(버퍼 캐시, 웹 캐시, 애플리케이션 캐시)에서는 해시 맵 + 이중 연결 리스트로 조회·갱신·제거를 모두 O(1)에 한다. 해시 맵이 키로 노드를 바로 찾고, 리스트가 최근 순서를 유지한다. 참조되면 노드를 맨 뒤로 옮기고, 가득 차면 맨 앞을 버린다. Java의 LinkedHashMap(접근 순서 모드 + removeEldestEntry)과 Python의 functools.lru_cache가 이 구조다. 직접 구현하는 코드와 LFU 캐시를 O(1)로 만드는 구조는 해시 테이블에 있다. 참조를 일일이 볼 수 없는 페이징과 CPU 캐시는 아래 Clock이나 pseudo-LRU로 근사한다.

Linux는 6.1부터 페이지를 여러 세대로 나눠 나이를 매기는 MGLRU(Multi-Gen LRU)를 선택해서 쓸 수 있다.

위 참조열을 프레임 4개로 OPT에 넣으면 페이지 폴트 6번이며, 어떤 알고리즘도 이보다 적을 수 없다. LRU와 LFU의 차이는 참조 기록 1 1 1 1 2 2 3 3 2 4 뒤에 5를 올릴 때 드러난다. LRU는 네 번이나 쓰인 1을, LFU는 방금 쓰이기 시작한 4를 내보낸다.

다양한 캐싱 환경

교체 알고리즘은 가상 메모리뿐 아니라 캐싱 기법 전반에 쓰인다. 캐싱은 한정된 빠른 공간(캐시)에 요청된 데이터를 저장해 두고, 다음 요청 때 느린 공간까지 가지 않고 캐시에서 바로 서비스하는 방식이다.

교체 알고리즘에 너무 많은 시간을 쓸 수는 없으므로, 버퍼 캐싱이나 웹 캐싱에서도 O(1)~O(log n) 정도까지만 허용된다.

페이징 시스템에서 LRU·LFU를 못 쓰는 이유

프로세스 A가 실행 중일 때 주소 변환은 하드웨어가 한다.

• 페이지가 이미 메모리에 있으면 하드웨어가 바로 변환하므로 운영체제는 참조 사실을 모른다.
• 페이지 폴트가 날 때만 운영체제가 개입하므로, 운영체제는 페이지가 메모리에 올라온 시점만 알 수 있다.

즉 페이징 시스템에서 OS가 가진 정보는 반쪽이라, 참조 시각·횟수가 필요한 LRU·LFU를 그대로 구현할 수 없다. 반면 버퍼 캐시·웹 캐시는 모든 요청이 시스템 콜·소프트웨어를 거치므로 LRU·LFU를 자유롭게 쓸 수 있다(파일 시스템 구현).

Clock 알고리즘

2차 기회(Second Chance) 알고리즘은 FIFO의 약점을 참조 비트로 보완한 변형이다. FIFO처럼 가장 오래된 페이지를 먼저 보되, 참조 비트가 1이면 한 번은 봐준다. 비트를 0으로 바꾸고 방금 들어온 페이지처럼 큐의 맨 뒤로 보낸 뒤 다음 페이지를 본다. 가장 오래 머물렀는데도 참조 비트가 0인 페이지, 즉 올라온 뒤 한 번도 쓰이지 않은 페이지를 내보낸다. 큐 대신 원형 리스트와 시곗바늘로 같은 일을 하면 Clock 알고리즘이다.

Clock은 LRU를 하드웨어 도움으로 근사한다. 페이지가 참조되면 하드웨어가 reference bit를 1로 세운다. 페이지 폴트가 나면 포인터가 원형 리스트를 돌며 1이면 0으로 바꾸고 지나가고(두 번째 기회), 0이면 그 페이지를 내보낸다. "가장 오래전에 참조된" 페이지가 아니라 "오랫동안 참조되지 않은" 페이지를 내보내는 셈이다.

modified(dirty) bit도 함께 본다. 0이면 backing store에 같은 내용이 있어 그냥 버리면 되지만, 1이면 디스크에 먼저 써야 해서 I/O가 생긴다. 그래서 가능하면 modified bit가 0인 페이지를 먼저 내보낸다.

페이지 버퍼링

교체 알고리즘과 함께 쓰여 폴트 처리 시간을 줄이는 보조 기법이다. 빈 프레임이 없을 때 폴트가 나면 victim을 디스크에 쓰고 나서야 새 페이지를 읽을 수 있어 디스크 접근이 두 번 필요하다. 이를 피하는 방법이 셋 있다.

Linux의 kswapd가 여유 메모리가 기준 아래로 떨어지면 미리 페이지를 회수하고, 더티 페이지를 백그라운드에서 내보내는 것이 같은 발상이다.

페이지 프레임 할당 (Allocation)

각 프로세스에 프레임을 몇 개씩 줄 것인가의 문제다. 페이지 폴트가 잦은 원인은 나쁜 교체 알고리즘만이 아니다. 프로세스가 쓸 수 있는 프레임 수 자체가 적으면 폴트가 더 근본적으로 늘어난다. 프레임이 무한하면 모든 페이지가 올라가 있어 폴트가 거의 없고, 프레임이 하나뿐이면 다른 페이지를 참조할 때마다 폴트가 난다.

명령어 하나도 명령어·데이터 등 여러 페이지를 함께 참조하므로 최소 프레임 수가 있다. 반복문의 페이지들이 한꺼번에 올라와 있지 않으면 반복마다 페이지 폴트가 난다.

균등 할당은 크기가 큰 게임과 작은 메모장에 같은 수를 주므로 비합리적이다. 비례 할당도 완벽하지 않다. 크기가 커도 실행해 보면 프레임이 많이 필요 없거나, 작아도 많이 필요한 프로세스가 있다. 필요한 프레임 수는 실행해 봐야 안다.

전역 교체 vs 지역 교체

현대 시스템은 두 방식을 적절히 섞어 쓴다.

스래싱 (Thrashing)

메모리에 올라간 프로세스 수(멀티프로그래밍 정도, degree of multiprogramming)에 따른 CPU 이용률을 보면:

1. 처음에는 프로세스가 늘수록 CPU 이용률이 오른다. 한 프로세스가 I/O를 하러 가도 다른 프로세스가 CPU를 쓰기 때문이다.
2. 어느 지점을 넘으면 각 프로세스가 받는 프레임이 너무 적어져, 모든 프로세스에서 페이지 폴트가 계속 발생한다.
3. 모두 디스크 I/O를 기다리느라 CPU 이용률이 급격히 떨어진다.
4. 운영체제는 CPU가 놀고 있으니 프로세스를 더 올리고, 상황은 더 나빠진다. 프로세스들이 swap in/out만 반복하며 실제 일은 거의 못 한다.

이것이 스래싱이다. 즉 프로세스가 실제로 실행하는 시간보다 페이지 교체에 더 많은 시간을 쓰는 상태다. 근본 원인은 각 프로세스가 무리 없이 실행되는 데 필요한 최소 프레임 수가 보장되지 않은 것이다. 10개가 필요한 프로세스에 5개만 주면 폴트가 끊이지 않는다. 해결하려면 운영체제가 프로세스마다 필요한 프레임 수를 파악해 그만큼은 보장하고, 멀티프로그래밍 정도를 조절해야 한다.

Working-Set 알고리즘

• 참조 지역성(locality of reference): 프로세스는 특정 시간에는 특정 메모리 영역만 집중적으로 참조한다. 예: 한 함수가 실행 중이면 그 함수를 이루는 페이지만 집중 참조. 이렇게 집중 참조되는 페이지 집합을 locality set, Working-Set 모델에서는 working set이라고 한다.
• 프로세스의 working set 전체가 한꺼번에 메모리에 올라와 있어야 페이지 폴트가 줄어든다. 올라갈 수 없다면(예: 5개 필요한데 3개만 남음) 그 프로세스의 메모리를 모두 반납하고 swap out 한다.
• working set은 미리 알 수 없으므로 과거 Δ시간(window) 동안 참조된 페이지들을 working set으로 간주해 메모리에 유지하고, 나머지는 버린다.

예: window 크기가 10이면 최근 10번의 참조에서 중복을 뺀 페이지들, 예컨대 {1, 2, 5, 6, 7}이 working set이다. 5개 프레임을 줄 수 있으면 이들을 올리고, 줄 수 없으면 프로세스를 swap out 한다. working set은 시간에 따라 변한다(t1에는 {1, 2, 5, 6, 7}, t2에는 {3, 4}).

• 모든 프로세스의 working set 크기 합이 프레임 수보다 크면, 일부 프로세스를 swap out 해 남은 프로세스의 working set을 우선 보장한다.
• working set을 다 주고도 프레임이 남으면, swap out 되었던 프로세스에게 working set을 할당한다.

모든 프로세스의 working set 크기 합을 D = Σ WSSᵢ라 하면, D가 전체 프레임 수보다 커지는 순간 스래싱이 시작된다. Working-Set 모델의 약점은 매 참조마다 창을 밀며 집합을 추적하는 비용이 크고, Δ를 정하기 어렵다는 것이다. Δ가 너무 작으면 지역성 하나를 다 담지 못하고, 너무 크면 여러 지역성이 겹쳐 프레임을 과하게 잡는다. 그래서 실제로는 참조 비트를 주기적으로 훑어 근사하거나, 아래 PFF처럼 결과(폴트율)를 직접 보는 방식을 쓴다.

PFF (Page-Fault Frequency)

현재 시점의 페이지 폴트율을 직접 측정해 프레임 수를 조절한다.

• 페이지 폴트율의 상한과 하한을 정한다.
• 상한을 넘으면 프레임을 더 할당하고, 하한보다 낮으면 할당 프레임을 줄인다.
• 빈 프레임이 없으면 일부 프로세스를 통째로 swap out 한다.

페이지 크기의 결정

페이지를 키우면 폴트 한 번에 더 많이 올리므로 순차 접근에서는 폴트 횟수가 줄어든다. 그러나 물리 메모리 양이 같으면 프레임 수가 줄어든다. 실제로 쓰는 데이터가 여러 페이지에 드문드문 흩어져 있으면 쓰지도 않는 부분까지 올리느라 working set을 다 담지 못해 폴트가 오히려 늘 수 있고, 내부 단편화도 커진다. 그래서 큰 페이지는 대용량 연속 데이터(DB 버퍼 풀, JVM 힙)에 골라 쓴다.

메모리 용량이 커지면서 페이지 크기를 키우는 쪽으로 가고 있다. x86-64의 기본 페이지는 4KB지만, 메모리를 많이 쓰는 프로그램은 2MB·1GB huge page를 함께 써서 TLB 항목 하나로 더 넓은 영역을 커버한다. Apple 실리콘의 macOS·iOS는 16KB 페이지를 쓰고, 안드로이드도 16KB 페이지로 옮겨 가고 있다. Google Play는 2025년 11월부터 Android 15 이상을 대상으로 하는 앱에 16KB 페이지 지원을 요구한다.

그 밖의 고려 사항

핵심 정리

• 요구 페이징: 필요한 페이지만 올리고, invalid 페이지 접근 시 페이지 폴트 → OS가 디스크에서 읽어 옴.
• OPT는 최적이지만 오프라인, FIFO는 Belady's anomaly, LRU는 최근성, LFU는 빈도 기준.
• 페이징 시스템의 OS는 참조 정보를 반쪽만 알아서 LRU 대신 Clock 알고리즘(reference bit)을 쓴다.
• 스래싱은 프로세스가 너무 많아 프레임이 부족할 때 생기며, Working Set·PFF로 멀티프로그래밍 정도를 조절해 막는다.

관련 노트: 메모리 관리, 캐시 메모리와 MMU, 파일 시스템 구현