8-2. 페이징, 세그먼테이션

- 페이징(1) -

 

메모리의 낭비 공간인 hole을 최소한으로 만들기 위해 앞 장에서 많은 방법을 사용하였다. 최초 적합과 최적 적합을 통해 메모리의 공간에 적재하는 방식에 변화를 주었는데 이를 통해서도 메모리 공간의 1/3 정도가 낭비가 되었다. 이렇기 때문에 다른 방식인 Compaction이라는 방식을 사용하였으나 프로세스나 hole을 메모리 공간에서 이동시키기 위해서는 메모리 계산의 부담이 발생하기 때문에 힘들었다. 그래서 사용한 방식이 바로 페이징이다.

페이징은 프로세스를 일정 크기인 페이지로 잘라서 메모리에 적재하는 방식이다. 프로세스는 항상 연속해서 들어가야 한다는 생각을 통해 메모리 공간 활용에 있어서 앞장에서는 연속 메모리 할당에 초점을 맞추었다. 이런 생각부터 뒤집어서 프로세스를 일정한 단위로 잘라서 사용하자는 방식이 페이징이다. hole과 프로세스를 모두 특정 페이지 단위로 잘라서 메모리 공간을 관리한다. 하지만 프로세스를 자르게 되면 실행이 될까? 에 대한 궁금증이 생긴다. 그러면 프로세스를 자르게 되더라도 실행을 할 수 있게 하는 방식은 무엇이 있을까?

앞에서 설명한 방식을 한 번 떠올려보자. 메모리 공간을 할당할 때 코드에서 명명한 메모리 주소 위치와 다르게 임의로 프로세스를 메모리에 적재하였다. 이렇게 할 수 있었던 이유는 바로 MMU의 재배치 레지스터의 값을 바꾸어 CPU를 속일 수 있었기 때문이다. 그러면 이왕 속이게 되는 거 재배치 레지스터를 많이 두어 각각의 페이지 단위의 프로세스를 활용할 수 있게 속이는 것은 어떻게 생각하는가? 프로세스를 나눈 페이지마다 재배치 레지스터를 만들어 놓으면 CPU는 마치 프로세스가 연속된 메모리 공간에서 동작하고 있다고 생각하게 될 것이다. 왜냐하면 재배치 레지스터에서 메모리 적재 공간의 값을 더해주어 CPU를 속이기 때문이다.

프로세스를 자르는 단위는 페이지이다. 이에 동일한 크기로 메모리를 자른 것을 프레임이라고 한다. 같은 크기로 페이지와 프레임으로 잘라져 있기 때문에 페이지를 프레임에 할당하면 딱 맞아 떨어진다. 이 때 페이지를 관리하는 MMU는 페이지 테이블이 된다. 페이지 테이블 안에 있는 개수는 프로세스를 몇 등분하는가에 따라 결정된다.

CPU가 내는 주소는 논리 주소(Logical address)라고 한다. CPU에서 보낸 논리 주소는 MMU인 페이지 테이블을 통해 물리 주소(Physical address)로 바뀌어서 메모리에서 찾게 된다. 논리 주소는 2진수로 표현된 m개의 비트이다. 하위 n비트는 오프셋 또는 변위를 나타내고 상위의 m-n비트는 페이지 번호를 나타낸다. n비트는 페이지를 어떤 크기로 나누는 정도에 따라 다르게 된다. 예를 들어 16바이트로 페이지를 나눈다고 생각하면 n은 4비트가 된다. 2진수로 표현된 값이기 때문이다. 페이지 테이블에서 페이지 번호를 가져와서 해당하는 프레임 번호를 가져오게 된다. 페이지 번호는 페이지 테이블의 인덱스 값으로 인식한다. 페이지 번호에 해당하는 페이지 테이블의 값과 n비트의 값을 가진 물리 주소로 바뀌게 된다.

