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

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

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

1. VAX/VMS 가상 메모리

VAX/VMS 미니컴퓨터 구조는 1970년대에서 1980년대 초에 개발됐는데, 이 시스템에서 사용되는 많은 테크닉과 접근법들은 오늘날에도 쓰이고 있으며, 몇몇 아이디어들은 50년이 지났음에도 배워둘 만하다.

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 디자이너들의 첫 번쨰 목표는 VMS가 페이지 테이블들로 메모리가 소진되는 일이 일어나지 않도록 보장하는 것이었다.

시스템은 페이지 테이블이 메모리에 가하는 압력을 두 가지 방법으로 줄인다. 그 첫 번째는 유저 주소 공간을 두 개의 세그먼트로 나눔으로써 프로세스마다 각 영역의 페이지 테이블을 가지게 하는 것이다. 이렇게 함으로써 스택과 힙 사이의 사용되지 않는 공간에 대한 페이지 테이블 공간은 필요하지 않게 된다. 베이스-바운드 레지스터들은 예상한 대로 사용되는데, 베이스 레지스터는 해당 세그먼트의 페이지 테이블의 주소를 가지고, 바운드는 그 사이즈를 가진다.

두 번째로, OS는 유저 페이지 테이블을 커널의 가상 메모리에 둠으로써 메모리 압력을 더 줄인다. 페이지 테이블을 할당하거나 그 크기를 키울 때, 커널은 자신의 세그먼트 $S$ 내 가상 메모리에서 공간을 할당한다. 만약 메모리 압력이 커지면, 커널은 이 페이지 테이블들의 페이지들을 디스크로 스왑 아웃함으로써 물리 메모리를 다른 용도로 사용할 수 있게 한다.

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

A Real Address Space

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

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

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

커널은 여러 이유로 각 주소 공간에 매핑된다. 이러한 구조를 선택할 때 커널의 동작은 간단해지는데, 예를 들어 OS가 유저 프로그램으로부터 포인터를 건네 받을 때, 그 포인터로부터 데이터를 자신의 구조로 복사하는 일은 쉽다. OS는 자신이 접근하는 데이터가 어디에서 오는지 고려할 필요없이, 자연스럽게 작성되고 컴파일 된다. 만약 반대로 커널이 완전히 물리 메모리에만 위치해있다면, 페이지 테이블의 페이지들을 디스크로 스왑 아웃하는 일은 어려운 일이나, 유저 응용 프로그램과 커널 사이의 데이터 이동은 더 복잡해졌을 것이다. 지금은 보편적으로 사용되는 이러한 구조를 통해, 커널은 보호 영역임에도 응용 프로그램에게는 라이브러리와 같이 쓰이게 된다.

이 주소 공간에서 주목할 만한 마지막 포인트는 보호와 관련되어있다. 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에서 삭제된 페이지가 위치하게 되는 곳이다. 해당 페이지는, 만약 수정이 된 적이 없다면(즉 clean이면) 클린-페이지 리스트의 끝에 추가되고, 반대의 경우라면 더티-페이지 리스트의 끝에 추가된다.

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

Clustering

VMS에서 사용되는 다른 최적화 기법은 VMS의 작은 페이지 사이즈를 극복하는 데에 도움을 준다. 이렇게 작은 페이지들을 가지고 있을 때의 스와핑을 위한 디스크 I/O 작업은 너무 비효율적이다. 스와핑을 위한 I/O 작업을 좀 더 효율적으로 만들기 위해 VMS는 많은 최적화 기법들을 사용하는데, 그 중 가장 중요한 건 클러스터링이다. VMS는 클러스터링을 통해 전역 더티 리스트의 페이지들을 큰 배치로 묶어 한 번에 디스크에 쓴다. 이는 운영체제가 페이지들을 스왑 공간에 어디에든 자유롭게 배치할 수 있기 때문에 가능해진다. 쓰기 작업의 수를 줄이고 크기를 늘리면 성능이 향상되므로 클러스터링은 대부분의 현대 시스템에서 사용되고 있다.

Other Neat Tricks

VMS는 지금은 표준으로 쓰이는 다른 두 기법들도 가지고 있다. 바로 demand zeroing과 copy-on write이다.

Demand Zeroing of Pages

한 페이지를 힙 주소 공간에 추가하려고 한다고 해보자. 단순한 구현에서 OS는 물리 메모리에서 페이지를 찾고, 이를 0으로 초기화하고, 이를 주소 공간에 매핑함으로써 해당 요청에 응답할 것이다. 하지만 간단한 구현은, 특히 페이지가 프로세스에 의해 사용되지 않는 경우, 너무 비싸다.

demand zeroing의 경우, OS는 페이지가 주소 공간에 추가 되었을 때 거의 아무 일도 하지 않고, 그저 페이지 테이블에 접근 불가능 페이지라 표기하고 항목을 추가할 뿐이다. 만약 프로세스가 해당 페이지를 읽고 쓰려 하면 OS에 트랩이 발생하게 된다. 이 트랩을 처리할 때 OS는 해당 페이지가 demand-zero page임을 알게 되고, 그제서야 물리 메모리를 찾고, 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을 유지하면서 성능 또한 개선시킬 수 있다.