Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

베이스-바운드 방식을 사용했을 때 프로세스에 할당된 힙과 스택 메모리 사이에 사용되지 않는 공간이 있음을 보았다. 단순히 베이스-바운드 레지스터 쌍을 이용해 메모리를 가상화하는 것은 비효율적이고, 전체 주소 공간이 메모리에 맞아 떨어지지 않을 경우 프로그램을 실행하기 어렵게 만들기도 한다.

1. Segmentation: Generalized Base / Bounds

이와 같은 문제를 해결하기 위해 만들어진 기법이 세그먼테이션(segmentation)이다. 아이디어는 간단하다. MMU에서 단 한 쌍의 베이스-바운드를 쓰는 게 아니라, 주소 공간의 논리적인 세그먼트마다 베이스-바운드 쌍을 주는 것이다. 세그먼트는 일정한 길이를 가지는, 주소 공간의 연속적인 부분으로, 아래의 예제에는 세 개의 논리적으로 구분되는 세그먼트들, 코드, 스택, 힙이 있다.

세그먼테이션을 이용하는 경우, OS는 각 세그먼트를 물리 메모리의 다른 부분들에 배치시켜, 사용되지 않는 가상 주소 공간으로 물리 메모리가 가득 차는 일이 일어나지 않게 한다.

프로세스는 여전히 자신이 왼쪽과 같이 메모리를 사용하고 있다고 생각하겠지만, 실제로는 오른쪽과 같이 세그먼트 별로 베이스-바운드 쌍을 사용함으로써 각 세그먼트를 물리 메모리에 독립적으로 위치시킨다. 이때 있듯 오직 사용 중인 메모리만이 물리 메모리에 공간을 할당받으며, 사용되지 않는 큰 주소 공간을 가지는 주소 공간(희소 주소 공간, sparse address space)이 가능해진다.

세그먼테이션을 위해 필요한 MMU의 하드웨어 구조는 예상하기 쉽다. 이 경우에는 세 쌍의 베이스-바운드 레지스터가 된다.

Segment	Base	Size
Code	32K	2K
Heap	34K	3K
Stack	28K	2K

2. Which Segment Are We Referring To?

하드웨어는 주소 변환 시 세그먼트 레지스터들을 사용한다. 그렇다면 이 하드웨어는 세그먼트의 오프셋을 어떻게 알고, 해당 세그먼트가 참조하고 있는 주소는 어떻게 알까?

Explicit Approach

한 가지 방법은 주소 공간을 가상 주소의 상위 몇 개의 비트를 기반으로 세그먼트로 나누는 것이다.

위 예시에서 우리는 세 개의 세그먼트를 가지고 있으므로 2비트만 사용하면 된다. 14비트의 가상 주소를 사용한다고 하면 다음과 같다.

만약 상위 2비트가 00이면, 하드웨어는 가상 주소가 코드 세그먼트에 있음을 알고 그 베이스-바운드 쌍을 사용하고, 마찬가지로 상위 2비트가 01이면 힙의 베이스-바운드 쌍을 쓴다.

그런데 이때 정해진 수의 비트로 표현할 수 있는 세그먼트의 개수가 실제 세그먼트의 개수보다 많은 경우 주소 공간의 낭비가 일어날 수도 있다. 예를 들어 상위 2비트로는 네 종류의 세그먼트를 표현할 수 있음에도, 실제로 쓰고 있는 세그먼트에는 세 종류 밖에 없을 수 있다. 이런 경우 몇몇 시스템들은 가상 주소 공간을 완전히 활용하기 위해 코드를 힙 세그먼트와 같은 곳에 넣고, 세그먼트 선택을 위해서는 한 비트만 사용하기도 한다.

또 다른 이슈는 세그먼트를 표시하기 위해 너무 많은 상위 비트들을 사용하면 가상 주소 공간의 사용을 제한하게 될 수도 있다는 것이다. 각 세그먼트는 최대 사이즈를 가지고 있는데, 14비트 주소 체계에서 상위 2비트를 세그먼트 구분을 위해 사용하면, 세그먼트는 4KB의 주소 공간을 이상을 가질 수 없다. 만약 실행 중인 프로그램이 세그먼트를 최대값을 넘게 키우고 싶어하는 경우가 있다면 실패하게 된다.

Implicit Approach

다른 방식으로는 하드웨어는 주소가 어떻게 구성되었는지를 통해서 세그먼트를 결정하는 방식이 있다. 만약 주소가 PC에 의해 만들어졌다면 이는 코드 세그먼트에 있다. 만약 주소가 스택 또는 베이스 포인터를 기반으로 한다면, 이는 스택 세그먼트에 있다. 이외의 경우는 힙에 있다.

3. What About The Stack?

