Intro
대부분의 General Purpose processor들은 page table을 이용해 VM을 지원하며, TLB의 page table에서 VA-PA mapping을 caching한다. TLB coverage는 이 cache된 mapping으로 access 가능한 memory의 양이다. (TLB entry # * page size) 지난 10년 동안 TLB coverage는 main memory size보다 천천히 증가했다. 따라서 오늘날 TLB coverage는 physical memory의 일부분밖에 안 된다. 따라서 working set이 더 큰 application은 성능 저하가 발생한다.
superpage는 한 TLB entry로 base page보다 더 큰 memory page를 차지할 수 있어, 같은 TLB entry 수로 더 큰 TLB coverage가 가능해 TLB miss가 줄어든다.
하지만 너무 큰 superpage를 부적절하게 사용하면
- application footprint가 증가 (4KB를 write하더라도 2MB씩 write하여 write하는 physical memory가 많아진다.)
- physical memory requirement가 증가 : memory pressure가 빨리 온다.
- paging traffic이 증가한다.
- internal fragmentation이 생긴다.
이러한 I/O 비용은 TLB miss 방지보다도 훨씬 크다. 따라서 OS는 page 크기를 혼합해서 사용해야 한다. 하지만 이 경우 external fragmentation이 생긴다. 따라서 external fragmentation이 생기지 않도록 OS가 지원해줄 필요가 있는데 대부분의 OS는 superpage를 이를 별로 지원하지 않는다.
본 논문은 general하고 transparent한(application에 상관없이 사용 가능한) superpage management system을 제안한다.
Contribution
- reservation-based approach를 확장하여 큰 superpage에 대해서도 적용.
- superpage에 대한 이점을 보여줌. fragmentation의 영향을 보여준 최초의 논문임
- fragmentation을 제어하기 위해 새로운 contiguity-aware page replacement 알고리즘을 제시
- dirty superpage의 demotion, eviction 등 superpage를 실용적으로 만드는데 필요한 문제를 해결
The superpage problem
Superpage에 대한 OS 지원의 필요성
지난 10년 동안 main memory의 크기가 증가하여 application의 memory requirement도 증가했으나 TLB coverage는 별로 증가하지 않았다. TLB는 일반적으로 fully associative이며 memory access의 critical path에 있기 때문에 access time이 작게 유지되어야 해서 TLB entry를 막 늘릴 수가 없으며 따라서 일반적으로 128개 이하의 entry를 사용한다. 이에 따라 최신 application은 TLB coverage보다 큰 working set을 가진다. 심지어 요새는 physical address cache가 TLB coverage보다 커져서 TLB miss가 cache에 있는 data에 대해서도 memory access를 해야 할 수도 있다.
TLB size ( = TLB entry # ) 를 키우지 않고 coverage를 증가시키는 방법인 더 큰 크기의 base page를 사용하는 방법을 채택할 수 있다. 근데 이 방법은 internal fragmentation이 증가하여 memory pressure가 더 빨리 발생하고, paging granularity가 증가하여 IO demand가 커진다.
따라서 base page는 그대로 두되 더 큰 size의 page를 같이 사용하여 internal fragmentation과 disk traffic을 줄이면서 TLB coverage를 늘릴 수 있다. 여러 size의 page를 사용하기 위해서 OS의 지원이 필요하다.
Hardware-imposed constraints
TLB hardware 설계에 의한 superpage 제약
- processor가 지원하는 page size 집합에 속해야 한다.
(Alpha processor는 8KB base page와 64KB, 512KB, 4MB superpage를 제공) - superpage는 physcial address space, virtual address space에서 모두 연속적이어야 한다.
- 같은 superpage 내의 모든 base page가 같은 protection attribute를 가져야 한다.
Issues and tradeoffs
virtual address space는 code, data, stack, heap 등의 memory object로 이루어졌다고 가정한다. 또 physical memory는 처음 access될 때 할당한다고 가정한다.
[Allocation]
- 언제, 얼마나, 무엇을 allocate할지?
- 연속성 보존 방법을 뭘로 할 것인지?
- reservation-based scheme : contiguity를 preserve한다. superpage 크기의 align으로 먼저 예약을 해놓는 방식이다. 나중에 superpage를 실제로 만들 때에는 이미 인접성, 정렬 제약 조건이 충족된다. 하지만 인접 page에 대한 지식 없이 superpage 크기를 정해야 한다는 단점이 있다.
- relocation-based scheme : contiguity를 create한다. superpage로 만들 수 있을 것 같으면 page frame을 인접 영역에 복사하여 superpage로 만든다. 재배치 비용이 크고 TLB miss가 많아서 reservation에 비해 성능은 좋지 않다.
[Fragmentation control]
multiple page size를 쓰거나 wired-page (paging이 불가능한 page)가 있으면 external fragmentation이 발생한다.
따라서 OS는 연속성 복구 technique을 적용해야 한다. 이 때 예약을 선점해서 다른 용도로 사용할 것인지 큰 예약으로 냅둘 것인지의 tradeoff가 있다.
[Promotion]
예약해놓은 곳이나, base page들이 크기, 연속성, 정렬, 보호제약을 만족하면 superpage로 승격할 수 있다.
promotion 정책은 TLB miss 감소라는 이점과 memory 소비 증가라는 손해에 대해 tradeoff가 있다.
[Demotion]
page attribute가 바뀌거나, 일부만 수정할 때 demotion이 필요하다. process가 superpage의 모든 부분을 사용하지 않고 메모리 부족이 있을 때 강등시킬 수 있다. 그런데 reference bit가 superpage에 대해 하나만 있기 때문에 어느 부분을 안 쓰는지 확인하기가 어렵다는 issue가 있다.
[Eviction]
memory pressure 시 physical memory로부터 inactive superpage를 evict해야 한다. 이 때 superpage는 dirty bit가 하나만 있어서 일부는 clean하더라도 superpage 전체를 flush해야 할 수도 있다는 문제가 있다.
Design
reservation-based superpage 관리 정책을 채택하여
- multiple superpage size
- very large superpage로의 scalability
- 드물게 참조된 superpage의 demotion
- compaction 없이 contiguity의 보존
- 부분적으로 수정된 superpage에 대한 효과적인 disk IO
로 확장
자료 구조
Buddy Allocator
- available physical memory는 Buddy Allocator를 이용해 관리
- multi-list reservation으로 2의 배수 크기로 각 크기별로 linked list를 가지고 있다가 할당하고 작은 크기로 쪼개는 형식
- 부분적으로 사용된 메모리 예약을 추적하고 예약을 선점할 때 사용
Population map
각 memory object의 allocation을 track할 때 사용한다. population map은 모든 page fault에 대해 query되기 때문에 효율적으로 찾을 수 있어야 하는데, 따라서 각 page size에 대응되는 level에 대해 radix tree를 만든다.
- root : 하드웨어에서 지원하는 가장 큰 superpage size
- leaf : base page
leaf가 아닌 node에는 다음 level의 superpage 크기 만큼의 영역을 유지하며, somepop (하위 level node 중 하나 이상 찬 것 개수), fullpop (하위 level node 중 꽉 찬 것 개수) counter를 가진다.
[Population map의 목적]
- Reserved frame lookup
page fault가 났을 때 이 page를 위한 reservation이 있는지 빠르게 찾을 수 있게 함. fault page에 대한 VA가 (memory object, page index) tuple로 변환되어 population map의 root를 결정함. - overlap avoidance
예약된 frame이 없으면 예약 시도. 이 때 physical address space에서 연속 공간을 찾는 동안 중복 영역을 감지하고 피한다. (somepop이 0인 root 경로의 첫번째 node로 결정) - promotion decision
fullpop인 애들에 대해 동일한 protection bit, dirty bit로 mapping된 page가 있으면 promote - Preemption assistance
preempt하는 동안 할당되지 않은 영역 상태를 population count로 확인
Multi-list reservation scheme
reservation list가 완전히 populate되지 않은 page frame extent를 linked list로 가지고 있음
ex) 64KB 범위가 필요한 경우
- buddy allocator에 요청
- 없는 경우 64KB의 reservation list 중 LRU를 선점
- list가 비어있으면 512KB list에 대해 선점 시도 (선점되면 쪼개짐)
- 없으면 base page 그냥 써야 함 (8KB reservation list)
Issue에 대한 Solution
Reservation-based allocation
page fault handler가 page frame을 할당할 때 한 번에 한 frame을 할당하지 않고 fault가 난 base page를 포함하는 영역에 대해 preferred superpage size만큼의 연속된 page frame set를 할당한다. 이 때 fault가 일어난 base page 외의 다른 page는 예약 상태로 예약된 page에서 fault가 발생하는 경우에는 base page의 page table의 mapping을 그대로 사용할 수 있다.
Preferred superpage size policy
page size를 크게 잡으면 demotion이 필요하지만, 너무 작게 잡으면 relocation이 필요하다. 일반적으로 demotion overhead가 relocation보다 작기도 하고, 크게 잡은 경우 예약을 선점할 수 있기 때문에 큰 size를 사용한다.
- fixed size memory object (ex : code, mmap file)
faulting page를 포함하고 다른 예약과 겹치지 않고 object를 초과하지 않는 선에서 가장 큰 size의 예약을 잡는다.
- variable size memory object (ex; stack, heap)
object의 현재 크기로 잡음. (안 커지는 개체도 있기 때문)
Preempting reservation
사용 가능한 메모리가 부족하거나, fragmentation이 과도하게 일어난 경우 reservation된 애들 중 사용하지 않는 frame을 선점할 수 있다.
할당이 요청되었으나 원하는 크기의 extent가 없는 경우
- allocation을 거부하고 더 작은 범위를 예약하거나
- 할당되지 않은 frame이 충분히 있는 기존의 예약을 선점
하여 원하는 크기의 extent를 만든다. 가능한 한 할당을 거부하기보다는 기존 예약을 선점한다고 한다. 선점하는 victim은 LRU policy로 선택한다.
Fragmentation control
여러 page size를 사용하다보면 external fragmentation이 생겨 큰 superpage의 개수가 부족해진다. 따라서 buddy allocator가 가능할 떄마다 coalescing을 수행한다.
또한 page replacement daemon이 contiguity-aware page replacement를 background에서 수행한다. 이 daemon의 기능은 implementation에서 설명한다.
Incremental promotion
예약이 모두 populate되지 않더라도 다음 크기로 승격할 수 있지만, 이 경우 memory footprint가 증가하기 때문에 그냥 모두 populate될 때 승격시킨다. 따라서 promotion은 점진적으로 일어난다.
populate : 예약 내의 base page가 mapping됨
footprint : 실제로 메모리에서 써야 하는 data의 크기. superpage를 사용하는 경우 base page만큼을 access하더라도 superpage의 size만큼 읽고 써야 한다.
Speculative demotion
- Incremental demotion
- page daemon이 eviction을 위해 특정 base page를 선택한 경우
- superpage의 일부분에서 protection attribute가 변경되는 경우 (hardware가 superpage에 대해 하나의 protection bit만 제공하기 때문)
demotion이 발생한다. demotion도 바로 base page 크기로 할 필요는 없기 때문에 incremental하게 수행한다.
- speculative demotion
superpage의 모든 부분이 활발하게 사용되는지 확인하기 위해 주기적으로 demotion을 하기도 한다. reference bit를 재설정할 때 해당 superpage를 demotion하고, 모든 base page가 참조되면 다시 promote한다.
Paging out dirty superpage (Evict)
dirty bit가 superpage에 대해 1개 뿐이어서 superpage 중 일부만 수정되었더라도 superpage 전체를 evict해야 한다. 이렇게 부분적으로 dirty한 superpage에 의한 I/O 성능 저하가 superpage의 이점을 초과할 수 있다. 따라서 write를 하면 superpage를 강등하고 모든 base page가 dirty되면 다시 promote한다.
[Inferring dirty page using hash digest]
대안으로 hash를 사용할 수도 있다. clean memory를 읽으면 해당 내용의 cryptrographic hash digest가 계산되어 기록된다. page을 flush할 때 hash를 다시 계산하여 실제로 disk에 기록할 base page를 확인한다. 근데 암호화하는 구현 자체가 overhead가 커서 본 논문에서는 사용하지 않았다고 한다.
Implementation Note
실제로 실험을 위해 위 내용들을 구현하기 위한 수정사항들을 설명한다.
Contiguity-aware page daemon
FreeBSD의 page daemon은 근사 LRU 순서로 active, inactive, cache page의 3개 list를 가진다.
- cache page : clean하고 unmapped → memory pressure일 때 쉽게 free 가능
- inactive page : mapping은 되었으나 오랫동안 참조되지 않은 page
- active page : 최근에 access된 page
memory pressure일 때 daemon은
- clean inactive page를 cache로 옮기고
- dirty inactive page를 page out하고
- active page에서 LRU 애들을 inactive page로 보냄
[본 논문에서 contiguity-aware하게 만들기 위해 수정 사항]
- cache page는 reservation 가능한 것으로 간주함.
즉, buddy allocator가 free page와 함께 coalesced하여 연속성을 높임. 이는 반대로 reservation 영역을 비워두지 않고 cache로 사용하겠다는 의미이기도 하다. cache page의 내용은 최대한 오래 유지하다가 참조되면 제거되고 active page로 넘어간다.
- page daemon은 memory가 부족할 때 말고 연속성이 낮아질 때에도 활성화한다. 이 때 낮은 인접성은 preferred size의 인접 영역을 할당하지 못하는 경우를 의미한다.
- inactive page가 많을 수록 연속성을 복원하기 쉬우므로 모든 clean page는 파일을 닫는 즉시 inactive로 이동함. (원래는 메모리가 부족하지 않으면 그냥 active로 유지한다고 한다.)
Wired-page clustering
wired-page는 위치를 바꿀 수 없어서 paging이 불가능한 page들을 말한다. 일반적으로 부팅 시 physical memory에 클러스터링되지만, 다른 프로세스가 실행되는 동안 kernel이 메모리를 할당하면 점점 scatter된다. 따라서 wired-page를 미리 식별하여 인접한 physical memory pool에 clustering한다.
Multiple mappings
두 프로세스가 file을 서로 다른 VA에 mapping할 수 있다. VA가 base page보다 더 크게 차이나는 경우 superpage를 만들 수 없다. application이 file을 mapping할 때 주소를 지정하지 않는 경우가 많으므로 kernel이 VA를 할당할 수 있다. 따라서 superpage와 호환되도록 VA를 선택하여 해결한다.
Reference
- Navarro, J., Iyer, S., Druschel, P., & Cox, A. (2002). Practical, transparent operating system support for superpages. ACM SIGOPS Operating Systems Review, 36(SI), 89-104.
