10. Segmentation¶

Inefficiency of the Base and Bound Approach¶

Recall: 09. Address Translation

• Base and Bound 문제점

• MMU 안에 오직 하나의 베이스와 바운드 쌍만 존재

1. 내부 단편화(internal fragmentation)

   현재 접근 방식에서 비록 더 많은 프로세스를 탑재할 수 있는 충분한 물리 메모리가 있더라도, 고정 크기의 슬롯에 주소 공간을 배치하고 할당된 영역의 내부 공간(스택과 힙 사이 메모리) 이 사용되지 않아 내부 단편화가 발생한다. (= 메모리 낭비)

2. 유연성 없음

   주소공간이 물리 메모리보다 큰 경우 실행이 어렵다.

세그멘테이션 (Segmentation)¶

세그멘트(Segment)¶

가변 분할 방식을 이용한 가상 메모리 관리기법
물리 메모리를 프로세스 크기에 따라 가변적으로 나누어 사용한다.

시스템이 각 주소 공간 구성 요소를 별도로 물리 메모리에 재배치하기 때문에 전체 주소 공간이 하나의 베이스-바운드 쌍을 가지는 간단한 방식에 비해 물리 메모리를 엄청나게 절약할 수 있다.
구체적으로는 스택과 힙 사이의 사용하지 않는 공간에 물리 메모리를 할당할 필요가 없기 때문에 같은 크기의 물리 메모리에 더 많은 주소 공간을 탑재할 수 있다.

• Segment: 특정 길이를 가지는 연속적인 주소 공간

  • 주소 공간의 논리적인 세그멘트(segment) 마다 베이스와 바운드 쌍이 존재한다.
  • 기존 주소 공간에서 보면 코드, 스택, 힙 세 종류의 세그멘트가 있다고 할 수 있다.
  • 운영체제는 각 세그멘트를 물리 메모리의 각기 다른 위치에 배치할 수 있고, 사용되지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지할 수 있다.

• 주소 공간
  

주소 공간을 물리 메모리에 배치하려고 한다.

• 각 세그멘트의 베이스와 바운드 쌍을 이용하여 세그멘트들을 독립적으로 물리 메모리에 배치할 수 있다.
• Base Bound 레지스터 3개 사용
• 64 KB의 물리 메모리에 3개의 세그멘트와 운영체제용으로 예약된 16 KB 영역이 존재한다.
  1. 코드 세그멘트가 물리 주소 32 KB, 크기는 2 KB
  2. 힙 세그 멘트가 34 KB에 배치, 크기는 2 KB
     (cf. 바운드 레지스터는 세그멘트의 크기를 저장)

운용 방법¶

• 각 세그멘트를 독립적으로 구분

  → 물리 메모리의 각기 다른 위치에 배치 가능, 사용하지 않는 가상 주소 공간이 물리 메모리를 차지하는 것을 방지

• 사용 중인 메모리에만 물리 공간 할당
  Placing Segment In Physical Memory

  사용되지 않은 대형 주소 공간 = 드문드문 사용되는 주소 공간, sparse address space)을 활용할 방법이 주어짐 - 세그멘트별로 베이스와 바운드 레지스터 집합은 시작 지점과 크기를 저장

• 세그멘트별로 베이스와 바운드 레지스터 집합은 시작 지점과 크기를 저장

주소 변환¶

참조 발생 시 기본적으로 하드웨어는

\(물리\ 주소 = 베이스\ 값 + 세그멘트의\ 오프셋(위치)\)

형태로 값을 구하고, 범위 내 있는지 검사 후 주소를 읽는다.

코드 세그멘트에 속하는 가상 주소 100 번지를 참조한다고 가정하자.

참조가 일어나면 하드웨어는 베이스 값에 이 세그멘트의 오프셋(이 경우, 100) 을 더해 물리 주소는 \(100+32 KB\) 또는 \(32868\)이 된다. 그 후, 주소가 범위 내에 있는지 검사하고 (= 100은 2 KB보다 작다), 범위 내에 있을 경우, 물리 메모리 주소 \(32868\)를 읽는다.

가상 주소 4200의 힙을 살펴보자.

가상 주소 4200을 힙의 베이스 (34 KB)에 더하면 물리 주소 39016을 얻지만 이 주소는 올바른 물리 주소가 아니다.
먼저 힙 안에서의 오프셋, 즉 주소가 참조하는 바이트가 이 세그멘트 시작으로부터 몇 번째 바이트인지를 얻어야 한다.

힙은 가상 주소 4 KB(4096) 에서 시작하기 때문에 오프셋 4200은 실제로는 \(4200 - 4096\), 즉 104가 된다.

