페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 메모리에 적재되지 않을 시 (page fault)
어떤 페이지 프레임을 선택하여 교체 할 것인지 결정하는 방법
페이지 교체 알고리즘의 종류
-
OPT : 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
가장 이상적, 효율적 방법, 페이지의 참조 상황을 미리 예측, 실현 가능성 희박
최적 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 알고 교체, 모든 페이지 교체 알고리즘을 통틀어 가장 페이지 교체 수가 적음 -
FIFO : 가장 먼저 들어와서 가장 오래 있던 페이지 교체
페이지 7은 프로세스 초기에 쓰인 후 한동안 사용 X -> FIFO 교체 방식이 문제 되지 않음
페이지 2(9번째)의 경우, 직전 페이지 부재(page4)로 인해 페이지 4와 페이지 2가 교체된 뒤 또 다시 페이지 2를 사용하기 위해 교체 했던 페이지 2를 다시 불러드림
- if) 활발하게 사용중인 페이지를 계속 교체, => 실행속도 감소, 부재율 증가
+) Belady의 이상현상(Belady's anomaly)
실패가 자주 발생한느 경우 pageFrame 증가, 메모리를 늘리면 된다는 생각을 할때 실패가 감소??
하지만 그렇게 되지 않을 수도 있는 현상 = Belady 현상
즉, pageFrame 수를 늘렸는데 오히려 실패가 증가
- LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지를 교체하는 기법, 각 페이지마다 카운터나 스텍을 두어 현 시점에서 가장 오랫동안 사용하지 않은 페이지 교체
단점은 초기에 한 페이지를 집중적으로 참조, 다시 참조 하지 않는 경우 문제 발생
사용하지 않아도 초기에 사용된 참조 횟수가 높아 메모리에 계속 남아 있음
- 7의 참조 횟수가 높지만 계속 메모리에 남아 있는 상황
- NUR (Not Used Recently)
LRU와 비슷한 방식, 최근에 사용하지 않은 페이지를 교체
LRU 교체의 단점인 시간과 오버헤드 감소
최근 사용 여부를 확인하기 위해 각 페이지마다 두개의 비트(참조비트/변형비트)를 사용
참조비트 : 페이지가 호출되었을 때는 1, 호출되지 않았을 때는 0
변형비트 : 페이지 내용이 변경되었을 때는 1, 변경되지 않았을 때는 0
- SCR(Seconde Chance Replacement)
가장 오래동안 주기억장치에 있던 페이지중 자주 사용되는 페이지의 교체를 방지하기 위한 것, FIFO 기법의 단점을 보안. 각 페이지마다 참조비트를 두고, FIFO 기법을 이용하여 페이지 교체 수행중 참조비트가 0일 경우 교체, 참조비트가 1일 경유 참조비트를 0으로 지정한 후 FIFO 리스트의 맨 마지막으로 피드백 시켜 다음 순서 기다름
교체 방식
- Golbal 교체
메모리 상의 모든 프로세스 페이지에 대해 교체 - Local 교체
메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
다중 프로그래밍의 경우 메인 메모리에 다양한 프로세스 동시에 올라갈 수 있음
따라서 프로세스의 페이지가 메모리에 존재
페이지 교체시 다양한 페이지 교체 알고리즘을 통해, 교체하 페이지를 선정, 선정기분을 전체(Global) 기준으로 하느냐 자기 프로세스(Local) 페이지를 기준으로 하느냐에 대한 차이
전체를 기준으로 페이지를 교체하는 것이 더 효율적
-> 자기 프로세스 페이지에서만 교체하면, Victim Page를 선정해야 하므로 비효율적.
