운영체제

19) 페이징: TLB

페이징은 성능저하를 유발할 수 있다...
왜?? 페이지테이블 보려고 메모리 참조해야하고,,, PTE때문에 메모리를 써야하니..
거기다.. 메모리..참조는... 오래걸림.. 그럼 어캐 주소 변환할 때 속도를 올리지?

하드웨어로부터 도움을 받자!!

TLB!!

TLB

• MMU의 부분이다

  • 주소 변환 캐시이다.

• 자주 참조되는 가상->실제 주소 변환 정보를 저장하는 하드웨어 캐시이다.

  • 가상 메모리 참조시, 하드웨어는 TLB에 원하는 정보가 있는지 본다
    • 있다면, 페이지테이블을 참조하지 않고 빠른 변환을 만들어 준다.

TLB entry

• 완전 연관 방식으로 설계된다.
• VPN, PFN, other bits로 구성
• 보통 TLB는 32,64,128 entry를 가진다
• 하드웨어는 변환을 위해 전체 TLB를 병렬적으로 동시에 찾는다
• other bits: valid(유효한 변환 정보를 가지는지), protection, address-space identifier, dirty

cache

• SRAM이다

  • 메인 메모리는 DRAM임

• 자주, 최근에 사용되는 인스트럭션이나 데이터를 저장해 놓는 메모리가 빠르게 접근할 수 있는 저장소이다.

• 메모리와 메인 메모리 사이 데이터 이동이 느리기때문에 캐시를 둔다

TLB 기본 알고리즘

1. 가상 주소를 추출하고 해당 VPN이 TLB에 있는지 체크한다.
2. TLB hit(있음)이면 TLB에서 PFN을 얻을 수 있다.
   1. 접근 권한 검사
   2. PFN을 얻어 offset과 합쳐 물리 주소 얻음
   3. 물리 메모리 접근 가능
3. TLB miss(없음)이면 PTBR과 VPN을 이용해 해당 PTE를 찾는다
   1. 접근가능한지 검사, 유효한지 검사
   2. TLB에 변환 정보를 갱신
   3. 재실행(TLB에 정보가 있으니 변환이 가능)

TLB는 프로세서와 가깝고, 빠르기 때문에 주소 변환이 빠르다.
하지만, 미스가 나면 페이지테이블을 참조해 페이징 비용이 커지게 된다.
TLB 미스를 줄여야한다.

배열 접근

어떻게 TLB의 성능을 향상시키지

깜짝 문제~~~~~!!

• 가상 주소 공간 8비트, 페이지 크기는 16바이트이면.. 나머지 정보는??

가상 주소 공간이 8비트니 실제 메모리는 2^8바이트만큼 존재
페이지크기가 16바이트니 offset은 4비트가 필요(2^4= 16)
그럼 가상 주소는 VPN이 4비트 offset이 4비트
가상 페이지는 총 16개 존재

메모리는 배열이야.. 그리고 메모리 한칸은 1바이트야
그래서 가상주소공간이 8비트로 이루어져 있다면 이를 이용해 만들 수 있는 주소는 2^8개니 실제 주소는 2^8바이트를 가져
페이지는 주소공간을 똑같이 나눈다 했어,, 페이지 크기가 16바이트래
offset은 페이지 어느 부분에 위치하는지 판단하는거야 그런데 페이지가 16바이트네?? 그렇다면 offset은 4비트가 필요해
가상 주소가 8비트라 했는데 offset이 4비트면 VPN은 남은 4비트로 활용해야겠네 그렇다면 가상 페이지는 총 16개가 존재해

이제 가상 주소를 실제 주소로 전환할때 VPN에 맞는 뭐.. TLB에 있거나 PTE에 있거나 한 PFN을 얻고, 여기에 offset을 추가해 어디에 위치하는지 알아내

int sum=0;
for(i=0;i<10;i++)
    sum += a[i];

피피티 그림봐

