[펌] 버추얼 메모리(Virtual Memory:가상 메모리)

버추얼 메모리는 일련의 프로세스들이 물리적인 메모리에 할당되지 않아도 실행이 가능하도록 만들어주는 테크닉이며, 가장 큰 장점으로써 물리적 메모리보다 프로그램이 요구하는 메모리가 클지라도 실행이 가능해진다는 점이겠죠. 여기까지는 여러분들이 상식선에서 익히 아시는 부분이라 생각됩니다. 그러나 곧 펼쳐질 버추얼 메모리의 해부도를 아는 이들은 그리 많지 않습니다.

버추얼 메모리의 의의는 -이거 멋진 말입니다. 맘속에 담아놓고 뽐낼때 씁시다- 메인메모리를 극도로 거대한 동일 어레이(uniform array) 저장매체로 추상화 시킨다는 사실로써 유저의관점에 있어서 물리적 메모리와 논리적 메모리를 완벽하게 분리시켜 버렸다는데에 있죠. 허나, 모든건 장단점이 공존하기 마련이듯, 벼쳐메모리의 오에스 차원에서 구현하기가 먼저 까다롭고 또한 잘못 사용되었을때 성능의 감소는 정말 끔찍하기조차 하죠.

지지난 장에서는 한정된 메모리상에 쏟아지는 프로세스들을 할당하기 위한 기법들로 오버레이(overlay) 또는 다이내믹 로딩(dynamic loading)등이 언급되었었죠. 이들과 버추얼 메모리와는 근본적인 차이점이 존재하게 되는데 후자들이 막말로 자수성가 해야하는 밑바닥 인생들이라면, 버추얼 메모리는 오에스라는 엄청난 빽의 지원으로 시작부터 부귀영화를 누리는 귀족이라고 할까요,,,

on systems which support virtual memory, overlays have virtually disappeared."
아아,,, 기술서가 아닌 문학서를 읽고있다는 착각조차 드는 멋들어진 표현이었습니다.

버추얼 메모리를 논하기 위해서는 제일먼저 디멘드 페이징(demand paging)이라는 말부터

살펴볼 필요가 있겠어요. 디멘드 페이징은 버추얼 메모리를 구현하기 위한 가장 일반적인 테크닉이죠. 먼저 디멘드 페이징은 전장에서 언급했던 페이징 기법에 전전 장에서 언급했던 스와핑 기법을 적당히 섞은 기법입니다. 여기서 우리는 "혹시 그렇다면 페이징 기법의 쌍벽인 세그멘테이션 기법과 스와핑을 짱뽕시켜도 뭔가 그럴듯하지 않을까!"라고 상상하시는 분이 간혹 계실수 있는데, 정말 예리하시군요,,,맞습니다. 그것또한 버추얼 메모리를 구현하기위한 또하나의 테크닉으로써 존재하고 있으며, 그것을 디멘드 세그멘테이션이라고 일컫습니다. 쏟아지는 무관심속에서 장렬하게 쓰러져간 오에스인 OS2가 바로 이렇게 진보적인 메모리 기법을 채용하고 있었죠.

여하튼, 세그멘테이션은 페이징과 달리 그 단위 크기가 불규칙하기에 그 원리가 여러모로 복잡한 관계로 여기서는 디멘드 페이징에 대한 설명만을 하겠습니다. 디멘드 페이징 기법의 원리는 간단합니다. 먼저 우리가 어떤 프로세스를 실행하고자 한다면 간단하게 해당 페이지를 메모리에 스와프 인 시킵니다. 하지만, 여기서 우리는 전체 프로세스에 대응되는 페이지들을 스와프 인 시키는것이 아니라 게으른 스와퍼(lazy swapper)라 불리우는 녀석이 스와핑을 시키는데 해당 페이지가 요구되어지지(demanded) 않을때까지는 절대로 메모리에 스와프 인 시키지 않는 독한 놈입니다. 자, 여기서 우리는 상당히 절묘한 기술용어를 또하나 접하게 되는데 바로 페이지 폴트(page-fault)라는 것이죠. 이경우는 우리의 프로세스군이 엄니의 밥먹으라는 소리에 식탁에 도착했지만 막상 떠먹으려니 주둥이를 방에 두고 왔다는 사실을 깨닫는 순간인것과도 같죠. 전장에서 말씀드렸듯이 페이징 기법은 프로세스의 크기와 상관없이 한개의 프로세스 조차 여러개의 페이지들로 조각조각 나누어버리는 기법인지라, 디멘드 페이징의 경우 프로세스 일부는 오에스로 페이지 폴트 트랩이 보내지기 전까지는 절대로 메모리에 할당되지를 않습니다.

