페이지 교체 알고리즘에 대하여

페이지 교체 알고리즘에는 몇 가지 종류가 있습니다. 첫 번째는 아웃을 뜻하는 FIFO입니다. 이 메서드에서 운영 체제는 로드된 페이지를 순서대로만 저장해야 하므로 공간을 만들어야 할 때 로드된 첫 페이지를 쉽게 선택할 수 있습니다. 큐가 사용되며 새 페이지를 로드하면 마지막 장소가 들어갑니다. FIFO 큐는 간단하고 직관적이지만 실제 응용 프로그램에서는 수용 가능한 방식으로 작동하지 않으므로 간단한 형태로 사용하는 것은 드뭅니다. 그들이 제시하는 문제 중 하나는 소위 FIFO 이상 또는 베레이디 이상입니다. Belady는 페이지 프레임이 3개에 해당하는 시스템이 4페이지 프레임이 있는 시스템보다 페이지 오류가 적은 사례를 발견했습니다. 문제는 우리가 메모리에서 메모리의 많이 사용되는 페이지를 취할 수 있다는 것입니다. 그것은 가장 오래된 메모리이기 때문입니다.

두 번째 알고리즘은 기회를 뜻하는 시계입니다. 이것은 FIFO 알고리즘을 약간 수정한 것으로, fifo보다 훨씬 더 잘 작동합니다. 이 경우 페이지를 큐의 첫 번째 페이지를 꺼내야 하는 경우 페이지를 꺼내는 대신 참조 비트의 값을 쿼리 합니다. 1에서 설정된 비트가 0으로 변경되어 장애물 끝에 배치되어 프로세서에 방금 도달한 것처럼 로드 시간을 업데이트합니다. 이런 식으로, 당신은 두 번째 기회가 주어집니다. 비트가 desqed 되지 않은 경우(0)는 페이지가 메모리에서 제거됩니다. MMU가 페이지에 액세스 할 때마다 참조 비트를 1로 설정합니다. 이렇게 하려면 하드웨어 참조 비트에 대한 지원이 필요합니다.

시계 페이지 알고리즘도 있습니다. 시계 알고리즘은 구현의 개선을 제공하는 두 번째 기회 알고리즘이 개선된 것입니다. 이것이 시계 알고리즘입니다. 시계 알고리즘은 무엇을 하는 것은 원형 목록, 그래서 그것은 목록의 마지막 요소에 도달 할 때, 그것은 자동으로 첫 번째로 전달합니다. 요소에 액세스 할 때 큐의 끝으로 이동되지 않고 참조 비트는 0으로 변경됩니다. 이렇게 하면 연결된 목록으로 포인터를 구현할 경우 포인터를 이동할 필요가 없습니다. 실제로 배열로 완벽하게 구현하여 메모리를 절약할 수 있습니다.

사용되지 않는다는 NRU 알고리즘은 최근에 사용된 페이지를 선호합니다. 페이지가 참조되면 해당 페이지의 참조 비트를 설정합니다. 마찬가지로 페이지가 수정되면 수정 비트를 설정합니다. 일반적으로 이러한 작업은 하드웨어에 의해 수행되지만 소프트웨어로도 수행할 수 있습니다. 고정된 시간에 운영 체제는 모든 페이지의 참조 비트를 0으로 설정하므로 참조 비트가 1에 있는 페이지는 마지막 클럭 범위 내에서 참조된 페이지입니다. 페이지를 교체해야 하는 경우 운영 체제는 페이지를 네 가지 범주로 나눕니다. 카테고리 0은 참조되지 않음, 변경되지 않음을 뜻합니다. 카테고리 1은 참조되지 않고 수정되었다는 것입니다. 카테고리 2는 참조되었으나, 변경되지 않음을 말합니다. 카테고리 3은 참조하였으며, 수정하였다는 것입니다. 변경할 수 있는 가장 좋은 페이지는 카테고리 0에 속하는 페이지이며, 최악의 페이지는 카테고리 3에 속합니다. 비어 있지 않은 가장 낮은 범주의 페이지가 무작위로 제거됩니다. 이 알고리즘은 많이 사용되는 깨끗한 페이지가 아니라 적어도 하나의 똑딱 시계에서 참조되지 않은 수정된 페이지를 제거하는 것이 좋습니다.

LRU 알고리즘은 최근에 사용되지 않은 알고리즘입니다. 이 알고리즘은 페이지의 참조 비트가 0으로 설정된 이후 시간 간격으로만 고정되어 있다는 점에서 '최근에 사용되지 않음' 알고리즘과 다르며, '가장 최근에 사용된' 알고리즘은 최근에 사용되지 않은 페이지를 관찰하여 거의 최적 동작을 제공하려고 시도합니다. 이러한 유형의 페이지는 통계적으로 다시 사용할 가능성이 가장 높습니다. 이 알고리즘은 이론적으로 좋은 동작을 제공하지만 소비되는 리소스 측면에서 구현하는 데 비용이 많이 듭니다. 비용을 절감하고 상당한 성능을 달성하려는 몇 가지 배포가 있습니다. 한 가지 방법은 메모리에 있는 모든 페이지의 바인딩 및 정렬된 목록을 갖는 것입니다. 목록의 끝에 가장 최근에 사용된 페이지이며, 처음에 가장 최근에 사용된 것을 뜻합니다. 이 방법의 높은 비용은 페이지를 참조할 때마다 목록에서 이동해야 하므로 시간이 많이 소요됩니다. 하드웨어 지원이 필요한 또 다른 방법은 각 CPU 명령에 대해 증분 되는 카운터를 갖는 것입니다. 페이지에 액세스 할 때마다 해당 시점에 카운터 번호가 이깁니다. 페이지를 메모리에서 꺼내야 하는 경우 가장 긴 숫자를 가진 페이지를 찾아야 합니다. 현재 이것을 허용하는 카운터가 너무 커지 않습니다. LRU의 높은 비용으로 인해 유사한 알고리즘이 제안되지만 비용이 적게 드는 구현을 허용합니다.