페이지 교체 알고리즘

가상 메모리 관리를 위해 페이징을 사용하는 운영체제에서, **페이지 교체 알고리즘**(page replacement algorithm)은 메모리 페이지를 할당해야 할 때 어떤 메모리 페이지를 페이지 아웃(스왑 아웃이라고도 함)하거나 디스크에 기록할지 결정한다. 페이지 교체는 요청된 페이지가 메모리에 없고(페이지 부재), 가용 페이지가 없거나 가용 페이지 수가 특정 임계값보다 낮아 할당을 만족할 수 없을 때 발생한다.

교체 대상으로 선택되어 페이지 아웃된 페이지가 다시 참조되면 페이지 인(디스크에서 읽어옴) 되어야 하며, 이 과정에서 I/O 완료를 기다려야 한다. 이것이 페이지 교체 알고리즘의 품질을 결정한다. 페이지 인을 기다리는 시간이 적을수록 더 좋은 알고리즘이다. 페이지 교체 알고리즘은 하드웨어가 제공하는 페이지 접근에 관한 제한된 정보를 바탕으로, 알고리즘 자체의 비용(주기억장치 및 프로세서 시간)과 균형을 맞추면서 전체 페이지 미스 횟수를 최소화하기 위해 어떤 페이지를 교체해야 할지 추측한다.

페이지 교체 문제는 최적의 결정론적 알고리즘이 알려져 있다는 점에서 경쟁 분석 관점의 전형적인 온라인 알고리즘 문제이다.

## 역사
페이지 교체 알고리즘은 1960년대와 1970년대에 활발한 연구와 논쟁의 주제였다.
그 논쟁은 정교한 LRU(최근 최소 사용) 근사 알고리즘과 워킹 세트 알고리즘의 개발로 대부분 마무리되었다. 그 이후 전통적인 페이지 교체 알고리즘이 전제했던 몇 가지 기본 가정들이 무효화되면서 연구가 재점화되었다. 특히 하드웨어와 사용자 수준 소프트웨어의 다음과 같은 변화 추세가 페이지 교체 알고리즘의 성능에 영향을 미쳤다.

* 주기억장치의 크기가 수십 배 이상 증가했다. 기가바이트 단위의 주기억장치 환경에서는 모든 메모리 프레임을 주기적으로 확인해야 하는 알고리즘의 실용성이 점점 떨어지고 있다.
* 메모리 계층 구조가 더 깊어졌다. CPU 캐시 미스 비용이 훨씬 더 비싸졌으며, 이는 이전의 문제를 악화시킨다.
* 사용자 소프트웨어의 참조 국부성이 약화되었다. 이는 수많은 작은 함수를 사용하는 객체 지향 프로그래밍 기법의 확산, 혼란스러운 메모리 참조 패턴을 유발하는 트리나 해시 테이블 같은 정교한 자료 구조의 사용, 그리고 애플리케이션의 메모리 접근 동작을 급격히 변화시킨 쓰레기 수집의 등장에 주로 기인한다.

운영체제 커널 아키텍처의 차이로 인해 페이지 교체 알고리즘에 대한 요구사항도 변했다. 특히 대부분의 현대 운영체제 커널은 가상 메모리와 파일 시스템 캐시를 통합했기 때문에, 페이지 교체 알고리즘은 사용자 프로그램의 가상 주소 공간과 캐시된 파일 페이지 모두에서 교체 대상을 선택해야 한다. 후자의 페이지들은 특정 속성을 가진다. 예를 들어, 잠금 상태일 수 있거나 저널링에 의해 쓰기 순서 요구사항이 부과될 수 있다. 또한 페이지 교체의 목적이 메모리 대기 시간을 최소화하는 것이므로, 메모리를 할당하는 다른 커널 하위 시스템의 메모리 요구사항도 고려해야 한다. 결과적으로 현대 커널(리눅스, FreeBSD, Solaris)의 페이지 교체는 가상 메모리 하위 시스템의 상위 수준보다는 범용 커널 메모리 할당자 수준에서 작동하는 경향이 있다.

## 지역 교체 vs. 전역 교체
교체 알고리즘은 지역적일 수도 있고 전역적일 수도 있다.

프로세스에서 페이지 부재가 발생했을 때, 지역 페이지 교체 알고리즘은 해당 프로세스(또는 메모리 파티션을 공유하는 프로세스 그룹)에 속한 페이지 중에서 교체 대상을 선택한다. 전역 교체 알고리즘은 메모리에 있는 모든 페이지 중 하나를 자유롭게 선택할 수 있다.

