[컴퓨터 구조] 5-4. Page table & TLB

 

 

 

 

Page Fault penalty : virtual memory와 physical memory 사이 관계

 

virtual address가 나와서 physical address로 translation되지 못하는 경우, 하드디스크에만 주소가 있고 메인 메모리에는 없다는 것이므로 translation하기 위해선 프로그램은 stall하고 os가 디스크로부터 physical address로 주소를 fetch해와야 한다.

하드디스크의 액세스 타임은 5ms이므로 매우 속도가 느리기 때문에 이와같은 상황이 발생하면 엄청난 시간소요가 발생하게 된다.

 

cpu성능에서 cache miss가 중요한 영향을 미쳤던 것처럼, page fault rate도 중요한 영향을 미친다.

 

<page fault rate를 줄이기 위한 방법>

• fully associative palcement : virtual address가 physical address의 아무 곳에나 매핑되도록 만듦
• smart replacement algorithms : 더 현명한 방식으로 대처
• LRU : physical address의 전체에서 가장 오랫동안 사용하지 않았던 엔트리를 내보냄

 

 

Page Tables

 

이전에 virtual memory의 실제로 사용하는 부분만을 main memory로 보낸다 했었는데, 이 때 주소를 변환해주는 과정에서 virtual address를 physical address로 translate하는 역할을 담당하는 것이 바로 page table이다.

프로그램이 virtual number가 40개이고 physical page number가 10개라 가정.

 

특정 virtual address에서

1. page offset 그대로 copy

2-1. page table에 해당되는 physical address가 있다면 남은 virtual page number)를 남은 physical page number로 translation해서 가져옴

(virtual address를 os가 관리하고 있는 page table로 가서 해당되는 physical address를 가져온 다음 그 address로 fetch)

3. 해당 virtual address에 해당하는 physical address를 x처리

4. x처리 되어있던 physical number값 하나를 채워주어 전체 10개값을 유지

 

2-2. page table에 해당되는 physical address가 없다면 esception 처리를 하고 stall한 뒤 os가 page를 swap

swap : 하드디스크에 있던 것 physical 메모리로, physical 메모리에 있던 것 하드디스크로 내보냄. 

 

 

 

 

 

Translation using a page table

 

1.valid bit : physical page number가 있는지 없는지 표시

• 0 : physical page number가 physical memory에 없고 하드디스크에 있음
• 1 : physical page number가 physical memory에 있음 

2. virtual page number에 해당하는 physical page number 가져옴

3. physical address offset 그대로 copy

 

 

 

 

Mapping pages to storage

 

page table은 virtual memory의 각 page를 main memory의 page나 디스크에 저장된 page로 매핑한다.

virtual page number는 page table의 인덱스로 사용된다.

valid bit가 1이면 page table은 virtual page에 대응되는 physical page를 제공한다.

valid bit가 0이면 page는 디스크상의 지정된 디스크 주소에 존재한다. 

 

 

 

Fast Translation using a TLB

 

page table의 문제점 : 모든 메모리 액세스 중 주소를 사용하는 경우는 모두 한번씩은 page table을 액세스 해야한다.

page table 자체가 메모리 안에 있기 때문에 주소가 virtual address 안에서 나오기만 하면 메모리를 액세스 하고 fetch해야 한다. → physical memory 상에서 프로그램이 수행될 때의 메모리 액세스에 비해 virtual memory를 사용하면  메모리 액세스가 2배로 늘어나는 현상

 

DRAM은 50ns로 0.5ns인 cpu에 비해 100배 가량 느리다. 이를 보완해 주기 위해 캐시를 사용하였는데, page table로 인해 메모리 액세스가 2배로 늘어나게 되므로 성능은 떨어지게 된다.

 

solution : locality

temporal : 1번 액세스 했던 메모리 또 액세스

spatial : 1번 액세스하면 그 주변 메모리를 액세스

이 특성을 사용해 page table이 자주 사용되는 공간에 TLB를 추가해줌

→ 느린 메모리까지 가지 않고 빠르게 virtual address를 physical address로 변환 가능

→ virtual memory를 사용해도 속도를 느리게 하지 않으면서 동작시킬 수 있다.

 

 

TLB (Translation Loockaside Buffer) ≒ Page table의 캐시메모리

page table에 접근하는 것을 피하기 위해 최근에 사용된 주소 매핑을 보관하고 있는 캐시

virtual address를 physical address로 바꾸는 page table 중 항상 같은 위치를 지속적으로 여러 번 액세스 할 것이므로 그 중 몇개만 따로 빠른 메모리에 둔다.

 

 

 

 

Fast Translation Using a TLB

 

 

 TLB에서 va를 pa로 translate할 수 있는 내용이 있는지 확인

• TLB에 있다면 physical page address를 physical memory로 액세스
• TLB에 없다면 page table로 감
  • page table의 valid bit가 1이면 : physical memory로 translate할 내용 가져감
  • page table의 valid bit가 0이면 : os가 exception을 일으키고 physical memory와 disk memory를 swap → page table 업데이트 → 다음 메모리 액세스 때 TLB에서 Hit이 발생하도록 만듦 → 시간이 매우매우 오래 걸리는 과정

 

 

 

 

 

 

Page Fault Handler

 

page table의 dirty bit : 메모리에 load된 이후 page에 write를 한 적이 있는지 없는지를 표시하기 위해 page table에 dirty bit을 추가

- page 내의 어떤 워드에 write를 하면 dirty bit을 1로 업데이트

- os가 내보낼 page를 선택하면 새로운 page에게 공간을 내어주기 전에 그 page를 디스크에 써야 할 지 말지를 dirty bit을 보고 알 수 있다. → 다음번에 dirty bit가 1이면 이전 page를 디스크에 씀 (LRU방식)

 

 

 

 

TLB and Cache Interaction

TLB : Fully associative mapping

Cache : Direct mapping

 

 

source of misses

1. compulsory misses :  근원적으로 한번도 액세스 한 적 없을 경우 miss를 피할 수 없다.

2. capacity misses : 메모리 크기에 비해 캐시 사이즈가 작다면 miss가 발생한다.

3. conflict misses : 캐시 공간은 한정되어 있는데 그 공간보다 많은 데이터가 와서 자리경쟁을 하면 miss가 발생한다.

 

 

Cache design trade-offs

가정	장점	단점
캐시사이즈 증가	capacity misses문제 해결	액세스 타임 증가
associativity 증가	conflict misses문제 해결	액세스 타임 증가
블록 사이즈 증가	compulsory misses문제 해결	miss rate 증가해 pollution 발생 (불필요하게 가져와진 것들일 원래 있던 필요한 영역을 덮어쓰게 되므로 오염됨)

 

 

 

 

 

 

 

출처

https://slideplayer.com/slide/13453485/

http://thebeardsage.com/virtual-memory-translation-lookaside-buffer-tlb/