segmentation

1. Discuss pros and cons of segmentation.

 

2.Search and understand classic algorithms to resolve external fragmentation, i.e., best-fit, worst-fit, and first-fit.

 

3.Try to write a heap (not a data structure but a set of free list) implementation in C. The full implementation needs not to be submitted, but you can suggest a C struct definition.

 

4.

Discuss pros and cons of buddy allocation.

 

 

7-2
segmentation

스택과 힙 사이에 큰 공간을 다른 프로그램들이 사용할 수 없었다. 이를 해결하기 위해 segmentation.

segmentation이란?
segment단위 별로 base(시작부분)와 bound(끝 경계)를 두자. segment = 연속적인 부분.(ex stack,heap)
불필요한 낭비를 막기 위해서.

segmentation fault
메모리 접근을 사용할 때 허용되지 않은 메모리에 접근할 때 발생.

명시적인 방법으로 접근하자면, 접근하려는 주소의 앞부분을 세그먼트를 나타내는 용도로 사용한다.

segment를

Code : 00

Heap : 01

Stack : 11

로 가정하자.

 

base가 34k(34816)이고 offset이 0x68(104)이므로 주소는 34920이다.

가상 주소의 값은 사진에 나온 그대로 4200(=2^12+104)이다.

 

 

가상주소 : 0x3C00 -> 0011 1100 0000 0000 -> seg : 11(2) = 3, offset : 0xC00

물리주소 : 28K+(-1)*0xC00 = 25K, -1을 곱하는 이유는 스택이 거꾸로 자라기 때문에.

 

Code Sharing

메모리 절약을 위해 메모리 segment를 공유하는 방법. 하드웨어의 도움(protection bits)이 필요함. 

read-only로 설정해두어 여러개의 프로세스가 쉐어를 해도 독립적임에는 문제 없음.

프로세스 몰래 메모리를 쉐어링 해 독립을 유지.

 

Fine-grained segmentation : 세그먼트의 크기를 제한하지 않음.

coarse-grained segmentation : 대충 대충 넓게 세그먼트를 잡음.

 

메모리 관리에 있어서 운영체제의 지원

 

1.

운영체제는 문맥교환이 복잡해짐. 세그먼트 별 레지스터를 불러왔다가 저장하는 걸 지원해야함.

세그먼트가 더 필요해지면 운영체제가 남은 공간을 더 할당해 줄 수 있음. 없으면 거절도 가능.

 

2.

빈 공간이 관리하기.

새로운 공간이 생기면 피지컬 메모리에 매핑되어야 함.  

external fragmentation : 필요에 맞춰 공간을 할당 했는데 중간중간 비어있는 부분이 있을 수 있음.

compacts를 사용해서 띄어진 빈 공간을 하나로 합쳐 사용할 수 있음. 메모리,시간 적으로 부담이 됨.

 

3.빈공간을 잘 배치하여 2번 방법을 사용하지 않고 해결하기.

best fit, worst fit, first fit이 있음.

best fit : 요청을 받은 세그먼트에 맞춰 끼워넣음.

worst fit : 가장 큰 공간을 먼저 할당.

first fit : 제일 처음 발견된 공간을 바로 배치. 빠른 응답에 좋음.

 

buddy algorithm

메모리를 최대한 요구에 맞춰(best fit) 나누어준다. 

내부 단편화 문제가 남아있다. 

 

피할 방법은 없지만 줄인 수는 있다.

 

variable-sized segmentation

sparse address spaces