페이지 치환 알고리즘

가상 메모리 관리에 페이징을 사용하는 컴퓨터 운영 체제에서 페이지 교체 알고리즘은 메모리 페이지를 할당해야 할 때 페이지 아웃(스왑 아웃 또는 디스크에 쓰기)할 메모리 페이지를 결정합니다.페이지 치환은 요청된 페이지가 메모리에 없는 경우(페이지 장애) 빈 페이지가 할당되지 않은 경우 또는 빈 페이지 수가 임계값보다 적기 때문에 할당을 충족하기 위해 사용할 수 없는 경우에 발생합니다.

교체 대상으로 선택되고 페이징 아웃된 페이지를 다시 참조할 경우 페이징 인(디스크에서 읽기)해야 하며, 여기에는 I/O 완료를 기다리는 작업이 포함됩니다.페이지 치환 알고리즘의 품질을 결정합니다.페이지인 대기 시간이 짧을수록 알고리즘이 향상됩니다.페이지 치환 알고리즘은 하드웨어에 의해 제공되는 페이지에 대한 액세스에 관한 제한된 정보를 확인하고, 이를 알고리즘 자체의 비용(프라이머리 스토리지 및 프로세서 시간)과 균형을 유지하면서 페이지 누락의 총 수를 최소화하기 위해 어떤 페이지를 치환해야 하는지 추측합니다.

페이지 치환 문제는 최적의 결정론적 알고리즘을 알고 있다는 점에서 경쟁 분석의 관점에서 전형적인 온라인 문제입니다.

역사

페이지 치환 알고리즘은 1960년대와 1970년대에 연구와 논쟁의 뜨거운 주제였다.이는 대부분 정교한 LRU(최신 사용 빈도가 낮은) 근사치와 작업 세트 알고리즘의 개발로 마무리되었습니다.그 후, 기존의 페이지 치환 알고리즘에 의한 몇 가지 기본적인 가정은 무효가 되어, 연구가 부활했다.특히, 기반이 되는 하드웨어 및 사용자 레벨의 소프트웨어의 동작에 있어서의 다음의 경향은, 페이지 치환 알고리즘의 퍼포먼스에 영향을 주고 있습니다.

primary 스토리지의 크기가 몇 배나 증가했습니다.몇 기가바이트의 프라이머리 메모리를 사용하면 메모리 프레임 하나하나를 정기적으로 체크해야 하는 알고리즘은 점점 실용성이 떨어지고 있습니다.
메모리 계층이 더 커졌습니다.CPU 캐시 미스 비용은 훨씬 더 비쌉니다.이로 인해 이전 문제가 악화됩니다.
사용자 소프트웨어의 참조 위치가 약해졌다.이는 다수의 작은 함수를 선호하는 객체 지향 프로그래밍 기술의 확산, 혼란스러운 메모리 참조 패턴을 초래하기 쉬운 트리나 해시 테이블과 같은 정교한 데이터 구조의 사용, 애플리케이션의 메모리 액세스 동작을 크게 바꾼 가비지 컬렉션의 출현에 주로 기인한다..

페이지 치환 알고리즘의 요건은 운영체제 커널 아키텍처의 차이로 인해 변경되었습니다.특히 최신 OS 커널의 대부분은 가상 메모리와 파일 시스템 캐시가 통합되어 있기 때문에 페이지 치환 알고리즘은 사용자 프로그램의 가상 주소 공간과 캐시된 파일의 양쪽 페이지에서 페이지를 선택해야 합니다.후자의 페이지에는 특정 속성이 있습니다.예를 들어, 문서철에 의해 기록 순서가 지정되거나 잠길 수 있습니다.게다가 페이지 치환의 목적은 메모리 대기 시간을 최소화하는 것이기 때문에 메모리를 할당하는 다른 커널 서브시스템에 의해 부과되는 메모리 요건을 고려해야 합니다.따라서 최신 커널(Linux, FreeBSD 및 Solaris)의 페이지 교체는 가상 메모리 서브시스템의 상위 레벨이 아닌 범용 커널 메모리 할당자 수준에서 작동하는 경향이 있습니다.

로컬 치환과 글로벌 치환

치환 알고리즘은 로컬 또는 글로벌할 수 있습니다.

프로세스에 페이지 장애가 발생하면 로컬페이지 치환 알고리즘은 같은 프로세스(또는 메모리 파티션을 공유하는 프로세스 그룹)에 속하는 페이지를 치환용으로 선택합니다.글로벌 치환 알고리즘은 메모리 내의 임의의 페이지를 자유롭게 선택할 수 있습니다.

로컬 페이지 치환에서는 특정 프로세스 또는 프로세스 그룹에 할당하는 페이지 수를 결정하는 메모리 파티셔닝의 형태를 상정하고 있습니다.파티셔닝의 가장 일반적인 형태는 고정 파티셔닝과 작업 세트 모델에 기반한 균형 세트 알고리즘입니다.로컬 페이지 치환의 장점은 확장성입니다.각 프로세스가 페이지 장애를 개별적으로 처리할 수 있기 때문에 프로세스의 퍼포먼스가 보다 일관되게 유지됩니다.다만, 글로벌 페이지의 치환은 시스템 ^[1]전체에서 보다 효율적입니다.

참조 및 수정된 페이지 감지

현대의 범용 컴퓨터와 일부 임베디드 프로세서는 가상 메모리를 지원합니다.각 프로세스에는 독자적인 가상 주소 공간이 있습니다.페이지 테이블은 프로세스 가상 주소의 서브셋을 물리 주소에 매핑합니다.또한 대부분의 아키텍처에서 페이지 테이블은 페이지 테이블의 각 페이지에 대해 "접근" 비트와 "더러운" 비트를 보유하고 있습니다.CPU는 프로세스가 해당 페이지에서 메모리를 읽거나 쓸 때 액세스 비트를 설정합니다.프로세스가 해당 페이지에 메모리를 쓸 때 CPU는 더티 비트를 설정합니다.operating system은, 액세스와 더티 비트를 변경할 수 있습니다.operating system은, 다음의 방법으로 메모리와 파일에의 액세스를 검출할 수 있습니다.

프로세스의 페이지 테이블에 있는 페이지의 액세스 비트를 클리어 합니다.잠시 후 OS는 페이지 테이블을 스캔하여 CPU에 의해 액세스 비트가 설정된 페이지를 찾습니다.이는 액세스 비트가 CPU에 의해 자동으로 설정되기 때문에 고속이며 OS는 액세스 알림을 즉시 수신하지 않으며 프로세스가 이러한 페이지에 액세스한 순서에 대한 정보도 제공하지 않기 때문에 정확하지 않습니다.
물리 메모리에서 삭제할 필요 없이 프로세스의 페이지 테이블에서 페이지를 삭제합니다.이 페이지에 대한 다음 액세스는 페이지 장애를 일으키기 때문에 즉시 검출됩니다.페이지 장애에는 OS로의 컨텍스트 전환, 대응하는 물리 주소의 소프트웨어 검색, 페이지 테이블의 변경 및 프로세스로의 컨텍스트 전환이 수반되기 때문에 속도가 느리고 액세스가 발생한 직후에 검출되기 때문에 정확합니다.
프로세스에서 다음과 같이 잠재적으로 페이지 캐시에 액세스하는 시스템 호출을 직접 실행할 때read그리고.writePOSIX에서.

