가상화 - 메모리 가상화 : 완전한 가상 메모리 시스템

지금까지 가상 메모리 시스템을 구성하는 여러 중요 구성 요소에 대해 살펴보았다.

이 구성 요소에는 페이지 테이블 설계 방식, TLB를 비롯한 하드웨어와의 상호 작용, 페이지 관리 정책 등이 포함된다.

두 개의 가상 메모리 시스템, VAX/VMS(Virtual Address Extension/Virtual Memory System)와 Linux를 상세히 살펴보면서

보다 완전한 가상 메모리 시스템을 구현하기 위해 필요한 특징들이 무엇인지 살펴보도록 하자.

VAX/ VMS 가상 메모리

VAX/VMS는 컴퓨터의 구조적 결함을 소프트웨어로 보완한 훌륭한 사례다. 

운영체제가 이상적인 개념과 환상을 제공하기 위해 하드웨어 의존하지만, 하드웨어가 모든 것을 제대로 해내지 못할 경우도 있다.

하드웨어 결함에도 불구하고 시스템이 효과적으로 작동하기 위해 운영체제가 무엇을 하였는지 살펴보자.

1) 메모리 관리 하드웨어

VAX는 프로세스마다 512바이트(2의 9승) 페이지 단위로 나누어진 32비트 가상 주소 공간을 제공한다.

가상 주소는 23비트 VPN과 9비트 오프셋으로 구성된다. VPN의 상위 2비트는 페이지가 속한 세그먼트를 나타내기 위해 사용되었다.

이 시스템은 페이징과 세그멘테이션의 하이브리드 구조를 갖고 있다.

 

전체 주소 공간의 절반은 프로세스 공간이며, 프로세스 공간의 첫 번째 절반에(P0) 사용자 프로그램과 힙이 존재한다.

프로세스 공간의 나머지 절반에(P1) 스택이 존재한다. 전체 주소 공간의 나머지 절반은 반만 사용되며, 시스템 공간(S)이라 불린다.

운영체제의 보호된 코드와 데이터가 이곳에 존재하며, 이 방식으로 여러 프로세스가 운영체제를 공유한다.

 

VMS 설계자들의 주요 고민 중 하나는 VAX 하드웨어의 페이지 크기였다. 선형 페이지 테이블의 크기가 지나치게 커진다는 것이 문제였다.

설계자들의 첫 목표는 VMS가 페이지 테이블 저장을 위해 메모리를 소진하는 것을 막는 것이었다. 이를 위해 두 가지 방법을 사용하였다.

첫째, 사용자 주소 공간을 두 개의 세그먼트로 나누어 프로세스마다 각 영역을 위한 페이지 테이블을 갖도록 하였다. 

이로 인해 스택과 힙 사이의 사용되지 않는 주소 영역을 위한 페이지 테이블 공간이 필요 없게 되었다.

둘째, 사용자 페이지 테이블들을 커널의 가상 메모리에 배치하였다.

페이지 테이블을 할당하거나 크기를 키울 때, 커널은 자신의 가상 메모리 세그먼트(S) 내에 공간을 할당한다. 

메모리가 고갈되면 커널은 페이지 테이블의 페이지들을 디스크로 스왑 하여 물리 메모리를 다른 용도로 사용할 수 있게 하였다.

2) 실제 주소 공간

위의 그림을 통해 VAX/VMS의 주소 공간을 대략적으로 확인할 수 있었다. 코드 세그먼트는 절대로 주소 공간 0에서 시작하지 않는다.

주소 공간 0은 접근 불가능 페이지로 마킹되어 있으며 널 포인터 접근을 검출할 수 있게 한다.

주소 공간 설계 시 고려해야 할 사항은 효과적인 디버깅 지원 여부이다. 접근 불가능한 페이지 0은 그중 하나이다.

좀 더 중요한 사실은 커널의 가상 주소 공간이 사용자 주소 공간의 일부라는 것이다.

문맥 교환이 발생하면 운영체제는 P0과 P1 레지스터를 다음에 실행될 프로세스의 페이지 테이블을 가리키도록 변경한다.

하지만 S의 베이스, 바운드 레지스터는 변경하지 않기 때문에 결과적으로 동일한 커널 구조들이 각 사용자 주소 공간에 매핑된다.

 

몇 가지 이유로 커널은 여러 주소 공간들로 매핑된다. 그러한 구조를 택하면 커널의 동작이 쉬워진다.

예를 들어, 운영체제가 사용자 프로그램으로부터 포인터를 전달받았다면 그 포인터로부터 데이터를 자신의 구조로 그냥 복사하면 된다.

