💿

08 : Segmentation

course

last review

2023/04/13

mastery

rookie

progress

pending

date

4 more properties

Previous chapter

07 : Address Spaces

Main Quest : How to support Large Address space

Segmentation : Normalize Base/Bounds

Fine-grained vs. Coarse-grained

OS Support

Example

베이스 & 바운드 방식은 프로세스를 물리 메모리의 다른 부분으로 쉽게 재배치할 수 있다.

그런데 효율성 측면에서 보면 다음과 같은 함정에 빠지게 된다.

프로세스는 다음과 같이 구성되어 있는데 힙과 스택 사이의 거대한 free메모리의 골짜기가 형성되어있다.

이 공간이 사용되지 않더라도 이 Address Space는 물리 메모리에 재배치할 때 같이 할당된다.

이런 점에서 베이스&바운드 방식은 메모리 낭비가 심하다.

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

즉, 베이스 바운드는 유연성이 없다.

Main Quest : How to support Large Address space

스택과 힙 사이에 빈 영역이 크게 존재하는 공간을 어떻게 지원할까? 크기가 큰 주소공간의 경우 실제 수 메가바이트만 사용함에도 불구하고 공간 전체가 메모리에 탑재되어야 한다.

Segmentation : Normalize Base/Bounds

핵심 : 프로세스별 B&B를 세그먼트 단위로 쪼개자!

아이디어는 간단하다.

MMU에 하나의 베이스와 바운드값이 존재하는 것이 아닌, 세그먼트별 베이스와 바운드값을 할당한다.

우리가 구성한 세그먼트는 다음과 같았다.

•

코드

•

힙

•

스택

즉, 베이스와 바운드 레지스터 3쌍이 필요하다.

64KB의 물리 메모리에 3개의 세그멘트와 운영체제용으로 예약된 16KB 영역이 존재한다.

사용중인 메모리에 대해서만 물리 공간을 할당하여, 사용되지 않은 영역이 많은 대형 주소공간을 수용할 수 있는 구조이다.

•

코드 세그먼트는 물리주소 32KB에 2KB짜리로 배치되고, 힙 세그먼트는 34KB에 3KB짜리로 배치된다.

세그먼트의 사이즈는 바운드 레지스터와 일치한다. 이 세그먼트에 몇 바이트가 유효한지 하드웨어에게 알려준다.

Examples

가상 주소 100번지의 물리주소

•

100번지는 프로그램 코드의 영역이다. 코드의 베이스 레지스터는 32KB이므로, 물리주소는 32KB + 100 = 32868이 된다.

◦

그 후, 주소가 범위 내에 있는지 검사하고, 범위 내에 있을 경우 물리 메모리 32868을 Read.

가상수조 4200번지의 물리주소.

•

4200은 힙이다. 코드의 베이스 레지스터는 34KB이다. 그런데 VM 내부의 힙의 주소는 4200번이 맞으나, 세그먼트의 관점으로 바라봐야한다. 우리가 진짜 입력해야하는 주소는 VM주소 - VM의 힙의 베이스 = 4200 - 4KB = 104이다.

•

즉, 34KB+104 = 34920이 된다.

Types of Segments

하드웨어는 변환을 위해 세그먼트 레지스터를 사용한다.

그렇다면 가상 주소가 어느 세그먼트를 참조하는가? 그 세그먼트 안에서 오프셋은 얼마인가?

여기에서 소개하는 방법은 최상위 비트 몇개를 세그먼트 종류를 나타내는데 사용했다.

최상위 비트가 00이면 코드, 01이면 힙, 02면 스택이 될 것이며

나머지 0~11비트까지는 그 세그먼트 안의 오프셋이 된다.

힙을 구할때처럼 VM - Segment bound를 할 필요가 없어지는 이야기다.

이는 바운드 검사에도 용이해 바운드에서 Offset을 빼기만 하면 되도록 바뀐다.

Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT //14 bit VA중 상위 2bit 추출
Offset = VirtualAddress & OFFSET_MASK //오프셋 추출
if(Offset >= Bounds[Segment])
		RaiseException(PROTECTION_FAULT)
else
		PhysAddr = Base[Segment] + Offset
		Register = AccessMemory(PhysAddr)