프리클리닝

대부분의 치환 알고리즘은 결과로서 타겟 페이지를 반환할 뿐입니다.즉, 타깃 페이지가 더러울 경우(즉, 페이지를 회수하기 전에 안정적인 스토리지에 기록해야 하는 데이터를 포함), 해당 페이지를 안정적인 스토리지로 보내기 위해(페이지를 정리하기 위해) I/O를 시작해야 합니다.가상 메모리의 초기 단계에서는 가상 메모리가 안정적인 스토리지에 대한 전이중 채널을 가진 시스템에 처음 구현되고 클리닝이 일반적으로 페이징과 겹쳤기 때문에 클리닝에 소요되는 시간은 크게 문제가 되지 않았습니다.한편, 현대의 범용 하드웨어는 전이중 전송을 서포트하고 있지 않기 때문에, 타겟 페이지의 클리닝이 문제가 됩니다.

이러한 상황에 대처하기 위해 다양한 사전 청소 정책을 시행합니다.프리클리닝은 (아마도) 곧 교체될 지저분한 페이지에서 I/O를 시작하는 메커니즘입니다.즉, 실제로 사전 클리닝된 페이지가 교체 대상으로 선택될 때까지 I/O가 완료되고 페이지가 깨끗해집니다.프리클리닝에서는, 다음에 교환할 페이지를 특정할 수 있는 것을 전제로 하고 있습니다.너무 급하게 프리클리닝을 하면 교체 대상으로 선택되기 전에 다시 디테일링할 수 있는 페이지를 쓰기 때문에 I/O 대역폭이 낭비될 수 있습니다.

예상 페이징

디맨드 페이징을 사용하는 시스템에 따라서는, 실제로 페이지가 요구될 때까지 기다렸다가 RAM에 로드하는 것이 있습니다.

다른 시스템에서는 RAM에 없는 페이지가 곧 필요할 것으로 예상하여 해당 페이지가 요구되기 전에 RAM에 미리 로드함으로써 지연을 줄이려고 합니다.(이것은, 현재 RAM내의 어느 페이지가 곧바로 필요 없는지를 추측해, 스토리지에 미리 기입하는 프리 클리닝과 조합하는 경우가 많습니다).

페이지 장애가 발생하면 "예상 페이징" 시스템은 참조된 페이지뿐만 아니라 다음 몇 페이지(CPU의 프리페치 입력 큐와 유사)도 가져옵니다.

스와프 프리페치메커니즘은 (연속되지 않더라도) 곧 필요할 것 같은 페이지를 로드하는 데 더 많은 도움이 됩니다.

(h,k) 페이징 문제

