[OSTEP] CH22 물리 메모리 크기의 극복 - 정책

CH22 물리 메모리 크기의 극복 - 정책 

빈 메모리 공간이 거의 없으면, 운영체제는 메모리 압박 Memory Pressure 을 해소하기 위해 

다른 페이지들을 강제적으로 페이징 아웃 Paging Out 하여 공간을 확보한다 

내보낼 Evict 페이지(들) 선택은 운영체제의 교체 정책 Replacement Policy 안에 집약되어 있다 

핵심 질문 - 내보낼 페이지는 어떻게 결정하는가
운영체제는 어떻게 메모리에서 내보낼 페이지(들)를 결정할 수 있을까? 이 결정은 시스템의 교체 정책에 의해서 내려진다
교체 정책은 보편 타당한 원칙들을 따르지만 코너 케이스를 피하기 위한 수정 사항들도 포함되어 있다 

22.1 캐시 관리 

시스템의 전체 페이지들 중 일부분만이 메인 메모리에 유지된다는 것을 가정하면

메인 메모리는 시스템의 가상 메모리 페이지를 가져다 놓기 위한 캐시로 생각될 수 있다 

캐시를 위한 교체 정책의 목표는 캐시 미스의 횟수를 최소화 (한편으로는 캐시 히트 횟수를 최대화) 하는 것이다

 

캐시 히트와 미스의 횟수를 안다면 프로그램의 평균 메모리 접근 시간 Average Memory Access Time, AMAT 을 계산할 수 있다 

Tm 은 메모리 접근 비용, Td 는 디스크 접근 비용, Pmiss 는 캐시에서 데이터를 못 찾을 확률 (미스) 을 나타낸다 

메모리의 데이터를 접근하는 비용은 항상 지불해야 하고, 메모리에서 데이터를 못 찾을 경우에는 디스크로부터 데이터를 가져오는 비용을 추가로 지불해야 한다 

현대 시스템에서는 디스크 접근 비용이 너무 크기 때문에 아주 작은 미스가 발생하더라도 전체적인 AMAT 에 큰 영향을 주기 때문에 

컴퓨터가 디스크 속도 수준으로 느리게 실행되는 것을 방지하기 위해서는 당연히 미스를 최대한 줄여야 한다

22.2 최적 교체 정책 

교체 정책의 동작 방식을 잘 이해하기 위해 최적 교체 정책 The Optimal Replacement Policy 과 비교하는 것이 좋다 

최적 교체 정책은 미스를 최소화한다 

Belady 는 가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 횟수의 미스를 발생시킨다는 것을 증명하였다 

가장 먼 시점에 접근하게 될 페이지보다 다른 페이지들을 먼저 참조할 것이기 때문에 이 주장은 참이다 

하지만 미래는 미리 알 수 없기 때문에 실제적이고 배포가 가능한 다른 방법을 찾아야 한다 

 

캐시는 처음에 비어 있는 상태로 시작하기 때문에 첫 번째 접근은 당연히 미스이고

이러한 종류의 미스를 최초 시작 미스 Cold-start miss 또는 강제 미스 Compulsory Miss 라고 한다 

22.3 간단한 정책 - FIFO 

FIFO 는 매우 구현하기 쉽다는 장점을 가진다 

시스템에 페이지가 들어오면 큐에 삽입되고, 교체를 해야 할 경우 큐의 테일에 있는 페이지가 내보내진다 

FIFO 는 블럭들의 중요도를 판단할 수가 없고, 최적의 경우와 비교하면 FIFO 는 눈에 띄게 성능이 안 좋다 

캐시의 크기가 커지면 캐시 히트율이 증가하는 것을 기대하겠지만, FIFO 를 사용하는 경우에는 더 안 좋아진다 
이 이상한 현상은 Belady's Anomaly 라고 불린다 
+ 일부 특수 페이지 접근 패턴에서는 프레임이 증가해도 불필요하게 교체가 많아진다
LRU와 같은 다른 알고리즘에서는 Stack Property 덕분에 프레임 수가 증가하면 미스가 줄어들지 않는다 
Stack Property : 캐시나 메모리 관리에서 특정 페이지 교체 알고리즘이 페이지 프레임 수가 증가할 때 캐시 성능이 악화되지 않는 특성을 의미한다 

