OSTEP 22장

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

캐시 관리

메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있음 
캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것 
즉, 디스크로부터 페이지를 가져오는 횟수를 최소로 만드는 것이다.  (캐시 히트 최대화) 
캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간을 계산할 수 있다. 
캐시 성능을 측정할 때 사용하는 미터 법

TM - 메모리 접근 비용
TD - 디스크 접근 비용
PHit - 캐시 히트 확률
PMiss - 캐시 미스 확률 
PHit와 PMiss는 0.0 ~ 1.0 사이의 값을 갖으며, 둘의 합은 1.0을 만족한다. 
**
디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT에 큰 영향을 주게 됨

최적 교체 정책

미스를 최소화한다. 
가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다. 
간단하지만 구현하기 어려운 정책

0, 1, 2, 0, 1, 3, 0, 3, 1, 2, 1 순서대로 가상 페이지들을 접근 
캐시가 처음에는 비어있으므로 첫 세 번의 접근은 미스 발생 
이를 최초 시작 미스, 강제 미스라고 한다.
이후 페이지 3을 만나게 되면 미스가 발생하고 캐시가 가득 차 있어 교체 정책이 실행되어야 한다.

이 때, 2가 가장 먼 미래에 접근이 될 것이란 것을 알 수 있다.

그러므로 페이지 2를 내보내내게 된다. 

히트율 85.7% 
하지만 미래는 일반적으로 미리 알 수 없으므로, 범용 운영체제에서는 최적 기법 구현이 불가능하다. 

간단한 정책

페이지가 들어오면 큐에 삽입되고, 교체해야할 경우 가장 먼저 들어온 페이지를 내보내는 정책
구현하기 쉽지만 내보낼 블록을 제대로 선택하려는 노력을 하지 않는다.

무작위 선택

교체해야할 경우 무작위로 페이지를 선택하여 교체한다.
구현하기 쉽지만 내보낼 블록을 제대로 선택하려는 노력을 하지 않는다. 
선택 정책은 전적으로 운에 의존한다. 
FIFO 정책 보다는 약간 더 좋은 성능을 보이며, 최적 방법보다는 약간 나쁜 성능을 보인다.

무작위 선택 방식은 최적 기법 만큼 좋은 성능을 보이기도 하며, 때로는 매우 안 좋은 성능을 보인다.

LRU

과거 사용 이력을 활용해서 내보낼 페이지를 선택하는 정책
빈도수(frequency)와 최근성(recency)
이런 류의 정책은 지역성의 원칙이라고 부르는 특성에 기반을 둔다.
이 원칙은 프로그램의 행동 양식을 관찰하여 얻은 겨로가이다.
프로그램들은 특정 코드들과 자료 구조를 상당히 빈번하게 접근하는 경향이 있다.

Ex) 반복문 코드
LFU(Least Frequently Used) - 가장 적은 빈도로 사용된 페이지를 교체
LRU (Least Recently Used) - 가장 오래 전에 사용하였던 페이지를 교체

**
FIFO 정책에 비해 LRU는 과거 정보를 사용하여 더 좋은 성능을 보인다.

** LRU가 최적 기법과 같은 정도의 성능을 얻을 수 있는 최고의 결과를 보여준다.

워크로드에 따른 성능 비교

워크로드란 운영체제나 시스템이 실행하는 작업의 집합을 의미 
즉, 시스템에 의해 처리되어야하는 작업, 프로세스, 요청의 패턴이나 특성을 의미 

지역성이 없는 경우

접근되는 페이지들의 집합에서 페이지가 무작위적으로 참조된다. 
예제에서 100개의 페이지들이 일정 시간 동안 계속 접근하는 워크로드 사용

접근되는 페이지는 무작위적으로 선택되며, 페이지들이 총 10,000번 접근된다. 
실험에서 캐시의 크기를 매우 작은 것부터, 모든 페이지들을 담을 수 있을 정도의 크기까지 증가 시킴
워크로드에 지역성이 없다면 어느 정책을 사용하든 비슷한 성능을 보인다.
캐시가 충분히 커서 모든 워크로드를 다 포함할 수 있다면 어느 정책을 사용하든 상관 없음 
→ 캐시에 들어갈 수 있으면 모든 정책들은 히트율 100%에 도달 

최적 기법이 구현 가능한 기타 정책들 보다 눈에 띄게 더 좋은 성능을 보인다.

80대 20 워크로드

20% 페이지들(인기 있는 페이지)에서 80% 참조가 발생하고 나머지 80% 페이지들에 대해서 20%의 참조만 발생 
인기 있는 페이지들에 대한 참조가 실험 시간 대부분을 차지한다.