스택은 거꾸로, 즉 낮은 주소의 방향으로 자란다. 위 예제에서 스택은 물리 메모리에서는 28KB에서 시작해서 26KB로 자라고, 상응하는 가상 메모리에서는 16KB에서 14KB로 자란다. 따라서 주소 변환도 조금 다르게 이뤄져야 한다.

이를 위해서도 하드웨어의 지원이 필요하다. 하드웨어는 그냥 베이스-바운드 값을 쓰지 않고, 이 세그먼트가 자라는 방식에 대해서도 알아야 하며, 세그먼트가 반대 방향으로 자란다는 것을 알면, 가상 주소도 조금 다른 방식으로 변환해야 한다.

Segment	Base	Size (max 4K)	Grows Positive?
Code 00	32K	2K	1
Heap 01	34K	3K	1
Stack 11	28K	2K	0

가상 주소 15KB에 접근하려고 한다고 하자. 이 주소는 물리 주소 27KB에 매핑되어 있다. 이는 이진법으로는 11 1100 0000 0000이 된다. 하드웨어는 앞의 두 비트 11을 이용해 어떤 세그먼트인지를 밝힌다.

이후 남은 3KB의 오프셋을 이용해 물리 메모리에서의 오프셋을 얻는다. 스택은 거꾸로 자라므로 오프셋도 음수가 돼야 한다. 이 음의 오프셋을 얻으려면 가상 주소의 오프셋에서 최대 사이즈를 빼면 되는데, 세그먼트의 최대 사이즈가 4KB이므로 3 - 4= -1KB가 원하는 오프셋이다. 이 음의 오프셋을 베이스에 더해 실제 물리 주소를 얻는다. 바운드는 음의 오프셋의 절댓값이 세그먼트의 현재 사이즈보다 작거나 같은지를 봄으로써 확인할 수 있다.

4. Support for Sharing

특정 메모리 세그먼트를 주소 공간에서 공유하면 메모리를 절약할 수 있는데, 특히 코드 공유가 대표적이다. 공유를 위해서도 추가적인 하드웨어의 지원이 필요한데, 보통은 보호 비트(protection bit)를 사용한다.

보호 비트는 각 세그먼트 뒤에 붙어 프로그램이 해당 세그먼트를 읽거나 쓸 수있는지, 혹은 해당 세그먼트의 코드를 실행할 수 있는지의 여부를 가리킨다. 코드 세그먼트를 읽기 전용으로 두면 프로세스 간 고립을 해치지 않으면서도 같은 코드를 가지는 여러 프로세스들 사이에서 세그먼트를 공유할 수 있다.

이렇게 실제로는 코드 세그먼트를 공유하더라도 여전히 각 프로세스는 자신이 자신만의 메모리에 접근하고 있다고 생각하는데, 이러한 환상은 OS가 프로세스에 의해 수정될 수 없는 메모리들을 비밀스럽게 공유하도록 해주기 때문이다.

보호 비트를 이용하면 앞서 말한 하드웨어 알고리즘도 변해야 한다. 원래는 가상 주소가 바운드에 있는지만을 확인했지만, 이제 하드웨어는 거기에 더해 특정한 접근이 허용 가능한지도 확인해야 한다. 만약 유저 프로세스가 읽기 전용인 세그먼트에 쓰려고 하거나, 실행할 수 없는 세그먼트를 실행하려고 하면 하드웨어는 예외를 일으켜 OS가 이를 처리할 수 있게 해야 한다.

5. Fine-grained vs. Coarse-grained Segmentation

지금까지의 예시들은 몇 개의 세그먼트를 가지는 시스템에만 초점을 맞췄다. 이렇게 주소 공간을 비교적 크고 거친 덩어리로 나누는 세그멘테이션을 coarse-grained라고 한다. 하지만 몇몇 초기 시스템은 주소 공간을 더 융통성 있고 많은 수의 작은 세그먼트들로 구성하기도 했는데, 이를 fine-grained 세그멘테이션이라 부른다.

여러 개의 세그먼트들을 이용하기 위해서는 일종의 세그먼트 테이블을 메모리에 저장하는 등, 더 많은 하드웨어 지원이 필요하다. 그런 세그먼트 테이블들은 보통 아주 많은 수의 세그먼트 생성을 지원해 시스템이 세그먼트를 더 융통성있게 사용할 수 있게 한다.

6. OS Support

세그먼테이션에서는 프로세스 별로 한 쌍의 베이스-바운드를 사용할 때보다 많은 물리 메모리를 절약할 수 있게 됐다. 구체적으로 스택과 힙 사이의 사용되지 않는 공간들은 물리 메모리에 할당되지 않게 함으로써 더 많은 주소 공간들을 물리 메모리에 집어 넣어, 프로세스마다의 크고 성긴 가상 주소 공간을 가능하게 한다.

하지만 이로써 염두에 둬야할 이슈들도 생긴다.

문맥 전환