지역 페이지 교체는 특정 프로세스나 프로세스 그룹에 할당될 페이지 수를 결정하는 일종의 메모리 파티셔닝을 전제로 한다. 가장 대중적인 파티셔닝 형태는 고정 파티셔닝과 워킹 세트 모델에 기반한 균형 세트 알고리즘이다. 지역 페이지 교체의 장점은 확장성이다. 각 프로세스가 독립적으로 페이지 부재를 처리할 수 있어 해당 프로세스에 대해 일관된 성능을 보장한다. 그러나 시스템 전체적인 관점에서는 전역 페이지 교체가 더 효율적이다.

## 참조 및 수정된 페이지 감지

현대적인 범용 컴퓨터와 일부 임베디드 프로세서는 가상 메모리를 지원한다. 대부분의 시스템에서 각 프로세스는 자신만의 가상 주소 공간을 가진다. 페이지 테이블은 프로세스 가상 주소의 일부를 물리 주소에 매핑한다. 또한 대부분의 아키텍처에서 페이지 테이블은 각 페이지에 대해 "접근(access)" 비트와 "더티 비트"를 보유한다. CPU는 프로세스가 해당 페이지의 메모리를 읽거나 쓸 때 접근 비트를 설정하며, 메모리를 쓸 때 더티 비트를 설정한다. 운영체제는 이러한 접근 및 더티 비트를 수정할 수 있다. 운영체제는 다음과 같은 수단을 통해 메모리 및 파일 접근을 감지할 수 있다.

* 프로세스의 페이지 테이블에 있는 페이지들의 접근 비트를 해제한다. 일정 시간이 지난 후 운영체제는 페이지 테이블을 스캔하여 CPU에 의해 접근 비트가 설정된 페이지들을 찾는다. 접근 비트가 CPU에 의해 자동으로 설정되므로 빠르지만, 운영체제가 접근 사실을 즉시 알 수 없고 프로세스가 이 페이지들에 접근한 순서 정보도 없으므로 부정확하다.
* 물리 메모리에서 페이지를 제거하지 않고 프로세스의 페이지 테이블에서만 페이지를 제거한다. 다음 접근 시 페이지 부재가 발생하므로 즉시 감지된다. 페이지 부재는 운영체제로의 문맥 교환, 소프트웨어를 통한 물리 주소 조회, 페이지 테이블 수정 및 프로세스로의 복귀를 수반하므로 느리지만, 접근 발생 즉시 감지되므로 정확하다.
* 프로세스가 POSIX의 `read` 및 `write`와 같이 페이지 캐시에 접근할 가능성이 있는 시스템 호출을 수행할 때 직접 감지한다.

## 사전 청소
대부분의 교체 알고리즘은 단순히 대상 페이지를 결과로 반환한다. 이는 만약 대상 페이지가 더러운(dirty) 상태라면(즉, 페이지를 회수하기 전에 데이터를 안정 저장소에 기록해야 한다면), 해당 페이지를 안정 저장소로 보내기 위한(페이지를 깨끗하게 만들기 위한) I/O가 시작되어야 함을 의미한다. 가상 메모리 초창기에는 청소에 소요되는 시간이 큰 문제가 아니었는데, 가상 메모리가 안정 저장소와의 전이중 채널을 갖춘 시스템에서 처음 구현되어 청소와 페이징이 관습적으로 겹쳐서 수행되었기 때문이다. 반면 현대의 범용 하드웨어는 전이중 전송을 지원하지 않는 경우가 많아 대상 페이지의 청소가 문제가 된다.

이 상황을 해결하기 위해 다양한 사전 청소(precleaning) 정책이 구현된다. 사전 청소는 곧 교체될 가능성이 높은 더러운 페이지들에 대해 미리 I/O를 시작하는 메커니즘이다. 아이디어는 사전 청소된 페이지가 실제로 교체 대상으로 선택될 즈음에는 I/O가 완료되어 페이지가 깨끗한 상태가 되어 있게 하는 것이다. 사전 청소는 다음에 교체될 페이지를 식별할 수 있다고 가정한다. 너무 의욕적인 사전 청소는 교체 대상으로 선택되기 전에 다시 더러워지는 페이지를 기록함으로써 I/O 대역폭을 낭비할 수 있다.

## (h,k)-페이징 문제
(h,k)-페이징 문제는 페이징 문제 모델의 일반화이다. h, k를 h \leq k인 양의 정수라고 하자. 캐시 크기가 k인 알고리즘의 성능을 이론적으로 최적인 페이지 교체 알고리즘의 크기 h 캐시 성능과 비교하여 측정한다. h인 경우, 최적 페이지 교체 알고리즘에 엄격하게 더 적은 자원을 제공하는 셈이다.

(h,k)-페이징 문제는 온라인 알고리즘의 캐시 크기와 최적 알고리즘의 캐시 크기를 별도로 매개변수화하여 비교함으로써 온라인 알고리즘의 성능을 측정하는 방법이다.

## 마킹 알고리즘

