본 글의 내용은 Operating Systems: Three Easy Pieces의 Beyond Physical Memory: Policies 챕터를 정리한 것입니다.

☑️ 개요

• 여유 메모리가 거의 남아있지 않으면 OS는 공간 확보를 위해 페이지를 page out하기 시작한다.

• 이때 어떤 페이지를 퇴출할지 결정하는 것은 OS의 교체 정책(replacement policy)에 포함되어 있다.

• 어떤 페이지를 제거할지 어떻게 결정할까? 몇 가지 일반적인 원칙을 따르며, 특정 조건을 회피하기 위한 조정도 포함된다.

☑️ 캐시 관리

• 페이지는 메모리 혹은 디스크에 존재하기 때문에, 사실상 메인 메모리가 모든 가상 메모리 페이지에 대한 캐시 역할을 한다고 볼 수 있다.

• 캐시를 사용한다면, 캐시 미스 횟수를 최소화하거나, 캐시 히트 횟수를 최대화하는 것을 목표로 할 수 있다.

• 캐시 미스와 히트 횟수를 알면 평균 메모리 접근 시간(AMAT)을 계산할 수 있게 되는데, 다음과 같은 형태를 띈다.
  

• Tm은 메모리 접근 비용, Pmiss는 캐시 미스 확률을 나타낸다. 또한 Td는 디스크 접근 비용이다.
  고로 메모리 접근 비용은 항상 지불하나, 실패하면 디스크에서 데이터를 가져오는 비용도 지불한다.

• 한 예시를 들어 히트가 10번 중에 9번 발생한다 하면, 미스 확률은 10%이다. 이때 메모리 접근 비용이 100ns이고, 디스크 접근 비용이 10ms라면 AMAT는 100ns + 10ms*0.1 = 1.0001ms가 된다.

• 만약 미스 확률이 0에 가깝다면 AMAT는 100ns에 수렴하기 때문에, 작은 미스 확률이라도 AMAT를 전반적으로 지배하게 된다. 따라서 가능한 많은 미스를 피하거나 디스크 속도에 맞춰 느리게 실행해야 한다.

☑️ 최적의 교체 정책

• 최적의 정책은 Belady에 의해 제시되었는데, 그것은 미래에 가장 멀리 접근될 페이지를 page out 시킨다는 것이다.
  

• 위 예시를 보면 첫 3개의 접근은 모두 미스가 발생하는데, 이때는 캐시가 비어있었기 때문이다. 이런 미스를 cold start miss(혹은 compulsotry miss. 강제 미스)라고도 한다.

• 예시의 교체 과정을 보면, 미래에 가장 늦게 접근되는 페이지를 캐시에서 제거하고 있다. 그것이 곧 최적의 정책인데, 사실 미래를 알 수 있는 방법은 세상에 없다. 그러나 최적의 정책이라는 것에 의의를 가지며, 이것은 완벽에 얼마나 근접했는지 알기 위한 지표로 사용된다.

☑️ 간단한 정책: FIFO

• 초기의 많은 시스템은 복잡함을 피하고 매우 간단한 교체 정책을 사용했다.

• 그 예시로 페이지를 단순히 대기열에 배치하고, 맨 뒤의 페이지(먼저 들어간 페이지)를 퇴출하는 FIFO를 사용했다.

• FIFO의 문제는 각 페이지의 중요성을 제대로 파악하지 못한다는 것이다.

☑️ 또 다른 간단한 정책: 랜덤

• 다른 단순한 정책으로는 무작위 선택인 랜덤이 있다. 무작위의 결과는 운에 따라 달라진다.

• 어떨 때는 최적에 가까운 성능을 보이지만, 때로는 훨씬 낮은 성능으로 적중한다.

☑️ 기록을 사용하기: LRU

• FIFO나 랜덤이나 미래에 다시 참조할 중요한 페이지를 내보낼 수 있다는 공통적인 문제를 안고 있다.

