How is the Hierarchy Managed?
지금까지는 cache controller hardware를 통한 cache와 main memory사이의 관계를 살펴봤습니다. 이 글에서는 main memory와 disk 사이의 관계에 대해 살펴보겠습니다. 이는 OS에 의해 관리되며, TLB와 같은 hardware를 통해 mapping되기도 합니다.
Virtual Memory
가상 메모리는 main memory를 secondary memory의 cache의 개념으로 사용하는 것입니다. 여러 프로그램 간의 효율적이고 안전한 메모리 공유를 가능하게 하기도 하고(virtual address space를 통해 program간의 메모리를 분리할 수 있습니다), physical memory보다 더 큰 프로그램을 실행할 수 있게 합니다.
이는 locality에 의해 동작할 수 있는 것 입니다. 프로그램은 locality 원리에 의해 주어진 시가네에 주소 공간의 상대적으로 작은 부분에만 접근하는 경향이 있고, 이 작은 부분만을 cache(main memory)에 적재하여 사용하는 것입니다. 각 프로그램은 자체적인 virtual address space를 갖고 그 공간에서 compile됩니다. run time에는 각 virtual address는 physical address로 변환되어야합니다.
위 그림은 두 프로그램이 physical memory를 공유하는 방법을 그림으로 나타낸 것입니다. 각 프로그램은 각각의 virtual address space를 갖고 있으며, 이는 page 또는 segment로 나뉩니다. 각 page의 물리 위치는 프로그램의 page table에 의해 알 수 있습니다. *즉, 프로그램마다 page table은 따로 관리됩니다.
Address Translation
virtual address와 physical address간의 변환은 hardware와 software에 의해 이뤄집니다. 기본적으로 모든 메모리 요청은 virtual address에서 physical address간의 변환을 필요로 합니다. *CPU가 사용하는 address는 virtual address이며 cache나 memory가 사용하는 address는 physical address이기 때문에 기본적으로 translation은 필요합니다.
이때 페이지가 physical memory에 없는 경우를 page fault라고 부릅니다. page fault는 찾고자 하는 데이터가 메모리에 없어서 disk에서 검색할 때 발생합니다. disk에 접근 시간은 memory에 접근하는 시간보다 훨씬 큽니다. 즉 매우 큰 miss penalty로 인해 page fault가 발생하는 것은 중대한 사항입니다.
이런 page fault를 줄이기 위해 page는 4KB정도로 상당히 커야하며, 전략적인 replacement를 위해 hardware대신 software가 이를 처리합니다. 또한 write through가 아닌 write back을 통해서 최대한 disk에 접근하는 시간을 줄입니다. fully associative placement를 사용하면 page fault가 줄어들 수 있습니다.
*fully associative placement와 page fault와의 관계
왜 fully associative placement가 page fault(페이지 부재)를 줄여 주는가?
| 매핑 제약 | 가상 페이지 번호(VPN)의 일부 비트가 물리적 페이지 프레임(PFN) 세트를 먼저 결정 ⇒ 한 세트 안에 들어갈 수 있는 페이지 수(ways)만큼만 저장 가능 | VPN --> 어떤 PFN이든 자유롭게 배치 가능 |
| 충돌(conflict) 가능성 | 동일 세트에 자주 쓰이는 두 페이지가 동시에 필요하면, 서로를 내보내며 “충돌 페이지 부재(conflict miss/page fault)” 발생 | 충돌이 사라짐 ⇒ OS가 LRU 등 정책으로 진짜 덜 쓰는 페이지만 교체 |
| 교체 후보 | 세트 안(또는 동일 PFN)에 한정 | 메모리 전체 프레임 중에서 선택 → 더 나은 희생자 선택 가능 |
| 결과 | 필요한 페이지가 이미 쫓겨난 경우가 잦아 page fault ↑ | 같은 물리 메모리 용량에서도 page fault ↓ Chapter_05-2-note |
1. Conflict page fault가 사라진다
- Direct-mapped(1-way)나 N-way set-associative 배치에서는,
- VPN의 일부 비트가 동일하면 서로 반드시 같은 세트에 들어가야 합니다.
- 세트 용량(ways)을 넘어가면, 아직 자주 쓰이는 페이지라도 강제로 내보내게 되고, 이후에 다시 접근하면 page fault가 납니다.
- Fully associative는 “어느 PFN이든 OK”이므로 세트 충돌 자체가 없음 → 이 유형의 page fault를 원천 제거합니다.
2. 교체 정책이 훨씬 ‘똑똑’해진다
- 세트 제한이 없으니 전체 프레임 중 가장 오래 안 쓴 페이지(LRU)·Clock·WSClock 등
전역 정책을 적용할 수 있습니다. - “최근에 활발히 사용되는 작업 집합(working set)”을 물리 메모리에 더 오래 머물게 하여
capacity fault도 일부 완화됩니다.
Page table
page table은 placement information을 저장합니다. 이는 virtual page number로 indexing되는 page table entry(PTE)의 배열입니다. page table base register(PTBR)에 의해 page table에 접근할 수 있으며,
페이지가 메모리에 있는 경우 PTE는 physical page number와 reference bit, dirty bit 등의 bit들을 저장합니다. 반면 페이지가 메모리에 없는 경우 PTE는 swap space에서 위치를 참조해야합니다.
Replacement and Writes
page fault는 줄이기 위해 LRU 교체 정책을 많이 사용합니다. 이는 PTE의 reference bit를 이용하며 페이지에 접근할 때 PTE의 reference bit는 1로 설정되며, OS가 주기적으로 0으로 초기화합니다. 즉, reference bit가 0인 페이지는 최근에 사용되지 않았음을 나타내며 교체 대상이 됩니다.
disk에 write하는 것은 수백만 사이클이 소모되므로, 개별 위치가 아닌 블록 단위로 작성됩니다. 그렇기에 write through(하위 level에 데이터를 쓰는것)는 비현실적이므로 write back을 사용합니다. write back을 사용하기 위해 dirty bit도 PTE에 포함되며 dirty bit가 1이면 페이지가 disk에 작성될 때 overwrite됩니다.
Fast Translation using a TLB
TLB를 사용하면 더 빠른 translation을 이룰 수 있습니다. TLB가 없이 translation을 진행한다면, 즉 page table만 존재한다면, 주소 변환 과정은 두 번의 메모리 접근을 필요로 합니다(page table접근 + 실제 주소로 접근). 따라서 page에 접근에도 있는 locality를 이용하여 CPU 내부에 PTE에 대한 cache를 만들어놨는데 이를 TLB라고 합니다.
TLB는 일반적으로 miss rate = 0.01% - 1%를 기록하며 10 - 100 cycle의 miss penalty를 갖습니다. TLB miss는 hardware 또는 software로 처리할 수 있습니다.
앞서 말했듯 CPU는 VA를 cache 및 main memory는 PA를 사용하기 때문에 무조선 translation과정을 거쳐야합니다. 하지만 이때 2번의 메모리 접근이 필요하다면(without TLB), cache 접근 비용이 매우 비싸집니다. 그래서 TLB를 사용하여 cost를 줄이는 것입니다.
TLB는 fully associative, set associative, direct mapped 방식 모두로 조직될 수 있으며, TLB는 cache보다 작기 때문에 접근 시간이 보다 빠릅니다.
TLB misses
TLB도 miss가 발생할 수 있습니다.
(1) 만약 페이지가 메모리에 있는 경우: PTE를 메모리에서 load하고 restart합니다. 이는 하드웨어나 handler가 포함된 소프트웨어를 통해 처리될 수 있습니다.
(2) 만약 페이지가 메모리에 없는 경우: page fault입니다. 운영체제가 페이지를 가져오고 page table을 업데이트합니다. 이후 restart하며 수백만 사이클이 소모됩니다.
TLB miss가 발생하면 가능한 경우는 (1) TLB에는 page가 없지만 PTE는 있는 경우, 즉 메모리에는 있는 경우와 (2) 페이지 자체가 아에 메모리에 없는 경우가 있습니다.
miss handler는 destination register가 이상한 위치에 덮어쓰기 전에 TLB miss를 인식해야하며, (1) 의 경우 exception을 발생시키고 handler가 메모리에서 PTE를 TLB로 복사한 다음 restart합니다. (2) 의 경우 page fault handler가 처리합니다.
Page fault handler
우선 fault를 일으킨 PTE를 찾습니다. 이를 이용해 disk에서 페이지를 찾고, 교체할 페이지를 선택합니다(이때 dirty가 1이었던 PTE였다면 disk에 먼저 씁니다). 페이지를 메모리로 읽어들이고 Page table을 업데이트 합니다. 프로세스를 restart하고, fault를 일으켰던 명령부터 다시 시작합니다.
*위 그림은 VA -> PA -> Cache access 까지를 나타내는 그림입니다.
TLB Event Combination
가능한 TLB, Page table, Cache miss/hit 표 입니다. 가장 마지막 3개를 보면,
(1) TLB가 hit이지만, Page Table이 miss일 수는 없습니다: TLB가 hit라면 해당 page가 memory에 있다는 의미인데, Page table에서 miss가 발생할 수 없습니다. inclusive에 의해 Page table은 TLB가 가지고 있는 page들을 포함해야합니다.
(2) Page Table이 miss이지만, Cache가 hit일 수는 없습니다: Page Table이 miss라면 해당 page는 disk의 swap space에 있다는 의미인데, cache가 hit라는 것은 해당 data는 memory에 존재한다는 뜻으로 모순됩니다.
Why not a virtual addressed cache?
이 모든 일들은 CPU는 VA를 만들고 Cache는 PA를 이용해서 생기는 문제입니다(즉 VA를 PA로 바꿔야만 Cache를 이용할 수 있는 상황). 그렇다면 Cache가 VA를 이용하게 만들면 되지 않을까요?
이는 공유 데이터를 사용하는 두 프로그램이 동일한 PA에 대해 서로 다른 VA를 가질 수 있습니다(VA space는 프로그램마다 존재하므로). 이로 인해 cache는 공유하는 데이터에 대한 복사본이 두 개가 생기며 일관성에 문제(coherence issues)가 발생할 수 있습니다.
Reducing Translation Time
하지만 아에 불가능한 것은 아닙니다. VA의 offset과 PA의 offset은 서로 같은 값을 가진다는 것을 이용하여 이를 병렬적으로 overlap하여 처리할 수 있습니다:
