Virtual Memory, TLB, Cache Interacton - 임베디드 컴퓨터 구조

Virtual Memory

• Physical Memory는 한정되어 있음
• Main Memory를 절약하기 위해 CPU와 OS를 이용하여 Secondary (Disk) Storage에서 데이터를 불러오자
• 프로그램들은 Main Memory를 공유한다
  • 각각의 프로그램은 독립된 Virtual Address Space를 가지는 것처럼 표현된다.
  • 각각의 프로그램은 다른 프로그램의 메모리를 침범하지 못한다
• CPU와 OS가 Virtual Address를 Physical Address로 변환하는 역할을 한다
  • VM "block" (최소 단위)는 page라고 불린다
  • VM translation "Miss"는 page fault라고 불린다

• Virtual Address는 VPN(Virtual Page Number), Page Offset 두 Component로 나뉜다.
• Page Offset은 page의 고정 크기에 따라 달라진다.
  • 여기에서는 4kb 크기를 갖기 때문에 4k = 2^12 => 12bits가 Page Offset으로 사용되었다.
  • Offset은 변환없이 Physical Address의 Page Offset으로 전달된다.
• 나머지 20bits는 VPN이 된다. VPN은 Translation을 거쳐 PPN(Physical Page Number)가 된다.
  • 그림에서 Physical Address가 30비트인 이유는 1GB 메모리를 가정하였기 때문.
  • 2^30 = 1024^3 = 1GB

Translation Using a Page Table

• Page Table은 Valid bit, PPN이 저장된 Array
• VPN의 개수만큼 Page Table Entry를 가진다
  • VPN이 20비트이니 2^20개, 1M개의 Entry를 가진다.
  • PPN이 18비트, Valid가 1비트. Entry가 19비트의 크기를 가진다면 전체 Page Table의 크기는 대략 2.375MB 정도
  • 프로그램이 하나 생성될 때마다 3MB씩
• Page Table 또한 메인 메모리에 저장된다.
  • 프로그램이 자신의 Page Table의 시작 주소를 알 방법이 필요하다
  • 프로그램 로딩 시 Page Table Register를 하나 할당하여 시작 주소를 저장
• Page가 메인 메모리에 존재한다면
  • PTE(Page Table Entry)가 PPN을 저장하고 있다
  • 다른 status bits가 세팅되어 있다 (referenced, dirty, valid)
  • referenced: 페이지 참조 시 1, 주기적으로 0. 0이면 퇴출 가능하다는 플래그
  • dirty: 데이터가 메인 메모리에서 수정되었는지 여부를 가리키는 플래그
  • valid: 메인 메모리에 존재하면 1
• Page가 디스크에 존재한다면
  • PTE가 Disk 주소를 가리킨다
  • valid: 디스크에 존재하면 0
  • 메인 메모리 Full 시 Policy 따라 퇴출 이후 메모리로 데이터를 가지고 들어온다

Mapping Pages to Storage

Page Fault Penalty

• page fault 시 page는 디스크로 가지고 들어와야 한다
  • milions of clock cycles가 걸린다
  • 하드웨어적으로 제어하기에는 너무 복잡하기 때문에 OS 코드에 의해 제어된다
• page fault rate를 줄이려는 노력
  • fully associative placement
    • 하드웨어 비용이 증가
  • Replacement Algorithm

Replacement and Writes

• LRU Replacement
  • 페이지에 접근 시 reference bit (= use bit)이 1로 세팅된다
  • OS가 reference bit을 주기적으로 0으로 만든다
• FIFO
  • 가장 먼저 들어온 페이지가 가장 먼저 교체된다
• Second Chance Algorithm
  • FIFO의 변형
  • Queue에서 첫 번째 요소를 뽑았을 때, 해당 PTE가 참조 비트가 세팅되어 있으면 참조 비트를 0으로 만들어 Queue의 맨 뒤로 이동시킨다
