1. 페이징(Paging)

코끼리를 냉장고에 넣으려면 어떻게 해야할까? (잔인하지만) 코끼리를 잘라서 냉장고에 넣으면 된다.

우리는 이전까지 프로세스는 메모리 공간에 연속적으로 존재해야 한다고 생각했다. 하지만 꼭 연속적으로 존재해야 할까? 페이징은 이런 발상의 전환으로부터 등장했다.

프로세스를 일정한 크기(=페이지)로 잘라서 메모리에 올리는 것을 페이징이라고 한다.

그런데 프로세스가 잘라져 있어도 실행될 수 있을까? CPU가 프로세스가 연속적으로 존재한다고 착각하게 만들면 된다. MMU의 재배치 레지스터를 여러 개 사용해 아래 그림과 같이 각 페이지의 실제 주소로 변경해준다. 이런 목적으로 사용되는 MMU는 재배치 레지스터가 테이블과 같은 형태로 배치되어 페이지 테이블(Page Table)이라고 한다.

프로세스를 자른 단위를 페이지, 메모리를 자른 단위를 프레임이라고 한다.

위의 그림에서는 프로세스 $P_1$을 5개의 페이지로 나누고, 이를 메인 메모리 5곳에 나누어 할당하였다. CPU는 논리 주소를 사용해 연속적인 주소값으로 명령을 내리지만, 메모리에 접근하기 전에 각 페이지의 실제 물리 주소를 찾아야 한다. 이를 위해 페이지 테이블이 사용되며, 이는 논리 주소를 해당 페이지의 물리 주소로 변환하는 역할을 한다.

1.1. 주소 변환(Address Translation)

CPU가 내는 주소를 논리 주소(Logical Address)라고 한다. 이 논리 주소를 메모리로 가는 물리 주소(Physical Address)로 바꿔줘야 한다.

앞서 언급한 바와 같이, CPU가 메모리의 여러 곳에 흩어진 페이지에 접근하기 위해서는 페이지의 물리 주소가 필요하다. 이를 어떻게 변환하는지 알아보자.

1.1.1. 논리 주소(Logical Address)

논리 주소는 2진수로 표현된다.전체 비트를 $m$이라고 했을 때, 하위 $n$비트는 오프셋(offset) 또는 변위(displacement)라고 한다. 상위 $m-n$비트는 페이지 번호다.$(n=d, m-n=p)$

1.1.2. 물리 주소(Physical Address)

물리 주소는 프레임 번호($f$)와 변위($d$)로 구성된다. 페이지 번호($p$)는 페이지 테이블의 인덱스 값이고, 변위는 변하지 않는다.

1.1.3. 예제

Page size = 4bytes, Page Table: 5 6 1 2일 때, 논리 주소 13번지는 물리 주소 몇 번지인가?

$13=1101_2$이고, $4=2^2$이므로 $d=2$이다. 따라서 뒤의 두 칸이 $d$를 가리키고, $p$는 $d$를 제외한 나머지 크기이다.

13 = 1101
p = 11
d = 01

$p=11_2=3$이므로 페이지 번호 3번을 가리킨다. 페이지 3번에 해당하는 프레임 번호는 2번이므로, 물리 주소를 구성하는 $f$값은 2가 된다.

f = 10
d = 01
물리 주소 = 1001

이처럼 프로세스를 흩어지게 함으로써 더이상 외부 단편화는 발생하지 않게 되나, 내부 단편화라는 문제가 생긴다.

1.2. 내부 단편화(Internal Fragment)

페이지 사이즈가 4byte이고, 프로세스 크기는 15byte라고 하면 페이지는 4개가 필요하다. 마지막 페이지는 크기를 다 채우지 못하고 1byte가 남게 된다.

프로세스 크기가 페이지 크기의 배수가 아닐 때 마지막 페이지가 한 프레임을 다 채울 수 없는 것을 내부 단편화라고 한다. 공간이 남는다는 것은 곧 메모리 낭비를 의미한다.

하지만 내부 단편화로 낭비되는 메모리의 최대 크기는 (page size - 1)byte쯤 된다. 이는 매우 미미한 수준이어서 크게 문제가 되지 않는다.

1.3. 페이지 테이블 만들기

CPU와 메모리 사이에는 페이지 테이블이 있는데, 이를 만드는 방법은 여러 가지가 있다.

1.3.1. CPU 레지스터