마킹 알고리즘(Marking algorithms)은 페이징 알고리즘의 일반적인 부류이다. 각 페이지에 대해 '마크(mark)'라고 불리는 비트를 연관시킨다. 초기에는 모든 페이지를 마킹되지 않은 상태로 설정한다. 페이지 요청 단계(일련의 요청 기간) 동안, 해당 단계에서 처음 요청된 페이지를 마킹한다. 마킹 알고리즘은 마킹된 페이지를 절대 페이지 아웃시키지 않는 알고리즘이다.

ALG가 크기 k의 캐시를 가진 마킹 알고리즘이고, OPT가 크기 h(h \leq k)의 캐시를 가진 최적 알고리즘이라면, ALG는  \tfrac{k}{k-h+1}-경쟁적이다. 따라서 모든 마킹 알고리즘은  \tfrac{k}{k-h+1}-경쟁비를 달성한다.

LRU는 마킹 알고리즘인 반면, FIFO는 마킹 알고리즘이 아니다.

## 보수적 알고리즘
k개 이하의 서로 다른 페이지 참조를 포함하는 임의의 연속된 요청 시퀀스에 대해, 알고리즘이 k번 이하의 페이지 부재를 발생시킨다면 그 알고리즘은 보수적(conservative)이라고 한다.

ALG가 크기 k의 캐시를 가진 보수적 알고리즘이고, OPT가 크기 h \leq k의 캐시를 가진 최적 알고리즘이라면, ALG는  \tfrac{k}{k-h+1}-경쟁적이다. 따라서 모든 보수적 알고리즘은  \tfrac{k}{k-h+1}-경쟁비를 달성한다.

LRU, FIFO 및 CLOCK은 보수적 알고리즘이다.

## 페이지 교체 알고리즘
다양한 페이지 교체 알고리즘이 존재한다.

### 이론적으로 최적인 페이지 교체 알고리즘
이론적으로 최적인 페이지 교체 알고리즘(OPT, 투시적 교체 알고리즘, 또는 벨라디의 최적 페이지 교체 정책으로도 알려짐)은 다음과 같이 작동하는 알고리즘이다. 페이지를 스왑 인 해야 할 때, 운영체제는 다음 사용까지의 시간이 가장 멀리 남은 페이지를 스왑 아웃한다. 예를 들어, 0.4초 이내에 사용될 페이지보다는 향후 6초 동안 사용되지 않을 페이지를 스왑 아웃한다.

이 알고리즘은 범용 운영체제에서 구현될 수 없는데, 시스템에서 실행될 모든 소프트웨어를 미리 알고 그 메모리 참조 패턴을 정적으로 분석할 수 있거나 런타임 분석이 가능한 특정 범주의 애플리케이션인 경우를 제외하고는 페이지가 사용되기 전까지 얼마나 걸릴지 신뢰성 있게 계산하는 것이 불가능하기 때문이다. 이러한 한계에도 불구하고 최적에 가까운 성능을 제공할 수 있는 알고리즘들이 존재한다. 운영체제는 프로그램이 참조한 모든 페이지를 추적하고, 그 데이터를 사용하여 이후 실행 시 어떤 페이지를 스왑 인/아웃할지 결정한다. 이 알고리즘은 프로그램의 첫 실행 시에는 불가능하지만, 실행 시마다 메모리 참조 패턴이 비교적 일관된 경우 최적에 가까운 성능을 제공할 수 있다.

페이징 문제에 대한 분석은 온라인 알고리즘 분야에서도 수행되었다. 페이징 문제에 대한 무작위 온라인 알고리즘의 효율성은 분할 상환 분석을 사용하여 측정된다.

### 최근 미사용 (NRU)
최근 미사용(NRU, Not Recently Used) 페이지 교체 알고리즘은 최근에 사용된 페이지를 메모리에 유지하는 것을 선호하는 알고리즘이다. 이 알고리즘은 다음과 같은 원리로 작동한다. 페이지가 참조되면 해당 페이지에 참조 비트가 설정되어 참조되었음을 표시한다. 마찬가지로 페이지가 수정(기록)되면 수정 비트가 설정된다. 비트 설정은 보통 하드웨어에 의해 이루어지지만 소프트웨어 수준에서도 가능하다.

특정 고정 시간 간격마다 타이머 인터럽트가 발생하여 모든 페이지의 참조 비트를 해제하므로, 현재 타이머 간격 내에 참조된 페이지들만 참조 비트가 설정된 상태로 남는다. 페이지 교체가 필요할 때 운영체제는 페이지를 다음의 네 가지 클래스로 분류한다.

