1. 고정 할당 방식(Fixed Allocation)
- 각 프로세스에게 고정된 갯수의 페이지 프레임을 할당하는 방식
- OPT(Optimal) 알고리즘
- 앞으로 가장 오랫동안 교체되지 않을 page를 교체하는 최적의 기법
- page reference string을 미리 알고있지 않으면 불가능한 방법
- 현실적으로 사용 불가능한 기법이지만 교체 알고리즘의 성능 평가를 위해 사용됨
- Random 알고리즘
- 무작위로 교체할 page를 선택
- 오버헤드가 없으며 정책도 없음
- Random 알고리즘보다 성능이 나쁜 알고리즘이라면 고려할 가치가 없음(성능평가의 기준)
- FIFO(First In First Out) 알고리즘
- 가장 오래된 page를 교체
- page가 적재된 시간을 알아야함
- Locality를 고려하지 않은 알고리즘이기에 좋은 성능을 보이긴 어려움
- 메모리를 더 많이 할당했는데도 page fault 발생률이 증가할 수도 있음
- LRU(Least Recently Used) 알고리즘
- 가장 오래동안 참조되지 않은 page를 교체
- 각 페이지를 마지막으로 참조한 시간을 기록해야함(오버헤드 있음)
- Locality를 고려한 알고리즘이기에 OPT 알고리즘에 근접하는 성능을 보임
- 실제로 가장 많이 사용되는 기법
- 문제점
- 반복적으로 참조되는 page 갯수보다 할당받은 page frame 수가 적을 경우
사실상 FIFO와 같아져 성능이 급격히 하락
- 할당 전략에서 충분한 메모리를 할당하는 것으로 해결 가능
- LFU(Least Frequently Used) 알고리즘
- 참조된 횟수가 가장 적은 page를 교체
- 각 페이지를 참조할 때 마다 참조횟수를 증가시켜야함(오버헤드 있음)
- 최근에 적재된 page의 경우 참조횟수가 적어 이후에 참조될 가능성이 높음에도 교체될 수 있음
- NUR(Not Used Recently) 알고리즘
- 유사 LRU 알고리즘
- Bit Vector를 사용하는 방식
- 참조 비트(Reference Bit)와 갱신 비트(Update Bit)를 참조하여 최근에 참조되지 않은 비트일수록,
참조 여부가 같다면 최근에 수정되지 않은 비트일수록 교체 우선도를 높게 본다.
- Bit Vector의 주기적인 초기화가 필요
- Clock 알고리즘
- NUR을 현실적으로 구현한 예시
- Reference Bit를 사용하지만 주기적인 초기화는 필요하지 않음
- page frame을 순차적으로 가리키는 pointer(시계바늘)를 사용하여 교체될 페이지를 결정
- 동작 방식
- 시계바늘이 특정 page의 reference bit를 체크했을 때 1이라면 0으로 초기화
- 0이라면 그 페이지를 교체
- Second Chance 알고리즘
- Clock 알고리즘과 유사
- Clock 알고리즘에서 Update Bit을 추가적으로 고려하는 방식
- 참조나 수정 전적이 둘 중 하나라도 있다면 한번의 기회를 더 주는 알고리즘
- 동작 방식
- 시계바늘이 특정 page의 reference bit, update bit 쌍을 확인하여 (0, 0)이라면 교체
- (0, 1)이라면 write back 하여 변경사항을 반영한 뒤 (0, 0)으로 초기화
- (1, 0)이라면 (0, 0)으로 초기화
- (1, 1)이라면 (0, 1)로 초기화
2. 가변 할당 방식(Variable Allocation)
- 프로세스에게 할당하는 메모리 크기가 변할 수 있는 경우
- WS(Working Set) 알고리즘
- 현재 작업에 필요한 페이지의 집합 => 프로세스가 특정 시점에 자주 참조하는 page의 집합
- working set의 페이지들을 메모리에 적재된 상태로 유지하는 방식
- 시간적 지역성(locality)에 기반한 방식이기에 page fault 발생률이 감소하며 시스템 성능 향상을 기대할 수 있음
- working set의 크기는 시간에 따라 변하지만 window_size 는 고정된 값을 가짐
- window_size가 커질수록 working set의 크기도 커진다.(프로그램이 참조하는 페이지의 갯수 이하)
- window_size를 적절한 크기로 설정하는 것이 working set 알고리즘의 성능에 큰 영향을 미침
- 메모리의 반납이 새로운 page의 적재와는 관계없이 이루어짐(window의 상태에 따라 이루어짐)
- page fault가 없더라도 working set을 지속적으로 관리해야한다는 오버헤드가 존재함
- W(current_time, window_size)
- current_time - window_size 부터 current_time 까지 참조된 페이지의 집합
- Working Set Transition
- loop중에는 working set이 loop에 필요한 만큼으로 유지
- loop를 빠져나오는 순간에는 working set이 일시적으로 증가하는 경향을 보임(새로운 페이지를 참조하기 때문)
- 성능평가
- 단순히 page fault만 보기엔 할당한 페이지 프레임의 수가 다름
- page fault의 처리비용과 page frame 할당 및 관리 비용을 복합적으로 고려하여 평가해야함
- PFF(Page Fault Frequency) 알고리즘
- Working Set 알고리즘의 단점인 page fault가 발생하지 않아도 지속적으로 working set을 관리해야하는
오버헤드를 해결하기 위한 알고리즘
- working set의 크기를 page fault 발생률에 따라 조정
- page fault 발생률이 높다면 working set의 크기를 증가, 낮다면 working set의 크기를 감소
- page fault가 발생할 때만 working set을 갱신하고 메모리를 할당하기 때문에 오버헤드가 적음
- page fault 간의 발생시간이 일정 수치를 넘어서면 page fault 발생률이 적다고 판단하고
반대로 일정 수치보다 낮다면 page fault 발생률이 높다고 판단한다.
- Variable OPT 알고리즘
- 가변 할당 방식에서의 최적 알고리즘
- 평균 메모리 할당량과 page fault 발생 횟수를 모두 고려한 최적
- 고정 할당방식의 OPT 알고리즘과 마찬가지로 page reference string을 미리 알고있어야 사용 가능하기에
현실적으로 구현 불가능한 방식
- current_time 부터 current_time + window_size 까지의 page reference string에서 참조되지 않는 page를
메모리에서 해제하고 참조되는 page만을 유지하는 방식
- window_size의 최적값?
- window_size가 커지면 page fault 발생률은 줄어들지만 메모리 유지비용이 증가한다.
- window_size가 작아지면 page fault 발생률은 늘어나지만 메모리 유지비용은 감소한다.
- (page fault 처리비용 / 단위 시간당 메모리 관리비용) 으로 정하는 것이 효율적
- 실현 불가능한 알고리즘이지만 페이지 교체 알고리즘의 성능 평가를 위해 사용할 수 있음