[Architecture] Page faults

 이런 상황을 가정해보자. 현재 상황은 CPU가 Page map상의 virtual page 5번에 접근하려고 하고 있다. 그런데 현재 해당 entry의 resident bit은 0이다. 즉, 이 virtual page가 찾고자 하는 데이터는 physical memory에 없다는 뜻이다. 이런 경우에 이전 포스트에서 소개했던 것처럼 MMU는 CPU에게 exception signal을 보내고, CPU는 context switching이 발생하면서 exception handler를 수행하게 된다. 이 전체 과정을 page fault라고 언급했었다. 

 우선 그때도 소개했지만 page fault가 발생하면 page fault handler는 disk로부터 읽어올 데이터를 저장할 공간을 physical memory로부터 찾는다. 되도록이면 사용하지 않는 빈공간을 찾겠지만, 그렇지 않은 경우라면 LRU같은 알고리즘을 사용해서 해당 page를 swap out시키게 된다. 여기서는 virtual page 1이 선택되었다고 가정해보자.

 만약 해당 virtual page 1의 dirty bit이 set되어 있다면, 이 말은 실제 physical memory상의 data와 disk같은 secondary storage의 data가 다르다는 것을 의미하므로, physical memory의 해당 영역을 정리하면서 그 안에 들어있던 data를 다시 disk에 써준다.(write back). 이렇게 되면 해당 공간은 이미 정보도 disk로 write back 상태이고 정리가 된 상태이기 때문에 아래 dirty bit도 0, resident bit도 0이 될 것이다. 그리고나서 기존의 disk로부터 불러온 데이터를 physical page 3에 저장하면 아래 그림과 같은 도식을 갖추게 된다.

 알고리즘에 대한 이야기가 나와서인데, 실제로 wikipedia를 살펴보면 다양한 page replacement algorithm에 대해서 언급되어 있다. 이전 포스트에서 소개했던 LRU (Least Recently Used)도 있겠지만, 최근에 많이 쓰이는 방법은 Aging 기법이라고 하여 page마다 age를 기록해서 나름의 알고리즘에 따라 replace가 발생하는 방법이라고 한다. 물론 이밖에도 FIFO(First In First Out) 방식이나, File Access에 따른 Frequency에 따라 NFU(Not Frequently Used)같은 기법도 있고, 심지어는 Random 기법도 있다. 

 아무튼 위 그림까지 도달하게 되면 virtual page 5의 resident bit은 1로 set되고, 여기에 따른 Physical Page Number는 4가 써지게 된다.

여기까지 수행되면 page fault에 따를 exception handler의 동작이 끝나고 CPU는 다시 context switching을 통해 이전에 수행하던 작업을 계속 진행하게 된다.

 실제 예를 살펴보면

위와 같은 Page table이 있다고 가정했을때,

이런 instruction을 수행하다고 치자, 참고로 위 instruction의 뜻은 BP(Base Pointer)에 저장되어 있는 값을 SP(Stack Pointer) - 4 가 가리키는 memory에 저장하겠다는 뜻이다.일단 위 instruction은 CPU에서 처리되는 값이므로 해당 virtual address에 대한 physical address를 찾아야 한다. 우선 지난 포스트에서 이야기 했던 것처럼 

 

이런 scheme을 따라간다고 가정하면 하위 8bit을 뺀 상위의 값들이 Page number를 가리키게 된다. 그러면 Virtual address가 0x604 - 0x4 = 0x600을 가리킬 때 이에 대한 Virtual page number는 0x6이 된다.

 그런데 위의 page table을 살펴보게 되면 virtual page 6의 resident bit이 0인 것을 볼 수 있다. 즉 이 instruction이 가리키는 주소는 physical memory에 없고 disk에 있다는 것을 의미한다.결국 page fault가 발생하게 된다. 그러면 CPU는 context switching이 발생하고 replacement algorithm에 따라 replace할 page를 찾게된다. 이렇게 찾은 virtual page가 0xE라고 가정해보자. 그럼 0xE의 page table entry를 살펴보면, dirty bit이 1로 정의되어 있는데, 결국 이 Virtual page가 가리키는 physical memory의 data와 실제 disk의 data가 일치하지 않다는 것을 나타낸다. 그래서 이럴경우 실제 physical memory의 영역(0x500 ~ 0x5FC)이 disk로 write back한다. 이렇게 되고 나면 실제 physical memory의 영역은 정리되고 이에 따라 page table도 다음과 같이 update된다.

