20. Superpage

서울대학교 컴퓨터공학과 김진수 교수님의 "고급 운영체제" 강의를 필기한 내용입니다.

다소 잘못된 내용과 구어적 표현 이 포함되어 있을 수 있습니다.

Superpage §

• Superpage 말고 Hugepage 라고 용어를 사용하기도 하는데 이것은 linux-specific 용어인듯.

Superpage, Basepage §

• Basepage: 원래의 page 사이즈 (4Ki)
• Superpage 는 basepage 보다 사이즈가 크다는 것 이외에는 동일
  • $2^n$ 크기
  • TLB 하나 차지
  • Physical 에서나 virtual 에서나 모두 연속된 공간
  • 경계에 맞아야 된다 (align)
    • 뭔지 알제? 안맞으면 superpage 로 묶을 수 없는 애매한 공간이 생겨벌임
  • Superpage 가 하나의 page 로 취급되기 때문에 전체에 대해 하나의 reference, dirty, protection 세트를 가진다
    • Superpage 내의 basepage 를 따로 취급할 수는 없다 이거야
• Superpage 를 basepage 로 사용하는 경우 - basepage 사이즈를 그냥 키워버리는 경우
  • 당연히 internal fragmentation 이 늘어나니까 안된다
  • swap 의 상황에서 IO amplification 이 발생
    • 데이터의 일부분만 바뀌었는데 큰 크기의 page 전부가 디스크로 내려간다.
• 이게 필요한 이유는 TLB coverage 때문
  • TLB 의 특혜를 받을 수 있는 physical frame 들이 너무나도 적더라
• Superpage 는 arch 눈치를 봐야 한다
  • 앞서 말한것 처럼 page table 의 구조는 arch-specific 하고, 이 page table 의 구조가 superpage 지원과 연관있기 때문에 당연히 arch 눈치를 봐야 한다.
  • x86_64 에서는 page table lv 없애는 식으로 2MB, 1GB superpage 구현
  • ARM 의 경우에는 임베디드에서 많이 사용되다 보니까 반대로 작은 사이즈의 page 를 제공한다.
• 이전에는 user 가 직접 superpage 를 요청할 수 있었다.
  • superpage 요청 인터페이스를 제공
  • 그래서 프로그래머가 코드를 짤 때 superpage 가 필요하면 명시적으로 요청하도록 했다 (뭐 mmap arg 같은걸로)
  • 하지만 유저는 이것을 모르게 (transparency) 하기 위해 기각

Concerns for superpage §

• Issue 1: Superpage allocation
  • Relocation based: virtual memory 상의 연속된 공간에 대한 page 할당을 그냥 막 physical page 를 할당해 준 뒤 나중에 superpage 사이즈가 되면 복사해서 물리적으로 연속되고 경계에 맞게 합치기
    • 당연히 복사 overhead 가 있다
  • Reservation-based: 나중에 superpage 로 합쳐질 것을 고려하여 해당 공간을 미리 예약해놓고 page fault 가 나면 예약된 공간에 넣는 것
    • 당연히 예약 공간을 필요로 하기에 낭비가 된다
  • 이 둘 중에 어떤 것을 택해야 할 지의 issue
• Issue 2: Promotion
  • Basepage (혹은 작은 사이즈의 superpage) 를 큰 superpage 로 묶는 것을 Promotion 이라고 한다.
  • 그럼 언제 superpage 로 묶을까가 issue 가 된다.
    • 작은사이즈부터 단계적으로 묶어나갈 수도 있고
    • 더 큰 사이즈가 될때까지 기다렸다가 묶을 수도 있고
  • Physical page 를 다 할당하기 전에 묶을 수는 없다
    • 그 전에 묶으면 다 오지도 않았는데 page table 에서는 valid bit 이 켜져 있어서 접근할 수 있다고 생각하기 때문
• Issue 3: Demotion
  • Superpage 를 잘라서 다시 작게 만드는 것을 Demotion 이라고 한다.
  • Superpage 내에서 reference, dirty, protection 등의 attribute 를 세부적으로 관리하고자 할 때 demotion 이 필요
    • Write amp 줄이기 - superpage 의 일부만이 modified 되었는데 이 큰 사이즈 전체를 디스크로 내려보내는 것은 비효율적
    • Protection bit 변경 - superpage 의 부분부분이 다른 protection bit 을 가져야 한다면, 이것을 superpage 로 묶인 상태로 두면 안된다
  • Issue 는 superpage 의 어느 부분이 자주 reference 되는지 어떻게 체크할 것이냐 이다.
    • 덜 reference 되는 애들을 swap 해야 하기 때문
• Issue 4: Fragmentation
  • 여러 사이즈의 page 들을 사용하다 보면 framentation 이 생긴다.
    • 뭐 디스크 조각 모음마냥 중간중간 hole 이 있어서 합치면 더 크게 superpage 로 묶을 수 있을텐데 싶은 아쉬운 모멘트들
  • Swap 안하는애들이 중간에 몰려있으면 연속된 공간을 찾기 어렵기 때문에
  • Swap 안하는 커널같은 애들을 한쪽에 몰아넣기

