페이지 교체 알고리즘

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

페이지 교체 알고리즘은 메모리 부족 시 메모리 페이지를 교체하는 방법으로, 1960년대부터 연구되어 왔다. 지역적 또는 전역적 방식, 이론적 최적 알고리즘(OPT)을 포함한 다양한 종류가 존재하며, NRU, FIFO, Second-chance, Clock, LRU, Random, NFU, Aging, LDF 등의 알고리즘이 개발되었다. 추가적으로 Precleaning, (h,k)-페이징 문제, 마킹 알고리즘, 보수적 알고리즘 등의 고려 사항이 있으며, 참조 비트가 없는 하드웨어에서의 구현, 리눅스 커널의 페이지 캐시 등 다양한 환경에 적용된다.

더 읽어볼만한 페이지

온라인 알고리즘 - 경쟁성 분석
경쟁성 분석은 위키백과 내에서 문서 분석, 주제 통합, 목차 설계가 예정된 상태로, 아직 내용이 채워지지 않아 내용 추가가 필요한 문서이다.
메모리 관리 알고리즘 - 키오시아
키오시아는 도시바의 반도체 메모리 사업을 계승하여, 2017년 분사 후 베인캐피털 컨소시엄에 인수되어 2019년 현재 사명으로 변경되었으며, NAND 플래시 메모리 기술 기반의 제품을 생산하고 요카이치, 키타카미 공장을 주요 생산 시설로 두고 있다.
메모리 관리 알고리즘 - Least Recently Used
Least Recently Used(LRU)는 가장 최근에 사용되지 않은 항목을 교체하는 캐시 알고리즘이며, 연결 리스트와 연관 배열을 통해 O(1) 시간 복잡도로 계산하고, CPU 캐시 메모리 및 정리법 등에도 활용된다.
가상 메모리 - 메모리 관리 장치
메모리 관리 장치(MMU)는 가상 주소를 물리 주소로 변환하여 메모리 접근을 관리하고 보호하는 하드웨어 장치로서, 가상 메모리 시스템에서 독립적인 가상 주소 공간을 제공하고 불법적인 메모리 접근을 차단하며, 페이지 테이블을 통해 외부 단편화 문제를 완화하고 트랜슬레이션 룩어사이드 버퍼(TLB)로 주소 변환 속도를 향상시킨다.
가상 메모리 - 가상 주소 공간
가상 주소 공간은 운영 체제가 프로세스에 제공하는 논리적인 메모리 공간으로, 실제 물리 메모리 주소와 독립적으로 관리되며, 프로세스는 이 공간을 통해 실행 파일, DLL 파일, 페이지 파일 등을 매핑하고 메모리를 할당받는다.

페이지 교체 알고리즘
페이지 교체 알고리즘
페이지 교체 알고리즘
일반 정보
유형	캐시 알고리즘
알고리즘 종류

2. 역사적 배경

페이지 교체 알고리즘은 1960년대부터 1970년대에 걸쳐 활발하게 연구되었으며, 이 과정에서 여러 논쟁이 있었다. 이 시기에는 정교한 LRU (최근 사용 안 함) 근사 알고리즘 및 작업 집합 알고리즘이 개발되면서 큰 발전을 이루었다.

하지만 이후 기존 페이지 교체 알고리즘의 기본 가정들이 무효화되면서 연구가 다시 활발해졌다. 특히 하드웨어 및 사용자 수준 소프트웨어의 다음과 같은 변화가 페이지 교체 알고리즘의 성능에 영향을 미쳤다.

주 메모리 용량 증가: 주 메모리 크기가 수 기가바이트에 달하면서 모든 메모리 프레임을 주기적으로 확인하는 방식은 실용성이 떨어지게 되었다.
메모리 계층 구조 심화: CPU 캐시 실패 비용이 증가하면서, 메모리 관리가 더욱 중요해졌다.
사용자 소프트웨어의 참조 지역성 약화: 객체 지향 프로그래밍의 확산, 트리 및 해시 테이블과 같은 복잡한 자료 구조의 사용, 가비지 수집 등으로 인해 메모리 참조 패턴이 불규칙해졌다.

운영체제 커널 아키텍처의 변화 또한 페이지 교체 알고리즘에 영향을 주었다. 현대 OS 커널은 통합 가상 메모리와 파일 시스템 캐시를 가지고 있어, 페이지 교체 알고리즘은 사용자 프로그램 가상 주소 공간의 페이지와 캐시된 파일의 페이지를 모두 고려해야 한다. 페이지 교체의 목표는 메모리 대기 시간을 최소화하는 것이므로, 다른 커널 하위 시스템의 메모리 요구 사항도 고려해야 한다.