• a[0]일때 TLB가 초기화된 상태니 TLB miss가 난다
  • 그럼 a[0]이 있는 6번 페이지를 TLB에 갱신
    • a[1],[2]는 hit
• a[3] miss
  • a[3]이 있는 7번 페이지를 TLB에 갱신
    • a[4],[5],[6]은 hit
• a[7] miss
  • a[7]이 있는 8번 페이지를 TLB에 갱신
    • a[8],[9] hit

=> 이 경우 spatial locality 덕분에 성능 향상이 되었다.

페이지의 크기가 크면 TLB 미스가 더 줄어든다

 왜? 미스가 나서 TLB에 페이지에 있는 데이터를 갱신할 때,  더 많은 데이터를 가져오니깐 spatial한 데이터들에 대해 미스가 줄어든다

=> TLB는 locality를 이용해 성능을 향상할 수 있다.

Locality 지역성

Temporal locality 시간 지역성

• 프로그램이 주소 x에 접근한다면, 곧 x 근처의 메모리에 접근할 것이다.

Spatial locality 공간 지역성

• 최근 사용된 인스트럭션이나, 데이터는 곧 다시 사용될 것이다.

=> 프로그램이 위의 지역성을 보인다면, TLB 사용 효과는 눈에 띌 것이다.

TLB미스는 누가 처리하는가

• CISC에선 하드웨어가 TLB 미스를 처리한다
• Risc에선 소프트웨어 관리 TLB를 사용한다

하드웨어는 안정성
하드웨어는 simple

EAT effective access time

TLB hit 비율 80% ,TLB 검색: 20ns, 메모리 접근: 100ns

EAT = 0.80 X (20+100) + 0.20 X (20+100+100) = 140ns

계산 방법

    hit했을 때 값 + miss때 값
    (hit 비율 X (tlb검색+메모리접근(원하는 메모리))) + (miss 비율 X (tlb검색 + 메모리접근(페이지테이블 접근) + 메모리접근(원하는 메모리)))

이슈: context switching

프로세스마다 TLB의 정보는 해당 프로세스에서만 유효하다

다른 프로세스인데 같은 VPN에 대한 전환 정보가 TLB에 있따면...

P1과 P2가 있다.
TLB에 P1과 P2의 페이지 테이블의 저장되어 있다. 두 정보 다 VPN이 10이다.

이렇게 된다면 TLB에는 VPN 10에 대한 변환 정보가 2개가 존재한다.
어떻게 어느 프로세스를 위한 정보인지 확인할까?

ASID 공간을 TLB에 추가한다.

• address space identifier, 주소 공간 식별자
• 프로세스 별로 TLB 변환 정보를 구분할 수 있다.

TLB를 context switch할 때마다 비우면(flush) 안되나??

context스위칭 마다 모든 valid bit을 0으로..

• 새 프로세스가 실행될 때마다 miss 발생
• 높은 성능 부담

다른 VPN을 가지는 두개의 프로세스들이 같은 물리 페이지를 가리킨다면??

• 페이지 공유는 실제 페이지 사용 수를 줄이는데 효과적이다

코드 공유

• read only(reentrant) 코드는 프로세스 사이 공유된다
• 다중 스레드가 같은 프로세스 공간을 사용하는 것과 유사하다
• 공유하는 페이지 수정이 허용된다면, ipc에 유용하다

TLB 교체 정책

TLB에 새로운 항목이 올라올때, 현재 존재하는 항목 중 하나와 교체해야한다.
누굴 선택하지??

• 목표는 miss 비율을 줄이는것, 히트 비율을 올리는 것

LRU를 교체

LRU least recently used

• 사용된지 오래된 것은 다시 사용될 확률이 낮다. => 교체대상
  • temporal locality에 이점을 사용
  • 반면에 만약 n개의 정보를 저장하는 TLB가 n+1개의 페이지에 대한 반복문을 수행하면...
    • 계속 미스가 난다..

랜덤

• 교체 대상을 무작위로 정함
• 예상치 못한 예외 상황을 피할수도...? 위와 같은