이 오프셋 (104)을 베이스 레지스터의 물리 주소 (34 KB)에 더해 원하는 결과 34920을 얻게 된다.

세그멘테이션 폴트 (Segmentation Fault)¶

세그멘트 사용 시스템에서 불법적인 주소 접근 시 발생한다.
단, 세그멘트를 지원하지 않는 시스템에서도 여전히 (관습적으로) 사용.

• 범위를 벗어나는 경우 (잘못된 주소를 접근하는 경우)
  1. 하드웨어가 주소 오류 감지한다.
  2. 운영체제에서 트랩 발생한다.
  3. (주로) 프로그램 종료

세그멘트 종류의 파악¶

• 주소 변환을 위해 하드웨어적으로 파악해야 할 것
  1. 가상주소가 참조하는 세그멘트
  2. 해당 세그멘트 내 오프셋 값

Explicit Approach: 가상 주소 최상위 비트를 기준으로 나누기¶

• 최상위 2비트를 세그멘트 구분 영역으로 사용하여 구분, 하드웨어는 구분된 영역을 바탕으로 주소를 정확한 물리 메모리에 재배치

• VAX, VMS 시스템에서 사용
  VAX(Virtual Address eXtension)는 DEC(디지털 장비 회사)에서 개발한 가상 메모리 구현 방식으로, VMS(Virtual Memory System) 운영 체제에서 사용된다.

주소 공간을 세그멘트로 나누기 위해서는 2비트가 필요하다.
세그멘트를 표시하기 위해 가상 주소 14비트 중 최상위 2비트를 사용하는 경우 가상 주소의 모양은 다음과 같이 보일 것이다.

1. 최상위 2비트가 00

   하드웨어는 가상 주소가 코드 세그멘트를 가리킨다는 것을 알고, 코드 세그멘트의 베이스와 바운드 쌍을 사용하여 주소를 정확한 물리 메모리에 재배치한다.

2. 최상위 2비트가 01

   하드웨어는 주소가 힙 세그멘트라는 것을 인지하여 힙의 베이스와 바운드를 사용한다.

이해를 돕기 위해서 앞에서 사용한 힙에 해당하는 가상 주소 (4200)를 변환해 보자.

하드웨어는 세그멘트 레지스터를 파악하는 데 처음 2비트를 이용하고 세그멘트 오프셋으로 다음 12비트를 취한다.

• 최상위 2비트 (01): 하드웨어에게 참조하는 세그멘트의 종류 = 힙 세그멘트라는 것을 인지
• 하위 12비트: 세그멘트 내의 오프셋
  • 2진수 0000 0110 1000
  • 16진수 0x068
  • 10진수 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 = 0x3000 (11000000000000)
• SEG_SHIFT = 12

• OFFSET_MASK = 0xFFF (00111111111111)

• 문제점

  세그멘트 종류를 나타내는 데 2^2 = 4가지 경우가 있는데,
  실제 주소 공간에는 세 개의 세그멘트 (코드, 힙, 스택)만 존재하기 때문에 지정 가능한 세그멘트 하나는 미사용으로 남는다.
  즉, 전체 주소 공간의 1/4은 사용이 불가능하다.
  이 문제를 해결하기 위해 일부 시스템은 코드와 힙을 하나의 세그멘트에 저장하고 세그멘트 선택을 위해 1비트만 사용한다.

묵시적(implicit) 접근 방식¶

주소가 어떻게 형성되었는지 관찰하여 세그멘트 결정.

주소가 프로그램 카운터에서 생성 (= 명령어 반입) → 코드 세그멘트

스택 혹은 베이스 포인터에 기반 → 스택 세그멘트

그 외 → 힙 세그멘트

Stack Segment¶

스택은 다른 세그멘트와 달리 반대 방향으로 확장
→ 하드웨어는 세그멘트가 어느 방향으로 확장하는지 저장하는 기능을 추가적으로 지원해야 한다.

물리메모리 28KB → 26KB
가상 메모리 16KB → 14KB

1일 경우, 주소가 커지는 쪽으로 확장
0 일 경우, 주소가 작아지는 쪽으로 확장

스택 가상 주소 변환¶

반대 방향으로 확장하는 스택에 대해서는 가상 주소 15 KB (물리 주소 27 KB 매핑) 에 접근하려고 한다고 가정하자.

이 가상 주소를 이진 형태로 바꾸면 11 1100 0000 0000 (16진수 0x3C00)이 된다.
하드웨어는 상위 2비트 (11)를 사용하여 세그멘트를 지정한다.
이를 고려하면 3 KB의 오프셋이 남는다.

올바른 음수 오프셋을 얻기 위해서 3 KB 에서 세그멘트 최대 크기 (2^12) 를 빼야 한다.

