운영체제 18. 물리 메모리 크기의 극복 : 정책

18. 물리 메모리 크기의 극복 : 정책

• 빈 메모리 공간이 거의 없으면 운영체제는 메모리 압박(memory pressure)을 해소하기 위해 다른 페이지들을 강제적으로 페이징 아웃(Paging out)하여 활발히 사용중인 페이지들을 위한 공간을 확보한다. 내보낼(evict) 페이지 선택은 운영체제의 교체정책(replacement policy) 안에 집약되어 있다.

18.1 캐시관리

• 캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간(AMAT : average memory access time)를 계산할 수 있다.
• AMAT = TM + (PMISS - TD)
  • TM : 메모리 접근 비용
  • TD : 디스크 접근 비용
  • PMISS : 캐시에서 데이터를 못 찾을 확률
• 메모리의 데이터를 접근하는 비용은 항상 지불해야 한다. 그러나 메모리에서 데이터를 못 찾을 경우에는 디스크로부터 데이터를 가져오는 비용을 추가로 지불해야한다.
• 현대 시스템에서는 디스크 접근 비용이 너무 크기 떄문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 주게 된다.

18.2 최적 교체 정책

• 최적 교체 정책은 미스를 최소화한다.
• 가장 먼 시점에 필요한 페이지보다 캐시에 존재하는 다른 페이지들이 더 중요하다. 가장 먼 시점에 접근하게 될 페이지보다 다른 페이지들을 먼저 참조할 것이기 때문이다.
• 캐시는 처음에 비어 있는 상태로 시작하기 떄문에 첫 접근은 미스다. 이러한 종류의 미스를 최초 시작 미스(Cold-start miss) 또는 강제미스(compulsory miss)라고 한다. 그 다음에 페이지를 참조하면 캐시에서 히트된다. 캐시가 가득 차 있는 경우 교체정책이 실행되어야 하는데, 캐시에 탑재되어있는 페이지의 미래를 살펴보고 먼 시점에 접근할 페이지를 교체한다.

18.3 간단한 정책 : FIFO

• 구현하기 매우 쉽다는 장점이 있다.
• FIFO를 사용할 때 교체 결정은 쉽다. 순서 상 첫 번째로 들어온 페이지를 선택하면 된다.
• 최적의 경우와 비교하면 FIFO는 눈에 띄게 성능이 안좋다. FIFO는 블럭들의 중요도를 판단할 수가 없다. 단순히 메모리에 먼저 들어왔다는 이유로 페이지를 내보낸다.

18.4 또 다른 간단한 정책 : 무작위 선택

• 메모리 압박이 있을 때 페이지를 무작위로 선택하여 교체한다. 무작위 선택 방식은 FIFO와 유사한 성질을 가지고 있다. 구현하기 쉽지만 내보낼 블럭을 제대로 선택하려는 노력을 하지 않는다.
• 무작위 선택 정책은 선택할 때 얼마나 운이 좋은지에 전적으로 기대한다. 무작위 선택 방식의 동작은 그때 그때마다 달라진다.

18.5 과거 정보의 사용 : LRU

• 페이지 교체 정책이 활용할 수 있는 과거 정보 중 하나는 빈도수(Frequency)이다. 만약 한 페이지가 여러 차례 접근 되었다면, 분명히 어던 가치가 있기 떄문에 교체되면 안될 것이다. 좀 더 자주 사용되는 페이지의 특징은 접근의 최근성(recently)이다. 더 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높을 것이다.
• 이런 류의 정책은 지역성의 원리이라고 부르는 특성에 기반을 둔다. 이 원칙은 프로그램의 행동 양식을 관찰하여 얻은 결과이다. 이 원칙이 말하는 것은 단순하다. 프로그램들은 특정 코드와 자료구조를 상당히 빈번하게 접근하는 경향이 있다는 것이다.
• LFU(Least-Frequency-Used) 정책은 가장 적은 빈도로 사용된 페이지를 교체한다,
• LRU(Least-Recently-Used) 정책은 가장 오래전에 사용했던 페이지를 교체한다.

18.6 워크로드에 따른 성능 비교

지역성이 없는 워크로드

• 지역성이 없는 워크로드는 접근되는 페이지들의 집합에서 페이지가 무작위적으로 참조된다는 것을 의미한다. 워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다. 히트율은 정확히 캐시의 크기에 의해서 결정된다.
• 두 번째, 캐시가 충분히 커서 모든 워크로드를 다 포함할 수 있다면 역시 어느 정책을 사용하든지 상관없다. 참조되는 모든 블럭들이 캐시에 들어갈 수 있다면 역시 어느 정책을 사용하든지 상관없다. 참조되는 모든 블럭들이 캐시에 들어갈 수 있다면 모든 정책들은 히트율이 100%에 도달한다.
• 마지막으로, 최적 기법이 구현 가능한 기타 정책들 보다 눈에 띄게 더 좋은 성능을 보인다. 미래를 알 수 있다면 교체작업을 월등히 잘할 수 있다.

80대 20 워크로드

• 80대 20 워크로드는 20% 페이지들에서 80% 참조가 발생하고 나머지 80% 페이지에서 20% 참조만 발생한다. 랜덤과 FIFO가 상당히 좋은 성능을 보이지만, 인기있는 페이지들을 캐시에 오래두는 경향이 있는 LRU가 더 좋은 성능을 보인다.

순차 반복 워크로드