(h,k) 페이징 문제는 페이징 문제의 모델을 일반화한 것입니다.h,k를 h ${\$ $h\leq k$ \ $displaystyle$ h \ $leq$ k와 $h\leq k$ 양의 정수라고 합니다.이론적으로 최적의 페이지 치환 알고리즘에 대해 $h\leq k$ k \ $displaystyle$ h \ $leq$ k의 $h\leq k$ 캐시를 가진 알고리즘의 성능을 측정합니다.h $h<k$ < $h<k$ \ $displaystyle$ h < $h<k$ k $h<k$ 의 $h<k$ , 보다 적은 리소스로 최적의 페이지 치환 알고리즘을 제공합니다.

(h,k) 페이징 문제는 온라인 알고리즘의 성능을 최적 알고리즘의 성능과 비교하여 온라인 알고리즘과 최적 알고리즘의 캐시 크기를 개별적으로 파라미터화하는 방법을 측정하는 방법입니다.

마킹 알고리즘

마킹 알고리즘은 페이징 알고리즘의 일반적인 클래스입니다.각 페이지에 대해 마크라고 불리는 비트와 관련짓습니다.처음에는 모든 페이지를 표시 안 함으로 설정합니다.페이지 요청 단계에서 이 단계에서 처음 요청되었을 때 페이지를 표시합니다.마킹 알고리즘은 마킹된 페이지를 페이지 아웃하지 않는 알고리즘입니다.

ALG가 캐시 크기가 k인 마킹알고리즘이고 OPT가 캐시 크기가 h인 최적의 알고리즘인 경우( $h\leq k$ ${\tfrac {k}{k-h+1}}$ $h\leq k$ \ $displaystyle$ h \ $leq$ k ) $h\leq k$ ALG는 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + 1 \ $displaystyle$ \ $tfrac$ { k ${\tfrac {k}{k-h+1}}$ } { k - h + $1$ - competitive ${\tfrac {k}{k-h+1}}$ 。따라서 모든 마킹 알고리즘은 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + ${\tfrac {k}{k-h+1}}$ (\ $displaystyle\tfrac {k}{k-h+1})$ - ${\tfrac {k}{k-h+1}}$ 에 ${\tfrac {k}{k-h+1}}$ 도달합니다.

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

보수적인 알고리즘

알고리즘은 k개 이하의 개별 페이지 참조를 포함하는 연속된 요청 시퀀스에서 k개 이하의 페이지 장애가 발생할 경우 보수적입니다.

ALG가 캐시 크기가 k인 보수적인 알고리즘이고 OPT가 캐시 $h\leq k$ 가 h $µk인$ 최적의 알고리즘인 경우 ALG는 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + ${\tfrac {k}{k-h+1}}$ (\ $displaystyle {k}{k-h+1})$ 입니다 ${\tfrac {k}{k-h+1}}$ .따라서 모든 보수적인 알고리즘은 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + $($ 스타일 { $tfrac {k}{k-h+1})$ - ${\tfrac {k}{k-h+1}}$ 에 ${\tfrac {k}{k-h+1}}$ 도달합니다.

LRU, FIFO 및 CLOCK은 보수적인 알고리즘입니다.

페이지 치환 알고리즘

페이지 치환 ^[2]알고리즘에는 다음과 같은 종류가 있습니다.

이론적으로 최적의 페이지 치환 알고리즘

이론적으로 최적의 페이지 치환 알고리즘(OPT, 클리어 보이언트 치환 알고리즘 또는 벨라디의 최적의 페이지 치환 ^[3]^[4]^[2]정책이라고도 함)은 다음과 같은 기능을 하는 알고리즘입니다.페이지를 교환할 필요가 있는 경우는, operating system은, 장래에 가장 오래 사용할 수 있는 페이지를 스왑 아웃 합니다.예를 들어, 다음 6초 동안 사용되지 않는 페이지는 다음 0.4초 내에 사용될 페이지에 걸쳐 스왑 아웃됩니다.

이 알고리즘은 범용 운영체제에서는 구현할 수 없습니다.이는 페이지가 사용될 때까지의 시간을 신뢰성 있게 계산하는 것이 불가능하기 때문입니다.단, 시스템에서 실행되는 모든 소프트웨어가 사전에 알려져 있고 메모리 참조 패턴의 정적 분석 또는 응용 프로그램 클래스만 가능한 경우를 제외합니다.실행 시간 분석을 가능하게 합니다.이러한 제한에도 불구하고 최적의 성능을 제공할 수 있는 알고리즘이^{[citation needed]} 존재합니다.운영체제는 프로그램에서 참조되는 모든 페이지를 추적하고 이러한 데이터를 사용하여 다음 실행 시 스왑할 페이지를 결정합니다.이 알고리즘은 최적에 가까운 성능을 제공할 수 있지만, 프로그램의 첫 번째 실행에서는 제공할 수 없습니다.또, 프로그램의 메모리 참조 패턴이 실행될 때마다 비교적 일관성이 있는 경우에만 가능합니다.

페이징 문제의 분석은 온라인 알고리즘 분야에서도 이루어지고 있습니다.페이징 문제에 대한 랜덤화된 온라인 알고리즘의 효율은 상각된 분석을 사용하여 측정된다.

최근 사용되지 않음

NRU(Not recently used) 페이지 치환 알고리즘은 최근에 사용된 페이지를 메모리에 보관하는 알고리즘입니다.이 알고리즘은 다음 원리로 동작합니다.페이지가 참조되면 해당 페이지에 참조 비트가 설정되어 참조 비트로 표시됩니다.마찬가지로 페이지가 변경(쓰기)되면 변경된 비트가 설정됩니다.비트의 설정은 보통 하드웨어에 의해 이루어지지만 소프트웨어 레벨에서도 가능합니다.

일정한 시간 간격으로 타이머 인터럽트가 모든 페이지의 참조 비트를 트리거 및 클리어하므로 현재 타이머 인터럽트 내에서 참조되는 페이지만 참조 비트로 마킹됩니다.페이지를 교환할 필요가 있는 경우, operating system은 페이지를 다음의 4개의 클래스로 나눕니다.

3. 참조, 변경

2. 참조, 미수정

1. 참조되지 않음, 변경됨

0. 참조되지 않음, 수정되지 않음

페이지가 변경되어 참조되지 않는 것은 불가능하다고 생각되지만, 이는 클래스 3 페이지가 타이머 인터럽트에 의해 참조된 비트를 클리어 했을 때 발생합니다.NRU 알고리즘은 삭제할 최하위 카테고리에서 임의의 페이지를 선택합니다.따라서 위의 4개 페이지 카테고리 중 참조되지 않은 페이지나 수정되지 않은 페이지가 존재할 경우 NRU 알고리즘에 의해 대체됩니다.이 알고리즘은 변경되었지만 참조되지 않은 페이지(마지막 타이머 간격 내)가 고도로 참조되지 않은 페이지보다 덜 중요하다는 것을 의미합니다.

NRU는 ${\tfrac {k}{k-h+1}}$ 이므로 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + 1 $({$ - ${\tfrac {k}{k-h+1}}$ 입니다 ${\tfrac {k}{k-h+1}}$ .

선입선출

가장 간단한 페이지 치환 알고리즘은 FIFO 알고리즘입니다.First-In, First-Out(FIFO; 선입선출) 페이지 치환 알고리즘은 오버헤드가 낮은 알고리즘으로 운영 체제의 부기가 거의 필요하지 않습니다.이 개념은 이름에서 알 수 있습니다.운영체제는 메모리 내의 모든 페이지를 큐에 기록하고 가장 최근에 도착한 페이지와 가장 오래된 페이지가 앞에 도착합니다.페이지를 교체해야 할 경우 큐의 맨 앞에 있는 페이지(가장 오래된 페이지)가 선택됩니다.FIFO는 저렴하고 직관적이지만 실제 적용에서는 성능이 떨어진다.따라서 수정되지 않은 형태로 사용되는 경우는 거의 없습니다.이 알고리즘은 벨라디의 변칙을 경험합니다.간단히 말하면, 페이지 폴트에서는, 메모리에 가장 오래 보존되어 있던 프레임이 교환됩니다.

FIFO 페이지 치환 알고리즘은 OpenVMS 운영체제시스템에 의해 사용되며 약간의 수정이 ^[5]가해지고 있습니다.유효한 변환 테이블 ^[6]참조가 있는 엔트리를 몇 개만 건너뛰면 부분적으로 두 번째 기회가 주어집니다.또, 페이지는 프로세스 작업 세트로부터 시스템 전체의 풀로 이동해, 아직 재이용하고 있지 않은 경우는 복구할 수 있습니다.

FIFO는 보수적인 알고리즘이므로 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + $({$ - ${\tfrac {k}{k-h+1}}$ 입니다 ${\tfrac {k}{k-h+1}}$ .

세컨드 찬스

세컨드 찬스페이지 치환 알고리즘이라고 불리는 FIFO 페이지 치환 알고리즘의 변경 형태는 개선을 위해 적은 비용으로 FIFO보다 비교적 우수한 성능을 발휘합니다.이 기능은 FIFO와 마찬가지로 큐의 앞쪽을 보고 동작하지만, 즉시 페이지를 페이징 아웃하는 것이 아니라 참조 비트가 설정되어 있는지 확인합니다.설정되어 있지 않은 경우는, 페이지가 스왑 아웃 됩니다.그렇지 않으면 참조된 비트가 클리어되고 페이지가 큐의 뒤쪽에 삽입되며(새로운 페이지인 것처럼), 이 프로세스가 반복됩니다.이것은 순환 큐라고도 할 수 있습니다.모든 페이지에 참조 비트가 설정되어 있는 경우, 리스트의 첫 번째 페이지의 두 번째 페이지에서는 참조 비트가 클리어 되어 있기 때문에, 그 페이지는 스왑 아웃 됩니다.모든 페이지에 참조 비트가 클리어 되어 있는 경우, 두 번째 기회 알고리즘은 순수 FIFO로 퇴보합니다.

이름에서 알 수 있듯이 Second-chance는 모든 페이지에 "second-chance"를 부여합니다. 즉, 참조된 오래된 페이지는 사용 중이므로 참조되지 않은 새 페이지를 통해 스왑 아웃해서는 안 됩니다.

시계

클럭은 페이지가 목록 뒤로 계속 밀릴 필요가 없기 때문에 세컨드 찬스보다 더 효율적인 FIFO 버전이지만 세컨드 찬스와 같은 일반적인 기능을 수행합니다.클럭 알고리즘은, 메모리의 페이지의 순환 리스트를 보관 유지해, 「손」(반복기)이 리스트내의 마지막에 검사한 페이지 프레임을 가리킵니다.페이지 장애가 발생하고 빈 프레임이 존재하지 않으면 R(기준) 비트가 핸드 위치에서 검사됩니다.R이 0인 경우, "손"이 가리키는 페이지 대신 새 페이지가 배치되고 손이 한 위치 앞으로 이동합니다.그렇지 않으면 R 비트가 클리어되고 클럭 바늘이 증가하며 페이지가 ^[7]교체될 때까지 프로세스가 반복됩니다.이 알고리즘은 1969년 F. J. Corbato에 ^[8]의해 처음 설명되었습니다.

시계의 변종

GCLOCK: 범용 클럭 페이지 치환 알고리즘.^[9]
Clock-Pro는 메모리의 모든 M 페이지와 페이지 아웃된 최신 M 페이지를 포함하여 최근에 참조된 페이지에 대한 정보의 순환 목록을 유지합니다.페이지 아웃 페이지에 관한 이 추가 정보는 ARC에 의해 유지되는 유사한 정보와 마찬가지로 대규모 루프 및 ^[10]원타임스캔에서는 LRU보다 더 잘 동작합니다.
WS클럭^[11]Clock 알고리즘을 작업 세트(즉, 일정 시간 간격 동안 그 프로세스가 사용할 것으로 예상되는 페이지 세트)의 개념과 결합함으로써 알고리즘의 성능을 향상시킬 수 있다.실제로는, 「에이징」알고리즘과 「WSClock」알고리즘이 가장 중요한 페이지 치환 ^[12]^[13]알고리즘입니다.
Clock with Adaptive Replacement(CAR)는 ARC와 동등한 성능을 가진 페이지 치환 알고리즘으로 LRU와 ^[14]CLOCK를 모두 크게 능가합니다.알고리즘 CAR은 셀프튜닝으로 사용자 지정 매직파라미터가 필요 없습니다.

CLOCK은 보수적인 알고리즘이므로 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + $(\$ - competitive입니다 ${\tfrac {k}{k-h+1}}$ .

최근 사용

Last Regently Used(LRU; 가장 최근에 사용된 페이지) 치환 알고리즘은 이름적으로는 NRU와 비슷하지만 LRU가 짧은 시간 동안 페이지 사용률을 추적하는 반면 NRU는 마지막 클럭 간격의 사용률만 조사한다는 점이 다릅니다.LRU는 과거 몇 가지 명령에서 가장 많이 사용된 페이지가 다음 몇 가지 명령에서도 많이 사용될 수 있다는 생각에 따라 작동합니다.LRU는 이론적으로는 최적에 가까운 성능을 제공할 수 있지만(거의 적응형 교체 캐시와 동일) 실제 구현에는 비용이 많이 듭니다.이 알고리즘에는 비용을 절감하면서 성능을 최대한 유지하는 몇 가지 구현 방법이 있습니다.

가장 비싼 방법은 메모리 내의 모든 페이지를 포함하는 링크 목록을 사용하는 링크드 리스트 방식입니다.이 목록의 뒷면에는 가장 최근에 사용한 페이지가 있고 앞면에는 가장 최근에 사용한 페이지가 있습니다.이 구현의 비용은 목록의 항목을 모든 메모리 참조에서 이동해야 한다는 사실에 있습니다. 이는 매우 많은 시간이 걸리는 프로세스입니다.

하드웨어 지원이 필요한 다른 방법은 다음과 같습니다.하드웨어에 명령마다 증가하는64비트 카운터가 있다고 가정합니다.페이지에 액세스 할 때마다, 페이지 액세스시의 카운터와 같은 값을 취득합니다.페이지를 교체해야 할 때마다 운영체제는 카운터가 가장 낮은 페이지를 선택하여 스왑 아웃합니다.

구현 비용 때문에 LRU와 비슷하지만 구현 비용이 저렴한 알고리즘을 고려할 수 있습니다.

LRU 알고리즘의 중요한 장점 중 하나는 완전한 통계 분석에 대응할 수 있다는 것입니다.예를 들어 LRU는 OPT 알고리즘의 N배 이상의 페이지 장애를 일으킬 수 없다는 것이 증명되었습니다.OPT 알고리즘에서는 N은 관리 풀의 페이지 수에 비례합니다.

한편, LRU의 약점은 매우 일반적인 참조 패턴에서 성능이 저하되는 경향이 있다는 것입니다.예를 들어 LRU 풀에 N페이지가 있는 경우 N+1페이지 배열에 대한 루프를 실행하는 어플리케이션은 각 액세스에서 페이지 장애를 일으킵니다.대규모 어레이에서의 루프가 일반적이기 때문에 이러한 상황에서 보다 효율적으로 동작하도록 LRU를 수정하는 데 많은 노력을 기울였습니다.제안된 LRU 변경의 대부분은 루프 참조 패턴을 검출하여 Most Recently Used(MRU; 가장 최근에 사용됨)와 같은 적절한 치환 알고리즘으로 전환하려고 합니다.

LRU에서의 바리안트

LRU-K는^[15] 과거 K번째 액세스 거리가 가장 먼 페이지를 삭제합니다.예를 들어 LRU-1은 단순히 LRU이지만 LRU-2는 최종 액세스 시간에 따라 페이지를 삭제합니다.LRU-K는 LRU의 현지성이 시간적으로 크게 향상됩니다.
ARC 알고리즘은^[16] 최근 삭제된 페이지의 이력을 유지함으로써 LRU를 확장하고 이를 사용하여 최근 또는 빈번한 액세스로 프리퍼런스를 변경합니다.순차 스캔에 특히 내성이 있습니다.
2Q^[17] 알고리즘은 LRU 및 LRU/2 알고리즘으로 개선됩니다.2개의 큐(하나는 핫패스 항목용, 이제1개는 슬로패스 항목용)를 가지면 우선 슬로패스 큐에 아이템이 배치되고 그 다음에 핫패스 항목에 배치된 아이템에 대한 두 번째 액세스 후에 아이템은 슬로패스 큐에 배치됩니다.추가된 항목에 대한 참조는 LRU 및 LRU/2 알고리즘보다 오래 유지되므로 캐시의 히트 레이트를 향상시키는 핫패스 큐가 더 우수합니다.

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

LRU는 ${\tfrac {k}{k-h+1}}$ 이므로 ${\tfrac {k}{k-h+1}}$ - ${\tfrac {k}{k-h+1}}$ + ${\tfrac {k}{k-h+1}}$ 1(\ $displaystyle {k}{k-h+$ }) - competitive입니다 ${\tfrac {k}{k-h+1}}$ .

랜덤

랜덤 치환 알고리즘은 메모리 내의 랜덤페이지를 치환합니다.이것에 의해, 페이지 참조의 트래킹에 드는 오버헤드가 없어집니다.일반적으로는 FIFO보다 성능이 우수하며 메모리 참조를 루프하는 경우에는 LRU보다 우수하지만 실제로는 LRU가 더 우수합니다.OS/390은 글로벌 LRU 근사치를 사용하여 LRU 퍼포먼스가 저하되면 랜덤 치환으로 돌아갑니다.인텔 i860 프로세서는 랜덤 치환 정책을 사용했습니다(Rodehamel 1989^[19]).

자주 사용하지 않음(NFU)

NFU(Not Frequency Used) 페이지 치환 알고리즘에는 카운터가 필요하며 각 페이지에는 처음에는 0으로 설정된 자체 카운터가 1개씩 있습니다.각 클럭 간격마다 그 간격 내에 참조된 모든 페이지의 카운터는 1씩 증가합니다.실제로 카운터는 페이지가 사용되는 빈도를 추적합니다.따라서 카운터가 가장 낮은 페이지는 필요에 따라 스왑 아웃할 수 있습니다.

NFU의 주요 문제는 사용 시간에 관계없이 사용 빈도를 추적한다는 것입니다.따라서 멀티패스 컴파일러에서는 첫 번째 패스에서는 많이 사용되었지만 두 번째 패스에서는 필요하지 않은 페이지가 두 번째 패스에서는 비교적 적게 사용되는 페이지보다 선호됩니다.이는 높은 주파수 카운터가 있기 때문입니다.이로 인해 퍼포먼스가 저하됩니다.OS 의 기동 등, NFU 가 같은 동작을 하는 일반적인 시나리오도 있습니다.다행히 유사하고 더 나은 알고리즘이 존재하며 그 설명은 다음과 같습니다.

자주 사용되지 않는 페이지 치환 알고리즘은 페이지 테이블에 늘 포인터 값이 포함되어 있는 경우 가장 최근에 사용한 페이지 치환 알고리즘보다 적은 수의 페이지 장애를 생성합니다.

에이징

에이징 알고리즘은 NFU 알고리즘의 후속으로 사용시간을 인식하도록 수정되어 있습니다.참조되는 페이지의 카운터를 늘리는 것만으로 시간에 관계없이 페이지 참조를 동일하게 강조하는 것이 아니라 페이지의 참조 카운터를 오른쪽(2로 나눈 후 참조된 비트를 바이너리 숫자의 왼쪽에 추가합니다.예를 들어 페이지가 과거6 클럭틱에서 비트 1,0,0,1,1,0을 참조한 경우 참조된 카운터는 10000000, 01000000, 00100000, 10010000, 11001000, 0110010000과 같습니다.현재 시간에 가까운 페이지 참조는 오래 전의 페이지 참조보다 더 큰 영향을 미칩니다.이것에 의해, 보다 최근에 참조된 페이지는, 보다 빈번하게 참조된 페이지보다 우선도가 높아집니다.따라서 페이지를 교환해야 할 경우 카운터가 가장 낮은 페이지가 선택됩니다.

다음 Python 코드는 에이징 알고리즘을 시뮬레이트합니다. $V_{i}$ $({$ })는 $V_{i}$ 0으로 초기화되고 위에 설명된 대로 $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ $Ri$ ( $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ - $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ ) $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ $Vi$ $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ 1) $V_{i}\leftarrow (R_{i}\ll (k-1))|(V_{i}\gg 1)$ ( { $displaystyle V_{i}\lll$ ( $k-1$ (V_ ${i}\g$ 1) 연산자를 사용하여 업데이트됩니다.

부터 collections.displicate 수입품 순서  방어하다 시뮬레이션-에이징(Rs: 순서, k: 인트) -> 없음.:     「에이징을 시뮬레이트 합니다."""     인쇄물(' T R 비트 (0-){length}) 페이지 0-의 카운터{length}'.포맷(길이=렌(Rs)))     대 = [0] * 렌(Rs[0])     위해서 t, R 에 열거하다(Rs):         대[:] = [R[i] << > k - 1   V >> 1                  위해서 i, V 에 열거하다(대)]         인쇄물('{:02d}     {}[{}]'.포맷(t, R,                                               ', '.합류하다(['{:0{}b}'.포맷(V, k)                                                          위해서 V 에 대])))

5 클럭 틱에 걸쳐 6페이지에 대한 R비트의 예에서는 이 함수는 다음 출력을 출력합니다.이 출력에는 각 클럭 $틱$ t의 R비트와 바이너리 ^[20]표시의 각 페이지의 개별 $V_{i}$ 값 $(\$ i $V_{i}$ })가 나열됩니다.

>>>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 >>>시뮬레이션-에이징(Rs, k) 페이지 0 ~ 5의 t R 비트(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]

에이징은 (프로세서 정수의 비트사이즈에 따라) 최신 16/32 시간 간격의 참조만을 추적할 수 있다는 점에서 LRU와 다릅니다.따라서 한 페이지는 9개 간격 전에 참조되고 다른 한 페이지는 1000개 간격 전에 참조되었음에도 불구하고 두 페이지는 00000000의 카운터를 참조할 수 있습니다.일반적으로 과거 16 간격 내의 사용 상황을 알면 어느 페이지를 교환할지를 잘 결정할 수 있습니다.따라서 에이징은 적당한 가격으로 거의 최적의 성능을 제공할 수 있습니다.

Longest Distance First(LDF; 최장거리 우선) 페이지 치환 알고리즘

이 알고리즘의 배후에 있는 기본 개념은 LRU에서 사용되는 Locality of Reference입니다만, LDF에서는 사용되는 참조가 아닌 거리에 근거하고 있습니다.LDF에서 현재 페이지에서 가장 먼 곳에 있는 페이지를 교체합니다.두 페이지가 같은 거리에 있는 경우 현재 페이지 옆에 있는 반시계 회전 페이지가 ^{[citation needed]}교체됩니다.

구현 상세

참조 비트가 없는 하드웨어 기술

위에서 설명한 많은 기술은 각 페이지와 관련된 참조 비트의 존재를 전제로 하고 있습니다.일부 하드웨어에는 이러한 비트가 없기 때문에 효율적인 사용을 위해서는 비트가 없어도 잘 작동하는 기술이 필요합니다.

주목할 만한 예로는 OpenVMS를 실행하는 VAX 하드웨어가 있습니다.이 시스템은 페이지가 수정되었는지 여부를 인식하지만 반드시 페이지가 읽혔는지는 알 수 없습니다.이 접근방식은 Secondary Page Caching으로 알려져 있습니다.작업 세트(일반적으로 프로세스 전용 메모리)에서 삭제된 페이지는 물리 메모리에 일정 시간 남아 있는 동안 특수 목적 목록에 배치됩니다.작업 세트로부터 페이지를 삭제하는 것은 엄밀히 말하면 페이지 치환 조작은 아니지만, 실질적으로 그 페이지를 후보로 특정합니다.백업 스토어가 유효한 페이지(내용물이 더럽지 않은 페이지 또는 보존할 필요가 없는 페이지)는 Free Page List의 맨 끝에 배치됩니다.백업 저장소에 써야 하는 페이지는 수정된 페이지 목록에 배치됩니다.이러한 액션은 보통 Free Page List의 크기가 조정 가능한 임계값을 밑돌았을 때 트리거됩니다.

기본적으로 랜덤하게 작업 세트를 삭제하도록 페이지를 선택할 수 있습니다.선택이 적절하지 않을 경우 나중에 참조가 물리 메모리에서 삭제되기 전에 Free 또는 Modified 목록에서 해당 페이지를 가져올 수 있습니다.이 방법으로 참조된 페이지는 Free 또는 Modified 목록에서 삭제되고 프로세스 작업 세트에 다시 배치됩니다.수정된 페이지 목록은 또한 여러 페이지의 그룹으로 구성된 백업 저장소에 페이지를 쓸 수 있는 기회를 제공하여 효율성을 향상시킵니다.그런 다음 이러한 페이지를 빈 페이지 목록에 배치할 수 있습니다.프리 페이지 리스트의 선두에 도달하는 일련의 페이지는 LRU 또는 NRU 메커니즘의 결과와 비슷하며 전체적인 효과는 앞서 설명한 Second-Chance 알고리즘과 유사합니다.

또 다른 예는 ARM의 Linux 커널에서 사용됩니다.하드웨어 기능의 부족은 2개의 페이지 테이블, 즉 참조 비트도 더티 비트도 없는 프로세서 네이티브 페이지 테이블과 필요한 비트가 있는 소프트웨어 유지보수 페이지 테이블을 제공함으로써 보충됩니다.소프트웨어 유지 관리 테이블의 에뮬레이트 비트는 페이지 장애별로 설정됩니다.페이지 폴트를 취득하기 위해 두 번째 테이블에서 에뮬레이트된 비트를 클리어하면 네이티브 테이블을 변경함으로써 구현되는 대응하는 페이지에 대한 액세스 권한의 일부가 취소된다.

Linux 페이지 캐시

Linux는 통합 페이지 캐시를 사용하여

brk 익명의 ED-RESS가 있어요여기에는 사용자 공간 프로그램의 힙 및 스택이 포함됩니다.페이지 아웃이 되면 스왑 하도록 쓰여 있다.
익명이 아닌(파일 백업)mmaped 지역메모리에 존재하며 개인적으로 수정되지 않은 경우 물리적 페이지는 파일 캐시 또는 버퍼와 공유됩니다.
를 통해 취득한 공유 메모리.
tmpfs 인메모리 파일시스템. 페이징 아웃 시 스왑하도록 써집니다.
파일 캐시: 페이징 아웃 시 기본 블록 스토리지에 기록됨(버퍼를 통과할 수 있음, 아래 참조).
Linux에 의해 "버퍼"라고 불리는 블록 디바이스의 캐시(Linux에서 내부적으로 사용되는 파이프 및 버퍼에 사용되는 것과 같은 다른 구조와 혼동하지 마십시오). 페이징 아웃 시 기본 스토리지에 기록됩니다.

통합 페이지 캐시는 CPU가 지원하는 최소 페이지 크기(ARMv8, x86 및 x86-64의 경우 4KiB)의 유닛으로 동작하며, Linux에서는 "대용량 페이지"라고 불리는 다음 큰 페이지(x86-64의 경우 2MiB)도 있습니다.페이지 캐시의 페이지는, 「액티브」세트와 「비액티브」세트로 분할됩니다.두 세트 모두 페이지의 LRU 목록을 유지합니다.기본적인 경우, 사용자 공간 프로그램에 의해 페이지가 액세스되면 비활성 집합의 선두에 배치됩니다.반복적으로 액세스하면 활성 목록으로 이동합니다.Linux 에서는 액티브세트가 비액티브세트보다 작도록 필요에 따라 액티브세트에서 비액티브세트로 페이지를 이동합니다.페이지가 비활성 세트로 이동되면 물리 ^[21]^[22]메모리로부터 호출되지 않고 프로세스 주소 공간의 페이지 테이블에서 삭제됩니다.비활성 세트에서 페이지가 제거되면 물리적 메모리 부족으로 페이징됩니다."active" 및 "inactive" 목록의 크기는 다음 위치에서 쿼리할 수 있습니다./proc/meminfo"Active", "Inactive(비활성)", "Active(비활성)", "Inactive(비활성)", "Active(파일)" 및 "Inactive(파일)" 필드에 입력합니다.

작업 세트

프로세스의 작업 세트는 일정 시간 간격 동안 해당 프로세스가 사용할 것으로 예상되는 페이지 세트입니다.

'작업 세트 모델'은 엄밀한 의미에서 페이지 치환 알고리즘이 아닙니다(실제로 일종의 중기 ^{[clarification needed]}스케줄러입니다).

레퍼런스

^ Bell, John. "Operating Systems Course Notes: Virtual Memory". University of Illinois at Chicago College of Engineering. Archived from the original on 23 September 2018. Retrieved 21 July 2017.
^ ^a ^b Jones, Douglas W. "22C:116 Lecture Notes". University of Iowa Department of Computer Science. Archived from the original on 30 June 2012. Retrieved 18 March 2008.
^ Torrez, Paul; et al. "CS111 Lecture 11 notes". UCLA Computer Science Department. Archived from the original on 9 January 2009.
^ Bahn, Hyokyung; Noh, Sam H. (12–14 February 2003). Characterization of Web reference behavior revisited: Evidence for Dichotomized Cache management. International Conference on Information Networking 2003. Jeju, South Korea: Springer-Verlag. pp. 1018–1027. doi:10.1007/978-3-540-45235-5_100. ISBN 978-3-540-40827-7.
^ Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (14 December 2004). Operating system concepts (7th ed.). Hoboken, NJ, USA: John Wiley & Sons. p. 339. ISBN 0-47169-466-5. OCLC 56913661.
^ VMS 도움말 - 시스템 파라미터, TBSKIPWSL
^ Tanenbaum, Andrew S. (2001). Modern Operating Systems (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall. p. 218 (4.4.5). ISBN 978-0-13-031358-4. LCCN 00051666. OCLC 45284637. OL 24214243M.
^ Corbató, Fernando J. (1969). "A Paging Experiment with the Multics System" (PDF). Festschrift: In Honor of P. M. Morse. MIT Press. pp. 217–228.
^ Smith, Alan Jay (September 1978). "Sequentiality and prefetching in database systems". ACM Transactions on Database Systems. New York, NY, USA: ACM. 3 (3): 223–247. doi:10.1145/320263.320276. S2CID 11611563.
^ Jiang, Song; Chen, Feng; Zhang, Xiaodong (10–15 April 2005). CLOCK-Pro: an effective improvement of the CLOCK replacement (PDF). 2005 USENIX Annual Technical Conference. Anaheim, CA, USA: USENIX Association. p. 35. Archived (PDF) from the original on 12 June 2019. Retrieved 24 March 2009.
^ Carr, Richard W.; Hennessy, John L. (14–16 December 1981). WSCLOCK—a simple and effective algorithm for virtual memory management (gzipped PDF). Eighth ACM symposium on Operating systems principles. Pacific Grove, CA, USA: ACM. pp. 87–95. doi:10.1145/800216.806596. ISBN 0-89791-062-1. Archived from the original on 10 June 2007.
^ Gottlieb, Allan. "WSClock". New York University Computer Science Department. Archived from the original on 30 July 2012. Retrieved 12 June 2019.
^ Tanenbaum, Andrew S. "Page Replacement Algorithms". InformIT. Archived from the original on 10 September 2012. Retrieved 12 June 2019.
^ Bansal, Sorav & Modha, Dharmendra S. (31 March – 2 April 2004). CAR: Clock with Adaptive Replacement (PDF). 3rd USENIX Conference on File and Storage Technologies (FAST '04). San Francisco, CA, USA: USENIX Association. pp. 187–200. CiteSeerX 10.1.1.105.6057. Archived (PDF) from the original on 31 July 2004.
^ O'Neil, Elizabeth J.; et al. (25–28 May 1993). The LRU-K page replacement algorithm for database disk buffering (PDF). 1993 ACM SIGMOD international conference on Management of data. Washington, D.C., USA: ACM. pp. 297–306. CiteSeerX 10.1.1.18.1434. doi:10.1145/170035.170081. ISBN 0-89791-592-5. Archived (PDF) from the original on 6 September 2019.
^ Megiddo, Nimrod & Modha, Dharmendra S. (31 March – 2 April 2003). ARC: A Self-Tuning, Low Overhead Replacement Cache (PDF). 2nd USENIX Conference on File and Storage Technologies (FAST '03). San Francisco, CA, USA: USENIX Association. pp. 115–130. Archived (PDF) from the original on 8 February 2010.
^ Johnson, Theodore; Shasha, Dennis (12–15 September 1994). 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (PDF). 20th International Conference on Very Large Data Bases. Santiago de Chile, Chile: Morgan Kaufmann. pp. 439–450. ISBN 1-55860-153-8. Archived (PDF) from the original on 17 March 2020. Retrieved 31 July 2005.
^ Megiddo, Nimrod & Modha, Dharmendra S. (2004). "Outperforming LRU with an Adaptive Replacement Cache Algorithm" (PDF). Computer. IEEE Computer Society. 37 (4): 58. CiteSeerX 10.1.1.231.498. doi:10.1109/MC.2004.1297303. S2CID 5507282. Archived (PDF) from the original on 21 October 2012. Retrieved 20 September 2013.
^ Rhodehamel, Michael W. (2–4 October 1989). The Bus Interface and Paging Units of the i860 Microprocessor. 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors. Cambridge, MA, USA: IEEE. pp. 380–384. doi:10.1109/ICCD.1989.63392. ISBN 0-8186-1971-6. INSPEC Accession Number 3719504.
^ Tanenbaum, Andrew S.; Bos, Herbert (2015). Modern Operating Systems (4th ed.). Boston, MA, USA: Pearson. p. 215. ISBN 978-0-13-359162-0. OL 25620855M.
^ Linux 소스의 선두에 있는 설명을 참조해 주세요.
^ Corbet, Jonathan Corbet (2 May 2012). "Better active/inactive list balancing". LWN.net.

추가 정보

Wong, Kin-Yeung (23 January 2006). "Web cache replacement policies: a pragmatic approach". IEEE Network. IEEE. 20 (1): 28–34. doi:10.1109/MNET.2006.1580916. ISSN 0890-8044. S2CID 17969287. INSPEC Accession Number 8964134.
Aho, Alfred V.; Denning, Peter J.; Ullman, Jeffrey D. (January 1971). "Principles of Optimal Page Replacement". Journal of the ACM. New York, NY, USA: ACM. 18 (1): 80–93. doi:10.1145/321623.321632. S2CID 3154537.
Tanenbaum, Andrew S. (1997). Operating Systems: Design and Implementation (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall. ISBN 0-13-638677-6. LCCN 96037153. OL 998396M.
Tanenbaum, Andrew S. (2001). Modern Operating Systems (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall. ISBN 978-0-13-031358-4. LCCN 00051666. OCLC 45284637. OL 24214243M. 페이지 치환 알고리즘에 관한 온라인 발췌: 페이지 치환 알고리즘.
유리는, 기디언. Cao, 페이(15–18 1997년 6월).적응적 페이지 교체 기억 장치 참조 행동에 근거한다.1997년 컴퓨터 시스템의 측정 및 모델링에 ACMSIGMETRICS 국제 회의.시애틀, 워싱턴, USA:ACM.를 대신하여 서명함. 115–126. doi:10.1145/258612.258681.아이 에스비엔 0-89791-909-2.또한 확장 형식에 유리는, 기디언. Cao, 페이(1997년)이용할 수 있다."기술 보고서 1338년".컴퓨터 과학, 위스콘신 대학교 매디슨 캠퍼스.
Kim, Jong Min; et al. (17–21 October 2000). A Low-Overhead High-Performance Unified Buffer Management Scheme that Exploits Sequential and Looping References (PDF). 4th Usenix Symposium on Operating System Design and Implementation (OSDI'2000). Vol. 4. San Diego, CA, USA: USENIX Association. Archived (PDF) from the original on 18 September 2004.
Smaragdakis, Yannis; Kaplan, Scott; Wilson, Paul (1–4 May 1999). EELRU: simple and effective adaptive page replacement (PDF). 1999 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. Atlanta, GA, USA: ACM. pp. 122–133. doi:10.1145/301453.301486. ISBN 1-58113-083-X. Archived (PDF) from the original on 4 March 2016.
Jiang, Song; Zhang, Xiaodong (15–19 June 2002). LIRS: a Low Inter Reference recency Set replacement (PDF). 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems. Marina Del Rey, CA, USA: ACM. pp. 31–42. doi:10.1145/511334.511340. ISBN 1-58113-531-9. Archived (PDF) from the original on 12 June 2019.
Lee, Donghee; et al. (1–4 September 1997). Implementation and Performance Evaluation of the LRFU Replacement Policy. 23rd Euromicro Conference New Frontiers of Information Technology. Budapest, Hungary: IEEE Computer Society. pp. 106–111. doi:10.1109/EMSCNT.1997.658446. ISBN 0-8186-8215-9. INSPEC Accession Number 5856800.
Zhou, Yuanyuan; Philbin, James; Li, Kai (25–30 June 2001). The Multi-Queue Replacement Algorithm for Second-Level Buffer Caches (PDF). 2001 USENIX Annual Technical Conference. Boston, MA, USA: USENIX Association. pp. 91–104. ISBN 1-880446-09-X. Archived (PDF) from the original on 24 November 2005.

[1] Bell, John. "Operating Systems Course Notes: Virtual Memory". University of Illinois at Chicago College of Engineering. Archived from the original on 23 September 2018. Retrieved 21 July 2017.

[lecture_notes_jones-2] Jones, Douglas W. "22C:116 Lecture Notes". University of Iowa Department of Computer Science. Archived from the original on 30 June 2012. Retrieved 18 March 2008.

[3] Torrez, Paul; et al. "CS111 Lecture 11 notes". UCLA Computer Science Department. Archived from the original on 9 January 2009.

[4] Bahn, Hyokyung; Noh, Sam H. (12–14 February 2003). Characterization of Web reference behavior revisited: Evidence for Dichotomized Cache management. International Conference on Information Networking 2003. Jeju, South Korea: Springer-Verlag. pp. 1018–1027. doi:10.1007/978-3-540-45235-5_100. ISBN 978-3-540-40827-7.

[Silber-5] Silberschatz, Abraham; Galvin, Peter Baer; Gagne, Greg (14 December 2004). Operating system concepts (7th ed.). Hoboken, NJ, USA: John Wiley & Sons. p. 339. ISBN 0-47169-466-5. OCLC 56913661.

[6] VMS 도움말 - 시스템 파라미터, TBSKIPWSL

[Tanenbaum-7] Tanenbaum, Andrew S. (2001). Modern Operating Systems (2nd ed.). Upper Saddle River, NJ, USA: Prentice-Hall. p. 218 (4.4.5). ISBN 978-0-13-031358-4. LCCN 00051666. OCLC 45284637. OL 24214243M.

[8] Corbató, Fernando J. (1969). "A Paging Experiment with the Multics System" (PDF). Festschrift: In Honor of P. M. Morse. MIT Press. pp. 217–228.

[9] Smith, Alan Jay (September 1978). "Sequentiality and prefetching in database systems". ACM Transactions on Database Systems. New York, NY, USA: ACM. 3 (3): 223–247. doi:10.1145/320263.320276. S2CID 11611563.

[10] Jiang, Song; Chen, Feng; Zhang, Xiaodong (10–15 April 2005). CLOCK-Pro: an effective improvement of the CLOCK replacement (PDF). 2005 USENIX Annual Technical Conference. Anaheim, CA, USA: USENIX Association. p. 35. Archived (PDF) from the original on 12 June 2019. Retrieved 24 March 2009.

[11] Carr, Richard W.; Hennessy, John L. (14–16 December 1981). WSCLOCK—a simple and effective algorithm for virtual memory management (gzipped PDF). Eighth ACM symposium on Operating systems principles. Pacific Grove, CA, USA: ACM. pp. 87–95. doi:10.1145/800216.806596. ISBN 0-89791-062-1. Archived from the original on 10 June 2007.

[12] Gottlieb, Allan. "WSClock". New York University Computer Science Department. Archived from the original on 30 July 2012. Retrieved 12 June 2019.

[13] Tanenbaum, Andrew S. "Page Replacement Algorithms". InformIT. Archived from the original on 10 September 2012. Retrieved 12 June 2019.

[14] Bansal, Sorav & Modha, Dharmendra S. (31 March – 2 April 2004). CAR: Clock with Adaptive Replacement (PDF). 3rd USENIX Conference on File and Storage Technologies (FAST '04). San Francisco, CA, USA: USENIX Association. pp. 187–200. CiteSeerX 10.1.1.105.6057. Archived (PDF) from the original on 31 July 2004.

[15] O'Neil, Elizabeth J.; et al. (25–28 May 1993). The LRU-K page replacement algorithm for database disk buffering (PDF). 1993 ACM SIGMOD international conference on Management of data. Washington, D.C., USA: ACM. pp. 297–306. CiteSeerX 10.1.1.18.1434. doi:10.1145/170035.170081. ISBN 0-89791-592-5. Archived (PDF) from the original on 6 September 2019.

[16] Megiddo, Nimrod & Modha, Dharmendra S. (31 March – 2 April 2003). ARC: A Self-Tuning, Low Overhead Replacement Cache (PDF). 2nd USENIX Conference on File and Storage Technologies (FAST '03). San Francisco, CA, USA: USENIX Association. pp. 115–130. Archived (PDF) from the original on 8 February 2010.

[17] Johnson, Theodore; Shasha, Dennis (12–15 September 1994). 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm (PDF). 20th International Conference on Very Large Data Bases. Santiago de Chile, Chile: Morgan Kaufmann. pp. 439–450. ISBN 1-55860-153-8. Archived (PDF) from the original on 17 March 2020. Retrieved 31 July 2005.

[18] Megiddo, Nimrod & Modha, Dharmendra S. (2004). "Outperforming LRU with an Adaptive Replacement Cache Algorithm" (PDF). Computer. IEEE Computer Society. 37 (4): 58. CiteSeerX 10.1.1.231.498. doi:10.1109/MC.2004.1297303. S2CID 5507282. Archived (PDF) from the original on 21 October 2012. Retrieved 20 September 2013.

[19] Rhodehamel, Michael W. (2–4 October 1989). The Bus Interface and Paging Units of the i860 Microprocessor. 1989 IEEE International Conference on Computer Design: VLSI in Computers and Processors. Cambridge, MA, USA: IEEE. pp. 380–384. doi:10.1109/ICCD.1989.63392. ISBN 0-8186-1971-6. INSPEC Accession Number 3719504.

[20] Tanenbaum, Andrew S.; Bos, Herbert (2015). Modern Operating Systems (4th ed.). Boston, MA, USA: Pearson. p. 215. ISBN 978-0-13-359162-0. OL 25620855M.

[21] Linux 소스의 선두에 있는 설명을 참조해 주세요.

[22] Corbet, Jonathan Corbet (2 May 2012). "Better active/inactive list balancing". LWN.net.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

Search

페이지 치환 알고리즘

네임스페이스

더

목차

역사

로컬 치환과 글로벌 치환

참조 및 수정된 페이지 감지

프리클리닝

예상 페이징

(h,k) 페이징 문제

마킹 알고리즘

보수적인 알고리즘

페이지 치환 알고리즘

이론적으로 최적의 페이지 치환 알고리즘

최근 사용되지 않음

선입선출

세컨드 찬스

시계

시계의 변종

최근 사용

LRU에서의 바리안트

랜덤

자주 사용하지 않음(NFU)

에이징

Longest Distance First(LDF; 최장거리 우선) 페이지 치환 알고리즘

구현 상세

참조 비트가 없는 하드웨어 기술

Linux 페이지 캐시

작업 세트

레퍼런스

추가 정보