[운영체제] 페이지 교체 정책 알고리즘

메모리에 필요한 페이지가 있을 때는 잘 진행되지만, 없을 경우에는 문제가 생긴다. 프로세스가 필요로 하는 페이지가 없는 경우(page-fault) 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩하는데, 여기서 또다시 ‘페이지를 올릴 빈 프레임이 없을 경우’ 란 문제에 직면할 수 있다.
메모리까지 꽉 차있는 상황이라면 대상 페이지를 정하고 이를 쫓아낸 뒤 요구한 페이지를 메모리에 올려야 한다.
이 때 사용하는 것이 새로 올릴 페이지와 교체할 희생 프레임을 찾는 알고리즘, 페이지 교체 알고리즘이다.

OPT (optimal)

• 가장 나중에 참조되는 페이지를 빼겠다. (앞으로 가장 오랫동안 사용되지 않을 페이지)
• 미래의 정보를 알아야 함.

FIFO (first in first out)

• 메모리에 가장 먼저 들어온 순서대로 빼겠다.
• 단점
  Belady’s Anomaly의 문제점이 발생 - 캐시(frame)를 늘렸음에도 page falut가 더 늘어나는 상황 발생.

LRU (least-recently-used)

• 제일 옛날에 참조된 애를 빼겠다. (가장 오랫동안 사용되지 않은 페이지)
• OPT는 미래의 정보 예측, LRU는 과거의 정보
• stack algorithm은 Belady/s anomaly에서 자유롭다. 캐시를 많이 쓰면 최소 손해는 안본다.

---

LRU는 페이지 교체 알고리즘 중 자주 사용되고, 가장 좋은 성능을 나타낸다.
문제는 마지막으로 사용 된 시간(가장 오랫동안 사용되지 않은)을 어떻게 결정하느냐이다.

LRU를 구현하기 위한 방법

1. doubly linked list or stack
   • head와 tail, top과 bottom
   • 메모리를 한번 참조할 때마다 stack에서의 위치를 바꿔주는 형태로 업데이트 하면은, LRU를 구현할 수 있을 것이다.
   • victim은 항상 list tail 또는 stack bottom에서 선택이 되는 것으로 구현이 가능하다.
   • 문제점
     메모리 참조가 계속 일어날텐데 더블 링크드 리스트에서 빼올 때마다 포인터 최소 네개는 바꿔야 한다. victim 찾는 건 쉬운데, 참조가 많이 일어나는 단점이 존재한다.
2. CPU의 clock or counter 사용
   • 스택처럼 쓰지 말고, 시계를 사용해보자.
   • 페이지 테이블 항목에 가장 마지막으로 참조된 시간을 기록하자.
   • 메모리 참조가 일어날 때 마다, 포인터 네개 바꿔줄 필요 없이 count 값만 바꿔주면 되겠네! → 참조가 빨라진다.
   • victim 어떻게 찾아? count를 쫙 스캔하여 값이 가장 작은 애가 나중에 참조된 애 일것 (오랫동안 참조 안된 것)
   • 문제점
     그러나, 이 방법은 참조가 굉장히 빠른데, 작은 애를 뺄 때 다 뒤져봐야 해서 시간복잡도가 높음. (log n)
     갯수가 많아지면 많아질수록 victim을 찾는데 시간이 많이 들 것.

⇒ 위 두 방법은 똑같은 LRU 구현하는데, 철학적 접근이 완전히 다른 방법.

참조하는 시점을 빨리하는게 중요하다! → counter

• 그러나, 갯수가 많아지면 한도 끝도 없을 것. 포인터 네개를 바꾸는 것보다 성능이 더 안좋아짐.
• 타이머를 쓰게 되면 갯수가 정해져 있기에 (?) 오버플로우 될 가능성이 있음. 썩 좋은 방식은 아님.

---

성능 고려하면 위 둘다 쓸 수 없다. 현실에서 LRU 바로 사용 못함.

LRU를 Approximate 해서 사용해볼까?

LRU Approcimation Algorithms

• 정확히 LRU는 아닌데, LRU스럽게 동작하도록 만듬. 가장 옛날에 참조한 애를 빼는 것은 아니고, 대충 옛날부터 참조안된 애를 대충 찾아서 빼는 방식.
• 이러한 방식은 시간 복잡도를 확 낮추면서, LRU의 핵심 아이디어를 사용할 수 있는 방식이다.