• 마지막 순차 반복 워크로드는 50개의 페이지를 순차적으로 참조한다. 여러 응용 프로그램에서 흔하게 볼 수 있는 이 워크로드는 LRU와 FIFO 정책에서 가장 안 좋은 성능을 보인다. 순차 반복 워크로드에서 이 알고리즘들은 오래된 페이지들을 내보낸다. 불행하게도 이 워크로드의 반복적인 특성으로 인해 오래된 페이지들은 정책들이 캐시에 유지하려고 선택한 페이지들보다 먼저 접근된다. 실제로, 캐시의 크기가 49라고 할지라도 50개의 페이지들을 순차 반복하는 워크로드에서는 캐시 히트율이 0%가 된다. 흥미롭게도 무작위 선택 정책은 최적의 경우에 못 미치기는 하지만 눈에 띄게 좋은 성능을 보인다. 무작위 선택 정책의 히트율은 최소한 0%는 아니다. 이렇게 무작위 선택은 몇 가지 좋은 특성을 가지고 있다는 것을 알 수 있다. 그 중 한 가지는 이상한 코너케이스가 발생하지 않는다는 것이다.

18.7 과거 이력 기반 알고리즘의 구현

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

18.8 LRU 정책 근사하기

• use bit(reference bit)라고 하는 하드웨어 지원이 필요하다. 시스템의 각 페이지마다 하나의 use bit가 있으며, 이 use bit는 메모리 어딘가에 존재한다. 페이지가 참조될 때마다 하드웨어에 의해서 use bit가 1로 설정된다. 하드웨어는 이 비트를 절대로 지우지 않는다. 0으로 바꾸는 것은 운영체제의 몫이다.
• 시계 알고리즘(clock algorithm)으로 활용한다. 시계 바늘(clock hand)이 특정 페이지를 가리킨다고 하자. 페이지를 교체해야 할때 운영체제는 현재 바늘이 가리키고 있는 페이지p의 use bit가 1인지 0인지 검사한다. 1이라면 p는 최근에 사용되었으며, 바람직한 교체 대상이 아니라는 것을 의미한다. p의 use bit는 0으로 설정되고 시계바늘은 다음 페이지 p+1로 이동한다. use bit가 0으로 설정되어 있는 페이지를 찾을 때 까지 반복된다. 완벽한 LRU만큼 좋은 성능을 보이지는 않지만 과거 정보를 고려하지 않는 다른 기법들에 비해서는 성능이 더 좋다.

18.9 갱신된 페이지(Dirty page) 고려

• 시계 알고리즘에 대한 추가 개선 사항은 운영체제가 교체 대상을 선택할 때 메모리에 탑재된 이휴에 변경되었지를 추가적으로 고려하는 것이다.
• 만약에 어떤 페이지가 변경(modified)되어 더티(dirty) 상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불해야 한다. 만약 변경되지 않았더라면 내 보낼 때, 추가 비용은 없다. 해당 페이지 프레임은 추가적인 I/O 없이 다른 용도로 재사용 될 수 있다. 때문에 어떤 VM 시스템들은 더티 페이지 대신 깨끗한 페이지를 내보내는 것을 선호한다.
• 이와 같은 동작을 지원하기 위해서 하드웨어는 modified bit(더티 비트라고도 한다)를 포함해야 한다. 페이지가 변경될 때마다 이 비트가 1로 설정되므로 페이지 교체 알고리즘에서 이를 고려하여 교체 대상을 선택한다.

18.10 다른 VM 정책들

• 페이지 선택(page selection) 정책 : 운영체제가 언제 페이지를 메모리로 불러들일지.
• 운영체제는 대부분 페이지를 읽어들일 때 요구 페이징(demand paging) 정책을 사용한다. 이 정책은 요청된 후 즉시, 즉 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어들인다. 운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 때문에 미리 메모리로 읽어들일 수도 있다. 이와 같은 동작을 선반입(prefetching)이라고 한다. 성공확률이 높을때만 한다.
• 또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는데 관련된 방식이다. 한번에 한 페이지씩 디스크에 쓸 수 있지만, 많은 시스템은 기록해야 할 페이지들을 메모리에 모은 후, 한번에 디스크에 기록한다. 이와 같은 동작을 클러스터링(Clustering) 또는 단순하게 쓰기 모으기(grouping of write)라고 부르며 효과적인 동작 방식이다. 왜냐하면 디스크 드라이브는 여러개의 작은 크기의 쓰기 요청을 처리하는 것보다 하나의 큰 쓰기 요청을 더 효율적으로 처리하는 특성을 갖고 있기 때문이다.

18.11 쓰래싱(Thrashing)

• 메모리 사용 요구가 감당할 수 없을만큼 많고 실행중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우 시스템은 끊임없이 페이징을 할 수 밖에 없고, 이와 같은 상황을 쓰래싱이라고 부른다.
• 몇며 초기 운영체제들은 쓰래싱이 발생했을 때, 이의 발견과 해결을 위한 상당히 정교한 기법을 가지고 있다. 다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지시킨다. 실행되는 프로세스의 수를 줄여서 나머지 프로세스를 모두 메모리에 탑재하여 실행하기 위해서다. 워킹셋(working set)이란 프로세스가 실행중에 일정시간동안 사용하는 페이지들의 집합이다. 일반적으로 진입제어(admission control)이라고 알려진 이 방법은 많은 일들을 엉성하게 하는 것보다는 더 적은 일을 제대로 하는 것이 나을 때가 있다고 말한다.
• 일부 최신 시스템들은 메모리 과부하에 대해 과감한 조치를 취한다. 일부 Linux는 메모리 요구가 초과되면 메모리 부족 킬러(out - of - memory killer)를 실행시킨다. 이 데몬은 많은 메모리를 요구하는 프로세스를 골라죽이는, 그다지 교묘하지 않은 방식으로 메모리를 줄인다. 메모리 요구량을 줄이는데는 성공적일지 몰라도, 이 방법은 문제가 될 수 있다.