페이지 교체 알고리즘 (Page Replacement) - LRU

페이지 교체 알고리즘

페이지 교체 알고리즘

페이지 교체 알고리즘 가운데 가장 간단한 페이지 전환 알고리즘인 FIFO는 페이지가 교체될 때 메모리에서 가장 오래된 페이지를 드래그한다. 각 페이지는 페이지 변경 알고리즘을 로드하는 시간을 기록하고 로드 순서에 따라 FIFO 큐를 생성할 수 있다. 이렇게 하면 홈 페이지를 변경하고 열 끝에 다시 로드된 페이지를 삽입할 수 있습니다.

 

LRU 알고리즘

LRU 정책은 페이지 교환 알고리즘으로 사용되는 경우가 많으며, 좋은 알고리즘으로 인식됩니다. 문제는 어떻게 이 알고리즘을 시행하느냐 하는 것이다. LRU 페이지의 교환 알고리즘에는 하드웨어 지원이 필요합니다. 사진은 최근 사용한 시간 순으로 식별할 수 있어야 한다. 구현에는 두 가지 방법이 있습니다.

• 세컨드: 가장 간단한 방법으로 각 페이지 요소의 타임 필드를 입력하여 페이지 교체 알고리즘 논리 시계 또는 마커를 CPU에 추가합니다. 기억에 다가갈 때마다 시간이 늘어납니다. 페이지를 참조할 때마다 시간 로그 내용이 페이지의 "사용 시간" 필드에 복사됩니다. 이를 통해 각 페이지의 마지막 '시간' 참조를 유지할 수 있습니다.

 

시간값이 가장 낮은 페이지가 대체됩니다. 페이지 교체 알고리즘 기술을 사용하려면 페이지 테이블을 탐색하여 LRU 페이지를 찾고 각 페이지 교체 알고리즘 메모리 참조에 대해 메모리 쓰기 태스크(페이지 테이블 사용 시간 필드를 업데이트하려면)가 필요합니다. 시간값은 페이지 테이블(CPU 프로그래밍 등)이 변경될 때마다 관리하며 시간값을 초과하는 것도 고려해야 합니다.

● LFU 대체 정책을 구현하는 또 다른 방법은 페이지 번호 스택을 유지하는 것입니다. 페이지를 참조할 때마다 페이지 번호가 스택 중앙에서 삭제되고 분리됩니다.

 

LRU를 교체하는 것은 Bellady에서 가능한 최고의 교체와 모순되지 않습니다. 일부 페이지 교체 알고리즘은 벨라디와의 모순을 보이지 않는다. 이 알고리즘은 밀착 알고리즘이라고 합니다. 스택 알고리즘은 프레임워크의 페이지 집합이 항상 n + 1 페이지의 하위 집합인지 여부에 관계없이 알고리즘이다.

 

LRU를 교체하는 경우 저장된 페이지는 최신 버전이 아닙니다. 체크의 수가 아무리 많아도 이 페이지는 여전히 마지막 페이지여서 기억에 남는다. LRU는 물론 스택 알고리즘입니다.

두 IRL 구현 방법 모두 TLB 등록 표준보다 높은 하드웨어 지원을 가져야 한다. 각 메모리 참조에서 카운터와 스택 값을 업데이트해야 한다. 소프트웨어에서 이러한 작업을 수행하는 데 인터럽트를 사용하면 메모리 참조가 최소 10배 이상 느려지고 모든 프로세스의 실행 속도가 느려진다. 이 메모리 관리를 관리할 수 있는 시스템은 거의 없다.

LRU 근사 페이지 교체

LRU 근사 페이지는 LRU 알고리즘의 최적 동작을 근사화하는 페이지 알고리즘입니다. 최적의 LRU 알고리즘은 가장 오래 사용하지 않는 페이지를 대체하지만 구현하기 어렵습니다.

 

LRU 근사 알고리즘은 더 저렴한 메커니즘을 사용하여 최신 페이지를 더 가깝게 함으로써 이러한 어려움을 극복하려고 합니다. 이는 각 페이지에 대한 카운터를 유지하고 페이지에 액세스할 때마다 업데이트하여 달성할 수 있습니다. 그러면 페이지가 카운터에서 가장 작은 값으로 변경됩니다.

 

LRU 접근 페이지의 대체 알고리즘은 다음과 같은 특징을 가지고 있다.

단순: 알고리즘은 각 페이지에 대한 정확한 페이지 교체 알고리즘 액세스 시간을 추적하기 보다는 각 페이지에 대한 카운터를 사용하기 때문에 구현이 간단합니다.

싸다: 알고리즘은 구현에 추가적인 데이터 구조가 필요하지 않기 때문에 저렴하며, 이는 다른 페이지 교체 알고리즘보다 더 빠르게 한다.

접근: LRU 근사 알고리즘은 최적의 LRU 알고리즘의 동작을 근사하려고 시도하지만 항상 최적의 LRU 알고리즘과 정확히 동일한 결과를 줄 수는 없다.

성능: LRU 근사 알고리즘의 성능은 LRU의 최적 알고리즘에 가깝지만 특정 경우에는 그다지 좋지 않을 수 있다.

적응: 알고리즘은 페이지의 최근 페이지 교체 알고리즘 액세스 패턴을 기반으로 행동을 조정하는 의미에서 적응적이며, 대부분의 경우 양호한 성능을 발휘합니다.

일반적으로 LRU 접근 페이지의 대체 알고리즘은 단순성, 효율성 및 성능 간에 좋은 균형을 제공하기 때문에 실용적인 응용 프로그램에 좋은 선택이다.

 

2022.12.19 - [운영체제] - 파일 접근 방법 (Access Method) 핵심 정리

파일 접근 방법 (Access Method) 핵심 정리