yeolyi.com성열의 컴퓨터공학

페이지 교체

초안아직 검토하지 않은 글이라 틀린 곳이 있을 수 있습니다.

가상 메모리는 프로세스의 페이지를 RAM의 프레임에 대응시킵니다. 그런데 프로세스들의 페이지를 모두 합치면 RAM보다 클 수 있습니다. 프레임이 모자라면 어떻게 할까요?

메모리 계층 글에서 본 것처럼 RAM 아래에는 느리지만 큰 디스크가 있습니다. 당장 쓰지 않는 페이지는 디스크에 내려 두고, RAM에는 지금 쓰는 페이지만 올려 두면 됩니다. 페이지 테이블에는 페이지가 RAM과 디스크 중 어디에 있는지도 적어 둡니다.

페이지 폴트

디스크에 있는 페이지에 접근하면 MMU는 주소를 바꿀 수 없어 운영체제에 넘깁니다. 이를 페이지 폴트(page fault)라 합니다. 운영체제는 디스크에서 페이지를 읽어 빈 프레임에 올리고 페이지 테이블을 고친 뒤 멈췄던 명령어를 다시 실행합니다.

프로세스는 페이지 폴트가 일어난 줄 모릅니다. 다만 디스크 접근은 수십만 사이클 이상 걸리니 페이지 폴트는 적을수록 좋습니다.

빈 프레임이 없으면 올라와 있는 페이지 하나를 디스크로 내보내고 그 자리를 씁니다. 이것이 페이지 교체(page replacement)입니다. 무엇을 내보낼지는 캐시가 가득 찼을 때와 같은 문제입니다. 여기서는 RAM이 디스크의 캐시입니다.

무엇을 내보낼까

페이지 참조 순서 (0~9)
프레임 수
FIFO페이지 폴트 0번
7
0
1
2
0
3
0
4
2
3
0
3
2

아직 참조하지 않았습니다.

LRU페이지 폴트 0번
7
0
1
2
0
3
0
4
2
3
0
3
2

아직 참조하지 않았습니다.

OPT페이지 폴트 0번
7
0
1
2
0
3
0
4
2
3
0
3
2

아직 참조하지 않았습니다.

  1. 다음을 여섯 번 눌러 봅시다.
  2. 재생을 눌러 세 방법의 페이지 폴트 수를 비교해 봅시다.

여섯 번째 참조에서 FIFO는 방금 쓴 0을 내보내고, 바로 다음 참조에서 0을 다시 올립니다. 0이 가장 먼저 들어왔다는 것만 보기 때문입니다.

OPT는 가장 좋지만 운영체제는 미래를 알 수 없어 쓸 수 없고, 다른 방법을 재는 기준으로만 씁니다. LRU는 미래 대신 과거를 봅니다. 오래 안 쓴 페이지는 앞으로도 안 쓸 거라는 추측이 지역성 덕분에 대개 맞아, LRU는 OPT에 꽤 가깝습니다.

마무리

이번 파트에서는 프로세스의 메모리 공간을 구역으로 나눠 쓰고, 힙을 빌리고 돌려주고, 버퍼가 넘치면 무엇이 망가지는지 보았습니다. 그리고 가상 메모리로 프로세스마다 제 메모리가 있는 것처럼 보이게 하고, 모자란 RAM은 디스크로 메웠습니다. 그런데 프로세스는 PC가 하나라 한 번에 한 가지 일만 따라갑니다. 그래서 다음 파트에서는 한 프로그램이 여러 일을 함께 하는 법, 동시성을 다룹니다. 첫 글은 스레드입니다.

도전 문제

프레임을 하나 늘렸을 때, 어떤 참조 순서에서든 페이지 폴트가 늘지 않는 방법을 모두 고른 것은 무엇일까요?