OSTEP 22 Swapping Policies

내보낼 페이지는 어떻게 결정할까? 교체 정책에 의해 이 결정이 내려진다. 교체 정책을 자세히 알아보자.

1. 캐시 관리

시스템의 전체 페이지들 중 일부만이 메인 메모리에 유지된다는 것은, 메인 메모리는 가상 메모리의 페이지를 가져다 놓기 위한 캐시로 생각할 수 있다. 즉, 디스크로부터 페이지를 가져오는 횟수를 최소한으로 하는 것이 우리의 목표다.

캐시 히트와 미스이 횟수를 안다면, 프로그램의 평균 메모리 접근 시간 (Average memory access time, AMAT) 을 계산할 수 있다.

$P_{Hit}$는 캐시 히트 확률, $P_{Miss}$는 캐시 미스 확률, $T_{M}$은 메모리 접근 비용, $T_{M}$은 디스크 접근 비용이다.

2. 최적 교체 정책

최적 교체 정책은 미스를 최소화한다. 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다는 것이 증명되었다.

페이지 3을 처음으로 접근할 때, 캐시 미스가 발생한다. 어떤 페이지를 내보내야 할까? 0, 1, 2 중에서 가장 나중에 접근한 2를 내보내는 것이 최적이다.

하지만 미래를 아는 것은 일반적으로 불가능하다. 이 최적 기법은 다른 정책들과 비교하는데만 사용 될 것이고, 그 정책이 얼마나 정답에 가까운지 알 수 있을 것이다.

3. 간단한 정책: FIFO

시스템에 페이지가 들어오면 큐에 삽입되고, 교체를 해야 할 경우 큐의 테일에 있는 페이지(먼저 들어온 페이지)가 내보내진다. FIFO는 매우 구현하기 쉽다.

3번 페이지에 처음 접근할 때 가장 처음 들어온 0번 페이지가 나가게 된다.

4. 무작위 선택

이 방식은 메모리 압박이 있을 때 페이지를 무작위로 선택하여 교체한다. FIFO처럼 구현하기 쉽지만 내보낼 블럭을 제대로 선택하려는 노력을 하지 않는다.

FIFO보다는 약간 더 좋은 성능을 보이며, 최적의 방법보다는 약간 나쁜 성능을 보인다.

5. 과거 정보의 사용: LRU

과거 사용 이력을 활용해 보자. 예를 들어 어떤 프로그램이 가까운 과거에 한 페이지를 접근했다면, 가까운 미래에 그 페이지를 다시 접근하게 될 확률이 높다. 이런 류의 정책은 지역성의 원칙 (principle of locality) 이라고 부르는 특성에 기반을 둔다.

Least Frequently Used (LFU) 정책은 가장 적은 빈도로 사용된 페이지를 교체한다. Least Recently Used (LRU) 정책은 가장 오래 전에 사용하였던 페이지를 교체한다.

3번 페이지에 처음 접근했을 때, 운영체제는 2번 페이지를 내보낸다. 0번 페이지와 1번 페이지가 최근에 사용되었기 때문이다. 그 후에는 0번 페이지를 내보낸다. 1번 페이지와 3번 페이지가 최근에 사용되었기 때문이다.

두 경우 모두 LRU는 과거 정보를 활용하였고, 결과적으로 이후의 참조들에서 히트가 발생하였다는 것을 보면 결정이 옳았다는 것을 알 수 있다.

6. 워크로드에 따른 성능 비교

80대 20 워크로드는 20%의 페이지들에서 80%의 참조가 발생하고, 나머지 80%의 페이지에서 20%의 참조가 발생한다. 인기 있는 페이지를 두는 LRU가 더 좋은 성능을 보인다.

이 워크로드는 50개의 페이지를 순차적으로 참조한다. 그 후 다시 처음으로 돌아가서 그 접근 순서를 반복한다.

LRU와 FIFO 정책에서 좋지 못한 성능을 보인다. 오래된 페이지를 내보낸다는 특성으로 인해 캐시 크기가 49라고 할지라도 50개 페이지를 순차 반복하는 경우 히트율이 0%가 된다.

7. 과거 이력 기반 알고리즘 구현

LRU 정책을 완벽하게 구현하기 위해서는 많은 작업을 해야한다. 각 페이지 접그남다 해당 페이지가 리스트의 가장 앞으로 이동하도록 자료 구조를 갱신해야 한다. 어떤 페이지가 가장 최근에 또는 가장 오래 전에 사용되었는지를 관리하기 위해서 모든 메모리 참조 정보를 기록해야 한다.

이 작업을 효율적으로 하는 법은 약간의 하드웨어 지원을 받는 것이다. 예를 들어 페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필드를 갱신하도록 할 수 있다. 이렇게 하여 페이지가 접근되면 하드웨어가 시간 필드를 현재 시간으로 설정한다. 페이지 교체 시에 운영체제는 가장 오래 전에 사용된 페이지를 찾기 위해 시간 필드를 검색한다.

페이지 수가 증가하면 페이지들의 시간 정보 배열을 검사하는 일이 매우 고비용의 연산이 된다. 가장 오래된 페이지를 꼭 찾아야 할까? 비슷하게 오래된 페이지를 찾아도 되지 않을까?

8. LRU 정책 근사

LRU를 근사하여 연산량을 줄일 수 있다. 이 개념에는 use bit 라고 하는 약간의 하드웨어 자원이 필요하다. 시스템의 각 페이지마다 하나의 use bit가 있으며 이 use bit는 메모리 어딘가에 존재한다.

페이지가 참조될 때마다 하드웨어에 의해서 use bit가 1로 설정된다. 하드웨어는 이 비트를 절대로 지우지 않는다. 운영체제만 0으로 바꿀 수 있다.

운영체제는 LRU에 가깝게 구현하기 위해 use bit를 어떻게 활용할까? 시계 알고리즘에 대해 알아보자. 시스템의 모든 페이지들이 환형 리스트를 구성한다고 가정하고, 운영체제는 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사한다. 만약 1이면 최근에 사용되었고, 바람직한 교체 대상이 아니라는 것이다. P의 use bit를 0으로 바꾸고 다음 페이지 P+1로 바늘을 이동한다. 이런 방식으로 use bit가 0인 페이지를 탐색한다. 최악의 경우 모든 페이지를 돌면서 use bit를 전부 0으로 설정하게 될 수도 있다.

미사용 페이지를 찾기 위해 매번 모든 메모리를 검사하지 않아도 된다.

9. 갱신된 페이지 (Dirty Page) 의 고려

어떤 페이지가 변경되어 dirty 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비용이 비싸다. 만약 변경되지 않았다면 내보낼 때 추가 비용은 없다. 때문에 dirty page 대신 수정된 적 없는 페이지를 내보내는 것을 선호한다. 하드웨어는 이를 지원하기 위해 더티 비트를 둔다.

예를 들어 시계 알고리즘으로 교체 대상을 선택할 때, 사용되지 않은 상태이고 깨끗한 페이지를 먼저 찾도록 하고, 이를 만족하는 대상을 찾지 못하는 경우, 깨끗하지 않지만 (dirty 상태이지만) 한동안 사용되지 않았던 페이지를 찾도록 할 수 있다.

10. 다른 VM 정책

페이지 교체 정책 외에도 다른 정책들이 존재한다. 예를 들어, 운영체제는 언제 페이지를 메모리로 불러들일지 결정해야 한다. 이 정책은 페이지 선택 (page selection) 정책 이라고 불린다.

운영체제는 대부분의 페이지를 읽어 들일 때 요구 페이징 정책을 사용한다. 이 정책은 요청된 후 즉시, 페이지가 실제로 접근 될 때 운영체제가 해당 페이지를 메모리로 읽어 들인다.

요청됐을 때 메모리로 읽어 들이는 대신, 어떤 페이지가 곧 사용될 것이라는 것을 예상하여 선반입하는 경우도 있다. 어떤 시스템은 페이지 P가 탑재될 때 P+1이 접근될 확률이 높기 때문에 P+1도 함께 탑재되도록 할 수 있다.

또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는 데 관련된 방식이다. 한 번에 한 페이지씩 디스크에 쓸 수 있지만, 기록해야 할 페이지들을 메모리에 모은 후, 한 번에 디스크에 기록할 수 있다. 이와 같은 동작을 클러스터링(clustering) 이라고 부르며 효과적인 동작 방식이다.

11. 쓰래싱 (Thrashing)

메모리 사용 요구가 감당할 수 없을 만큼 많고 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 운영체제는 어떻게 해야 할까?

이런 경우 운영체제는 끊임없이 페이징을 하게 될 것이고 이와 같은 상황을 쓰래싱 (Thrashing) 이라 부른다.

몇몇 초기 운영체제들은 다수 프로세스 중 일부 프로세스의 실행을 중지시키고, 나머지 프로세스를 메모리에 올려 실행하도록 했다.

최신 운영체제들은 더 과감한 방법을 사용하기도 한다. 예를 들어, Linux의 일부 버전에서는 ‘메모리 부족 킬러’를 동작시켜 메모리 요구가 많은 프로세스를 강제로 종료함으로써 메모리 부족 상황을 해결하려고 시도한다. 이 방법은 효과적으로 메모리 부족 문제를 해결할 수 있지만, 중요한 프로세스를 종료하게 되면 다른 문제가 발생할 수 있다.