[OS/OSTEP] 22.vm-beyondphys-policy : 메모리 교체 정책 - LRU,FIFO,OPTIMAL,RANDOM,CLOCK #16

22.vm-beyondphys-policy

# 시작하며

 교체 정책의 핵심은 내보내도 될만한 페이지를 어떤 방식으로 선택하는 것인가이다. 생각보다 특이한 케이스들이 존재하고 공부하닥 랜덤이라는 방식이 어쩌면 가장 뛰어날 수 있다는 생각도 하게 됐다. 천천히 살펴보자

 

# 캐시 관리

 페이지를 메모리와 디스크상에서 관리하면서 많이 쓰이는 페이지를 구별해내는 이 과정 또한 캐싱의 한 과정이라고 볼 수 있다. 캐싱의 모든 목적은 캐싱 된 것을 가장 많이 사용하게 해야한다. 그래야지 성능 향상이 있다. 지금의 문제에서는 디스크에서 가져오는 페이지를 최소화 해야한다. 즉 캐시 히트 횟수를 늘리는 것이다.

 이 hit/miss 횟수를 안다면 평균 메모리 접근 시간(average memory access time, AMAT)을 계산 할 수 있다. 그렇게 어려운 수식은 아니다.

hit한 경우는 메모리에서 데이터를 읽어올때의 시간을 곱해주고, 미스한경우의 비율만큼 디스크에서 메모리를 읽어논 시간을 곱해준다. 그리고 이걸 더해주면 평균 메모리 접근 시간이 된다. 당연히 Tm의 시간이 Td의 시간보다 현저히 작을 것이다. 메모리와 디스크는 엄청난 속도차이가 있다.

 

# 최적 교체 정책( optimal )

 먼저 살펴볼 정책은 optimal한 정책 이상적인 정책이다. 현실성은 떨어지지만 이 최적의 상황을 알고 우리가 행하는 교체정책과의 비교를 통해서 얼마나 효율적인 교체정책인지를 비교 할 수 있다.

 이 교체의 핵심은 가장 나중에 쓰이는 페이지를 교체해야 한다느 것이다. 당연히도 가장 나중에 쓰이기 때문에 최근에 쓸 일이 없다는걸 뜻한다.

 첫 3번은 처음 접근하는 것이기 때문에 당연히 캐싱이 되어 있을 일이 없기 때문에 compulsory miss가 나타난다. cold start라고도 불리는데 이러한 miss는 어떠한 정책을 펼치더라도 일어난다. 

 그 다음 미스는 캐시가 꽉 차서 발생한다. 꽉 찬 캐시에는 현재 원하느 값이 들어있지 않기때문이다. 이제 optimal하게( 가장 나중에 사용되는 것을 내보냄) 내보내고, 새로운 것을 캐싱한다.

 이렇게 작업을 끝까지 진행해보고 나서 히트된과 미스 된 비율을 통해서 캐시 히트율을 계산할 수 있다.  히트 / ( 히트 + 미스 ) = 6 / ( 6+ 5)  = 54.5%가 나온다. 첫 3개의 콜드스타트를 제외하면 85.7%의 히트율을 보여준다. 

 이 가장 이상적인 수치를 가지고 다른 정책들을 비교해 보도록 하겠다.

 

# FIFO : is Simple

 First In First Out 가장 먼저 들어온 것은 가장 먼저 나가는 것, 컨베이어 벨트에서 계속 뒤로 밀려나 결국 끝으로가서 떨어지는 것을 생각해보자.

콜드 스타트 이후 FIFO 정책에 따라서 선입 된 것들이 떨어져 나간다. 그뒤에 바로 오더라도 정책에 맞게 빠져나간다. 여기서 히트율을 계산해보면 36.4% 강제 미스를 제외하면 57.1%가 된다.

성능이 좋지 않다는 것을 알 수 있다. 각 블럭들의 중요도를 판단하지 않기 때문이다.

 