이러한 변화로 인해, 현대 커널 (리눅스, FreeBSD, 솔라리스)의 페이지 교체는 가상 메모리 하위 시스템의 상위 수준이 아닌, 범용 커널 메모리 할당기 수준에서 작동하는 경향을 보인다.

3. 페이지 교체 알고리즘의 종류

페이지 교체 알고리즘은 크게 지역적 교체 알고리즘과 전역적 교체 알고리즘으로 나눌 수 있다.

지역적 페이지 교체 알고리즘: 프로세스에서 페이지 부재가 발생하면, 해당 프로세스(또는 메모리 파티션을 공유하는 프로세스 그룹)에 속한 페이지 중에서 교체 대상을 선택한다. 워킹 집합 모델을 기반으로 하는 ''고정 분할'' 및 ''균형 집합'' 알고리즘이 주로 사용된다. 각 프로세스가 페이지 부재를 독립적으로 처리하여 일관된 성능을 보장하는 확장성이 장점이다.
전역적 페이지 교체 알고리즘: 메모리 내의 모든 페이지를 자유롭게 선택하여 교체할 수 있다. 전체 시스템 효율성을 높일 수 있다는 장점이 있다.^[1]

3. 1. 이론적으로 최적의 페이지 교체 알고리즘 (OPT)

이론적으로 최적의 페이지 교체 알고리즘(OPT, 투시 교체 알고리즘 또는 벨라디 최적 페이지 교체 정책이라고도 함)^[2]^[3]^[4]은 미래에 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다. 페이지를 스왑인해야 할 때 운영 체제는 다음에 가장 나중에 사용될 페이지를 스왑아웃한다. 예를 들어, 다음 6초 동안 사용되지 않을 페이지는 다음 0.4초 이내에 사용될 페이지보다 스왑아웃된다.

하지만, 이 알고리즘은 범용 운영 체제에서 구현할 수 없다. 왜냐하면 페이지가 사용되기까지 얼마나 걸릴지 정확하게 예측하는 것이 불가능하기 때문이다. 이러한 제한에도 불구하고, 근접 최적의 성능을 제공할 수 있는 알고리즘이 존재한다.^[5] 운영 체제는 프로그램에서 참조하는 모든 페이지를 추적하고, 해당 데이터를 사용하여 후속 실행에서 스왑인 및 스왑아웃할 페이지를 결정한다. 이 알고리즘은 프로그램의 첫 번째 실행에서는 근접 최적의 성능을 제공할 수 없지만, 프로그램의 메모리 참조 패턴이 실행할 때마다 비교적 일관된 경우에만 가능하다.

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

3. 2. NRU (Not Recently Used)

NRU (Not Recently Used) 알고리즘은 최근에 사용되지 않은 페이지를 우선적으로 교체하는 알고리즘이다. 이 알고리즘은 다음과 같이 작동한다.

페이지가 참조되면 해당 페이지의 참조 비트를 설정한다.
페이지가 변경(쓰기)되면 변경 비트를 설정한다.
이러한 비트 설정은 주로 하드웨어 (MMU)에 의해 수행되지만, 소프트웨어적으로도 가능하다.

일정 시간 간격으로 타이머 인터럽트가 발생하여 모든 페이지의 참조 비트를 지운다. 따라서 현재 타이머 간격 내에 참조된 페이지만 참조 비트를 가지게 된다. 페이지 교체가 필요할 때, 운영체제는 페이지들을 다음과 같이 네 가지 범주로 나눈다.

카테고리 0: 참조되지 않음, 변경되지 않음
카테고리 1: 참조되지 않음, 변경됨
카테고리 2: 참조됨, 변경되지 않음
카테고리 3: 참조됨, 변경됨

카테고리 3의 페이지는 타이머 인터럽트에 의해 참조 비트가 지워지면 카테고리 1의 페이지처럼 보일 수 있다. NRU 알고리즘은 가장 낮은 범주에 속하는 페이지를 무작위로 선택하여 교체한다. 즉, NRU 알고리즘은 변경 여부보다 참조 여부를 더 중요하게 고려한다. NRU는 마킹 알고리즘이므로

\tfrac{k}{k-h+1}

-경쟁적이다.

3. 3. FIFO (First-In First-Out)

FIFO(First-In First-Out) 알고리즘은 가장 먼저 들어온 페이지를 가장 먼저 교체하는 방식이다. 운영 체제에서 부기(bookkeeping)가 거의 필요하지 않아 오버헤드가 적다. 이름에서 알 수 있듯이, 운영 체제는 메모리의 모든 페이지를 큐에 보관하며, 가장 최근에 들어온 페이지가 뒤에, 가장 오래된 페이지가 앞에 위치한다. 페이지 교체가 필요할 때 큐의 맨 앞(가장 오래된 페이지)에 있는 페이지가 선택된다. FIFO는 구현이 간단하고 비용이 적게 들지만, 실제 응용 프로그램에서는 성능이 좋지 않아 수정 없이 사용되는 경우는 드물다. 이 알고리즘은 Bélády의 이상 현상이 발생할 수 있다.

