프로그래밍 언어론 3-2-3강. 메모리할당- 힙기반 할당(Heap-Based Allocation)

 

[힙 기반 할당]

: 임의의 시간에 하위 블록을 할당 및 할당 해제 할수 있는 저장 영역( = 사용자 임의 할당 가능)

: 자료구조의 동적할당, 상황에 따라 크기 달라지는 객체(문자열, 리스트, set등)들이 저장.

: 힙 공간 관리의한 수많은 전략 존재(공간과 속도가 주요 관심사)

 

 

 

[힙 공간 문제와 해결전략]

: 힙 공간에서 나타나는 문제는 크게 내부단편화와 외부단편화로 구분된다.

 

1. 내부 단편화(Internal fragmentation)

: 메모리 공간이 일정크기로 나뉘어있을때 발생한다.

: 메모리가 할당되고 남은 공간이 너무 작아 사용할 수 없는 상태

내부단편화 모습 예시

2. 외부 단편화(External fragmentation)

: 메모리 공간이 동적으로 할당(들어오는데로 그냥) 할당될때 발생한다.

: 공간에 데이터 순서대로 할당되고 일부데이터가 반환되어 빈공간 생겼지만, 새로 할당된 객체들이 들어가기에 너무 작은 상태

 

외부단편화의 모습 예시

: 사용되고 있지 않는 힙 내 블록들은 단일 연결 리스트(Free list)로 되어있다. (이후 새로 객체할당되면 이 연결리스트를 검색)

 

 

 

[저장소 관리 알고리즘(Storage-management algorithms)]

• 최초 적합(First-fit) : 주어진 객체가 들어갈수 있는 첫번째 free 블록 선택 (빠름)
• 최적 적합(Best-fit) : 주어진 객체가 들어갈 수 있는 가장 작은 free 블록 선택 (효율성)
• 만약 선택한 자유블록이 필요이상으로 크면, 이 자유블록을 둘로 나누고 안쓰는 부분을 자유 리스트로 반환
• 블록 할당 해제되고 자유 리스트로 돌아갈때, 물리적으로 양쪽 검사해 프리 블록있으면 결합한다. (malloc, free 호출시 실행)

 

 

단일 free 리스트를 가지고 있는 알고리즘은 할당에 O(n)의 비용이 할당된다.
이 비용을 줄이기 위해 몇몇 저장소 관리 알고리즘들은 자유블록들을 특정 기준크기에 따라 분리된 free list에서 관리한다.
ex. 객체크기 6은 4, 8, 12... 크기 free list중 8 free list에서 관리한다.

 

 

 

[pool]

: 특정 크기에 따라 나뉜 free list를 의미 (ex. 4,8,12... pool)

: pool 크기 할당 메커니즘으로 크게 두가지 존재.

 

 

 

[힙내 pool 크기 할당 메커니즘]

• buddy system : 메모리 2의 거듭제곱 크기 기준으로 할당 (1,2,4,8,16... pool)
• Fibonacci heap : 메모리 피보나치 수 기준으로 할당(1,2,3,5,8,11... pool) / 더 복잡하지만 보다 내부단편화 방지

 

 

힙은 시간이 지날수록 요청에 만족하는 크기 제공 능력이 떨어진다. 
이로인해 외부 단편화 발생 확률이 증가하고, 이를 방지하기 위해 free block들을 한군데로 모을 필요가 있다(다음장).