[Architecture] Basics of Virtual Memory (2)

  Demand Paging의 전제는 Virtual Page들이 HDD 같은 secondary storage에 있고, MMU가 비어 있는 것에서부터 출발한다. 즉, physical memory에는 Page와 관련한 정보가 없는 것부터 출발하는 것이다. 이 상태에서 CPU가 프로그램을 구동하기 시작하면, CPU내에서 사용되는 virtual address는 실제 해당 프로그램이 올라가 있는 memory의 physical address로 맵핑된다. 만약 해당 address로 접근했을 때, 원하는 내용이 physical memory에 있는 경우는 그냥 그 정보를 CPU가 사용함으로써 처리가 종료된다.

 그런데 만약 그 정보가 없는 경우면 어떻게 될까? 이렇게 virtual address가 가리킨 주소가 physical memory에 없는 경우에는 우선 MMU가 CPU에 해당 page에 대한 주소가 없다는 signal을 보내게 된다. 보통 이런 경우를 page fault 라고 하는데, 이건 일종의 exception이다. exception라고 하면, system이 구동되는데 있어서 심각한 문제가 발생한 경우, 기존의 처리 정보를 어딘가에 저장하고 그 문제를 처리하는 routine을 수행한다. 그 저장하는 동작 자체를 context switching 이라고 하는데, context에 대한 설명은 추후에 하려고 한다. 아무튼 page fault가 발생하면, MMU가 cpu에게 signal을 날리고 일종의 exception handler를 통해 page fault에 대한 처리를 수행하게 한다. 

  이렇게 page fault가 발생하면 exception handler, 구체화시키면 page fault handler는 secondary storage에 있는 정보를 memory에 할당시킨다. 여기까지 수행되면 우선 CPU가 원하는 정보가 memory 상에 올라가 있게 되는데, 지금 MMU의 scheme을 따라가는 만큼 해당 정보도 MMU의 page table내에 새로 정의되어야 한다. 이렇게 정의된 physical page number를 CPU에게 알려줌으로써 이용할 수 있게 된다.

 그런데 한가지 더 예외 상황이 있다. 만약 이렇게 secondary storage로부터 memory로 data를 올리는데 이 memory에 해당 data를 올릴 공간이 없는 경우면 어떻게 될까?

 상식적으로 page fault가 발생해 필요한 data를 disk로부터 올릴 정도면, 이 data는 중요하다는 뜻이고, 다른 것들을 치우고서라도 그 공간을 만들어야 했을 것이다. 그럼 또 하나 가질 수 있는 궁금증이 그 치울 다른 것을 어떻게 선정하냐는 것이다. 가장 효율적인 방법은 가장 덜 쓰는, 아니면 아예 안쓰는 data를 치우고 page fault로 인해 전달받은 page를 넣는게 될 것이다. 물론 아주 똑똑한 시스템이라면 그런 data가 뭔지 바로 알고 치우겠지만, 현재까지는 그정도까지는 아니고 대신 해당 시점까지 보고 가장 덜 access된 data를 먼저 swap out 시키는 알고리즘(Least Recently Used - LRU)을 사용하곤 한다. 여기까지 하면 memory에는 secondary storage의 page를 할당할 수 있는 공간이 생성되고, page table에 있는 virtual page들을 update하게 된다.

 page fault가 발생하고, 이를 처리하는 과정에 대해서 언급했다. 그런데 말이 fault라는 단어가 들어있어서 시스템에 큰 문제가 발생한 건 아닐까 걱정할 수도 있는데(적어도 나는 이런 개념에 익숙하지 않았을때는 그런줄 알았다.) 이런 동작 자체는 physical memory가 모든 page를 가질 수 없기 때문에 발생하는 현상이고, 어떻게 보면 프로그램 동작시 당연히 발생할 수 있는 현상이다. 가령 프로그램의 working set, 즉 program 구동시 필요한 데이터들을 실행하고자 할경우, 이 정보를 secondary memory로부터 physical memory로 할당하기 때문에 page fault가 매우 많이 발생한다. 이러는 와중에 conext switching도 발생하고, 동작이 느린것처럼 보일 수 있다. 하지만 위에서 말한바와 같이 일종의 알고리즘을 통해서 swap out이 되고 나서는 해당 page table이 정상적으로 업데이트된 이후이므로 page fault가 발생하는 빈도도 그만큼 줄어들게 된다. 물론 thrashing이라고 해서 page fault가 지속적으로 나타나는 프로그램의 동작도 있긴 한데, 우선 이 모든 동작이 page fault handling, 혹은 demand paging의 간략한 요약이라고 하겠다.

 Page table의 형태는 간단하게 다음과 같이 그릴 수 있다.

 Virtual memory의 한 block 당 하나의 page를 나타낸다고 가정했을 때 page table의 구성은 위와 같이 R (resident bit), D (dirty bit), PPN (physical page number) 등으로 이뤄진다. Resident bit이란 말 그대로 virtual memory 상의 한 block에 해당하는 내용이 실제 physical memory에도 있는지 여부를 확인하고자 하는 필드이다. 따라서 실제로 있는 경우는 1로 표시되지만 할당되어 있지 않거나 disk에 존재하는 경우라면 0으로 표시될 것이다. 당연히 R=0이면 page fault가 발생한다. PPN은 virtual page에 할당된 memory영역을 가리키는 값이다. Dirty bit은 cache의 그것과 거의 유사한 기능인데, 해당 page가 disk로부터 읽어들어온 것인지의 여부를 확인하기 위한 bit이다. 조금더 다르게 표현하면 실제 memory의 data와 disk의 data에 차이가 있는 경우에 1이 정의되는 것으로 이해하면 좋을 듯 하다.

 이를 토대로 MMU가 어떻게 동작하는지를 확인해보자. 우선 virtual address와 physical address의 구성은 다음과 같다.

 위 그램에서도 보면 Virtual Address나 physical address의 offset은 8bit으로 동일하다. 이 offset은 하나의 page내에서 원하는 데이터가 저장되는 곳을 가리키는 값인데, 이를 통해 하나의 페이지당 256 byte (=2^8)가 들어 있는 것을 알 수 있다. 그리고 Virtual Page Number(VPN)에 할당되어 있는 bit은 4 bit이므로, 이를 통해 나타낼 수 있는 virtual page의 갯수는 총 16개(=2^4)임을 알 수 있다. 동일한 방법으로 Physical Page Number로 나타낼 수 있는 page(physical page)의 갯수도 8개(=2^3)가 되겠다.

 자 그럼 각 page를 표현하는 map은 몇 bit으로 표현 가능할지도 확인할 수 있다. 자 우선 앞에서 소개했던 Dirty bit, Resident bit 등이 각각 1 bit으로 할당되어 있다고 가정한다면, 각 entry가 가지는 bit은 dirty bit (1 bit) + resident bit (1 bit) + Physical Page Number bit (3 bit) = 5bit이 될 것이고, 앞에서 소개했던 것처럼 각 page table 당 표현할 수 있는 virtual page의 갯수는 16개라고 했으므로 총 소모 bit은 5*16=80 bit이 된다. 그래서 이런 도식을 예상할 수 있다.

그럼 위의 table을 토대로  다음 예제를 살펴보자.

 이해가 필요하다면 위의 명령은 일종의 LD instruction인데, R 접두어가 들어간 것을 뺀 0x2C8은 CPU에서 처리되는 주소인 virtual address이므로 이 값을 토대로 physical memory로부터 읽어오려면 physical address로 변환되어야 한다. 그러면 위의 scheme을 그대로 따라가면 하위 8 bit을 제외한 상위 bit, 여기서는 0x2가 virtual page number가 되는데, 이걸 page map에서 참조하면 해당 virtual page에 대한 정보는 physical memory 상의 0x400부터 있는 것을 확인할 수 있다.

 그럼 여기서도 physical address는 offset에 할당된 하위 8bit을 제외한 내용이 physical page number가 될텐데, 여기에 비춰볼때 Physical page number는 0x4인것을 알수 있다. 따라서

(virtual address) 0x2C8 -> 0x4C8 (physical address)

로 변환되었음을 알 수 있다. 위 과정에서 유념할 것은 위와 같이 virtual address에서 physical address로 translation이 일어나도 offset은 변함이 없다는 것이다.