[운영체제 아주 쉬운 세 가지 이야기 - Virtualization] 16. Segmentation
이 글은 제 개인적인 공부를 위해 작성한 글입니다.
틀린 내용이 있을 수 있고, 피드백은 환영합니다.
개요
지금까지 프로세스 주소 공간 전체를 메모리에 탑재하는 것을 가정해 왔다. 베이스와 바운드 레지스터를 사용하면 운영체제는 프로세스를 물리 메모리의 다른 부분으로 쉽게 재배치할 수 있다. 이러한 형태의 주소 공간에서는 스택과 힙 사이에 사용되지 않는 큰 공간이 존재한다.
그림에서 볼 수 있듯이 스택과 힙 사이의 공간은 사용되지 않더라도 주소 공간을 물리 메모리에 재배치할 때 물리 메모리를 차지한다. 베이스와 바운드 레지스터 방식은 메모리 낭비가 심하다. 또한 주소 공간이 물리 메모리보다 큰 경우 실행이 매우 어렵다. 이런 측면에서 볼 때 베이스와 바운드 방식은 유연성이 없다.
그러면 스택과 힙 사이에 큰 빈 영역이 존재하는 대용량 주소 공간을 어떻게 지원할까?
세그멘테이션 : 베이스/바운드의 일반화
1960년대 초에 탄생한 세그멘테이션(segmentation)이라는 아이디어이다. MMU 안에 오직 하나의 베이스와 바운드 쌍만 존재하는 것이 아니라 주소 공간의 논리적인 세그멘트(segment)마다 베이스와 바운드 쌍이 존재한다.
세그멘트는 특정 길이를 가지는 연속적인 주소 공간이다. 우리가 기준을 삼은 주소 공간에는 코드, 스택, 힙의 세 종류의 세그멘트가 있다. 세그멘테이션을 사용하면 운영체제는 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지할 수 있다.
위의 그림을 다시 보고, 주소 공간을 물리 메모리에 배치하려고 한다. 각 세그먼트의 베이스/바운드 쌍을 이용하여 세그멘트들을 독립적으로 물리 메모리에 배치할 수 있다.
위 그림을 보면 64KB의 물리 메모리에 3개의 세그먼트와 운영체제용으로 예약된 16KB 영역이 존재한다.
그림에서 볼 수 있듯이, 사용 중인 메모리에만 물리 공간이 할당된다. 사용되지 않은 영역이 많은 대형 주소 공간(드문드문 사용되는 주소 공간(sparse aaddress space)라고 부른다)을 수용할 수 있다.
세그먼트 지원을 위한 MMU 하드웨어 구조는 에상한 것과 같다. 이 예제의 경우 3쌍의 베이스와 바운드 레지스터 집합이 필요하다
위 그림은 앞의 예에 해당하는 각 레지스터의 값을 보여준다. 각 바운드 레지스터는 세그먼트의 크기를 저장하낟.
그림에서 코드 세그먼트가 물리 주소 32KB에 배치되고 크기는 2KB이며, 힙 세그먼트가 34KB에 배치되고 역시 크기는 2KB인 것을 알 수 있다.
그림 19.1의 주소 공간을 사용하여 주소 변환을 해 보자. 코드 세그먼트에 속하는 가상 주소 100번지를 참조한다고 가정해보자. 참조가 일어나면 하드웨어는 베이스 값에 이 세그먼트의 오프셋(100)을 더해 물리 주소는 100 + 32KB 또는 32868이 된다. 그 후, 주소가 범위 내에 있는지 검사하고(100은 2KB보다 작다), 범위 내에 있을 경우 물리 메모리 주소 32868을 읽는다.
가상 주소 4200의 힙을 살펴보자. 가상 주소 4200을 힙의 베이스(34KB)에 더하면 물리 주소 39016을 얻지만 이 주소는 올바른 물리 주소가 아니다. 먼저 힙 안에서의 오프셋, 즉 주소가 참조하는 바이트가 이 세그먼트 시작으로부터 몇 번째 바이트인지를 얻어야 한다. 힙은 가상주소 4KB(4096)에서 시작하기 때문에 오프셋 4200은 실제로는 4200 - 4096 = 104가 된다. 이 오프셋 104를 베이스 레지스터의 물리 주소 34KB에 더해 원하는 결과 34920을 얻을 수 있다.
만약 힙의 마지막을 벗어난 7KB와 같은 잘못된 주소를 접근하려고 한다면 하드웨어가 그 주소가 범위가 벗어났다는 것을 감지하고 운영체제에 트랩을 발생시킨다. 운영체제는 아마두 문제의 프로세스를 종료시킬 가능성이 크고, 세그먼트 위반(segment violation) 또는 세그먼트 폴트(segment fault)라고 부른다.
세그먼트 종류의 파악
하드웨어는 변환을 위해 세그먼트 레지스터를 사용한다. 하드웨어는 가상 주소가 어느 세그먼트를 참조하는지 그리고 그 세그먼트 안에서 오프셋은 얼마인지를 어떻게 알 수 있는가?
한 가지 일반적인 접근법은 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그먼트로 나누는 것이다. 이 기법은 VAX/VMS 시스템에서 사용되었다. 위의 예에서는 3개의 세그먼트가 있다. 주소 공간을 세그먼트로 나누기 위해서는 2비트가 필요하다. 세그먼트를 표시하기 위해 가상 주소 14비트 중 최상위 2비트를 사용하는 경우 가상 주소 모양은 다음과 같이 보일 것이다.
우리의 예에서 최상위 2비트가 00이면, 하드웨어는 가상 주소가 코드 세그먼트를 가리킨다는 것을 알고, 따라서 코드 세그먼트의 베이스와 바운드 쌍을 사용하여 주소를 정확한 물리 메모리에 재배치한다.
최상위 2비트가 01이면 하드웨어는 주소가 힙 세그먼트라는 것을 인지하여 힙의 베이스와 바운드를 사용한다. 이해를 돕기 위해서 앞에서 사용한 힙에 해당하는 가상 주소(4200)를 변환해 보자. 가상 주소 4200에 해당하는 이진 형식은 다음과 같다.
그림에서 볼 수 있듯이 최상위 2비트(01)는 하드웨어에게 참조하는 세그먼트의 종류를 알려준다. 하위 12비트는 세그먼트 내의 오프셋이다.
000 0010 1000 또는 16진수 0x068 또는 10진수로 104, 하드웨어는 세그먼트 레지스터를 파악하는 데 처음 2비트를 사용하고 세그먼트 오프셋으로 다음 12비트를 취한다. 오프셋에 베이스 레지스터 값을 더하여 하드웨어는 최종 물리 주소를 계산한다.
오프셋은 바운드 검사도 쉽게 만든다. 오프셋이 바운드보다 작은지 여부만 검사하면 된다. 그렇지 않으면 주소가 잘못된 것이다. 베이스와 바운드 쌍을 세그먼트당 하나의 배열 형식으로 저장할 경우, 원하는 물리 주소를 얻기 위하여 다음과 같은 작업을 하게 된다.
우리는 현재 예를 기준으로 위 코드에서 사용된 상수 값들을 정할 수 있다. SEG_MASK는 0x3000, SEG_SHIFT는 12, OFFSET_MASK는 0xFFF로 지정된다.
세그먼트 종류를 나타내는 데 최상위 2비트를 사용하고 주소 공간에는 세 개의 세그먼트(코드, 힙, 스택)만 존재하기 때문에 지정 가능한 세그먼트 하나는 미사용으로 남는다. 즉, 전체 주소 공간의 1/4은 사용이 불가능하다. 이 문제를 해결하기 위해 일부 시스템은 코드와 힙을 하나의 세그먼트에 저장하고 세그먼트 선택을 위해 1비트만 사용한다.
특정 주소의 세그먼트를 하드웨어적으로 파악하는 다른 방법들이 있다. 묵시적(implicit) 접근 방식에서는 주소가 어떻게 형성되었나를 관찰하여 세그먼트를 결정한다. 예를 들어, 주소가 프로그램 카운터에서 생성되었다면 (즉, 명령어 반입) 주소는 코드 세그먼트 내에 있을 것이다. 주소가 스택 또는 베이스 포인터에 기반을 둔다면 주소는 스택 세그먼트 내에 있다. 다른 주소는 모두 힙에 있어야 한다.
스택
스택은 물리 주소 28KB에 배치되어 있지만 한가지 중요한 차이점이 있다. 다른 세그먼트들과는 다르게 반대 방향으로 확잗된다는 것이다. 물리 메모리 28KB에서 시작해서 26KB까지 차지한다. 가상 주소 16KB에서 14KB에 해당한다.
그러므로 다른 방식의 변환이 필요하다.
첫 번째, 간단한 하드웨어가 추가로 필요하다. 베이스와 바운드 값뿐 아니라 하드웨어는 세그먼트가 어느 방향으로 확장하는지도 알아야 한다. 예를 들어, 하나의 비트를 사용하여 주소가 커지는 쪽(양의 방향)으로 확장하면 1, 작아지는 쪽(음의 방향)으로 확장하면 0으로 표시할 수 있다.
위 그림은 이 사실을 반영하여 하드웨어가 관리해야 하는 정보를 표현하고 있다.
하드웨어는 세그먼트가 반대 방향으로 늘어날 수 있다는 것을 알고 있기 떄문에, 그런 가상 주소에 대해서는 다른 방식으로 변환한다. 이 과정을 이해하기 위하여 스택에 해당하는 가상 주소를 예로 들어 변환해 보자.
가령, 가상 주소 15KB에 접근하려고 한다고 가정하자. 이 주소는 물리 주소 27KB에 매핑되어야 한다. 이 가상 주소를 이진 형태로 바꾸면 11 1100 0000 0000 (16진수로 0x3C00)이 된다. 하드웨어는 상위 2비트 (11)를 사용하여 세그먼트를 지정한다. 이를 고려하면 3KB의 오프셋이 남는다. 올바른 음수 오프셋을 얻기 위해서 3KB에서 세그먼트 최대 크기를 빼야 한다.
이 예에서는 세그먼트의 최대 크기가 4KB이고 따라서 올바른 오프셋은 3KB에서 4KB를 밴 -1KB이다. 이 음수 오프셋 -1KB를 베이스 오프셋 28KB에 더하면 올바른 물리 주소 27KB를 얻게 된다. 바운드 검사는 음수 오프셋의 절대값이 세그먼트의 크기보다 작다는 것을 확인하여 계산할 수 있다.
공유 지원
세그멘테이션 기법이 발전함에 따라 시스템 설계자들은 간단한 하드웨어 지원으로 새로운 종류의 효율성을 성취할 수 있다는 것을 깨달았다. 구체적으로, 메모리를 절약하기 위해 때로는 주소 공간들 간에 특정 메모리 세그먼트를 공유하는 것이 유용하다. 특히, 코드 공유가 일반적이며, 현재 시스템에서도 광범위하기 사용 중이다.
공유를 지원하기 위해, 하드웨어에 protection bit의 추가가 필요하다. 세그먼트마다 protection bit를 추가하여 세그먼트를 읽거나 쓸 수 있는지 혹은 세그먼트의 코드를 실행시킬 수 있는지를 나타낸다.
코드 세그먼트를 읽기 전용으로 설정하면 주소 공간의 독립성을 유지하면서도, 여러 프로세스가 주소 공간의 일부를 공유할 수 있다. 각 프로세스는 여전히 자신의 전용 메모리를 사용하고 있다고 생각하지만 운영체제는 이 변경이 불가능하도록 설정된 메모리 영역을 비밀리에 공유시켜 그러한 환상을 유지토록한다.
하드웨어 및 운영체제가 유지하는 부가 정보의 예시는 위와 같다.
코드 세그먼트는 읽기 및 실행으로 설정되어 같은 물리 세그먼트가 여러 가상 주소 공간에 매핑될 수 있다.
protection bit를 사용하면 앞서 언급한 하드웨어 알고리즘이 수정되어야 한다. 가상 주소가 범위 내에 있는지 확인하는 것 이외에 특정 액세스가 허용되는지를 확인해야 한다. 사용자 프로세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 또는 실행 불가 페이지에서 실행하려고 하면 하드웨어는 예외를 발생시켜서 운영체제가 위반 프로세스를 처리할 수 있게 해야 한다.
소단위 대 대단위 세그멘테이션
우리의 예제의 대부분은 소수의 세그먼트인 코드/스택/힙만을 지원하기에 대단위(coarse-grained) 세그멘테이션이라고 생각할 수 있다. 주소 공간을 비교적 큰 단위의 공간으로 분할하기 때문이다.
반대로 일부 초기 시스템은 주소 공간을 작은 크기의 공간으로 잘게 나누는 것이 허용되었기 떄문에 소단위(fine-grained) 세그멘테이션이라고 부른다. 많은 수의 세그먼트를 지원하기 위해서는 세그먼트 테이블같은 여러 세그먼트의 정보를 메모리에 저장할 수 있는 하드웨어가 필요하다. 컴파일러가 코드나 데이터를 여러 세그먼트로 분할할 경우 운영체제와 하드웨어가 이를 지원할 수 있게 하였다. 당시의 생각은 소단위 세그먼트로 관리하는 것이 운영체제가 사용 중인 세그먼트와 미사용중인 세그먼트를 구분하여 메인 메모리를 더 효율적으로 활용할 수 있다는 것이었다.
운영체제의 지원
세그멘테이션은 코드/스택/힙을 각각 별도로 물리 메모리에 배치하기에 전체 주소 공간이 하나의 베이스-바운드 쌍을 가지는 간단한 방식에 비해 물리 메모리를 엄청나게 절약할 수 있다. 구체적으로는 스택과 힙 사이의 사용하지 않는 공간에 물리 메모리를 할당할 필요가 없기에 같은 크기의 물리 메모리에 더 많은 주소 공간을 탑재할 수 있다.
세그멘테이션은 새로운 많은 문제를 제기한다.
먼저, 문맥 교환 시 운영체제는 어떤 일을 해야 하는가? 세그먼트 레지스터의 저장과 복원이다. 각 프로세스는 자신의 가상 주소 공간을 가지며, 운영체제는 프로세스가 다시 실행하기 전에 레지스터들을 올바르게 설정해야 한다.
두 번째, 더 중요한 문제는 미사용 중인 물리 메모리 공간의 관리이다. 새로운 주소 공간이 생성되면 운영체제는 이 공간의 세그먼트를 위한 비어있는 물리 메모리 영역을 찾을 수 있어야 한다. 이전에 우리는 각 주소 공간의 크기가 동일하다고 가정했다. 물리 메모리는 프로세스가 탑재될 슬롯의 집합이라고 생각될 수 있었다. 지금은 프로세스가 많은 세그먼트를 가질 수 있고, 각 세그먼트는 크기가 다를 수 있다.
일반적으로 생길 수 있는 문제는 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워진다는 것이다. 이 작은 빈 공간들은 새로이 생겨나는 세그먼트에 할당하기도 힘들고, 기존 세그먼트를 확장하는 데에도 도움이 되지 않는다. 이러한 문제를 외부 단편화(external fragmentation)라고 부른다.
위 사진에서 새로운 프로세스가 생성되어 20KB를 할당하려고 한다. 왼쪽 예에서느 24KB의 빈 공간이 있지만, 모두 청크로 나누어져 있어 운영체제는 요청을 충족시킬 수 없다.
이 문제를 해결하기 위해 물리 메모리를 압축(compact) 할 수 있다.
운영체제는 현재 실행 중인 프로세스를 중단하고, 그들을 하나의 연속된 공간에 복사하고, 세그먼트 레지스터가 새로운 물리 메모리 위치를 가리키게 하여 자신이 작업할 큰 빈 공간을 확보할 수 있다. 하지만 세그먼트 복사는 메모리에 부하가 큰 연산이고 일반적으로 CPU 시간을 많이 잡아먹기에 압축은 비용이 많이 든다.
간단한 방법은 빈 공간 리스트(free-list, 가용 리스트)를 관리하는 알고리즘을 사용하는 것이다. 이 알고리즘은 할당 가능한 메모리 영역들을 리스트 형태로 유지한다.
최초 적합 (first-fit)
가용 리스트를 처음부터 순차적으로 검색하여 첫번째로 찾은 충분한 크기의 블록에 할당
검색 시간이 최소이지만, 메모리 앞쪽에 작은 청크들이 생겨 외부 단편화 유발최악 적합 (worst-fit)
가장 큰 빈 블록에 할당
남은 조각이 커서 재사용 가능성이 높으나 큰 청크가 빨리 소진최적 적합 (best-fit)
모든 빈 블록을 검색하여 요청 크기에 가장 가까운 블록에 할당
메모리 낭비 최소화지만 전체 검색 시간이 오래 걸림다음 적합 (next-fit)
마지막으로 할당한 위치부터 검색하여 첫번째로 찾은 충분한 크기의 블록에 할당
최초 적합과 유사하지만, 검색 시작 위치를 기억하여 전체 검색 시간을 줄임버디 알고리즘 (buddy algorithm)
메모리를 2의 거듭제곱 크기로 분할하여 관리
외부 단편화가 줄지만, 내부 단편화가 심함
이 외에도 수백 개의 방식이 존재한다. 이러한 알고리즘들이 아무리 잘 동작한다고 해도 외부 단편화는 여전히 존재한다. 좋은 알고리즘의 목표는 외부 단편화를 최소화하는 것이다.
여러 가용 리스트들
묵시적 가용 리스트 (implicit free list)
묵시적 가용 리스트는 블록 헤더의 크기 정보를 이용해 다음 블록을 찾아가는 각 블록들이 묵시적으로 연결된 가용 리스트이다.
현재 블록의 크기가 16바이트라면, 현재 블록에서 16바이트만큼 앞으로 이동하는 식으로 다음 블록을 탐색한다.
구현이 간단하지만 가용 리스트를 탐색하는 비용이 전체 할당된 블록과 가용 블록의 수에 비례한다.
명시적 가용 리스트 (explicit free list)
명시적 가용 리스트는 각 블록들이 포인터로 명시적으로 연결된 가용 리스트이다.
가용 블록의 블록 내에 Predecessor와 Successor 포인터를 추가하여 가용 블록을 연결한다.
기존의 묵시적 가용 리스트에서 전체 블록 수에 비례하는 시간이었던 할당 시간이 가용 블록의 수에 비례하는 것으로 줄어든다.
분리 가용 리스트 (segregated free list)
분리 가용 리스트는 Segregated Storage라고 불리는 여러 개의 가용 리스트를 사용하여 임의의 크기 클래스로 메모리를 분리하여 관리하는 기법이다.
대표적으로 SSS, Segregated Fits, Buddy System이 있다.
Simple Segregated Storage (SSS)
SSS는 동일한 크기의 청크들로 고정 분할하여 가용 리스트를 관리한다.
가용 리스트는 단일 연결 리스트로 구현되며, 헤더나 풋터가 필요하지 않고 후속 가용 블록을 가리키는 포인터만 있으면 된다.
가용 리스트의 청크들은 할당 요청 시에 합쳐지거나 분할되지 않는다.
매우 단순하기에 할당과 해제 모두 O(1)시간에 수행 가능하다.
할당은 가용 리스트의 첫 번째 청크를 꺼내고, 해제는 다시 가용 리스트에 넣기만 하므로 할당 속도의 불확실성을 제거하고 헤더와 풋터가 필요 없기에 메타데이터 오버헤드가 적다.
하지만 SSS는 하나의 풀에서 하나의 크기만 지원하기에 크기가 서로 다른 객체 (ex. 16바이트, 64바이트)가 동시에 필요한 경우 각 크기에 맞는 풀을 따로 만들어야 한다.
또한 내/외부 단편화에 취약하다.
SSS는 다음과 같은 상황에서 매우 유리하다.
- 반복적으로 동일한 크기의 객체가 할당되고 해제되는 경우
- 대량의 소형 객체를 빠르게 생성해야 하는 경우
- 메모리 오버헤드가 시스템 성능에 직접적인 영향을 미치는 임베디드 환경
분리 맞춤 Segregated Fits
Segregated Fits은 여러 개의 가용 리스트를 크기 클래스로 구분하여 관리하는 기법이다.
대표적인 방법으로는 2^k 크기로 분리하여 {1}, {2}, {3, 4}, {5-8}, … , {1,025-2,048}, {2,049-4,096}, {4,097-$\infty$} 식으로 관리할 수 있다.
각 크기 범위는 2^k 이상 2^(k+1) 미만의 크기를 가지는 블록들을 저장한다.
할당을 요청받으면 작은 크기 클래스부터 시작하여 적합한 크기 클래스를 찾는다.
할당 가능한 블록을 찾는 과정이 전체 힙이 아닌 힙의 특정 부분(크기 클래스)에 제한되기에 빠르고 Segregated Fits의 first-fit 검색은 전체 힙의 best-fit 검색의 성능과 근사하다 (== 메모리 효율적이다).
버디 시스템/알고리즘 Buddy System/Algorithm
버디 시스템은 크기 클래스가 2의 제곱인 특수한 경우의 분리 맞춤 방식이다.
예를 들어, 각 블록의 크기가 1, 2, 4, 8, 16인 분리 가용 리스트를 사용한다.
전체 크기가 2^m인 워드에서 2^k 크기의 블록을 할당하려면 k <= j <= m인 크기 2^j인 첫 번째 가용 블록을 찾는다.
만약 j == k라면 그 블록에 할당하면 되고, 아니라면 재귀적으로 j == k일 때까지 블록을 절반으로 분할한다.
이와 같이 분할을 수행할 때 생기는 두 개의 블록은 서로가 서로의 친구 즉, 버디(buddy)가 된다.
크기 2^k인 블록을 해제하려면, 반환하려는 블록의 가용 버디들을 계속해서 연결한다. 할당된 버디를 만나면 연결이 종료된다.
버디 시스템의 핵심은 블록의 주소와 크기가 주어지면 이 블록의 버디 주소를 계산하기 쉽다는 것이다.
만약 크기가 32 바이트인 블록의 주소가 다음과 같다면, 버디의 주소는 아래와 같다.
xxx…x00000
xxx…x10000
즉, 블록과 이 블록의 버디 주소는 정확히 한 비트 위치만 다르다.
버디 시스템은 빠른 검색과 결합(coalescing) 가능하지만, 블록 크기의 2의 거듭제곱이라는 조건 때문에 내부 단편화가 심하다.
참고