간단히 말해, 페이지 부재(page fault)가 발생하면 메모리에 가장 오래 있었던 프레임이 교체된다.

FIFO 페이지 교체 알고리즘은 일부 수정된 형태로 OpenVMS 운영 체제에서 사용된다.^[6] 유효한 변환 테이블 참조가 있는 제한된 수의 항목을 건너뛰는 방식으로 부분적인 두 번째 기회(second chance)를 제공하며,^[7] 또한 페이지는 프로세스 작업 세트에서 시스템 전체 풀로 이동되어, 이미 재사용되지 않은 경우 복구될 수 있다.^[27] ^[28]

3. 4. Second-chance

Second-chance 페이지 교체 알고리즘은 FIFO 페이지 교체 알고리즘을 개선한 알고리즘이다. FIFO와 같이 큐의 맨 앞을 확인하지만, 바로 페이지를 교체하는 대신 참조 비트(Reference bit)를 확인한다. 참조 비트가 0이면 해당 페이지를 교체하고, 1이면 참조 비트를 0으로 지우고 큐의 맨 뒤로 보낸다. 마치 새 페이지가 들어온 것처럼 처리하는 것이다. 이를 원형 큐로 생각할 수도 있다.

만약 모든 페이지의 참조 비트가 1로 설정되어 있다면, 큐를 한 바퀴 돌아 다시 처음 페이지로 돌아왔을 때 해당 페이지를 교체한다. 이때는 참조 비트가 0으로 지워져 있기 때문이다. 모든 페이지의 참조 비트가 0이라면 Second-chance 알고리즘은 순수한 FIFO 알고리즘과 동일하게 동작한다.

Second-chance 알고리즘은 이름처럼 모든 페이지에게 "두 번째 기회"를 준다. 즉, 참조된 적이 있는 오래된 페이지는 최근에 사용되었을 가능성이 높으므로, 참조되지 않은 새 페이지보다 먼저 교체 대상이 되어서는 안 된다는 아이디어에 기반한다.

하지만 페이지 교체가 필요할 때 큐의 모든 페이지를 확인하고 큐를 조작해야 하므로, 대용량 메모리를 사용하고 응답 속도가 중요한 시스템에서는 예상치 못한 지연이 발생할 수 있다는 단점이 있다.

3. 5. Clock

Clock 알고리즘은 Second-chance 알고리즘을 개선한 효율적인 페이지 교체 알고리즘이다. 메모리에 있는 페이지들을 원형 목록으로 관리하며, '핸드'(포인터)가 마지막으로 검사된 페이지 프레임을 가리킨다. 페이지 부재가 발생하고 빈 프레임이 없으면, 핸드가 가리키는 페이지의 R(참조) 비트를 확인한다. R 비트가 0이면 새 페이지를 해당 페이지와 교체하고 핸드를 한 위치 앞으로 이동시킨다. R 비트가 1이면 해당 비트를 0으로 지우고 핸드를 다음 위치로 이동시킨 후, 이 과정을 반복하여 교체될 페이지를 찾는다.^[8] 이 알고리즘은 1969년 페르난도 J. 코르바토에 의해 처음으로 설명되었다.^[9]

Clock 알고리즘은 다음과 같은 다양한 변형 알고리즘을 가지고 있다.

GCLOCK: 일반화된 Clock 페이지 교체 알고리즘이다.^[30]
Clock-Pro: 최근 참조된 페이지에 대한 정보를 원형 목록으로 유지한다. 메모리에 있는 모든 M개의 페이지와 최근에 페이지 아웃된 M개의 페이지를 포함한다. 페이지 아웃된 페이지에 대한 이러한 추가 정보는 ARC에서 유지되는 정보와 유사하며, 큰 루프 및 일회성 스캔에서 LRU보다 더 나은 성능을 제공한다.^[31]
WSclock: Clock 알고리즘과 작업 집합(특정 시간 간격 동안 프로세스에서 사용될 것으로 예상되는 페이지 집합) 개념을 결합하여 알고리즘 성능을 향상시킨다. 실제로 "에이징" 알고리즘과 "WSClock" 알고리즘은 가장 중요한 페이지 교체 알고리즘으로 간주된다.^[33]^[34]
CAR (Clock with Adaptive Replacement): ARC와 비슷한 성능을 가지며, LRU와 Clock 알고리즘보다 훨씬 뛰어난 성능을 보이는 페이지 교체 알고리즘이다.^[35] CAR 알고리즘은 자동 조정되며, 사용자가 지정하는 매개변수가 필요하지 않다.

