[OS] Page replacement

Page replacement

Page fault 가 발생해서 해당 페이지를 로딩하기 위해 Free frame 을 찾는데 free frame 이 없는 상황에서 사용중인 frame 을 내쫓고 할당하는 방법

최대한 오버헤드가 없도록 해야함. 즉 frame 을 잘 골라서 내쫓는게 중요함

• 많이 사용 안될것같은 frame

• 가급적 수정이 안된 frame

• Write 된 frame 을 내쫓으면 디스크에 Write back(백업) 해줘야 하기 때문에 읽기만 수행된 frame 을 내쫓는게 이득임

• 페이지 테이블에 Modify(dirty) bit 를 추가하여 해당 페이지가 write 된 적이 있는지 체크

Over allocation(= 메모리 크기보다 큰 페이지를 할당하는 것)을 막는 것 또한 중요함

Page replacement 순서

1. 디스크에서 요청한 페이지의 위치를 파악

2. Free frame 찾기

1. 있으면 로딩하고 페이지 테이블 수정

2. 없으면 Victim frame(쫓겨날 프레임)을 선정함

3. Victim frame 이 dirty(write 된 적이 있다면)하다면 disk에 write back

3. 해당 페이지를 Frame 에 로딩하고 페이지 테이블을 수정함

1. Victim frame 이 기존에 갖고 있던 페이지에는 invalid 표시를 함

2. 새롭게 할당받은 페이지에 victim frame 의 넘버와 valid 표시를 함

4. 명령어를 재시작

 

당연하게도 페이지 프레임이 늘어나면 늘어날수록 page fault 는 적게 일어남

 

Victim frame 을 선정하는 알고리즘

• FIFO(First In First Out) 알고리즘

• Optimal 알고리즘

• LRU(Least Recently Used) 알고리즘

• Second-Chance 알고리즘

• Enhanced second-chance 알고리즘

• Counting 알고리즘

• Page-Buffering 알고리즘

 

FIFO 알고리즘

Page fault 발생 시 먼저 들어온 순서대로 내보내는 알고리즘

페이지 요청 순서 : 7,0,1,2,0,3,0,4,2,3,0,3,0,3,2,1,2,0,1,7,0,1

 

효율성은 떨어지나 구현이 간단해서 종종 사용됨

효율성은 왜 떨어지냐?  → Belady’s Anomaly(Belady의 이상현상)

Belady’s Anomaly

프레임은 더 늘었는데 오히려 페이지 부재율이 더 증가하는 현상을 말함

 

Optimal 알고리즘

이론적으로 가장 최적인 알고리즘은 가장 나중에 사용되는 프레임을 쫓아내는 것임

하지만 이는 예측이 어렵기 때문에(미래를 봐야하기 때문에) 구현이 어렵다.(불가능에 가까움)

예를 들어 3번재 줄 7,0,1 에서 2번 페이지를 요구할 때 7이 쫓겨나는 것을 볼 수 있는데 0은 한 칸 뒤에서, 1은 12칸 뒤, 7은 16칸 뒤에서 사용되기 때문에 가장 나중에 사용되는 7이 내쫓기는 것임

 

LRU(Least Recently Used) 알고리즘

Optimal 알고리즘의 현실적인 버전으로, 최근에 가장 오래동안 사용되지 않은 것을 내쫓는 방법

미래를 내다볼 수는 없으므로 과거를 바라보는 관점. 3번째 줄 7,0,1에서는 LRU 를 사용할 수 없으므로 FIFO 를 사용했지만 이후부터는 사용 가능

5번째 줄(2, 0, 1)에서 6번째 줄(2, 0, 3)로 넘어갈 때 1이 내쫓긴 이유는 2는 2단계 전에, 1은 1단계 전에, 0은 3단계 전에 마지막으로 사용되었기 때문

LRU 구현방법

• Counter implementation : 프레임이 참조될 때마다 기록을 해두고 page replacement 될 때 이 기록을 탐색 -> 검색 시간이 오래걸림

