- 페이지 교체 알고리즘의 개요
페이지 부재 발생 시 스왑 영역에 있는 페이지를 메모리에 올릴 때 빈 프레임이 없는 경우 어떤 페이지를 스왑 영역으로 결정하는 알고리즘
- 대상 페이지
알고리즘에 의해 스왑 영역으로 보낼 페이지
- 페이지 교체 알고리즘의 종류
- 간단한 알고리즘
- 무작위 페이지 교체 알고리즘
무작위로 대상 페이지를 선정하여 스왑 영역으로 보냄
가장 간단함
지역성을 고려하지 않기 때문에 성능이 좋지 않음
- FIFO 페이지 교체 알고리즘
처음 메모리에 올라온 페이지를 스왑 영역으로 보냄
큐로 구현함
시간의 지역성을 메모리에 올라온 시간만 고려하기 때문에 자주 사용되는 페이지가 스왑 영역에 옮겨지기도 함
- 이론적 알고리즘
- 최적 알고리즘
미래의 접근 대상을 보고 대상 페이지를 선정하여 스왑 영역으로 보냄
미래의 접근 패턴을 안다는 것은 불가능하여 실제로 구현할 수 없음
- 최적 근접 알고리즘
구현이 가능하면서 성능이 최적 페이지 교체 알고리즘에 근접하는 알고리즘
- LRU 페이지 교체 알고리즘
메모리에 올라온 후 가장 오랫동안 사용되지 않은 페이지를 대상 페이지로 선정하는 알고리즘
접근 시간이나 참조 비트를 유지하기 위해 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많음
- 페이지 접근 시간에 기반한 구현
페이지가 접근될 때 마다 시간을 같이 기록하는 방식
- 카운터에 기반한 구현
페이지가 접근될 때 마다 시간을 카운터로 기록하는 방식
- 참조 비트 시프트 방식
각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것
참조 비트의 초깃값은 0이며 페이지에 접근할 때 마다 1로 바뀌며 주기적으로 오른쪽으로 한 칸씩 이동함
- LFU 페이지 교체 알고리즘
페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정하는 알고리즘
페이지에 접근될 때 마다 접근 횟수를 기록함
추가 공간이 필요하므로 메모리가 낭비됨
- NUR 페이지 교체 알고리즘
최근에 사용한 적이 없는 페이지를 스왑 영역으로 보냄
참조 비트와 변경 비트를 이용하여 대상 페이지를 선정함
우선 고려 대상은 참조 비트
공간 낭비 문제를 해결한 알고리즘
- FIFO 변형 알고리즘
FIFO 알고리즘 변형한 알고리즘
- 2차 기회 페이지 교체 알고리즘
특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외하는 알고리즘
큐를 유지하는 비용이 높음
- 시계 알고리즘
원형 큐를 사용하는 방식
스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용함
각 페이지에 참조 비트를 추가함
페이지 참조가 성공하면 참조 비트를 0에서 1로 변경함
참조 비트가 1인 페이지는 대상 페이지에서 제외되며 건너뛸 때 0으로 바꿔놓음
- 페이지 교체 알고리즘의 성능 평가 기준
페이지 부재 횟수, 평균 대기 시간, 전체 작업 시간을 비교할 수 있음
성능 뿐 아니라 유지 비용도 고려해야 함