3. 6. LRU (Least Recently Used)

LRU(Least Recently Used)는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. NRU(Not Recently Used)와 이름은 비슷하지만, LRU는 단기간의 페이지 사용 기록을 유지하는 반면, NRU는 마지막 클럭 간격 동안의 사용 여부만 확인한다는 차이가 있다.^[16] LRU는 최근에 자주 사용된 페이지가 앞으로도 자주 사용될 것이라는 시간 지역성(Locality)을 기반으로 한다.

LRU는 이론적으로 최적(OPT)에 가까운 성능을 보이지만, 실제 구현에는 비용이 많이 든다. 이러한 비용을 줄이기 위해 다음과 같은 여러 구현 방법이 존재한다.

연결 리스트(Linked List) 사용: 메모리의 모든 페이지를 포함하는 연결 리스트를 사용한다. 리스트의 맨 뒤에는 가장 오랫동안 사용되지 않은 페이지가, 맨 앞에는 가장 최근에 사용된 페이지가 위치한다. 하지만 이 방법은 페이지가 참조될 때마다 리스트를 갱신해야 하므로 오버헤드가 크다.
하드웨어 카운터 사용: 하드웨어에 각 페이지 접근 시 증가하는 카운터를 둔다. 페이지 교체 시점에 가장 낮은 카운터 값을 가진 페이지를 선택한다. 그러나 이 방법은 하드웨어 지원이 필요하며, 운영체제가 모든 페이지의 카운터를 조사해야 하므로 현실적이지 않다.

구현 비용 문제로 인해, LRU와 유사하지만 더 효율적인 다른 알고리즘들이 고려되기도 한다.

LRU의 장점 중 하나는 통계적 분석이 가능하다는 것이다. 예를 들어, LRU는 관리되는 페이지 수에 비례하여 OPT 알고리즘보다 페이지 부재(Page Fault)를 N배 이상 발생시키지 않는다는 것이 증명되었다.

하지만 LRU는 특정 참조 패턴에서 성능이 저하되는 경향이 있다. 예를 들어, LRU 풀에 N개의 페이지가 있을 때, N+1개의 페이지 배열에 순차적으로 접근하는 애플리케이션은 매 접근마다 페이지 부재를 발생시킨다. 이러한 단점을 보완하기 위해 루프 참조 패턴을 감지하고 MRU(Most Recently Used)와 같은 다른 알고리즘으로 전환하는 등의 개선 방법이 연구되었다.

LRU의 변형 알고리즘은 다음과 같다.

LRU-K: K번째로 가장 최근에 접근한 시점이 가장 오래된 페이지를 교체한다. LRU-1은 일반적인 LRU와 같으며, LRU-2는 페이지를 두 번째로 마지막에 접근한 시점을 기준으로 교체한다. LRU-K는 시간 지역성을 개선한 알고리즘이다.^[16]
ARC(Adaptive Replacement Cache):^[17] 최근에 제거된 페이지의 기록을 유지하여 최근 접근 또는 빈번한 접근에 대한 우선순위를 동적으로 조정한다. 순차적 스캔에 강하다.^[19]
2Q:^[18] LRU 및 LRU/2 알고리즘을 개선한 알고리즘이다. 핫 패스(hot pass) 항목과 슬로우 패스(slow pass) 항목의 두 개의 큐를 사용한다. 항목은 먼저 슬로우 패스 큐에 배치되고 항목의 두 번째 접근 후 핫 패스 항목에 배치된다. 추가된 항목에 대한 참조가 LRU 및 LRU/2 알고리즘보다 더 오래 유지되므로 핫 패스 큐가 더 좋아 캐시 적중률을 향상시킨다.

3. 7. Random

Random 페이지 교체 알고리즘은 메모리 내의 임의의 페이지를 교체하는 방식으로, 페이지 참조를 추적하는 데 드는 오버헤드 비용을 제거한다. 일반적으로 FIFO보다 성능이 좋으며, 메모리 참조가 반복될 때는 LRU보다 낫다. 하지만 일반적으로 LRU가 실제 환경에서는 더 나은 성능을 보인다. OS/390은 전역 LRU 근사치를 사용하며, LRU 성능이 저하될 경우 무작위 교체로 전환한다. 또한, 인텔 i860 프로세서는 무작위 교체 정책을 사용했다^[20].^[38]

3. 8. NFU (Not Frequently Used)

NFU(Not Frequently Used, 자주 사용되지 않음) 페이지 교체 알고리즘은 각 페이지마다 카운터를 두어 참조될 때마다 1씩 증가시켜 사용 빈도를 측정한다. 이 카운터는 초기에는 0으로 설정되며, 페이지 교체가 필요할 때 카운터가 가장 낮은 페이지를 교체한다.^[1]

