[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 18. Introduction to Paging
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
운영체제는 거의 모든 공간 관리 문제를 해결할 때 두 가지 중 하나를 사용한다. 첫 번째 방법은 세그멘테이션으로 가변 크기의 조각들로 분할하는 것이다. 세그멘테이션은 공간을 다양한 크기의 청크들로 분할할 때 공간 자체가 단편화(fragmented) 될 수 있고, 할당은 점점 어려워진다.
두 번째 방법은 페이징(paging)으로, 공간을 동일 크기의 청크들로 분할하는 것이다. 프로세스의 주소 공간을 몇 개의 가변 크기인 논리 세그먼트(ex. 코드, 힙, 스택)로 나누는 것이 아니라 고정 크기의 단위로 나눈다. 이 각각의 고정 크기 단위를 페이지(page)라고 부른다. 상응하여 물리 메모리도 페이지 프레임(page frame)이라고 불리는 고정 크기의 슬롯의 배열이라고 생각한다. 이 프레임 각각은 하나의 가상 메모리 페이지를 저장할 수 있다.
그렇다면 세그멘테이션의 문제점을 해결하기 위해 페이지를 사용하여 어떻게 메모리를 가상화할 수 있는가? 공간과 시간 오버헤드를 최소로 하면서 그 기법을 잘 동작하게 만들기 위한 방법은 무엇인가?
간단한 예제
이 방법을 명확히 이해하기 위해 간단한 예시를 살펴보자. 아래 그림은 총 크기가 64바이트이며 4개의 16바이트 페이지(가상 페이지 0, 1, 2, 3)로 구성된 작은 주소 공간이다.
물리 메모리는 아래 그림처럼 고정 크기의 슬롯들로 구성된다. 이 경우 8개의 페이지 프레임, 총 128바이트의 비현실적으로 작은 물리 메모리이다. 그림에서 볼 수 있듯이, 가상 주소 공간의 페이지들은 물리 메모리 전체에 분산 배치되어 있다. 또한 운영체제가 자기 자신을 위해서 물리 메모리의 일부를 사용한다.
페이징은 세그멘테이션에 비해 많은 장점을 가지고 있다. 가장 중요한 개선점은 유연성이다. 페이징을 사용하면 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 가령, 힙과 스택이 어느 방향으로 커지는가, 어떻게 사용되는가에 대한 가정을 하지 않아도 된다.
또 다른 장점은 페이징이 제공하는 빈 공간 관리의 단순함이다. 가령, 운영체제가 우리의 작은 64바이트 주소 공간을 8페이지 물리 메모리에 배치하기를 원한다고 할 때, 운영체제는 비어 있는 네 개의 페이지만 찾으면 된다. 아마 이를 위해 운영체제는 모든 비어 있는 페이지의 빈 공간 리스트를 유지하고 리스트의 첫 네 개 페이지를 선택할 것이다.
주소 공간의 각 가상 페이지에 대한 물리 메모리 위치 기록을 위하여 운영체제는 프로세스마다 페이지 테이블(page table)이라는 자료 구조를 유지한다. 페이지 테이블의 주요 역할은 주소 공간의 가상 페이지 주소 변환(address translation) 정보를 저장하는 것이다. 각 페이지가 저장된 물리 메모리 위치가 어디인지 알려준다.
위 예시에서 페이지 테이블은 아래 4개의 항목을 갖는다.
- 가상 페이지 0 -> 물리 프레임 3
- VP 1 -> PF 7
- VP 2 -> PF 5
- VP 3 -> PF 2
대부분의 페이지 테이블 구조는 프로세스마다 존재하는 구조이다. 역 페이지 테이블(inverted page table)이라는 예외적인 기법도 있다.
이제 주소 변환 준비가 되었다. 작은 주소 공간 64바이트를 가진 프로세스가 특정 가상 주소로 메모리 접근을 시도할 때를 가정하자.
프로세스가 생성한 가상 주소의 변환을 위해 먼저 가상 주소를 가상 페이지 번호(virtual page number, VPN)와 페이지 내의 오프셋 2개의 구성 요소로 분할한다. 이 예씨에서는 가상 주소 공간의 크기가 64바이트이기 때문에 가상 주소는 6비트가 필요하다. (2^6 = 64)
아래 그림에서 Va5는 가상 주소의 최상위 비트이며, Va0은 최하위 비트를 나타낸다. 우리는 페이지 크기 16바이트를 알고 있기 때문에, 아래와 같이 가상 주소를 나눌 수 있다.
페이지 크기는 64바이트의 주소 공간에서 16바이트이다. 따라서 4페이지를 선택할 수 있어야 하고 주소의 최상위 2비트가 그 역할을 한다. 우리는 2비트 가상 페이지 번호 VPN을 가지고 되고, 나머지 비트는 페이지 내에서 우리가 원하는 바이트의 위치를 나타낸다. 이것을 오프셋이라고 부른다.
프로세스가 가상 주소를 생성하면 운영체제와 하드웨어가 의미있는 물리 주소로 변환한다. 가령, 가상 주소가 21이라고 하고 이를 이진 형식으로 변환하면 010101을 얻고 이 가상 주소를 검사하고 가상 페이지 번호와 오프셋으로 나눈다.
가상 주소 21은 가상 페이지 01 또는 1의 5번째(0101번째) 바이트이다. 이 가상 페이지 번호를 가지고 페이지 테이블의 인덱스로 사용하여 가상 페이지 1이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다. 위의 페이지 테이블에서 물리 프레임 번호(physical frame number, PFN) 혹은 물리 페이지 번호(physical page number, PPN)는 7(이진수 111)이다. VPN을 PFN으로 교체하여 가상 주소를 변환할 수 있다.
오프셋은 페이지 내에서 우리가 원하는 위치를 알려주기에 변환되지 않고 동일하다! 최종적으로 계산된 물리 주소는 1110101(십진수 117)이며, 이곳이 탑재할 데이터가 저장된 정확한 위치이다.
페이징에 관해 몇 가지 기본적인 질문을 해보자면
페이지 테이블은 어디에 저장되고 내용과 크기는 어떻게 되는가?
페이징은 시스템을 너무 느리게 만들지는 않을까?
페이지 테이블은 어디에 저장되는가
작은 세그먼트 테이블이나 베이스-바운드 쌍에 비해 페이지 테이블은 매우 커질 수 있다. 가령, 4KB 크기의 페이지를 가지는 전형적인 32비트 주소 공간을 상상해 보자. 이 가상 주소는 20비트 VPN과 12비트 오프셋으로 구성된다.
20비트 VPN은 운영체제가 각 프로세스를 위해 관리해야 하는 변호나의 개수가 2^20이라는 것을 의미하고 어림잡아 백만이다. 물리 주소로의 변환 정보와 다른 필요한 정보를 저장하기 위해 페이지 테이블 항목(page table entry, PTE)마다 4바이트가 필요하다고 가정하면, 각 페이지 테이블을 저장하기 위하여 4MB라는 꽤 큰 메모리가 필요하게 된다.
프로세스 100개가 실행 중이라고 가정한다면 주소 변환을 위해 운영체제가 400MB의 메모리를 필요로 하는 것을 의미한다. 컴퓨터가 기가바이트 단위의 메모리를 가지고 있는 현재라도 변환을 위해서 이런 큰 청크를 사용하는 것은 비정상적이고, 64비트 주소 공간을 위한 페이지 테이블의 크기가 얼마나 클지에 대해서는 생각하기조차 싫다.
페이지 테이블이 매우 크기 때문에 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로를 MMU 안에 유지하지 않을 것이다. 대신 각 프로세스의 페이지 테이블을 메모리에 저장한다. 당분간 페이지 테이블은 운영체제가 관리하는 물리 메모리에 상주한다고 가정하자.
나중에 운영체제 메모리 자체의 많은 부분이 가상화될 수 있다는 것을 알게 될 것이다. 페이지 테이블은 운영체제 가상 메모리에 저장할 수 있고 심지어 디스크에 스왑될 수 있다.
페이지 테이블에는 실제 무엇이 있는가
페이지 테이블 구성에 대해 살펴보자. 페이지 테이블은 가상 주소 (또는 가상 페이지 번호)를 물리 주소(물리 프레임 번호)로 매핑하는 데 사용되는 자료 구조이다. 임의의 자료 구조도 사용 가능하다.
가장 간단한 형태는 선형 페이지 테이블(linear page table)로 단순한 배열이다. 운영체제는 원하는 물리 프레임 번호(PFN)를 찾기 위하여 가상 페이지 번호(VPN)로 배열의 항목에 접근하고 그 항목의 페이지 테이블 항목(PTE)을 검색한다.
각 PTE에는 여러 비트가 존재한다.
Valid 비트는 특정 변환의 유효 여부를 나타내기 위하여 포함된다. 예를 들어, 프로그램이 실행을 시작할 때 코드와 힙이 주소 공간의 한쪽에 있고 반대쪽은 스택이 차지하고 있을 것이다. 그 사이의 모든 미사용 공간은 무효(invalid)로 표시되고, 프로세스가 그런 메모리를 접근하려고 하면 운영체제에 트랩을 발생시킨다. 운영체제는 그 프로세스를 종료시킬 확률이 높다.
Valid 비트는 할당되지 않은 주소 공간을 표현하기 위해 반드시 필요하다. 주소 공간의 미사용 페이지를 모두 표시함으로써 이러한 페이지들에게 물리 프레임을 할당할 필요를 없애 대량의 메모리를 절약한다.
Protection 비트는 페이지가 읽기/쓰기/실행 가능한지 여부를 나타낸다. 이 비트가 허용하지 않는 방식으로 페이지에 접근하려고 하면 운영체제에 트랩을 생성한다.
Present 비트는 이 페이지가 물리 메모리에 있는지 혹은 디스크에 있는지(즉, 스왑 아웃되었는지) 가리킨다.
Dirty 비트는 메모리에 반입된 후 페이지가 변경되었는지 여부를 나타낸다.
Reference 비트 혹은 Accessed 비트는 때때로 페이지가 접근되었는지를 추적하기 위해 사용된다. 또한, 어떤 페이지가 자주 접근되는지 결정하여 메모리에 유지되어야 하는 페이지를 결정하는 데에도 사용된다. 이 정보는 페이지 교체에서 중요하게 사용된다.
페이징 : 너무 느림
페이지 테이블의 크기가 메모리 상에서 매우 크게 증가할 수 있다. 페이지 테이블로 인해 처리 속도가 저하될 수 있다.
movl 21, %eax
주소 21에 대한 참조만 고려하고 명령어 반입에 대해서는 고려하지 않기로 하자. 이 예에서 하드웨어가 주소 변환을 담당한다고 가정한다. 원하는 데이터를 가져 오기 위해, 먼저 시스템은 가상 주소 21을 정확한 물리 주소 117로 변환해야 한다.
주소 117에서 데이터를 반입하기 전에 시스템은 프로세스의 페이지 테이블에서 적절한 페이지 테이블 항목을 가져와야 하고, 변환을 수행한 후, 물리 메모리에서 데이터를 탑재한다.
이렇게 하기 위해서 하드웨어는 현재 실행 중인 프로세스의 페이지 테이블의 위치를 알아야 한다. 당분간 하나의 **페이지 테이블 베이스 레지스터(page table base register)가 페이지 테이블의 시작 주소(물리 주소)를 저장한다고 가정하낟. 원하는 PTE의 위치를 찾기 위해 하드웨어는 다음과 같은 연산을 수행한다.
이 예제에서 VPN_MASK는 0x30(16진수 30 또는 이진수 110000)으로 설정되고, 전체 가상 주소에서 VPN 비트만 골라낸다. SHIFT는 오프셋 비트 수인 4로 설정되고 올바른 정수 가상 페이지 번호를 만들기 위해 VPN 비트를 오른쪽으로 이동시킨다. 가상 주소 21(010101)을 마스킹하면 010000이 되고, 쉬프트는 10 또는 우리가 원하는 가상 페이지 1로 변환한다. 우리는 이 값을 페이지 테이블 베이스 레지스터가 가리키는 PTE 배열에 대한 인덱스로 사용한다.
이 물리 주소가 알려지면 하드웨어는 메모리에서 PTE를 반입할 수 있고, PFN을 추출하고, 가상 주소의 오프셋과 연결하여 원하는 물리 주소를 만든다. 구체적으로, PFN을 SHIFT만큼 왼쪽으로 쉬프트하고 오프셋과 논리적 OR 연산을 하여 최종 주소를 만든다고 생각할 수 있다.
마지막으로, 하드웨어는 메모리에서 원하는 데이터를 가져와서 eax 레지스터에 넣을 수 있다. 이제 프로그램은 메모리로부터 값을 성공적으로 탑재하였다.
정리를 위하여,각 메모리 참조 시 일어나는 세부 동작을 살펴보자. 아래 그림은 기본적인 방식을 보여준다. 모든 메모리 참조에 대해 먼저 페이지 테이블에서 변환 정보를 반입해야 하기 때문에 반드시 한 번의 추가적인 메모리 참조가 필요하고, 엄청난 양의 작업이다. 메모리 참조는 비용이 비싸고 프로세스는 2배 이상 느려진다.
이제 우리가 반드시 해결해야 할 두 개의 진짜 문제를 알게 되었다. 하드웨어와 소프트웨어의 신중한 설계 없이는 페이지 테이블로 인해 시스템이 매우 느려질 수 있으며 너무 많은 메모리를 차지한다. 페이징이 메모리 가상화에 필요한 중요한 해결책처럼 보이지만, 먼저 이 두 가지 중요한 문제가 해결되어야 한다.
여담으로 현대 운영체제의 메모리 관리 서브시스템에서 가장 중요한 자료 구조 중 하나는 페이지 테이블이다. 일반적으로, 페이지 테이블은 가상-물리 주소 변환(virtual-to-physical address translation)을 저장하여 주소 공간의 각 페이지의 물리 메모리 위치를 알 수 있게 한다. 각 주소 공간은 이런 변환을 필요로 하기 때문에 페이지 테이블은 프로세스마다 하나씩 존재한다. 페이지 테이블의 정확한 구조는 하드웨어에 의해 결정되거나 융통성 있게 운영체제에 의해 관리된다. (예전 시스템에서는 하드웨어, 현대 시스템에서는 운영체제)
정리
- 페이징 Paging
메모리를 고정 크기 단위로 분할하는 메모리 관리 기법
장점 : 프로세스 주소 공간 사용 방식에 무관하여 유연하고, 단순하기에 빈 공간 관리가 용이, 외부 단편화 문제 해결 가능
단점 : 페이지 테이블 크기가 커지면 메모리 오버헤드가 증가하고, 추가적인 메모리 접근이 필요하기에 성능 저하가 일어날 수 있다.
- 페이지 Page
가상 메모리를 고정 크기로 분할한 단위
- 페이지 프레임 Page Frame
물리 메모리를 고정 크기로 분할한 슬롯
- 세그멘테이션 vs 페이징
가변 크기 vs 고정 크기 분할
- 가상 페이지 번호 Virtual Page Number (VPN)
가상 주소의 상위 비트
- 오프셋 Offset
페이지 내에서의 바이트 위치 (하위 비트)
- 물리 프레임 번호 Physical Frame Number (PFN)
물리 메모리 프레임 번호
- 물리 페이지 번호 Physical Page Number (PPN)
PFN과 동일
- 페이지 테이블 Page Table
가상-물리 주소 변환 정보를 저장하는 자료 구조
- 페이지 테이블 항목 Page Table Entry (PTE)
페이지 테이블의 각 항목
- PTE 구성 비트
- Valid 비트: 변환의 유효성 여부
- Protection 비트: 읽기/쓰기/실행 권한
- Present 비트: 페이지가 물리 메모리에 있는지 여부
- Dirty 비트: 페이지 수정 여부
- Reference/Accessed 비트: 페이지 접근 여부
참고