랜덤과 FIFO 정책이 상당히 좋은 성능을 보이지만, 
인기 있는 페이지들을 캐시에 더 오래두는 경향이 있는 LRU가 더 좋은 성능을 보인다.
인기 있는 페이지들이 과거에 빈번하게 참조되었기 때문에 그 페이지들은 가까운 미래에 다시 참조되는 경향이 있다. 
최적 기법은 여전히 더 좋은 성능을 보이고 잇으며 , LRU의 과거 정보가 완벽하지 않다는 것을 보임 

**
만약 각 미스로 인해 매우 비싼 값을 치뤄야 한다면, 히트율이 약간만 증가하더라도 성능에 큰 차이를 줌
반면 미스로 인한 영향이 그리 크지 않으면, LRU로 얻을 수 있는 장점은 크기 않음

순차 반복 워크로드

이 워크로드는 50개의 페이지들을 순차적으로 참조한다.

이 워크로드는 LRU와 FIFO 정책에서 가장 안 좋은 성능을 보인다.
→ 순차 반복으로 인해 두 정채의 히트율을 0%가 된다.

무작위 선택 정책의 경우 히트율은 최소한 0%는 아니다. 
→ 운 좋게도 다음에 다시 필요한 페이지가 교체되지 않고 남아 있을 수 있기 때문

이렇게 무작위 선택 정책은 몇 가지 좋은 특성을 가지고 있다. 
그 중 한가지는 이상한 코너 케이스가 발생하지 않는다는 것이다.
→ 복잡한 접근 패턴에 대해 예기치 않은 코너 케이스 발생

코너 케이스란 극단적으로 비효율적인 결과를 초래하는 경우 
무작위 선택 정책은 특정 접근 패턴에 대해 극단적인 성능 저하를 유발하는 일이 거의 없음 
→ 랜덤이므로 접근 패턴에 영향을 받지 않음

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

각 페이지 접근마다.(명령어 탑재나 로드 또는 저장하려는 각 메모리 접근) 해당 페이지가 리스트에 
가장 앞으로 이동하도록 자료 구조를 갱신해야한다.
LRU는 어떤 페이작 가장 최근에 또는 가장 오래 전에 사용되었는지를 관리하기 위해서
모든 메모리 참조 정보를 기록해야 한다.
세심한 주의 없이 정보를 기록하면 성능이 크게 떨어진다.
이 작업을 좀 더 효율적으로 하는 것은 하드웨어의 지원을 받는 것 
→ 페이지 접근이 있을 때마다 하드웨어가 메모리 시간 필드를 갱신
    Ex) 정보를 각 프로세스의 페이지 테이블에 포함 또는 물리 페이지마다 한 항목씩 할당된 배열로 보관

페이지가 접근되면 하드웨어가 시간 필드를 현재 시간으로 설정 
페이지 교체 시에 운영체제는 가장 오래 전에 사용된 페이지를 찾기 위해 시간 필드를 검사 

**
시스템의 페이지 수가 증가하면 페이지들의 시간 정보 배열 검색 비용이 커진다. 
→ 가장 오래된 페이지가 아닌 비슷하게 오래된 페이지를 찾으면 됨

LRU 정책 근사하기

가장 최적의 페이지 선택이 아닌 근사한 페이지를 찾는 것이 핵심 
이 개념에는 use bit라는 하드웨어가 필요함 
시스템의 각 페이지마다 use bit가 있으며, 이 use bit는 메모리 어딘가에 존재한다.
페이지가 참조될 때마다. use bit가 1로 설정된다. // 하드웨어는 이 비트를 절대 지우지 않음 
0으로 바꾸는 것은 운영체제가 수행

시계 알고리즘

- 시스템의 모든 페이지들이 환형 리스트를 구성한다고 가정
- 시계 바늘(clock hand)이 특정 페이지를 가리킨다고 함

1. 페이지를 교체해야할 때, 현재 바늘이 가리키고 있는 페이지 P의 use bit가 1인지 0인지 검사
2. 만약 1이라면, 페이지 P는 최근에 사용되었으며 바람직한 교체 대상이 아님
3. P의 use bit는 0으로 설정되고 시계 바늘은 다음 페이지 P + 1로 이동한다.
4. 최근에 사용된 적이 없는 페이지를 찾을 때까지 반복수행 

use bit를 사용하여 LRU를 근사하는 다른 방법 존재
주기적으로 use bit를 지우고, 교체 대상 페이지 선택을 위해 use bit가 1과 0인 페이지를 구분할 수 있으면 된다.

변형된 시계 알고리즘 

이 변형 방식은 교체할 때마다 페이지들을 랜덤하게 검사한다.

reference bit가 1로 설정되어 있는 페이지를 만나게 되면 비트를 지운다(0으로 설정)

