[OS] Complete VM Systems: Linux

이번 글에선 Linux for Intel x86의 VM system에 대해서 다룬다.

 

Linux Virtual Memory System

 

Linux Address Space

Linux 또한 VAX/VMS를 비롯한 modern OS와 비슷하게 virtual address space가 user spcae / kernel space로 이루어진 구조이다.

• 0 ~ 0xBFFFFFFF (3/4) 까지 user space, 0xC0000000 ~ 0xFFFFFFFF (1/4) 까지 kernel's virtual address space이다.
• kernel virtual address space는 두 가지 종류로 나누어진다.
  • kernel logical address
    • kmalloc()을 이용해 추가 메모리를 할당
    • 대부분의 kernel data structures (page table, per-process kernel stacks 등) 이 존재
    • swap-out to disk 불가능
    • contiguous in physical memory이므로 I/O transfer 시 direct memory access (DMA) 등이 가능함
  • kernel virtual address
    • vmalloc()을 이용해 추가 메메뢰 할당
    • contiguous 하지 않고, virtual page는 임의의 physcial frame에 매핑 될 수 있음
    • large buffer 같은거에 쓰기 좋음 (allocation이 비교적 contiguous 한 logical space에 비해 쉽기 때문)

Page Table Structure

 x86은 hardware-managed, multi-level page table structure를 가지고 있다. 그래서 특정 "privileged register"을 page directory를 가르키게 설정해두면 hardware가 알아서 page table을 다룬다. 물론, OS가 context switch 등을 할 때는, process creation, deletion에 관여하고 context switch 시 이 register를 올바른 page table을 가르키도록 잘 설정해주어야 한다.

 최근에 더 큰 사이즈의 address space가 필요해지면서 64bit x86에서는 64bit address space를 사용한다. 실제로는 위의 16bit는 안쓰이고 48bit를 이용해서 address space를 구성한다. 이때 아래 그림에 나타나듯, 64bit 시스템에선 four-level page table을 사용한다. 12bit의 offset, 그리고 각 9bit로 나누어 구성된다.

 

 

 

 

Page Cache

대부분의 시스템들은 persistent storage로 부터 오는 cost들을 줄이기 위해 page cache를 사용한다.

Linux의 page cache는 세 가지 소스로 부터온 page들을 memory에 담으려고 한다.

• memory-mapped files
• file data, metadata from devices (보통 read(), write() call들을 file system으로 넘기면서 액세스된다.)
• anonymous memory (heap, stack 등 process를 이루는 page들에는 딱히 파일이 아니라 swap space와 매핑되므로)

이 entity들은 page cache hash table을 이용해서 관리되며, disk access를 할 때 page cache에 이미 있는 경우 이것을 이용해서 page cache에서 data를 받아온다.

 

• page cache는 entry들이 clean/dirty한지를 트래킹한다.
  • dirty data는 주기적으로 pdflush (background threads)를 이용해서 storage에 작성된다.
• page cache 또한 용량 제한이 있으므로 replacement algorithm이 필요하다.
  • 2Q replacement
    • inactive list, active list 리스트로 page를 나누어 관리한다.
    • 처음으로 access 된 page는 inactive list에 추가된다.
    • 만약 re-reference 된 경우 page는 active list로 승격된다.
    • replacement가 필요한 경우, inactive list에서 page 하나를 evict한다.
    • 또한, 주기적으로 active list에 bottom에 위치한 page들을 inactive list로 보낸다
  • 이 list들을 LRU로 관리하면 좋지만, 그러면 costly하므로 clock algorithm과 비슷한 approximation을 사용한다.