테마
요구 페이징과 페이지 교체
가상 메모리(virtual memory)를 쓰면 프로그램의 모든 페이지(page)가 한꺼번에 물리 메모리(physical memory)에 있을 필요가 없다. 실제로 접근하는 순간에만 페이지를 디스크에서 올리는 방식을 요구 페이징(demand paging)이라고 하고, 메모리에 없는 페이지에 접근해 운영체제가 끼어드는 사건을 페이지 폴트(page fault)라고 한다. 메모리가 가득 차면 누군가를 내보내야 하는데, 무엇을 내보내느냐에 따라 폴트 횟수가 크게 달라진다. 이 선택 규칙이 페이지 교체 알고리즘(page replacement algorithm)이다.
요구 페이징: 쓸 때만 올린다
프로그램을 실행할 때 모든 페이지를 미리 올리면 시작이 느리고, 한 번도 쓰지 않을 코드와 데이터까지 메모리를 차지한다. 요구 페이징은 페이지 테이블(page table)의 항목만 만들어 두고 "아직 메모리에 없음"으로 표시한 채 시작한다. 그러면 프로그램이 빨리 뜨고, 같은 메모리에 더 많은 프로세스(process)를 올릴 수 있으며, 물리 메모리보다 큰 프로그램도 실행할 수 있다.
대가는 첫 접근마다 치르는 페이지 폴트다. 디스크 읽기는 메모리 읽기보다 몇 자릿수나 느리므로, 폴트가 드물게 일어나야만 이 방식이 이득이다. 다행히 프로그램은 최근에 쓴 곳과 그 근처를 반복해 쓰는 지역성(locality)이 강해서 대부분의 접근은 이미 올라온 페이지에서 끝난다.
페이지 폴트가 처리되는 흐름
- 프로세스가 어떤 주소에 접근하면 MMU(Memory Management Unit, 메모리 관리 장치)가 그 페이지의 PTE(Page Table Entry, 페이지 테이블 항목)를 본다. 유효 비트(valid bit)가 꺼져 있으면 변환을 멈추고 커널(kernel)로 제어를 넘긴다.
- 커널은 그 주소가 프로세스가 원래 쓸 수 있는 영역인지 확인한다. 아예 잘못된 주소라면 잘못된 메모리 접근 오류(segmentation fault)로 프로세스를 끝낸다.
- 올바른 주소라면 빈 페이지 프레임(page frame)을 찾는다. 빈 프레임이 없으면 교체 알고리즘으로 내보낼 페이지를 고른다. 그 페이지의 수정 비트(dirty bit)가 켜져 있으면 바뀐 내용을 먼저 디스크에 쓴다.
- 필요한 페이지를 디스크에서 프레임으로 읽어 온다. 읽는 동안 이 프로세스는 대기 상태가 되고, CPU는 다른 프로세스를 실행한다.
- 읽기가 끝나면 PTE에 프레임 번호를 적고 유효 비트를 켠다.
- 폴트를 일으킨 명령어를 처음부터 다시 실행한다. 이번에는 변환이 성공한다.
쓰기 시 복사
같은 원리로 복사를 미루는 기법이 쓰기 시 복사(copy-on-write)다. fork()로 자식 프로세스를 만들면 부모의 메모리를 바로 복사하지 않고, 부모와 자식의 페이지 테이블이 같은 프레임을 가리키게 하되 둘 다 읽기 전용으로 표시한다. 어느 한쪽이 그 페이지에 쓰려고 하면 읽기 전용 페이지에 쓰려 한 보호 위반이라 폴트가 나고, 커널은 그때서야 그 페이지 하나만 복사해 쓰기를 허용한다. fork() 직후 exec()로 다른 프로그램을 실행하는 흔한 경우에는 복사가 거의 일어나지 않아 비용이 크게 준다.
페이지 교체 알고리즘
빈 프레임이 없을 때 내보낼 페이지를 희생 페이지(victim page)라고 한다. 앞으로 오래 쓰지 않을 페이지를 골라야 폴트가 줄어든다. 알고리즘은 접근한 페이지 번호를 차례로 늘어놓은 참조열(reference string)로 비교한다.
- FIFO(First In First Out, 선입선출)는 가장 먼저 들어온 페이지를 내보낸다. 구현은 쉽지만, 오래전에 올라왔어도 계속 쓰는 페이지를 쫓아낼 수 있다.
- 최적(OPT, optimal) 교체는 앞으로 가장 오랫동안 쓰이지 않을 페이지를 내보낸다. 폴트 수가 이론상 최소이지만 미래의 참조를 알아야 하므로 실제로는 구현할 수 없다. 다른 알고리즘이 얼마나 좋은지 재는 기준선으로 쓴다.
- LRU(Least Recently Used, 최근 최소 사용)는 가장 오랫동안 쓰이지 않은 페이지를 내보낸다. "최근에 안 쓴 것은 앞으로도 안 쓸 것"이라는 지역성 가정으로 과거를 보고 미래를 추측한다.
프레임 3개로 참조열 1 2 3 1 4 1 2 5를 처리하면 다음과 같다. F는 폴트, ·는 이미 메모리에 있어 폴트가 없는 경우이고, 괄호 안은 그때 내보낸 페이지다.
| 참조 | 1 | 2 | 3 | 1 | 4 | 1 | 2 | 5 | 합계 |
|---|---|---|---|---|---|---|---|---|---|
| FIFO | F | F | F | · | F(1) | F(2) | F(3) | F(4) | 7 |
| LRU | F | F | F | · | F(2) | · | F(3) | F(4) | 6 |
| OPT | F | F | F | · | F(3) | · | · | F | 5 |
차이는 네 번째 참조 뒤에 4가 들어올 때 갈린다. FIFO는 가장 먼저 온 1을 내보냈다가 바로 다음에 1을 다시 부른다. LRU는 방금 쓴 1을 지키고 가장 오래 안 쓴 2를 내보낸다. OPT는 앞으로 다시 안 쓰일 3을 내보내 폴트를 가장 적게 낸다. 마지막 5가 들어올 때는 남은 1·2·4가 모두 다시 쓰이지 않으므로, OPT는 셋 중 아무것이나 내보내도 된다.
이어지는 내용은 요구 페이징과 페이지 교체 2에서 다룬다.
면접 포인트
- "요구 페이징을 왜 쓰나요?" → 빠른 시작, 같은 메모리에 더 많은 프로세스, 물리 메모리보다 큰 프로그램. 대가는 첫 접근마다의 폴트지만 지역성 덕분에 드물다.
- "페이지 폴트가 나면 무슨 일이 일어나나요?" → MMU가 유효 비트 꺼짐 확인 → 커널 진입 → 빈 프레임 확보(없으면 교체, 수정됐으면 디스크에 기록) → 디스크에서 읽기(프로세스 대기) → PTE 갱신 → 명령어 재실행.
- "쓰기 시 복사란?" →
fork()때 페이지를 읽기 전용으로 공유하다가, 한쪽이 쓰려는 순간 그 페이지만 복사한다. - "FIFO·LRU·OPT의 차이는?" → 가장 먼저 들어온 것, 가장 오래 안 쓴 것, 앞으로 가장 오래 안 쓸 것을 내보낸다.
- OPT는 최소 폴트지만 미래를 알아야 해서 구현할 수 없다. "가장 좋은 알고리즘은 OPT"라고만 답하면 부족하다.