[OS] 페이징

페이징

외부 단편화로 인한 메모리 낭비는 매우 심하다는 것을 이전 포스트에서 살펴보았다. Compaction을 사용하면 단편화는 해결할 수 있지만 그로인해 발생하는 오버헤드와 비효율적인 성능으로 사용하기는 어렵다. 그래서 등장한 것이 페이징이다. 페이징은 hole을 가지고 해결하는 것이 아닌 프로세스를 작은 크기로 나눠 외부 단편화를 해결하려 했다.

 

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

 

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

 

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

 

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

어야 한다.

 

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

1. 주소 변환

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

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

논리주소를 물리주소로 변환하기 위해서 페이지 번호(p)는 페이지 테이블의 인덱스 값이고 p에 해당되는 테이블 내용은 메모리의 프레임 번호이다. 변위(d)는 불변값이다. 이 규칙에 대한 예제를 살펴보자.

 

• Page size = 16bytes
• Page Table : 5, 3, 2, 8, 1, 4
• 논리 주소 50번지는 물리주소 몇 번지인가?

위 그림은 프로세스 P가 메모리에 할당된 모습이다. CPU가 50번지에 접근하려 한다. 그러면 페이지 테이블의 정보를 읽기 위해 논리 주소를 p, d로 나눠야 한다.

 

d 는 페이지 크기에 따라 달라지는데, 현재 페이지 크기는 16byte이다. 이는 2^4로 d=4이다.

p는 d를 제외한 나머지 크기이다.

 

그러면 실제로 p, d를 계산해보자. 현재 논리 주소는 50이며, 이진수로 나타내면 110010이다. 먼저 d는 4이므로 이 이진수의 뒤에서 4칸이 d이다. d를 제외한 나머지 2칸이 p가 된다.

 

50 = 110010
p = 11
d = 0010

 

p는 이진수로 11이고 십진수로 3이다. 즉, 페이지 테이블의 페이지 번호 3을 가리킨다. 페이지 3번에 해당하는 프레임 번호는 8이므로 물리주소를 구성하는 f값은 8이 된다.

 

f = 1000
d = 0010
물리주소 = 10000010

 

최종적으로 물리주소는 f와 d로 구성되어 있으므로 물리주소는 이진수로 10000010 이 되고, 십진수로 130번지가 된다. 즉 변위는 2이므로 8번째 프레임의 시작주소는 128번지(16*8)가 된다. 

연속메모리 할당을 하면서 외부 단편화가 발생하여 이를 해결하기 위해 페이징 기법이 나왔다. 하지만 페이징은 외부 단편화가 아닌 내부 단편화가 발생한다.

2. 내부 단편화

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

 

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

 

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

3. 페이지 테이블 만들기

페이지 테이블을 만드는 방법은 여러 가지가 있다. 먼저, CPU 내부에 페이지 테이블을 만들 수 있다. CPU 내부의 기억장치는 레지스터로 여러 개의 레지스터로 페이지 테이블을 만드는 것이다. CPU 내부에 페이지 테이블을 만들면 장점은 주소 변환 속도가 빠르다. 하지만 단점은 CPU 내부에 사용할 수 있는 레지스터는 한정되어 있어 페이지 테이블의 크기가 매우 제한적이다.

 

반대로, 페이지 테이블을 메모리 내부에서 만들 수도 있다. 메모리 내부에 만드는 것의 장단점은 CPU와 정 반대이다. 즉 장점은 페이지 테이블의 크기에 제한이 없다는 것, 단점은 주소 변환 속도가 느리다는 것이다. CPU는 프로세스의 주소에 접근하기 위해 메모리에 위치한 페이지 테이블에 한 번, 실제 주소로 접근하는데 한 번해서 메모리에 총 2번 접근해야 하므로 속도 역시 2배로 느려진다.

 

페이지 테이블을 CPU에 만들때나 메모리에 만들때 장단점이 확실하므로 이를 해결하기 위해 페이지 테이블도 캐시로 만들어 해결했다. 페이지 테이블을 별도의 칩(SRAM)으로 만들어 CPU와 메모리 사이에 위치시키는 것이다 이러한 테이블을 TLB(Translation Look-aside Buffer)라고 부른다. 이는 CPU 보다 변환 속도는 느리고 메모리보다 테이블 크기는 작지만 CPU 보다 테이블 크기가 크고 메모리보다 변환 속도가 빠르다.

 

TLB는 캐시와 역할이 동일하므로, 실제 전체 페이지 테이블은 메모리에 위치해 있고 테이블의 일부를 TLB에 가져와 사용한다. 그러므로 TLB에 유효한 페이지가 있을 때와 없을 때의 속도차이가 발생한다. 

 

그렇다면 TLB의 효율을 알아보기 위해 Effective Memory Access Time을 계산해보자.

• 메모리 읽는 시간(Tm) = 100ns
• TLB 읽는 시간(Tb) = 20ns
• TLB에 유효한 페이지 엔트리가 있을 확률(hit ratio) = 80%

먼저 EMAT의 정형화된 식을 보자.

EMAT = h(Tb + Tm) + (1 - h)(Tb + Tm + Tm), h는 hit ratio

 

실제 유효한 메모리에 접근하는 시간은 위와 같다. TLB에 유효한 페이지가 있다면 TLB를 읽는 시간과 실제 메모리를 읽는 시간만 있으면 된다. 하지만 TLB에 유효한 페이지가 없다면 이를 다시 메모리에서 가져와야 하므로 메모리를 총 2번 읽어야한다.

 

예제를 계산해보면 0.8 * (20 + 100) + 0.2 * (20 + 100 + 100) = 140ns이다. hit ratio는 실제로 평균 95% 이상이므로 충분히 효율적으로 동작한다고 볼수 있다.

4. 보호와 공유

4.1 보호(Protection)

모든 주소는 페이지 테이블을 경유하므로, 테이블을 이용하여 보호기능을 수행할 수 있다. 대표적으로 페이지 테이블 마다 r(read), w(write), x(execute) 비트를 두어, 해당 비트가 켜져있을 때, 그 수행이 가능하도록 한다.

 

위 그림은 페이지 테이블에 r,w,x비트를 추가한 모습이다. 만약, 1번 페이지 엔트리처럼 쓰기 비트가 꺼져있는 페이지에 쓰기 작업을 시도하면 CPU에 인터럽트가 발생하여 ISR에서 강제로 해당 프로세스를 종료 시킨다.

4.2 공유(Sharing)

공유는 메모리 낭비를 방지하기 위함이다. 같은 프로그램을 쓰는 복수개의 프로세스가 있다면 프로세스의 메모리는 code + data + stack 영역으로 나뉘는데 프로그램이 같다면 code 영역은 같을 것이다. 그러므로 하나의 code 영역을 복수 개의 프로세스가 공유하여 메모리 낭비를 줄이는 것이다. 단, code가 공유되려면 code가 변하지 않는 프로그램이어야 한다. 이를 non-self-modifying code = reentrant code(재진입가능 코드) = pure code 라고 한다.