:3. 참조됨, 수정됨
:2. 참조됨, 수정되지 않음
:1. 참조되지 않음, 수정됨
:0. 참조되지 않음, 수정되지 않음
페이지가 수정되었으나 참조되지 않는 것이 불가능해 보일 수도 있지만, 이는 클래스 3 페이지의 참조 비트가 타이머 인터럽트에 의해 해제되었을 때 발생한다. NRU 알고리즘은 가장 낮은 카테고리에서 무작위로 페이지를 선택하여 제거한다. 즉, 위 네 가지 카테고리 중 참조되지 않고 수정되지 않은 페이지가 있다면 이를 먼저 교체한다. 이 알고리즘은 (최근 타이머 간격 내에) 수정되었으나 참조되지 않은 페이지가, 집중적으로 참조되고 있는 수정되지 않은 페이지보다 덜 중요하다는 점을 시사한다.

NRU는 마킹 알고리즘이므로  \tfrac{k}{k-h+1}-경쟁적이다.

### 선입 선출 (FIFO)
가장 단순한 페이지 교체 알고리즘은 FIFO 알고리즘이다. 선입 선출(FIFO, First-In, First-Out) 페이지 교체 알고리즘은 운영체제 측의 관리 부담이 적은 저비용 알고리즘이다. 아이디어는 이름에서 알 수 있듯이 명확하다. 운영체제는 메모리에 있는 모든 페이지를 큐에 유지하며, 가장 최근에 들어온 페이지는 뒤에, 가장 오래된 페이지는 앞에 둔다. 페이지 교체가 필요할 때 큐의 맨 앞에 있는 페이지(가장 오래된 페이지)가 선택된다. FIFO는 저렴하고 직관적이지만 실제 응용 프로그램에서의 성능은 좋지 않다. 따라서 수정되지 않은 순수 형태로 사용되는 경우는 드물다. 이 알고리즘은 벨라디의 변이 현상을 겪는다.
단순히 말해, 페이지 부재 시 메모리에 가장 오래 머물렀던 프레임이 교체된다.

FIFO 페이지 교체 알고리즘은 일부 수정된 형태로 OpenVMS 운영체제에서 사용된다. 유효한 변환 테이블 참조가 있는 항목들을 제한적으로 건너뜀으로써 부분적인 2차 기회를 제공하며, 추가적으로 프로세스 워킹 세트에서 축출된 페이지들을 시스템 전체 풀로 이동시켜 아직 재사용되지 않았다면 복구할 수 있도록 한다.

FIFO는 보수적 알고리즘이므로  \tfrac{k}{k-h+1}-경쟁적이다.

### 2차 기회
FIFO 페이지 교체 알고리즘의 수정된 형태인 2차 기회(Second-chance) 페이지 교체 알고리즘은 적은 비용으로 FIFO보다 상대적으로 나은 성능을 보인다. FIFO처럼 큐의 맨 앞을 확인하지만, 즉시 페이지 아웃하는 대신 참조 비트가 설정되어 있는지 확인한다. 설정되어 있지 않으면 페이지를 스왑 아웃한다. 설정되어 있다면 참조 비트를 해제하고 페이지를 큐의 맨 뒤에 (마치 새 페이지인 것처럼) 삽입한 뒤 이 과정을 반복한다. 이는 원형 큐로 생각할 수도 있다. 모든 페이지의 참조 비트가 설정되어 있다면, 리스트의 첫 번째 페이지를 다시 만났을 때 해당 페이지의 참조 비트가 이미 해제된 상태이므로 스왑 아웃된다. 모든 페이지의 참조 비트가 해제된 상태라면 2차 기회 알고리즘은 순수 FIFO와 동일하게 작동한다.

이름에서 알 수 있듯이 2차 기회 알고리즘은 모든 페이지에 "2차 기회"를 준다. 참조된 적이 있는 오래된 페이지는 아마도 사용 중일 가능성이 높으므로, 참조된 적이 없는 새 페이지보다 먼저 스왑 아웃되어서는 안 된다는 논리다.

### 클럭 (Clock)
클럭(Clock) 알고리즘은 페이지를 리스트의 뒤로 계속 밀어낼 필요가 없기 때문에 2차 기회 알고리즘보다 효율적인 버전이지만, 2차 기회와 동일한 일반적 기능을 수행한다. 클럭 알고리즘은 메모리에 있는 페이지들의 원형 리스트를 유지하며, "시곗바늘"(반복자)은 리스트에서 마지막으로 검사된 페이지 프레임을 가리킨다. 페이지 부재가 발생하고 빈 프레임이 없으면 시곗바늘 위치의 R(참조) 비트를 검사한다. R이 0이면 "시곗바늘"이 가리키는 페이지 자리에 새 페이지를 넣고 바늘을 한 칸 전진시킨다. R이 1이면 R 비트를 0으로 지우고 바늘을 전진시키며 페이지가 교체될 때까지 이 과정을 반복한다. 이 알고리즘은 1969년 페르난도 J. 코바토에 의해 처음 기술되었다.

