페이지 교체: RAM이 가득 찼을 때 무엇을 내보낼까
필요한 페이지를 RAM에 올려야 하는데 빈 프레임이 없다면 운영체제는 기존 페이지 일부를 내보내야 한다. 페이지 교체는 어떤 페이지를 희생자로 고를지 결정하는 정책이다. 앞으로 곧 쓸 페이지를 잘못 내보내면 바로 다시 불러와야 한다. 데이터가 저장 장치로 오가는 비용이 큰 만큼 선택의 작은 차이가 프로그램 지연을 크게 바꿀 수 있다.
교체 정책은 무엇을 다시 사용할지 서로 다른 기준으로 추정한다.
미래를 안다면 쉬운 선택
이상적인 OPT 정책은 앞으로 가장 늦게 다시 사용할 페이지를 내보낸다. 정해진 참조 순서에서 교체 실패 수를 최소화하는 비교 기준이지만, 일반적인 실행에서는 미래 참조를 알 수 없다. 따라서 실제 정책은 과거 기록이나 접근 상태로 미래를 추정한다. OSTEP의 페이지 교체 정책 장은 OPT와 FIFO·LRU·Clock의 목적과 차이를 설명한다.
FIFO는 가장 먼저 들어온 페이지를 내보낸다. 관리가 간단하지만 오래 머물렀다는 사실이 덜 쓰인다는 뜻은 아니다. LRU는 최근 가장 오랫동안 쓰지 않은 페이지를 고른다. 최근 사용한 데이터를 다시 사용할 가능성이 높다는 시간적 지역성을 이용한다. 정확한 LRU는 접근 순서를 계속 관리해야 하므로 운영체제 수준에서는 근사 방법도 중요하다.
작은 참조 문자열로 비교하기
빈 프레임 두 개에서 페이지를 1, 2, 1, 3, 1, 2 순서로 읽는다고 하자. FIFO는 1과 2를 채운 뒤 1에 히트한다. 3이 필요할 때 먼저 들어온 1을 내보낸다. 이어 1을 위해 2를, 마지막 2를 위해 3을 내보내므로 총 다섯 번 실패한다. LRU는 3이 들어올 때 최근 사용하지 않은 2를 내보내 다음 1은 히트하고 총 네 번 실패한다.
이 결과가 LRU의 모든 상황에서의 승리를 뜻하지는 않는다. 참조 패턴에 따라 정책의 성적은 달라진다. FIFO는 프레임 수를 늘려도 특정 참조 순서에서 실패가 오히려 늘어나는 현상이 가능하다. 알고리즘을 비교할 때는 프레임 수, 초기 상태, 참조 순서, 실패의 정의를 고정해야 의미가 있다.
최근 사용을 싸게 추정한다
Clock은 페이지를 원형으로 보고 접근 비트 등을 이용해 최근 사용한 페이지에 추가 기회를 준다. 포인터가 돌며 비트가 켜진 항목은 끄고 넘어가고, 꺼진 후보를 교체하는 단순 모델이 대표적이다. 매 접근마다 완전한 순서를 갱신하지 않으면서 최근 사용 정보를 반영하려는 접근이다. 실제 운영체제의 정책은 이보다 더 많은 상태를 결합할 수 있다.
수정된 페이지는 원래 저장 위치와 내용이 달라 그대로 버릴 수 없을 수 있다. 다시 쓸 수 있는 형태로 기록하는 비용이 생긴다. 반대로 수정되지 않은 파일 페이지는 필요할 때 파일에서 다시 읽을 수 있다. 따라서 희생자 선택은 사용 빈도뿐 아니라 회수 가능성, 쓰기 비용, 전체 메모리 압력도 고려하게 된다.
활발히 사용하는 페이지 집합이 RAM을 계속 넘으면 내보낸 페이지를 곧바로 다시 읽는 스래싱이 생길 수 있다. CPU는 계산보다 대기와 페이지 이동에 시간을 쓴다. 정책을 바꾸는 것만으로 부족한 물리 용량을 무한히 보완할 수는 없다. 작업 집합을 줄이고 한 영역에서 충분히 계산하도록 접근 순서를 바꾸는 일도 페이지 교체 성능을 개선하는 중요한 방법이다.