페이징을 아라보자

1. 페이징(Paging)

외부 단편화로 인한 메모리 낭비는 매우 심하다. Compaction을 사용하면 외부 단편화는 해결할 수 있지만, 그로 인해 발생하는 오버헤드와 비효율적인 성능으로 사용하기는 어렵다. 그 이후에 연구를 통해 나온 것이 페이징이다. 페이징은 hole을 가지고 해결하려 한 것이 아니라 프로세스를 작은 크기로 나눠서 외부 단편화를 해결하려고 하였다.

 

페이징은 프로세스를 일정한 작은 크기로 나누는데, 프로세스뿐아니라 hole도 같은 크기로 나눈다. 이러한 작은 조각들의 크기를 맞춰서 메모리에 할당한다. 하지만, 하나의 프로세스는 연속적인 동작을 수행하는데 이를 작은 조각으로 나누어서 여기저기 흩어진다면 프로세스가 정상적으로 동작할까?

 

메모리상에 여러 곳에 흩어진 프로세스를 수행하기 위해 CPU를 속여야한다. 이전 다중프로그래밍을 살펴봤을 때 MMU를 통해 논리 주소와 물리 주소를 나눠서 사용한다고 했었다. 이 역시 CPU를 속이는 행동이다. 실제 메모리는 전혀 연속적이지 않는데, CPU는 연속적으로 사용하고 있다는 것을 보장받으며 정상적으로 수행한다.

페이징으로 작은 크기로 나눈 것도 위와 같은 방법으로 할 수 있다. 만약 50byte 크기의 프로세스가 있다고 하자. 페이징의 크기는 각 10byte로 나눈다.

위 그림과 같이 프로세스 P1은 5개의 페이지로 나눌 수 있다. 이를 메인 메모리 5곳에 나눠서 할당하였다. CPU는 논리 주소로 프로그램이 설정한대로 연속적인 주소값으로 명령을 내리고 이는 메모리로 가기전에 각 페이지의 실제 메모리 주소가 저장되어 있는 테이블에서 물리 주소로 변경되어야 한다.

프로세스를 나눈 조각을 page 라 하고, 메모리를 나눈 조각을 frame 이라 한다. 프로세스는 페이지의 집합이고, 메모리는 프레임의 집합이다. 프로세스를 정상적으로 사용하기 위해 MMU의 재배치 레지스터를 여러개 사용해서 위의 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이러한 여러 개의 재배치 레지스터를 페이지 테이블(Page Table) 이라 한다.

1.1. 주소 변환(Address Translation)

페이징 기법을 사용하기 위해서는 여러 개로 흩어진 페이지에 CPU가 접근하기 위해서 페이지 테이블을 통해 주소를 변환해야 한다.

1.1.1 논리 주소(Logical address)

CPU가 내는 주소는 2진수로 표현된다. 이 주소가 m비트로 표현된다고 가정하자. 여기서 하위 n비트는 오프셋(offset) 또는 변위(displacement)라고 한다. 그리고 상위 m-n 비트는 페이지의 번호에 해당한다.(n = d, m-n = p)

논리주소를 물리주소(physical address)로 변환하기 위해서 페이지 번호(p)는 페이지 테이블의 인덱스 값이고, p에 해당되는 테이블 내용은 메모리의 프레임 번호이다. 변위(d)는 변하지 않는 값이다. d는 페이지 크기에 따라 달라진다. 만약 현재 페이지 크기를 16byte이라고 한다면, 이는 2^4이므로 d = 4 이다.

만약 논리주소가 50번째로 주어진다면, 50=110010 이고, page size가 16byte라 주어졌을 때, 4자리를 제외한 p=11이고 d=0010 이다.

1.1.2 동작 예시

위 그림을 보면, 어떻게 동작하는 지 한눈에 확인 할 수 있다. 우리가 해야할 일은, 논리 주고가 들어왔을 때, 이것을 page, displacement로 나누고, page 변수를 frame 변수로 바꿔주는 page table을 통과하여 나온 값을 가지고 물리 주소를 찾으면 된다.

위 그림으로 부터 따라해 볼 수 있다. p와 d만 잘 생각하면 쉬운 아이디어임을 알 수 있다. 이 페이징으로부터 연속 메모리 할당을 하면서 외부 단편화가 발생하는 문제는 해결했다.

1.2 내부단편화(Internal Fragment)

페이징은 외부 단편화가 아닌 내부 단편화가 발생한다. 내부단편화는 프로세스 크기가 페이지 크기의 배수가 아닐 경우, 마지막 페이지는 한 프레임을 다 채울 수 없다. 이로 인해 발생하는 공간은 결국 메모리 낭비로 이어진다.

예를 들어, 15bytes 크기의 프로세스 P가 있다. 페이지 크기(프레임 크기)를 4bytes라 하면, P를 페이지로 나눈 결과인 4, 4, 4, 3 의 크기로 총 4개의 페이지가 만들어진다. 여기서 마지막 3bytes 페이지는 프레임 크기보다 1byte작으므로, 이 만큼 메모리 공간이 비게 된다. 이렇게 비어진 공간은 프로세스 P에서도 쓰지 않고, 다른 프로세스에서도 쓰지 못하는 낭비되는 공간이 된다.

내부단편화는 해결할 방법이 없다. 하지만 내부단편화는 외부단편화에 비해 낭비되는 메모리 공간은 매우 적다. 내부단편화의 최대 낭비되는 크기는 page size - 1 이 된다.(외부 단편화는 최대 전체 메모리의 1/3이 낭비된다고 이전에 살펴봤다.) 이는 무시할 정도로 작은 크기이다.