#17 가상메모리와 요구 페이징, 페이지 교체

프로세스 전체를 안 올려도 실행이 된다고? — 가상메모리와 요구 페이징

가상메모리가 실제로 뭘 해결하는 기술인지, 요구 페이징이 어떻게 필요한 것만 골라서 올리는지, 페이지 폴트가 터지면 내부에서 정확히 무슨 일이 일어나는지, 그리고 메모리가 꽉 찼을 때 어떤 페이지를 빼낼지 정하는 알고리즘들까지 알아보자!

지금까지 주소 변환, 세그멘테이션, 페이징, TLB, Multi-level Page Table을 쭉 봐왔는데, 이 모든 걸 관통하는 마지막 조각이 바로 가상메모리야. 지금까지는 "필요한 페이지는 항상 메모리에 있다"고 가정했는데, 이제 그 가정을 깰 차례야.

프로세스 전체는커녕, 지금 당장 필요한 부분만 메모리에 올려놓고 나머지는 디스크에 던져놓은 채로도 프로그램이 잘 돌아가.

---

가상메모리가 뭐야

실제 물리 메모리보다 더 커 보이게 만드는 기술이야. 핵심 아이디어는 단순해 — 프로세스가 실행되려면 전체가 메모리에 올라가 있을 필요가 없다는 거야. 지금 실행 중인 코드가 참조하는 부분만 메모리에 있으면 충분하고, 나머지는 디스크에 그대로 둬도 돼. 이게 가능한 이유가 바로 참조 지역성이야 — 프로그램은 특정 시점에 전체 주소 공간의 아주 일부분만 집중적으로 건드리거든.

램이랑 디스크를 하나의 추상화된 메모리 공간처럼 묶어서 제공한다고 보면 돼. OS는 논리 주소 공간에서 지금 필요한 부분만 실제 메모리에 올려놓고, 나머지는 디스크에 남겨둬.

 

왜 이런 게 필요했을까

초창기엔 프로그램이 메모리를 점유하다 비정상 종료되면 시스템 전체가 흔들리는 문제가 있었어. 프로세스가 쓸 수 있는 공간을 가상의 영역으로 딱 제한해두면 이런 문제에서 시스템을 지킬 수 있어. 여기에 더해서, 실제 물리 메모리보다 더 큰 프로그램을 돌리고 싶은 요구도 있었고.

 

장점

• 프로그램이 실제 물리 메모리 크기에 제한받지 않아
• 프로세스 전체가 메모리에 안 올라가도 되니까, 더 많은 프로그램을 동시에 띄울 수 있어서 CPU 이용률이랑 처리율이 올라가
• 프로세스 전체를 스왑하는(swap) 방식보다 필요한 페이지만 오가니까, 스왑에 드는 입출력 자체가 줄어들어

---

가상 주소 공간

사용자·프로세스 입장에서 보는 논리적인 메모리 공간이야. 항상 0번지부터 시작하고, 실제 물리 주소로는 MMU가 변환해줘.

가상메모리를 구현하는 핵심 기술 두 가지가 있어.

• 요구 페이징(Demand Paging): 스왑됐던 페이지를 필요할 때만 메모리에 적재해
• 페이지 교체(Page Replacement): 메모리가 부족하면 기존 페이지를 스왑해서 자리를 비워

---

요구 페이징이 뭐야

논리 주소 공간의 각 페이지를 실제로 필요할 때만 메모리에 올리는 방식이야. 당장 안 쓰는 페이지는 스왑 공간(디스크)에 그대로 둬. 이러면 물리 메모리를 아낄 수 있고, 프로세스를 시작할 때 전체를 한 번에 올리지 않아도 되니까 스왑 시간도 줄어.

문제는 이제 각 페이지가 "메모리에 있는지, 스왑 공간에 있는지" 구분할 방법이 필요하다는 거야. 이걸 표시하는 게 valid/invalid bit이야.

• valid: 페이지가 지금 메모리에 있는 상태
• invalid: 페이지가 스왑 공간에 있는 상태

만약 프로세스가 invalid 상태인 페이지를 참조하면, OS가 인터럽트로 페이지 폴트 트랩을 발생시키고, 스왑 공간에서 그 페이지를 메모리로 가져오는 I/O를 시작해. 이 I/O가 끝날 때까지 해당 프로세스는 대기 상태로 들어가.

---

페이지 폴트, 내부에서 정확히 무슨 일이 벌어질까

