페이징

페이징 (Paging)

페이징은 논리주소 공간이 연속된 하나의 공간에 모두 모여 있어야 한다는 제약을 없앤다. 그러므로 페이징을 사용하면, 주 메모리에 올라와 있던 부분을 디스크로 내보낼 때 디스크 상에 이들을 연속적으로 수용할 수 있는 자유 공간을 찾기 위해서 부산을 떨 필요가 없다.

전통적으로 페이징을 구현하기 위한 기능은 하드웨어가 제공해 왔다. 그러나, 최근 디자인에서는 하드웨어와 운영체제의 긴밀한 연계를 통해서 페이징을 구현하고 있다.

1. 기본 방법

물리 메모리는 프레임(frame)이라고 불리는 고정 크기의 블록으로 나누어져 있다. 논리 메모리는 페이지(page)라 불리는 프레임과 같은 크기의 블록으로 나누어진다. 논리 메모리는 페이지(page)라 불리는 프레임과 같은 크기의 블록으로 나누어진다. 프로세스가 실행될 때 그 프로세스의 페이지는 보조 메모리로부터 가용한 임의의 주 메모리 프레임으로 적재된다. 보조 메모리는 메모리 프레임과 같은 크기의 블록들로 나누어져 있다.

위의 이미지는 페이징을 위한 하드웨어를 나타낸다. CPU에서 나오는 모든 주소는 페이지 번호(p)와 페이지 변위(d: offset) 두 부분으로 나누어진다. 페이지 번호는 페이지 테이블(page table)에 접근할 때 사용한다. 페이지 테이블은 주 메모리에 존재하는 페이지들의 기준 주소들을 가지고 있다. 이 페이지 주소에 페이지 변위를 더하면 메모리 장치로 전송될 물리 주소가 된다.

프레임 크기와 마찬가지로 페이지 크기도 하드웨어에 의해 결정된다. 페이지 크기는 대개 컴퓨터 구조에 따라 페이지 당 512B에서 16MB 사이이며, 2의 거듭 제곱이다. 만약 논리 주소 공간의 크기가 2^m이고,  페이지의 크기가 2^n이면 논리 주소의 논리 주소의 상위 (m-n) 비트는 페이지 번호를 나타내고, 하위 n 비트는 페이지 변위를 나타낸다.

주목할 만한 점은, 이 페이징 자체가 동적 재배치의 한 형태라는 것이다. 모든 논리 주소는 페이징 하드웨어에 의해 물리 주소로 사상된다. 게다가, 페이징 기법을 사용하면 외부 단편화가 발생되지 않는다. 임의의 가용 프레임이 프로세스에게 할당될 수 있기 때문이다. 대신, 이제는 내부 단편화가 발생된다. 할당은 항상 프레임의 정수 배로 할당되기 때문이다. 만약 프로세스가 페이지 경계와 일치하지 않는 크기의 메모리를 요구한다면, 마지막 페이지 프레임은 전부 사용되지 않는다.

평균적으로는 프로세스 당 반 페이지 정도의 내부 단편화가 예상된다. 이런 측면에서는 작은 페이지 크기가 바람직하다는 것을 알 수 있다. 그러나, 페이지 크기가 작아지면 그에 반비례하여 페이지 테이블이 커지게 되고, 테이블이 차지하는 공간은 낭비된다.

그동안, 페이지 크기는 프로세스, 데이터, 그리고 주 메모리가 커짐에 따라 함께 커져 왔다. 현재는 보통 페이지 크기가 2~8KB이다. 어떤 CPU나 OS 커널은 여러 크기의 페이지를 사용할 수 있게 지원한다. 예를 들어, Solaris는 4KB, 8KB 두 가지 페이지를 허용한다. 또한 2018년 현재에는 시스템을 운영하는 도중에도 페이지 크기를 정하도록 하는 연구들도 진행 중이다.

프로세스가 실행되기 위해 도착하면, 그 프로세스의 크기가 페이지 몇 개분에 해당하는가를 조사한다. 각 사용자 페이지는 한 프레임씩을 필요로 한다. 즉, 한 프로세스가 n개의 페이지를 요구한다면, 메모리에서 이용할 수 있는 프레임이 n개 있어야 한다. n개의 프레임을 사용할 수 있다면, 프레임들이 프로세스에 할당된다. 그런 다음, 프로세스의 첫 페이지가 할당된 프레임들 중 하나에 적재되고, 그 프레임 번호가 페이지 테이블에 기록된다. 그 다음 페이지는 또 다른 프레임에 적재되고, 그 프레임 번호가 페이지 테이블에 기록된다.