reference bit가 0으로 설정되어 있는 페이지를 만나면 그 페이지를 교체 대상으로 선정 
완벽한 LRU 만큼 좋은 성능을 보이지 않지만, 과거 정보를 고려하지 않는 다른 기법들에 성능이 더 좋음

갱신된 페이지 고려

만약에 어떤 페이지가 변경되어 더티 비트가 1로 설정된 경우
그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불한다.
만약 변경되지 않았다면, 내보낼 때, 추가 비용은 없다. 

즉, 시스템은 수정된 페이지 보단 수정되지 않은 페이지를 내보내는게 선호
그래서 시스템은 dirty bit를 고려하여 희생자 페이지를 선택한다.
1. 수정되지 않았고 최근에 사용되지 않은 페이지 선택
2. 없다면 수정되었지만 최근에 사용되지 않은 페이지 선택

다른 VM 정책들

페이지 교체 정책만이 VM 시스템이 채택하는 유일한 정책이 아님 
예를 들어, 운영체제는 언제 페이지를 메모리로 불러들일지 결정해야 함
이 정책은 운영체제에게 몇 가지 다른 옵션을 제공
이는 페이지 선택 정책이라고 불린다.


운영체제는 대부분의 페이지를 읽어 들일 때, 요구 페이징 정책을 사용한다.
이 정책은 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어들인다. 
운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 예상할 수 있기 때문에 
미리 메모리로 읽어들일 수 있다.
이와 같은 동작은 선반입(prefetching)이라고 하며 성공할 확률이 높을 때에만 한다.
Ex) 어떤 시스템은 코드 페이지 P가 메모리에 탑재되면 P + 1이 접근될 확률이 높기 때문에 P가 탑재될 때 P + 1도 함께 탐재되어야 한다고 가정


또 다른 정책은 운영체제가 변경된 페이지를 디스크에 반영하는 데 관련된 방식
한 번에 한 페이지씩 디스크에 쓰는 것보단, 대부분의 시스템은 기록해야 할 페이지들을 메모리에 모은 후, 한 번에 디스크에 기록한다. 
이와 같은 동작을 클러스터링(clustering) 또는 단순하게 모으기(grouping of writes)라고 부르며,
효과적인 동작 방식이다. 왜냐하면 디스크 드라이브는 여러 개의 작은 크기의 쓰기 요청 처리 보다
하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있는 특성을 가지고 있다. 

- 디스크의 물리적 구조와 느린 접근 속도로 인해 한 번에 하는 것이 적합
- 디스크는 연속적인 데이터 전송 속도가 빠름, 한 번 디스크 헤드가 데이터를 쓰기 시작하면, 인접한 섹터나 트랙에 연속적으로 데이터 쓰는 것이 가능하므로, 데이터 전송 속도 향상
- 대부분의 디스크 드라이브는 쓰기 요청을 모아서 한 번에 처리할 수 있도록 쓰기 캐싱과 버퍼링 기능 제공
- 디스크 I/O 오버헤드 감소
각 I/O 요청은 오버헤드가 큼, 그러므로 한 번에 모아서 처리하는 것이 성능을 높인다.

쓰래싱

메모리 사용 요구가 감당할 수 없을 만큼 많고 실행 중인 프롯세스가 요구하는 메모리가 
가용 물리 메모리 크기를 초과하는 경우가 있다.
이런 경우 시스템은 끊임 없이 페이징을 하게 되는데 이를 쓰래싱이라고 부른다.

진입 제어
다수의 프로세스가 존재할 때, 일부 프로세스의 실행을 중지시켜, 프로세스의 수를 줄여 이를 해결

일부 최신 시스템들은 메모리 과부하에 대하여 좀 더 과감한 조치를 취한다.
Ex) 일부 버전의 리눅스는 메모리 요구가 초과되면 메모리 부족 킬러를 실행시킨다.
이 데몬은 많은 메모리를 요구하는 프로세스를 골라 죽이는, 그다지 정확하지 않은 방식으로 메모리 요구를 줄인다.  때문에 메모리 요구량을 줄이는데 성공적일지언정, 이 방법은 문제가 될 수 있다. 
→ 만약 서버를 죽이게 되면 화면이 필요한 모든 응용 프로그램들을 쓸모 없게 만든다.

기타

지금까지 언급한 알고리즘의 중요성은 점차 퇴색되고 있다.
메모리 접근 시간과 디스크 접근 시간의 차이가 점차 증가하고 있기 때문
디스크에 페이징 하는 비용이 너무 비싸기 때문에 빈번한 페이징을 감당할 수 없다.
과도한 페이징에 대한 최적의 해결책은 아주 간단하다.

그냥 더 많은 메모리를 구입해라