Address Translation_운영체제(10)

Page Tables

• Space over head of page tables
  • 32 bit address의 page(0~11 : offset/12~31 : page#)를 table로 만들면 process당 4MB의 space
• 낭비가 심해서 table의 사용하는 부분만 구현을 하는 방식을 생각

Two-level Page Tables

• Virtual address의 page number를 2개의 부분으로 분할한다.
• Master page# : master page number → secondary page number
• Secondary page# : secondary page number → page frame
• 마지막에 offset과 결합하여 physical memory로 도달
• Advantage
  • 전체를 다 사용하지 않고 일부만 사용하기 때문에, 이러한 일부를 나타내는 page table은 memory에 적재될 필요가 없다.
• 만일 전체 주소 공간을 다 사용하는 program이면 장점이 존재하지 않고 메모리 access만 더 늘어나게 된다.
• 일부만 사용하는 application에 도움이 된다.

Hashed Page Tables

• 자신의 page number를 가진 entry가 나올 때까지 hash를 search
• 매 page마다 hash function을 사용한다.

Clustered page tables

• 매 page마다 사용하는 것이 아닌 page block에 대해서 hash function을 적용한다.
• block offset을 이용하여 block의 page를 찾아간다.

Inverted Page Tables

• 4KB/page, 64bit : 12 offset, 52 page number → 2의 52제곱 개의 PTE
• main memory에 어느 process에 어떤 page의 number를 알려준다.
• Frame I에 어떤 process가 있는지 pid를 담아둔다.
• inverted page table은 process마다 제공되는 것이 아니다. system에 1개 존재한다.
• page table에서는 linear하게 차례대로 순회하며 찾는다. 시간이 걸릴 수 있다.
• matching이 일어나지 않으면 이 pid의 process는 memory에 존재하지 않는 것을 의미한다.
• page table에서 linear하게 찾기 때문에 hash table을 사용하는 방식도 존재한다.

Paging Page Tables

• Page table도 kernel이 관리하는 memory에 위치한다.
• 이를 physical memory에 위치하게 하면 translation이 필요없고 address하기 쉽다. 하지만 process를 사용하는 시간동안 memory를 차지하고 있는 문제가 있다.
• OS virtual memory로 관리하게 된다면 사용하지 않는 page를 disk에 위치시킬 수 있다. 하지만 모든 page가 disk에 위치한다면 문제가 있을 수 있기 때문에 outer page table은 절대 내보내지 않는다.(wiring)

TLBs

• address translation을 지원하는 cache memory를 이용하는 방식(hardware)
• page table을 거치기 때문에 memory access 과정이 늘어나는 문제를 해결하기 위한 방식이다.
• 모든 entry를 pararell하게 볼 수 있는 특수 memory
• TLB에 원하는 virtual page가 존재하면 TLB hit가 발생하고 page frame이 output으로 나온다.
• TLB miss가 발생하면 page table로 접근하여 진행한다.
• process에서 가장 많이 사용하는 address pair를 가지고 있는 working set이다.
• Hit rate가 중요하다. 약 99% hit 된다.

Handling TLB misses

• miss가 발생하면 TLB를 update 해야한다.
• Hardware : OS가 table을 관리하지만 Hardware도 접근할 수 있기 때문에 정의를 한다.
• Software : OS를 호출하고 PTE를 읽어 TLB에 load한다.
• software 방식은 느리지만 TLB를 OS가 원하는 방식으로 flexible하게 구성할 수 있다.

Managing TLBs

• context switch가 일어나면 TLB를 reload해야한다.
• TLB miss가 발생하면 새로운 PTE가 load되야하고, TLB가 가득 차있다면 LRU 방식을 이용하여 replacement를 한다.

Memory Reference

• read가 일어나면 TLB에 접근하여 page number match를 하고 PTE를 return
• TLB에서는 PTE가 읽혀지도록 승인한다.
• PTE에는 frame이 존재하고 MMU는 이 frame과 offset을 결합하여 physical address에 접근한다.
• MMU가 physical address를 이용하여 CPU에게 data(value)를 넘겨준다.