예를 들어 50번지라는 논리 주소를 물리 주소로 바꾸고 싶다고 한다고 가정해보자. 이때 페이지의 크기는 16바이트이다. 50번지를 2진수로 바꾸게 되면 110010이 된다. 이때 페이지의 크기가 16바이트이므로 하위 4비트는 n비트가 되고 앞의 두 비트가 페이지 번호를 나타내는 인덱스 값이 된다. 그러면 페이지 테이블에서 11에 해당하는 3의 값을 가진 페이지 번호로 가게 되어 페이지 테이블 값을 읽는다. 만약 이 때의 페이지 테이블 값이 8이라고 하면 8과 n비트를 합쳐서 물리 주소를 가지게 된다. 그 값은 10000010 이라는 메모리 공간의 주소로 가게 되는 것이다. 10진수로 바꾸게 되면 130번지가 된다. 다시 해석하게 되면 테이블 값의 8은 128번지를 의미하게 되고 여기서 하위 n비트의 변위 값에 의해 130번지에서 이 프로세스의 페이지가 동작하게 되는 것이다.

---

- 페이징(2) -

예시를 통해 주소 변환을 하는 과정을 살펴보자. 자세한 계산 방법은 앞 장을 참고하면 좋을 것이다.(운영체제 17장) 페이지 사이즈가 4바이트이고 페이지 테이블에 페이지 번호 당 5, 6, 1, 2를 가진다고 한다. 그러면 페이지 번호가 0번이면 5로 1번이면 6으로 가는 것으로 인식하면 된다. CPU가 논리 주소로 13번지를 요구한다면 메인 메모리의 어디의 물리 주소 위치로 가야하는가? 13을 이진수로 표현하면 1101이 된다. 이 주소 값에서 페이지 사이즈가 4바이트이므로 변위는 하위 2비트가 된다. 그러므로 나머지 상위 2비트는 페이지 번호가 된다. 페이지 번호가 11이므로 3이 된다. 그러므로 3에 해당하는 2라는 물리 주소 값으로 가게 된다. 2는 이진수로 10이고 하위 비트 01을 붙여 물리 주소가 1001로 바뀌게 된다. 따라서 9번지에 실제 프로세스의 페이지가 위치하게 되는 것이다.

하지만 페이징 과정을 진행하면 내부 단편화가 발생할 수 있다. 페이징은 프로세스를 특정 단위인 페이지 단위로 나누어 주고 된다. 하지만 프로세스의 크기가 페이지 크기의 배수가 아니라면 마지막 프로세스의 페이지는 한 프레임을 다 채울 수 없다. 따라서 이런 공간이 메모리 안에서 빈 공간으로 남아 낭비되게 된다. 이런 문제를 내부 단편화라고 한다. 예를 들어 프로세스가 15바이트인데 페이지를 4바이트 단위로 나눈다고 생각해보자. 그러면 3묶음의 4바이트 페이지가 나오지만 마지막 페이지는 3바이트의 크기가 만들어 진다. 프레임은 4바이트 크기인데 3바이트 크기의 페이지가 들어오면 1바이트의 메모리 낭비가 생기게 되는 것이다. 하지만 외부 단편화에 비해 낭비되는 내부 단편화의 메모리 공간이 매우 미비하다.

---

Hardware Support

page table은 메모리에 저장되어 있다. PTBR(Page-Table Base Register)가 page table을 가리키고, PTLR(Page-Table Length Register)가 page table의 크기를 가지고 있다. 따라서 매번 데이터에 접근할 때마다 한 번은 데이터에, 한 번은 page table에 접근해야 한다. 물론 이는 비효율적인 일이기 때문에 캐시같은 것을 사용해 해결했다.

TLB(Translation Look-aside Buffer)는 참조했던 페이지를 담아주는 캐시 역할을 한다. TLB는 key-value pair로 데이터를 관리하는 acssociative memory이며, CPU는 page table보다 TLB을 우선적으로 참조한다.

page number가 TLB에서 발견되는 비율을 hit ratio라고 하며, effective memory-access time을 구하는데 쓸 수 있다.

effecftive memory-access = hit ratio * memory access time + (1 - hit ratio) * (2 * memory access time)

만약 hit ratio가 80%이고, 평균 메모리 접근 시간이 100 나노초라면 다음과 같이 계산한다.

effective memery-access time = 0.8 * 100 + 0.2 * 200 = 120

Protection

