Segmentation (세그멘테이션)

불연속적으로 할당하면 중간에 프리 스페이스를 아낄 수 있음

그 중 하나가 세그멘테이션 (요즘엔 세그멘테이션보단 페이징이 대부분)

각 세그먼트를 물리 메모리에 따로따로 저장

 

프로그램을 여러개의 세그먼트로 나누고

세그먼트 마다 각각의 base/bound per segment를 지원

각 세그먼트의 사이즈는 가변

 

주소 변환

Segment	Base	Size
Code(00)	32KB	2KB
Heap(01)	34KB	3KB
Stack(11)	28KB	2KB

virtual address 100 -> 32KB + 100

virtual address 4200 -> 34KB + 104  (4200 - 4096)

virtual address 8000 -> Segmantation fault

 

virtual address: segment number + offset

세그먼트 번호로 베이스를 찾고 오프셋을 더하면 물리 주소를 찾을 수 있음

 

버추얼 어드레스 스페이스 사이즈: 16KB = 2^14 -> 14 bit 필요

세그먼트 수 3개: 2비트 필요

오프셋 수 -> 12 비트 => 세그먼트 최대 사이즈 4KB

 

Segment: 00 => code

Segment: 01 => heap

Segment: 11 => stack

 

virtual address 4200 = 4096 + 64 + 32 + 8 = 4200

=> 01000001101000

01 : 세그먼트 넘버

00001101000 : 오프셋

 

4200 -> 01(Heap) + 104 => 34K + 104

 

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
Offset = VirtualAddress & OFFSET_MASK

if ( Offset >= Bounds[Segment] ) {
    RaiseException( PROTECTION_FAULT )
}
else {
    PhysAddr Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)
}

SEG_MASK : 0x3000 (11 0000  0000 0000) -> 상위 두 개만 뜯어오면 됨

SEG_SHIFT : 12

OFFSET_MASK : 0xFFF (1111 1111 1111) 

 

Segment	Base	Size (max 4K)	Grows Positive
Code(00)	32KB	2KB	1
Heap(01)	34KB	3KB	1
Stack(11)	28KB	2KB	0

주의할 것은 스택 주소 변환

최대 스택 사이즈로 빼줌

베이스 + (오프셋 - 최대)

 

버추얼 어드레스: 15KB -> 11 1100 0000 0000

Segment number : 11 -> stack

Offset : 1100 0000 0000 -> 3KB

Physical address: 28KB + (3KB - 4KB) => 27KB

 

다른 예시: 16830 (16KB - 4B) = 11 1111 1111 1100

Segment number : 11 -> stack

Offset : 1111 1111 1100 -> 4902

Physical address: 28KB + (4902B - 4096KB) => 28KB - 4B

 

 

세그멘테이션의 장점

페이징보다 개발자 입장에서 이해하기가 쉬움

접근 권한을 따로 줄 수 있음

공유하기 쉬움 (ex. 에디터를 2개 연다고 할 때, 데이터는 따로 코드는 같은 곳을 가리킬 수 있음)

 

세그먼트 사이즈

Coarse-grained

- 큰 크기로 적은 세그먼트

Fine-grained

- 작은 크기로 많은 세그먼트

 

For segmentation support

- 컨텍스트 스위칭: 세그먼트 관련 레지스터를 저장 / 회복

- 프리 스페이스 매니지먼트

- Allocation (베스트 핏, 워스트 핏, 퍼스트 핏, 버디 알고리즘)

 

장점: 연속적 할당보다 공간을 아낄 수 있음

단점:

가변 크기라 프리스페이스 다루기가 복잡함(외부 단편화) -> 고정 크기로 바꾸는 시도가 페이징

가변 크기라 하드웨어 구현하기 힘듦

---

Free-space management

공간이 모자람 -> 기존에 있던 프로세스 중 하나를 내림

내리는 것 중 run 상태는 안되고, ready나 wait 상태를 내림

어디로 내려주냐 -> 디스크의 스왑 공간 .. 메모리의 두배 크기 정도

다시 올라올 때는 "재배치"되는 걸 관찰 가능

 

기본적으로 더블리 링크드 리스트로 프리 스페이스를 관리

- Splitting and Coalescing

head - [addr : 0 , len : 10] - [addr : 20 , len : 10] - NULL

 

Request

10바이트 요청 => 위 엔트리 중 하나를 뽑아서 줌

10바이트보다 큼 => fail or need compaction

10바이트보다 작음 => need spliting

head - [addr : 0 , len : 10] - [addr : 21 , len : 9] - NULL

 

Free

10~19에 해당하는 주소가 프리되었다

head - [addr : 0 , len : 10] - [addr : 10 , len : 10] - [addr : 20 , len : 10] - NULL

=> Coalescing

head - [addr : 0 , len : 30] - NULL

 

Free-space allocation policy

- Best-fit: 가장 딱 맞는 곳에 할당

- Worst-fit: 가장 과하게 남는 공간에 할당

- First-fit: 그냥 첫번째로 넣을 수 있는 공간에 할당

- Next-fit: 마지막으로 할당된 위치 다음으로 들어갈 수 있는 곳에 할당

 

퍼스트 핏의 단점은 초반에 단편화가 많이 남는다는 점

---

프리 스페이스 관리를 위한 다른 방법

Buddy allocation

트리로 관리

- 2의 정수승으로 계속 나누어서 가장 적당한 크기에 할당

예) 100K 요청 - 전체 크기를 계속 2씩 나누다 128K 할당해줌

 

버디가 프리하면 Coalescing해서 합쳐줌

 

Segregated Lists

솔라리스의 slab 같은 거

같은 크기의 프리 공간을 Coalescing하지 않고 모아둠

PCB같은 경우 할당과 반납이 계속 될 수 있는데 이때마다 스플릿, 코얼리싱하는 건 비효율