페이징의 가장 중요한 특징은 메모리에 대한 사용자가 생각하는 메모리와 실제 물리 메모리를 명확하게 분리한다는 사실이다. 사용자 프로그램은 메모리가 하나의 연속된 공간이며, 메모리에는 이 플그램만 있다고 생각한다. 그러나, 실제로 프로그램은 물리 메모리 여러 곳에 프레임 단위로 산재되어 있고, 이 물리 메모리는 많은 다른 프로그램을 적재하고 있다. 사용자가 생각하는 메모리와 실제 물리 메모리의 차이는 주소 변환 하드웨어에 의해 가려진다. 사용자 프로그램이 만들어내는 논리 주소는 물리 주소로 변환된다. 이 사상은 사용자에게는 안 보이고 운영체제에 의해 조정된다.

정의에 따라 사용자 프로세슨 자신이 소유하지 않은 메모리는 접근할 수 없다. 페이지 테이블을 통하지 않고서는 다른 공간을 접근할 방법이 없으며, 페이지 테이블은 그 프로세스가 소유하고 있는 페이지들만을 가리키고 있기 때문이다.

운영체제는 메모리를 관리하기 때문에 물리 메모리의 자세한 할당에 대해 파악하고 있어야 한다. 즉, 어느 프레임이 할당되어 있고, 어느 프레임이 사용 가능한지, 총 프레임은 몇 개나 되는지 등을 알아야 한다. 이런 정보는 일반적으로 프레임 테이블(frame table)이라는 자료구조에 저장되어 있다. 프레임 테이블은 각 프레임 당 하나의 항목을 가지고 있으며, 프레임이 가용한지, 할당되었는지, 그리고 할당되었다면  어느 페이지에게 할당되었는지를 나타낸다.

또한, 운영체제는 모든 프로세스들이 사용자 공간에 동작한다는 것을 알고 있어야 하고, 모든 논리 주소는 물리 주소로 전환될 수 있어야 한다. 사용자가 시스템 호출을 호출해서 매개 변수로 메모리 주소(예를 들어, 자신의 영역 내로 입력할 버퍼의 주소)를 전달하면 제대로 전환하여 정확히 그 물리 주소를 찾아가야 한다. 이를 위해 운영체제는 각 프로세스에 대해 페이지 테이블의 복사본을 갖고 있어야 한다. 이 복사본은 운영체제가 수작업으로 논리 주소를 물리 주소로 변환할 때마다 사용된다. 또한, 프로세스가 CPU를 할당받았을 때 하드웨어 페이지 테이블을 설정하는데 CPU 디스패처가 사용된다. 따라서, 페이징은 문맥 교환 시간을 증가시킨다.

2. 하드웨어 지원 (Hardware Support)

페이지 테이블이 작을 경우에는 레지스터에 저장하여 속도를 올릴 수 있지만 대부분 컴퓨터는 페이지 테이블이 크다. 그래서 페이지 테이블을 메모리에 올려두고 페이지 테이블 기준 레지스터(PTBR - Page Table Base Register)를 이용하여 페이지 테이블에 접근한다. 다른 페이지를 사용할려면 이 레지스터만 변경하면 된다. 다만 이 방식은 특정 위치에 대한 정보를 얻기 위해서 메모리에 2번 접근을 해야한다. 이러한 시간을 줄이기 위해 TLB(Table Look-aside Buffer)라는 하드웨어 캐시가 사용된다.

TLB는 매우 빠른 연관 메모리(associative memory)로 구성된다.TLB 내의 각 항목은 키-값 (key-value)의 한 쌍으로 구성된다. TLB에 페이지를 찾아달라고 용청이 들어오면, TLB 내의 모든 내부 키(페이지 번호)와 찾고자하는 페이지의 번호를 비교한다. 페이지 번호가 같은 것이 발견되면 그에 대응하는 프레임 번호를 알려준다. 이 탐색의 속도는 매우 빠르지만 하드웨어가 매우 비싿.

또 어떤 TLB는 저장된 페이지가 어느 프로세스의 페이지인지 알려주는 ASIDs(Address-Space Identifiers)를 저장하여 복수의 프로세스들의 페이지를 동시에 저장한다. 만약 ASIDs가 없다면 프로세스가 변경될 때마나 프로세스를 잘못된 접근에 대한 보호를 위해 TLB는 전부 flush가 되어야한다. 이 ASIDs는 그 TLB 항목이 어느 프로세스에게 속한 것인지를 알려주며, 그 프로세스의 주소 공간을 보호하기 위해 사용된다.

