[OS] Virtual Memory I (Intro)

Virtual Memory

 간단하게 정의를 해보자면, 각 Process에게 전용의 큰 메모리를 제공하는 기법이다. 실제로는 없는 메모리를 있게 보이게 하는 기법이라고 생각하면 편하다. 이전의 Paging과 Segmentation은 다음과 같은 특성을 지니고 있었다. 먼저 Process들을 조각내는 것이다. 조각냄으로서 메모리에 연속적으로 할당될 필요가 없이 단순하게 분산적재를 하기만 하면 된다. 이어지는 얘기로는 분산적재를 한 Process의 조각이 Memory공간 어디에 위치하고 있는지 알 수 있는 Mapping Table이 필요하다. 조각에 대한 정보가 있어야 어디에서 정확한 Memory의 주소를 알 수 있기 때문이다. Mapping Table의 특징은 Relocatable할 수 있어야 한다는 것이다. Address Translation이 Dynamic하게 일어나기 때문이다. 

 

 지금까지 다뤘던 방법은 Process가 전부 다 메모리에 올라갈 수 있다고 가정을 한 상태였다. 그러나 이제는 Virtual Memory로 인해서 모든 Process를 전부 다 올릴 필요가 없게 되었다. 예를 들어서 자주 수행되지 않는 에러코드에 대한 처리같은 경우는 Locality를 반영하면 Memory에 올라갈 필요가 크게 없다. 따라서 부분 적재(Partially-Loaded)가 필요하다. 이를 다시 정리해서 말하자면, 부분 적재가 가능한 이유는 결국 Locality가 반영이 되기 때문이다. 책에는 Kruth의 논문을 인용한 부분이 나온다. 이를 Kruth's Estimate라고 하는데, 10%의 코드가 90%의 time을 소비하는 경향이 있다고 분석한 글이다. 다시 말해서 핵심적으로만 동작하는 코드들이 존재한다 라는 말이다. 따라서 이런 아이디어들이 부분 적재의 개념과 너무 잘 맞아 떨어지는 것이다. 

Fetch Policy

 Fetch Policy는 어느 시점에 메모리에 올릴 것인지에 대한 정책이다. 당연하게도 부분 적재를 위해 등장했다. Fetch Policy에는 크게 두 가지의 방법이 있다. 먼저 Demand Paging이다. Page가 요청될 때 메모리에 적재하는 기법이다. 처음에는 Memory에 올라가지 않고, 시작 될 때 Page를 적재하고, 또 다른 Page가 요구되면 또 넣게 되는 방식이다. 이 방식은 초기에 Page Fault가 많이 발생하지만, 추후에 대부분의 Page들이 Kruth's Estimate의 로직을 따라 Optimize된다. 대부분의 OS가 이 방식을 채택하고 있다. 다른 방식 중 하나는 Prepaging이라는 기법이다. 말 그대로 Page를 선반입 하는 전략이다. 미리 Page를 메모리에 올려놓아 다음 페이지까지 읽어오는 방식이다. 이 방식 역시 Locality에 따른 것이다. 예전에 언급했던 Spatial Locality를 생각하면 이 방식이 효율적으로 보일 수도 있다. 그러나 문제는 이 방식의 Miss Cost가 너무 크다는 것이다. Page Fault, 즉 Miss가 일어나게 된다면, Miss가 일어난 Page는 계속해서 내려가고 새로운 페이지가 Memory에 올라오고 이러한 악순환에 빠질 수 있게 된다. 따라서 이 방식을 많이 사용하지는 않는다. 

Replacement Policy(교체 전략)

 이전 Paging 기법에 대해서 다룰 때 Placement Policy에 대해 다뤘던 적이 있다. Replacement Policy는 이와 정반대의 개념으로서 부분 적재가 되어 있는 메모리 중 어떤 Page Frame을 골라 Swap Out시킬 것인가에 대한 전략이다. 그렇기 때문에 교체를 당하는 Page는 안쓰이고, 안쓰일만한 Page여야 한다. Least Likely Referenced되는 Page를 찾기 위해서는 히스토리를 참고해서 어떤 페이지가 얼마나 Reference되었는지, 그리고 가까운 미래에 해당 페이지를 Reference할 계획이 있는지를 파악해야 한다. 따라서 대부분의 Policy들이 과거의 행동을 바탕으로 미래에 대한 예측을 하는 것은 필수적이다. Replacement Policy의 평가 척도 중 가장 중요하게 여겨지는 것은 Page Fault의 수 이다. 물론 Execution Time, Overhead등 여러가지 평가 척도들이 존재하지만, 교체 전략에서 중요하게 여겨지는 것은 Page Fault의 수 이며, Page Fault의 수가 적어질 수록 좋은 알고리즘이라고 평가를 받는다. 교체 전략에 대한 본격적인 설명은 다음 포스트에서 이루어지겠지만, 참고해야 할 부분이 2가지 정도가 있다. 첫 번째는 Reference String이다. 이는 Page 번호의 Sequence, 즉 input으로 들어오는 친구들이다. 다음으로는 Initial Page Fault인데, Demand Paging을 가정하고 있기 때문에 Initial Page Fault는 어쩔 수 없이 앉고 가야 할 부분이다. 따라서 Initial Page Fault는 세기 않을 예정이다. Replacement Algorithm에는 Optimal, FIFO, LRU, Clock, Enhanced Second Chance 등의 알고리즘 등이 있는데, 이에 대해서는 다음 포스팅에서 다루어보겠다.