하지만 NFU 알고리즘은 사용 기간을 고려하지 않고 사용 빈도만 추적한다는 주요 문제점이 있다. 예를 들어, 다중 패스 컴파일러에서 첫 번째 패스 동안 많이 사용되었지만, 두 번째 패스에서는 필요하지 않은 페이지가 두 번째 패스에서 비교적 적게 사용된 페이지보다 높은 카운터 값을 가질 수 있다. 이 때문에 실제로 덜 필요한 페이지가 메모리에 남아있게 되어 성능 저하를 유발한다. OS 부팅 시에도 이와 유사한 상황이 발생할 수 있다.^[1]

페이지 테이블에 널 포인터 값이 포함된 경우, NFU는 LRU 알고리즘보다 페이지 부재를 적게 발생시킨다.^[1]

3. 9. Aging

에이징(Aging) 알고리즘은 NFU 알고리즘의 한 종류로, 페이지 사용 시간을 고려하여 개선된 알고리즘이다. 페이지 참조 횟수를 단순히 증가시키는 대신, 각 참조에 동일한 가중치를 부여하지 않고 페이지의 참조 카운터를 먼저 오른쪽으로 시프트(2로 나눔)한 다음 해당 이진수의 왼쪽에 참조 비트를 추가한다. 예를 들어, 어떤 페이지가 지난 6번의 클럭 틱 동안 1, 0, 0, 1, 1, 0의 참조 비트를 가졌다면, 참조 카운터는 시간 순서대로 10000000, 01000000, 00100000, 10010000, 11001000, 01100100과 같이 변화한다. 즉, 현재 시간에 가까운 페이지 참조가 오래전의 페이지 참조보다 더 큰 영향을 미치게 된다. 이는 최근에 참조되었지만 참조 빈도가 적은 페이지가 과거에 더 자주 참조된 페이지보다 우선순위가 높도록 보장한다. 따라서 페이지를 교체해야 할 때 가장 낮은 카운터를 가진 페이지가 선택된다.^[21]

다음은 에이징 알고리즘의 작동 예시이다.

시간	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와 달리 프로세서 정수의 비트 크기에 따라 가장 최근 16 또는 32의 시간 간격 내에서만 참조를 추적할 수 있다. 결과적으로 두 페이지가 모두 00000000의 참조 카운터를 가질 수 있지만, 한 페이지는 9개 간격 전에 참조되었고 다른 페이지는 1000개 간격 전에 참조되었을 수 있다. 일반적으로 지난 16개 간격 내의 사용량을 아는 것은 어떤 페이지를 교체할지 좋은 결정을 내리기에 충분하므로, 에이징은 적당한 가격으로 거의 최적의 성능을 제공할 수 있다.

3. 10. LDF (Longest Distance First)

LDF 알고리즘의 기본 아이디어는 LRU에서 사용된 참조 지역성의 개념이지만, LDF에서는 지역성이 사용된 참조가 아닌 거리에 기반한다는 차이점이 있다. LDF에서는 현재 페이지로부터 가장 먼 거리에 있는 페이지를 교체한다. 두 페이지가 동일한 거리에 있는 경우, 반시계 방향 회전에서 현재 페이지 다음의 페이지가 교체된다.

4. 추가 고려 사항

페이지 교체 알고리즘은 1960년대와 1970년대에 활발히 연구되었으며, LRU (최근 사용 안 함) 근사 및 작업 집합 알고리즘 개발로 이어졌다. 이후 하드웨어 및 소프트웨어 발전으로 페이지 교체 알고리즘에 대한 몇 가지 기본 가정이 무효화되면서 연구가 다시 활발해졌다. 이러한 추세는 다음과 같다.

주 기억 장치 크기 증가: 수 기가바이트의 주 메모리를 갖춘 시스템에서 모든 메모리 프레임을 주기적으로 확인하는 것은 비효율적이다.
메모리 계층 구조 확장: CPU 캐시 미스 비용 증가로 페이지 교체 알고리즘 효율성이 더욱 중요해졌다.
사용자 소프트웨어 참조 지역성 약화: 객체 지향 프로그래밍 기술 확산, 트리 및 해시 테이블과 같은 정교한 데이터 구조 사용, 가비지 수집 등장으로 메모리 참조 패턴이 복잡해졌다.

운영체제 커널 아키텍처 차이도 페이지 교체 알고리즘에 영향을 미친다. 최신 OS 커널은 통합 가상 메모리와 파일 시스템 캐시를 사용하므로, 페이지 교체 알고리즘은 사용자 프로그램 가상 주소 공간 페이지와 캐시된 파일 페이지를 모두 고려해야 한다. 페이지 교체 목표는 메모리 대기 시간을 최소화하는 것이므로, 다른 커널 하위 시스템의 메모리 요구 사항도 고려해야 한다. 따라서 현대 커널(리눅스, FreeBSD, 솔라리스)의 페이지 교체는 범용 커널 메모리 할당기 수준에서 작동하는 경향이 있다.

