페이지 교체 정책(Page Replacement Policy)

Page Replacement Policy

• evict할 페이지를 고르는 여러가지 알고리즘

OPT(Belady’s Algorithm)

• 앞으로 가장 오랫동안 사용되지 않을 페이지를 빼는 알고리즘
• page fault가 나면, 가장 나중에 참조될 페이지를 빼는 방식이다. 대신 이 방식은 어느 페이지가 참조될 지 알아야 한다는 단점이 있다. 대부분의 현실 컴퓨팅의 경우 미래에 어느 페이지가 참조될 지 아는 것은 불가능하다. 따라서 belady’s algorithm은 다른 알고리즘의 효율성을 따지는 평가기준으로 많이 쓰인다.

FIFO

• 가장 먼저 들어온 페이지를 가장 먼저 빼는 알고리즘
• 가장 직관적이고 일반적인 방법이다. 하지만 이 알고리즘에는 치명적인 문제점이 있는데, 이를 belady’s anomaly라고 부른다.
• belady’s anomaly란, page frame이 커졌지만, page fault rate가 증가하는 문제이다. 즉, 메모리를 하나 더 쓰느라 돈을 쓰고도 컴퓨터 성능이 떨어지는 것을 의미한다.

LRU(Least Recenty Used)

• 가장 과거에 참조된 페이지를 빼는 알고리즘
• OPT 방식에서 변형된 것으로, 우리가 미래를 보고 판단할 수 없으니, 과거를 보고 미래를 예측하는 것이다.
• 만약, n개의 page frame을 가지고 있을 때, page frame이 1,2,3,4, …n 라는 페이지를 포함한다고 하자. 이 때, n+1개의 page frame으로 늘어나도 page frame이 1,2,3,4,…n을 무조건 포함하고 있는 경우를 stack algorithm이라고 한다.
• LRU Algorithm은 stack algorithm의 한 예시이다. 따라서 LRU는 belady’s anomaly를 겪지 않는다.
• LRU를 구현하는 방식은 크게 두 가지가 있다.
  • doubly linked list
    • 페이지들을 linked list 형식으로 구현하여 관리하는 방식이다.
    • 이 방식은 evict 할 때, tail을 자르면 되므로, evict 하기 빠르다는 장점이 있지만, linked lsit를 매번 업데이트 해줘야 하므로, 페이즈를 참조할때는 느리다는 단점이 있다.
  • clock or counters
    • 각 page frame마다 시간을 기록할 수 있는 변수를 두고, 페이지가 참조될 때마다 clock을 업데이트 해주는 방식이다.
    • 이 방식은 참조될 때마다 clock을 업데이트해주기만 하면 되므로 페이지를 참조할 때 빠르다는 장점이 있지만, evict 페이지를 찾으려면 전체를 다 살펴봐야 하므로, evict하기 느리다는 단점이 있다.

LRU Approximation Algorithm

• 근사적으로 늦게 참조된 페이지를 찾는 방식을 사용하는데, 이를 LRU Approximation Algorithm이라고 한다.
• 크게 reference bit을 사용하는 방법과 second chance algorithm이라는 방식이 있다.
  • reference bit
    • 각 page를 나타내는 pte의 reference bit은 참조될 때마다 1로 세팅된다.
    • 특정 시간 간격을 두고 reference bit를 모아서, 모인 값이 가장 작은 페이지를 evict하는 방식이다.
  • second chance algorithm(clock algorithm)
    • 페이지들이 시계 모양의 ring buffer형식으로 구현되어 있는 상태에서 특정 페이지가 참조되면 reference bit을 1으로 바꿔준다. 그리고 특정 페이지를 evict해야 한다면, 시계바늘이 가리키고 있는 페이지를 evict 하려고 한다. 다만 이 때, 시계바닐이 가리키는 페이지의 reference bit가 0이면 그냥 evict하고, 1이면 0으로 만들고 시계바늘을 한칸 옮긴다.