[OS] Base & Bounds의 한계와 Segmentation의 등장

 

Base & Bounds 방식의 문제점?

먼저, 세그멘테이션이 왜 나왔는지부터 파악해보자.

지난번에 포스팅했던 Base & Bounds 방식 기억에서 프로세스가 사용하는 메모리 영역 전체를 물리 메모리 어딘가에 통째로(contiguous) 배치하고, 시작 주소(Base)와 크기(Bounds) 두 개로 관리하는 방법이었다.

 

 

이 방식의 가장 큰 문제점은 바로 'waste'가 발생한다는 것이다.

 

 

 

가상 주소 공간(Virtual Address Space)을 보면, 프로그램 Code, Heap, Stack 사이에 실제로 쓰지 않는 거대한 "free space"이 있다. 예를 들어, 32비트 주소 공간(4GB) 중 실제 프로그램이 쓰는 건 몇 MB 안 되는데, Base & Bounds 방식은 이 4GB 전체를 물리 메모리에 올려야 한다고 가정해 버린다.

이런 비효율을 해결하려고 나온 게 segmentation이다

 

 

 

---

 

 

 

 

Segmentation: 논리적 분할

Segmentation의 기본적인 아이디어는 Base & Bounds를 여러 개 쓰는 것이다.

 

Segment란?

Segment는 주소 공간의 논리적으로 구분된 연속적인 부분이다. 보통 프로그램의 구조에 맞춰 Code, Heap, Stack 이렇게 세 가지 논리적 Segment로 나눈다.

 

Segmentation의 핵심 원리

각 Segment(Code, Heap, Stack)마다 독립적인 Base와 Bounds 쌍을 준다. 그리고 OS는 이 각각의 세그먼트들을 물리 메모리의 서로 다른 위치에 배치할 수 있게 된다.

 

예를 들어 다음과 같은 그림을 보자

 

 

64KB 물리 메모리에 3가지 Segments가 존재한다. 오직 사용되는 공간만 할당되며 MMU는 3가지 base & bound 레지스터 쌍을 갖는다. 따라서 각각의 segment는 독립적으로 물리 메모리에 존재한다.

 

 

 

위 그림과 같이 Base and Bounds방식과 Segmentation방식을 비교해보면 더 명확하다

• Base and Bounds방식은 heap과 stack사이 10KB공간이 할당되지만 사용할 수 없어 낭비된다.
• Segmentation방식에서는 각각의 Segment들(Code, Heap, Stack)이 독립적으로 물리 메모리에 할당되고 사용되지 않는 부분은 할당되지 않아 낭비되지 않는다.

 

 

 

---

 

 

Segmentation의 Address Translation방법

Segmentaion 환경에서 CPU가 가상 주소(Virtual Address)를 주면, MMU(Memory Management Unit)가 물리 주소(Physical Address)로 바꿔줘야 한다.

 

Code Segment 주소 변환

Code Segment는 가장 쉽다. 처음 시작(offset)에 base를 더해주면 물리 주소를 알 수 있다.

 

 

 

위의 예시에서 offset이 100이고, Base가 32KB이기 때문에 100 + 32KB가 물리 주소가 된다.

Code segment는 가상 주소 0부터 시작하기 때문에 주소 변환이 직관적이고 쉽다.

 

 

Heap Segment 주소 변환

Heap Segment는 Code Segment 바로 다음에 오기 때문에 가상주소가 0이 아닌, 특정 주소에서 시작한다.

따라서 Virtual address + base가 아닌 Offset of Virtual address + base이기 때문에 이 점에 유의해야된다.

 

 

 

 

위의 그림에서 Virtual address는 4200이다. 따라서 offset of Virtual address는 4200 - 4KB =  104이다.

따라서 물리 주소는 104 + 34KB이다. Offset을 계산할 때, Segment가 Virtaul address 공간의 어디서 시작하는지 파악하는 것이 중요하다. 

 

 

Stack Segment 주소 변환

Stack은 Code나 Heap과는 다르게, 메모리 주소 값이 낮은 쪽으로 자라나는, 그러니까 역방향으로 자라는 특성이 있다.

위의 이유로 하드웨어(MMU)는 세그먼트 레지스터에 이 방향 정보를 담아야한다.

 

위와 같이 Grwos Positive값이 0이면 역방향으로 생각한다.

 

 

Code나 Heap처럼 가상주소에서 시작 주소를 빼는 방식으로 Offset을 계산하면 안 된다. 왜냐하면 스택은 가장 높은 주소부터 데이터를 채우기 때문이다.

그래서 스택의 Offset을 계산할 때는, 가상 주소 비트에서 뽑아낸 Offset값에다가 스택 세그먼트의 최대 크기를 빼줘야 실제 Base로부터의 거리가 나온다.

 

 

 

위의 예시에서 Stack의 물리 주소를 구해보자

1. 실제 Offset 계산: 추출된 Offset (3KB) - Max Segment Size (4KB)  = -1KB
2. Bound Check: 절댓값(-1KB) < Size(2KB) 확인
3. 물리 주소 계산: Stack base (28KB) + (-1KB) = 27KB

 

 

 

Segmentation Fault or Violation

Code, Heap, Stack 세그먼트의 주소를 물리 주소로 바꾼다. 근데 이 과정에서 Bounds Check가 엄청나게 중요하다. MMU가 주소 변환을 할 때, 접근하려는 위치가 Segment안에 있는지 체크하는 과정이다.

 

만약 프로그램이 할당된 세그먼트의 크기를 넘어선 주소에 접근하려고 하면 어떻게 될까?

이런 경우, 하드웨어는 즉시 Segmentation Fault라는 예외를 발생시키고, OS는 해당 프로세스를 강제 종료시켜 버린다.

 

 

 