메모리 할당이 contiguous한 경우 limit만 비교해도 메모리를 보호할 수 있었다. 하지만 paging은 contiguous하지 않기 때문에 다른 방법을 쓴다. page table의 각 항목에는 valid-invalid bit가 붙어있어 그 값이 valid라면 해당 페이지에 접근이 가능하고, invalid라면 해당 페이지가 logical address space에 속하지 않아 접근할 수 없다는 것을 의미한다.

Shared Pages

paging의 또 다른 장점은 코드를 쉽게 공유할 수 있다는 것이다. 만약 코드가 reentrant code(또는 pure code)라면 공유가 가능하다. reentrant code는 runtime 동안 절대로 변하지 않는 코드이며, 따라서 여러 프로세스들이 동시에 같은 코드를 수행할 수 있다. 이런 식으로 공통 page를 공유하면 12개 로드해야 할 것을 6개만 로드해도 된다.

Structure of the Page Table

paging을 직접 적용하면 page table의 크기가 커진다. 페이지 테이블을 효율적으로 구성하는 몇 가지 방법이 있다.

Hierachial Paging

hierachical paging은 logical address space를 여러 단계의 page table로 분할하는 기법이다. two-level paging scheme이 예시인데, page table과 메모리 사이에 page table을 하나 더 둠으로써 모든 페이지를 로드해야 하는 부담을 줄일 수 있다.

Hashed Page Tables

말그대로 hash table을 이용해 page table을 관리하는 기법. address space가 32비트보다 커지면 hierachial paging이 비효율적이기 때문에 주로 이 방법을 쓴다. virtual page number를 hashing해 page table을 참조하는 데 사용한다. hashed page table에서는 linked list를 따라가며 page number를 비교하고, 일치하면 그에 대응하는 page frame number를 얻는다. hash table은 검색에 O(1) 시간이 걸려 매우 빠르지만 구현이 어렵다.

Inverted Page Tables

지금까지 page table은 각 page마다 하나의 항목을 가졌다. inverted page table은 메모리의 frame마다 한 항목씩 할당하는데, 이렇게 하면 physical frame에 대응하는 항목만 저장하면 되기 때문에 메모리를 훨씬 적게 사용하게 된다. 다만 탐색 시간이 오래 걸리기 때문에 대부분의 메모리는 inverted page table과 hased page table을 결합하는 방식으로 구현되어있다.

---

- 세그멘테이션(Segmentation) -

 

앞선 장들에서 페이징을 배우면서 프로세스를 일정 크기인 페이지 단위로 잘라서 메모리에 적재하는 방법을 알았다. 페이지는 정확하게 일정한 간격으로 자르는 단위였다. 하지만 프로세스를 물리적인 단위인 페이지 말고 논리적 내용 단위인 세그먼트로 자를 수 있는 세그먼테이션 방법이 있다. 예를 들면 우리가 돼지를 잡아서 보관을 한다고 생각해보자. 페이징의 방법을 사용하면 돼지를 모두 같은 단위로 잘라서 보관을 하는 것이다. 반면에 세그먼테이션은 부위별로 다른 크기로 잘라서 보관하는 것이다.

세그멘테이션은 프로세스를 세그먼트의 집합으로 생각한다. 사실 하나의 프로세스가 동작하려면 기본적으로 코드, 데이터, 스택 세 가지의 세그먼트는 항상 가지고 있다. 그리고 더 들어가 보면 코드에서도 main 함수가 있을 수 있고, 다른 함수들이 있을 수도 있고, 다른 루틴이 있을 수도 있다. 데이터를 보아도 어떤 구조체가 있을 수도 있고 배열도 있을 수 있다. 그래서 세그먼테이션은 물리적인 크기의 단위가 아닌 논리적 내용의 단위(의미가 같은)로 자르기 때문에 세그먼트들의 크기는 일반적으로 같지 않다.

프로세스를 어떻게 자르는가에 대한 방법 빼고 메모리에 할당하는 방법에 대해서는 페이징과 방법이 같다. MMU 내의 재배치 레지스터를 이용하여 논리 주소를 물리 주소로 바꾸어 주는 방식을 취한다. MMU는 세그먼트 테이블로 CPU에서 할당한 논리 주소에 해당하는 물리 주소의 위치를 가지고 있다. 이 방법을 이용하면 CPU는 프로세스가 연속된 메모리 공간에 위치한다고 착각을 하게 된다.