22.4 또 다른 간단한 정책 - 무작위 선택 

무작위 선택 방식은 FIFO 와 유사한 성질을 가지고 있다, 구현하기 쉽지만 내보낼 블럭을 제대로 선택하려는 노력을 하지 않는다 

그렇기 때문에(?) 선택할 때 얼마나 운이 좋은지 (또는 운이 나쁜지)에 전적으로 의존한다

무작위 선택 방식의 동작은 그때그때에 따라 달라진다 

22.5 과거 정보의 사용 -  LRU 

어떤 프로그램이 가까운 과거에 한 페이지를 접근했다면 가까운 미래에 그 페이지를 다시 접근하게 될 확률이 높다 

페이지 교체 정책이 활용할 수 있는 과거 정보는 빈도수 Frequency 와 최근성 Recency 이 있고

이러한 류의 정책은 지역성의 원칙 Principle of Locality 이라고 부르는 특성에 기반을 둔다 

공간 지역성 Spatial Locality 어떤 페이지가 접근되었다면 그 페이지 주변의 페이지들이 참조되는 경향이 있다 
시간 지역성 Temporal Locality 가까운 과거에 참조되었던 페이지는 가까운 미래에 다시 접근되는 경향이 있다 

 

프로그램들은 특정 코드들과 자료 구조를 상당히 빈번하게 접근하는 경향이 있기 때문에 

과거 이력에 기반한 교체 알고리즘 부류가 탄생하게 되었다 

Least-Frequently-Used LFU 가장 적은 빈도로 사용된 페이지 교체 

Least-Recently-Used LRU 가장 오래 전에 사용하였던 페이지 교체 

LRU 는 최적 기법과 같은 정도 수준의 성능을 얻을 수 있다 

 

이와 반대되는 Most-Frequently-Used, MFU 와 Most-Recently-Used, MRU 와 같은 알고리즘도 존재하지만 

지역성 접근 특성을 사용하지 않고, 오히려 무시하기 때문에 대부분의 경우 잘 동작하지 않는다 

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

1) 지역성이 없는 워크로드

워크로드에 지역성이 없다면 어느 정책을 사용하든 상관이 없다 

모두 동일한 성능을 보이며, 히트율은 캐시의 크기에 의해서 결정된다 

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

미래를 알 수 있다면 교체 작업을 월등히 잘할 수 있다 🐣 너무 당연한 말 아님,..?

2) 80대 20 워크로드

20% 의 "인기 있는" 페이지에서 80% 의 참조가 발생하고, 나머지 80% 의 "비인기" 페이지에서 20% 참조만 발생한다 

랜덤과 FIFO 정책이 상당히 좋은 성능을 보이지만, LRU 가 더 좋은 성능을 보인다 (하지만 LRU 의 과거 정보도 완벽하지는 않다)

미스로 인한 영향이 그렇게 크지 않다면, LRU 로 얻을 수 있는 장점은 그렇게 중요하지 않다 

3) 순차반복 워크로드 

의외로, 무작위 선택 정책이 최적의 경우에 못 미치기는 하지만 눈에 띄게 좋은 성능을 보인다 

+ 연속적인 페이지를 순차적으로 접근한 다음, 다시 처음 페이지로 돌아와 순차 접근을 반복하는 패턴

순체적으로 페이지가 계속 순환되기때문에 FIFO와 LRU가 반복적으로 오래된 페이지를 교체하다가 다시 필요하게 되서 히트율이 낮아질 수 있음. → 0%

FIFO와 LRU는 적절한 캐시 크기를 확보하지 않으면 0% 히트율에 가까운 최악의 성능을 보일 수 있다.

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

LRU 를 완벽하게 구현하기 위해서는 많은 작업을 해야 한다 