• Stack implementation : 더 자주 사용되는 방법으로 프레임이 참조될 때마다 해당 프레임을 나타내는 링크드 리스트 노드를 Top 으로 이동시킴

•  Top 에 있을수록 최근에 사용된 것이며 Replace 시에는 bottom 을 내쫓음

• Double linked list = 중간에 있는 노드를 빼가려면 double 이 편하기 때문

• Double linked list 를 유지하는 비용 소모. 대신 검색 시간은 없음

 

LRU 는 실제로 구현하게 되면 추가적인 하드웨어가 필요하기도 하고, 매우 느리기 때문에 우회적인 방법으로 구현함

Reference bit 구현법

프레임 테이블에 참조될 때마다 1로 바뀌는 Reference bit 를 추가하여 Page replacement 수행 시 ref bit 가 0인 페이지를 내쫓는 방식

완전한 LRU 가 아니긴함. 왜냐면 참조된 순서를 알고 그 순서대로 내쫓아야하는데 단순 비트만으로는 순서를 알아낼 수 없기 때문

동작 방식

• 초기화는 0

• 해당 페이지가 참조되면 1

• Page replacement 수행 시 참조 비트가 0인 아무 페이지나 내쫓음

• 쭉 탐색할 때 참조비트가 1이면 해당 페이지를 내쫓지않고 비트를 0으로 되돌림 (다시 되돌아 왔을 때는 내쫓김)

Second-chance Page-replacement 알고리즘

일정 주기마다 모든 Reference bit 를 0으로 초기화하는 reference bit 알고리즘

Enhanced Second-chance 알고리즘

Reference bit 에 이어 Modify bit 도 추가하여 관리하는 기법. Modify bit 는 해당 페이지가 수정되었는지 여부를 기록함

(Ref, Mod) 기준

• (0, 0) : 최근에 참조되지도 않았고, 수정도 안된 페이지 = 가장 좋은 선택지

• (0, 1) : 최근에 참조되지 않았지만 수정은 된 페이지(처음에 불려오면서 수정되었거나, 굉장히 옛날에 수정된 경우)

• (1, 0) : 최근에 참조되었지만 수정은 안된 페이지

• (1, 1) : 최근에 참조되기도 했고, 수정도 된 페이지 = 최악의 선택지

Counting 알고리즘

• LRU

• LFU(Least Frequently Used) 알고리즘 : 일정 Period 동안 가장 적게 참조된 페이지 쫓아내는 알고리즘

• 잠깐동안 폭발적으로 사용되고 이후에 사용되지 않는 경우 성능이 저하됨

• 참조 횟수를 일정 시간마다 오른쪽 쉬프트하여 영향력을 감소시킴

• MFU(Most Frequentily Used) 알고리즘 : 일정 Period 동안 가장 많이 참조된 페이지를 쫓아내는 알고리즘

• 모든 Page 는 평균적으로 비슷한 횟수만큼 접근된다는 논리

• 순차탐색을 쭉 하는걸 여러번 하는 데이터 웨어하우스 같은 경우에 MFU 가 LRU 보다 유리함

• 구현 비용은 높으나 성능이 안나와 잘 사용되지 않음

페이지 버퍼링 알고리즘

Page replacement 기법과 병행하여 사용되는 알고리즘으로, 항상 가용한 Frame 을 풀(pool)에 몇 개 갖고 있고, 필요할 때 풀에서 꺼내주는 방식

• Write-back 을 해야 Free frame 이 나오는 상황에서는 해당 프로세스가 대기하는 시간이 너무 길어지니까 어느정도 가용 프레임을 항상 갖고 있으면서 일단 할당해주고, 나중에 천천히 Write-back 하여 성능을 개선.

• Write back 할 때에도 바로 디스크에 쓰지 않고, 버퍼에 썼다가 천천히 디스크에 write 할 수 있음. write 되는 도중에 해당 페이지가 다시 요구된다면 디스크에서 읽지않고 버퍼에서 읽어들일 수 있기에 더 빠름

• Disk 가 쉴 때마다 modify 된 페이지를 디스크에 틈틈히 write-back 해두고, modify bit 를 0으로 초기화함