전자전기공학/운영체제

[Operating System/운영체제][TLB, Multilevel page table]

Sim 2024. 11. 3. 19:44
반응형

 

 

 

 

 

 

 

지난 시간에 paging의 단점에는 두 가지가 있다고 배우고 간단한게 첫 번째 문제를 해결하기 위한 방법으로

TLB에 대해서 간략하게 소개하고 난 이후에 글을 끝냈습니다.

 

지난 내용을 잠시 떠올리자면, 첫 번째로 paging기법에서 main memory로 정보를 가져가기 위한 cost가 많이 든다는 것이고,

두 번째로 page table이 너무 큰 용량을 차지하기 때문에 문제가 발생할 수 있다는 단점이 존재했습니다.

 

 

이제 해당 단점을 개선하기 위한 방법들을 이야기 할 건데, 지난 시간에 TLB에 대해서 간략하게만 이야기 했기 때문에

자세하게 살펴보고 난 이후에 두 번째 문제점의 개선 방법을 알아보고 글을 마치도록 하겠습니다.

 

 

 

 

 

 

 

 

TLB(Table Lookaside Buffer)

 

 

 

 

 

 

 

 

 

TLB는 page table의 일부 내용을 cache한 것 입니다. cache란 자주 사용하는 데이터 등을 미리 임시 복사해놓은 것 입니다.

왜 TLB를 이용해서 page table의 내용을 cache해 놓은 것일까요?

 

지난 시간에도 이야기 했지만 page table에 access하기 위해서 많은 cost가 발생한다는 단점이 존재한다는 것 입니다.

 

cost가 많이 발생한다는 것은 지난 번에 이야기한 memory 계층구조에서 main memory까지 접근하기 위해서

많은 clock이 소요되기 때문이라는 것을 짚고 넘어갔었습니다. 

 

 

결국 main memory까지 access하기 위한 cost를 없애기 위해서 page table의 일부 내용을 임시 저장하기 위해서

TLB(table lookaside buffer)를 사용해서 cost를 줄이고 빠르게 원하는 정보를 가져오기 위함입니다.

 

 

TLB는 기본적으로 Fully associative cache구조를 이용해서 hit ratio가 99%임을 가정하고 사용합니다.

만약에 TLB miss가 발생하게 된다면 어떻게 될까요?

 

TLB miss가 발생하게 된다면 Page table에 가서 해당 주소가 존재하는지 확인하게 됩니다.

Page table에서 확인하는 이유는 page table이 로딩된 주소에 대한 정보를 가지고 있기 때문입니다.

 

여기서도 만약에 찾는 주소가 없다고 하면 page fault가 발생하고 Disk에 가서 정보를 가져오게 되는 것 입니다.

 

 

그렇다면 page fault가 발생하게 되면 어떤 일이 발생할까요?

 

예를 들어서 STUR instruction을 가지고 memory에 write해야 하는 상황이라면,

page fault가 일어났기 때문에 해당 주소의 정보를 가져오기 위해서 Disk에 가서 확인을 해야 합니다.

그럼 그 동안 process는 blocked 처리가 되어 I/O를 실행해서 Disk에 가서 일을 처리하게 됩니다.

여기서 많은 overhead가 발생하게 됩니다.

 

 

 

여기서 더 자세히 들어가 보자면, page fault가 발생했을 때 TLB를 관리하는 주체에는 hardwareOS가 있습니다.

 

hardware를 주체로 하는 방법은 위에서 봤던 TLB miss가 발생했을 때 page table에 가서 확인을하고

page table에도 해당 주소가 없어서 page fault로 Disk까지 가서 정보를 main memory에 올려주고나서

다시 TLB까지 정보를 update해주는 과정을 전부 hardware에서 처리하는 것 입니다.

 

여기서 hardware의 입장에서 page table이 어디에 있는지 모를텐데 어떻게 위치를 알고 update를 해줄지에 대한 의문이 드는데,

해당 위치를 저장해둔 Page table Pointer를 사용해서 그 위치를 알 수 있는 것 입니다.

 

여기서도 당연히 단점은 존재하는데, hardware가 page table을 access하기 때문에 page table entry가 CPU에

규정되어 있는 방식을 OS 개발자가 따라야 한다는 것과 위의 방법을 hardware로 처리해야 하기 때문에

hardware의 구성이 복잡해질 수 있다는 단점을 가지고 있습니다.

 

 

software(OS)로 TLB를 관리해주는 방법은 OS로 점프해서 PTE를 받아서 TLB에 로딩하는 과정을 수행합니다.

또한 OS로 처리하기 위해서는 CPU의 ISA중에 TLB를 다뤄주는 명령어를 구현해 놔야 OS가 사용할 수 있습니다.

software(OS)로 TLB를 관리해주는 방법의 장점으로는 20-200cycle의 빠른 속도로 일을 처리할 수 있다는 장점이 있습니다.

 

 

software(OS)로 관리해줄 때 해줘야 하는 역할은 또 무엇이 있을까요?

 

 

software(OS)가 PTE를 수정할 때, TLB에 이미 캐시되어 있는 entry와 일관성을 유지해줘야 합니다.

 

위의 내용이 도대체 무슨 내용인지 한번에 안들어올 수도 있는데, 아래의 상황을 생각해보면 쉽습니다.

 

