Chapter#14 Segmentation

Chapter#14 Segmentation

- Address Translation Techniques

 - Segmentation ( #14 )

 - Paging ( #15~16 )

- Free-space Management

---

Segmentation

Idea : code, stack, heap 각각 base-bound register을 두자

 

앞의 일부 bit는 Segment를 표시하고 해당 Base + 뒤의 Offset으로 physical address를 찾음

physical address = offset + base

Segment Register Value

Code같은 경우 바뀌는 값이 아니므로 같은 프로그램 프로세스가 Share가능함 ( Protection : fork 등 )

 

 

OS Support : Fragmentation

External fragmnetation : free space가 non-contiguous하게 배열된 경우, OS의 메모리 할당이 어려움

Compaction : free space를 위해 Rearranging함 -> Costly(Stop process > Copy data > Change segment register)

---

Free-space Management

External Fragmentation은 불가피하게 일어난다

- OS가 segmentation으로 physical memory 관리할 때

- User-level heap-allocation library ( malloc(), free() )

 

Strategies minimizing fragmentation :

Splitting : free chunk를 찾아서 해당 requst에 맞으면 used 및 free로 분할

Coalescing : used를 free 시켰을 때 연속된 메모리 주소의 free chunk들이 있으면 다 합쳐서 큰 free chunk로 만듦

 

Allocated Region은 Header block을 가져 명시된 길이보다 더 많은 메모리 공간을 차지한다

Header는 size(chunk 길이)와 magic(error handle용 값)을 가진다

 

Embedding A Free List

- linked list 만들고 초기화

- kernel 함수인 mmap()으로 heap 생성

- 가장 큰 Free Chunk를 linked list에 할당

- malloc()나 free() 발생 시 manage

- 필요하다면 sbrk() 등을 통해 heap size 증가

 

typedef struct node_t {
  int size;
  struct node_t *next;
} nodet_t;

//mmap () returns a pointer to a chunk of free space
node_t *head = mmap(NULL, 4096, PROT_READ|PROT_WRITE, MAP_ANON|MAP_PRIVATE, 1, 0);
head->size = 4096 - sizeof(node_t); // 할당된 크기에서 header크기 제외 | sizeof node_t is 8
head->next = NULL;

Allocation

 

4k(4096) free chunk 하나를 만듦(8byte header를 가지므로 size는 4088 = 4096-8)

malloc(100)실행 : free chunk의 size는 108(= 100(length)+8(header)) 감소

 

Free

Free되는 경우 head 바로 다음에 새 Chunk가 연결됨.

Addr값은 Header의 pointer값, len은 size값, Header의 next값은 기존 head->next값의 offset(=addr)

위의 경우 Coalescing하면 됨

 

Managing Free Space : Basic Startegies

Best Fit:

- request보다 같거나 큰 free chunks 찾음

- 가능한 chunk중 가장 작은 것 할당

- full search가 필요

Worst Fit:

- largest free chunk를 할당

- 나머지 chunk는 free list에 keep

- full search 여전히 필요

 

First Fit:

- 가장 처음 나온 request보다 같거나 큰 free chunks 할당

- full search까지는 필요 없음

Next Fit:

- 가장 처음 나온 request보다 같거나 큰 free chunks 할당

- 그 다음 탐색 시 이전에 찾은데부터 이어서 탐색

- full search까지는 필요 없음

 

---

학교 강의를 토대로 개인 공부 목적으로 작성되어 오타가 및 오류가 있을 수 있으며, 문제가 될 시 삭제될 수 있습니다.