디스크 캐시는 디스크 섹터 일부를 주기억장치에 복사해 둔 버퍼다. 자주 펴는 책 몇 권을 책상 위에 두는 것처럼, 같은 섹터를 다시 찾으면 디스크까지 가지 않고 메모리에서 바로 준다. 지역성 덕분에 한 번 가져온 블록은 곧 또 쓰일 가능성이 크다. 문제는 캐시가 찼을 때 무엇을 내보낼지인데, 최근 사용과 사용 횟수 중 무엇을 볼지에 따라 결과가 크게 달라진다.
예시로 보기
같은 블록을 짧은 시간에 여러 번 읽는 일은 흔하다. 예를 들어 레코드 하나를 처리하면서 같은 블록을 열 번 읽는다고 하자. 사용 횟수만 보는 LFU라면 이 블록의 횟수는 10이 된다. 처리가 끝나 다시는 안 쓰여도, 횟수가 높아 캐시에서 오래 버틴다. 그동안 진짜로 계속 쓰이는 다른 블록이 횟수가 낮다는 이유로 쫓겨난다1.
빈도 기반 교체는 이 문제를 고친 것이다. 방금 참조된 블록에서 되풀이되는 참조는 횟수로 치지 않는다.
정확히 말하면
디스크 캐시는 디스크 섹터를 담는 주기억장치의 버퍼다. 일부 섹터의 복사본을 가진다. 어떤 섹터에 입출력 요청이 오면 먼저 그 섹터가 캐시에 있는지 본다. 있으면 캐시로 처리하고, 없으면 디스크에서 캐시로 읽어 온다.
| 교체 방법 | 내보내는 블록 | 구현 |
|---|---|---|
| LRU | 캐시에 들어온 뒤 가장 오랫동안 참조되지 않은 블록 | 캐시를 가리키는 포인터 스택. 참조되거나 새로 들어온 블록을 스택 맨 위에 올린다. 맨 아래가 교체 대상이다 |
| LFU | 참조 횟수가 가장 적은 블록 | 블록마다 계수기를 두고 참조마다 1 늘린다. 교체할 때 계수기가 가장 작은 블록을 고른다 |
| 빈도 기반 교체 | 아래 설명 | LRU 스택을 구역으로 나눈다 |
빈도 기반 교체. 블록들을 LRU 스택처럼 최근 사용 순으로 늘어놓고 구역을 나눈다.
MRU ← [ 새 구역 | 중간 구역 | 옛 구역 ] → LRU
- 블록이 참조되면 스택 맨 위(새 구역)로 옮긴다.
- 이미 새 구역에 있던 블록이 다시 참조되면 계수기를 늘리지 않는다. 짧은 시간의 되풀이 참조를 횟수로 치지 않기 위해서다. 새 구역 밖에서 참조되면 계수기를 1 늘린다.
- 교체할 때는 옛 구역의 블록 가운데 계수기가 가장 작은 것을 내보낸다. 동률이면 가장 오래된 것이다.
flowchart TD
R(["블록 하나가 참조됨"]) --> Q{"그 블록이 지금 새 구역에 있나?"}
Q -->|"예"| K["계수기 그대로"]
Q -->|"아니오"| I["계수기 1 늘림"]
K --> T["스택 맨 위로 옮김"]
I --> T
T --> S["나머지 블록은 한 칸씩 아래로 밀려 새 구역에서 중간 구역, 옛 구역으로"]
S --> V(["교체할 때: 옛 구역에서 계수기가 가장 작은 블록을 내보냄"])
참조가 오면 위쪽 갈림길에서 셀지 말지를 먼저 정한다. 어느 쪽이든 블록은 맨 위로 가고, 내보낼 후보는 맨 아래 옛 구역에서만 고른다.
구역을 둘(새, 옛)만 두면, 새 구역을 막 벗어난 블록은 계수기를 늘릴 기회가 없어 바로 쫓겨날 수 있다. 그래서 가운데에 중간 구역을 두어, 옛 구역에 닿기 전에 횟수를 쌓을 시간을 준다1.
성능 비교의 함정. LRU를 잰 여러 연구(VAX의 UNIX 등)의 결과와 빈도 기반 교체의 시뮬레이션 결과를 나란히 놓으면 LRU가 나아 보인다2. 하지만 같은 참조 패턴과 같은 캐시 구조로 비교하면 빈도 기반 교체가 낫다. 참조 패턴의 정확한 순서와 캐시 크기 같은 설계 조건이 결과를 크게 좌우한다.
활용
- 리눅스 2.4 이후에는 디스크와 주기억장치 사이의 모든 데이터를 하나의 통합 페이지 캐시로 다룬다. 바뀐(dirty) 페이지를 모아 효율적으로 쓰고, 시간 지역성 때문에 다시 참조될 페이지를 붙잡아 둔다.
- Windows의 캐시 관리자가 모든 파일 캐싱을 맡는다.
- 페이지 교체, 캐시 메모리와 같은 고민(LRU냐 LFU냐)을 디스크와 주기억장치 사이에서 한다.
연결
- 선수: 입출력 버퍼링, 페이지 교체 알고리즘
확인 문제
C1 순수 LFU를 디스크 캐시에 쓰면 생기는 문제를 예로 설명하라.
답: 짧은 시간에 몰아서 여러 번 참조된 블록은 계수기가 커져, 그 뒤로 다시 안 쓰여도 오래 남는다. 그동안 꾸준히 쓰이지만 횟수가 아직 낮은 블록이 쫓겨난다. 횟수가 “최근에 쓰이는가”를 반영하지 못하기 때문이다.
C2 빈도 기반 교체에서 “새 구역에서의 참조는 세지 않는다”는 규칙이 하는 일을 한 문장으로 쓰라.
답: 방금 가져온 블록을 연달아 읽는 짧은 되풀이 참조가 계수기를 부풀리지 못하게 해서, 계수기가 오랜 기간에 걸친 진짜 인기를 나타내게 한다.
C3 LRU 스택(위가 최근)이 위에서부터 [B, D, A, C]이고 캐시 칸은 4개다. 참조 A, 그다음 새 블록 E가 들어오면 스택은?
답: A 참조 뒤 [A, B, D, C]. E가 들어오면 맨 아래 C를 내보내고 E를 맨 위에 올려 [E, A, B, D].