PTE에는 protection bit이 포함되어 있어서 해당 페이지에 대해 읽기, 쓰기, 실행 권한을 설정합니다.

만약 OS가 특정 이유로 PTE의 보호 비트를 변경하게 되면 TLB에 해당 엔트리가 캐시 되어 있을 수도 있어서

TLB에 반영해주지 않고 계속해서 TLB의 정보를 사용하게 되면 문제가 발생할 수도 있는 것 입니다.

 

만약에 cache된 이후에 memory에 쓰기 operation이 발생하면 그저 over write해주면 되기 때문에 간단합니다.

 

 

마지막으로, 지금까지는 process context switch가 일어날 때 SP, PC 등등 값들을 저장해주고 난 이후에

다시 running할 때 값을 불러와야 하는 overhead에 대해서만 이야기 했었지만

context switch가 발생할 때 TLB의 모든 내용을 flush해줘야 합니다. 왜냐하면 지금까지 사용하는

정보와 다르게 TLB는 context switch로 돌아가게 될 process의 memory정보를 caching하고 있어야 하기 때문입니다.

 

 

 

 

 

 

 

 

 

 

Multilevel page table

 

 

 

 

 

 page table이 너무 큰 용량을 차지하기 때문에 문제가 발생할 수 있다는 단점이 존재했습니다.

 

위의 단점을 해결하기 위한 방법으로 multilevel page table의 방법을 사용합니다.

 

 

 

multilevel page table의 전체적인 구조는 위의 그림과 같고, 우선 매커니즘을 살펴보자면 아래와 같습니다.

 

 

 

 

 

virtual address의 $2^{20}$의 VPN을 두 단계로 나누게 됩니다.

 

master page를 index값으로 main memory에 있는 master page table에 access하고 해당 master page table의

결과값으로 Frame number가 아닌 secondary page table의 시작주소가 output으로 나오기 때문에 해당 주소를 가지고

secondary page table의 값을 더해서 해당 entry의 output으로 나오는 Frame number를 가지고

offset과 더해서 physical memory에 접근하는 매커니즘입니다.

 

 

 

자세히 들어가자면 기존에 $2^{20}$으로 사용되던 page table을 $2^{10}$개의 entry를 가지는

page table로 나누게 되고, master page를 가지고 index를 가르키게 되고 해당 entry 내부의 entry를 선택하게 되는 것 입니다.

 

아래의 그림을 보면 이해가 더 쉬운데, 쉽게 설명해서 master page는 $(2^{10}-1$개 중에서 선택하는 것이고

secondary page는 master page에 의해서 선택된 block의 내부에서 몇 번째에 있는 주소를 선택하느냐를 결정하는 것 입니다.

 

아래의 예로 따지면, master page로 2번 block을 선택하고 secondary page로 4번째 주소를 선택해서 해당 Frame number를

얻어서 page offset과 합쳐서 PA(Page address)를 가지고 physical memory에 접근하게 되는 것 입니다.

 

 

 

결국 위에서 전체 개요의 그림과 같은 구조로 표현이 되는 것입니다.

 

다시 그림을 가져오자면 아래와 같습니다.



여기서 의아한 부분이 하나 생깁니다. 저희는 page table이 one-level로 했을 때 너무 크기 때문에

two-level이상의 n-level page를 사용하는 것인데, total로 one-level과 two-level의 entry를 세어보면

오히려 two-level의 크기가 더 큰데 어떻게 된 일일까요?

 

 

 

 

 

 

위가 기본적인 one-level page table이라면 그 아래가 two-level page table을 본 것 입니다.

 

해당 그림대로 virtual address영역을 page table과 mapping을 할 때 현재 heap(stack과 code, global data 등등)을 사용하는

영역을 제외하고는 나머지 영역은 비어있게 됩니다. 그렇다면 실제적으로 $2^{10}$개의 page table 2개와 to-level page table

하나가 필요하기 때문에 전체적으로 $2^{10}*3$개의 페이지 테이블만 필요하게 되기 때문에

page table이 줄어든 것 입니다.

 

만약에 heap이 늘어나게 된다면 4M가 영역까지는 아래의 page table만 사용하다가 더 넓은 공간을 사용하게 되면

가운데에 필요없다고 표시해 놓은 공간을 추가적으로 할당해서 사용하게 되는 것 입니다.

 

 

여기서 꼭 two-level page table뿐만 아니라 design하기에 따라서 n-level page table로 구성할 수 있습니다.

 

 

만약에 64bit짜리라고 한다면 12bit의 offset을 제외하고 10bit씩 잘라보게 되면 총 five-level page table 구조를 만들 수 있습니다.

 

 

여기서 만약에 page table miss가 발생한다고 하면 총 5번의 access가 필요하기 때문에

여기서 TLB의 역할이 중요하게 됩니다. TLB hit가 발생해야 access를 줄일 수 있기 때문입니다.

 

 

 

 


 

지금까지 TLB와 multilevel page table에 대해서 살펴봤습니다.

 

 

다음에는 Inverted page table 구조와 page replacement algorithm에 대해서 배워보도록 하겠습니다.

 

 

글 읽어주셔서 감사합니다.

반응형