TLB가 사용되었을때 메모리 접근 시간은 (TLB 적중률) * (메모리 접근시간) + (1-TLB 적중률) * (메모리 접근시간 X 2)이다.

3. 보호 (Protection)

페이지화 된 환경에서 메모리 보호는 각 프레임과 연관된 보호 비트(protection bits)에 의해 구현된다. 이 비트들은 보통 페이지 테이블에 포함되어 있다. 한 비트는 이 페이지가 읽고 쓰기 또는 읽기 전용(read-only)임을 정의할 수 있다. 메모리에 대한 모든 접근은 페이지 테이블을 거치므로 이때 주소 전환과 함께 읽기 전용 페이지에 쓰기 연산이 실행되지 않도록 검사하는 작업도 실행된다. 읽기 전용 페이지에 대해 쓰기를 시도하면, 운영체제에게 하드웨어 트랩이 전달된다(혹은 메모리 보호 위반 - memory protection violation).

페이지 테이블의 각 항목에는 유효/무효(valid/invalid)라는 하나의 비트가 더 있다. 이 비트가 유효로 설정되면 관련된 페이지가 프로세스의 합법적인 페이지임을 나타내며, 이 비트가 무효로 설정되면 그 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타낸다. 불법적인 주소는 유효-무효 비트를 사용하여 잡아낼 수 있다. 운영체제는 이 비트를 이용해서 그 페이지에 대한 접근을 허용하든지 또는 허용하지 않든지 할 수 있다.

프로세스가 자신의 모든 주소 범위를 늘 사용하는 경우는 드물다. 사실 많은 프로세스들은 일정한 시각에 일부분만을 집중적으로 사용한다. 이런 경우에 모든 페이지에 페이지 테이블 항목을 하는 것은 낭비일 것이다. 몇몇 시스템은 페이지 테이블의 크기를 나타내기 위해 페이지 테이블 길이 레지스터(PTLR - Page Table Length Register)를 제공한다. 프로세스가 제시한 주소가 유효한 범위 내에 있는지를 확인하기 위해 모든 논리 주소 값이 PTLR 값과 비교된다. 이러한 검사에서 오류가 나타나면 트랩을 발생시킨다.

4. 공유 페이지 (Shared Pages)

페이징의 또 다른 장점은 공통 코드를 쉽게 공유할 수 있다는 점이다. 이 점은 시분할 환경에서 특히 중요하다. 40명의 사용자를 지원하는 시스템을 생각해보자. 각각의 사용자는 문서 편집 프로그램을 실행하려고 한다. 만약 문서 편집기가 150KB의 코드와 50KB의 데이터 공간으로 구성되어 있다면, 40명의 사용자를 지원하기 위해서는 8,000KB의 메모리 공간이 필요하다. 그러나 만약 재진입 가능 코드(reentrant code 또는 pure code)라면 여러 사용자가 공유할 수 있다.

위의 이미지는 세 개의 편집기 페이지(한 페이지 크기는 50KB)가 세 개의 프로세스 사이에서 어떻게 공유되고 있는지 보여주고 있다.

재진입 가능 코드는 실행하는 동안 절대로 변하지 않는다. 따라서 두 개 또는 그 이상의 프로세스들이 동시에 같은 코드를 실행할 수 있다. 이때 코드 부분은 서로 공유하더라도 각각의 프로세스들은 레지스터들의 복사 값과 프로세스가 실행에 필요한 데이터들을 저장하는 데이터 저장소를 따로 가지고 있다. 물론 두 개의 서로 다른 프로세스의 데이터는 다르다.

이렇게 하면 단 하나의 편집기 코드 사본이 물리 메모리에 존재해도 된다. 각각의 사용자 페이지 테이블은 같은 물리 주소를 가리키게 된다. 그러나데이터는 서로 다른 프레임에 사상한다. 따라서, 40명의 사용자를 지원하기 위해서 150KB 크기의 단 하나의 편집기 코드 사본과 50KB 크기의 40개 데이터 복사본만 있으면 된다. 전체 필요한 공간은 이제 8,000KB가 아닌 2,150KB가 된다. 이는 매우 커다란 절약이다.

컴파일러, 윈도우 시스템, 실시간 라이브러리, 데이터베이스 시스템 등과 같이 자주 사용되는 프로그램도 공유 가능하다. 공유되기 위해서는 코드가 반드시 재진입 가능해야 한다. 공유 코드의 읽기전용 속성은 코드가 올바르게 작성되어야 유지될수 있게 해서는 안되고, 운영체제가 이를 강제해야 한다.