페이지 폴트가 발생한 상황에 대한 대처는 비교적 심플합니다. 제일먼저 페이지 폴트가 발생하면 프로세스로 부터 해당 메모리로의 레퍼런쓰가 옳았는지부터 확인을 하게 되고, 만일 잘못된 레퍼런쓰였다면 프로세스를 종료시켜주게 되죠. 바로 폭탄맞는 경우입니다. 이경우는 프로세스 자체의 오류이기 때문에 오에스도 어쩔수가 없겠죠. 하지만, 만일 제대로된 레퍼런스였고, 해당 페이지가 메모리에 할당이 되지 않은 상태였다면은 빈 프레임(페이지와 프레임은 각각 논리적 메모리와 물리적 메모리의 단위를 일컫죠)을 재빨리찾아내어 해당 페이지를 프레임에 할당하게 되고, 비로서 아까 중간에 멈추었던 인스트럭션을 재실행! 하게 되는것이죠. 위와같은 식으로 메모리에 단 한개의 페이지를 할당하지 않고서도 결국 프로세스를 실행할수 있게 만드는 무서운 기법이 가능해질수도 있을진데, 바로 순수 디멘드 페이징(pure demand paging) 기법입니다.

위에서 비교적 심플한 방법으로 대처한다고는 막상 말했지만, 이것을 현실적으로 구현한다는 측면에서는 아주 골치아픈 첨병이 숨어있어요. 페이지 폴트의 발생시 프로세스는을 재실행 한다고 했는데, 재실행 한다는 뜻은, 바로 이전까지의 자신의 위치, 레지스터 정보등의 상태를 저장해야 한다는 사실을 암시하게 되지요. 또한 여러게의 프로세스들이 연속적으로 페이지 폴트를 쎄려버리면 씨피유,,,정말 뚜껑 열리게 되겠죠. 허나 다행히도 메모리에서는 신비한 현상이 한가지 일어나는데 바로 레퍼런스의 지역성(locality of reference)로써 후반부에서 다시 다루도록 하겠습니다. 결론적으로 그 지역성 덕분에 매번 한순간 다발적으로 페이지 폴트가 일어나는 일은 극히 드물게 됨으로 나름대로 효율성을 기할수가 있게 되었죠.

자, 디멘드 페이징 특유의 상황이 또한가지 연출되는데 바로 페이지 바꿔치기(page replacement)입니다. 이경우는 페이지 폴트가 발생해서 해당 페이지를 막상 할당하려고 보니 빈 프레임이 하나도 없드라,,,고로 현재 할당되어있는 녀석들중 하나와 바꿔치기 해서라도 올려주는 것이죠. 이때 과연 그렇다면 어떤 녀석을 다시 디스크로 끌어내리는 희생양으로 삼을지가 또한 여러개의 알고리즘들로 존재하고 있고, 이들 알고리즘들과는 별도로 페이지 바꿔치기를 함에있어서 참으로 드러진 기법이 등장하게 되는데 바로 더티 비트(dirty bit)의 활용입니다. 자, 한번 생각해 보셔요. 페이지 바꿔치기가 일어나려면 2번의 I/O가 필요하겠죠? 먼저 현재 프레임에 할당된 페이지중 한개의 희생양을 디스크로 끌어내릴때 한번, 그리고 디스크에서 요구된 페이지를 프레임으로 올릴때 한번,,,이렇게 총 두번입니다. 이러한 I/O는 순전히 오버헤드로 작용하여 시스템의 성능을 감소시키게 되겠죠. 하지만, 더티 비트라는 비트를 한개의 프레임마다 달아놓고 만일 해당 프레임의 내용이 바뀌었을경우 1로, 그렇지 않을경우 0으로 세팅한다고 약속을 하게되면,,,한번의 I/O로도 바꿔치기가 가능해집니다. 왜냐하면 더티 비트가 0인 녀석의 경우 디스크로 다시 내려올 이유가 전히어~ 없어지기 때문입니다. 뭣하러 내려오남,,,백업본이 고스란이 이미 디스크에 있는디,,,