중요한 포인트 하나: 6단계 마지막에서 프로세스는 원래 실패했던 그 명령어를 처음부터 다시 실행해. 페이지가 이제 메모리에 올라와 있으니까, 이번엔 valid 상태라서 그대로 통과되는 거야.

---

페이지 폴트, 실제로 얼마나 느려질까

 

전체 정보가 다 메모리에 있을 때랑 비교해서, 페이지 폴트가 섞이면 접근 시간이 느려져.

얼마나 느려지는지는 페이지 폴트율에 크게 좌우돼.

 

여기서 숫자를 좀 더 정확히 짚고 가면 좋을 것 같아.

페이지 폴트 하나가 발생했을 때 걸리는 시간은 "10배 정도" 수준이 아니야. 메모리 접근은 보통 수백 나노초(ns) 단위인데, 디스크에서 페이지를 읽어오는 건 밀리초(ms) 단위야 — 자릿수로 치면 수만 배에서 수십만 배 차이가 나. 그래서 페이지 폴트가 조금만 자주 일어나도 전체 성능은 순식간에 무너져.

이걸 숫자로 보면 감이 와. 메모리 접근이 200ns, 페이지 폴트 처리가 8ms(=8,000,000ns)라고 해보자. 전체 접근 시간(EAT)이 원래보다 딱 10%만 느려지게 하려면, 페이지 폴트율은 대략 0.0000025(백만 번 중 2~3번) 수준까지 낮아야 해. 그만큼 페이지 폴트는 자주 나면 절대 안 되는 이벤트야.

다행히 프로세스가 실제로 메모리를 참조하는 패턴은 참조 지역성 덕분에 아주 좁은 범위에 몰려있어. 그래서 실제로는 가상 메모리 때문에 생기는 성능 저하가 이론상 최악의 경우보다 훨씬 드물게 일어나.

 

성능을 위해 챙기는 것들

• 스왑 공간을 빠르게: 스왑 공간은 일반 파일 I/O보다 빠르게 설계돼. 한 번에 큰 단위(block)로 입출력하고, 파일 검색이나 간접 할당(indirect block) 같은 파일시스템 오버헤드를 아예 안 써
• 실행 파일은 스왑 안 해도 됨: 프로그램의 실행 코드 영역은 read-only라서 내용이 바뀔 일이 없어. 그래서 이 페이지가 메모리에서 밀려나도 스왑 공간에 따로 쓸 필요 없이, 원래 실행 파일에서 다시 읽어오면 그만이야
• 페이지 폴트 자체를 줄이기: 이건 프로세스의 접근 패턴에 크게 의존하는 부분이라 OS가 마음대로 통제할 수 있는 영역이 아니야. 대신 OS가 손댈 수 있는 건 페이지 교체 알고리즘 쪽이야

---

메모리가 꽉 찼을 때: 페이지 교체

물리 메모리 전체가 이미 다른 프로세스들에 할당돼있고, 요구 페이징을 처리할 빈 프레임이 하나도 없는 상태를 메모리 과할당이라고 해. 이 상태를 풀어내는 방법은 세 가지가 있어.

• 프로세스 종료: 가장 간단하지만, 메모리가 부족하다고 프로세스를 죽여버리는 건 메모리 관리 서비스가 원래 하려던 일에 어긋나
• 프로세스 전체 스와핑: 프로세스 하나를 통째로 디스크로 내보내는 건데, 다시 메모리에 올릴 때 비용이 커서 결국 동시에 돌아가는 프로세스 수(멀티프로그래밍 정도)를 낮추는 셈이 돼
• 일부 페이지만 스와핑(페이지 교체): 이게 요구 페이징이 정상적으로 굴러가려면 반드시 필요한 방식이야

---

페이지 교체 알고리즘

프레임 할당 알고리즘이랑 더불어 요구 페이징에서 가장 핵심적인 문제야. 목표는 하나, 페이지 폴트를 최소화하는 것.

 

FIFO(First In First Out)

메모리에 가장 먼저 들어온 page를 내보내. Queue로 관리하면 되니까 구현이 제일 간단해. 근데 성능을 전혀 보장 못 해 — 심지어 프레임 수를 늘렸는데 오히려 페이지 폴트가 더 늘어나는 Belady의 모순이 생길 수도 있어.

 

OPT(Optimal Page Replacement)

