Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

완전한 가상 메모리 시스템 실현을 위해 필요한 기능에는 어떤 것들이 있을까?
이 기능들은 어떻게 성능을 향상시키고, 보안성을 높이고, 시스템을 개선할까?

두 종류의 시스템을 예시로, 가상 메모리 시스템이 어떻게 실현되고 있는지를 살펴보도록 하자. 첫 번째는 현대 가상 메모리 관리 시스템의 조상이라 할 수 있는 VAX/VMS이고, 두 번째는 리눅스다.

1. VAX/VMS 가상 메모리

VAX/VMS 미니컴퓨터 구조는 1970년대에서 1980년대 초에 개발됐다. 여기서 사용했던 많은 테크닉 및 접근법들은 오늘날에도 쓰이고 있다.

VAX-11 미니컴퓨터 아키텍처는 1970년대 후반에 DEC에 의해 도입되었다. 이 시스템의 OS는 VAX/VMS라 알려져있는데, VMS는 다양한 종류의 기계들(아주 값싼 VAX부터 하이엔드의 고사양 기계까지)에서 실행되어야 했고, 따라서 OS는 이렇게 넓은 범위에서 모두 잘 작동하기 위한 메커니즘과 정책들을 필요로 했다.

VMS는 아키텍처의 내재적 단점들을 숨기는 소프트웨어 혁신의 훌륭한 예이기도 하다. OS는 효율적인 추상화를 위해 하드웨어에 의존하지만, 하드웨어 디자이너들이 항상 하드웨어를 훌륭하게만 만드는 것은 아니다. VMS 운영체제가 어떻게 VAX 하드웨어의 결함들을 극복하고 효과적으로 동작하는 시스템을 만들 수 있었는지 알아보자.

Memory Management Hardware

VAX-11은 프로세스 별로 512 바이트의 페이지로 나뉘는, 32비트 가상 주소 공간을 제공한다. 따라서 가상 주소는 23 비트의 VPN와 9비트의 오프셋으로 이루어져있다. VPN의 상위 2비트는 페이지가 들어있는 세그먼트를 구분하기 위해 사용되며, 시스템은 페이징과 세그먼테이션 하이브리드 구조를 가진다.

주소 공간의 하위 절반은 각 프로세스에 할당되는 프로세스 공간(process space)이다. 프로세스 공간의 첫 절반($P0$)은 유저 프로그램과 아래로 자라는 힙이 있고, 나머지 반($P1$)에는 위로 자라는 스택이 있다. 주소 공간의 상위 절반은 시스템 공간($S$)인데, 실제로 사용되는 것은 이 중에서도 절반이다. OS의 보호 코드와 데이터가 이 안에 들어가 있고, 이를 통해 프로세스들은 OS를 공유한다.

VMS 디자이너들의 주요 고민 중 하나는 VAX 하드웨어의 페이지 사이즈가 너무 작다는 것이다. 이렇게 페이지 사이즈가 작을 때 생기는 문제점 중 하나는 페이지 테이블이 너무 커진다는 것이다. VMS 디자이너들의 첫 번째 목표는 페이지 테이블들로 메모리가 소진되는 일이 일어나지 않도록 보장하는 것이었다. 이 시스템에서는 페이지 테이블로 인한 메모리 압력을 두 가지 방법으로 줄인다.

1. 유저 주소 공간을 두 개의 세그먼트로 나누고, 각 영역에 대한 페이지 테이블을 만든다. 스택과 힙이 각각의 방향으로만 자라므로, 그 사이의 사용되지 않는 공간은 페이지 테이블에 추가할 필요가 없다. 이때 베이스 레지스터는 해당 세그먼트의 페이지 테이블의 주소를 가지고, 바운드는 그 사이즈를 가진다.
2. OS는 유저 페이지 테이블을 커널의 가상 메모리에 배치해 메모리 압력을 더 줄인다. 페이지 테이블을 할당하거나 그 크기를 키울 때, 커널은 자신의 세그먼트 $S$의 가상 메모리에서 공간을 할당한다. 만약 메모리 압력이 커지면, 커널은 이 페이지 테이블들의 페이지들을 디스크로 스왑 아웃함으로써 물리 메모리를 다른 용도로 사용할 수 있게 한다.

페이지 테이블들을 커널 가상 메모리에 두면 주소 변환은 더 복잡해진다. 예를 들어 $P0$, $P1$에 있는 가상 주소를 변환하려면 하드웨어는 우선 페이지 테이블에서 해당 페이지의 PTE를 찾아야 한다. 그런데 이 때, 하드웨어는 먼저 시스템 페이지 테이블을 찾아야 할 수도 있다. 변환이 완료되면 하드웨어는 페이지 테이블 페이지의 주소에 대헤 알게 되고, 최종적으로는 원하던 메모리 접근의 주소에 대해서도 알게 된다. 이 모든 과정은 VAX의 하드웨어로 관리되는 TLB로 빠르게 처리된다.

