페이지 교체 알고리즘이란 무엇입니까?

주소 매핑 과정에서 접근하려는 페이지가 메모리에 없는 것으로 확인되면 페이지 폴트 인터럽트가 발생합니다. 페이지 부재가 발생할 때 운영 체제 메모리에 사용 가능한 페이지가 없으면 운영 체제는 메모리에서 페이지를 선택하고 해당 페이지를 메모리 밖으로 이동하여 페이지가 전송될 공간을 확보해야 합니다. 제거할 페이지를 선택하는 데 사용되는 규칙을 페이지 교체 알고리즘이라고 합니다.

일반적인 교체 알고리즘

최적 교체 알고리즘(OPT)

이것은 이상적인 페이지 교체 알고리즘이지만 실제로 달성하는 것은 불가능합니다. 이 알고리즘의 기본 아이디어는 페이지 오류가 발생하면 일부 페이지가 메모리에 있으며 그 중 하나는 곧 액세스되고(다음 명령의 페이지도 포함) 다른 페이지는 10 또는 10까지 액세스되지 않을 수 있다는 것입니다. 100 또는 1000개의 명령어 후에 액세스됩니다. 각 페이지는 페이지가 처음으로 액세스되기 전에 실행될 명령어 수로 표시될 수 있습니다. 최적의 페이지 교체 알고리즘은 단순히 가장 큰 마크업이 있는 페이지를 교체해야 한다고 명시합니다. 이 알고리즘의 유일한 문제점은 구현할 수 없다는 것입니다. 페이지 오류가 발생하면 운영 체제는 각 페이지에 다음에 액세스할 시기를 알 수 없습니다. 이 알고리즘은 구현이 불가능하지만 최적 페이지 교체 알고리즘을 사용하여 달성 가능한 알고리즘의 성능을 측정하고 비교할 수 있습니다.

선입선출 교체 알고리즘(FIFO)

가장 간단한 페이지 교체 알고리즘은 FIFO(선입선출) 방식입니다. 이 알고리즘의 핵심은 항상 주 메모리에 가장 오랫동안 머물렀던(즉, 가장 오래된) 페이지를 선택하여 교체하는 것, 즉 메모리에 먼저 들어가고 메모리에서 먼저 나가는 페이지를 선택하는 것입니다. 그 이유는 메모리로 전송된 가장 빠른 페이지가 방금 메모리로 전송된 페이지보다 더 이상 사용되지 않을 가능성이 높기 때문입니다. FIFO 대기열을 생성하여 모든 페이지를 메모리에 저장합니다. 교체된 페이지는 항상 대기열의 선두에 배치됩니다. 페이지가 메모리에 저장되면 대기열 끝에 삽입됩니다.

이 알고리즘은 선형 순서로 주소 공간 [1]에 액세스할 때만 이상적이며, 그렇지 않으면 효율적이지 않습니다. 자주 액세스되는 페이지는 주 메모리에 가장 오래 머무르는 경향이 있고 결과적으로 "오래된" 페이지이므로 교체해야 합니다.

FIFO의 또 다른 단점은 비정상적인 현상이 있다는 것입니다. 즉, 저장 블록이 증가하면 페이지 폴트 인터럽트 비율이 증가합니다. 물론 이러한 이상 현상을 일으키는 페이지 방향은 실제로 매우 드뭅니다.

LRU(Least Recent Used) 알고리즘

FIFO 알고리즘과 OPT 알고리즘의 주요 차이점은 FIFO 알고리즘은 페이지가 메모리에 들어간 후의 시간을 교체 기준으로 사용하는 반면 OPT 알고리즘은 페이지 시간의 향후 사용을 기반으로 합니다. 최근 과거를 가까운 미래의 근사치로 사용하는 경우 과거에 가장 오랫동안 사용되지 않은 페이지를 교체할 수 있습니다. 그 본질은 페이지를 교체해야 할 때 이전 기간 동안 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다는 것입니다. 이 알고리즘을 가장 최근에 사용된 알고리즘(Least Recent Used, LRU)이라고 합니다.

LRU 알고리즘은 각 페이지가 마지막으로 사용된 시간과 관련이 있습니다. 페이지를 교체해야 하는 경우 LRU 알고리즘은 지난 기간 동안 가장 적게 사용된 페이지를 선택합니다.

LRU 알고리즘은 자주 사용되는 페이지 교체 알고리즘으로 꽤 좋다고 평가되지만, 어떻게 구현하느냐의 문제가 있습니다.

LRU 알고리즘은 실제 하드웨어의 지원이 필요합니다.

문제는 마지막으로 사용한 시간의 순서를 결정하는 방법입니다. 이를 위한 두 가지 가능한 방법이 있습니다:

1.

가장 간단한 경우는 각 페이지 테이블 항목을 사용 시간 필드에 대응시키고 논리적 시계 또는 카운터를 CPU에 추가하는 것입니다. 이 클록은 메모리 액세스마다 1씩 증가합니다. 페이지에 액세스할 때마다 시계 레지스터의 내용이 해당 페이지 테이블 항목의 사용 시간 필드에 복사됩니다. 이렇게 하면 각 페이지를 마지막으로 방문한 "시간"을 항상 유지할 수 있습니다. 페이지 교체 시 시간 값이 가장 작은 페이지를 선택합니다. 이를 위해서는 페이지 테이블을 조회해야 할 뿐만 아니라, 페이지 테이블이 변경될 때(CPU 스케줄링으로 인해) 페이지 테이블의 시간을 유지해야 하며, 클럭 값 오버플로 문제도 고려해야 합니다. .