각 페이지 접근마다 해당 페이지가 리스트에 가장 앞으로 이동하도록 자료 구조를 갱신해야 한다 

LRU 에서는 어떤 페이지가 가장 최근에 또는 가장 오래 전에 사용되었는지를 관리하기 위해 모든 메모리 참조 정보를 기록해야 한다 

 

이 작업을 좀 더 효율적으로 하기 위해서 약간의 하드웨어 지원을 받을 수 있고 

페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필드를 갱신하도록 하면, 페이지 교체 시에 시간 필드만 검사하면 된다 

 

시스템의 페이지 수가 증가하면 페이지들의 시간 정보 배열을 검색하는 것도 매우 고비용의 연산이 된다 

가장 오래된 페이지를 꼭 찾아야만 할까? 대신 비슷하게 오래된 페이지를 찾아가도 되지 않을까? 

22.8 LRU 정책 근사하기 

LRU 정책에 가깝게, "근사"하는 식으로 만들 수 있다 

이 개념에는 Use Bit (때로는 Reference Bit 라고도 불린다) 라고 하는 약간의 하드웨어 지원이 필요하다 

시스템의 각 페이지마다 하나의 Use Bit 가 있고, 이 Use Bit 는 메모리 어딘가에 존재한다 

페이지가 참조될 때마다 (읽히거나 기록되면) 하드웨어에 의해서 Use Bit 가 1  로 설정되고, 운영체제가 0 으로 바꿀 수 있다 

 

Use Bit 를 활용하는 방법에 시계 알고리즘 Clock Algorithm 이 있다 

시계 바늘 Clock Hand 이 특정 페이지를 가리킨다고 하면, 페이지를 교체해야 할 때 바늘이 가리키고 있는 페이지 P 의 Use Bit 가 1 인지 0 인지 검사하고, 만약 1 이라면 페이지 P 가 최근에 사용되어 교체 대상이 아니라는 뜻이다, P 의 Use Bit 가 0 으로 설정되고 (지워짐) 시계 바늘은 다음 페이지 P+1 로 이동하면서 Use Bit 가 0 으로 설정되어 있는 페이지를 찾을 때까지 반복된다 

(최악의 경우 모든 페이지들이 사용된 적이 있어서 모든 페이지를 모두 탐색하면서 Use Bit 를 전부 0 으로 설정해야 할 수도 있다)

그 외에 주기적으로 Use Bit 를 지우거나, 교체할 때 페이지들을 랜덤하게 검사하여 Refence bit 를 참고하는 기법도 있다 

22.9 갱신된 페이지 Dirty Page 의 고려 

🐣 Clock 알고리즘의 변형 : Second-Chance 알고리즘 🐣

시계 알고리즘에서, 운영체제가 교체 대상을 선택할 때 메모리에 탑재된 이후에 변경되었는지를 고려할 수 있다 

만약 어떤 페이지가 변경 Modified 되어 더티 Dirty 상태가 되었다면, 그 페이지를 내보내기 위해서 디스크에 변경 내용을 기록해야 하기 때문에 비싼 비용을 지불해야 한다 

하드웨어에 Modified bit (Dirty Bit 라고도 불림) 를 포함하여, 페이지가 변경될 때마다 Dirty Bit 를 1 로 설정하고

페이지 교체 알고리즘에서 이를 고려하여 교체 대상을 선택할 수 있다 

ex. 시계 알고리즘은 1) 사용되지 않은 상태이고, 2) 깨끗한 페이지를 먼저 찾아서 교체 대상으로 선정하고

만약 두 조건을 만족하는 페이지가 없다면, 수정되었지만 한동안 사용되지 않았던 페이지를 찾는다 

22.10 다른 VM 정책들 

운영체제는 언제 페이지를 메모리로 불러들일지 결정해야 한다

요구 페이징 Demand Paging 정책은 "요청된 후 즉시", 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어 들이는 정책이다, 운영체제는 어떤 페이지가 곧 사용될 것이라는 것을 대략 예상할 수 있기 때문에 미리 메모리로 읽어 들일 수 있고, 이와 같은 동작을 선반입 Prefetching 이라고 한다 (성공할 확률이 충분히 높을 때에만 해야 한다)

