Intro
Virtual Machine에 대한 개념은 옛날부터 나와있었지만, 필요성을 느끼지 못해서 practical하게는 잘 사용하지 않았다고 한다.
수십, 수백개의 processor가 있는 scalable computer가 상용화되고 나서는 상황이 달라졌는데, 하드웨어는 빠르게 발전하는데 비해 이를 위한 system software는 하드웨어가 기대하는 기능과 안정성에 도달하지 못한다는 것이었다. scalable system을 효율적으로 지원하기 위해서는 OS에 많은 수정이 필요하다. 그런데 최신 OS의 크기와 복잡성으로 인해 바꿀 양이 상당하기 때문에 수정이 어렵다는 것이다.
본 논문에서는 OS를 바꾸기보단, 하드웨어와 OS 사이에 Disco라는 새로운 SW layer를 추가하는 것을 제안한다. 이 layer는 상용 OS의 여러 복사본을 single scalable comupter에서 실행할 수 있는 기존의 VMM (Virtual Machine Monitor)처럼 동작한다. 이 monitor를 통해 각 VM은 서로 cooperate하고 자원을 공유할 수 있으며 OS에 많은 수정이 필요하지도 않다.
Contribution
scalable multiprocessor를 위한 system software 제공 문제를 해결
- 큰 구현 overhead 없이 OS를 large-scale shared memory 멀티프로세서에서 실행하도록 함
- monitor의 오버헤드가 작고, non-uniform memory access에 대한 scalability를 제공
- memory overhead를 더 줄이기 위해 virtual machine이 coe, buffer cache 등 주요 데이터 구조를 transparent하게 공유하는 기술을 개발함.
Problem Description
scalable shared memory multiprocessor에 대해 하드웨어는 계속 발전하는데, system software를 이에 맞추려면
- 시스템을 scalable하게 partitioning
- unit 전체에 단일 system image를 구축
- 오류 억제, ccNUMA 관리
등 OS 변경이 많이 필요하다.
ccNUMA의 적용에 대한 문제는 구체적으로 아래와 같은 것들이 있다.
- non-uniform memory access : 일반 OS는 memory가 uniform하다고 가정
- processor 수 증가에 따른 lock contention 증가
- fault를 isolate하지 못함 : 문제가 생기면 모든 시스템 망가짐
- cache-coherence해야 함.
VM 개요
일반적인 OS는 OS 내의 register에 있는 주소로 jump해서 해당 code를 수행하고 return되면 context switch해서 다른 코드를 수행한다. 즉 CPU가 돌기 위해서는 kernel code, data가 memory에 있고 해당 code를 실행하기만 하면 된다.
따라서 VM은 register를 통해 machine의 bios 코드, boot 코드로 jump해서 실행하게 하는 것이다. 실제 OS 입장에서는 thread 하나가 도는 것이지만, thread 내의 register가 VM의 process들을 interleaving한다.
[장점]
- 각 VM에 대해 강한 isolation 가능
- software compatibility : 옛날 OS에서만 동작하는 app도 VM과 옛날 OS를 올려서 실행 가능
- logical partitioning, server consolidation
- OS debugging의 편의성
- security
[단점]
physical machine보다 성능이 안 좋다
Return to Virtual Machine Monitor
위 문제를 해결하기 위해 VMM 개념을 가져와서 hardware와 OS 사이에 추가적인 SW layer를 삽입한다. machine의 모든 자원을 가상화하여 general한 HW interface를 OS로 보내며, 여러 VM이 동일한 multiprocessor에 있을 수 있도록 모든 자원을 관리한다.
VMM은 범용, 특수 OS와 machine을 위한 system software solution을 제공한다. 모니터는 간단한 code이므로 구현을 위한 effort나 버그, 비호환성 위험이 적다.
[flexibility]
- 상용 OS
- application이 VM의 경계를 넘어 memory 영역을 명시적으로 공유
- 여러 VM에서 실행되는 프로세스가 memory를 공유할 수 있도록 special virtual memory segment driver로 확장
- 특수 OS (상용 OS의 전체 기능을 필요로 하지 않는 경우)
- VM을 사용하여 machine의 크기로 application을 확장할 수 있음.
- VM에서 실행되기 때문에 다른 상용 OS와 함께 실행할 수 있음.
[ccNUMA machine의 문제 해결]
- scalability : VM이 확장성의 단위가 되므로 모니터와 분산 시스템 프로토콜만 system 크기에 맞춰서 확장하면 됨. 모니터가 단순하므로 OS를 아예 확장하는 것보다 작업이 더 쉽다.
- fault containment : 각 machine이 cell로 구성되므로 HW error가 있을 때에도 전체 OS를 보호하는 것보다 더 쉽다. system SW의 fault가 전체 machine에 퍼지지 않도록 한다.
- NUMA memory 관리 문제 : monitor에서 처리 가능하다. VM memory의 적절한 배치, 동적 page migration, page replication을 통해 memory에 대한 일반적인 view를 UMA machine으로 export할 수 있다. 따라서 NUMA를 인식하지 못하는 OS에서도 NUMA를 사용할 수 있다.
[기존 VMM의 장점을 상속]
단일 ccNUMA multiprocessor에서 동시에 여러 OS를 실행 가능
- software compatibility : system SW의 이전 버전을 유지하여 application을 실행하기 위한 안정적인 플랫폼 제공 가능
Virtual Machine이 가진 문제
[overhead]
하드웨어 가상화에 필요한 추가 exception 처리, instruction 실행, memory
- time overhead
- privileged instruction은 OS로 직접 내보낼 수 없으며 monitor에서 SW로 emulate해야 한다.
- IO 장치에 대한 access가 가상화되므로 monitor에서 remapping해야 한다.
- memory overhead
- 각 OS와 application의 code, data가 각 VM의 memory에 복제
- file system buffer cache 등 대용량 메모리도 복제되어 메모리 사용량이 증가
[자원 관리]
정보가 부족해서 resource 관리 정책을 잘 못 내릴 수도 있음
- 모니터는 OS의 idle loop의 busy-waiting을 몇 개의 중요한 계산 instruction과 구분할 수 없다.
→ 불필요한 계산을 위해 자원 할당 가능 - page가 VM에서 active하게 사용되지 않을 때를 알지 못함.
→ 다른 VM에 page를 reallocate할 수 없음
[communication, sharing]
- VM/370의 CMS에서 user file이 포함된 가상 disk가 VM에서 사용 중이면 다른 VM에서 access 불가능함.
- 동일한 사용자가 두 개의 가상 머신을 시작할 수 없음
- VM 간 파일의 공유가 어려움.
최신 OS에서의 support에 의해 이 통신, 공유 문제는 많이 줄어들었음
Disco : A Virtual Machine Monitor
[Processor]
- FLASH 머신과 일치시키기 위해 MIPS R10000 프로세서의 abstraction 제공
→ 모든 instruction, memory 관리 장치, trap architecture를 emulate하여 기존의 app과 OS를 수정 없이 실행할 수 있음 - 일부 프로세서 기능에 대한 효율적인 access를 지원
- CPU interrupt의 활성화 및 비활성화
- privileged register에 대한 접근
→ 이러한 빈번한 kernel 작업을 special address에 대한 load, store 명령으로 수행하여 trap emulation으로 인해 발생하는 overhead를 줄일 수 있음
[Physical Memory]
- 0으로 시작하는 연속된 physical address space의 abstraction을 제공
- 동적 page migration, replication으로 NUMA에 대해서도 거의 균일한 memory access time을 가진 메모리 구조를 SW에 제공
→ NUMA를 인식할 수 없는 OS도 FLASH에서 실행 가능
[IO Device]
각 VM은 disk, network interface, interrupt timer, clock, console 등 정해진 IO 장치로 구성된다. 대부분의 OS는 IO 장치의 exclusive access를 가정하므로 각 IO 장치를 가상화해야 한다. 따라서 IO 장치로의 operation을 translate하고 emulate해야 한다.
network device의 경우에도 기본 system의 networking 장치에 대한 access를 가상화, 각 VM에 내부 virtual subnet의 고유한 주소가 할당된다.
Implementation of Disco
multi-threaded shared memory program에서 구현했다. NUMA 메모리 배치, cache-aware 자료구조, processor 간 통신 패턴에 주의를 기울였다는 점에서 기존 시스템과 다르다.
linked list 등 cache behavior가 안 좋은 자료구조가 없다.
NUMA locality의 향상을 위해 72KB의 Disco code segement가 FLASH 머신의 모든 메모리에 복제된다. 대부분 shared memory를 이용해 통신하며 특정 작업에만 IPI를 사용. (TLB shootdown, virtual CPU에 대한 interrupt)
[Virtual CPUs]
-
virtual CPU를 스케줄하기 위해서는, 실제 machine의 register를 virtual CPU로 설정하고, virtual CPU의 현재 PC로 jump함.
→ 직접 실행하므로 그냥 하드웨어와 동일한 속도로 실행됨. -
supervisor mode에서 issue할 수 없는 operation은 따로 emulate함
(ex : TLB 수정 등 OS에서 수행하는 privileged instruction, physical memory나 IO device에 대한 direct access) -
virtual processor에 대해 간단하게 time-share함.
-
각 virtual CPU에 대해 유지하는 자료구조
- 기존 OS의 process table entry와 같은 자료 구조 (saved register, other state of virtual CPU)
- privileged instruction의 emulation을 위해 virtual CPU의 privileged register와 TLB 내용을 추가적으로 가짐.
-
virtual processor가 실제 processor에 time-sharing될 수 있도록 하는 간단한 스케줄러도 포함함. affinity도 지원해서 locality도 향상 가능
-
operating mode
MIPS에서 Disco는 시스템 하드웨어에 대한 모든 권한이 있는 kernel mode로 실행. 가상 머신의 OS는 supervisor mode로, 그냥 application은 user mode로 설정함.
supervisor mode에 의해 OS는 address space의 protected 영역을 사용할 수 있지만 privileged instruction이나 physical memory의 access는 허용하지 않음.
Disco는 kernel mode라서 page fault, system call, bus error 등의 trap에 대해 emulate할 수 있음. virtual processor의 privileged register를 update하여 virtual machine의 trap vector로 jump해서 수행함.
[Virtual Physical Memory]
physical memory의 가상화를 위해, Disco에는 physical-to-machine address mapping이 추가됨. VM은 주소 0에서 시작하여 메모리 크기만큼 연속된 물리적 주소를 사용할 수 있다.
MIPS 프로세서의 software-reloaded TLB를 사용하여 physical-to-machine translation을 수행. OS가 virtual-to-physical mapping을 TLB에 넣으려고 하면, Disco가 이 physical address를 machine address로 변환하여 삽입하는 것을 emulate함. TLB entry가 있으면 추가 overhead 없이 바로 변환 가능
- pmap 자료 구조
- VM의 각 physical page마다 있다.
- 미리 계산된 TLB entry를 저장하여 TLB entry를 빠르게 계산
- virtual address에 대한 back map (VM에서 page를 없앨 때 TLB mapping을 invalidate하기 위해)
- kernel mode reference
user mode memory 참조는 TLB에 의해 변환되지만, kernel mode reference는 kernel virtual address space의 mapping되지 않은 segment를 통해 physical memory와 IO device에 직접 access 가능함. 일반적으로 OS는 OS code, data를 이 segment에 배치한다.
따라서 Disco가 TLB로 이 주소를 mapping할 수 없으므로 OS code, data를 address space의 mapping된 영역에 re-link함.
- ASID (address Space ID)
MIPS는 MMU context switch에서 TLB flush를 막기 위해 ASID 존재. ASID 가상화는 너무 복잡해지므로 다른 virtual CPU를 예약할 때 system의 TLB를 flush한다. 따라서 원래 VM에서 사용하는 ASID를 그대로 쓸 수 있음
- Second-level TLB
모든 OS에 대해 TLB를 공유하고 virtual CPU switch에 대해 flush하므로 TLB miss가 증가한다. TLB miss는 trap의 emulate, physical address의 re-mapping으로 인해 더 cost가 높다.
따라서 second-level SW TLB를 만들어 최근의 virtual-machine translation을 cache한다. TLB miss 시 먼저 이 second-level TLB를 먼저 참조한다. 따라서 MIPS보다 더 큰 TLB를 가지는 것처럼 가상화할 수 있다.
[NUMA Memory 관리]
Disco는 VM에 대한 빠른 주소 변환 뿐만 아니라, 실제 메모리 할당도 처리해야 함. ccNUMA는 memory access time이 불균일하기 때문에 Disco가 이를 관리해야 함. 즉, remote cache miss에 의한 추가 latency를 방지해야 함. 따라서 cache miss가 발생한 virtual CPU와 memory page 사이의 locality를 위해 동적 page migration, replication system을 구현
- migration : 한 node에 의해서만 많이 사용되면 이동
- replication : read-shared가 여러 node에서 많이 사용되면 복제
Policy
- 진짜 성능의 개선을 일으킬 수 있는 page만 이동하는 robust policy 사용.
- read-shared page들은 가장 많이 access하는 node에 복제된다.
- write-shared page는 이동, 복제에 의미가 없어서 이동하지 않는다.
- 과도한 overhead를 피하기 위해 이동 횟수를 제한
FLASH 하드웨어 support
FLASH 하드웨어는 cache miss counting 기능을 제공하여 모든 physical processor에서 각 page에 대한 cache miss를 계산한다. 따라서 hot page 감지 시 cache miss counter를 기반으로 이동, 복제 중 선택한다.
- page migration 과정
- physical-machine mapping을 transparent하게 변경
- 이전 machine page를 mapping하는 모든 TLB를 invalidate
- data를 local machine page에 복사
- page replication 과정
- machine page를 mapping하는 모든 TLB를 downgrade하여 read-only access를 보장
- page를 local node에 복사
- 이전 machine page를 mapping하는 TLB entry를 update
- memmap 자료 구조
- machine page의 entry를 포함
- page migration, replication에 필요한 TLB shootdown을 위해 page를 사용하는 VM 목록과 access하는데 사용되는 VA를 포함. 복사본에 대한 pointer도 포함
[Virtual IO device]
IO device access를 가상화하기 위해 모든 device access를 intercept하여 physical device로 전달함. OS의 device driver의 PIO에 개입할 수도 있으나, 단순히 special device driver를 추가하는 것이 더 깔끔함. Disco 장치는 device driver가 single trap에서 모든 argument를 전달할 수 있도록 하는 monitor call을 정의한다.
- DMA
disk, network interface의 경우 일부 argument에 DMA map이 포함됨. 이 경우 Disco가 OS에서 지정한 PA를 실제 system address로 변환. access의 독점성을 보장하기 때문에 IO resource 자체를 가상화할 필요는 없음
[Copy-on-Write Disk]
read-only page를 DMA의 destination address page에 매핑. 공유 page를 수정하려고 하면 monitor에서 내부적으로 copy-on-write fault가 발생한다.
공유 disk에 access하는 여러 VM이 machine memory를 공유 (모든 VM이 kernel과 application이 포함된 동일한 root disk를 공유함)
disk에 저장된 code 및 read-only data가 첫번째 VM에 의해 memory도 DMA되면 이후의 request는 data를 전송하지 않고 DMA에 있는 page를 단순 mapping함.
→ single shared memory multiprocessor operating system의 memory 공유 패턴처럼 나타남.
[Virtual Network Interface]
CoW disk를 사용하면 memory 자원의 공유는 가능하지만 서로 통신은 불가능함. 통신을 위해 표준 분산 프로토콜을 사용한다.
- NFS를 통해 파일 공유 : 공유 data가 client와 server의 buffer cache 모두에 저장됨. 이 data가 machine memory에 복제될 수 있기 때문에 이를 막기 위해 가상 subnet, network interface을 설계함.
- Copy-on-Write mapping
- CoW mapping을 통해 복사량을 줄이고 메모리 공유를 허용함.
- VM 간 메시지 전송을 하면 보내는 machine과 수신하는 machine의 physical address space 모두에 DMA가 page를 mapping한다.
한 VM에서 실행중인 file server의 file cache로 읽은 data page를 NFS 등으로 file을 요청하는 client와 공유할 수 있음. global disk cache를 지원하여 모든 VM에 대해 transparent하게 공유됨.
c.f.) server, client 통신 과정
- send buffer가 가리키는 machine page를 receive buffer도 mapping함.
- receive buffer가 mapping된 machine page를 client의 buffer cache도 mapping함.
모든 read-only page가 VM 간에 공유될 수 있다. 이 메커니즘은 memory footprint를 줄일 수는 있지만, 많은 sharer가 원격 access를 하기 때문에 locality가 떨어질 수 있다. 하지만, page 복제 정책이 있어서 이를 완화해준다.
상용 OS의 실행
상용 OS의 실행을 위한 변경사항을 명시한다.
[MIPS architecture의 변경사항]
supervisor mode에서 실행되는 virtual processor의 virtual address space의 KSEG0는 TLB를 우회하기 때문에 효율적으로 access할 수 없다. 일반적으로 MIPS는 kernel code와 data를 KSEG0 segment에 배치하므로, VM의 mapping되지 않은 segment를 MIPS의 supervisor segment의 일부로 re-mapping해야 한다. 이를 통해 TLB로 모든 DMA를 효율적으로 access할 수 있다.
[Device Drivers]
monitor call interface : IO device access의 복잡성과 overhead를 줄임
[HAL 변경 사항]
모든 privileged register access에 대해 trap을 수행하면 overhead가 크다.
- 자주 사용되는 privileged instruction을 non-trapping load, store로 변환하여 address space의 special page를 사용하도록 변환했다.
- resource 관리 정책에 대한 hint를 monitor에 전달하여 resource usage에 대한 high-level 지식을 전달했다.
- OS의 메모리 관리 모듈에 일부 monitor call을 삽입함. (1번째 monitor call은 zero page를 요청하고, 2번째 monitor call은 page가 OS의 사용가능 목록에 추가되었음을 알림)
- processor utilization을 높이기 위해 절전 모드에 semantic을 할당함. 시스템이 idle일 때, Disco는 interrupt가 있거나 mode가 지워질때까지 virtual CPU를 스케줄하지 않는다. HAL의 idle loop에 삽입된 monitor call도 동일한 효과를 가짐
Evaluation
- 가상화 overhead는 3%~16%로 나타남
- OS의 일부 작업을 모니터에서 직접 처리하므로, kernel 시간은 줄어듬.
- kernel text (code), buffer cache를 효과적으로 공유하여 memory overhead가 일정 이상 늘어나지 않음.
- VM이 늘어날 수록 scalability 이점이 커짐. kernel stall 시간과 동기화 시간이 감소하기 때문
- NFS를 사용하더라도 NFS protocol에 의한 overhead와 idle time 증가에도 기존 IRIX보다 빠르게 실행됨.
- Dynamic Page Migration and Replication에 의해 Disco의 overhead가 약간만 증가하면서 local memory의 cache miss를 줄이고 원격 지연시간도 감소됨.
Reference
- Bugnion, E., Devine, S., Govil, K., & Rosenblum, M. (1997). Disco: Running commodity operating systems on scalable multiprocessors. ACM Transactions on Computer Systems (TOCS), 15(4), 412-447.