주소를 변환하는 방법 역시 같다. 하지만 논리 주소에서 보내는 주소 값에서 하위 변위 비트를 제외한 앞의 비트들은 페이징 번호가 아니라 세그먼트 번호가 되는 것이다. 따라서 논리 주소는 세그먼트 번호와 변위 비트로 이루어져 있게 된다. 세그먼트 테이블에 논리 주소 값이 들어가게 되면 세그먼트 번호는 세그먼트 테이블의 인덱스 값으로 인식을 하게 된다. 세그먼트 번호를 토대로 테이블 내용으로 들어가 시작 위치 및 한계 값을 파악한다. 물리 주소는 세그먼트 테이블에 있는 시작 위치와 변위 값을 합하여 구할 수 있다. 그런데 이런 주소 값이 한계(각 세그먼트의 크기)를 넘어서면 segment violation 예외 상황 처리를 하게 된다. 이런 경우는 변위가 한계보다 크면 발생한다.

세그먼테이션의 경우에도 보호와 공유의 기능을 수행하고 있다. 모든 논리 주소들은 세그먼테이션 테이블을 경우하게 되므로 세그먼트 테이블 엔트리마다 r, w, x 비트를 만들어 해당 세그먼트에 대한 접근 제어를 가능하게 해준다. 또한 같은 프로그램을 사용하는 복수 개의 프로세스가 있다면 메모리에 하나만 적재하여 프로세서의 세그먼트 테이블 코드 영역이 같은 곳을 가리키게 만든다. 그런데 위와 같은 기능이 페이징의 기법보다 더 좋다고 할 수 있다. 간단하게 생각을 해보아도 그렇다는 것을 알 수 있다. 페이징은 프로세스를 같은 단위로 자르게 되므로 중요한 부분과 중요하지 않은 부분이 같은 페이지 안으로 잘라질 수 있다. 또한 코드 영역 또한 같은 단위로 잘리므로 애매하게 잘려질 확률이 있다. 하지만 세그먼테이션의 방법으로 자르게 되면 코드 영역은 코드 영역으로 잘리게 되고 중요한 세그먼트, 중요하지 않은 세그먼트를 논리적인 내용 측면으로 자를 수 있다. 그렇게 되면 보호와 공유의 기능을 수행하기 쉬워지는 것이다. 내용적인 측면으로 다 나누어 졌기 때문이다.

그러면 세그먼테이션만 사용하면 될 것 같지만 이 또한 단점을 가지고 있다. 세그먼트는 크기가 고정되어 있지 않고 가변적이다. 크기가 다른 각 세그먼트를 메모리에 두려면 동적 메모리 할당을 해야 한다. 앞에서 말한 외부 단편화가 발생할 수 있다. 외부 단편화는 메모리 낭비를 매우 크게 발생시킨다. 세그먼테이션을 사용하기 힘든 것이다. 따라서 우리는 세그먼테이션과 페이징의 기법을 모두 사용하고자 한다. 두 방식 모두 장단점을 가지고 있으니 장점만을 가져오게 되면 좋은 방법이 될 수 있기 때문이다. 세그먼테이션은 보호와 공유 면에서 효과적이고 페이징은 외부 단편화 문제 해결에 효과적이므로 두 가지 모두를 사용할 수 있으면 좋을 것이다. 따라서 세그먼트를 페이징 하는 방법을 취한다.

프로세스를 처음에 세그먼트 단위로 자른다. 의미 있는 단위로 나누게 되면 보호와 공유를 하는 측면에 이점을 가질 수 있게 된다. 하지만 앞서 말했듯 외부 단편화가 발생할 수 있다. 그래서 우리는 잘라진 세그먼트를 다시 일정 간격인 페이지 단위로 자르는 페이징 방법을 취한다. 그래서 메모리에 적재하면 페이징의 일정 단위로 다시 잘렸기 때문에 외부 단편화가 발생하지 않는다. 하지만 이와 같은 경우에는 테이블을 두 가지를 모두 거쳐야 하므로 속도 면에서 조금 떨어질 수 있다.

출처: http://copycode.tistory.com/108?category=740133 [ITstory]