• Disk Write는 Milions of Clock Cycles가 걸림
  • write-through는 실용적이지 않음
  • write-back을 사용한다
  • 변경 사항이 있을 경우 PTE 내 Dirty Bit을 1로 Set한다
  • Replace 될 때 Dirty Bit이 1이면 write-back 매커니즘이 실행됨

Fast Translation Using a TLB

• Address Translation은 두 번의 Memory Access를 요구한다
  • 메모리의 Page Table에서 PPN 읽을 때 한 번
  • 메모리에서 Phys Adder 읽을 때 한 번
  • 시간이 두 배로 소요된다
• 그러나 우리에겐 시간 낭비를 방지해줄 Locality라는 개념이 있다
  • PTE에 대한 Cache를 만든다
  • TLB(Translation Look-aside Buffer)라고 부른다
    • 보통 16~512 PTE는 Hit이면 0.5~1 cycle이 걸린다
    • Miss면 10~100 cycle 걸린다
    • Miss Rate는 보통 0.01% ~ 1%
    • Miss에 대한 처리는 HW or OS가 한다
• TLB는 하드웨어
• Page Table은 메인 메모리에 존재하는, 메인 메모리의 자료구조
• Page Table의 PPN에는 Physical Memory나 Disk Storage의 주소가 올 수 있다.

TLB Miss가 발생했을 때

• 페이지가 메모리면
  • PTE를 메모리에서부터 불러오고 다시 시도
  • 하드웨어 제어 가능
    • page table 구조에 따라 하드웨어가 복잡해짐
  • 소프트웨어 제어 가능
    • 특별한 예외를 발생, 적절한 핸들러 배치
• 페이지가 디스크면 (page fault)
  • OS가 페이지를 불러오고 페이지 테이블을 업데이트
  • fault가 발생한 명령어를 재실행한다

TLB Miss Handler

• TLB Miss는 다음을 의미함
  • 페이지가 존재하나 PTE가 TLB에 없음
  • 페이지가 존재하지 않음
• 레지스터 값이 덮어씌여지기 이전에 TLB Miss를 식별해야 함
  • 에러 유도 후 overwrite 이전에 먼저 처리
• Handler는 메모리에서 TLB로 PTE를 복사한다
  • 이후 명령어 다시 실행
  • 페이지가 존재하지 않으면 Page Fault가 또 발생
  • Page Fault Handler -> TLB Miss Handler -> Restart Instruction

Page Fault Handler

• Faulting Virtual Address 사용하여 PTE를 찾아낸다
• Disk에서 읽어올 Page 찾아낸다
• 변경될 페이지 선택
  • dirty bit이 설정되어 있으면 write to disk
  • Write Buffer를 적용할 수 있지 않나 -> OS의 문제
• 페이지를 메모리로 읽어오고 페이지 테이블을 업데이트한다
• Faulting Instruction 다시 실행

TLB and Cache Interaction

• 캐시 tag가 Phys Addr를 저장하면

  • 현재 Virtual Page Number를 각 Cache Block들과 비교하기 전에 PPN으로 Translate 할 필요가 있음

• 문제는 Physical Page Number에 Cache Index 중 2비트가 들어있다는 거임

  • Data를 찾는 속도가 현저히 느려짐 (Critical Path)

  • 이를 해결하기 위한 방안

    1. 페이지 크기를 4배 키워 Page Offset을 2비트 키운다
    2. 4-way Set Associative Cache를 사용하여 Cache Index를 2비트 줄인다
    • 두 번째 방법이 더 많이 사용됨

Memory Protection

• 서로 다른 task는 Virtual Address 공간 일부를 공유할 수 있다
  • 잘못된 접근은 막아야 함
  • OS의 권능이 필요함
• HW가 OS의 메모리 Protection을 도움
  • Privileged Supervisor Mode (kernel mode)
  • Privileged Instruction
  • kernel mode에서만 접근할 수 있는 Page Tables과 Other State Information
  • System Call Exception