[11] 페이징

KOCW - 양희재 교수님 강의를 기반으로 운영체제 정리

프로세스를 적재하기 위한 연속된 메모리를 확보하는 문제는 지속적으로 연구되어 왔습니다. 이전 시간에는 하나의 프로세스를 적재하기 위해 연속된 메모리를 확보하는 다양한 방법에 대해서 알아보았습니다. 결론적으로 외부 단편화는 언제든지 일어날 수 있으며 뚜렷한 해결책을 찾지 못하고 글이 마무리 되었습니다.

페이징

페이징은 발상의 전환을 하여 연속된 메모리를 확보하지 말고 프로세스를 일정 크기(페이지)로 잘라서 사용하자는 아이디어에서 출발했습니다.

• 프로세스는 페이지(page)의 집합 : process를 일정 단위로 잘라서 사용

• 메모리는 프레임(frame)의 집합 : Memory(hole)를 일정 단위로 잘라서 사용

프로세스와 메모리를 일정 단위로 잘라서 같은 크기를 갖도록 설정합니다. 그 후 MMU의 Relocation 레지스터를 여러개 두어 CPU의 입장에서 프로세스가 연속적으로 할당되어 있는것과 같이 속일 수 있습니다. 이처럼 MMU의 Relocation을 여러개 두는 것을 페이지 테이블이라고 합니다.

주소변환

논리주소

CPU가 내는 주소는 2진수로 표현됩니다. 만약 m개의 비트를 표현할 수 있다면 하위 n개의 비트는 오프셋(offset) 또는 변위(displacement)를 나타내고 상위 (m-n)개는 페이지 번호(page number)를 나타냅니다.

전체 주소중에 n을 몇 비트로 정할지는 한 페이지의 크기가 결정합니다. 만약 한 페이지의 크기가 16byte라고 한다면 하위 n은 4가 됩니다. 한 페이지의 크기가 1KB(1024byte)라면 n은 16으로 설정할 수 있습니다.

논리주소에서 물리주소로의 변환

이해를 돕기 위해 위의 예시를 들어보겠습니다. 현재 페이지의 크기는 16byte라고 가정하고 CPU가 내놓은 주소는 50번지 입니다. 50번지는 이진수로 110010입니다. 여기서 d의 비트는 4이기 때문에 p는 11을 d는 0010을 나타냅니다.

p 값을 십진수로 변환하면 3입니다. 현재 page table의 3번지에 저장되어 있는 frame 주소는 5번지이고 이 값을 이진수로 변환하면 101 이기 때문에 page table이 내놓은 주소는 frame주소와 변위를 합친 1010010입니다.

1010010값은 십진수로 82를 나타내고 현재 변위는 2였기 때문에 Page 3의 시작주소는 82 - 2인 80(16 * 5)번지가 됩니다.

내부 단편화

외부 단편화를 해결할 수 있는 페이징 기법은 또 다른 문제인 내부 단편화가 발생합니다. 만약 프로세스의 총 크기가 페이지의 크기의 배수가 아니라면 마지막 페이지는 하나의 프레임을 다 사용하지 못하고 남는 공간이 발생하는 것을 내부 단편화라고 합니다.

예를 들어, 15byte 크기의 프로세스가 존재하고 페이지(프레임)의 크기가 4 byte라고 했을때 프로세스의 마지막 페이지는 3byte이며 이 페이지는 하나의 프레임을 다 사용하지 못하고 1 byte만큼 메모리 낭비가 발생합니다.

내부 단편화는 해결할 방법이 없지만 외부 단편화에 비해 낭비되는 메모리 공간이 매우 적습니다. 외부 단편화는 전체 메모리의 1/3이 낭비될 수 있지만 내부 단편화는 페이지 크기 - 1정도의 메모리 낭비만 일어나기 때문입니다.

페이지 테이블 만들기