그럼 아까 page fault가 발생한 부분인 virtual page 6에 대한 정보를 정리된 physical memory 영역(0x500 ~ 0x5FC)에 넣고 page table도 여기에 맞춰서 update를 해주면 page fault에 대한 handling이 마무리되는 것이다.

아까 말했던 것처럼 page fault가 처리되면 context switching을 통해 이전에 수행되던 instruction이 다시 수행된다. 어떤 사람이라면 지금 virtual page 6이 가리키는 부분은 disk에서 physical memory로 load한 것이기 때문에 당연히 같고, dirty bit도 0으로 되어 있어야 하는 것 아니냐고 의문을 가질 수 있는데, 지금 처리되는 instruction이 ST (store)이기 때문에, 안에 저장되어 있는 데이터가 바뀐다. 이때문에 dirty bit이 1로 정의된다.

 간단한 pseudo code로 이런 변환 과정을 살펴보면 Virtual Address를 physical address로 변환하는 코드는 다음과 같이 볼 수 있다.

여기서 R Array는 Page table이 가지고 있는 Resident bit array인데, 만약 찾고자 하는 Virtual page number의 resident bit이 0이라면 page fault가 발생해야 할 것이다. 물론 page fault가 처리되고 난 이후에는 virtual page number에 맞는 Physical page number의 값과 Page offset을 합친 값이 physical address으로 생성될 것이고, 이게 전체적인 코드 동작이다. 

 그러면 page fault는 어떻게 구성되어 있을까?

Page fault는 위와 같이 처리된다. 우선 특정 알고리즘(여기서는 LRU를 썼다고 명시되어 있다.)를 통해서 replace 시킬 virtual page 영역을 찾는다. 그리고 나서 해당 page의 dirty bit을 살펴봤을 때, 1일 경우면 해당 virtual page가 가리키는 physical memory 영역을 disk에 저장한다. 이렇게 한후 해당 page의 resident bit은 0으로 초기화됨으로써 할당된 정보가 없다는 것을 알려준다.

여기까지 오면 이제 이전 virtual page가 가리키는 영역을 이 새롭게 생긴 physical memory로 load시킨후 이에 대한 physical page number로 update시킨다. 당연히 이제 data가 할당된 상태이므로 resident bit은 1로 정의되고, 앞에서 언급했던 바와 같이 disk와 memory 간 data의 차이가 없으므로 dirty bit은 0이 된다. (앞의 case는 ST instruction으로 인해 memory의 정보가 수정되는 상황이기 때문에 dirty bit이 1로 set되는 상태였다.)

 대충 코드와 함께 page fault의 처리 과정에 대해서 살펴봤다.

이걸 조금더 발전시켜서 생각해보면 여기까지 나아갈 수 있다.

사실 virtual address를 physical address로 변환하는 과정은 MMU, 즉 CPU가 가진 일종의 hardware에서 이뤄지는 작업이다. 그래서 내부 code도 보면 알겠지만, 논리 연산자도 들어가 있는 형태이다. 반면 page fault를 처리하는 부분은 단순히 array에 들어있는 값들을 비교해서 디스크에 적거나 page를 update하는 등의 software로 처리가 가능한 수준이다. 이처럼 Hardware와 Software의 처리 영역을 분산시켜서 performance를 optimize시킬 수 있다. 가령 page fault 같이 발생했을 때 성능에 큰 영향을 미치는 부분 같은 경우는 Hardware로 처리하고 이에 대한 handling은 hardware보다 조금 cost도 저렴하고 성능이 조금 낮은 software로 처리하는 게 이상적이다.