캐시 관리
- 시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면, 메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다.
- 이 캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화하는 것이다.
- 캐시 히트와 미스의 회수를 안다면,
평균 메모리 접근 시간(average memory access time. AMAT)을 계산할 수 있다.
AMAT = (PHit * TM) + (PMiss * TD)
PHit: 캐시에서 데이터를 찾을 확률
TM: 메모리 접근 비용
PMiss: 캐시에서 데이터를 못 찾을 확률
TD: 디스크 접근 비용
- 현대 시스템에서는 디스크 접근 비용이 너무 크기에 아주 작은 미스가 나더라도 전체적인 AMAT에 큰 영향을 주게 된다. 따라서 최적 교체 전략이 그만큼 중요하다.
최적 교체 정책(The Optimal Replacement Policy)
가장 나중에 접근될 페이지를 교체하는 것이 최적이다.- 범용 운영체제에서 최적 기법 구현은 불가능하기에, 이는 비교기준으로만 사용된다.
간단한 정책: FIFO
- 교체를 해야 할 경우 먼저 들어온 페이지(큐에 테일에 있는 페이지)가 내보내진다.
- 구현하기가 매우 쉽다.
- 캐시의 크기가 커지면 캐시 히트율이 증가하는데, FIFO의 경우는 더 안좋아진다. (Belady`s anomaly)
- 최적의 경우와 비교했을 때 성능이 눈에 띄게 좋지 않다.
또 다른 간단한 정책: 무작위 선택
- 메모리 압박이 있을 때 페이지를 무작위로 선택하여 교체한다.
- 무작위 선택 방식이 FIFO보다는 약간 더 좋은 성능을 보이며 최적의 방법보다는 약간 나쁜 성능을 보인다.
과거 정보의 사용: LRU
- 지역성의 원칙(principle of locality), 어떤 페이지가 여러 차례 접근 되었다면 분명 어떤 가치가 있는 것이다. 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높은 것이라는 원칙이다.
- LFU(Least-Frequently-Used 정책은 가장 적은 빈도로 사용된 페이지를 교체한다.
- LRU(Least-Recently_Used 정책은 가장 오래 전에 사용하였던 페이지를 교체한다.
- MFU(Most-Frequently_USED), MRU(Most-Recently-Used): 대부분의 경우 이러한 정책은 잘 동작하지 않는다. 지역성 접근 특성을 무시하기 때문이다.
워크로드에 따른 성능 비교
1. 지역성이 없는 워크로드
- 워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다.
- 캐시가 충분히 커서 모든 워크로드를 포함할 수 있다면 어느 정책을 사용하든 상관이 없다.
- 최적 기법이 구현 가능한 기타 정책보다 눈에 띄게 좋은 성능을 보인다.
2. 80 대 20 워크로드
- 20%페이지에서 80%의 참조가 발생하고 나머지 80%페이지들에 대해서 20%참조만 발생하는 경우를 말한다.
- 랜덤과 FIFO정책이 상당히 좋은 성능을 보이지만, 인기 있는 페이지들을 캐시에 더 오래두는 경향이 있는 LRU가 더 좋은 성능을 보인다.
3. 순차 반복 워크로드
- LRU와 FIFO 정책에서 가장 안좋은 성능을 보인다.
- 랜덤 선택 정책은 최적의 경우에 못 미치기는 하지만 눈에 띄게 좋은 성능을 보인다. 즉, 이 방식은 코너 케이스를 방지할 수 있다.
과거 이력 기반 알고리즘 구현
- LRU를 완벽하게 구현하기 위해선 많은 작업이 필요하다.
- 각 페이지 접근마다 해당 페이지가 리스트에 가장 앞으로 이동하도록 자료구조를 갱신해야 한다.
- LRU에서는 어떤 페이지가 가장 최근에 또는 가장 오래 전에 사용되었는지를 관리하기 위해서 모든 메모리 참조 정보를 기록해야 한다.
- 하드웨어의 지원을 받으면 좀 더 효율적으로 할 수 있다. 예를 들어 페이지 접근이 있을 때마다
하드웨어가 메모리의 시간 필드를 갱신하도록 할 수 있다.
- 페이지 교체 시에 운영체제는 가장 오래 전에 사용된 페이지를 찾기 위해 시간 필드를 검사한다.
- 시스템의 페이지 수가 증가하면 페이지들의 시간 정보 배열을 검색하여 가장 오래 전에 사용된 페이지를 검색하는 것은 매우 고비용의 연산이다.
LRU를 완벽히 구현하는 것은 비싼 비용이 든다.
어떻게 하면 효율적으로 유사하게 구현할 수 있을까?
시계 알고리즘(Clock Algorithm)
- 시스템의 모든 페이지들이 원형 연결 리스트를 구성한다고 가정하고, 시계 바늘(clock hand)이 특정 페이지를 가리킨다고 해보자.
- 현재 바늘이 가리키고 있는 페이지의 use bit가 1인지 0인지 검사한다.
- 1이라면 P는 최근에 사용되었으며 바람직한 교체 대상이 아니므로 use bit는 0으로 설정되고 시계 바늘은 다음 페이지 P + 1로 이동한다.
- 알고리즘은 최근에 사용된 적이 없는 페이지를 찾을 때까지 반복된다.
- 변형된 시계 알고리즘
- 교체할 때 페이지들을 랜덤하게 검사한다.
- reference bit가 1로 설정되어 있는 페이지를 만나면 비트를 지운다. (0으로 설정한다)
- reference bit가 0으로 설정되어 있는 페이지를 만나면 그 페이지를 교체 대상으로 설정한다.
갱신된 페이지(Dirty Page)의 고려
- 어떤 페이지가 변경(modified)되어 더티(dirty)상태가 되었다면, 그 페이지를 내보내기 위해서는 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불해야 한다.
- 이와 같은 지원을 위해서는 하드웨어는 modified bit(더티 비트)를 포함해야 한다.
- 페이지가 변경될 때 마다 이 비트가 1로 설정되므로 페이지 교체 알고리즘에서 이를 고려하여 페이지를 선택한다.
- 사용되지 않은 상태이고, 깨끗한 페이지를 우선적으로 찾는다.
다른 VM 정책들
요구 페이지(demand page)
- 요청된 후 즉시, 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어들인다.
- 운영체제는 어떤 페이지가 곧 사용될 지 대략 예상할 수 있기에 미리 메모리로 읽어들일 수 있다.
- 이러한 선반입(prefetching)은 성공할 확률이 충분히 높을 때만 한다.
클러스터링(clustering)
- 기록해야 할 페이지들을 메모리에 모은 후 한 번에 디스크에 기록하는 방식을 말한다.
쓰레싱(thrashing)
- 메모리 사용 요구가 과도하게 많고, 가용 물리 메모리 크기를 초과할 때 시스템은 끊임없이 페이지를 할 수 밖에 없는 상황을
쓰레싱(thrashing)이라고 부른다.
- 해결을 위해 실행되는 프로세스의 수를 줄여서 나머지 프로세스를 모두 메모리에 탑재하여 실행시킨다. (워킹셋: 프로세스가 실행 중에 일정 시간동안 사용하는 페이지들의 집합)
- 일부 시스템에서는 메모리 부족 킬러(out-of_memory killer)를 실행시킨다. 이는 교묘하지 않은 방식으로 메모리 요구를 줄인다.