# 랜덤 선택 ( 무작위 선택 )

FIFO와 마찬가지로 구현하기 쉬운 성질을 가지고 있다. 대신 운에 의존하는 결과를 낳게 된다. 어떨때는 이상적인 히트비율을 보일수도 있고 어떨때는 최악의 히트비율을 보일 수도 있다.

 

# 여담 : Stack 특성

 이 특성에 관해서는 수업시간 퀴즈에서 나온적이 있었다. 나름 특수한 케이스에서 작용하는 중요한 개념이다.

 어떤 메모리의 참조 흐름이 1,2,3,4,1,2,4,1,2,3,4,5와 같이 루프(loop)형태가 지속된다는 가정하에 생각한다. 일반적은 캐시메모리를 늘리면 성능이 향상해야한다. 돈을 쓰면 좋아져야 하는건 당연한 이치이다. 그러나 FIFO에서는 더 안좋아지는 경향을 보여줬다.

 LRU와 같은 다른 정책들은 이와 같은 문제를 겪지 않는다. LRU는 사실 스택 특성을 가진다. 꼬리에 꼬리를 물었다.

 일반적으로 N+1로 캐시가 증가하면 N의 내용을 자연적으로 포함하게 돼 있다. 그렇기 때문에 캐시의 크기가 증가하면 히트율은 그대로 유지되거나 향상 되어야한다.

 

# 과거 정보를 이용하는 LRU

 무작위나 FIFO는 지금 내보는것이 바로 다음에 참조될 수 있다는 비슷한 문제를 겪는다. 물론 LRU또한 모든 물리적 세계에서는 미래의 결과를 알 수 없지만, 과거의 정보의 기반에서 미래를 예측할 수는 있다. 고기도 먹어본 놈이 먹는다고, 선택 당한놈은 또 선택당할 가능성이 높은 것이다. 이러한 것들을 빈도수(frequency)와 최근성(recency)의 특징을 이용한다. 더 최근에 접근된 페이지일수록 가까운 미래에 접근될 확률이 높다는 표현이다.

결국 앞서 몇번 공부했던 지역성의 원칙(principle of locality)라고 부르는 특성에 기반을 둔다.

 

 즉 아래 그림과 같이 최근에 사용했다면 해당 블락을 다시 맨 뒤(MMU)로 옮기는 것이다. 점점 컨베이어 벨트의 끝부분으로 가다가 한번 선택하면 다시 맨앞으로 오고를 반복하면 지역성(temporal locality)을 띄게 해준다.

 

# 워크로드에 따른 비교

실행하는 코드들에는 어떠한 특성을 띌 것이다. 가장 먼저 무작위로 참조되는 지역성이 없는 워크로드를 살펴보자

 결론은 지역성이 없다면 어느 정책을 사용해도 된다.

 

# 80 : 20 워크로드 : 20%의 페이지들에서 80%의 참조 발생, 80% 페이지들에서 20%의 참조 발생

지역성을 고려한 LRU가 가장 우수한 결과를 보여주고 있고, FIFO와 랜덤은 비슷하다.

 

# 순차 반복 워크로드

50개의 페이지들을 순차적으로 참조한다. 0 , 1 , 2 ... 49 -> 0, 1, 2 ... 49 -> 반복 ..

일단 50개의 페이지에 접근하기 때문에, 캐시 블록의 크기가 50개를 모두 담는 순간이 되면 그 이후부터는 모든 것이 캐싱된다. 이건 어떠한 정책이든 마찬가지이다. 

 LRU와 FIFO에서 가장 안좋은 성능을 보인다. 순차 반복 워크로드는 가장 오래된 페이지들을 내보낸다. 반복적인 특성 탓에 LRU에서도 이러한 특징을 담아내지 못한다. 그러나 무작위(Random)방식은 기대 이상의 방식을 보여주고 있다. 

 

