[sp] Dynamic Memory Allocation (2)

1. Knowing How much to free

(1) Standard Method

 - 블락 앞에 word 크기의 블럭의 길이를 작성: the header field, header

 - 모든 할당된 블럭에 대해 추가적인 word가 필요함

 

 

payload 앞에 블럭의 전체 사이즈를 적는 추가적인 블럭이 하나 더 필요함

 

 

2. Keeping track of free blocks

(1) 길이를 사용하는 implicit list : 모든 블럭을 연결, 모든 블럭을 traverse해야하기 때문에 free block만 traverse 할 수 없음

(2) 포인터를 사용한 free block 사이의 explicit list : 공간 효율이 떨어짐, 다음 free block의 위치를 가리킴

(3) Segregated free list : free block을 분리하고 기준에 맞게 class 별로 묶음

 

(4) 사이즈로 분류된 블럭

 - 각 free block 내부에 포인터가 있는 balanced tree (ex. Red-black tree)를 사용하고, key로 길이를 사용

 

 

 

 

3. Implicit List

(1) 각 블럭에 대해 사이즈와 allocatio status 필요

 ; 이 정보를 2개의 word 블럭에 저장할 경우 낭비

(2)  Standard tric

 - 만약 블럭이 할당됐으면, 몇몇 lsb는 항상 0

 - 0 비트를 저장하는 것 대신, 0 비트를 allocated/free flag로 사용

 

- size를 담은 word를 읽을 때, 이 비트를 mask out 해야함

 

(3) Detailed implicit free list example

 

 

할당된 블럭 : 칠해짐

free block : 칠해지지 않음

headers : 할당된 블럭의 전체 크기 / 할당된 비트(LSB)

 

(4) Finding a free block

- First fit : 항상 처음부터 서치하고, 알맞은 free block의 first를 선택

p = start; 
while ((p < end) && \\ not passed end
	((*p & 1) || \\ already allocated
	(*p <= len))) \\ too small 
p = p + (*p & -2); \\ goto next block (word addressed)
// -2 : 다음 free point로 가려면 lsb가 0이 돼야함

p가 end보다 작고 할당된 블럭이면 next block으로 이동

 

총 블럭 (allocated and free) 수의 선형 시간이 소요될 수 있음

실제로 list의 시작 부분에서 splinters(조각)가 발생할 수 있음

 

- Next fit : 찾은 부분 다음부터 서치

first fit과 같지만, 이전 탐색이 끝난 부분에서 서치를 시작

first fit보다 더 빠름 : 도움이 되지 않은 블럭을 탐색하는 것을 피할 수 있음

 

- Best fit

리스트를 탐색하고 최적의 free block을 고름 : 가장 적은 바이트가 남아 있음

fragment가 작게 유지 -> 메모리 이용이 향상

first fit보다 느림

 

 

(5) Allocating in free block

- splitting

할당된 영역이 free한 영역보다 작을 수 있기 때문에, 블럭을 쪼개야 함

void addblock(ptr p, int len) {
    int newsize = ((len + 1) >> 1) << 1; // round up to even (doubled word로 할당)
    //lsb = 0이 됨
    
    int oldsize = *p & -2; // mask out low bit
    *p = newsize | 1; // set new length
    if (newsize < oldsize)
    	*(p+newsize) = oldsize - newsize; // set length in remaining
}

 

(6) Freeing a block

- allocated flag를 지워줌

void free_block(ptr p) {
	*p = *p & -2;
}

 

잘못된 fragmentation을 일으킬 수 있음

 

계속 안의 내용이 남아 있게 됨

 

충분한 free 영역이 있지만 allocator가 찾을 수 없음

 

 

(6) Coalescing

이전/다음 블럭 중에서 free한 블럭이 있으면 합침

 

void free_block(ptr p) {
    *p = *p & -2; // clear allocated flag
    next = p + *p; // find next block
    if ((*next & 1) == 0)
   	 *p = *p + *next; // add to this block if
}