[OS] 메인 메모리(2) - 페이징 기법

 

서론

---

지금까지 논의된 메모리 관리는 프로세스의 물리 공간이 연속적이어야 했습니다. 이제 프로세스의 물리 주소 공간이 연속되지 않아도 되는 메모리 관리 기법인 페이징에 대해 정리해 보겠습니다. 페이징은 외부 단편화 문제를 해결해 주기 때문에 대형 서버용 시스템에서 모바일 장치용 시스템에 이르기까지 대부분의 운영체제에서 다양한 형태의 페이징이 사용됩니다. 페이징은 운영체제와 컴퓨터 하드웨어 간의 협력을 통해 구현됩니다.

 

이 장의 목표
1. 논리 주소와 물리 주소의 차이점과 주소를 변환할 때 MMU(메모리 관리 장치)의 역할을 정리해 본다.(이전 게시글)
2. 메모리를 연속적으로 할당하기 위해 최초, 최적, 및 최악 접합 전략을 적용해 본다.(이전 게시글)
3. 단편화에 대해 알아보고 단편화의 두 가지 종류 내부 및 외부 단편화의 차이점을 정리해 본다. (이전 게시글)
4. 외부 단편화 문제를 해결하기 위한 페이징 기법을 살펴본다. (현재 게시글)
5. TLB(translation look-aside buffer)가 포함된 페이징 시스템에서 논리 주소를 물리 주소로 변환한다. (다음 게시글)
6. 계층적 페이징, 해시 페이징 및 역 페이지 테이블을 설명한다. (다음 게시글)

 

페이징(Paging)

---

페이징의 기본 개념은 아래와 같습니다.

• 물리 메모리는 프레임(frame)이라 불리는 같은 크기 블록으로 나눈다.
• 논리 메모리는 페이지(page)라 불리는 같은 크기의 블록으로 나눈다.

이러한 다소 간단한 아이디어가 엄청난 기능을 수행하고 폭넓은 영향을 끼치게 되었습니다. 예를 들어 논리 주소 공간은 문리 주소 공간으로부터 완전히 분리되었기 때문에 물리 메모리의 크기가 2^64 바이트보다 적게 장착된 시스템에서도 프로세스는 64비트로 이루어진 논리 주소 공간을 사용할 수 있습니다.

 CPU에서 나오는 모든 주소는 아래와 같이 페이지 번호(p)와 페이지 오프셋(d: offset) 두 개의 부분으로 나누어집니다.

페이지 번호는 프로세스 페이지 테이블(page table)을 액세스 할 때 사용됩니다. 아래의 이미지를 기준으로 정리해 보겠습니다.

(좌) 페이징 하드웨어 (우)논리 메모리와 물리 메모리의 페이징 모델

페이지 테이블은 물리 메모리의 각 프레임의 시작 주소를 저장하고 있으며 오프셋은 참조되는 프레임 안에서의 위치입니다. 따라서, 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 됩니다. 메모리의 페이징 모델은 우측 이미지를 확인하시면 됩니다.

 CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 위해 MMU가 취한 단계를 정리해보면 아래와 같습니다.

1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용한다.
2. 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.

오프셋 d는 변하지 않기 때문에 대체되지 않으며, 프레임 번호와 오프셋은 이제 물리 주소를 구성합니다.

 프레임 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해집니다. 페이지 크기는 2의 거듭제곱으로, 일반적으로 컴퓨터 아키텍처에 따라 페이지당 4 KB와 1 GB 사이입니다. 페이지 크기로 2의 거듭제곱을 선택하면 논리 주소를 페이지 번호 및 페이지 오프셋으로 쉽게 변환할 수 있습니다. 논리 주소 공간의 크기가 2^m이고 페이지 크기가 2^n바이트인 경우 논리 주소의 상위 m-n 비트는 페이지 번호를 지정하고 n 하위 비트는 페이지 오프셋을 지정합니다. 따라서 논리 주소는 다음과 같습니다.

여기서 p는 페이지 테이블에 대한 인덱스로 사용되며, d는 페이지 내에서의 오프셋으로 사용됩니다.

 소규모이지만 구체적으로 아래 이미지의 메모리 예제로 생각해 보겠습니다.

4바이트 페이지 크기를 가진 32바이트 메모리에서의 페이징 예

위 이미지의 논리 주소에서 n = 2, m = 4입니다. 4B의 페이지 크기와 32B의 물리 메모리(8페이지)를 사용하여 프로그래머가 보는 메모리가 물리 메모리로 매핑되는 예를 살펴보겠습니다.

• 논리 주소 0은 페이지 0, 오프셋 0입니다.
• 페이지 테이블은 색인(indexing)으로 찾아서 페이지 0이 프레임 5에 있다는 것을 알아냅니다.
• 그래서 논리 주소 0은 실제 주소 20(5*4+2)으로 매핑됩니다. 
• 논리 주소 3(페이지 0, 오프셋 3)은 실제 주소 23((5*4)+3)으로 매핑됩니다. 
• 논리 주소 4는 페이지 테이블에 의해 페이지 1, 오프셋 0이고, 페이지 1은 오프셋 6으로 매핑됩니다. 따라서 실제 주소 24((6*4)+0)로 매핑됩니다.
• 논리 주소 13은 실제 주소 9로 매핑됩니다.

페이징 자체는 일종의 동적 재배치라는 것을 알 수 있습니다. 모든 논리 주소는 페이징 하드웨어에 의해 실제 주소로 바인딩됩니다. 페이징을 사용하는 것은 각 메모리 프레임마다 하나씩 기준(또는 재배치) 레지스터를 테이블로 유지하는 것과 유사합니다.

 페이징 기법을 사용하면 외부 단편화가 발생하지 않습니다. 모든 놀고 있는 프레임이 프로세스에 할당될 수 있기 때문입니다. 그러나 이제는 내부 단편화가 발생합니다. 할당은 항상 프레임의 정수배로 할당되기 때문입니다. 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면, 마지막 페이지 프레임은 전부 할당되지 않습니다. 예를 들어, 페이지 크기가 2,048B이고 프로세스가 72,766B를 요구한다면 35개의 페이지 프레임을 할당하고 1,086B가 남습니다. 36번째로 할당되는 페이지 프레임은 2,048 - 1,986 = 962B의 내부 단편화가 발생하게 됩니다. 최악의 경우 프로세스가 n개의 페이지와 추가로 1B를 요구할 수 있습니다. 그 결과 n + 1번째 프레임은 거의 모든 프레임이 내부 단편화가 됩니다.

메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만 페이지 테이블을 확인하기 위해 메모리 액세스를 함으로써 시간이 더 느려질 수도 있습니다. 따라서 다음 게시글에서는 이러한 문제를 해결하는 TLB(translation look-aside buffers)라고 불리는 특수한 소형 하드웨어 캐시에 대해 알아보겠습니다.

[OS] 메인 메모리(3) - TLB(translation look-aside buffers)