# LRU 정책 근사하기

 굳이 LRU를 100%구현할 필요는 없다. 가장 최근에 사용한 것을 제외하고, 가장 오래된 것을 없애버리는 이 방식은 사실 그 블럭들에 대한 정보를 기록하고, 하나씩 접근하면서 찾아내야한다. 너무나도 고비용이 발생하기 때문에. "적당히" 오래된 놈을 선택하여 내보내 버리자는 것이다. 이런 방식에 use bit( refernece bit)를 활용한다. 하드웨어의 도움을 받는 것이다. 페이지 테이블이 참조되면 use bit를 1로 바꾸고, use bit가 1인 블록은 선택되지 않는다.

 그러나 계속 1이면 안되기 때문에 0으로 바꿔줘야한다. 그래서 시계 알고리즘(clock algorithm)이 등장했다. 시계바늘이 계속 페이지들을 순회한다. 현재 가르키는 페이지의 use bit를 확인한다 0이면 선택되고 1이면 지나간다. 이 지나가는 것에 주목한다. 최초가 아닌 두번째 만남에서 지나가게 되면 use bit를 1에서 0으로 바꾼다. "한바퀴 돌 동안 사용 안했으니까 넌 이제 인기 없는 페이지야"라고 말해주는 것이다.

 시계 기법은 LRU와 비슷한 성능을 보임과 동시에 LRU보다 구현이 간단하고 자원 소모가 덜하다.

 

# 추가된 가정 : 페이지가 갱신 된다면 ? Dirty Page

 modified bit라고도 불리는 dirty bit는 페이지가 수정 됐는지를 기록하는 비트이다. 데이터를 읽기만 하면 별 문제 없지만, 물리메모리상에서 데이터가 수정된다면, 디스크의 수정되기 전 상태인 디스크의 정보와 다를 것이다. 그렇기 때문에 dirty bit가 ture인 페이지에 대해서는 내보내기 위해서는 디스크에 변경 내용을 기록해야하는 일이 추가된다. 이것은 I/O요청이기에 꽤 비싼 자원을 소모한다. 그러나 수정되지 않은 페이지라면 이러한 번거로움을 덜 수 있다. 그렇기 때문에 dirty bit인 페이지가 선택되는 일은 최소화 해야한다. 즉 dirty bit가 1이라면 우선순위 맨뒤로 밀려난다.

 dirty bit가 선택되는 것을 줄이거나 막기 위해서  N'th chance Algorithm이라고 하여, dirty bit에게는 N의 기회를 더 부여하는 방식이 있다. 

 

# 정리하며

 어찌 됐든 이틀안에 중간고사 범위를 모두 정리했다. 교재내용을 주로 다뤘기 때문에 강의시간에 배웠던 조금 세세한 내용은 빠졌지만, 이러한 것들은 시험공부를 추가적으로하며 더욱 자세히 공부하도록 할 것이다. 또 시간이 된다면 그것들도 정리하는 시간을 가지도록 하겠다.

 생각보다 엄청 힘들다. 대충 20시간은 쓴거 같다.. 이틀동안.. 

 그래도 목표를 이뤘다는거에 1차 뿌듯함과, 나름 큰 개념들을 다시한번 보니까 내용 정리도 되고 좋았다.

 열심히 한만큼 시헙에서도 좋은 결과가 있으면 정말 뿌듯할거 같다. 새벽 4시가 넘어가는 이 시점 난 씻고 자야겠다 ~~ 😇

아 그리고 다시보면서 Stack특성이랑 LRU가 궁금하다. LRU stack 특성인건가? 스택 특성이라면 루핑 수행을 할때 좋아야 하는거 아닌가? 스택특성일아 루핑이라는 별개인건가..? 또 시계 알고리즘은 변형된 LRU인데 그럼 스택특성을 지니는건가? 내일 교수님한테 꼭 질문 드려야 겠다.