#### 클럭의 변형
* GCLOCK: 일반화된 클럭 페이지 교체 알고리즘.
* Clock-Pro: 메모리에 있는 M개의 페이지뿐만 아니라 페이지 아웃된 최근 M개의 페이지 정보를 포함하는 최근 참조 페이지 정보의 원형 리스트를 유지한다. 페이지 아웃된 페이지에 대한 이 추가 정보는 ARC와 유사하게 작동하여, 거대한 루프나 일회성 스캔 상황에서 LRU보다 더 나은 성능을 내도록 돕는다.
* WSclock: 클럭 알고리즘과 워킹 세트(즉, 특정 시간 간격 동안 해당 프로세스가 사용할 것으로 예상되는 페이지 집합) 개념을 결합하여 성능을 향상시킨다. 실제로 "에이징(aging)" 알고리즘과 "WSClock" 알고리즘은 아마도 가장 중요한 페이지 교체 알고리즘일 것이다.
* Clock with Adaptive Replacement (CAR): ARC와 대등한 성능을 내면서 LRU 및 CLOCK보다 월등히 뛰어난 성능을 보이는 페이지 교체 알고리즘이다. CAR 알고리즘은 자가 조정(self-tuning)이 가능하며 사용자가 지정하는 매직 파라미터가 필요 없다.

CLOCK은 보수적 알고리즘이므로  \tfrac{k}{k-h+1}-경쟁적이다.

### 최근 최소 사용 (LRU)
최근 최소 사용(LRU, Least Recently Used) 페이지 교체 알고리즘은 이름은 NRU와 비슷하지만, NRU가 마지막 클럭 간격의 사용 여부만 보는 반면 LRU는 짧은 기간 동안의 페이지 사용 기록을 추적한다는 점에서 다르다. LRU는 지난 몇 번의 명령 동안 가장 집중적으로 사용된 페이지가 다음 몇 번의 명령 동안에도 집중적으로 사용될 가능성이 높다는 아이디어에 기반한다. LRU는 이론적으로 최적에 가까운 성능을 제공할 수 있지만(적응형 교체 캐시만큼 훌륭함), 실제 구현하기에는 비용이 많이 든다. 성능은 최대한 유지하면서 비용을 줄이려는 몇 가지 구현 방법이 존재한다.

가장 비용이 많이 드는 방법은 메모리에 있는 모든 페이지를 포함하는 연결 리스트를 사용하는 것이다. 리스트의 맨 뒤에는 최근에 가장 적게 사용된 페이지가, 맨 앞에는 최근에 가장 많이 사용된 페이지가 위치한다. 이 구현의 비용은 메모리 참조가 일어날 때마다 리스트의 항목을 이동시켜야 한다는 점에 있으며, 이는 매우 시간 소모적인 프로세스이다.

하드웨어 지원이 필요한 또 다른 방법은 다음과 같다. 하드웨어에 매 명령마다 증가하는 64비트 카운터가 있다고 가정하자. 페이지에 접근할 때마다 해당 페이지는 접근 당시의 카운터 값을 획득한다. 페이지 교체가 필요할 때 운영체제는 카운터 값이 가장 낮은 페이지를 선택하여 스왑 아웃한다.

구현 비용 때문에 이후 설명할 LRU와 유사하지만 더 저렴한 구현을 제공하는 알고리즘들을 고려할 수 있다.

LRU 알고리즘의 한 가지 중요한 장점은 완전한 통계적 분석이 가능하다는 점이다. 예를 들어, LRU는 OPT 알고리즘보다 N배 이상의 페이지 부재를 발생시키지 않는다는 것이 증명되었으며, 여기서 N은 관리되는 풀의 페이지 수에 비례한다.

반면 LRU의 약점은 상당히 일반적인 여러 참조 패턴에서 성능이 저하되는 경향이 있다는 것이다. 예를 들어, LRU 풀에 N개의 페이지가 있을 때 애플리케이션이 N+1개 페이지의 배열에 대해 루프를 실행하면 매 접근마다 페이지 부재가 발생한다. 대형 배열에 대한 루프는 흔하기 때문에, 이러한 상황에서 더 잘 작동하도록 LRU를 수정하려는 노력이 많이 이루어졌다. 제안된 많은 LRU 변형들은 루프 참조 패턴을 감지하여 최근 최대 사용(MRU)과 같은 적절한 교체 알고리즘으로 전환하려고 시도한다.