페이지 바꿔치기를 위하여 희생양 프레임을 고르는데 사용할수 있는 대표적인 알고리즘들을 이제는 살펴봅시다.

1. FIFO 알고리즘 : 곰곰히 생각하면 FIFO라는 말은 이제 우리에게 익숙해졌을 정도로 도처에 등장하는 감초알고리즘같습니다. 말그대로 이 알고리즘은 프레임에 올라온지 가장 오래된 페이지를 내려버리죠. 이 알고리즘을 구현하기 위해서는 반드시 각 페이지가 올라온 시간을 나름데로 트래킹하고 있어야 할듯 하지만, 그 방법보다는 FIFO큐(Queue)를 구성해서 순서만을 트래킹하는 방법을 사용하게 됩니다. FIFO알고리즘의 성능은 언제나 좋지만은 않지요. 더구나 아주 요상한 현상이 본 알고리즘에서는 발생할수 있는데, 바로 벨로디의 요상함(Belody's anomaly)라는 현상으로써 프레임의 수를 늘렸음에도 오히려 페이지 폴트수가 증가할수도 있는 현상을 나타내주기도 해요. 즉, 램을 올렸는데 이게 어떻게된건지 오히려 가끔씩 디스크가 더욱 버벅거리게 되는격이죠. 본 현상은, 프레임수가 늘어나면 페이지 폴트가 줄어들것이라는 상식적인 실험을 하는 와중에 언제나 그렇지가 않다는 사실을 연구하다 졸지에 발견한겁니다. 상식적인 가정을 의심하는 가운데 빛나는 논문이 여러분을 기다리죠,,,-_-+

2. 최적(Optimal) 알고리즘 : 이것은 앞으로 장시간 동안 사용되지 않을 페이지를 프레임에서 내려버린다는 알고리즘입니다. 말그대로 최적이죠. 하지만 가장큰 단점은 구현이 불가능하다는 것입니다. 미래에 어떤 페이지가 어떻게 안쓰일지를 무슨수로 결정하겄습니까,,,결론적으로 특정 알고리즘의 성능을 측정함에 있어서 이론적 비교의 대상으로 주로 사용됩니다.

3. LRU(Least Recently Used) 알고리즘 : 꽁머리대신 닭대가리라고, 최적알고리즘은 미래의 현상에 대한 판단이 필요하다면, 요 알고리즘은 과거의 행적에 대한 판단을 기준으로 페이지 바꿔치기를 하게 되요. 즉, 가장 오랫동안 침묵을 지키던 페이지를 내려버리죠. 구현을 위해서는 카운터 또는 스택을 이용해서 얼마나 오랫동안 개겼는지를 트래킹하게 됩니다. 최적 알고리즘과 LRU알고리즘에는 벨로디의 요상함 현상이 일어나지 않죠. 허나, 최적은 구현이 불가능하고, LRU는 특유의 오버헤드가 많은데다가 하드웨어의 특별한 지원까지 필요로 하게되는 단점을 가지고 있습니다.

4. LRU Approximation 알고리즘 : LRU가 그래도 좋긴 좋은가 봅니다. 이것의 구현이 까다로우니 흉내라도 내겠다는 알고리즘이죠. 흉내를 내는 여러자기의 알고리즘들이 있습니다만, 그중에 하나 주목할 만한 것이 있는데, 바로 Enhanced Second-Chance 알고리즘입니다. Second-Chance 알고리즘은 기본적으로 FIFO알고리즘의 골격에 큐의 꼬리와 머리를 연결하여 원형 순환을 시킨뒤 각각의 큐옆에 레퍼런스 비트(reference bit)를 달아주는 형태를 하고 있어요. 레퍼런스 비트가 0일경우는 바꿔치기를 하고, 만일 1일경우는 0으로 리셋되는 대신에 다음 프레임으로 넘어가게 되는것이죠. 만일 0으로 리셋된 프레임이 히트되었을경우는 0을 다시 1로 전환시켜주겠죠? 본 알고리즘의 핵심은 말그대로 두번째 기회를 주게 된다는 것이며, 이렇게 한번 넘어가게 된다면 포인터가 전체 큐를 한번 싸그리 돌기전까지는 안전하게 프레임에 남아있게되죠. 본 알고리즘이 최악의 경우 어떤 현상을 나타낼듯한가요? 바로 2번 뺑이치는 FIFO그 이상 이하도 아니겠죠.

그렇다면 Enhanced Second-Chance이란? Ehhanced는 위에 간략하게 설명한 알고리즘에 또하나의 비트를 추가해주게 됩니다. 바로 더티비트! 이죠. 더티비트와 레퍼런스 비트의 조합에는 다음과 같은 경우의 수가 나오게 됩니다.

(레퍼런스비트, 더티비트)
(0,0):최근에 사용되지도 않았을뿐더러 변하지도 않났다네,,,

       :이거, 당장 방빼야하는 페이지입니다.
(0,1):최근에 사용되지는 않았지만, 내용이 조금 변하긴 했지,,,

       :썩 빼기 좋은 경우는 아닙니다만(2번의 I/O가 필요하죠) 최악의 경우 이녀석도 방빼게

        됩니다.
(1,0):최근에 사용되었지만, 내용은 그대로라네,,,:아마도 곧 다시 사용되겄죠,,,

        빼기가 참 그렇군요,,,
(1,1):최근에 사용되었을뿐더러 내용까지 변했다네,,,:곧 다시 사용될듯하며,

        내리기 전에는 반드시 디스크에 기록을 해야할겁니다.

참고로 우리의 호프 매틴토시의 버추얼 메모리 매니져가 위의 알고리즘을 사용하고 있습니다.

그밖엔 카운팅 알고리즘, 페이지 버퍼링 알고리즘등이 책에 소개가 되지만, 핵심은 위에서 소개가 다 된듯하군요. 이것으로 페이지 바꿔치기에 대한 고찰이 끝난것이 아닙니다. 페이지 바꿔치기를 함에있어서 또하나의 기준으로 글로벌(global) 이냐, 아니면 로컬(local)이냐하는 논의가 있죠. 전장에서 페이징을 하기 위해서는 한개의 프로세스조차 조각낸다는 말을 한적이 있죠? 즉 한개의 프로세스가 10조각으로 나위었을때 5조각을 올린다음 페이지 폴트가 발생했다고 가정해봅시다. 만일 이때 5조각중 한조각을 내린뒤 필요한 한조각을 올리게 될경우(이럴경우 해당 프로세스의 조각은 5개로 불변이죠)가 바로 로컬 바꿔치기 알고리즘이고, 다른 프로세스의 페이지를 내린뒤 한개를 올려서 총 6개의 조각을 만들어주는것이 글로벌 바꿔치기 알고리즘이죠. 결과적으로 글로벌 페이지 바꿔치기는 시스템 전체적인 프로세스 처리량을 향상시켜주기는 하지만, 프로세스가 자기 자신에 대한 페이지 폴트율을 도무지 제어하기가 어려워 진다는 단점이 있습니다만 현재 대부분의 버추얼 메모리가 글로벌 바꿔치기 알고리즘을 사용합니다.

가끔씩, 버추얼 메모리를 사용할때,,,자신의 하드가 갑자기 미쳐서 쉴새없이 드르르르륵~~~거리며 사람을 화들짝 놀라게 만드는 경우를 혹시 경험해 보셨나요? 그 현상에 대한 정확한 설명을 여기서 드립니다. 바로 트래슁(thrashing)이라 하는 현상이거든요.

오에스는 언제나 자신의 시스템에 대한 효율을 기하기 위하여 씨피유사용량(CPU Utilization)을 점검하곤 하지요. 만일 씨피유사용량이 낮아졌다는 판단이 들경우에는 멀티프로그래밍의 수준을 높여줌으로써 언제나 적정한 사용량을 유지하도록 분위기를 조성해줍니다. 그런데, 버추얼 메모리가 인스톨된 시스템에서 어느 프로세스가 실행됨에 있어서 새로운! 페이즈(phase:여기서는 늘 하던 일이 아닌 뭔가 새로운 일을 하려는 경우로 이해하시길)로 전환되게 될경우 프레임에 해당 페이지가 할당되어 있지 않다면 당연히 페이지 폴트가 발생하기 시작하겠죠. 이때 페이지 발생하는 폴트의 결과로 다른 프로세스의 프레임을 점유하게 되면, 다른 프로세스 또한 페이지 폴트율이 증가하게 되고 이런식으로 서로의 페이지 폴트율이 증가하기 시작합니다. 전체적인 페이지 폴트율이 증가하면서 페이징 디바이스의 큐또한 기하급수적으로 쌓여가고 반면에 레디큐는 텅텅,,,비어가죠. 레디큐가 비어간다는 것은 현재 실행중인 프로세스가 줄어든다는 곳이고 이는 과연 무엇을 뜻하게될까요,,,바로 씨피유사용량이 낮아졌다는 뜻입니다. 고로 씨피유는 이러한 상황에서 눈치없이 멀티프로그래밍레벨을 올려버릴테고,,,그 결과는 ? 정말 참담합니다,,,더더욱 낮아지는 레디큐와 자꾸만 올라가는 멀티프로그래밍 레벨,,,고로 결국은 작은 눈한덩이가 눈사태를 일으키듯이 모든 프로세스는 서로 페이징하느라 아무일도 못하게 되죠. 이러한 현상이 바로 트래슁이랍니다. 트래슁을 미연에 방지하는 궁극의 테크닉은 바로 로컬 페이지 바꿔치기 알고리즘이지만, 각 프로세스에게 과연 얼마만큼의 프레임을 지정해줄것인가에 대한 문제또한 만만한것이 아니죠. 물론 시스템의 프로세스 처리량의 감소도 감수해야 합니다.

트래슁을 방지하기 위하여 프로세스당 적정한 프레임수를 결정할수 있는 방법에는 워킹셋전략(working-set strategy)이라는 것이 있지요. 본 기법의 핵심은 프로세스 실행에 있어서 로컬리티 모델(locality model)에 대한 정의인데, 여기서는 이 로컬리티 모델만을 간략하게 다루겠습니다. 로컬리티 모델이란 은 메모리상에서의 정보의 변화를 표시해주는 지도에서 확인이 되는 현상으로 x축을 시간, y축을 메모리 어드레스로 설정하고 플로팅을 했을때 2차원 평면상에 주기적인 패턴이 나타나게 되는 것입니다. 만일 이 평면이 무작위적인 정보가 왔다갔다한다면 전체적으로 흑과 백으로 회색을 디더링한것과 같은 결과가 나오겠지만, 부분 부분 만이 패턴을 그리며 연결된 무늬가 형성된다는 점에서 분명히 메모리 주소값들의 사용은 어떤 패턴을 가지고 있다는 사실을 암시해주죠. 이 사실이 뭐가 그리 중요하냐구요? 바로 이것이 캐쉬메모리가 존재하도록 만든 배경이론입니다. 매번 다른 인스트럭션과 다른 데이터들이 메모리와 씨피유 사이를 관통한다면 캐쉬메모리는 그 존재의미가 전혀 없어져 버리죠.

이상으로 버추얼 메모리에 대한 이론적인 배경을 살펴보았습니다. 메모리에 대한 논의를 완전히 끝내기 전에 한가지 지난번 다루지 못한 부분이 있기에 잠시 언급을 할까 해요. 바로 리엔트랑코드(reentrant code)입니다. 리엔트랑코드는 앞장의 페이징과 세그멘테이션 기법을 논의하면서 특정 페이지와 세그멘트를 공유할때 등장하는 말이죠. 세그멘테이션 에서 에디터의 예를 들면서 에디터 세그먼트와 데이터 세그먼트로 나눌경우 두사람이 각자의 데이터 세그먼트를 메모리에 할당하되, 에디터 세그먼트는 메모리에서 공유가 가능해진다고 했었죠. 이때 에디터 세그먼트가 공유되기 위해서는 바로 리엔트랑코드로 만들어져야 합니다. 리엔트랑 코드는 간단하게 말한다면 자신을 변화시키지 않는(non-self-modifying) 코드입니다. 즉 실행되는 동안은 자신을 절대로 변화시키지 않죠. 이것은 아주 교묘하게도 예전에 말씀드렸던 데이터의 싱크(Sync:Syncronization)문제와도 연관이 되어있는 있는문제로, 최근에 오에스가 고차원적으로 발전하며 자주 등장하는 말입니다. 리엔트랑코드,,,그냥 우리와 아무 상관없는 이야기로 들리겠지만, 여러분 애플의 카본(Carbon)의 정체가 무엇인줄 아십니까? 바로 애플의 툴박스 루틴들중 리엔트랑코드만을 골라내거나 또는 리엔트랑코드로 재작성된 코드들의 묶음입니다.


-duffer 경준 (http://vorlon.cwru.edu/~kxm73)