4. 1. Precleaning (사전 클리닝)

사전 클리닝(Precleaning)은 곧 교체될 가능성이 있는 'dirty' 페이지(내용이 변경되어 디스크에 다시 써야 하는 페이지)를 미리 디스크에 기록하여, 실제로 페이지 교체가 일어날 때 입출력(I/O) 시간을 줄이는 기법이다.

초기 가상 메모리 시스템에서는 전이중 채널을 통해 안정적인 저장소와 연결되어 있었기 때문에 페이지를 'clean'하게 만드는 데 걸리는 시간이 큰 문제가 되지 않았다. 클리닝 작업은 페이징과 겹쳐서 처리할 수 있었기 때문이다. 그러나 현대의 일반적인 하드웨어는 전이중 전송을 지원하지 않으므로, 대상 페이지를 클리닝하는 것이 문제가 된다.

사전 클리닝은 이러한 문제를 해결하기 위해 구현되었다. 이 메커니즘은 사전 클리닝된 페이지가 실제로 교체 대상으로 선택될 때쯤에는 입출력이 완료되어 'clean' 상태가 되도록 한다.

하지만 사전 클리닝은 '다음에' 교체될 페이지를 정확히 예측할 수 있다고 가정한다. 만약 너무 성급하게 사전 클리닝을 수행하면, 교체 대상으로 선택되기 전에 페이지가 다시 'dirty' 상태가 될 수 있으며, 이 경우 입출력 대역폭을 낭비하게 된다.

4. 2. (h,k)-페이징 문제

(h,k)-페이징 문제는 페이징 문제 모델의 일반화이다. h와 k를

h \leq k

를 만족하는 양의 정수라고 할 때, 크기가

h \leq k

인 캐시를 가진 알고리즘의 성능은 이론적으로 최적의 페이지 교체 알고리즘에 상대적으로 측정된다.

h 인 경우, 최적의 페이지 교체 알고리즘에 더 적은 자원을 제공한다. (h,k)-페이징 문제는 온라인 알고리즘과 최적 알고리즘의 캐시 크기를 개별적으로 매개변수화하여, 온라인 알고리즘의 성능을 최적 알고리즘의 성능과 비교하는 방법이다.

4. 3. 마킹 알고리즘

마킹 알고리즘은 페이지 교체 알고리즘의 한 종류이다. 각 페이지에는 해당 페이지의 표시(mark) 여부를 나타내는 비트가 연결되어 있다. 초기에는 모든 페이지가 표시되지 않은 상태로 설정된다. 페이지 요청 단계(작동 기간 또는 요청 시퀀스) 동안, 해당 단계에서 처음 요청되는 페이지는 표시 상태가 된다. 마킹 알고리즘은 이렇게 표시된 페이지를 절대 교체하지 않는 알고리즘이다.

ALG가 크기 k의 캐시를 사용하는 마킹 알고리즘이고, OPT가 크기 h의 캐시를 사용하는 최적 알고리즘일 때,

h \leq k

이면 ALG는

\tfrac{k}{k-h+1}

-경쟁적이다. 따라서 모든 마킹 알고리즘은

\tfrac{k}{k-h+1}

-경쟁률을 가진다.

LRU는 마킹 알고리즘이지만, FIFO는 마킹 알고리즘이 아니다.

4. 4. 보수적 알고리즘

k개 이하의 서로 다른 페이지 참조를 포함하는 연속된 요청 시퀀스에 대해 k개 이하의 페이지 부재가 발생하는 경우 보수적이라고 한다.

ALG가 크기가 k인 캐시를 가진 보수적 알고리즘이고, OPT가

h \leq k

크기의 캐시를 가진 최적 알고리즘이라면, ALG는

\tfrac{k}{k-h+1}

-경쟁적이다. 따라서 모든 보수적 알고리즘은

\tfrac{k}{k-h+1}

-경쟁적 비율을 달성한다.

LRU, FIFO, CLOCK는 보수적인 알고리즘이다.

4. 5. 참조 비트가 없는 하드웨어에서의 구현

일부 하드웨어에는 참조 비트가 존재하지 않아 페이지 교체를 효율적으로 수행하기 위한 별도의 기술이 필요하다.

