가상 메모리
물리 및 가상 주소 방식
컴퓨터 시스템의 메인 메모리는 M개의 연속적인 바이트 크기 셀의 배열로 구성된다. 각 바이트는 고유의 물리 주소를 가진다.
CPU가 메모리에 접근하는 가장 자연스러운 방식은 물리 주소(PA)를 사용하는 것이다. 이러한 접근을 물리 주소 방식이라고 한다.
초기 PC들, 현재의 일부 시스템들은 여전히 물리 주소 방식을 사용하지만, 현대의 프로세스 대부분은 가상 주소 방식을 사용한다.
CPU는 가상 주소(VA)를 생성해서 메인 메모리에 접근하며, 이것은 메모리로 보내지기 전에 적절한 물리 주소로 변환된다.
가상 주소를 물리 주소로 변환하는 작업을 주소 번역이라고 하며, 이는 CPU 하드웨어와 운영체제 간에 긴밀한 협력을 필요로 한다.
CPU 칩 내에 메모리 관리 유닛(MMU)이라는 하드웨어가 메인 메모리에 저장된 참조 테이블을 사용해서 가상 주소를 번역하며,
해당 테이블의 내용은 운영체제가 관리한다.
주소 공간
주소 공간은 비음수 정수 주소의 정렬된 집합이다. 만일 주소 공간의 정수가 연속적이라면, 이 공간은 선형 주소 공간이다.
CSAPP에서는 설명의 편의를 위해 선형 주소 공간을 가정한다. CPU는 가상 주소 공간에서 가상의 주소를 생성한다.
가상 주소 공간의 크기는 보통 아래와 같이 가장 큰 주소를 표시하는 데 필요한 비트 수로 나타낸다.
현대 시스템은 32비트 또는 64비트 가상 주소 공간을 지원한다.
또한 컴퓨터 시스템은 M 바이트의 물리 메모리로 대응되는 물리 주소 공간을 갖는다.
M은 2의 제곱일 필요는 없지만 CSAPP에서는 논의를 단순하게 하기 위해 M을 2의 제곱 수로 가정한다.
캐싱 도구로서의 VM
가상 메모리는 디스크에 저장된 N개의 바이트 크기의 셀 배열로 구성된다.
각 바이트는 특정한 가상 주소를 가지며, 디스크 안의 배열 정보는 메인 메모리에 캐시 된다.
VM 시스템은 가상 메모리를 규정된 사이즈 블록 단위로 분할하여 관리한다. 분할된 블록들은 가상 페이지라 부른다.
각 가상 페이지는 P 바이트 크기를 갖는다. 유사하게 물리 메모리도 P 바이트 크기의 물리 페이지(물리 프레임)로 분할되어 사용된다.
가상 페이지의 집합은 아래와 같이 세 개의 중첩되지 않는 부분집합으로 나누어진다.
1. Unallocated : VM 시스템에 의해 아직까지 할당되지 않은 페이지들을 의미한다.
비 할당된 블록들은 이들과 관련된 데이터를 하나도 가지고 있지 않으며, 따라서 디스크 상에 어떤 공간도 차지하지 않는다.
2. Cached : 현재 물리 메모리에 캐시 되어 할당된 페이지들을 의미한다.
3. Uncached : 물리 메모리에 캐시 되지 않은 할당된 페이지들을 의미한다.
DRAM 캐시의 구성
CSAPP에서는 CPU와 메인 메모리 사이의 L1, L2, L3 캐시 메모리를 SRAM 캐시라고 하며,
가상 페이지를 메인 메모리로 캐싱하는 VM 시스템 캐시를 DRAM 캐시라고 한다.
DRAM이 최소한 SRAM보다 10배 더 느리고 디스크는 DRAM보다 약 100,000배 더 느리다.
따라서 DRAM 캐시 미스는 SRAM 캐시 미스보다 비용이 많이 든다.
또한 디스크 섹터로부터 첫 번째 바이트를 읽는 비용은 섹터에서 연속적인 바이트를 읽는 것보다 약 100,000배 더 느리다.
이러한 큰 규모의 미스 비용과 첫 번째 바이트를 접근하는 데 드는 비용 때문에 가상 페이지는 커지고 있다.
대개 4KB에서 2MB까지 값을 갖는다.
DRAM 캐시는 완전 결합성이다. 즉, 모든 가상 페이지는 물리 페이지에 둘 수 있다.
디스크의 큰 접근 시간 때문에 DRAM은 항상 write-through 대신에 write-back을 사용한다.
페이지 테이블
VM 시스템은 캐시와 관련한 다양한 기능을 갖고 있어야 한다.
예를 들어, 가상 페이지를 어떤 물리 페이지로 캐싱하는지 결정하는 기능,
캐시 미스 발생 시 디스크 어디에 가상 페이지가 저장되어 있는지 확인하는 기능,
또한, 메모리가 가득 찬 경우, 물리 메모리 중에서 방출할 페이지를 선택하고 교체하는 기능 등이 있어야 한다.
이러한 기능은 운영체제 소프트웨어와 MMU 내의 주소 번역 하드웨어,
가상 페이지를 물리 페이지로 매핑하는 페이지 테이블이라고 알려진 물리 메모리에 저장된 자료구조의 조합으로 제공된다.
주소 번역 하드웨어는 가상 주소를 물리 주소로 변환할 때마다 페이지 테이블을 읽는다.
운영체제는 페이지 테이블의 콘텐츠 관리와 페이지들을 디스크와 DRAM 사이에서 왔다 갔다 하는 것을 관장한다.
아래는 페이지 테이블의 기본 구조를 보여준다. 페이지 테이블은 페이지 테이블 엔트리(PTE)의 배열이다.
가상 주소 공간의 각 페이지는 페이지 테이블 내에 고정된 오프셋 위치에 PTE를 갖는다.
CSAPP에서는 편의상 각 PTE가 한 개의 유효 비트(valid), n비트의 주소 필드로 구성된다고 가정한다.
유효 비트는 가상 페이지가 현재 DRAM에 캐시 되어 있는지를 나타낸다.
만일 유효 비트가 세팅되었다면 주소 필드는 가상 페이지가 캐시 되어 대응되는 DRAM의 물리 페이지 시작을 나타낸다.
만일 유효 비트가 세팅되어 있지 않다면, Null 주소는 가상 페이지가 아직 할당되지 않았음을 나타내고,
그렇지 않은 주소는 디스크 상의 가상 페이지의 시작 부분을 가리킨다.
페이지 히트(Page Hits)
위의 왼쪽 그림에서 CPU가 물리 메모리에 캐시 되어 있는 VP 2 한 개를 읽을 때, 이를 페이지 히트라고 한다.
페이지 히트의 과정은 다음과 같다. 우선, 가상 주소를 인덱스로 사용하여 페이지 테이블에서 PTE를 찾는다.
해당 PTE의 유효 비트를 확인하고(히트 상황에서는 1로 세팅), 주소 필드를 이용하여 물리 메모리 주소(PP1)를 찾는다.
페이지 폴트(Page Faults)
가상 메모리 용어에서 DRAM 캐시 미스는 페이지 폴트라고 한다.
위의 오른쪽 그림에서 CPU는 물리 메모리에 캐시 되어 있지 않은 VP 3을 참조하였다.
주소 번역 하드웨어는 메모리에서 PTE 3을 읽으며, 유효 비트를 통해 VP 3가 캐시 되어 있지 않다는 것을 확인한다.
이렇게 캐시 미스된 상황이 페이지 폴트이며, 주소 번역 하드웨어는 커널 내에 페이지 폴트 핸들러를 호출한다.
커널은 방출 정책에 따라 물리 메모리에서 방출할 페이지를 선정하고, VP3를 방출할 페이지의 주소로 복사한다.
요구 페이징(Demand Paging)
디스크와 메모리 사이에 페이지를 전송하는 동작을 스와핑 또는 페이징이라고 한다.
페이지들은 디스크에서 물리 메모리로 스와핑해 들어오며(paged in), 물리 메모리에서 디스크로 스와핑 되어 나간다(paged out).
프로세스 실행 시, 프로세스의 모든 페이지를 물리 메모리에 할당하지 않고 필요한 부분만 할당 후,
실제로 특정 페이지가 요구되는 순간에 물리 메모리에 할당하는 기법을 요구 페이징이라 한다.
메모리 관리를 위한 도구로서의 VM
VM은 코드와 데이터의 공유, 메모리 할당
공유를 단순화한다.
일반적으로 각 프로세스는 다른 프로세스와 공유되지 않은 자신만의 코드, 데이터, 힙, 스택 영역을 갖는다.
따라서 운영체제는 각 프로세스마다 별도의 페이지 테이블을 제공하며,
각각의 페이지 테이블은 페이지를 중첩되지 않는 물리 페이지로 매핑한다.
그렇지만 일부 경우에는 프로세스들이 코드와 데이터를 공유하는 것이 바람직할 때가 있다.
예를 들어, 모든 프로세스는 동일한 운영체제 커널 코드를 호출해야 한다.
이 경우, 해당 코드를 각 가상 페이지를 서로 다른 물리 페이지에 매핑하여 사용하는 것보다
아래와 같이 하나의 동일한 물리 페이지에 매핑하는 것이 적절할 수 있다.
메모리 할당을 단순화한다.
가상 메모리는 사용자 프로세스에 추가적인 메모리 할당하는 것을 쉽게 만들어준다.
예를 들어, 프로세스가 힙 공간을 요청할 때 운영체제는 적당한 수의 연속적인 가상 메모리 페이지를 할당하고
이들을 물리 메모리 내에 위치한 임의의 물리 페이지로 매핑한다.
이때, 페이지 테이블 덕분에 물리 메모리에서는 연속적인 페이지를 찾을 필요가 없어 빠르게 매핑할 수 있다.
링킹을 단순화한다.
별도의 주소 공간은 각 프로세스들이 각 메모리 이미지에 대해서 코드와 데이터가 실제로 물리 메모리 내 어디에 위치하는지와 상관없이
동일한 기본 포맷을 사용하도록 해 준다. 이러한 통일성은 링커의 설계와 구현을 매우 단순화해 주며, 물리 메모리 상에서 궁극적인 코드와
데이터의 위치에 독립적인 완전히 링크된 실행 가능 파일을 만들 수 있게 해 준다.
메모리 보호를 위한 도구로서의 VM
현대 모든 컴퓨터 시스템은 운영체제가 메모리 시스템 접근을 제어할 수 있도록 한다.
사용자 프로세스는 자신의 read-only 코드 섹션을 수정할 수 없으며, 커널 내의 코드와 데이터 구조들도 읽거나 수정할 수 없다.
또한, 다른 프로세스의 사적 메모리도 명시적으로 허용된 경우가 아니라면 읽거나 쓸 수 없으며,
다른 프로세스와 공유하는 어떤 가상 페이지도 수정해서는 안된다.
별도의 가상 주소 공간을 제공하면 사적 메모리를 다른 프로세스로부터 분리하는 것이 쉬워진다.
더불어 페이지 테이블에 몇몇 비트를 추가하면 섬세한 접근 제어가 가능해진다.
아래는 각 PTE에 세 개의 허가 비트를 추가한 예시이다.
만일 어떤 인스트럭션이 이 비트의 허가 사항을 위반한다면 CPU는 일반 보호 오류를 발생시켜서 커널의 예외 핸들러로 제어를 이동시킨다.
리눅스 쉘은 일반적으로 이러한 예외를 세그멘테이션 폴트(Segmentation Fault)라고 한다.
주소의 번역
아래 그림은 MMU가 매핑을 하기 위해 페이지 테이블을 어떻게 사용하는지 보여준다.
1. CPU의 페이지 테이블 베이스 레지스터(PTBR)는 현재 페이지 테이블을 가리킨다.
2. 가상 주소의 VPN을 사용하여 해당 페이지 테이블에서 적합한 PTE를 선택한다.
3. 유효 비트가 세팅되어 있다면, PTE에서 확인한 PPN과 가상 주소의 VPO를 연결하여 물리 주소를 찾는다.
페이지 히트
1. CPU는 가상 주소를 생성하고 이것을 MMU로 보낸다.
2. MMU는 PTE 주소를 생성하고 이것을 캐시/메인 메모리에 요청한다.
3. 캐시/메인 메모리는 PTE를 MMU로 리턴한다.
4. MMU는 물리 주소를 구성하고 이것을 캐시/메인 메모리로 보낸다.
5. 캐시/메인 메모리는 요청한 데이터 워드를 프로세서로 보낸다.
페이지 폴트
1. CPU는 가상 주소를 생성하고 이것을 MMU로 보낸다.
2. MMU는 PTE 주소를 생성하고 이것을 캐시/메인 메모리에 요청한다.
3. 캐시/메인 메모리는 PTE를 MMU로 리턴한다.
4. PTE 유효 비트가 0이므로 MMU는 예외를 발생시키고, CPU 내의 제어를 운영 체제 커널의 페이지 폴트 예외 핸들러로 이동시킨다.
5. 예외 핸들러는 물리 메모리 내의 방출 페이지를 선택하고, 만일 이 페이지가 수정되었다면 디스크로 페이지를 이동한다.
6. 예외 핸들러는 새 페이지를 페이지 이동해서 들여오고, 메모리 내의 PTE를 갱신한다.
7. 예외 핸들러는 1단계로 돌아가 인스트럭션을 재시작한다.
TLB를 사용한 주소 번역 속도의 개선
CPU가 가상 주소를 생성할 때마다, MMU는 가상 주소를 물리 주소로 번역하기 위해서 PTE를 참조해야 한다.
해당 과정으로 인해 실제 물리 주소 찾는 과정에서 CPU는 메모리 참조를 두 번해야 한다. 메모리 참조는 비용이 많이 드는 작업이다.
해당 비용을 줄이기 위해 MMU 내에 번역 참조 버퍼(TLB, Translatio Lookaside Buffer)라고 부르는 작은 캐시를 이용한다.
TLB는 작은 가상 주소 지정 캐시로, 각 라인은 하나의 PTE로 구성된 하나의 블록을 저장한다.
TLB에서 블록을 찾기 위한 TLB Tag(TLBT)와 TLB Index(TLBI)는 VPN의 비트들로 구성한다.
아래는 TLB를 사용한 주소 번역 과정의 단계이다.
TLB 히트
1. CPU는 가상 주소를 생성하고 이것을 MMU로 보낸다.
2. MMU는 VPN을 사용하여 TLB의 블록을 찾는다.
3. TLB는 해당 블록에서 PTE를 찾아 MMU로 리턴한다.
4. MMU는 가상 주소를 물리 주소로 번역하고, 그것을 캐시/메인 메모리로 전송한다.
5. 캐시/메인 메모리는 요청한 데이터 워드를 CPU로 리턴한다.
TLB 미스
1. CPU는 가상 주소를 생성하고 이것을 MMU로 보낸다.
2. MMU는 VPN을 사용하여 TLB의 블록을 찾는다.
3. TLB에 블록이 존재하지 않는다면 MMU는 PTE 주소를 생성하여 캐시/메인 메모리에 요청한다.
4. 캐시/메인 메모리는 PTE 주소를 이용하여 TLB의 PTE를 갱신하고, MMU는 물리 주소를 캐시/메인 메모리로 전송한다.
5. 캐시/메인 메모리는 요청한 데이터 워드를 CPU로 리턴한다.