( 페이지 교체(페이지 교체) )
페이지를 제거하는 것을 페이지 교체라고 합니다.
운영 체제가 수행하는 작업오전. 이 경우에 사용되는 알고리즘은 대체 알고리즘입니다.
.빈 페이지가 없는 경우 페이지를 제거한 후 페이지를 해당 메모리에 로드해야 합니다.
가능하면 페이지 폴트가 발생하지 않으며 가능하면 메모리에서 직접 처리할 수 있습니다.
왜냐하면 페이지가 제거된 직후 페이지가 다시 참조되면 페이지를 스왑 공간에서 메모리로 다시 로드해야 합니다.
이 프로세스는 시간이 오래 걸립니다.
.
메모리에서 삭제할 페이지와 제자리에 넣을 페이지를 결정해야 합니다.
가능한 페이지 폴트가 발생하지 않음 가능한 한 많이 메모리에서 직접 처리할 수 있는 일이 많을수록 성능이 좋아집니다.
.
참조 문자열은 페이지가 연대순으로 참조되는 순서입니다.
참조 문자열이 1,2,3,4,1,2,5,1,2,3,4,5이면 첫 번째 페이지가 먼저 참조된 다음 두 번째, 세 번째, 첫 번째 페이지가 참조됩니다.
페이지 번호 1이 사용 중이고 나중에 스왑 공간으로 스왑 아웃된 경우 페이지 폴트가 발생한 후에는 디스크에서 메모리로 다시 로드해야 합니다.
페이지 번호 1이 메모리에서 배출되지 않은 경우 페이지 폴트를 일으키지 않고 메모리에서 다시 참조할 수 있습니다.
.
✓ 여유 프레임이 없을 때 페이지 교체
- 훔칠 프레임을 결정해야 합니다.
- 바로 사용하지 않을 페이지는 퇴출시키는 것이 좋습니다.
- 동일한 페이지를 메모리에서 꺼내고 여러 번 다시 입력할 수 있습니다.
✓ 대체 알고리즘
- 목표는 페이지 부재율을 최소화하는 것입니다.
- 알고리즘 평가: 주어진 페이지 참조 문자열에 대해 얼마나 많은 페이지 폴트가 생성되는지 조사합니다.
- 참조 문자열 예: 1,2,3,4,1,2,5,1,2,3,4,5
희생 페이지가 결정되면 적절한 페이지가 디스크로 배출됩니다.
콘텐츠가 디스크에서 메모리로 로드된 이후 변경된 경우(쓰기가 발생한 경우)
메모리 밖으로 밀려났을 때 변경 사항은 백업 스토리지에 기록되어야 합니다.
하다, 변화가 없다면 메모리에서 꺼내기만 하면 됩니다.
피해자 페이지가 선정되어 퇴출된 경우 배출된 페이지에 대한 테이블 항목이 유효하지 않은 것으로 변경됩니다.
그리고 이 페이지에 대해 메모리에 새 페이지를 로드합니다.
페이지 테이블 항목에 프레임 번호를 쓰고 비트를 유효한 것으로 변경합니다.
운영 체제가 이 역할을 맡습니다.
● 최적 알고리즘
이러한 알고리즘 중에는 이 알고리즘이 있습니다.
최소 오차 알고리즘이다
먼 미래에 참조되는 페이지 교체그러나 실제 시스템에서는 미래를 알 수 없습니다.
.
현재 1페이지를 참조하고 있으나 향후 1페이지가 사용될지 모르기 때문에 1페이지를 삭제할지 여부를 결정하기 어렵습니다.
.
이 알고리즘은 페이지의 사용이 미리 알려져 있다고 가정합니다.
실제 시스템에서는 사용할 수 없습니다.
페이지 폴트는 항상 페이지가 사용 가능한 메모리에 처음 로드될 때 생성됩니다.
그것은 난다
페이지가 하나씩 메모리에 로드되고 페이지 1이 다시 참조되면 (이미 메모리에 있기 때문에) 직접 참조된다
.
그 이후에 페이지 5를 나중에 요청하면 메모리에 없습니다.
페이지 오류가 발생하여 메모리에서 제거해야 하는 페이지를 결정합니다.
하다.
1, 2, 3, 4면 중 어느 쪽을 킥아웃할지 결정해야 합니다.
먼 미래에 참조될 페이지를 꺼냅니다.
페이지 4는 마지막으로 참조되므로 페이지 5를 메모리에 넣기 위해 페이지 4를 버립니다.
이 알고리즘을 사용할 때 총 6개의 페이지 폴트발생합니다.
어떤 알고리즘을 사용하든 페이지 폴트가 6회 미만인 경우는 없다.
.
어쨌든 이 알고리즘은 미래가 알려져 있다고 가정하므로 실제 시스템에서는 사용할 수 없습니다.
그러나 실제 시스템에서는 다른 알고리즘에 상한선 제공하다.
아무리 좋은 알고리즘이라도 이보다 더 좋은 알고리즘을 만들 수는 없습니다.
예를 들어 알고리즘을 만들고 그 알고리즘과 최적의 알고리즘의 성능이 비슷하다면, 이것은 더 이상 좋은 알고리즘을 만들 수 없다는 것을 의미합니다.
● FIFO(첫 번째 인퍼스트 아웃 알고리즘
실제 시스템에서 사용할 수 있는 알고리즘입니다.
미래를 모른다면 가장 좋은 길잡이는 과거를 들여다보는 것입니다.
FIFO 알고리즘은 첫 페이지를 쫓는 방법오전.
일반적으로 메모리 양을 늘리면 성능이 향상됩니다.
이 알고리즘 메모리 크기를 늘리면 실제로 성능이 저하됩니다.
나타납니다.
앞서 본 참고용으로 3프레임과 4프레임의 경우를 비교해 보자.
사이드 프레임이 3개 있는 것처럼 4개일 때 더 많은 페이지 오류 발생볼 수 있습니다
● LRU 알고리즘(가장 오래 사용됨).
가장 오래된 참조 페이지실패하는 알고리즘이다
FIFO는 먼저 온 페이지를 배출하지만 LRU 알고리즘은 가장 오래 사용된 페이지를 먼저 배출합니다.
기준이 아니라 사용시하니까 먼저 들어갔는데 들어와서 재사용하는 경우 방출하지 마십시오.
최근에 참조한 페이지가 다시 참조될 가능성이 높기 때문입니다.
페이지 폴트를 상대적으로 줄일 수 있습니다.
● LFU 알고리즘(가장 적게 사용됨).
이것이 가장 적게 참조된 페이지를 버리는 방법입니다.
오전.
링크가 가장 적은 페이지가 메모리에서 배출됩니다.
과거에 참조된 페이지는 앞으로도 계속 참조될 가능성이 높습니다.
이것은 쫓겨나지 않을 것입니다.
참조가 적은 페이지가 많은 경우 모두 버리지만 여전히 성능을 조금 더 개선하고 싶습니다.
링크된 페이지 중 마지막 참조 포인트가 오래된 페이지가 쫓겨납니다.
.
✓ LFU
- 참조 횟수가 가장 적은 페이지를 삭제하십시오.
- – 여러 페이지 중에서 참조 수가 가장 적은 페이지를 무작위로 선택합니다.
- – 성능 향상을 위해 가장 오래된 참조 페이지를 삭제하도록 구현할 수 있습니다.
✓ 장점과 단점
- LRU처럼 이전 기준점만 보는 것이 아니라 긴 시간 척도를 보기 때문에 페이지의 인기도를 보다 정확하게 반영할 수 있습니다.
- 기준점의 실제를 반영하지 않습니다.
- LRU보다 구현하기가 더 복잡합니다.
● LRU 및 LFU 알고리즘의 예
아래 그림에서 LRU와 LFU 알고리즘을 비교해 봅시다.
시간순으로 4개의 페이지 프레임이 있으며, 1번은 4번, 2번은 2번, 3번은 2번 참조했습니다.
여기에서도 역시 2페이지를 한 번 참조하고 마지막에는 4페이지를 참조합니다.
.이 글을 쓰는 시점에서 5페이지를 참조해야 하므로 한 페이지를 빼야 합니다.
이 경우 LRU 알고리즘은 페이지 1입니다.
쫓아내다 LFU는 4페이지에 있습니다.
내 던지다
.
LRU 연산이전 레코드를 생각하지 않기 때문에 가장 오래된 참조입니다.
과거에 레퍼런스가 많았던 것을 고려하지 않는 문제있다
LFU 연산4페이지를 쫓았지만 참조가 한 번 계산되었지만 여러 참조가 방금 시작되었습니다.
이 경우 문제가 발생할 수 있습니다.
● LRU 및 LFU 알고리즘 구현
LRU 알고리즘참조 시간에 따라 메모리의 페이지를 정렬합니다.
맨 위 페이지는 가장 오래된 참조 페이지입니다.
이다, 페이지 아래로 내려갈수록 최근에 참조된 페이지오전.
.
Linked List로 페이지 참조 시간을 관리하세요.
페이지가 메모리에 로드되거나 메모리에서 다시 참조되면 해당 페이지는 맨 아래로 돌아가고 쫓겨나면 맨 위 페이지가 쫓겨납니다.
.
위와 같은 리스트 형태로 구현 시간 복잡도는 O(1)된다
페이지가 참조될 때마다 시간 기록 가장 오래된 페이지를 제거할지 여부를 결정할 때, .O(n)의 시간복잡도로 매우 비효율적된다
LFU 알고리즘은 링크가 가장 적은 페이지가 맨 위에 있고 링크가 가장 많은 페이지가 맨 아래에 있습니다.
오전.
킥아웃 시 LRU 알고리즘과 마찬가지로 맨 위 페이지를 내보냅니다.
.
LRU 알고리즘은 시간 순서 기반이므로 한 번만 참조해도 다운될 수 있습니다.
LFU 알고리즘은 참조 카운터는 1씩 증가하지만 감소하지는 않습니다.
차근차근 내려가야 합니다.
시간 복잡도가 O(n)이기 때문입니다.
LFU 알고리즘은 더미로 구현그러면 O(logN)을 구현할 수 있습니다.
.
두 아이를 낳다 이진 트리의 모양오전.
위는 가장 적게 참조된 페이지입니다.
세트 더 많은 참조가 있는 페이지는 아래에 계산됩니다.
세트
.
참조 횟수가 1씩 증가하면 직계 자식과 비교하여 적절한 경로로만 이동합니다.
나는 내가 얼마나 멀리 갈 수 있는지 찾고 있습니다.
.
이진 트리의 높이 규약2N이다, 녹아웃할 때 트렁크에서 페이지를 제거하고 힙을 재구성합니다.
하다.