운영체제는 접근하는 데이터가 어디에서 오는지 고려할 필요 없이 자연스럽게 작성되고 컴파일될 수 있다. 

만약, 커널이 전부 물리 메모리에만 존재한다면 페이지 테이블의 페이지들을 디스크로 스왑 하는 등의 작업은 상당히 어려웠을 것이다.

커널이 자체 주소 공간을 가진다면 사용자 프로그램들과 커널 간의 데이터 이동이 매우 복잡하고 고통스러운 일이 될 것이다.

 

주소 공간에 관한 마지막 이슈는 보호와 관련 있다.

운영체제는 응용 프로그램이 운영체제의 데이터나 코드를 읽거나 쓰는 것을 분명히 원하지 않는다.

운영체제의 자료를 보호하기 위해서는 하드웨어가 페이지 별로 보호 수준을 다르게 설정할 수 있어야 한다.

이를 위해 VAX는 페이지 테이블의 Protection Bit에 보호 수준을 지정한다.

특정 페이지를 접근하기 위해서 필요한 CPU의 권한 수준이 기록된다.

운영체제의 데이터와 코드는 사용자 프로그램의 데이터와 코드보다 더 높은 보호 수준으로 지정된다.

3) 페이지 교체

VAX의 페이지 테이블 항목은(PTE) 다음과 같은 비트들을 가지고 있다.

유효(Valid), 보호(Protection), 변경(Dirty) 비트, 운영체제가 사용하기 위해 예약해 놓은 비트, 물리 프레임 번호(PFN)가 있다.

참조(Reference) 비트가 없다. VMS 교체 알고리즘은 어떤 페이지가 자주 사용 중인지를 하드웨어 지원 없이 판단해야 한다.

또한, 메모리를 너무 많이 사용하는 프로그램, 메모리 호그에 대해서도 고민해야 한다. 지금까지 살펴보았던 대부분의 정책들은

메모리를 많이 소비하는 프로세스에 대한 대비책이 없다. 이와 같은 문제를 해결하기 위해 몇 가지 정책들을 도입하였다.

 

대표적으로 세그먼트 된 FIFO 교체 정책이 이 있다.

각 프로세스는 상주 집합 크기(RSS, Resident Set Size)를 지정받는다. 이는 메모리에 유지할 수 있는 최대 페이지 개수를 의미한다.

페이지들은 FIFO 리스트에 보관되며, 페이지의 개수가 RSS보다 커지면 제일 먼저 들어왔던 페이지가 방출된다.

그런데 순수한 FIFO는 성능이 좋지 않다.

성능 개선을 위해 클린 페이지 프리 리스트와 더티 페이지 리스트라고 하는 두 개의 second-chance list를 도입하였다.

second-chance list는 메모리에서 제거되기 전에 페이지가 보관되는 리스트이다.

프로세스가 자신의 RSS를 넘긴다면 자신의 FIFO에서 페이지가 제거된다.

제거된 페이지가 클린 상태라면 클린 페이지 리스트에, 더티 상태라면 더티 페이지 리스트에 추가된다.

이제 다른 프로세스가 실행되어 빈 페이지가 필요한 경우, 클린 리스트에서 첫 번째 프리 페이지를 꺼낸다. 

 

또한, 페이지 크기가 작을수록 스왑 할 때 디스크 I/O가 비효율적이다. 디스크는 전송 단위가 클수록 성능이 좋기 때문이다.

페이지 크기가 작은 VMS는 더티 리스트에 있는 페이지들을 작업 묶음으로 만들어서 한 번에 디스크로 보낸다.

쓰기 횟수는 줄이고 한 번에 쓰는 양은 늘려서 성능을 향상하는 작업 방식을 클러스터링 기법이라고 한다.

이는 대부분의 현대 시스템에서 사용하는 기법이다.

4) 그 외의 기법들 

VAX/VMS는 이제는 표준화가 된 기법 두 가지를 더 가지고 있었다.

요청 시 0으로 채우기(Demand Zeroing)와 쓰기 시 복사(Copy On Write)가 그것이다.

 

Demand Zeroing 먼저 살펴보자. 힙 등의 주소 공간에 페이지를 추가한다고 하였을 때,

단순한 구현에서는 힙에 페이지를 추가하는 요청이 오면 운영체제는 물리 메모리에서 페이지를 찾아 0으로 채운다. 

그런 후에 주소 공간에 그 페이지를 매핑한다. 하지만 이 경우 프로세스가 해당 페이지를 사용하지 않으면 메모리 낭비이다.

