Segmentation

segmentation

메모리 관리 기법중의 하나로, base and bound를 일반화한것이다.

base and bound가 address space를 통째로 물리적 메모리에 배치하는 방식이라면, segmentation은 address space를 논리적으로 다른 공간으로 나누는 방식이다.

 

segmentation은 virtual address space에서 사용하지 않는 빈공간을 굳이 물리적 메모리로 옮길 필요가 없다는 아이디어에서 시작한다. 즉, 가상주소공간에서 사용하지 않는 공간은 물리적 메모리에도 배치하지 않는다는 것이다.

 

따라서 듬성듬성 주소공간을 사용하는 sparse address space의 경우에는 segmentation이 유리하다.

 

16KB를 addressing하려면 14bit가 필요하다.

16KB의 address space를 addressing하려면 오른쪽 필기와 같이 14bit가 필요하다.

그리고 상위 2bit는 segment를 구분하는데에 사용되고(00,01,10,11), 뒤의 12bit는 각 segment의 시작부터 얼마나 떨어졌는지(offset)를 표현한다.

2^12 = 2^2 * 2^10 = 4KB이므로, 여기서 각 segment가 가질 수 있는 최대크기는 4KB가 된다.

 

이것은 위에서 설명한 세그먼트들이 물리적 메모리에 배치된 예시인데, 세그먼트들의 배치는 아래 표와 같다. (이 예시의 경우 세그먼트중 10은 사용되지 않음) 각 세그먼트별로 아래 표의 base와 bound를 적용한것이다.

segment table. 이 부분이 context switching할때 잘 관리가 되어야 한다.

segment table의 segment속성은 꼭 사용되지 않더라도 entry를 가져야 한다. 그래야 00,01,10,11 모든 인덱스의 정보를 정확하게 읽어올 수 있다. (segment index를 통한 direct indexing이 가능해짐.)

code는 32k부터 시작해서 2k, heap은 34k부터 시작해서 3k를 차지하고,

stack은 heap과 반대방향으로 증가하므로 이 시스템에서는 주소가 감소하는 방향으로 증가하고 있다. 따라서 stack은 base(bottom) 28k부터 시작해서 2k를 차지하게 된다.

그래서 예를 들어 프로그램 코드상 100이라는 주소를 물리적 주소로 변환하면 100+32KB = 32868이 되는것이다.

 

 

주소를 통해 어떤 세그먼트에 속하는지, 그리고 물리적주소 알아내기

segmentation을 통해 주소변환을 할 때, 해당 주소가 어떤 segment인지를 알아내야 그 segment가 배치되는 물리적인 메모리의 주소와 그 크기를 알아낼 수 있다.

우리가 살펴보는 주소공간은 16KB이므로 14bit를 쓰는데, 상위 2bit는 세그먼트를 판별하는데에 사용하고 나머지 12bit는 offset에 사용한다. offset이란 segment 시작부터의 거리이므로 여기서는 2^12 = 2^2 * 2^10 = 4KB가 segment의 크기가 된다.

 

또한 mmu는 다음과 같은 방식으로 작동한다.

Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT

이 부분을 통해 얻어진 segment값은 segment table의 인덱스로 사용되고,

이걸 인덱스로 매칭시켜 얻어낸 bound값을 통해 offset이 bound보다 작은지를 판별한다.

if (Offset >= Bounds[Segment])
	RaiseException(PROTECTION_FAULT) //trap에 걸린다. (segment fault)

그리고 문제가 없다면 segment에 매칭되는 base값에 offset을 더해 물리적 메모리 주소를 구한다.

else
	PhysAddr = Base[Segment] + Offset
	Register = AccessMemory(PhysAddr) //물리적주소를 메모리에서 읽어 레지스터로 가져옴.

 

 

stack은 heap과 반대 방향이다!!

위에서 살펴본 그림들과 이 표의 Grows Positive를 보면 code와 heap은 순방향, stack은 역방향으로 증가하고 있다는 것을 알 수 있다.

그리고 이 방향이 순방향인지 역방향인지에 따라 segment별 offset의 계산 방식이 다르다.

주소공간이 0부터 시작하니까 사실상 주소공간에 들어오는 유효한 주소는 16KB-1까지이다. (16KB는 한칸 넘어감)