VAX 하드웨어에서 실행되는 OpenVMS는 Secondary Page Caching (2차 페이지 캐싱)이라는 방식을 사용한다. VMS가 동작하는 VAX는 페이지가 수정되었는지 여부는 알 수 있지만, 페이지가 읽혔는지 여부는 반드시 알 수 없다. 작업 집합(일반적으로 프로세스 전용 메모리)에서 제거된 페이지는 일정 시간 동안 실제 메모리에 남아 있으면서 특수 목적 목록에 배치된다. 작업 집합에서 페이지를 제거하는 것은 페이지 교체 작업은 아니지만, 해당 페이지를 후보로 효과적으로 식별한다. 백업 저장소가 여전히 유효한 페이지(내용이 더럽지 않거나 보존할 필요가 없는 경우)는 자유 페이지 목록(Free Page List)의 꼬리에 배치되고, 백업 저장소에 쓰기를 해야 하는 페이지는 수정된 페이지 목록(Modified Page List)에 배치된다. 이러한 작업은 일반적으로 자유 페이지 목록의 크기가 조정 가능한 임계값 아래로 떨어질 때 트리거된다.

페이지는 기본적으로 임의의 방식으로 작업 집합 제거를 위해 선택될 수 있으며, 잘못된 선택이 이루어진 경우 향후 참조를 통해 해당 페이지가 실제 메모리에서 제거되기 전에 자유 또는 수정된 목록에서 검색될 수 있다는 기대를 가진다. 이러한 방식으로 참조된 페이지는 자유 또는 수정된 목록에서 제거되어 프로세스 작업 집합으로 다시 배치된다. 수정된 페이지 목록은 또한 여러 페이지 그룹으로 페이지를 백업 저장소에 기록할 수 있는 기회를 제공하여 효율성을 높인다. 그런 다음 이러한 페이지는 자유 페이지 목록에 배치될 수 있다. 자유 페이지 목록의 맨 위로 이동하는 페이지 시퀀스는 LRU 또는 NRU 메커니즘의 결과와 유사하며 전체적인 효과는 앞에서 설명한 2차 기회 알고리즘과 유사하다.

ARM에서 리눅스 커널은 참조 비트도 수정 비트도 없는 프로세서 네이티브 페이지 테이블과 필요한 비트가 있는 소프트웨어 유지 관리 페이지 테이블, 두 개의 페이지 테이블을 제공하여 하드웨어 기능의 부족을 보완한다. 소프트웨어 유지 관리 테이블의 에뮬레이션된 비트는 페이지 폴트에 의해 설정된다. 페이지 폴트를 얻기 위해 두 번째 테이블에서 에뮬레이션된 비트를 지우면 기본 테이블을 변경하여 구현되는 해당 페이지에 대한 일부 액세스 권한이 취소된다.

4. 6. 리눅스 커널의 페이지 캐시

리눅스는 통합 페이지 캐시를 사용한다.^[22]^[23]

`brk`와 익명 `mmap`된 영역. 여기에는 힙과 스택과 같은 사용자 공간 프로그램이 포함된다. 페이지 아웃될 때 스왑에 기록된다.
비 익명(파일 백업) `mmap`된 영역. 메모리에 있고 개인적으로 수정되지 않은 경우 물리적 페이지는 파일 캐시 또는 버퍼와 공유된다.
`shm_open`을 통해 획득한 공유 메모리.
tmpfs 메모리 내 파일 시스템; 페이지 아웃될 때 스왑에 기록된다.
파일 캐시 포함; 페이지 아웃될 때 기본 블록 스토리지에 기록된다(아래 버퍼를 거칠 수 있음).
블록 장치의 캐시, 리눅스에서는 "버퍼"라고 한다(익명 파이프 및 리눅스 내부에서 사용되는 버퍼와 같은 버퍼라고도 불리는 다른 구조와 혼동하지 말 것); 페이지 아웃될 때 기본 스토리지에 기록된다.

통합 페이지 캐시는 CPU에서 지원하는 최소 페이지 크기(ARMv8, x86 및 x86-64에서 4KiB) 단위로 작동하며, 리눅스에서는 "거대한 페이지"라고 하는 다음 더 큰 크기(x86-64에서 2MiB)의 일부 페이지가 있다. 페이지 캐시의 페이지는 "활성" 세트와 "비활성" 세트로 나뉜다. 두 세트 모두 페이지의 LRU 목록을 유지한다. 기본적으로 사용자 공간 프로그램에서 페이지에 액세스하면 비활성 세트의 헤드에 배치된다. 반복적으로 액세스하면 활성 목록으로 이동한다. 리눅스는 필요에 따라 활성 세트에서 비활성 세트로 페이지를 이동하여 활성 세트가 비활성 세트보다 작도록 한다. 페이지가 비활성 세트로 이동되면 물리적 메모리에서 페이지 아웃되지 않고 모든 프로세스 주소 공간의 페이지 테이블에서 제거된다. 페이지가 비활성 세트에서 제거되면 물리적 메모리에서 페이지 아웃된다. "활성" 및 "비활성" 목록의 크기는 `/proc/meminfo`의 "Active", "Inactive", "Active(anon)", "Inactive(anon)", "Active(file)" 및 "Inactive(file)" 필드에서 쿼리할 수 있다.