그런데 Demand Zeroing의 경우, 페이지가 주소 공간에 추가되는 시점에는 거의 하는 일이 없다.

페이지 테이블 항목에 접근 불가능 페이지라고 표기하고 추가하는 것이 끝이다. 

그런데 프로세스가 추가된 페이지를 읽거나 쓸 때 운영체제로 트랩이 발생한다.

트랩을 처리하면서 운영체제는 Demand Zeroing 할 페이지라는 것을 알게 된다.

이 시점에서 운영체제는 물리 페이지를 0으로 채우고 프로세스의 주소 공간으로 매핑하는 등의 필요한 작업을 진행한다.

프로세스가 해당 페이지를 전혀 접근하지 않는다면, 즉 사용하지 않는다면 이 모든 작업을 피할 수 있다.

 

다음으로 Copy On Write이다. 운영체제가 한 주소 공간에서 다른 공간으로 페이지를 복사할 필요가 있을 때,

복사를 바로 하지 않고 해당 페이지를 대상 주소 공간으로 매핑만 한다. 이후, 해당 페이지의 페이지 테이블 항목을 읽기 전용으로 표시한다.

만약 양쪽 주소 공간이 읽기만 한다면 더 이상의 조치는 필요 없다. 운영체제는 실제로 데이터 이동 없이 빠른 복사를 할 수 있게 된다.

그런데 두 주소 공간 중에 하나가 페이지 쓰기를 시도한다면 운영체제로 트랩이 발생한다.

운영체제는 그때 해당 페이지가 COW 페이지라는 것을 파악한다.

그런 후에 새로운 페이지를 할당하고 데이터로 채우고 이를 페이지 폴트를 일으킨 주소 공간에 매핑한다.

이제 프로세스는 독자적인 페이지의 사본을 갖게 된다.

공유 라이브러리들을 여러 프로세스들의 주소 공간에 COW로 매핑하면 메모리 공간을 절약할 수 있다. 

Linux 가상 메모리 시스템

Linux VM의 모든 측면에 관해 논의할 수는 없지만 VAX/VMS와 같은 고전적인 VM 시스템보다 발전한 부분을 다룰 것이다.

1) Linux 주소 공간

다른 현대적인 운영체제와 마찬가지로 Linux 가상 주소 공간은 사용자 영역과 커널 영역으로 구성된다. 

문맥 교환 시 현재 실행 중인 주소 공간의 사용자 영역이 변경된다. 커널 영역은 모든 프로세스에서 동일하다.

사용자 모드에서 실행되는 프로그램은 커널 영역에 접근할 수 없다.

커널로 트랩이 발생하고 특권 모드로 전환되어야만 커널 영역에 접근할 수 있다.

32비트 Linux 주소 공간에서 사용자 영역과 커널 영역의 구분은 주소 0xC0000000 또는 주소 공간의 3/4 지점에서 발생한다.

 

Linux의 한 가지 흥미로운 점은 커널 영역의 유형이 두 개라는 것이다. 

첫 번째는 커널 논리 영역으로 이것은 일반적으로 생각하는 커널의 가상 주소 공간이다.

페이지 테이블, 프로세스 별 커널 스택 등과 같은 대부분의 커널 데이터 구조가 이 공간에 존재한다.

커널 논리 영역의 가장 흥미로운 점은 물리 메모리와의 연결이다. 커널 논리 영역의 시작 주소가물리 메모리의 첫 부분에 직접 매핑된다.

이 직접 매핑에는 두 가지 의미가 있다.

첫 째는 커널 논리 영역의 주소와 물리 주소 사이의 변환이 간단하다는 것이다.

둘 째는 메모리 청크가 커널 논리 영역에서 연속적이면 물리 메모리에서도 연속적이라는 것이다. 

따라서 이 공간은 DMA와 같이 연속적인 물리 메모리를 필요로 하는 작업에 적합하다.

 

커널 주소의 다른 유형은 커널 가상 영역이다. 커널 가상 영역의 메모리는 보통 연속적이지 않다. 커널 가상 영역의 페이지는 연속하지 않은 물리 페이지에 매핑될 수 있다. 결과적으로 더 쉽게 할당할 수 있기 때문에 대용량 버퍼 할당에 사용된다. 또한, 물리 메모리와 정확하게 매핑될 필요가 없기에 커널은더 많은 양의 메모리를 사용할 수 있게 된다.

2) 페이지 테이블 구조

인텔x86은 하드웨어가 관리하는 멀티 레벨 페이지 테이블 구조를 제공하며, 프로세스 당 하나의 페이지 테이블이 있다.

