. 9.9.4 단편화 / 9.9.5 구현 이슈 / 9.9.6 묵시적 가용 리스트
본문 바로가기
프로그래밍 공부/CSPP

9.9.4 단편화 / 9.9.5 구현 이슈 / 9.9.6 묵시적 가용 리스트

by 불냥이_ 2021. 1. 15.

단편화(Fragmentation)는 할당 요청을 수행할 수 없는 조건일 때 일어난다.

단편화는 내부 단편화와 외부 단편화로 나뉜다.

 

  • 내부 단편화

 내부 단편화는 할당된 블록이 데이터 자체보다 더 클 때 일어난다.

예를 들어 아래의 그림을 보자

그림 1. 내부 단편화의 예시

그림 1은 64bit에서의 할당 예시이다. 그림의 한칸은 4바이트를 의미한다.

정수는 4바이트이기 때문에 5*sizeof(int)는 5칸을 차지하지만, 64비트에서는 8바이트씩 (2칸씩)만 배치할 수 있기때문에 2의 배수로 할당해서 6칸을 차지하게된다. 즉, 4바이트가 낭비되고 있는 것이다. (왜 이런지에 대해서는 이전 게시글 (9.9.1 malloc과 free함수 (tistory.com)) 에서 논의한적이 있다.) 

 

이렇게 할당된 블록이 실제로 요구하는 데이터의 크기보다 클 때는 내부 단편화라고 한다.

 

 

  • 외부 단편화

 외부 단편화는 메모리에는 충분한 용량의 메모리의 여유가 있지만, 정렬 문제때문에 그 메모리에 할당하지 못하는 경우이다. 어떤 것인지는 아래의 그림을 보자.

 

그림 2. 외부 단편화의 예시

현재 여유메모리는 6칸(흰색 칸 수;24바이트) 이나, 4칸 2칸으로 나누어져 있기 때문에 24바이트의 블록을 할당할 수 없다.

 

 이전글의 할당기의 요구사항 중에 '할당된 블록을 수정하지 않기' 를 보면, '일단 블록이 할다되면 이들을 수정하거나 이동하지 않는다.' 라는 조건이 있었다. 즉, 한번 할당된 블록에 대해서는 정렬을 할 수 없기 때문에 대응하기도 상당히 힘들다.

 

 외부 단편화가 측정하기도 어렵고, 예측은 불가능하기 때문에 할당기들은 대개 많은 수의 더 작은 가용 블록들보다는 적은 수의 큰 블록들을 유지하려는 방법을 채택하고 있다. 

 

 이 말인 즉슨, 8칸을 배정할 때, 4개로 쪼개서 2칸씩 여기저기에 배치하는 것 보다는 8칸짜리로 한 곳에 배치하는 것을 선호한다는 것이다. 

 

 

- 구현 이슈

그림 3. 간단한 할당기의 예제

 그림3을 보자. p1, p2, p3는 각각 할당된 공간을 가리키는 포인터이다. p1, p2, p3는 할당된 공간의 처음을 가리킨다. 그리고 p4는 p3가 사용하는 오른쪽 공간에 온다고 생각해보자. 여기서 free(p2)를 했는데, 사실 free함수는 아무것도 하지 않는다고 하자. 그러면 2칸을 배정받아도 p2의 공간이 아닌 p3 다음에 올 것이다. 

 

 이 경우에는 연산이 매우 간단하기 때문에 (심지어 free는 아무것도 하지 않는다.) 속도는 매우 빠를 것이나 금방 메모리가 가득찰 것이다.

 

 반대로, free가 해당 공간을 비우고, 다음 배정을 할 때, 메모리의 상황에서 모든 경우의 수를 고려해서 새로운 공간을 배정한다고 하자. 그 경우에는 메모리의 공간은 극도로 효율적일 것이다. (최고이용도라고 쓰기도 한다.) 그러나 속도는 매우 느릴 것이다. 

 

 이 때문에, 할당기는 속도와 공간의 효율사이에서 좋은 균형을 추구해야한다. 그래서 할당기는 다음과 같은 이슈를 고려해야한다.

 