#### LRU의 변형
# LRU-K: K번째 이전의 접근이 가장 과거에 일어난 페이지를 축출한다. 예를 들어 LRU-1은 일반 LRU이며, LRU-2는 직전이 아닌 그 이전(penultimate)의 접근 시간을 기준으로 페이지를 축출한다. LRU-K는 시간 국부성 측면에서 LRU보다 크게 개선되었다.
# ARC: 최근에 축출된 페이지의 이력을 유지함으로써 LRU를 확장하고, 이를 통해 최근 접근(recent) 또는 빈번한 접근(frequent)에 대한 선호도를 조정한다. 특히 순차적 스캔에 매우 강하다.
# 2Q: LRU 및 LRU/2 알고리즘을 개선한다. 두 개의 큐를 두어, 하나는 핫 패스(hot-path) 항목용, 다른 하나는 슬로우 패스(slow-path) 항목용으로 사용한다. 항목은 먼저 슬로우 패스 큐에 배치되고 두 번째 접근 시 핫 패스 큐로 이동한다. 추가된 항목에 대한 참조를 LRU나 LRU/2보다 더 오래 유지하므로 히트율을 높이는 더 나은 핫 패스 큐를 갖게 된다.

ARC와 다른 알고리즘들(LRU, MQ, 2Q, LRU-2, LRFU, LIRS)의 비교는 Megiddo & Modha 2004에서 확인할 수 있다.

LRU는 마킹 알고리즘이므로  \tfrac{k}{k-h+1}-경쟁적이다.

### 무작위 (Random)
무작위 교체 알고리즘은 메모리에 있는 페이지 중 하나를 무작위로 교체한다. 이는 페이지 참조를 추적하는 오버헤드 비용을 제거한다. 보통 FIFO보다는 성능이 좋고, 루프형 메모리 참조의 경우 LRU보다 낫지만 일반적으로 실제 환경에서는 LRU의 성능이 더 우수하다. OS/390은 전역 LRU 근사 방식을 사용하다가 LRU 성능이 저하되면 무작위 교체 방식으로 전환하며, 인텔 i860 프로세서는 무작위 교체 정책을 사용했다(Rhodehamel 1989).

### 최저 빈도 사용 (NFU)
최저 빈도 사용(NFU, Not Frequently Used) 페이지 교체 알고리즘은 카운터가 필요하며, 모든 페이지는 초기에 0으로 설정된 자신만의 카운터를 가진다. 각 클럭 간격마다 해당 간격 내에 참조된 모든 페이지의 카운터가 1씩 증가한다. 사실상 카운터는 페이지가 얼마나 자주 사용되었는지를 추적한다. 따라서 필요할 때 카운터가 가장 낮은 페이지를 스왑 아웃할 수 있다.

NFU의 주요 문제는 사용 기간(time span)을 고려하지 않고 사용 빈도만 추적한다는 점이다. 따라서 다단계 컴파일러에서 첫 번째 단계 동안 집중적으로 사용되었지만 두 번째 단계에서는 필요 없는 페이지가, 두 번째 단계에서 비교적 적게 사용되는 페이지보다 카운터가 높아 우선적으로 유지되는 현상이 발생한다. 이는 저조한 성능으로 이어진다. 운영체제 부팅 시와 같은 다른 일반적인 시나리오에서도 NFU는 비슷하게 작동한다. 다행히 이와 유사하면서 더 나은 알고리즘인 에이징 알고리즘이 존재한다.

최저 빈도 사용 페이지 교체 알고리즘은 페이지 테이블에 널 포인터 값이 포함되어 있을 때 최근 최소 사용 페이지 교체 알고리즘보다 페이지 부재를 적게 발생시킨다.

### 에이징 (Aging)
에이징(Aging) 알고리즘은 NFU 알고리즘의 후손으로, 사용 기간을 인식할 수 있도록 수정된 것이다. 단순히 참조된 페이지의 카운터를 증가시켜 시간에 관계없이 동일한 비중을 두는 대신, 페이지의 참조 카운터를 먼저 오른쪽으로 시프트(2로 나눔)한 뒤 해당 이진수의 왼쪽에 참조 비트를 추가한다. 예를 들어, 지난 6번의 클럭 틱 동안 한 페이지의 참조 비트가 1,0,0,1,1,0이었다면 참조 카운터는 시간순으로 10000000, 01000000, 00100000, 10010000, 11001000, 01100100이 된다. 오래전의 페이지 참조보다 현재에 가까운 페이지 참조가 더 큰 영향을 미친다. 이를 통해 과거에 빈번하게 참조되었더라도 최근에 참조되지 않은 페이지보다, 최근에 참조된 페이지가 더 높은 우선순위를 갖게 된다. 따라서 스왑 아웃이 필요할 때 카운터가 가장 낮은 페이지를 선택한다.

다음 파이썬 코드는 에이징 알고리즘을 시뮬레이션한다.
카운터 V_i는 으로 초기화되며, 위에서 설명한 대로 산술 시프트 연산자를 사용하는 V_i \leftarrow (R_i \ll (k-1)) | (V_i \gg 1)를 통해 업데이트된다.