A Real Address Space

지금까지는 유저 코드, 데이터, 힙만을 위한 간단한 주소 공간을 가정했지만, 실제 주소 공간은 훨씬 더 복잡하다.

1. 코드 세그먼트는 절대 page 0에서 시작하지 않는다. 이 페이지는 널-포인터 접근 탐지를 위해 접근 불가능한 것으로 마크되기 때문이다. 주소 공간을 설계할 때는 효과적인 디버깅을 지원할 수 있어야 하고, 접근 불가능한 페이지 0이 그런 기능을 제공한다.

2. 커널 가상 주소 공간은 각 유저 주소 공간의 부분이다. 문맥 전환이 일어날 때 OS는 $P0$, $P1$ 레지스터를 곧 실행될 프로세스의 적절한 페이지 테이블들을 가리킬 수 있도록 바꾸지만, $S$의 베이스-바운드 레지스터 쌍이 바뀌지는 않는다. 결과적으로는 같은 커널 구조가 각 유저 주소 공간에 매핑된다.

3. 커널이 각 유저 주소 공간의 부분으로 매핑되는 구조에서 커널의 동작은 간단해진다. 예를 들어 OS는 유저 프로그램으로부터 포인터를 건네 받아, 간단하게 그 포인터가 가리키는 데이터를 자신의 구조로 복사할 수 있다.

   반대로 커널이 유저 주소 공간에 매핑되지 않고 순수하게 물리 메모리에만 위치해있는 경우, 페이지 테이블의 페이지들을 디스크로 스왑 아웃하는 일이나, 유저 프로세스와 커널 간의 데이터 이동은 더 복잡해졌을 것이다. 커널을 유저 주소 공간에 매핑하는 구조를 통해, 커널은 실제로는 보호 영역이지만 응용 프로그램에게는 라이브러리와 같이 쓰일 수 있게 된다.

4. OS는 유저 응용 프로그램이 OS의 데이터나 코드를 쓰거나 읽기를 원하지 않는다. 이를 위해 하드웨어는 각 페이지에 다른 보호 레벨을 설정할 수 있어야 하는데, VAX는 페이지 테이블의 보호 비트에 해당 페이지에 접근하기 위해 필요한 CPU 특권 레벨을 명시한다. 시스템 데이터와 코드는 유저 데이터와 코드보다 높은 보호 레벨을 가지며, 만약 유저 코드에서 이 정보들에 접근하려 하면 OS에 트랩이 발생되어 보통은 해당 프로세스를 종료시키게 된다.

Page Replacement

VAX의 PTE는 다음의 비트들을 포함한다.

• valid bit
• protection bit
• dirty bit
• filed reserved for OS use
• PFN.

여기서 우리는 VAX의 PTE에는 참조 비트가 없음을 알 수 있다. VMS의 교체 알고리즘은 하드웨어의 지원 없이도 어떤 페이지가 자주 사용되고 있는지를 파악할 수 있어야 한다.

개발자들은 많은 메모리를 써서 다른 프로그램들이 실행되기 어렵게 만드는 프로그램, 메모리 호그(memory hog)에 대해서도 신경을 써야 한다. 지금까지 다룬 대부분의 정책들은 이런 메모리 호깅에 취약하다.

Segmented FIFO

위의 두 문제들을 해결하기 위해 해결책이 세그먼트화 된 FIFO(segmented FIFO)다.

각 프로세스는 상주 집합 크기(resident sert size, RSS, 해당 프로세스가 메모리에서 가질 수 있는 페이지의 최대 수)를 가지고 있고, 각 페이지들은 FIFO 리스트에 담겨 있다. 만약 프로세스가 자신의 RSS를 초과하게 되면 가장 먼저 들어간 페이지는 디스크로 쫓겨나게 된다. FIFO는 하드웨어의 지원을 필요로 하지 않아 구현하기 쉽다.

하지만 순수한 FIFO는 잘 작동하지 않는다. VMS는 FIFO의 성능을 높이기 위해 전역 클린-페이지 프리 리스트(clean-page free list)와 더티-페이지 리스트(dirty-page list)라는, 두 개의 second-chance list들을 이용한다.

