Advanced Operating Systems Structure(4): L3 Microkernel

개요

이전 포스트에서는 SPIN, Exokernel이 u-kernel의 문제를 해결하는 OS 구조로 소개했다. 이번 포스트에서는 u-kernel에 대해서 다시 알아보려고 한다. 이 구조는 본질적으로 확장성 및 이식성이 좋은 구조이기 때문에 낮은 성능을 가진다는 생각을 갖게 한다. 이 번 포스트에서는 u-kernel 구조를 유지하고 성능도 유지할 수 있는 L3 u-kernel에 대해서 알아보자

잠재적 성능 손실

먼저 u-kernel이 가지는 성능 문제를 보자. 먼저 Border crossing 이슈가 있다. 각 service들은 각자의 address space를 가지고 있고, privilege level이 다르기 때문에 context switch, data copy 등 고정적인 비용이 들어가고, cache locality 이슈 등 암시적인 비용이 같이 들어간다.

OS service 내부에서도 PPC(Protected Procedure Call)들은 일반적인 Procedure Call보다 100배 이상의 비용이 소모된다.

L3 microkernel

L3 u-kernel은 위의 잠재적인 성능 손실에 대한 부분을 증명을 통해서 u-kernel은 성능이 낮다는 미신을 없애려고한다.

L3 microkernel은 Address Space, Threads, IPC, UID 등에 대한 최소 셋의 abstraction을 제공한다. 이 전 슬라이드에서 봤듯이 각 u-kernel OS 시스템들은 각자의 hardware address space를 가지고 있다. L3 u-kernel이 구분되는 점은 각 시스템들이 hardware address space로 구분될 필요 없이 Protection Domain로 구분되고 하드웨어 플랫폼에 대해 알고 있는 것이다. L3 u-kernel은 u-kernel의 구조적인 원칙이 아니라 효율적인 구현 방법에 대한 것이다.

microkernel에 대한 의혹

먼저 microkernel에서 문제가 될만한 부분을 알아보자. 보통 Explicit Cost, 직접적으로 성능 저하를 시키는 비용과, Implicit Cost, 간접적으로 성능을 저하시키는 비용이 있다.

Explicit Cost

• kernel-user switches: border crossing cost
• address space switches: Protection Domain을 밖의 기능을 사용하기 위한 PPC
• thread switches + IPC: 커널이 PPC에 대한 중재 역할을 해야 한다.

Implicit Cost

• memory effect: cache locality 손실

위와 같은 문제를 L3 u-kernel은 어떻게 풀어가는 지를 지금부터 설명하겠다. 먼저 kernel-user switches 문제부터 알아보자

Kernel-User Switches

이 부분은 경험적인 증명을 통해서 밝혀냈다. L3 u-kernel은 kernel-user switching 하는데 123 cycle만에 했다(TLB와 cache miss까지 포함한 것이다). processor 자체의 kernel-user switch만 계산했을 때 107 cycle만에 처리했다. 이것으로 u-kernel 베이스 OS가 kernel-user switch 비용이 많이 든다는 미신을 아니라는 결론이다.

이와 비슷하게 CMU에서 만든 Mach OS의 경우 u-kernel 처럼 확장성에 중심을 뒀지만 900 cycle이나 걸렸다. Mach OS 같은 경우 확장성 뿐만 아니라 Potability까지 고려해서 추가적인 작업들에 의해서 더 많은 cycle을 소모했다.

Address Space Switches

Address Space Switch 할 때 TLB를 Flush 해야 되나? 를 먼저 생각해보자. 결론부터 말하자면 경우에 따라 다르다. MIPS 아키텍처의 경우에는 address space tag가 있어서 flush하지 않고, intel pentium 같은 경우는 address space tag가 없어서 flush 한다.

Address Space Tag

Address Space Tag를 설명하기 전에 TLB의 동작 원리부터 잠깐 살펴보자

프로세스가 메모리에 접근할 때는 memory menagement system에서 제공한 VPN(Virtual Page Number)를 가지고 을 TLB를 통해서 PFN(Physical Frame Number)로 변환해서 실제 hardware memory에 접근한다.