참조

_[1] 웹사이트 Operating Systems Course Notes: Virtual Memory http://www2.cs.uic.e[...] 2017-07-21
_[2] 웹사이트 CS111 Lecture 11 notes http://www.read.cs.u[...]
_[3] 학회자료 Characterization of Web reference behavior revisited: Evidence for Dichotomized Cache management Springer-Verlag 2003-02-12
_[4] 웹사이트 22C:116 Lecture Notes http://www.cs.uiowa.[...] 2008-03-18
_[5] 학회자료 Back to the Future: Leveraging Belady's Algorithm for Improved Cache Replacement https://www.cs.utexa[...] IEEE 2016
_[6] 서적 Operating system concepts John Wiley & Sons 2004-12-14
_[7] 문서 VMS Help — Sys Parameters, TBSKIPWSL http://mx.isti.cnr.i[...]
_[8] 서적 Modern Operating Systems https://archive.org/[...] Prentice-Hall 2001
_[9] 서적 Festschrift: In Honor of P. M. Morse MIT Press
_[10] 논문 Sequentiality and prefetching in database systems ACM 1978-09
_[11] 학회자료 CLOCK-Pro: an effective improvement of the CLOCK replacement http://www.cse.ohio-[...] USENIX Association 2009-03-24
_[12] 학회자료 WSCLOCK—a simple and effective algorithm for virtual memory management http://infolab.stanf[...] ACM 1981-12-14
_[13] 웹사이트 WSClock http://www.cs.nyu.ed[...] 2019-06-12
_[14] 웹사이트 Page Replacement Algorithms http://www.informit.[...] 2019-06-12
_[15] 학회자료 CAR: Clock with Adaptive Replacement http://usenix.org/pu[...] USENIX Association 2004-03-31
_[16] 학회자료 The LRU-K page replacement algorithm for database disk buffering https://www.cs.cmu.e[...] ACM 1993-05-25
_[17] 학회자료 ARC: A Self-Tuning, Low Overhead Replacement Cache http://www.usenix.or[...] USENIX Association 2003-03-31
_[18] 학회자료 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm http://www.vldb.org/[...] Morgan Kaufmann 2005-07-31
_[19] 논문 Outperforming LRU with an Adaptive Replacement Cache Algorithm http://dbs.uni-leipz[...] IEEE Computer Society 2013-09-20
_[20] 학회자료 The Bus Interface and Paging Units of the i860 Microprocessor IEEE 1989-10-02
_[21] 서적 Modern Operating Systems Pearson 2015
_[22] 문서 See explanation at the start of /mm/workingset.c in the Linux source https://github.com/t[...]
_[23] 뉴스 Better active/inactive list balancing https://lwn.net/Arti[...] LWN.net 2012-05-02
_[24] 문서 Lecture Notes http://www.cs.uiowa.[...] Douglas W. Jones 1995
_[25] 문서 2006fall:notes:lec11 CS111 http://www.read.cs.u[...]
_[26] 문서 Characterization of Web reference behavior revisited: Evidence for Dichotomized Cache management http://cat.inist.fr/[...]
_[27] 문서 Operating Systems Concepts (Seventh Edition). Abraham Silberschatz, Peter Baer Galvin, Greg Gagne
_[28] 문서 VMS Help ログイン必要 http://mx.isti.cnr.i[...]
_[29] 문서 Modern Operating Systems (Second Edition) Andrew S. Tanenbaum 2001
_[30] 문서 Sequentiality and prefetching in database systems http://portal.acm.or[...]
_[31] 문서 CLOCK-Pro: An Effective Improvement of the CLOCK Replacement http://www.cse.ohio-[...] Song Jiang, Feng Chen, and Xiaodong Zhang 2005
_[32] 문서 WSCLOCK—a simple and effective algorithm for virtual memory management http://portal.acm.or[...] Richard W. Carr and John L. Hennessy 1981
_[33] 문서 WSClock http://www.cs.nyu.ed[...] Allan Gottlieb
_[34] 문서 Page Replacement Algorithms http://www.informit.[...] Andrew S. Tanenbaum 2002
_[35] 학회자료 CAR: Clock with Adaptive Replacement http://citeseerx.ist[...] 2012-02-19
_[36] 문서 ARC: A Self-tuning, low overhead replacement cache http://www.almaden.i[...]
_[37] 간행물 Outperforming LRU with an Adaptive Replacement Cache Algorithm http://www.almaden.i[...] IEEE Computer Magazine 2004-04
_[38] 학회자료 The Bus Interface and Paging Units of the i860(tm) Microprocessor

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com