1. 캐시 관리
시스템의 전체 페이지들 중 일부분만 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다.
교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.
캐시 히트와 미스이 횟수를 안다면, 프로그램의 평균 메모리 접근 시간 (Average memory access time, AMAT) 을 계산할 수 있다.
은 메모리 접근 비용, 은 디스크 접근 비용 은 캐시 히트 확률, 는 캐시 미스 확률이다.
2. 최적 교체 정책
최적 미스 정책은 미스 발생 횟수를 최소화한다. 페이지를 내보내야할 때, 지금부터 가장 먼 시점에 필요하게 될 페이지를 버린다.
페이지 3 미스가 발생했을 때, 가장 과거에 참조된 페이지 0을 교체하게 된다.
그러나 미래는 일반적으로 알 수 없다. 그래서 실제적인 구현을 불가능하며, 해당 기법은 비교 기준으로서 다른 정책이 얼마나 ‘정답’에 가까운지 알 수 있을 것이다.
3. 간단한 정책: FIFO
시스템에 페이지가 들어오면 큐에 삽입되고, 교체 시에는 큐의 테일에 있는 페이지가 아웃된다.
페이지 3 미스 발생 시, 가장 나중에 접근되었던 페이지 2를 아웃시킨다.
4. 간단한 정책: 무작위 선택
메모리 압박이 있을 때, 페이지를 무작위로 선택하여 교체한다. 구현하기는 쉽지만, 내보낼 블럭을 제대로 선택하려는 노력은 하지 않는다. FIFO보다는 약간 더 좋은 성능을 보이고, 최적 정책보다는 약간 나쁜 성능을 보인다.
5. 과거 정보의 사용: LRU
스케줄링 정책에서와 같이 미래에 대한 예측을 위해 과거 사용 이력을 활용해보자. 어떤 프로그램이 최근에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 다시 접근하게 될 확률이 높다. 빈도수(frequency), 최근성(recency)이라는 과거 정보를 활용하고, 지역성의 원칙(principle of locality)라는 특성에 기반을 둔다.
두가지 방식이 있는데, Least-Frequently-Used(LFU)는 가장 적은 빈도로 사용된 페이지를 교체한다. Least-Recently-Used(LRU)는 가장 오래전에 사용된 페이지를 교체한다.
3번 페이지 미스 발생 시, 가장 오래전에 사용된 페이지 2를 아웃시킨다. 적어도 이 예제에서는, 지금까지 중에 가장 높은 히트 비율을 보여준다.
6. 워크로드에 따른 성능 비교
워크로드에 지역성이 없다면, 어느 정책을 사용하든 상관이 없다.
20%의 페이지들에서 80%의 참조가 일어나고, 나머지 80% 페이지들에 대해서 20%의 참조가 일어나는 상황이다.
FIFO, 무작위 정책보다 LRU가 더 좋은 성능을 보인다.
해당 워크로드는 50개의 페이지들을 순차적으로 참조한다. 1-50을 순차적으로 참조하는 것을 10000번 반복한다.
LRU와 FIFO 정책에서 좋지 못한 성능을 보인다. 오래된 페이지를 내보낸다는 특성으로 인해 캐시 크기가 49라고 할지라도 50개 페이지를 순차 반복하는 경우 히트율이 0%가 된다.
7. 과거 이력 기반 알고리즘 구현
LRU를 완벽하게 구현하기 위해서는 많은 작업이 필요하다. 페이지 접근마다 해당 페이지를 자료구조의 맨 앞으로 이동해야되고, 가장 오래전에 사용된 페이지 관리를 위해 모든 메모리 참조 정보를 기록해야한다.
이 작업을 더 효율적으로 하기 위해, 하드웨어의 지원을 받는다. 페이지의 접근이 있을 때마다 하드웨어가 시간 필드를 갱신한다. 이렇게 갱신된 시간 필드를 활용해 페이지 교체를 수행한다.
페이지 수가 증가하게 되면, 가장 오래 전에 사용된 페이지를 찾는 것은 매우 고비용의 연산이 된다. 가장 오래된 페이지를 꼭 찾아야만 할까? 대신 비슷하게 오래된 페이지를 찾아도 되지 않을까?
8. LRU 정책 근사하기
연산량이라는 관점에서 볼 때, LRU를 근사하는 식으로 만들면, 구현이 훨씬 쉬워진다. 실제로 현대의 많은 시스템도 이런 방식을 택하고 있다.
이 개념을 위해 use bit(reference bit)라는 약간의 하드웨어의 지원이 필요하다. 페이지가 참조될 때마다 하드웨어는 use bit를 1로 설정한다. 운영체제는 이를 0으로 바꾼다.
use bit를 적절히 활용하기 위한 방법 중, 시계 알고리즘(clock algorithm)이란 것이 있다. 시계 바늘이 특정 페이지를 가르키면서 use bit가 1이라면 최근에 사용되었다는 뜻이기 때문에 교체 대상이 되지 않는다. 해당 페이지의 user bit를 0으로 설정하고 다음 페이지를 가르킨다. use bit가 0일 페이지를 가르킨다면 그 페이지가 교체 대상이 된다. 최악의 경우(모든 use bit가 1인 경우) 모든 페이지를 다 돌 수도 있다.
완벽한 LRU보다 좋은 성능을 보이지는 않지만, 과거 정보를 고려하지 않는 다른 기법에 비해서는 성능이 더 좋다.
9. 갱신된 페이지(Dirty Page)의 고려
시계 알고리즘을 추가적으로 개선하기 위해서, OS가 페이지 교체 대상을 선택할 때, 메모리에 탑재된 이후에 변경 여부를 추가적으로 고려한다.
어떤 페이지가 변경되어 dirty 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비용이 비싸다. 만약 변경되지 않았다면 내보낼 때 추가 비용은 없다. 때문에 dirty page 대신 수정된 적 없는 페이지를 내보내는 것을 선호한다. 하드웨어는 이를 지원하기 위해 dirty bit(modified bit)를 둔다.
예를 들어, 시계 알고리즘은 교체 대상을 선택할 때 사용되지 않은 상태이고 깨끗한 페이지를 먼저 찾는다. 이런 페이지를 찾지 못할 경우, 수정되었지만(더티 상태이지만) 한동안 사용되지 않았던 페이지를 찾는다.
10. 다른 VM 정책들
페이지 교체 정책 말고도 여러 정책이 존재한다. 운영체제는 언제 페이지를 메모리로 불러들일지를 결정하기 위한 페이지 선택 정책이 존재한다.
대부분의 운영체제는 요구 페이징(demand paging) 정책을 사용한다. 말 그대로 “요청된 후 즉시” 즉, 페이지가 실제로 접근될 때 메모리로 읽어들인다.
운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 때문에 미리 메모리로 선반입(prefetching)할 수도 있다. 예를 들어 페이지 P가 탑재될 때, P + 1도 함께 탑재되어야 한다고 가정할 수 있다.
또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는데 관련된 방식이다. 한번에 한 페이지 씩 디스크에 쓰는 것이 아니라, 기록해야할 페이지를 메모리에 모은 후, 한 번에 기록한다. 이를 clustering 또는 grouping이라고 부른다.
11. 쓰래싱 (Thrashing)
메모리 사용 요구가 감당할 수 없을만큼 많고, 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 어떡할까?
이런 경우 시스템은 끊임없이 페이징을 할 수 밖에 없고, 이런 상황을 쓰래싱(Thrashing)이라고 한다.
몇몇 초기 운영체제들은 다수 프로세스 중 일부 프로세스의 실행을 중지시키고, 나머지 프로세스를 메모리에 올려 실행하도록 했다.
최신 운영체제들은 더 과감한 방법을 사용하기도 한다. 예를 들어, Linux의 일부 버전에서는 ‘메모리 부족 킬러’를 동작시켜 메모리 요구가 많은 프로세스를 강제로 종료함으로써 메모리 부족 상황을 해결하려고 시도한다. 이 방법은 효과적으로 메모리 부족 문제를 해결할 수 있지만, 중요한 프로세스를 종료하게 되면 다른 문제가 발생할 수 있다.
12. 요약
지금까지 언급했던 알고리즘의 중요성은 점차 퇴색되고 있다. 메모리 접근 시간과 디스크 접근 시간의 차이가 점차 증가하고 있기 때문이다. 디스크에 페이징 하는 비용이 너무 비싸기 때문에 빈번한 페이징을 감당할 수 다. 과도한 페이징에 대한 최적의 해결책은 아주 간단하다. 그냥 더 많은 메모리를 구입해라.
→ ??