우선 문맥 전환이 일어날 때 OS는 세그멘테이션 레지스터를 저장되고 복원해야 한다. 각 프로세스는 자신만의 가상 주소 공간을 가지고, OS는 프로세스를 재실행하기 전에 이 레지스터들을 제대로 복원해야 한다.

세그먼트의 크기 변화

세그먼트가 자라거나 줄어들 때 OS는 무엇을 해야할까? 예를 들어 프로그램이 malloc()을 한다고 해보자.

지금 있는 힙만으로 해당 요청을 처리할 수 있는 경우, malloc()은 필요한 가용 공간을 찾아 해당 주소의 포인터를 반환하기만 하면 된다. 하지만 그렇지 못하는 경우에는 힙 세그먼트의 크기 자체를 키워야 한다. 이 경우 메모리 할당 라이브러리는 힙의 크기를 증가시키는 시스템 콜을 수행하고 OS는 세그먼트 사이즈를 업데이트해 더 많은 공간을 제공하고, 그렇게 할 수 없는 경우 OS는 요청을 거부한다.

가용 공간 관리

가장 중요한 마지막 이슈는 물리 메모리에서 가용 공간을 관리하는 것이다. 새 주소 공간이 만들어지면 OS는 그 세그먼트를 위한 공간을 물리 메모리에서 찾을 수 있어야 한다. 예전에는 각 주소 공간이 같은 크기를 가진다고 가정하고 물리 메모리는 프로세스가 들어갈 수 있는 슬롯의 배열 정도로 생각했지만, 지금은 프로세스마다 많은 세그먼트들이 있고, 각 세그먼트들은 서로 다른 크기를 가진다.

가장 일반적인 문제는 외부 단편화(external fragmentation)다. 물리 메모리가 가용 공간의 홀들로 가득차게 되는 것이다. 이는 새 세그먼트의 할당을 어렵게 만들고 이미 있는 세그먼트의 크기를 늘리는 것도 어렵게 만든다.

이 문제에 대한 한 해결법은 물리 메모리에 존재하는 세그먼트들을 압축 compact)하는 것이다. 예를 들어 OS는 실행 중인 모든 프로세스를 정지한 후 그 데이터를 메모리의 연속적인 영역에 복사하고, 세그먼트 레지스터의 값을 새로운 물리적 위치로 바꿔 사용할 수 있는 더 큰 가용 메모리 공간을 만들어 낸다. 이후 OS는 그 큰 가용 메모리 공간을 이용해 새로운 할당 요청을 성공시킬 수 있다.

하지만 압축은 너무 비싸다. 세그먼트를 복사하는 작업이 많은 메모리와 시간을 사용하기 때문이다. 또한 압축은 이미 있는 세그먼트의 크기를 늘리는 일을 어렵게 만들기 때문에, 이후의 요청에 따라 더 많은 재배치가 필요해질 수도 있다.

가용 공간 관리 문제를 해결하기 위해서는 가용-리스트 관리 알고리즘을 이용하는 더 간단한 접근법을 사용할 수도 있다. 이 접근법에는 고전적인 best-fit, worst-fit, first-fit, 혹은 더 어려운 buddy 알고리즘을 포함한 수 백 가지가 있다. 하지만 아무리 똑똑한 알고리즘을 쓰더라도 외부 단편화는 근본적으로 없앨 수 없다.

7. Summary

세그먼테이션을 이용하면 더 효과적인 메모리 가상화 설계가 가능해지고,주소 공간의 논리적 세그먼트 사이에 있을 수 있는 메모리 낭비를 방지할 수 있다.

세그먼테이션은 빠르기도 하다. 왜냐하면 세그먼테이션이 필요로 하는 연산 자체도 쉽고 하드웨어에도 잘 맞기 때문에 변환의 오버헤드가 최소가 되기 때문이다. 세그먼테이션에는 코드 공유와 같은 부가적인 이점도 있다. 별개의 세그먼트에 위치하는 코드는 여러 실행 중인 프로그램 사이에서 잠재적으로 공유될 수 있다.

하지만 다양한 사이즈의 세그먼트들을 메모리에 할당하는 것은 문제를 일으키기도 한다.

• 외부 단편화
  - 세그먼트는 다양한 사이즈를 가지고 있기 때문에 가용 공간들이 잘못된 사이즈로 잘려 메모리 할당을 어려워 질 수 있다. 좋은 알고리즘을 사용하거나 주기적으로 메모리를 압축함으로써 이를 일부 완화할 수는 있겠지만, 이 문제는 근본적이고 해결되기 어렵다.

• 완전히 일반화된 성긴 주소 공간을 위한 충분한 융통성을 가지지는 못한다.
  + 큰 힙 세그먼트를 만들어 놓고 일부만 드문드문 쓰는 경우, 세그먼테이션의 이점을 제대로 살리기 어렵다.
  + 실제 메모리 사용 방식과 세그먼트 설계가 어긋나면 세그먼테이션이 장점을 제대로 살릴 수 없다.