개발 공부
[운영체제][OSTEP] 세그멘테이션
대용량 주소 공간을 지원하는 방법에 대해 공부해봅니다.
![[운영체제][OSTEP] 세그멘테이션](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?auto=format&w=860)
1️⃣ 세그멘테이션: 베이스/바운드(base/bound)의 일반화
💡아이디어
MMU 안에 오직 하나의 베이스와 바운드 쌍만 존재하는 것이 아니라 주소 공간의 논리적인 세그멘트(segment)마다 베이스와 바운드 쌍이 존재
📏 세그멘트 = 특정 길이를 가지는 연속적인 주소 공간
코드, 스택, 힙 세 종류의 세그멘트
➡️ 세그멘테이션을 사용하면 운영체제는 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있음 + 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지
다음의 예시와 함께 이를 살펴보자.
0 KB ┌──────────────────────┐
│ │
1 KB │ │
│ Program Code │
2 KB ├──────────────────────┤
│ │
3 KB │ │
│ │
4 KB ├──────────────────────┤
│ │
5 KB │ Heap │
│ │
6 KB ├──────────────────────┤
│ │ │
│ │ │
│ │ │
│ ↓ │
│ (free) │
│ ↑ │
│ │ │
│ │ │
│ │ │
14 KB ├──────────────────────┤
│ │
15 KB │ Stack │
│ │
16 KB └──────────────────────┘위의 주소 공간을 물리 메모리에 배치하려고 한다. 각 세그멘트의 베이스와 바운드 쌍을 이용하여 세그멘트들을 다음과 같이 독립적으로 물리 메모리에 배치할 수 있다.
0 KB ┌──────────────────────┐
│ │
│ │
│ Operating System │
│ │
│ │
16 KB ├──────────────────────┤
│ │
│ (not in use) │
│ ↑ │
├──────────────────────┤
│ Stack │
├──────────────────────┤
│ (not in use) │
32 KB ├──────────────────────┤
│ Code │
├──────────────────────┤
│ Heap │
├──────────────────────┤
│ ↓ │
│ │
48 KB │ │
│ │
│ (not in use) │
│ │
│ │
│ │
64 KB └──────────────────────┘위의 예시에서 확인할 수 있듯이, 사용 중인 메모리에만 물리 공간이 할당된다.
➡️ 사용되지 않은 영역이 많은 대형 주소 공간(sparse address space라고도 부름)을 수용할 수 있다.
위의 경우 3쌍의 베이스와 바운드 레지스터 집합이 필요하며 이는 세그멘트 레지스터에서 다음과 같이 나타낼 수 있다.
Segment Base Size
──────────────────────────
Code 32K 2K
Heap 34K 3K
Stack 28K 2K이때, 가상 주소 100번지를 참조한다고 가정해보자.
첫 번째 그림에서 100번지는 코드 세그멘트에 속하므로 참조가 일어나면 하드웨어는 베이스 값(32KB)에 이 세그멘트의 오프셋(100)을 더해 물리 주소 32868(100+32KB)을 얻어낸다.
그 후, 주소가 범위 내에 있는지 검사(100 < 2KB)하고, 범위 내에 있을 경우 물리 메모리 주소 32868을 읽는다.
가상 주소 4200번지를 참조하는 경우를 다시 가정해보자.
4200번지는 힙 세그먼트에 속하므로 베이스 값(34KB)에 오프셋(4200-4096(힙은 가상 주소가 4KB에서 시작하므로!))을 더하여 34920(104+34KB)을 얻게 된다.
힙의 마지막을 벗어난 7KB와 같은 잘못된 주소를 접근하는 경우를 가정해보자.
⛔ 하드웨어가 그 주소가 범위를 벗어났다는 것을 감지하고 운영체제에 트랩을 발생
➡️ 세그멘트 폴트(segment fault)가 발생
2️⃣ 세그멘트 종류의 파악
하드웨어는 변환을 위해 세그멘트 레지스터를 사용
가상 주소가 참조하는 세그멘트와 세그멘트 내 오프셋의 크기를 알아내는 일반적인 접근법
➡️ 가상 주소의 최상위 몇 비트를 기준으로 주소 공간을 여러 세그멘트로 나누는 것
➡️ VAX/VMS 시스템에서 사용된 기법
1️⃣의 예시에서는 3개의 세그멘트가 존재 ➡️ 주소 공간을 세그멘트로 나누기 위해 2비트가 필요
세그멘트 표시를 위해 가상 주소 14비트 중 최상위 2비트를 사용하는 경우 가상 주소의 모양은 다음과 같다.
13 12 11 10 9 8 7 6 5 4 3 2 1 0
┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
└──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
└─────┴───────────────────────────────────┘
Segment Offset최상위 2비트의 세그멘트 표기는 다음과 같이 나타낼 수 있다.
00: 코드 세그멘트
01: 힙 세그멘트
11: 스택 세그멘트
따라서 최상위 2비트의 세그멘트 표기를 통해 하드웨어는 그에 해당하는 베이스와 바운드를 사용할 수 있다.
예를 들어, 위의 예시 중 가상 주소 4200번지를 참조하는 경우 그에 해당하는 이진 형식은 다음과 같다.
13 12 11 10 9 8 7 6 5 4 3 2 1 0
┌────────────────────────────────────────┐
0 1 0 0 0 0 0 1 1 0 1 0 0 0
└────────────────────────────────────────┘
└────┴───────────────────────────────────┘
Segment Offset하드웨어는 최상위 2비트 01을 통해 힙 세그먼트를, 하위 12비트 0000 0110 1000을 통해 오프셋 104를 알아낼 수 있다.
오프셋은 바운드 검사도 쉽게 만듦.
➡️ 오프셋이 바운드 보다 작은지 여부만 검사하면 됨.
베이스와 바운드 쌍을 배열 형식으로 저장할 경우(세그멘트당 하나의 항목), 원하는 물리 주소를 얻기 위해 다음과 같은 작업을 수행
// 14 bit VA중의 상위 2 bit를 얻어옴
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)위의 예시를 기준으로 코드의 상수 값들을 다음과 같이 정할 수 있다.
SEG_MASK: 0x3000SEG_SHIFT: 12OFFSET_MASK: 0xFFF
주소 공간에는 세 개의 세그멘트(코드, 힙, 스택)만 존재하기 때문에 지정 가능한 세그멘트 하나는 미사용으로 남음. ➡️ 전체 주소 공간의 1/4은 사용이 불가능
이 문제의 해결을 위해 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하고 세그멘트 선택을 위해 1비트만 사용
특정 주소의 세그멘트를 하드웨어적으로 파악하는 다른 방법 ➡️ 묵시적(implicit) 접근 방식
묵시적 접근 방식에서는 주소가 어떻게 형성되었나를 관찰하여 세그멘트를 결정
주소가 프로그램 카운터에서 생성(명령어 반입): 주소는 코드 세그멘트 내에 있을 것임.
주소가 스택 또는 베이스에 기반을 둠: 주소는 스택 세그멘트 내에 있음.
다른 모든 주소: 힙 세그멘트 내에 있음.
3️⃣ 스택
다른 세그멘트들과는 반대 방향으로 확장
➡️ 다른 방식의 변환이 필요
간단한 하드웨어가 추가로 필요
➡️ 베이스와 바운드 값뿐 아니라 하드웨어는 세그멘트가 어느 방향으로 확장하는지도 알아야 함.
ex) 하나의 비트를 사용하여 주소가 커지는 쪽으로 확장하면 1, 작아지는 쪽으로 확장하면 0으로 설정
이 사실을 반영하여 세그멘트 레지스터 상에서 하드웨어가 관리해야하는 정보를 다음과 같이 표현할 수 있다.
Segment Base Size(max 4K) Grows Positive?
─────────────────────────────────────────────────────
Code(00) 32K 2K 1
Heap(01) 34K 3K 1
Stack(11) 28K 2K 0예를 들어, 1️⃣의 예시 상황에서 가상 주소 15KB에 접근한다고 가정해보자.
이 주소는 물리 주소 27KB에 매핑 되어야 한다.
이 가상 주소를 이진 형태로 바꾸면 다음과 같다.
13 12 11 10 9 8 7 6 5 4 3 2 1 0
┌────────────────────────────────────────┐
1 1 1 1 0 0 0 0 0 0 0 0 0 0
└────────────────────────────────────────┘
└────┴───────────────────────────────────┘
Segment Offset하드웨어는 최상위 2비트(11)을 사용하여 스택 세그먼트를 지정하고, 3KB의 오프셋이 남게 된다.
올바른 음수 오프셋을 얻기 위해 3KB에서 최대 크기(4KB)를 뺀 -1KB를 얻는다.
이 음수 오프셋을 베이스에 더하여 올바른 물리 주소 27KB(-1KB + 28KB)
바운드 검사는 음수 오프셋의 절댓값이 세그멘트의 크기보다 작다는 것을 확인하여 계산할 수 있음.
4️⃣ 공유 지원
메모리 절약을 위해 때로는 주소 공간들 간에 특정 메모리 세그멘트를 공유하는 것이 유용
➡️ 특히, 코드 공유가 일반적(현재 시스템에서도 광범위하게 사용 중)
공유 지원을 위해 하드웨어에 protection bit의 추가가 필요
➡️ 세그멘트를 읽거나 쓸 수 있는지 혹은 세그멘트의 코드를 실행시킬 수 있는지를 나타냄.
코드 세그멘트를 읽기 전용으로 설정 ➡️ 주소 공간의 독립성을 유지하면서도, 여러 프로세스가 주소 공간의 일부를 공유할 수 있음.
이를 반영하여 세그멘트 레지스터 값에 부가 정보를 추가하면 다음과 같이 나타낼 수 있다.
Segment Base Size(max 4K) Grows Positive? Protection
───────────────────────────────────────────────────────────
Code(00) 32K 2K 1 Read-Execute
Heap(01) 34K 3K 1 Read-Write
Stack(11) 28K 2K 0 Read-Writeprotection bit를 사용하면 앞의 하드웨어 알고리즘이 수정되어야 함.
➡️ 가상 주소가 범위 내에 있는 지 확인 + 특정 엑세스가 허용되는지 확인
사용자 프로세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 또는 실행 불가 페이지에서 실행하려고 하는 경우
➡️ 하드웨어는 예외를 발생시켜 운영체제가 위반 프로세스를 처리할 수 있게 해야 함.
5️⃣ 소단위 대 대단위 세그멘테이션
지금까지 예제의 대부분은 소수의 세그멘트(코드, 스택, 힙)만들 지원하는 시스템에 주로 초점을 맞춤.
➡️ 주소 공간을 비교적 큰 단위의 공간으로 분할하므로 이 세그멘테이션을 대단위(coarse-grained)라고 생각할 수 있음.
일부 초기 시스템은 주소 공간을 작은 크기의 공간으로 잘게 나누는 것이 허용되었음.
➡️ 소단위(fine-grained) 세그멘테이션
많은 수의 세그멘트를 지원하기 위해서는 여러 세그멘트의 정보를 메모리에 저장할 수 있는 세그멘트 테이블과 같은 하드웨어가 필요
➡️ 매우 많은 세그멘트를 손쉽게 생성하고 융통성 있게 세그멘트를 사용할 수 있음.
💡 당시 소단위 세그멘테이션의 목표: 메인 메모리를 더 효율적으로 활용하자!
6️⃣ 운영체제의 지원
세그멘테이션의 사용 = 하나의 베이스-바운드 쌍을 사용하는 방식에 비해 물리 메모리를 엄청나게 절약
⚠️ 세그멘테이션은 새로운 많은 문제를 제기
[1. 문맥 교환 시 운영체제는 어떤 일을 해야 하는가?]
세그멘트 레지스터를 저장하고 복원해야 함.
[2. 미사용 중인 물리 메모리 공간의 관리]
새로운 주소 공간이 생성 ➡️ 운영체제는 이 공간의 세그멘트를 위한 빈 물리 메모리 영역을 찾을 수 있어야 함.
일반적으로 생길 수 있는 문제 ➡️ 물리 메모리가 빠르게 작은 크기의 빈 공간들로 채워짐.
➡️ 외부 단편화(external fragmentation)
Not Compacted Compacted
0 KB ┌──────────────────────┐ 0 KB ┌──────────────────────┐
│ │ │ │
8 KB │ Operating System │ 8 KB │ Operating System │
│ │ │ │
16 KB ├──────────────────────┤ 16 KB ├──────────────────────┤
│ (not in use) │ │ │
24 KB ├──────────────────────┤ 24 KB │ │
│ Allocated │ │ Allocated │
32 KB ├──────────────────────┤ 32 KB │ │
│ (not in use) │ │ │
├──────────────────────┤ │ │
40 KB │ Allocated │ 40 KB ├──────────────────────┤
├──────────────────────┤ │ │
48 KB │ │ 48 KB │ │
│ (not in use) │ │ (not in use) │
56 KB ├──────────────────────┤ 56 KB │ │
│ Allocated │ │ │
64 KB └──────────────────────┘ 64 KB └──────────────────────┘이와 같은 문제의 해결책 중 하나로 위와 같이 기존의 세그멘트를 정리하여 물리 메모리를 압축(compact)하는 방법이 있다.
위의 그림에서 왼쪽과 같이 압축이 되지 않은 상태에서는 20KB의 크기를 갖는 새로운 프로세스를 위한 공간을 할당할 수 없다.
반면 운영체제가 현재 실행 중인 프로세스를 중단하고, 그들의 데이터를 하나의 연속된 공간에 복사하고, 세그멘트 레지스터가 새로운 물리 메모리 위치를 가리키게 하여 작업을 위한 큰 빈 공간을 확보할 수 있다.
⚠️ 하지만 세그먼트 복사는 메모리에 부하가 큰 연산 & 일반적으로 상당량의 프로세서 시간을 사용
💡 간단한 방법: 빈 공간 리스트를 관리하는 알고리즘을 사용
최적 적합(best-fit)
최악 적합(worst-fit)
최초 적합(first-fit)
버디 알고리즘(buddy algorithm)
등을 포함한 수백 개의 방식이 존재
알고리즘이 아무리 정교하게 동작한다고 해도 외부 단편화는 여전히 존재
➡️ 좋은 알고리즘은 외부 단편화를 가능한 줄이는 것이 목표
🧺 세그멘테이션 정리 하기
✅ 메모리 가상화를 효과적으로 실현할 수 있음.
✅ 단순한 동적 재배치를 넘어 주소 공간 상의 논리 세그멘트 사이의 큰 공간에 대한 낭비를 피함.
➡️ sparse address space를 지원
✅ 세그멘테이션에 필요한 산술 연산은 쉽고 하드웨어 구현에 적합 ➡️ 속도가 빠름.
✅ 변환 오버헤드도 최소임.
✅ 코드 공유의 장점도 부가적으로 발생
⚠️ 세그멘트의 크기가 일정하지 않으므로 외부 단편화 문제 발생
⚠️ sparse address space를 지원할 만큼 충분히 유연하지 못함.
![[운영체제][OSTEP] 주소 변환의 원리](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?ar=1&auto=format&crop=focalpoint&dpr=0.47&fit=crop&fp-x=0.5&fp-y=0.5&w=430)