가상 메모리, 세그먼테이션(Segmentation) [2 / 4]

junto·2024년 3월 16일

Operating System

operating system

목록 보기

8/13

한 쌍의 베이스-리밋 레지스터를 사용하는 방식은 스택과 힙 사이 사용하지 않는 공간이 단순하게 낭비된다. 베이스-리밋 레지스터를 일반화한 세그먼테이션(Segmentation) 방식에 대해 알아본다.

1. 세그먼테이션

1) 베이스와 리밋 레지스터 일반화

주소 공간의 논리적인 세그먼트(Segment)마다 베이스와 리밋 레지스터 쌍이 존재하도록 한다.
작게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의할 수 있고, 크게는 프로그램 하나를 하나의 세그먼트로 볼 수 있다.
일반적으로 code, data, stack 부분이 하나의 세그먼트로 정의된다.
프로그램마다 세그먼트 테이블(Segment table)이 필요하다. 세그먼트 테이블에는 세그먼트의 시작 주소를 저장하는 레지스터(base register)와 세그먼트 크기를 나타내는 레지스터(limit register)가 존재한다. 추가로 세그먼트 테이블 엔트리 개수를 나타내는 레지스터(Segment Table Length Register)가 존재하여 유효한 엔트리 접근을 보장한다.
뒤에 살펴볼 페이징(Paging)에서는 동일한 크기로 메모리를 분할하기 때문에 크기 정보(limit register)가 필요 없다는 걸 참고하자.

스택과 힙 사이 사용하지 않는 공간에 물리 메모리를 할당할 필요가 없어졌기 때문에 물리 메모리에 더 많은 주소 공간을 올릴 수 있다.

2) 세그먼트 접근 방법

하드웨어는 가상 주소가 어느 세그먼트를 참조하는지 그리고 그 세그먼트 안에서 오프셋은 얼마인지를 어떻게 알 수 있을까? code, data, stack 세그먼트가 있다고 가정한다.

한 가지 일반적인 접근법은 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그먼트로 나누는 것이다. 이는 실제 VAX/VMX 시스템에서 사용되었다.
이를 기준으로 주소 공간을 세그먼트로 나누기 위해서는 2비트가 필요하다. 00은 코드 영역, 01은 힙 영역, 11은 스택 영역 세그먼트를 의미한다. 주소 공간의 4분의 1이 낭비되는 문제를 막기 위해 힙과 스택 영역을 하나의 세그먼트에 저장하여 최상위 비트 1비트만 사용할 수도 있다.
가상 주소 14비트 중 최상위 2비트를 사용하는 경우 가상 주소의 모양은 다음과 같다.

(1) 힙 세그먼트 접근

가상 주소 4200를 물리 주소로 변환해 보자.
이진수로 표현하면 [01 0000 0110 10000]이다.
최상위 2비트는 세그먼트의 종류를 알려주고, 하위 12비트는 해당 세그먼트 내의 오프셋이다. 오프셋에 베이스 레지스터 값을 더하여 하드웨어의 최종 물리 주소를 계산할 수 있다. 코드로 표현하면 아래와 같다.

// SEG_MASK = 0b11'0000'0000'0000
// SEG_SHIFT = 12, OFFSET_MASK = 0b00'1111'1111'1111
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
Offset = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
	RaiseException(PROTECTION_FAULT)
else {
	PhysAddr = Base[Segment] + Offset;
	Register = AccessMemory(PhysAddr);
}

가상 주소 4200은 오프셋이 104가 된다. 위 수식에 따라 베이스 주소가 12288이라면 물리주소는 12288 + 104로 12392가 된다.

(2) 스택 세그먼트 접근

스택은 다른 세그먼트와는 달리 반대 방향으로 확장된다. 스택의 경우 음수 오프셋을 구해야 한다. 음수 오프셋은 전체 세그먼트 크기에서 오프셋을 차감해 주면 구할 수 있다.
가상 주소 15KB 스택 공간을 물리 주소로 변환해 보자.
이진수로 표현하면 [11 1100 0000 0000]이다.
가상 주소 15KB의 오프셋은 3KB[1100 0000 0000]가 된다. 스택의 증가방향은 음수이므로 전체 세그먼트 크기 4KB를 차감해주면 음수 오프셋 -1KB를 구할 수 있다. 스택 베이스 주소가 28KB라면 가상 주소 15KB는 물리 주소 27KB로 변환되는 것을 알 수 있다.
잘 이해가 가지 않는다면 아래 링크에서 구체적인 동작을 시뮬레이션할 수 있다. https://github.com/martalist/ostep/blob/master/chapter_16/README-segmentation
- 스택의 가상 주소 802, base 레지스터 4692, limit 레지스터 450이고, 세그먼트 크기가 1K라고 할 때 해당 가상 주소가 유효한가?
- 스택의 시작 주소는 4692에서 4242까지 가능하다. 스택의 음수 오프셋은 세그먼트 크기(1024 - 802)를 하면 222가 나온다. 시작 주소에서 음수 오프셋을 빼면 해당 가상 주소의 물리 주소는 4470이 되고, 유효한 물리 주소로 판단할 수 있다.