운영체제가 변경될 페이지를 메모리에 모은 후, 한 번에 디스크에 기록하는 정책도 있다

이 동작을 클러스터링 Clustering 또는 단순하게 쓰기 모으기 Grouping of writes 라고 부르며, 디스크 드라이브는 여러 개의 작은 크기의  쓰기 요청을 처리하는 것보다 하나의 큰 쓰기 요청을 더 효율적으로 처리할 수 있는 특성을 가지고 있기 때문에 효과적인 동작 방식이다

🐣 막둥 공부 내용 추가 

• 요구 페이징(Demand Paging) : 운영체제가 주로 사용하는 정책으로 페이지가 실제로 접근될 때 운영체제가 해당 페이지를 메모리로 읽어들인다. 처음에는 메모리에 없으므로 페이지 폴트가 발생하고, 그 이후에 해당 페이지를 디스크에서 불러온다.
• 프리페칭(Prefetching) : 페이지가 필요하기 전에 미리 메모리에 가져오는 방식이다. 현재 참조하고 있는 페이지와 인접한 페이지를 미리 가져와서 페이지 폴트를 줄이고 성능을 높이는 것이 목표다.
• 클러스트링은 데이터베이스나 파일 시스템에서 자주 쓰이는 최적화 방법이다 

+ 페이지 쓰기 정책

어떻게, 언제 페이지를 디스크에 쓸지를 결정하는 정책

페이지를 메모리에서 제거할 때마다 디스크에 쓰면, 디스크 입출력 횟수가 많아져서 성능이 떨어질 수 있다.

• 즉시 쓰기(Write-Through) : 페이지 변경때마다 즉시 디스크에 기록
• 지연 쓰기(Write-Back) : 페이지가 메모리에서 제거될 때 한 번에 디스크에 기록

22.11 쓰래싱 Thrashing 

메모리 사용 요구가 감당할 수 없을 만큼 많고, 실행 중인 프로세스가 요구하는 메모리가 가용 물리 메모리 크기를 초과하는 경우, 끊임없이 페이징을 할 수 밖에 없고, 이와 같은 상황을 쓰래싱 Thrashing 이라고 부른다 

몇몇 초기 운영체제들은 쓰래싱이 발생했을 때, 실행되는 프로세스의 수를 줄여서 나머지 프로세스를 모두 메모리에 탑재하여 실행하는 방법을 사용했다, 워킹 셋 Working Set 은 프로세스가 실행 중에 일정 시간 동안 사용하는 페이지들의 집합이다, 진입 제어 Admission Control 라고 알려져 있는 이 방법은 많은 일들을 엉성하게 하는 것보다 더 적은 일을 제대로 하는 것이 나을 때가 있다고 말한다 

일부 버전의 Linux 는 메모리 요구가 초과되면 메모리 부족 킬러 Out-of-Memory Killer 를 실행시켜서, 많은 메모리를 요구하는 프로세스를 골라 죽여 메모리 요구를 줄인다, 메모리 요구량을 줄이는 데는 성공적일지 몰라도, 만약 X 서버를 죽이게 되면 화면이 필요한 모든 응용 프로그램들을 쓸모없게 만들 수 있다 

22.12 요약 

탐색 내성 Scan Resistance 은 ARC [MM03] 와 같은 다수의 현대 알고리즘의 중요한 요소이다 

탐색 내성이 있는 알고리즘은 대개 LRU 와 유사하지만 LRU 가 최악의 경우에 보이는 행동을 방지한다 

🐣 특정 패턴의 메모리 접근이 캐시 성능에 미치는 부정적 영향을 줄이기 위해서 설계된 페이지 설계 알고리즘 🐣

 

요새는 메모리 접근 시간과 디스크 접근 시간의 차이가 점차 증가하기 때문에 빈번한 페이징을 감당할 수 없다 

과도한 페이징에 대한 최적의 해결책은, 그냥 더 많은 메모리를 구입하는 것이다