MMU를 CPU 안에 넣는 방법이다. 페이지 테이블은 프레임 넘버를 기억하기 때문에 일종의 기억장치이다. 따라서 CPU 안의 기억장치인 레지스터로 페이지 테이블을 만들 수 있다.

CPU 안에 있기 때문에 주소 변환이 매우 빠르다는 장점이 있으나, 많이 넣을 수는 없다는 단점이 있다.

1.3.2. 메모리

MMU를 메인 메모리 안에 넣는 방법이다. 메모리는 용량이 매우 크므로 페이지 테이블의 엔트리 개수가 아무리 많아도 넣기 용이하다.

하지만 주소 변환 속도가 느리다는 단점이 있다. CPU가 주소를 내면 그 주소는 OS 영역 안에서 페이지 테이블을 한 번 읽고, 읽고 나서 나온 프레임 넘버에 따라 물리 주소로 가야하기 때문이다.

1.3.3. TLB(Translation Look-aside Buffer)

MMU를 캐시 메모리로 만드는 방법으로, 실제로 가장 많이 사용된다. 별도의 high speed SRAM 칩을 만들어 주소 변환만을 위해 이용하는 걸 TLB라고 부르며, 원리는 캐시 메모리와 동일하다.

이 방식은 CPU 레지스터로 만드는 방법이나 메모리로 만드는 방법과 테이블 엔트리 개수, 변환 속도 측면에서 성능을 비교할 수 있다.

e.g. TLB 사용 시 유효 메모리 접근 시간(Effective Memory Access Time) 구하기

메모리를 읽는 데 걸리는 시간 $T_m=100ns$, TLB를 읽는 시간 $T_b=20ns$, 어떤 주소가 페이지 테이블 엔트리에 있을 확률 hit ratio = 80%

$T_e=h(T_b+T_m)+$$(1-h)(T_b+T_m+T_m)$$=0.8*120+0.2*220=140ns$

이는 $T_m=100ns$보다 40% 느려진 시간이나, 실제로는 hit ratio가 95% 이상에 달하기 때문에 외부 단편화 해결을 위해 감수해야 하는 부분이라고 할 수 있다.

1.4. 보호와 공유

1.4.1. 보호(Protection)

운영체제가 해야하는 중요한 일 중 하나가 보호이다. CPU가 내는 모든 주소는 페이지 테이블을 경유하므로 해당 페이지에 대한 접근 제어가 가능하다.

페이지 테이블은 엔트리마다 r(read), w(write), x(execute) 비트를 두어 해당 비트의 값에 따라 수행 여부를 결정한다.

e.g. 2번 엔트리에 읽기 비트가 꺼져있는데 읽기 작업을 시도하면 CPU에 인터럽트가 발생하여 ISR에서 강제로 해당 프로세스를 종료시킨다.

1.4.2. 공유(Sharing)

하나의 프로그램이 실행될 때 code, stack, data가 필요하다. 같은 프로그램을 사용하는 복수 개의 프로세스 $P_A, P_B, P_C$가 있다고 해보자. 이들은 각각 독립적인 프로세스이기 때문에 data가 다르고, stack과 같이 실행 시점에 따라 달라지는 지역 변수 등도 다를 것이다.

하지만 같은 프로그램이기 때문에 code 영역은 동일하다. 동일한 값을 중복되게 메모리에 띄우는 것은 명백한 낭비이다. 따라서 같은 프로그램을 쓰는 프로세스가 있다면 code 영역을 공유하여 컨텍스트 스위치가 될 때마다 같은 곳을 가리키게 한다.

단, 코드가 실행되는 동안 스스로 내용을 바꾸지 않는다는 전제가 있어야 한다. 이는 non-self-modifying code = reentrant code(재진입가능 코드) = pure code라고 한다.

2. 세그멘테이션(Segmentation)

코끼리를 냉장고에 넣을 때 그냥 일정 크기로 자르는 방법도 있고, 부위별로 자르는 방법이 있다.

앞서 우리는 프로세스를 일정한 크기에 따라 잘랐다. 세그멘테이션은 프로세스를 논리적 내용, 세그먼트 단위로 잘라 메모리에 올리는 것을 말한다. 이때문에 세그먼트의 크기는 일정하지 않다.

2.1. 주소 변환(Address Translation)

세그멘테이션을 위한 테이블을 세그먼트 테이블이라고 한다. 세그먼트 테이블은 세그먼트 번호, base, limit으로 구성되어 있다.