3) 공유 지원(Protection bit)

메모리를 절약하기 위해 특정 메모리 세그먼트를 공유할 수 있다. 이를 위해선 하드웨어 지원을 받아 세그먼트 테이블에 protection bit를 추가한다.
protection bit를 이용하여 세그먼트를 읽고, 쓰고, 실행하는 권한을 제어할 수 있다. 각 프로세스 입장에선 자신의 전용 메모리를 사용한다고 생각하지만, 운영체제는 변경이 불가능하도록 설정된 메모리 영역을 비밀리에 공유시키는 것이다.

2. 빈 공간 할당 방법

세그먼테이션 방식은 물리 메모리가 빠르게 작은 메모리 공간으로 분할된다는 것이다. 외부 단편화를 해결하기 위해 압축(Compaction)을 고려할 수 있으나 세그먼트 복사는 굉장히 메모리 부하가 큰 연산이다. 따라서 다양한 크기의 빈 공간을 관리하는 기본 방법을 알아본다.

1) 최적 적합(Best Fit)

빈 공간 리스트를 검색하여 요청한 크기와 같거나 더 큰 빈 메모리 청그를 찾는다. 그 후 후보자 그룹 중 가장 작은 크기의 청크를 반환한다.

2) 최악 적합(Worst Fit)

가장 큰 빈 청크를 찾아 요청된 크기만큼만 반환하고 남는 부분은 빈 공간 리스트에 계속 유지한다.

3) 최초 적합(First Fit)

요청보다 큰 첫 번째 블럭을 찾아서 요청만큼 반환한다. 빈 공간 리스트 시작 부분에 크기가 작은 객체가 많이 생길 수 있다.

(1) 주소 기반 정렬 적용(address-based ordering)

주소 기반 정렬(address-based ordering)을 사용하여 빈 공간 리스트를 주소로 정렬하면 인접한 공간끼리 쉽게 병합할 수 있다.

(2) 다음 적합(Next Fit)

마지막으로 찾았던 원소를 가리키는 포인터를 추가하여 마지막 위치를 유지한다. 외부 단편화가 리스트 전체에 균등하게 분산되므로 빈 공간 탐색 시간을 줄일 수 있다.

4) 개별리스트와 슬랩 할당기

개별 리스트 방식은 특정 응용 프로그램이 한두 개 자주 요청하는 크기가 있다면, 그 크기의 객체를 관리하기 위해 별도의 리스트 유지한다. 다른 요청은 일반적인 메모리 할당기에 전달한다. 특정 크기 요청을 위한 메모리 청크를 유지하여 외부 단편화를 상당히 줄일 수 있다
슬랩할당기는 커널이 부팅될 때 커널 객체를 위한 여러 객체 캐시(Object Cache)를 할당한다. 커널 객체란 락, 파일 시스템 아이노드 등 자주 요청되는 자료 구조를 말한다. 객체 캐시는 지정된 크기의 객체들로 구성된 빈 공간 리스트이고 메모리 할당 및 해제 요청을 빠르게 하기 위해 사용된다. 이는 객체당 잦은 초기화와 반납의 작업을 피할 수 있어 오버헤드를 현저히 감소시킨다.

5) 이진 버디 할당기

빈 메모리는 처음에 개념적으로 $2^n$ 인 하나의 큰 공간으로 생각된다. 메모리 요청이 발생하면 요청한 공간을 충족시키는 최소 크기가 나올 때까지 계속 분할한다.
2의 거듭제곱 크기의 블럭만 할당할 수 있기에 내부 단편화를 유발한다. 하지만 빈 공간을 결합하는 과정에서 굉장히 효율적으로 동작한다. 예를 들어 8KB 블럭을 반환하면 8KB 블럭이 존재하는 지 확인한다. 비어있다면 병합하여 16KB를 만든다. 16KB 블럭이 비어있는지 확인한다. … 전체 빈 공간이 복원되거나 사용 중인 공간이 생길 때까지 반복한다.

이러한 간단한 방식의 단점은 확장성이다. 빈 공간 개수가 늘어날수록 리스트의 검색이 매우 느려진다. 실제 할당기는 성능 개선을 위해 복잡한 알고리즘을 사용하고 있다. 궁금하다면, 실제로 glibc 할당기가 어떻게 동작하는지 아래 링크로 확인해보자.
https://sploitfun.wordpress.com/2015/02/10/understanding-glibc-malloc/

세그먼트 방식은 세그먼트마다 크기가 다르기 때문에 외부 단편화 문제가 발생한다. 또한, 크기가 아주 크지만 드문드문 사용하는 주소 공간 일부에 접근하기 위해서도 해당 메모리 전체가 물리 메모리에 존재해야 한다는 단점이 있다. 이런 문제를 해결할 수 있는 페이징(Paging)에 대해서 알아보자.