[Architecture] MMU improvements

 이번 포스트에서는 MMU의 효율을 높일 수 있는 방법에 대해서 다뤄보려고 한다. 지난 시간에 언급한 내용중에 보면

- Page map의 entry 중 일부만 physical memory에 상주한다.

라고 한 내용이 있었다. 왜 하필 일부일까. 이때도 항상 계산때 강조한 p, v, m 값을 살펴보면 된다. 지금까지 살펴본 값들을 살펴봐도 일반적으로 virtual page number에 할당된 bit수가 physical page number에 할당된 bit수보다 많은 것을 알 수 있었다. 아무래도 1대1 mapping이 발생하려면 두개의 bit수가 같아야 하는데, 그게 아니니 일부만 상주할 수 있는 것이다.

 이런 문제를 해결하기 위한 방안이 multi-level page map이다.

위의 그림과 같이 virtual page number 의 형태를 지니고 있다면 이 page를 모두 physical memory에 할당하기 위해서는 총 2^20 만큼의 word가 있었야 한다. 다르게 말하면 2^12 page 만큼의 영역이 존재해야 한다. 이때 page map이 계층적으로 구성되어 있다면 조금더 넓은 영역에 대해서 physical memory에 상주시킬 수 있게 된다. 그래서 이때문에 virtual page number를 두개로 나눠서 각각에 대한 page map을 생성하고 이에 대한 entry를 관리하게 한다. 이중 상위 10 bit이 나타내는 부분을 Page Directory라고 한다. 간단하게 말해 탐색기의 directory를 생각하면 된다. directory안을 살펴보면 파일이 있는 것처럼 page map을 담은 directory 라는 뜻이다. 즉, physical memory의 일부를 page map 저장하는데 쓰는 것이다. 이게 시사하는 점은 크다. 말은 page map 이 계층적으로 되어 있기 때문에 일부로 page map을 두번 access해야 되는것 아니냐고 할수도 있겠지만, 우리가 원하는 것은 실제 구동되는 data가 가져온 physical memory 속 정보에 있느냐의 것이지 정확히 어디에 위치해 있냐는 것이다. 따라서 지난 포스트에서 다룬 개념처럼 모든 context가 resident하지 않더라도 page directory만 읽어서 가져온 data 중에 포함되어 있다. 참고로 page table중 까만색으로 표시되어 있는 부분이 resident하지 않다는 뜻이다. 이말은 page directory에서 resident하지 않은 entry는 그 자체도 유효하지 않는 데이터를 가지고 있으므로 굳이 virtual page segment를 찾기 위해 하위 page table을 참고하지 않아도 된다는 뜻이다. 

 다음 방법은 Rapid Context-Switching이라는 방법이다. 말그대로 CPU내에서 context switching이 발생할 때 이를 어떤 방법을 써서 빠르게 처리한다는 것이다. 어떤 방법일까?

 이전 포스트에서도 쭉 다뤘지만 자주 access되는 page table의 entry에 대해서는 TLB라는 일종의 cache에 저장하고 physical memory에 직접적으로 접근하는 방식을 취한다고 했었다. 여기서 TLB miss 가 발생할 경우 page table에 접근해서 이에 맞는 PPN을 찾는게 그다음 과정일 것이다. 이럴때 page table을 가리키는 일종의 pointer (page table pointer)가 두게 되면 context switching이 발생한다면 page map도 바뀌어야 할텐데, physical하게 page map이 바뀌어지는게 아니라(보통 이런 과정을 invalidate 라고 한다.) 이 pointer를 reload하는 방식으로 다음으로 사용할 page table이나 page directory를 가리키게 된다. 이러면 miss가 발생해도 Pointer만 바꾸면 되므로 그만큼 빠르게 처리할 수 있을 것이다. 여기에 덧붙여서 몇몇 MMU는 Translation 발생시 context number register field를 따로 두어 TLB에서 해당 context number 만 보고 바로 찾을 수 있게끔 해준다. 이렇게 하면 만약 context switching이 발생한 경우라 해도 굳이 모든 TLB contents를 flushing 할 필요 없이 context number와 page table pointer만 reload시켜주면 원하는 정보가 저장된 physical memory에 직접적으로 접근할 수 있게 된다. 추가로 TLB의 공간이 충분해서 VPN->PPN 정보까지 담겨져 있다면 조금더 효율적으로 성능을 향상시킬 수 있을 것이다.

 그럼 이제 MMU와 연결된 cache에 대해서 언급해보자.

우리가 이전까지 봐왔던 TLB의 형태는 위와 같이 virtual address가 담긴 cache였다. virtual address야 CPU에서 처리되는 주소이므로 굳이 MMU를 거칠 필요가 없기 때문에 빠르게 사용할 수 있다. 다만 단점이 있다. 만약 context switching이 발생해서 page table을 바꿔야 한다면 어떡할까? 물론 이전에 소개한 기법도 있겠지만, 그런게 구현되어 있지 않다면 cache에 들어있는 정보들은 모두 쓸모가 없어지고, OS는 cache를 invalidate를 시키게 된다. 즉 context switching 발생시 cache를 반드시 flush시켜줘야 한다는 것이다.

 반면 cache에 physical address를 담는 방식도 생각해볼 수 있다.

이렇게 하면 cache에는 MMU에서 translate된 Physical address가 담기게 된다. 이렇게 되면 context switching이 발생하더라도 physical address의 형태로 담겨있는 만큼 cache를 flush시킬 필요가 없게 된다. 그런데 이전 방식과 반대로 physical address가 담기는 만큼 memory access 때마다 MMU를 거치는 시간이 소요된다. 바로 이런점에서 trade off가 발생하는 것이다. 그리고 보통 그걸 해결할 수 있는 방안이 두개의 절충점을 찾는 것이다.

title에 나와있는 것처럼 physical information과 virtual information을 동시에 사용하는 것이다. 먼저 virtual address의 일부 bit을 활용해서 physical address에 대한 정보를 생성하고 그 다음 나머지를 cache의 index처럼 활용해서 찾는 것이다. 보통 이 cache의 index를 cache line이라고 하기도 하는데, 만약 그 나머지에서 찾았으면 굳이 MMU를 거치지 않더라도 원하는 physical address를 구할 수 있고, miss가 발생했더라도 일부 bit을 이용해서 MMU속 physical information을 얻어올 수 있는 것이다. 이 모든 작업이 parallel하게 수행할 수 있기 때문에 기존 방법에 비해서 속도도 빠르다. 또한 경우에 따라서는 MMU를 거칠 필요도 없기 때문에 time penalty를 줄일 수 있는 방법이 되겠다.

 물론 이렇게 하면 cache line을 offset field에 맞게 설정해야 되기 때문에 무작정 늘릴 수는 없지만, 이런 경우라면 cache size를 크게 늘려서 해결할 수 있다. 이를 통해서 cache associativity도 늘릴수 있다.