[Operating System] 페이징(Paging)이란?

이번 주제는 운영체제의 페이징입니다.
본격적으로 페이징에 대해 공부하기 전, 페이징이 왜 필요한지?에 대해서 먼저 이해를 해보도록 하겠습니다.

모든 프로그램은 프로세스가 되기 위해 메인 메모리를 할당 받아야 합니다.
그리고 페이징이라는 개념이 등장하기 전, 하나의 프로세스는 무조건 연속적인 메모리 영역을 할당 받았습니다. 예를들어서 아래와 같이 말이죠.

현재 메모리에 OS, Process 5, Process 8, Process 2가 올려져 있다고 보시면 됩니다. 아직까지는 큰 문제가 보이질 않습니다.
이 상황에서 Process 5가 종료되어 할당받은 메모리를 해제하게 되었습니다.

메모리 영역에 구멍이 생긴 것을 볼 수 있습니다. 이렇게 연속적인 프로세스 할당으로 인해 메모리에 생긴 구멍을 'Hole'라고 부르며, 이 영역은 다시 다른 프로세스에게 할당할 수 있는 메모리 영역입니다.

Process 5가 종료된 이후 Process 2가 종료되었다고 합니다. 그러면 현재 메모리의 상태는 아래의 그림과 같을 것입니다.

커다란 Hole이 두개 생겼습니다. 이제 문제가 발생하는데요,

새로운 Process 1이 메모리 영역을 사용받으려고 합니다. 하지만, 프로세스는 메모리에 연속적으로 할당될 수 있다고 했죠.
Process 1이 할당 받고자 하는 메모리 공간의 크기만큼 현재 메모리에는 여유가 없습니다. 그래서 Process 1은 메모리 영역에 올라갈 수가 없고 대기하게 됩니다.

만약 위의 그림과 같이 Process 8이 남은 공간을 최대한 아껴쓸 수 있다면, Process 1은 실행될 수 있습니다. 다시말해 메모리 공간은 여유가 있음에도, 프로세스는 메모리를 연속적으로 할당받아야 한다는 제한때문에 Process 1이 실행되지 못하는 상황이 발생한 것이죠. 그리고 이는 명백하게 컴퓨터 자원이 낭비되는 문제상황입니다.

위에서 본 예시와 같이 Hole이 생기면서 메모리가 낭비되는 현상을 '외부 단편화(external fragmentation)'라고 부릅니다.
그리고 이 외부 단편화 문제를 해결하기 위한 기법이 이번 글의 주제인 '페이징'입니다.

페이징은 프로세스가 할당받는 물리 메모리 공간이 연속되지 않아도 되는 메모리 관리 기법이며, 자연스럽게 외부 단편화 문제를 해결할 수 있습니다. 이제 페이징이 어떻게 동작하는지 알아보겠습니다.

페이징 기법이 추가되면서 기존 컴퓨터 시스템에서 크게 3가지의 변화가 생겼는데요, 아래와 같습니다.

• 물리 메모리는 '프레임(frame)'이라 불리는 같은 크기 블록으로 나누어졌습니다.
• 논리 메모리는 '페이지(page)'라 불리는 같은 크기 블록으로 나누어졌습니다.
• CPU에서 나오는 모든 주소는 '페이지 번호(p)'와 '페이지 오프셋(d : page offset)' 부분으로 나누어졌습니다.

이러한 변화를 그림으로 나타내면 아래와 같고 이제 이해할 준비가 끝났습니다.

그림을 보면 지금까지 등장한적이 없는 '페이지 테이블'이 보입니다. 페이지 테이블은 물리 메모리의 각 프레임 시작 주소를 저장하고 있고, 분할된 논리 주소의 오프셋은 참조되는 프레임 안에서의 위치를 나타냅니다.

여기서 한가지 의문을 가질 수 있는데요, 이전에 살펴본 MMU 는 어디갔을까요?
MMU의 역할은 '논리 주소를 물리 주소로 매핑하는 하드웨어'라고 언급했었는데, 페이징이 추가되어도 MMU의 역할은 변하지 않습니다.
사실 위의 그림에서 논리 주소를 물리 주소로 변환하는 과정들은 모두 MMU가 수행하며, 논리 주소를 물리 주소로 변환하기 위해 MMU가 수행하는 단계를 요약하면 아래와 같습니다.

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

그림에서 알 수 있듯이 오프셋 d는 변하지 않기에 MMU는 오프셋에 별도의 처리를 하지 않으며, 위의 단계를 거쳐 물리 주소를 구성합니다.

이렇게 페이징의 큰 아키텍처를 이해하게 되었는데요, 페이징을 적용했을때 논리 메모리와 물리 메모리의 관계는 어떻게 변할까요? 살펴봅시다.

페이징 기법 덕분에 더이상 프로세스가 연속적인 메모리 영역을 차지하지 않아도 되고, 모든 놀고 있는 프레임이 프로세스에 할당될 수 있으므로 외부 단편화가 발생하지 않습니다.

그러나 이제는 '내부 단편화'가 발생할 수 있습니다. 모든 프레임 크기는 항상 정수배로 할당되며, 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면 마지막 페이지 프레임이 전부 할당되지 않기 때문입니다.

그렇다면 페이지 크기가 작을 수록 내부 단편화 문제가 감소한다는 것을 유추할 수 있습니다. 하지만, 페이지 크기가 작아지면 페이지의 개수가 증가할 것이고 페이지 테이블의 크기는 증가할 것입니다. 이러한 이유로 적절한 크기로 페이지 크기를 설정해야 하는데 현대의 일반적인 페이지 크기는 4KB 혹은 8KB로 설정됩니다.

페이지 테이블은 어디에 저장될까?
페이지 테이블은 프로세스별로 유일하게 가지고 있는 자료구조입니다. 그렇다면 이 페이지 테이블은 어디에 저장될까요?
가장 단순하게 생각해보면, 페이지 테이블에 대한 포인터를 PCB에 저장하면 될것 같습니다. 하지만, 이 접근 방식은 기존 Context Switching 시간에 레지스터의 페이지 테이블을 교체하는 시간을 더하게 됩니다. 쉽게 말해 문맥 교환 시간이 증가한다는 것이죠.

그래서 'TLB(Translation Look-aside Buffers)'라고 불리는 특수한 소형 하드웨어 캐시를 사용하는 해결방법이 등장했습니다.
여기까지 페이징이 어떤 문제를 해결하기 위해 등장했는지, 어떻게 논리 주소를 물리 주소로 변환하는지에 대해 알아봤습니다. 하지만, 페이징 기법을 사용하기 위해서는 페이징 테이블이 필요하다는 사실을 알게 되었고, 페이징 테이블을 효율적으로 관리하기 위해 TLB라는 하드웨어가 사용된다는 사실을 알게 되었습니다.

TLB에 대한 내용은 다음 포스팅에서 다루도록 하겠습니다. 잘못된 내용이 있다면 지적 및 피드백 해주시면 감사하겠습니다.

Ref : Operating System Concept 10