2.스택.

페이지 번호를 유지하려면 스택을 사용하세요. 페이지에 액세스할 때마다 해당 페이지는 스택에서 꺼내어 스택 상단에 배치됩니다. 이러한 방식으로 가장 많이 사용된 페이지는 항상 스택의 맨 위에 배치되고 가장 적게 사용된 페이지는 스택의 맨 아래에 배치됩니다. 항목을 스택 중간에서 제거해야 하므로 머리 포인터와 꼬리 포인터가 있는 양방향 체인을 사용하여 항목을 연결합니다. 최악의 경우 페이지를 제거하고 스택 위에 배치하려면 6개의 포인터를 변경해야 합니다. 수정할 때마다 오버헤드가 발생하지만 tail 포인터가 교체할 페이지가 있는 스택의 맨 아래를 가리키기 때문에 검색 없이 교체해야 할 페이지를 직접 얻을 수 있습니다.

LRU 알고리즘을 구현하려면 많은 양의 하드웨어 지원이 필요하기 때문에 일정량의 소프트웨어 오버헤드도 필요합니다. 그래서 실제로 구현된 것은 간단하고 효과적인 LRU 근사 알고리즘입니다.

하나의 LRU 근사 알고리즘은 NUR(Not Recent Used) 알고리즘입니다.

저장 블록 테이블의 각 항목에 참조 비트를 추가하고 운영 체제는 주기적으로 이를 0으로 설정합니다. 페이지에 액세스할 때 이 비트는 하드웨어에 의해 설정됩니다. 시간이 지남에 따라 이러한 비트를 검사하여 마지막으로 0으로 설정된 이후 사용된 페이지와 사용되지 않은 페이지를 확인할 수 있습니다. 비트가 0인 페이지는 최근 기간 동안 액세스되지 않았으므로 제거할 수 있습니다.

4) 클럭 교체 알고리즘(LRU 알고리즘의 대략적인 구현)

5) LFU(Least Used) 교체 알고리즘

Least Used 교체 알고리즘을 사용하는 경우 메모리의 각 페이지마다 시프트 레지스터를 설정해야 하며, 이 페이지를 얼마나 자주 방문했는지 기록하는 데 사용됩니다. 교체 알고리즘은 이전 기간에 가장 적게 사용된 페이지를 퇴거 페이지로 선택합니다.

메모리는 100ns와 같은 높은 액세스 속도를 갖기 때문에 특정 페이지는 1ms 내에 수천 번 연속적으로 액세스될 수 있습니다. 따라서 일반적으로 카운터를 사용하여 특정 페이지가 방문한 횟수를 직접 기록할 수는 없습니다. 액세스했지만 시프트 레지스터 방식을 사용합니다. 페이지에 액세스할 때마다 시프트 레지스터의 최상위 비트가 1로 설정되고, 이후 특정 시간(예: 100ns)마다 오른쪽으로 시프트됩니다. 이런 방식으로 최근 기간에 가장 적게 사용된 페이지는 ΣRi가 가장 작은 페이지가 됩니다.

LFU 대체 알고리즘의 페이지 액세스 그래프는 LRU 대체 알고리즘의 액세스 그래프와 정확히 동일합니다. 즉, 이러한 하드웨어 세트를 사용하면 LRU 알고리즘과 LFU 알고리즘을 모두 구현할 수 있습니다. LFU 알고리즘은 각 시간 간격에서 페이지 사용량을 기록하는 데 레지스터의 1비트만 사용되므로 실제로 페이지 사용량을 반영하지 않는다는 점에 유의해야 합니다. 따라서 한 번 액세스하는 것은 10,000번 액세스하는 것과 같습니다. ...

두 번째 기회 알고리즘의 기본 아이디어는 FIFO와 동일하지만 자주 사용하는 페이지를 교체하지 않도록 개선되었습니다. 대체 페이지가 선택되면 해당 페이지의 액세스 비트가 확인됩니다. 0이면 페이지가 제거되고, 액세스 비트가 1이면 두 번째 기회가 주어지고 다음 FIFO 페이지가 선택됩니다. 페이지가 두 번째 기회를 얻으면 해당 액세스 비트는 0으로 지워지고 도착 시간은 현재 시간으로 설정됩니다. 이 기간 동안 페이지를 방문했다면 위치 1을 방문합니다. 따라서 두 번째 기회가 주어진 페이지는 다른 모든 페이지가 제거될 때까지(또는 두 번째 기회가 주어질 때까지) 제거되지 않습니다. 따라서 페이지가 자주 사용되는 경우 해당 페이지의 액세스 비트는 항상 1로 유지되고 제거되지 않습니다.

두 번째 기회 알고리즘은 순환 대기열로 볼 수 있습니다. 포인터를 사용하여 다음에 제거할 페이지를 나타냅니다. 메모리 블록이 필요할 때 포인터는 액세스 비트가 0인 페이지를 찾을 때까지 전진합니다. 포인터가 앞으로 이동하면 액세스 비트가 0으로 지워집니다. 최악의 경우 모든 액세스 비트는 1이고 포인터는 일주일 동안 전체 대기열을 통과하여 각 페이지에 두 번째 기회를 제공합니다. 이때 FIFO 알고리즘으로 변질됩니다.

위 내용은 페이지 교체 알고리즘이란 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!