Superpage (OSDI’02) §

Observation §

• 하나의 virtual memory object 의 경우에는 얘네들이 한번에 참조되는 경우가 많더라
• 그래서 얘네의 경우에는 적극적으로 superpage 로 만들겠다

Superpage Allocation: Preemptible Reservation §

• Superpage 를 위한 연속 공간을 확보할 때, relocation 방식이 reserve 하는 것을 기본으로 가져간다.

Opportunistic reservation policy §

• Page fault 시에, 어느 사이즈의 superpage 가 적합할지 예측하여 reserve 한다.
  • Fixed size virtual memory object (code 등) 의 경우에는 원본 사이즈보다 크지 않는 최대의 supersize 크기로 reserve
    • 당연히 사이즈가 안바뀌니까 더 많이 reserve 하면 무조건 낭비
  • Dynamic size virtual memory object (heap 등) 의 경우에는 넘어갈 수 있게 reserve
• 그리고 만약 이 예측이 틀리면, 나중에 조정
  • 너무 커: 나중에 preempt 시킴
  • 너무 작어: 나중에 realocation 방식으로 더 큰 superpage 로 전환
• 참고로 Reserve 할 때에는 free frame 뿐 아니라 언제든 내보낼 수 있는 frame 도 가능하다고 한다.
  • 가령 page cache 공간도 가능하다

Reserve Preemption §

• 연속된 공간이 더 이상 없다면, 지금 reservation 되어 있는 공간을 reserve 해제해서 주겠다는 것.
• 이를 위해, reserve 되었지만 사용되지는 않은 공간을 index 로 하여 각 superpage reservation 을 관리하는 자료구조인 Reservation list 를 활용한다.

Incremental Promotion §

• Reserve 는 max 로, 실제로 superpage 로 만드는 promotion 은 incremental 하게

Speculative + Incremental Demotion §

• Speculative demotion
  • Memory pressure 상황에서, superpage 전체를 전부 swap 하는 것은 바보같은 짓이니 이 중에서 실제로 많이 reference 되고 있지 않은 부분만 swap 하는 것이 현명할 것이다.
  • 근데 어떻게 어느 부분이 자주 reference 되고 어느 부분은 그렇지 않은지 알 수 있을까?
  • 알 수가 없으니 일단 쪼갠 뒤 좀 시간을 두고 지켜보고 나중에 다시 묶자는 생각 (Speculative).
    • 메모리가 부족해지면, Superpage 의 reference bit 을 끌때 얘를 아예 demotion 시켜버린다.
    • 그리고 일정 시간이 지나면 몇몇 basepage 들에 대해서는 reference bit 가 다시 켜져있을 테니 얘네들만 다시 promotion 하고
    • 시간이 지나도 reference bit 이 켜지지 않는 애들에 대해서는 swap out 시켜버린다.

• Incremental demotion
  • 위의 상황은 (1) swap 영역으로 내쫒을 때 (2) 누구를 내쫒아야 할 지 모르는 것이고,
  • Incremental demotion 을 하는 상황은 그 target 이 누구인지 알 때이다.
  • 즉, 어떤 특정한 basepage 에 대해 modified 되어서 dirty bit 가 켜져야 하거나, protection bit 을 바꿔야 하는 상황인 것.
  • 이를 위해 어떤 basepage 가 modified 되면, 그 superpage 를 demotion 시켜서 basepage 로 다 쪼개버리고 다시 incremental promotion 을 진행한다.
    • 근데 이게 incremental demotion 이 맞는지는 모르겠음; 이것도 그냥 speculative demotion 으로 치는건가?
  • 논문에서는 변경감지를 위해 hash 도 언급하지만 구현 오버헤드가 커서 사용은 못한다.

Population map §

• Reservation 공간에서 어디가 populate 되었는지를 추적하기 위함
• 그래서 어떤 virtual page 가 있을때 이놈에 대한 physical page 가 이미 reserved 된 공간인지 확인
• virtual 공간을 최대 superpage 사이즈로 나누고
• 각 superpage 공간에 대해 어디를 사용하고 있는지 등을 redix tree 로 관리하는 것
• 다만 여기에서 사용하지 않는 superpage 공간이 있을 테니 사용하는 superpage 공간을 hash table 로 관리
• 그래서 다 차면 promotion, preemption 할 때는 어디를 줘야 하는지 등 파악

FreeBSD implementation §

#draft 이부분은 논문 참고해야 한다..

Evaluation §

• page 사이즈 섞어찌개가 더 좋다

Follow up §

• Ingens (OSDI;16): VM 의 physical 은 host 의 virtual 이어서 VM physical 을 host 의 huge page 로?
• ATC;20 에 superpage 비교논문있다