```python
from collections.abc import Sequence

def simulate_aging(Rs: Sequence, k: int) -> None:
    """에이징 시뮬레이션"""
    print(" t  |  R-비트 (0-{length})        |  페이지 0-{length}의 카운터".format(length=len(Rs)))
    Vs = [0] * len(Rs[0])
    for t, R in enumerate(Rs):
        Vs[:] = [R[i] << (k - 1) | V >> 1 for i, V in enumerate(Vs)]
        print("{:02d}  |  {}  |  [{}]".format(t, R,
                                              ", ".join(["{:0{}b}".format(V, k)
                                                         for V in Vs])))
```

5번의 클럭 틱 동안 6개 페이지에 대한 R-비트 예시에서, 함수는 각 클럭 틱 에 대한 R-비트와 각 페이지의 개별 카운터 값 V_i를 이진수 표현으로 출력한다.

```pycon
>>> Rs = [[1,0,1,0,1,1], [1,1,0,0,1,0], [1,1,0,1,0,1], [1,0,0,0,1,0], [0,1,1,0,0,0]]
>>> k = 8
>>> simulate_aging(Rs, k)
 t  |  R-비트 (0-5)        |  페이지 0-5의 카운터
00  |  [1, 0, 1, 0, 1, 1]  |  [10000000, 00000000, 10000000, 00000000, 10000000, 10000000]
01  |  [1, 1, 0, 0, 1, 0]  |  [11000000, 10000000, 01000000, 00000000, 11000000, 01000000]
02  |  [1, 1, 0, 1, 0, 1]  |  [11100000, 11000000, 00100000, 10000000, 01100000, 10100000]
03  |  [1, 0, 0, 0, 1, 0]  |  [11110000, 01100000, 00010000, 01000000, 10110000, 01010000]
04  |  [0, 1, 1, 0, 0, 0]  |  [01111000, 10110000, 10001000, 00100000, 01011000, 00101000]
```


에이징은 프로세서 정수의 비트 크기에 따라 최신 번의 시간 간격 내 참조만 추적할 수 있다는 점에서 LRU와 다르다. 결과적으로 한 페이지는 9개 간격 전에 참조되었고 다른 페이지는 1000개 간격 전에 참조되었더라도 두 페이지의 참조 카운터가 모두 00000000일 수 있다. 일반적으로 지난 16번의 간격 내 사용량을 아는 것만으로도 어떤 페이지를 스왑 아웃할지 결정하는 데 충분하다. 따라서 에이징은 적절한 비용으로 최적에 가까운 성능을 제공할 수 있다.

### 최장 거리 우선 (LDF) 페이지 교체 알고리즘
이 알고리즘의 기본 아이디어는 LRU에서 사용된 참조 국부성이지만, LDF에서의 국부성은 사용된 참조가 아닌 거리에 기반한다는 점이 다르다. LDF에서는 현재 페이지에서 가장 멀리 떨어져 있는 페이지를 교체한다. 두 페이지의 거리가 같다면 시계 반대 방향 회전에서 현재 페이지 다음에 있는 페이지가 교체된다.

## 구현 세부 사항

### 참조 비트가 없는 하드웨어를 위한 기법
위에서 논의된 많은 기법은 각 페이지와 연관된 참조 비트가 있다고 가정한다. 일부 하드웨어에는 이러한 비트가 없으므로, 이를 효율적으로 사용하려면 참조 비트 없이도 잘 작동하는 기법이 필요하다.

한 가지 주목할 만한 예는 OpenVMS를 실행하는 VAX 하드웨어이다. 이 시스템은 페이지가 수정되었는지는 알 수 있지만, 반드시 읽혔는지는 알 수 없다. 이 시스템의 접근 방식은 '2차 페이지 캐싱'으로 알려져 있다. 워킹 세트(일반적으로 프로세스 전용 메모리)에서 제거된 페이지들은 당분간 물리 메모리에 유지되는 동안 특수 목적 리스트에 배치된다. 워킹 세트에서 페이지를 제거하는 것은 엄밀히 말해 페이지 교체 작업은 아니지만, 사실상 해당 페이지를 교체 후보로 식별하는 역할을 한다. 백업 저장소가 여전히 유효한(더럽지 않거나 보존할 필요가 없는) 페이지는 가용 페이지 리스트(Free Page List)의 꼬리에 배치된다. 백업 저장소에 기록이 필요한 페이지는 수정된 페이지 리스트(Modified Page List)에 배치된다. 이러한 작업은 일반적으로 가용 페이지 리스트의 크기가 조정 가능한 임계값 아래로 떨어질 때 트리거된다.