• 그래서 과거 기록을 기준으로 삼게 되는데, 여러 번 접근한 경우 해당 페이지가 가치 있다고 판단한다. 이런 계열의 정책은 지역성(locality)를 기반으로 하는 것이다.

• 이렇게 최근 접근 횟수가 가장 적은 페이지를 퇴출하는 LRU(Least-Recently-Used) 정책이 등장하였다.

💡 지역성의 종류

프로그램의 지역성에는 두 가지 유형이 있는데, 첫째로 공간 지역성이다. 특정 페이지 P에 접근한다면 그 근처의 페이지 또한 접근될 가능성이 높다.
둘째로는 시간 지역성으로, 가까운 과거에 접근된 페이지가 미래에도 다시 접근될 가능성이 높다는 것이다.
이런 지역성 원칙은 절대적인 것은 아니며, 하드웨어 혹은 소프트웨어 설계에 도움은 되지만 성공을 보장하지는 않는다.

☑️ 작업 종류에 따른 예시

• 이런 지역성이 전혀 없는 작업에서 각 정책은 어떤 결과를 보일까?
  

• 위 그래프를 통해 몇 가지 결론을 도출해낼 수 있다. 첫째로는 지역성이 없는 작업에는 어떤 정책을 사용하는지가 중요하지 않다는 것이다. LRU, FIFO, 랜덤 모두 동일한 성능을 보였다. 그러나 최적의 정책(미래를 내다보는 정책)에는 부족하다.

• 둘째로, 캐시의 크기가 작업의 크기와 동일해질수록 적중률이 100%로 수렴하게 된다.
  

• 다음 그래프는 80%의 참조가 전체 페이지의 20%에만 이루어지는 경우이다. 이때는 랜덤과 FIFO의 성능이 비슷하지만, 미래에 다시 참조될 가능성이 높은 페이지를 보유하는 LRU의 성능이 더 우수하다.

• 물론 LRU도 최적의 성능에는 미치지 못한다.
  

• 다음으로는 50페이지만 반복적으로 참여하는 작업이다. 이 경우에는 LRU와 FIFO 모두 최악의 경우를 나타낸다. 오래된 페이지를 제거하는데 특화된 정책들이 힘을 쓰지 못한다.

• 랜덤은 최적 수준은 아니지만 적어도 0이 아닌 적중률을 달성한다. 여기서 랜덤의 좋은 특성을 알 수 있는데 코너 케이스에 대응하지 못하는 상황이 발생하지 않는다는 것이다.

☑️ 기록을 사용하는 알고리즘 구현하기

• LRU는 FIFO나 랜덤보다 더 나은 성능을 발휘할 수 있지만, 어떻게 구현할 것인가가 문제가 된다.

• 페이지에 접근할 때 일부 데이터 구조를 갱신하여 해당 페이지를 리스트의 앞으로 이동시켜야 한다.

• 이런 접근 때문에 성능이 크게 저하될 수 있는데, 속도를 높이는 데 도움이 될 방법은 하드웨어 지원을 추가하는 것이다. 예시로 페이지에 접근할 때마다 ‘시간’에 관련된 필드를 갱신해줄 수 있다.

• OS는 시스템의 모든 ‘시간’ 관련 필드를 스캔해서 가장 최근에 사용된 페이지를 찾을 수 있는데, 이것은 페이지 수가 많을 수록 엄청난 비용이 소모된다. 그래서 절대 값 대신 근사치를 찾는 것을 목표로 한다.

☑️ LRU 근사치

• 근사치를 참조하기 위해 use bit(reference bit, 참조 비트)를 사용한다. Atlas 시스템에서는 페이지당 한 개의 use bit를 사용했는데, 이것은 메모리 어딘가에 존재했다.

• 페이지를 참조할 때마다 이 use bit는 1로 설정됐고, 추후 OS에 의해 0으로 변경되었다.

• 이렇게 1에서 0으로 바꾸는 작업에 clock hand 알고리즘을 사용했는데, 시스템의 모든 페이지가 원형으로 배열돼있다고 생각하고, 순차적으로 페이지의 use bit를 확인하는 방식이었다.