이 second-chance list는 페이지들이 메모리로부터 쫓겨나기 전에 위치하는 곳으로, 프로세스 $P$가 RSS를 초과할 때 해당 프로세스의 FIFO에서 삭제된 페이지가 위치하게 되는 곳이다. 해당 페이지는, 만약 수정이 된 적이 없다면 클린-페이지 리스트의 끝에 추가되고, 반대의 경우라면 더티-페이지 리스트의 끝에 추가된다.

어떤 다른 프로세스 $Q$가 가용 페이지를 원한다면 클린 리스트의 첫 번째 페이지를 가져오면 된다. 원래 프로세스 $P$가 어떤 페이지에 폴트를 일으킬 때에는 해당 페이지를 클린-리스트나 더티-리스트에서 다시 가져오면 된다. 이렇게 하면 비용이 높은 디스크 접근을 피할 수 있게 되고, 이 전역 second-chance list가 커질 수록 세그먼트화된 FIFO 알고리즘은 LRU와 같이 동작하게 된다.

Clustering

VMS의 작은 페이지 사이즈를 극복하기 위한 다른 최적화 기법도 있다. 페이지가 작으면 페이지 테이블은 커지고, 페이지 테이블이 커지면 디스크 I/O 작업의 효율성은 떨어지게 된다. 이를 최적화할 수 있는 기법들 중 중 가장 중요한 건 클러스터링이다.

VMS는 클러스터링을 통해 전역 더티 리스트의 페이지들을 큰 배치로 묶어 한 번에 디스크에 쓴다. 쓰기 작업의 수를 줄이고 크기를 늘리면 성능이 향상되므로 클러스터링은 대부분의 현대 시스템에서 사용되고 있다.

Other Neat Tricks

VMS에서 유래해, 지금은 표준으로 쓰이는 다른 두 기법들도 있다. 바로 demand zeroing과 copy-on write이다.

Demand Zeroing of Pages

한 페이지를 힙 주소 공간에 추가하려고 한다고 해보자. 단순한 구현에서 OS는 물리 메모리에서 페이지를 찾아 0으로 초기화하고, 이를 주소 공간에 매핑해 해당 요청에 응답할 것이다. 하지만 이러한 방식은 너무 비싸다. 특히 프로세스가 해당 페이지에 접근하지 않는 경우에는 더욱 그렇다.

demand zeroing의 경우, OS는 페이지가 주소 공간에 추가 되었을 때 거의 아무 일도 하지 않고, 그저 페이지 테이블에 접근 불가능 페이지라 표기하고 항목을 추가하기만 한다. 이때 프로세스가 해당 페이지를 읽고 쓰려 하면 OS에 트랩이 발생하게 되는데, OS는 이 트랩을 처리할 때가 되면 그제서야 물리 메모리를 찾고, 0으로 초기화하고, 프로세스의 주소 공간에 매핑하는 작업 등을 진행한다. 프로세스가 해당 페이지에 접근하지 않으면 이러한 작업들은 이루어지지 않는다.

Copy-On-Write(COW)

COW 기법에서 OS는 한 주소 공간을 다른 곳으로 복사해야 할 때, 이를 실제로 복사하는 대신, 대상 주소 공간에 매핑만 하고, 해당 페이지의 PTE를 양쪽의 주소 공간에서 read-only로 마크한다. 만약 두 주소 공간이 페이지를 읽기만 한다면 다른 추가적인 행동은 필요가 없으며, 실제로 데이터를 옮기지 않고도 그렇게 한 것만 같은 효과를 낼 수 있다.

이때 한 주소 공간이 쓰기 작업을 하려고 하면 트랩을 발생시킨다. OS는 페이지가 COW 페이지임을 알게 되고, 그제서야 새 페이지를 할당하고 데이터를 채우고, 이 새 패이지를 폴트를 발생시킨 프로세스의 주소공간에 매핑한다. 이후 프로세스는 재개되고 자신만의 페이지를 가지게 된다.

COW는 여러 이유로 유용하다. 예컨대 공유 라이브러리들은 여러 프로세스들의 주소 공간에 COW로 매핑되어 메모리 공간을 절약하는 효과를 낸다. UNIX 시스템에서 COW는 더 중요한데, fork()나 exec() 때문이다. fork()는 호출자의 주소 공간과 정확히 동일한 사본을 만드는데, 이 작업은 느리고 데이터도 많이 사용한다. 이때, 대부분의 주소 공간은 이후에 따라오는 exec() 콜에 의해 덮어 쓰이는데, $exec()$은 호출 프로세스의 주소 공간을 실행할 프로그램으로 덮어 쓴다. fork()에 대해 COW를 적용하면 OS는 필요없는 복사를 피하고 정확한 semantic을 유지하면서 성능 또한 개선시킬 수 있다.