위의 예시에서 Heap segment의 시작지점은 4KB이고 접근하려는 가상 주소는 7KB이다. 따라서 Offset은 7KB - 4KB = 3KB가 되고, bound인 2보다 크기 때문에 Segmentation Fault가 발생한다.

 

 

 

---

 

 

 

Segment를 찾는 방법

주소 변환을 하려면 Code, Heap, Stack 중 어느 Segment를 사용할지 판단하는 Segment 식별 과정이 필요하다.

우리가 쓰는 가상 주소는 사실 두 부분으로 나뉘어 있다.

 

1. Segment ID: 주소의 최상위 몇 비트를 사용해서 어느 세그먼트인지 고르는 것이다. 3가지 세그먼트를 구분하면 되기에 보통 상위 2개의 비트를 사용한다. (Code: 00, Heap: 01, Stack: 11)
2. Offset: 나머지 비트는 해당 세그먼트 내에서의 상대적인 위치를 나타낸다.

 

 

위 예시를 보면 상위 2개의 비트 값이 01이기 때문에 Heap Segment이다. 그리고 Offset은 104이다. 

 

 

 

Segment의 장점: Sharing and Protection

세그멘테이션의 강력한 장점 중 하나는 Sharing과 Protection가 쉽다는 것이다.

1. Segment Sharing:
   • 여러 프로세스가 같은 Code segment를 공유하기가 아주 쉽다. 예를 들어, 같은 웹 브라우저를 여러 개 띄워도 실행 파일 코드는 딱 한 번만 메모리에 올리고, 각 프로세스의 세그먼트 레지스터만 동일한 물리 주소를 가리키게 하면 된다. 
2. Protection:
   • 각 세그먼트마다 Protection Bits를 둬서 읽기, 쓰기, 실행 권한을 따로 설정할 수 있다. 

 

 

 

---

 

 

 

 Fine-Grained vs. Coarse-Grained 

세그멘테이션을 적용할 때, 논리적인 단위를 어떻게 나누느냐에 따라 두 가지 방식이 있다. 세그먼트를 나누는 방식, 즉 세분화 정도의 차이이다.

1. Coarse-Grained Segmentation:
   • 특징: 상대적으로 크기가 큰 세그먼트를 적게 사용하는 방식이다.
   • 예시: 우리가 지금까지 이야기한 Code, Heap, Stack처럼, 프로그램의 주요 논리적 부분을 통째로 묶는 것이다.
2. Fine-Grained Segmentation:
   • 특징: 크기가 작은 세그먼트를 많이 사용하는 방식이다.
   • 장점: 이렇게 쪼개면 메모리 공간을 훨씬 유연하게 배치할 수 있다. 
   • 단점: 세그먼트가 많아지니까 이걸 관리할 세그먼트 테이블이 커지고, 그만큼 하드웨어 지원이 더 많이 필요해진다.

 

 

---

 

 

OS의 역할

Segmentation 방식을 유지하기 위해서는 OS의 역할이 필수적이다.

• Context switch handling:
  • 프로세스가 바뀔 때마다 OS는 해당 프로세스의 모든 Segment 레지스터(Base, Bound)값을 저장하고 다음 프로세스의 값으로 복원해야한다. 
• Handling segment growth:
  • malloc() 호출처럼, 프로그램이 실행 중에 Heap 같은 세그먼트의 크기를 늘려달라고 요청할 수 있다.
  • 공간이 부족하면 sbrk()같은 system call이 발생한다. 
  • 이때 OS는 새로운 물리 메모리 공간을 할당하고 해당 세그먼트의 크기 레지스터 (Bounds)를 업데이트해서 세그먼트를 늘려야된다. 

 

 

 

Segmentation의 문제: External Fragmentation

 

• 문제: 세그먼트의 크기가 가변적이기 때문에, 메모리 할당과 해제가 반복되면 작은 빈 공간들이 흩어져 생기게 된다. 이를 외부 단편화(external fragmentation)라고 한다
• 현상: 프로세스들이 메모리를 할당받고 반납하는 과정이 반복될수록, 물리 메모리에는 총합은 크지만, 하나로 연속되지 않은 수많은 작은 빈 공간들만 남게 된다.

 

 

 

만약 위의 상황에서 20KB segment 요청이 오면 만족하지 못한다. (총합은 24KB이지만 연속적인 20KB가 없기 때문)

 

 

Solution: Compation

이 문제를 해결하기 위해 등장한 방법 중 하나이다. 쉽게 말하면 작은 메모리 구멍을 하나의 큰 덩어리 공간으로 만드는 과정이다.

 

1. 실행 중인 프로세스를 멈추고
2. 물리 메모리 상의 세그먼트들을 한쪽으로 몰아서 복사하고
3. Base 주소를 업데이트 하는 방식이다. 

 

하지만 이 방식은 높은 비용과 Segment 성장 부작용과 재배치 문제가 발생한다. 

 

 

이러한 비용과 복잡성 때문에, OS 개발자들은 Best-fit, First-fit 같은 더 좋은 할당 알고리즘을 사용해서 단편화를 줄이려고 했지만,

근본적인 구조상 external fragment를 완전히 제거할 수는 없었다.

 

 

 

Paging으로의 전환

Segmentation은 각 세그먼트가 물리 메모리에 연속적으로 존재해야 하므로, 세그먼트 전체를 한 번에 메모리에 올려야 한다는 제약이 있다.
이러한 구조적 한계와 외부 단편화 문제로 인해, 현대 OS에서는 Paging 기법이 주류 메모리 관리 방식으로 자리 잡게 되었다.

 

 

 

 

 

 

 

출처: 경북대학교 한명균 교수님, “운영체제” 강의 자료