1. Additional-Reference-Bits Algorithm

   • LRU를 구현하는 방식 중 counter를 가지고 estimation했던 것의 approcimation 버전
   • Reference bit을 사용하기 시작. 이 비트를 일정 시간 간격으로 기록하는 방식이다. 이는 운영체제가 아닌 MMU가 알아서 셋팅한다.
   • 페이지 테이블 내의 각 페이지에 8 bit짜리 참조 비트가 존재한다.
   • 다음 시점에 스캔 할 때의 reference 값을 그 전 reference bit 앞에 표시한다. 기존의 비트 수를 right shift하여 참조 비트 기록.
   • 이 비트 기록을 정수로 변환하였을 때, 가장 오랫동안 참조되지 않은 페이지는 가장 작은 정수값을 갖게 된다. 숫자가 크면 클수록 최근에 참조된 애. 따라서, 숫자가 작은 애를 찾으면 되겠네.

그런데, 이 counter는 approcimation를 하고 있음. 정확한 값을 보는게 아니라 time frame 안에 참조 됐는지 안됐는지만 보는 것.

counter part를 n bit shift가 가능한 array로 만들어놓고, 운영체제가 주기적으로 스캔하면서 각 페이지의 R bit를 앞에 계속 붙여가는 형태로 만들어 놓으면 counter overflow 없이 LRU 구현할 수 있는 방식이다.

counting은 잘할 수 있는데, 빼는 애를 찾아야할 때 오래 걸릴 것. 항상 쓸 순 없음.
페이지 갯수가 조금 적은 경우에 사용하는 것이 효율적이다.

2. Second-Chance Algorithm

   • 기본적으로 FIFO 알고리즘에 기반을 둔다.
   • MMU가 참조되는 페이지들의 reference bit을 돌면서 셋팅할 것.
   • 이 시점에서 누군가 페이지를 빼고, replace 해야하는 상황이 발생했으면, 현재 MMU가 가리키고 있는 애를 본다.
     • 봤더니 참조 안됐어. R == 0
       • 얘를 빼고 새로운애가 들어가면 됨. 한칸 전진 시킴. 다음 페이지 보려고 넘어감.
     • R == 1
       • 그 페이지는 교체되지 않고 (빠지지 않고) 한번의 기회를 더 얻게됨. 이 때, 해당 페이지의 R 비트는 0으로 초기화되고, 페이지 선택은 다음 페이지로 넘어감.
   • 빠져야 할 기회(R == 1)에 토큰을 반납하면서 한번 더 살아남겠다.
   • victim을 select하기 쉬움.
   • R 비트가 0인 페이지를 찾을 때 까지 페이지를 계속해서 순환하며 탐색하므로 원형 큐를 통해 구현
   • 최악의 경우, n개를 다 스캔해야 하기는 하지만, 보통 중간에 하나가 빠지게 되어 있음. 운이 좋으면 바로 빠질 수 있음.
   • 메모리 참조할 때 마다 리스트 바꾸지 않음. 하드웨어가 알아서 bit 세팅만 하며 지나감. 메모리 참조 할 때도 효과적으로 잘 뽑아냄.

3. Enhanced Second-Change Algorithm

   • Second-Chance Algorithm을 개선한 알고리즘
   • Reference bit과 Modify bit을 이용하여 victim page를 찾는 알고리즘
   • 내용이 바뀌었다. write를 했다. 의 여부를 표시하는 M (modify or dirty) bit 존재. → MMU가 알아서 셋팅.
   • read는 그냥 지나가고, write 관련 요청이 들어오면 알아서 MMU가 M = 1로 셋팅하고 해당하는 페이지 내용 바꿔줌. 이렇게 계속 돌아감.
   • victim을 뽑을 때
     • 참조도 안됐고 수정되지도 않은 애는 걍 빼버리면 됨.
     • 참조는 안됐는데, 수정은 됨 → 디스크 좀 써야함
     • 참조는 됐는데, 수정 안됨
     • 참조도 됐고, 수정도 됨. → 빼면 큰일. 다시 참조될 가능성이 높다는 뜻.