이 예에서는 세그멘트의 최대 크기가 4 KB이고 따라서 올바른 오프셋은 3 KB에서 4 KB를 뺀 -1 KB이다.
이 음수 오프셋 (-1 KB)을 베이스 (28 KB)에 더하면 올바른 물리 주소 27 KB를 얻게 된다.
바운드 검사는 음수 오프셋의 절댓값이 세그멘트의 크기보다 작다는 것을 확인하여 계산할 수 있다.

공유 지원¶

메모리 절약을 위해 주소 공간들 사이에 특정 메모리 세그멘트를 공유하도록 하드웨어가 지원 (일반적으로 코드 공유)
세그멘트마다 Protection bit를 추가하여 읽기, 쓰기, 실행이 가능한지 표시.
→ 현행 시스템에서 광범위하게 사용.

코드 세그멘트는 읽기 및 실행으로 설정되어 같은 물리 세그멘트가 여러 가상 주소 공간에 매핑될 수 있다.

Protection Bit¶

• 하드웨어에 Protectin bit 추가 필요함
  1. 특정 액세스가 허용되는지를 확인
  2. 사용자 프로세스가 읽기 전용 페이지에 쓰기를 시도하는 경우 또는 실행 불가 페이지에서 실행하려고 하면 하드웨어는 예외를 발생시켜서 운영체제가 위반 프로세스를 처리할 수 있게 해야 한다.

액세스 종류

1. 읽기

   읽기 전용으로 설정 시, 주소 공간의 독립성을 유지하면서도 여러 프로세스가 주소 공간의 일부 공유 가능
   운영체제는 이 영역을 공유하여 각 프로세스가 자신의 전용 메모리를 사용하고 있다고 생각하도록 처리

2. 쓰기
3. 실행

메모리 사용 시 protection bit의 추가로 가상 주소의 범위 검사 외에도 특정 권한이 허용되어 있는지 확인이 필요

세그멘테이션의 규모¶

대단위 세그멘테이션(Coarse-grained segmentation)¶

코드, 스택, 힙 등 소수의 세그멘트로 구성된 시스템에서의 세그멘테이션.

주소 공간을 비교적 큰 단위의 공간으로 분할하기 때문

소단위 세그멘테이션(Fine-grained segmentation)¶

Multics와 같은 초기 시스템에서 지원한 것과 같이 작은 크기의 공간으로 주소 공간을 잘게 나누는 것이 허용된 체계.

여러 세그멘트 정보를 메모리에 저장할 세그멘트 테이블 과 같은 하드웨어가 필요.

컴파일러가 코드, 데이터를 여러 세그멘트로 분할 → 운영체제와 하드웨어가 지원하는 구조

[info]
소단위 세그멘트로 관리하는 것이 사용 중인 세그멘트와 사용하지 않고 있는 세그멘트를 구분하여 메인 메모리를 보다 효율적으로 사용할 수 있을 것이라는 생각에 기초

운영체제의 지원¶

세그멘테이션의 문제¶

1. 문맥 교환 시 세그멘트 레지스터의 저장과 복원

   각 프로세스가 자신의 가상 주소 공간을 갖고, 운영체제는 프로세스 재실행 전 레지스터를 올바르게 설정해야한다.

2. 사용하지 않는 물리 메모리 공간의 관리

   세그멘트 크기가 같다고 가정하고 이야기를 했지만 실제로는 새로운 주소 공간 생성 시 사용할 비어있는 물리 메모리 영역을 알고 있어야 프로세스가 많은 세그멘트를 가질 수 있으며 크기가 다를 수도 있다.

3. 외부 단편화 (External fragmentation)

   물리 메모리가 작은 크기의 빈 공간으로 채워지는 현상. 새 세그멘트에 할당하기 어렵고, 기존 세그멘트 확장에도 도움이 되지 않는다.

해결: 물리 메모리의 압축(compact)¶

기존 세그멘트를 정리하여 공간을 확보하는 것.

절차

1. 운영체제가 현재 실행 중인 프로세스를 중단
2. 하나의 연속된 공간에 프로세스의 데이터를 복사
3. 세그멘트 레지스터가 새로운 물리 메모리 위치를 가리키도록 변경
4. 빈 공간 확보

단점

• 메모리에 부하가 큰 연산
• 상당량의 프로세서 시간 사용

→ 비용이 많이 든다

요약¶

세그멘테이션 장점¶

• 산술 연산이 쉽다
• 하드웨어 구현에 적합하여 속도가 빠르다
• 변환 오버헤드가 최소

단점¶

• 외부 단편화
• 드문드문 사용되는 주소 공간 지원에 유연하지 못함.
  크기가 크지만 잘 사용되지 않는 데이터도 여전히 물리 메모리에 위치해야 한다.