세그먼트 번호($s$)는 세그먼트 테이블 인덱스 값을 의미한다. Base는 시작 번지, 즉 해당 세그먼트가 메모리 몇 번지에 있는지를 의미한다. Limit은 세그먼트 크기를 의미한다.

세그먼트의 주소 변환 역시 페이징 주소 변환과 유사하나, 세그먼트의 크기는 일정하지 않기 때문에 테이블에 limit 정보가 주어진다. CPU에서 해당 세그먼트의 크기를 넘어서는 주소가 들어오면 인터럽트가 발생해 해당 프로세스를 강제로 종료시킨다.

위 그림은 세그먼트 테이블과 프로세스가 할당된 메모리의 모습이다. 페이징 주소 변환과 동일하게 $d$는 논리 주소와 물리 주소가 동일하다. 물리 주소는 $base[s]+d$로 계산된다.

e.g.

• 논리 주소 (2, 100) ⇒ 물리 주소 4400번지
• 논리 주소 (1, 500) ⇒ 인터럽트로 인해 프로세스 강제 종료(잘못된 세그먼트 violation)

2.2. 보호와 공유

세그멘테이션은 보호와 공유 측면에서 페이징보다 더 나은 방법이다. 핵심은 세그멘테이션은 프로세스를 기능 단위로 자른다는 점이다.

2.2.1. 보호(Protection)

모든 주소는 세그먼트 테이블을 경유하므로 세그먼트 테이블 엔트리마다 r, w, x 비트를 두어 해당 세그먼트에 대한 접근을 제어한다.

프로세스를 자를 때에 페이징은 그저 일정 크기로 자르기 때문에 예를 들어 어떤 페이지에는 code가 있고, 다음 페이지에는 data+code가 있고, 다음 페이지에는 code+stack이 있다.

반면 세그멘테이션은 기능별로 자르기 때문에 섞일 일이 없다. Data는 읽고 쓰되 실행은 하면 안 될 것이고, 어떤 것은 읽기만 하고 실행과 쓰기를 하면 안 된다. 그런데 페이징처럼 어중간하게 잘리면 r, w, x 비트를 어떻게 설정할지 곤란해진다.

따라서 보호의 측면에서 프로세스를 논리적으로 의미가 있는 구분으로 자르는 것이 더 나은 방식이다.

2.2.2. 공유(Sharing)

같은 프로그램을 돌리는 복수의 프로세스가 있을 때, 세그먼트 테이블의 code 영역이 같은 곳을 가리키게 하면 된다. 세그먼트는 확실하게 code 영역을 자르기 때문에, 페이징과 다르게 code 영역이 확실히 분리된다. 이때문에 공유의 측면에서도 세그멘테이션은 페이징보다 우월하다.

그럼에도 대부분의 운영체제는 페이징을 사용한다. 왜 그런 것일까?

2.3. 외부 단편화(External Fragment)

1.1에서 설명한 것과 같이, 다중 프로그래밍에서는 프로세스가 실행되고 종료됨에 따라 메모리에 hole이 생긴다. 이때문에 남는 메모리 공간 자체는 충분함에도 프로세스를 할당하지 못하는 외부 단편화 문제가 발생한다.

세그멘테이션에서도 똑같은 문제가 발생하는데, 이는 세그먼트가 논리적인 단위로 나누어져 크기가 상이하기 때문이다. 이로 인해 다양한 크기의 hole이 발생해 외부 단편화 문제가 또다시 나타난다.

3. 세그멘테이션과 페이징

이러한 문제 때문에 세그먼트를 페이징하는 방식이 나타났다.

프로세스를 자를 때 처음에는 세그먼트로 자른다. 그런데 이를 바로 메인 메모리에 올리면 외부 단편화 문제가 발생할 수 있기 때문에 세그먼트를 다시 일정 간격, 즉 페이지 단위로 자른다. 이를 Paged Segmentation이라고 한다.

이를 통해 우리는 두 가지 방식의 장점을 둘 다 가져갈 수 있게 되었다. 그런데 이는 주소 변환에 있어 시간적 부담이 늘어난다는 단점이 있다. 처음 주소가 세그먼트 테이블로 가고, 그 다음 페이징 테이블로 가서 단계가 하나 늘어났기 때문이다.

Paged Segmentation으로 보호와 공유 측면, 외부 단편화 문제에서도 더 뛰어난 성능을 가져갈 수 있게 되었으나, 이러한 이점에는 시간이 더 오래 걸린다는 trade-off가 따른다.

Reference

• KOCW 양희재 운영체제
• [운영체제(OS)] 13. 페이징