1. 가용블록 구성 : 어떻게 메모리의 비어있는 공간이 어디에, 얼마만큼 있는지 알 것인가?

2. 배치 : 어떻게 블록을 배치해야 효율적으로 공간을 사용할 수 있을 것인가?

3. 분할 : 새로운 블록을 배치한 후, 남은 부분들로 무엇을 할 것인가?

4. 연결 : 방금 반환된 블록으로 무엇을 할 것인가?

 

 

- 묵시적 가용 리스트 (Implicit Free Lists)

 실전에서 쓰이는 할당기는 블록 경계를 구분하고, 할당된 블록과 가용 블록을 구분하기 위해 데이터 구조를 필요로 한다. 그리고 이 데이터 구조는 블록 내에 저장된다. 단순한 접근법은 아래와 같다.

그림 4. 간단한 묵시적 가용 리스트의 구조 

 그림 4에서 실제로 할당된 하늘색과 짙은 하늘색으로 칠해진 부분은 실제로 할당받은 메모리며, 흰색은 비어있는 메모리이다. 하늘색 영역과 흰색 영역들의 앞 칸에는 x/y로 표시되어 있는데, y는 이 영역이 할당되어있으면 1, 아니면 0을 나타내고, x는 해당 영역의 크기(바이트)를 나타낸다.

 

 즉, 8/0은 여기는 할당되있지 않는 8바이트의 영역이라는 뜻이므로, 8바이트의 영역을 할당할 수 있는 것이다.

 

 하지만, 실제로는 이 정보(정수1개)를 저장해야하므로 가용 공간은 한칸=4바이트만 남는다. 그래서 위에서 말한 ' 많은 수의 더 작은 가용 블록들보다는 적은 수의 큰 블록들을 유지하려는 방법을 채택하려고 한다.' 도 이 때문이다. 할당된 크기가 어떻든 간에 최소 4바이트의 공간은 그 블록의 정보를 표시하는 데 필요하기 때문이다. (일종의 고정비문제?)

 

 

 이 정보를 저장하는 처음 칸을 헤더header라고 한다. 이 header 다음에 저장하려고 한 데이터가 저장되어 있으며, 데이터 뒤에 남는 공간에는 패딩이 따라올 수 있다.

 또한, 힙 공간의 마지막 블록 (그림4의 0/1)은 힙 공간이 종료한다는 표시를 해주어야한다. 

 

 

 묵시적 가용 리스트의 구조는 아래와 같다.

그림 5. 묵시적 가용리스트의 구조

 

 우선 처음 3비트 (그림 5의 오른쪽 상단) 을 보자. a는 0과 1로 표시하는데, 0은 현재 공간이 할당되지 않아있다./1은 현재 공간이 할당되어있다 로 표시하고, 최소 공간 ( 그림 4에서 한 칸 ) 은 4바이트=8비트이기 때문에 4번째칸 (2^3)부터 1씩 올라간다. 그래서 항상 1번(2^1)과 2번자리(2^2)는 0으로 된다. 

 

 만약 24바이트를 갖는 블록이 있다고 하자.

헤더는 16진수이기 때문에 0x00000018 에 사용하고 있다는 1비트를 더해서 0x00000019로 표시될 것이다.(0x는 16진수임을 나타낸다.) 

블록 크기가 40바이트인 가용 블록의 헤더는 다음과 같다.

0x00000028 (16*2 + 8) 

 

 그리고 다음은 실제 데이터가 담기는 payload 가 온다. 그럼 패딩은 무엇이냐?

만약 8바이트의 메모리를 할당하고 싶다면 헤더 4바이트 + 데이터 8바이트 = 12 바이트의 공간이 필요하지만, 전술했듯이 메모리는 8바이트 단위 (그림 4에서 2칸)로 묶여있기 떄문에 실제로는 16바이트를 할당받게 되고, 쓰지않는 4바이트의 공간이 남아있다. 이 남아있는 4바이트의 공간을 패딩이라고 한다.

 

 

 

 

댓글