그래서 순방향으로 증가하는 code와 heap공간의 경우에는 시작하는 주소가 0KB, 4KB 정확히 그 부분부터 시작하지만,

역방향으로 증가하는 stack의 경우에는 16KB-1부터 시작하게 된다.

code = 0KB ~ 2KB-1
heap = 4KB ~ 7KB-1
stack = 16KB-1 ~ 14KB

가상주소를 물리적 메모리 주소로 변환하는 과정을 몇가지 예시를 통해 살펴보자.

 

1. virtual address가 100이다.

offset이 100이고 bound인 2k안에 들어오므로 valid하다.

따라서 32k에서 100떨어진 곳은 100+32k = 32868

 

2. virtual address가 4200이다.

4200이면 4K를 넘어가므로 heap공간이고, 4k에서 거리가 104 < 3K이므로 valid하다.

따라서 34k에서 104떨어진 곳은 104+34k = 34920

 

3. virtual address가 7K이다.

heap은 4KB ~ 7KB-1이므로 7K는 heap의 범위를 벗어난 것이다.

따라서 segment fault이다.

 

4.virtual address가 15K이다.

stack은 역방향이므로 자신이 가질수 있는 4k 중에서 물리적으로 아랫부분에 배치가 된다.

그리고 15k를 이진수로 나타내보면 11 1100 0000 0000으로 segment는 3, offset은 3k인 것을 알 수 있는데,

이 offset은 실질적인 stack의 시작으로부터 크기를 나타내는것이 아니라 물리적인 시작지점부터의 offset이 3k라는 뜻이다.

따라서 stack 시작부터의 역방향 offset은 방금 구한 offset(3k) - segment의 물리적 최대 크기(4k) = -1k가 된다.

그리고 -1k의 절댓값은 2k보다 작으므로 유효하다고 볼 수 있다.

또 stack의 실질적 offset이 -1이라면 물리적주소는 28kb에서 -1을 더한 27kb가 된다.

 

공유할 수 있는 자원은 공유한다.

같은 프로그램 코드가 두번 실행되어 프로세스가 두개 생성될 경우, 물리적 메모리공간의 코드를 공유할 수 있다. 이를 위해 segment table에 세그먼트의 protection속성을 포함해야 한다.

code segment는 read+execution은 되지만 write는 할 수 없고, heap이나 stack은 read+write는 되지만 execution이 안된다.

 

 

Find-grained, Coarse-grained segmentation

각 세그먼트의 크기가 세밀한지(find grained), 큰 크기로 되어있는지(coarse grained)로 segmentation을 나눌 수 있다.

지금 살펴보는 것처럼 code, stack, heap등으로 영역이 크게크게 나누어져있는 세그먼트는 coarse grained segmentation이라고 하고, 이 경우 세그먼트 자체가 많지 않기 때문에 위에서 살펴본 segment table의 내용이 얼마없어도 된다.

그런데 find grained 방식을 이용하여 각 세그먼트를 더 작게 나눌 수도 있다. 그럴 경우에는 segment table이 커지게 된다. (하드웨어의 부담이 올라감.)

 

 

조각화 현상(external fragmentation)과 compact

 

segment가 할당되어 사용하고 반납하고를 반복하다보면 중간에 사용하지 않는 공간들이 끼어서 생기게된다. 그러면 kernel이 사용하지 않는 이 공간들을 linked list형태인 free list로 관리해야하는데, 이 상황에서 잔여 공간들이 너무 작아서 쓸만한 공간이 없는 조각화 현상(단편화, external fragmentation)이 생길 수 있다.

그럴 경우, free인 메모리 공간들을 모아주는 compact를 통해 해결할 수 있다.

 

 

os가 지원해야 하는 것

1. Context switch : 문맥교환이 일어날 때 주소변환정보를 잘 저장하고 복원해야 한다.

 

2. OS interaction when segments grow : segment가 커지거나 줄어들 때 정해진 세그먼트 범위를 벗어나면 os가 에러를 내든지, sbrk()으로 공간을 늘려주든지 해서 관리해주어야 한다.

 

3. managing free space in physical memory : free list로 free공간을 관리하다가 external fragmentation이 발생하면 모든걸 중단하고compaction을 통해 한쪽으로 몰아 해결한다.