Assembly
복사

여기에는 몇가지 문제가 있다.

11에 해당하는 블록은 사용하지 못한다.

따라서 어떤 프로세스는 힙과 스택을 합쳐 1비트로 나타내기도 한다.

세그먼트의 크기는 여전히 정적이다.

세그먼트의 최대 오프셋은 12bit이므로, 이 이상 힙이나 스택을 할당할 수 없게 된다.

Stack

스택은 다른 세그먼트와는 결정적인 차이점을 가지고 있는데 바로 역방향이라는 점이다.

물리메모리 28KB에서 시작해서, 26KB까지 확장된다. 이를 위해서는 다른 방식의 변환이 필요하다.

간단한 하드웨어가 추가로 필요하다.

세그먼트가 어느 방향으로 확장하는지 일종의 Sign비트를 추가한다.

하드웨어는 세그먼트가 반대 방향으로 늘어날 수 있다는 걸 알고 있으므로 그런 가상 주소에 대해서는 다른 방식으로 변환한다.

Examples

가상주소 15KB에 접근할 때, 물리주소 27KB에 매핑되어야 한다. 이 주소를 바이너리 비트로 바꾸면

11 1100 0000 0000 (0x3C00)이 된다.

상위 2비트는 세그먼트 지정 비트이므로, 3KB의 오프셋이 된다.

이 세그먼트가 스택일 경우, 하드웨어는 이 오프셋에서 세그먼트의 최대 크기를 뺀다.

3KB-4KB = -1KB이므로, 이 음수 오프셋을 베이스에 더해 최종 오프셋을 얻는다.

Support for Sharing

세그멘테이션 기법을 응용하면 새로운 종류의 효율성을 얻을 수 있다!

특정 메모리 세그먼트를 공유(특히 코드)함으로써 메모리를 절약할 수 있다.

공유를 지원하기 위해 각 세그먼트별로 다른 세그먼트가 자신의 세그먼트에 어떤 일을 할 수 있는지 Protection bit를 추가함으로써 엑세스 권한을 도입할 수 있다.

Fine-grained vs. Coarse-grained

OS Support

•

세그멘테이션의 안정적인 도입을 위해서는 운영체제가 몇가지 문제를 도와야 한다.

Context Switch

컨텍스트 스위치가 일어날 시 운영체제는 어떤일을 해야할까?

OS는 이때까지 사용했던 세그먼트 레지스터를 메모리에 저장하고, 다음 프로세스의 세그먼트 레지스터를 불러와야한다.

두번째는 세그먼트 크기의 변경이다.

어떤 프로그램이 malloc을 호출해 객체를 할당할 경우, 기존의 힙에서 해당 요청을 처리할 수 있을 것이다.

빈 공간을 찾거나, 빈공간이 없다면 힙의 세그먼트 크기를 늘려야 할 것이다.

마지막으로, 미사용중인 물리 메모리 공간의 관리다.

새로운 주소 공간이 생성되면 운영체제는 이 공간의 세그먼트를 위한 비어있는 물리 메모리 영역을 찾아야 한다.

일반적으로 생기는 문제는 세그먼트의 크기가 제각각이다보니, 빈 슬롯에 적당한 세그먼트를 채워넣다 보면 사용할 수 없는 자투리 공간이 생기게 된다. 이를 외부 단편화(external fragmentation)이라 한다.

Example

위와 같이 메모리가 할당되어있을 경우, 새 프로세스 (20KB)를 할당하려고 할 때, 24KB가 이론적으로 비어있으나, 모두 잘게 나뉘어 있어 해당 요청을 충족시키기 어렵다.

이 문제의 해결책은 기존 세그먼트를 압축해서 정리한 후, 새로운 세그먼트를 채우는 방식이 될 것이다.

일반적으로 이들의 데이터를 하나의 연속된 공간에 복사하는 방식인데, 세그먼트의 복사는 메모리 부하와 시간복잡도가 매우 큰 연산이라 코스트가 상당하다.

한가지 대응방법으로는 빈 공간 리스트를 관리하는 알고리즘을 쓰는 것이다.

Next chapter

09 : Paging