• 이때 페이지의 use bit가 1이면 0으로 변경하고 다음 페이지로 넘어가는 것을 반복했는데, 0으로 설정된 use bit를 찾을 때까지 계속 진행되었다.

• 이것이 유일한 방법은 아니며, 주기적으로 use bit를 지우는 방식도 가능했다.
  

• 이전 예시 중 LRU가 강세였던 메모리의 참조의 80%가 전체 페이지의 20%에만 발생하는 경우에, clock hand 알고리즘은 LRU와 거의 동일한 성능을 보인다. 즉, 말그대로 근사치를 보인다.

☑️ 더티 페이지 고려

• 이 clock hand 알고리즘에 하나의 조건을 더 추가할 수 있는데, 그것은 더티 비트를 확인하는 것이다.

• 페이지가 메모리에 올라온 이후 수정된 적이 있으면 더티 비트가 설정되는데, 수정된 페이지는 page out할 때 디스크에 다시 기록해야 되기 때문에 많은 비용을 소모한다.

• 그래서 수정되지 않은 페이지를 퇴출하는 것이 선호됐으며, 이 더티 비트를 사용해 수정되지 않은 페이지부터 퇴출 후, 그게 없다면 수정된 적이 있는 페이지를 퇴출하였다.

☑️ 기타 정책

• 페이지 교체 뿐만 아니라 페이지를 메모리에 언제 가져올 것인지에 대한 정책도 필요하다. 이것은 페이지 선택(page selection) 정책이라 부른다.

• 대부분의 OS는 단순히 demand paging을 사용하는데, 이것은 페이지에 접근하는 시점에 메모리에 로드하는 것이다. 이런 접근 시점을 추측해서 미리 가져올 수도 있는데, 그것은 prefetching이라 한다.

• 또 다른 정책은 페이지를 디스크에 쓰는 방법에 대한 것인데, 디스크에 여러 데이터를 몰아서 쓰는 것으로 비용을 절감하는 것을 클러스터링 혹은 그룹화라고 부른다.

☑️ Thrashing

• 실행 중인 프로세스들의 메모리 요구량이 사용 가능 메모리를 초과하는 경우에는 어떻게 할까? 이런 경우에 시스템이 지속적으로 페이징을 하면서 마비되어 버린다. 그것을 thrashing이라 한다.

• 이것을 대처하기 위해 프로세스의 일부를 실행하지 않기로 해버리는데, 메모리를 확보하는 것으로 적은 작업이라도 진행하는 것이 목표가 됐기 때문이다. 이것을 admission control이라 한다.

• 일부 Linux는 out of memory killer를 실행하여 메모리 intensive한 프로세스를 종료해버린다.

✅ 요약

• 페이지 교체 비용을 절감하기 위해 AMAT를 지표로 삼을 수 있으며, 페이지 미스를 줄이는 것을 목표로 한다.

• 미래를 내다보고 페이지 교체를 하는 것이 최적이지만, 현실적으로 불가능하고 그것을 기준으로 삼아 다른 정책들의 성능을 확인한다.

• 정책의 성능은 작업의 유형에 따라 달라지기도 한다.

• 단순한 FIFO, 랜덤 정책이 있으나 LRU가 보통 효율적이며, LRU를 구현하는 데에 어려움이 있어 그것에 근사치를 달성하는 clock hand 알고리즘을 활용한다.

• clock hand 알고리즘을 위해 use bit, 즉 최근 접근 여부를 활용하고, 알고리즘을 더욱 최적화 하기 위해 dirty bit를 사용하기도 한다. 수정되지 않은 페이지를 디스크에 보내는 것이 비용이 적다.

• 이전에는 디스크 접근 시간과 메모리 접근 시간의 차이가 너무 커서 페이지 교체 알고리즘의 중요성이 줄어들기도 하였으나, 최근에는 보조 저장 장치의 혁신으로 페이지 교체 알고리즘의 중요성이 다시금 커지고 있다.