앞으로 가장 오랫동안 사용되지 않을 page를 내보내는 방식이야. Belady의 모순이 안 생기고, 페이지 부재율도 최소로 만들 수 있어. 근데 문제는 실제로 구현이 불가능하다는 거야 — 미래에 어떤 page가 언제 다시 쓰일지 미리 알아야 하니까. 그래서 실제 시스템에 쓰이는 게 아니라, 다른 알고리즘들의 성능이 얼마나 최적에 가까운지 비교하는 기준선으로만 쓰여. 미리 주어진 참조열이랑 프레임 수를 놓고 계산으로만 확인할 수 있어.

 

LRU(Least Recently Used)

OPT를 흉내 내는 현실적인 방법이야. 과거의 참조 이력을 기반으로, 가장 오래 안 쓴 page를 내보내. 이걸 구현하려면 몇 가지가 필요해.

• page별 참조 이력(언제 쓰였는지에 대한 시간 정보 기록)을 확인할 수 있어야 해
• 모든 메모리 참조마다 참조 시간을 갱신할 하드웨어 지원이 필요해
• 실제로는 스택 구조로 많이 구현해. 가장 최근에 참조된 page가 스택 맨 위로 올라가고, 교체 대상은 항상 스택 맨 아래(가장 오래 안 쓴 것)가 돼

Counting 기반 (LFU / MFU)

각 page의 참조 횟수를 세는 방식이야. 실제 구현이 까다롭고 최적 알고리즘에 근사하기도 어려워서 잘 안 쓰이는 편이지만, 개념은 알아둘 만해.

• LFU(Least Frequently Used): 참조 횟수가 가장 적은 page를 내보내
• MFU(Most Frequently Used): 반대로 참조 횟수가 가장 많은 page를 내보내

 

 

면접 포인트 ( •̀ ω •́ )✧

Q. 요구 페이징에서 페이지 폴트가 발생하면 어떤 과정을 거치는지 설명해 주세요.

프로세스가 참조한 페이지가 Page Table에 invalid로 표시돼 있으면 페이지 폴트 트랩이 발생해서 제어권이 운영체제로 넘어갑니다. 운영체제는 스왑 공간에서 해당 페이지의 위치를 확인하고 I/O를 시작해서 빈 프레임에 페이지를 적재합니다. 그 다음 Page Table을 invalid에서 valid로 갱신하고, 실패했던 명령어를 처음부터 다시 실행시켜서 프로세스를 재개합니다.

Q. FIFO, OPT, LRU 페이지 교체 알고리즘의 차이를 설명해 주세요.

FIFO는 가장 먼저 들어온 페이지를 교체하는 가장 단순한 방식인데, 프레임을 늘려도 폴트가 늘어나는 Belady의 모순이 발생할 수 있습니다. OPT는 앞으로 가장 오랫동안 안 쓰일 페이지를 교체해서 이론적으로 최적의 폴트율을 보장하지만, 미래 참조를 알아야 해서 실제 구현이 불가능하고 다른 알고리즘의 성능 비교 기준으로만 쓰입니다. LRU는 OPT를 현실적으로 흉내 낸 방식으로, 과거 참조 이력을 근거로 가장 오래 안 쓴 페이지를 교체합니다.

---

주소 변환부터 시작해서 세그멘테이션, 페이징, TLB, Multi-level Page Table을 거쳐 여기까지 왔네.

정리하면 이런 흐름이었어.

주소 변환이 가상 주소와 물리 주소를 잇는 기본 메커니즘을 만들었고,
세그멘테이션과 페이징이 그 메커니즘을 효율적으로 구현하는 방법을 다퉜고,
TLB가 그 변환 과정의 속도를 잡았고,
Multi-level Page Table이 그 과정에 드는 공간을 줄였어.
그리고 마지막으로 가상메모리는 이 모든 걸 딛고서 "메모리보다 큰 프로세스도 돌아가게 만든다"는, 애초에 이 전체 메커니즘이 존재하는 이유 그 자체로 돌아온 셈이야.

이 글에서 꼭 기억할 것 하나만 꼽자면 페이지 교체 알고리즘은 전부 다 "OPT를 어떻게든 흉내 내보려는 시도"야. LRU가 그나마 제일 근접한 현실적 답이고, 이게 대부분의 실제 OS에서 기본 전략으로 쓰이는 이유이기도 해. 여기까지 오면 OS 메모리 관리 파트는 한 바퀴 돈 거야 — 수고했어.