워킹 세트 제거를 위한 페이지 선택은 본질적으로 무작위 방식으로 이루어질 수 있으며, 잘못된 선택이 되더라도 미래의 참조가 해당 페이지가 물리 메모리에서 실제로 제거되기 전에 가용 또는 수정 리스트에서 검색할 수 있을 것이라는 기대를 바탕으로 한다. 이렇게 참조된 페이지는 가용 또는 수정 리스트에서 제거되어 다시 프로세스 워킹 세트로 복귀한다. 또한 수정된 페이지 리스트는 여러 페이지를 그룹으로 묶어 백업 저장소에 한꺼번에 기록할 기회를 제공하여 효율성을 높인다. 기록이 완료된 페이지들은 가용 페이지 리스트로 이동할 수 있다. 가용 페이지 리스트의 맨 앞으로 이동하는 페이지의 시퀀스는 LRU나 NRU 메커니즘의 결과와 유사하며, 전체적인 효과는 앞서 설명한 2차 기회 알고리즘과 유사하다.

또 다른 예는 ARM 아키텍처에서 리눅스 커널이 사용하는 방식이다. 하드웨어 기능의 부족은 두 개의 페이지 테이블을 제공함으로써 보완된다. 하나는 프로세서 네이티브 페이지 테이블로 참조 비트나 더티 비트가 없으며, 다른 하나는 필요한 비트들이 존재하는 소프트웨어 유지 페이지 테이블이다. 소프트웨어 유지 테이블의 에뮬레이션 비트들은 페이지 부재에 의해 설정된다. 페이지 부재를 발생시키기 위해 두 번째 테이블의 에뮬레이션 비트를 해제하면 해당 페이지에 대한 일부 접근 권한이 취소되며, 이는 네이티브 테이블을 수정함으로써 구현된다.

### 리눅스의 페이지 캐시
리눅스는 다음에 대해 통합된 페이지 캐시를 사용한다.
* <code>brk</code> 및 익명 <code>mmap</code> 영역. 이는 사용자 공간 프로그램의 힙과 스택을 포함한다. 페이지 아웃될 때 스왑 영역에 기록된다.
* 비익명(파일 기반) `mmap` 영역. 메모리에 존재하고 사적으로 수정되지 않은 경우 물리 페이지는 파일 캐시 또는 버퍼와 공유된다.
* <code>shm_open</code>을 통해 획득한 공유 메모리.
* Tmpfs 인메모리 파일 시스템. 페이지 아웃될 때 스왑에 기록된다.
* 파일 캐시. 페이지 아웃될 때 기본 블록 저장소에 기록된다(아래의 버퍼를 거칠 수 있음).
* 리눅스에서 "버퍼"라고 부르는 블록 장치의 캐시(파이프용 버퍼나 리눅스 내부에서 사용되는 다른 버퍼 구조와 혼동하지 말 것). 페이지 아웃될 때 기본 저장소에 기록된다.
통합 페이지 캐시는 CPU가 지원하는 가장 작은 페이지 단위(ARMv8, X86 및 X86-64에서 4&nbsp;KiB)로 작동하며, 리눅스에서 "휴즈 페이지(huge pages)"라고 부르는 한 단계 더 큰 크기(X86-64에서 2 MiB)의 페이지들도 일부 사용한다. 페이지 캐시의 페이지들은 "활성(active)" 세트와 "비활성(inactive)" 세트로 나뉜다. 두 세트 모두 페이지의 LRU 리스트를 유지한다. 기본적으로 페이지가 사용자 공간 프로그램에 의해 접근되면 비활성 세트의 헤드에 놓인다. 반복적으로 접근되면 활성 리스트로 이동한다. 리눅스는 활성 세트가 비활성 세트보다 작게 유지되도록 필요에 따라 활성 세트의 페이지를 비활성 세트로 이동시킨다. 페이지가 비활성 세트로 이동할 때 물리 메모리에서 축출되지 않은 채로 모든 프로세스 주소 공간의 페이지 테이블에서 제거된다. 페이지가 비활성 세트에서도 제거될 때 물리 메모리에서 페이지 아웃된다. "활성" 및 "비활성" 리스트의 크기는 `/proc/meminfo`의 "Active", "Inactive", "Active(anon)", "Inactive(anon)", "Active(file)", "Inactive(file)" 필드에서 확인할 수 있다.

## 워킹 세트

프로세스의 워킹 세트는 특정 시간 간격 동안 해당 프로세스가 사용할 것으로 예상되는 페이지의 집합이다.

"워킹 세트 모델"은 엄밀한 의미의 페이지 교체 알고리즘은 아니며, 사실 일종의 중기 스케줄러에 가깝다.

## 같이 보기
* 캐시 알고리즘
* LRU 알고리즘
* NUR 알고리즘

## 각주

분류:가상 메모리
분류:메모리 관리 알고리즘
분류:온라인 알고리즘