VPN는 tag와 index로 구성되어있다. 먼저 index를 가지고 TLB entry line을 찾는다. 그리고 tag와 TLB entry와 같으면 hit 시키고 PFN를 통해 메모리 접근을 하고, 아니면 Page fault를 일으킨다.

가상 메모리의 경우는 프로세스마다 같은 index를 가질 확률이 높기 때문에 TLB를 flush하지 않으면 page fault가 날 확률이 높다. 그래서 프로세스 ID를 AS tag로 쓰게 TLB를 확장해서 사용한다.

원리는 기존 방식처럼 tag 매치와 AS tag 매치를 해서 두 결과가 모두 같을 때, hit를 시킨다. 이 방법이 가지는 장점은 context switch가 일어날 때 프로세스별 TLB entry를 구별할 수 있기 때문에 TLB를 flush하지 않아도 되는 장점이 있다.

하지만 이러한 AS-tagged TLB를 모든 프로세서가 지원하는 것은 아니기 때문에 이 방법이 최고의 설루션은 될 수 없다. L3 u-kernel의 저자인 Liedtke는 TLB flush를 피하기 위해서 H/W가 지원하는 기능을 최대한 이용하라고 한다. 에를 들어서 x86 or PowerPC의 segment register가 있다.

Segment Register

segment register는 virtual address space를 range 단위로 지정할 수 있다. 그래서 nbits 컴퓨터의 HW 주소 공간을 segment로 잘라서 하나의 주소 공간을 각 Domain이 나눠서 사용하게 된다. 이러면 PFN이 출동하지 않기 때문에 TLB를 flush하지 않아도 된다. 하지만 Protection Domain이 클 경우는 이러한 방식으로 해결되지 않는다.

Large Protection Domain

File System이나 Storage System 같은 경우 큰 주소공간을 사용하게 된다. 이럴 경우 segment register 방식은 사용할 수 없다. 하지만 Large Protection Domain은 explicit cost에 대해서 고려하지 않아도 된다. 왜냐하면 locality issue에 비하면 explicit cost는 매우 작기 때문이다.

정리하면, Small Protection Domain의 경우에는 AS-TLB, segment register 등 최대한 하드웨어 자원을 이용해서 효율적으로 만들고, Large Protection Domain의 경우는 cache locality 이슈가 TLB 이슈에 비해 너무 커서 switch cost는 별로 중요하지 않는다.

Thread Switches and IPC

Explicit cost에 대해서만 얘기하고 있기 때문에 context switch가 일어나면 CPU의 volatile data에 대해서 저장하고, Thread Context Block에 저장하는 부분은 SPIN or Exokernel과 다를 바가 없다.

Memory Effect

컴퓨터 구조에서 메모리는 계층적으로 구성되어있다. L1~L3 cache, main memory, virtual memory 등으로 구성되어있는데. L1 cache는 매우 작다. u-kernel에 대해 Protection Domain 전환될 때 cache pollution 생긴다고 생각한다. 하지만 Protection Domain의 working set이 충분히 작다면 각 Protection Domain마다 HW 주소 공간을 할당하지 말고, 여러 Protection Domain을 묶어서 하나의 패키지로 HW 주소 공간에 할당하면 context switch가 일어나더라도 cache locality를 유지할 수 있다.

그렇다면 Large Protection Domain일 경우는 어떻게 하냐? 이 건 이전에 설명했던 Monolithic, SPIN, Excokernel 등 어떤 구조를 가져와도 해결할 수 없다. 어차피 발생하게 되어있는 것이다.

정리

지금까지 OS Structure들, Monolithic, SPIN, Exoknel, u-kernel에 대해서 알아봤다. 현대의 대부분의 OS는 내부적으로 u-kernel 기반 설계로 되어있다. 커널 모듈을 동적으로 로딩하는 것처럼 말이다.

다음 OS 관련 포스트는 Virtualization에 대해서 다뤄 볼 것이다.