가상기억장치관리(2)

운영체제 13

LRU 알고리즘 : 최근 가장 오랫동안 참조되지 않은 페이지를 교체. 프로그램의 지역성에 기반을 둠. MIN과 비슷.

단점 : 매번 참조시간을 기록해야하는 오버헤드가 큼.

LFU알고리즘 : 가장 참조횟수가 적은 페이지를 교체함. 참조시마다 참조횟수를 누적시켜야함. LRU의 오버헤드를 줄이면서 프로그램의 지역성 이용. 가장 최근에 참조되었음에도 교체될 수 있다.

NUR알고리즘 : 적은 오버헤드롤 LRU의 성능을 내기위한 기법.

비트벡터 사용.

참조비트벡터 : 일정주기마다 0으로 재설정 되며 해당페이지가 참조되면 1로 설정.

갱신비트벡터 : 내용이 갱신되면 1로 설정되고 해당 페이지의 내용을 디스크에 기입하여야 함을 표시함.

참조비트와 갱신비트를 검사하여 페이지를 교체하는데

교체순서 0,0 -> 0,1 -> 1,0 -> 1,1

클럭 알고리즘 : 주기억장치에 적재되어 있는 페이지들을 환형 리스트로 보고 이 페이지들을 따라 움직이는 포인터를 사용하여 교체될 페이지를 선정하는 기법.

먼저 적재된페이지가 교체의 대상이 될 가능성이높음.(FIFO유사)

참조비트를 검사하여 그 값이 0 인 페이지가 교체 대상이 됨.(LRU,NUR유사)

1환형으로 되어있으며, 페이지의 참조비트가 0 이면 교체대상으로 선정 후 시계방향으로 한단계 이동.

2페이지의 참조비트가 1이면 0으로 설정 후 시계방향으로 한단계 진행 후 1부터 반복.

SecondChance알고리즘. 클럭알고리즘과 유사. 다른점은 참조비트뿐만 아니라, 갱신비트도 함께 고려. 

참조,갱신

0,0 이면 교체대상 선정, 시계방향으로 한단계 진행

0,1 이면 0,0 으로 설정하고, 소거대상 리스트 추가.

1,0 이면 0,0으로 설정하고 한단계 진행

1,1이면 0,1로 설정하고 한단계 진행

LRU알고리즘 구현.

스택을 사용한다. 새로적재된 페이지 번호를 top에 삽입. bottom에 있는 페이지를 교체대상으로 선정.