1. 운영체제는 참조를 보지 못합니다
LRU는 "가장 오래 전에 참조된 페이지"를, LFU는 "참조 횟수가 가장 적은 페이지"를 쫓아냅니다. 둘 다 각 페이지가 언제, 몇 번 참조됐는지를 알아야 합니다.
문제는 운영체제가 그 정보를 가질 수 없다는 것입니다. 페이지가 이미 메모리에 있으면 주소 변환은 하드웨어가 처리하고 끝납니다. 운영체제는 CPU를 얻지 못하므로 그 참조가 일어났다는 사실 자체를 모릅니다. page fault가 났을 때만 개입할 수 있는데, 그때 알 수 있는 것은 "지금 이 페이지가 없다"는 사실뿐입니다.
즉 페이징 시스템에서 순수한 LRU와 LFU는 구현할 수 없습니다. 버퍼 캐시나 웹 캐시처럼 소프트웨어가 모든 접근을 거치는 곳에서는 쓸 수 있지만, 페이지 교체에는 근사 알고리즘이 필요합니다.
2. Clock 알고리즘
그래서 하드웨어가 아주 작은 힌트만 남겨 줍니다. 페이지 테이블 항목의 비트 두 개입니다.
- reference bit: 그 페이지가 참조되면 하드웨어가 1로 바꿉니다
- modified bit (dirty bit): 그 페이지의 내용이 변경되면 1로 바꿉니다
Clock 알고리즘은 이 reference bit만 보고 동작합니다. 프레임들을 원형으로 늘어놓고 포인터를 돌립니다.
reference bit이 1이면 "최근에 쓰였구나" 하고 0으로 바꾼 뒤 넘어갑니다. 한 번 더 기회를 주는 셈이라 second chance 알고리즘이라고도 합니다. 포인터가 한 바퀴 돌아 다시 왔을 때도 0이라면, 그 사이에 한 번도 참조되지 않았다는 뜻이므로 교체합니다. 자주 쓰이는 페이지는 포인터가 올 때마다 비트가 1이라 계속 살아남습니다.
modified bit을 함께 보면 더 개선됩니다. 이 비트가 1인 페이지는 내용이 바뀌었으므로 쫓아낼 때 디스크에 써야 합니다. 비용이 크므로 같은 조건이면 modified bit이 0인 페이지를 먼저 내보냅니다.
NUR(Not Used Recently), NRU(Not Recently Used)라는 이름으로도 불립니다.
3. 프레임을 몇 개나 줄 것인가
교체 알고리즘과 별개로, 각 프로세스에 프레임을 몇 개 배정할지 정해야 합니다. 너무 적게 주면 명령 하나를 수행하는 동안에도 page fault가 반복됩니다.
| 방식 | 기준 | 문제 |
|---|---|---|
| equal allocation | 모든 프로세스에 똑같이 | 크기 차이를 무시함 |
| proportional allocation | 프로세스 크기에 비례해서 | 실제 사용량과 크기가 다를 수 있음 |
| priority allocation | 우선순위가 높은 쪽에 더 많이 | 우선순위 기준이 필요함 |
작은 예제
가용 프레임이 62개이고 P1은 10페이지, P2는 127페이지입니다.
- equal allocation: 31개씩 줍니다. P1은 10페이지뿐이라 21개가 놀고, P2는 127페이지인데 31개라 턱없이 모자랍니다
- proportional allocation: P1에게 10 ÷ 137 × 62 ≈ 4개, P2에게 127 ÷ 137 × 62 ≈ 57개를 줍니다
쫓아낼 페이지를 어디서 고르느냐도 갈립니다.
| 구분 | global replacement | local replacement |
|---|---|---|
| 교체 대상 | 전체 프레임에서 고름 | 자기에게 할당된 프레임 안에서만 고름 |
| 할당량 | 실행 중에 바뀜 | 고정 |
| 특징 | 다른 프로세스의 페이지를 뺏을 수 있음 | 프로세스별로 성능이 독립적 |
4. Thrashing
프로세스에 프레임이 충분하지 않으면 심각한 일이 벌어집니다.
- 프레임이 모자라 page fault가 자주 납니다
- page fault 처리는 디스크 입출력이므로 그 프로세스는 Blocked가 됩니다
- CPU가 놀기 시작합니다
- 운영체제는 "CPU 이용률이 낮으니 프로세스를 더 올리자"고 판단합니다
- 프로세스가 늘어 프레임이 더 모자라집니다. 1번으로 돌아갑니다
이 악순환을 쓰래싱(thrashing)이라고 합니다. 시스템이 일은 거의 못 하고 페이지를 올렸다 내렸다 하는 데만 시간을 씁니다.
가로축은 동시에 올라간 프로세스 수, 세로축은 CPU 이용률입니다. 어느 지점까지는 프로세스를 늘릴수록 CPU가 바빠지지만, 임계점을 넘으면 급격히 떨어집니다.
5. Working set과 PFF
해법은 "각 프로세스가 지금 실제로 필요로 하는 만큼은 보장해 주자"입니다.
근거는 참조 지역성(locality of reference)입니다. 프로그램은 특정 시점에 주소 공간의 일부 집중적으로 참조합니다. 그 집합을 locality set이라 하고, 이를 일정 기간 동안의 참조로 추정한 것이 working set입니다.
추정 방법은 단순합니다. window size(Δ)를 정하고, 최근 Δ번의 참조에 등장한 페이지들을 working set으로 봅니다.
작은 예제
Δ = 4이고 참조열이 1 2 3 1 2 4 5 5 5입니다.
| 시점 | 최근 4번의 참조 | working set | 크기 |
|---|---|---|---|
| 4번째 | 1, 2, 3, 1 | {1, 2, 3} | 3 |
| 6번째 | 3, 1, 2, 4 | {1, 2, 3, 4} | 4 |
| 9번째 | 4, 5, 5, 5 | {4, 5} | 2 |
필요한 프레임 수가 시점마다 달라집니다. working set 알고리즘은 이 크기만큼 프레임을 주고, 그만큼도 줄 수 없으면 그 프로세스를 통째로 swap out해서 suspended 상태로 만듭니다. 어설프게 조금 주는 것보다 아예 빼는 편이 전체에 이롭기 때문입니다.
PFF(Page Fault Frequency)는 다른 접근입니다. 각 프로세스의 page fault rate를 직접 보면서, 상한선을 넘으면 프레임을 더 주고 하한선 아래로 내려가면 프레임을 뺏습니다. 줄 프레임이 없으면 역시 swap out합니다.
6. 페이지 크기
페이지를 작게 하면 어떤 일이 생기는지 한꺼번에 봐야 합니다.
- 페이지 수가 늘어 페이지 테이블이 커집니다
- 내부 조각이 줄어듭니다. 낭비되는 자투리가 작아집니다
- 디스크 입출력 효율이 나빠집니다. 디스크는 한 번에 많이 읽을수록 유리합니다
- 필요한 정보만 정확히 올릴 수 있어 메모리 이용은 효율적이 됩니다
장단이 엇갈리므로 어느 쪽도 공짜가 아닙니다. 다만 메모리가 커지고 디스크 전송량이 중요해지면서, 내부 조각을 감수하더라도 페이지를 크게 하는 쪽으로 가는 흐름이 있습니다.