운영체제는 메모리에 매핑을 설정하고, 특권 레지스터가 페이지 디렉터리의 시작 주소를 가리키도록 하는 것이 전부이다.

하드웨어가 그 이후의 모든 처리를 담당한다. 운영체제는 프로세스 생성, 삭제, 문맥 전환에 관여하며,

각 경우의 주소 변환 시 MMU가 적절한 페이지 테이블을 사용하게 한다.

 

32비트 시스템에서 64비트 시스템으로 전환하면서 x86의 페이지 테이블 구조 역시 변화하였다.

현재 64비트 시스템은 4 레벨 페이지 테이블을 사용한다.

그러나 전체 64비트 크기의 전체 가상 주소 공간이 아직 사용되지 않고 아래와 같이 하위 48비트만 사용한다. 

 

그림에서 볼 수 있듯이 가상 주소의 상위 16비트는 사용되지 않고 하위 12비트(페이지 크기가 4KB이므로)가 오프셋으로 사용된다.

따라서 변환에는 중간의 36비트가 관여한다. 주소의 P1 부분은 최상위 페이지 디렉터리를 색인하는 데 사용되며,

변환은 거기서부터 시작하여 페이지 테이블의 물리 페이지가 P4에 의해 색인될 때까지 한 번에 한 레벨씩 변환이 진행된다.

3) 크기가 큰 페이지 지원

x86은 4KB 페이지 뿐만 아니라 여러 페이지 크기를 사용할 수 있다. 특히 최근의 설계는 2MB, 심지어 1GB까지도 지원한다.

Linux는 응용 프로그램이 거대한 페이지를 활용할 수 있도록 진화해왔다.

거대한 페이지를 사용하면 페이지 테이블에 필요한 매핑 개수가 줄어든다. 중요한 점은 TLB가 효과적으로 작동한다는 것이다.

TLB의 더 적은 슬롯을 사용하더라도 TLB 미스 없이 매우 큰 메모리 공간에 접근할 수 있다는 것이 주된 이점이다.

그런데 거대한 페이지를 사용하는 데에는 대가가 있다. 가장 큰 잠재적인 비용은 내부 단편화이다.

즉, 크기는 크지만 드문드문 사용되는 페이지이다. 이 형태의 낭비는 크기만 크고 거의 사용되지 않는 페이지들로 메모리를 채울 수 있다.

거대한 페이지를 사용하는 경우, 스와핑도 제대로 작동하지 않으며 이로 인해 시스템이 수행하는 I/O 양이 크게 증가할 수 있다.

메모리 크기가 커짐에 따라 VM 시스템의 필수적인 발전의 일부로서 4KB보다 큰 페이지의 도입과 그 해결책이 필요해졌다.

4) 페이지 캐시

영구 저장장치에 대한 접근 비용을 줄이기 위해 대부분의 시스템은 공격적인 캐싱 서브 시스템을 사용하여 데이터를 메모리에 유지한다.

Linux 페이지 캐시는 세 가지 주요 소스, 메모리 맵 파일(memory-mapped file), read( ), write( )를 호출하여 액세스 되는 파일 데이터와 메타 데이터, 힙, 스택과 관련한 페이지(anonymous memory)로부터 온 페이지를 메모리에 유지할 수 있도록 한다.

이러한 항목들은 페이지 캐시 해시 테이블에 보관되어 빠른 검색이 가능하다.

 

페이지 캐시는 항목이 클린 혹은 더티 상태인지를 추적한다.

더티 상태의 데이터는 백그라운드 스레드에 의해 백킹 스토어에 주기적으로 기록되며, 결국에는 영구 저장 장치에 반영된다.

이때 백킹 스토어란 파일 데이터의 경우 특정 파일을 의미하며, anonymous memory의 경우 스왑 공간을 의미한다.

백그라운드 활동은 일정 시간이 경과하거나 너무 많은 페이지가 더티로 분류되면 발생한다.

 

시스템의 메모리가 부족할 경우, Linux는 2Q 교체 알고리즘의 변형된 형태를 사용한다.

두 개의 리스트를 유지하여 메모리를 두 부분으로 나눈다. 처음 액세스되면 페이지는 비활동 리스트에 들어간다.

다시 참조되면 이 페이지는 활동 리스트로 승격된다. 교체가 필요할 때, 교체 후보는 비활동 리스트에서 가져온다.

또한, Linux는 주기적으로 활성 리스트의 맨 아래 페이지를 비활성 리스트로 이동시킨다.

이를 통해, 활동 리스트의 길이가 총 페이지 캐시 크기의 약 2/3가 되도록 유지한다.