페이지 테이블은 프레임 번호를 찾기 위한 일종의 저장장치입니다. 이 저장장치를 CPU 내부로 이동시키려면 CPU 레지스터를 사용할 수 있습니다.

CPU 레지스터로 페이지 테이블을 구성한다면 CPU 외부로 접근하는것 보다 훨씬 빠른 접근이 가능합니다. 페이지 테이블의 크기는 프로세스의 크기에 따라 달라지게 됩니다. 만약 크기가 큰 프로세스라면 페이지 수가 매우 많게 되고 이는 곧 페이지 테이블의 크기가 크다는 의미입니다. CPU 내부의 레지스터는 한정된 자원이므로 이 자원만으로 페이지 테이블을 표현하기에는 한계가 있을 수 있다는 단점이 있습니다.

다음으로 페이지 테이블을 메모리에 구성하는 방법입니다. CPU 레지스터에 비해 메모리는 매우 크기 때문에 충분히 페이지 페이블을 구현할 수 있다는 장점이 있습니다. 하지만 CPU 외부에 위치하게 된다면 페이지 테이블에 접근하고 실제 메모리 주소에 접근하는 과정을 거치기 때문에 2배로 느려지게 되는 단점이 있습니다.

다음으로 캐시메모리를 사용하는 방법입니다. 캐시메모리(SRAM)는 일반 메모리(DRAM)에 비해 훨씬 빠릅니다. 페이지 테이블을 위한 캐시메모리 사용은 TLB(Translation Look-aside Buffer)라고 부릅니다. 이 방법은 CPU 레지스터보다는 크기가 크지만 메모리 보다는 작습니다. 반면에 메모리 보다는 변환 속도가 훨씬 빠르기 때문에 조금 더 효율적인 방법입니다. TLB는 캐시의 동작 처럼 전체 페이지 페이블은 메모리에 저장되어 있고 이 중 일부만 TLB에 적재되어 있습니다.

TLB의 효율을 알아보기 위한 기준으로는 Effective Memory Access Time이 있습니다.

• 메모리를 읽는 시간(Tm) = 100ns

• TLB를 읽는 시간(Tb) = 20ns

• TLB에 유효한 페이지 엔트리가 있을 확률(h) = 80%

Effective Memory Access Time = h(Tb + Tm) + (1-h)(Tb + Tm + Tm)

• TLB에 원하는 엔트리가 있는 경우(hit) = h(Tb + Tm)

• TLB에 없어서 메모리를 읽고 TLB로 이동시켜 읽는 경우(miss) = (1-h)(Tb + Tm + Tm)

실제 hit ratio는 95% 이상이므로 위의 동작은 매우 효율적으로 움직이고 있습니다.

보호와 공유

보호 (Protection) : 해킹 등 방지

모든 주소는 페이지 테이블을 경유므로, 테이블을 이용해서 보호 기능을 수행할 수 있습니다. 페이지 테이블에는 프레임 번호 이외에도 r(읽기), w(쓰기), x(실행)에 관한 비트를 따로 두어 해당 프레임의 페이지의 내용을 읽기, 쓰기, 실행할 수 있는 권한을 부여하여 보호 기능을 할 수 있습니다. 만약 쓰기 비트가 0인데 CPU가 내용을 바꾸려고 한다면 인터럽트가 발생할 수 있습니다.

공유 (Sharing) : 메모리 낭비 방지

같은 프로그램을 여러개 실행하는 경우 메모리에는 code, data, stack이 적재됩니다. data와 stack은 각각의 프로세스 별로 다를 수 있지만 code 영역은 동일합니다. 따라서 하나의 code 영역을 여러 프로세스가 공유하도록 하여 메모리 낭비를 줄이는 방법입니다.

공유가 가능하려면 프로세스가 실행되면서 코드 부분이 변하지 않는 non-self-modifying code = reentrant code(재진입가능) = pure code 인 경우에만 가능합니다.