메모리 외부 단편화
메모리는 운영체제가 관리하는 컴퓨터의 중요한 자원입니다. 프로세스는 운영체제로부터 필요한 만큼의 메모리를 할당받고 실행이 끝나면 운영체제에게 반납합니다. 대다수의 운영체제는 여러 프로세스를 동시에 실행하는 멀티태스킹을 지원합니다. 프로세스들은 각자에게 필요한 메모리를 운영체제로부터 할당받고 해제하기를 반복합니다. 만약 여러 프로세스가 메모리를 차례대로 할당하게 되면 메모리의 상태는 아래와 같을 것입니다.
메모리는 여러 프로세스들을 위해 분리되어 있지도 않고 프로세스를 위해 아메바처럼 복제를 만들지도 않습니다. 메모리 주소는 연속적이고 프로세스는 각자의 메모리 시작주소로부터 원하는 크기만큼의 메모리를 할당받습니다. 위 그림의 A, B, C, D 프로세스 중 B, D 프로세스가 메모리를 해제한 상황을 가정해 보겠습니다.
이제 새로운 프로세스 E 가 64 바이트의 메모리를 요구한다고 할 때 실제 사용 가능한 메모리는 64바이트 이상이지만 메모리가 연속적으로 존재하지 않아 프로세스 E 는 메모리를 할당 받을 수 없습니다. 이와 같은 현상을 메모리 외부 단편화라고 합니다. 메모리 외부 단편화는 메모리 여유가 있음에도 다른 프로세스를 실행시키지 못하니 이를 해결할 방법이 필요합니다.
💡 참고로 메모리 내부 단편화는 프로세스가 사용 중인 메모리 중 사용하지 않는 메모리 공간을 갖는 경우입니다. 예를 들어 128바이트의 메모리를 할당받은 프로세스가 실제 사용하는 메모리는 100바이트라면 28바이트의 메모리가 낭비됩니다. 이 경우 메모리 내부 단편화에 해당합니다.
버디 블록 알고리즘
외부 단편화를 해결할 하나의 방법은 버디 블록 또는 버디 메모리 할당이라 불리는 알고리즘입니다. 버디 블록 알고리즘은 전체 메모리를 여러 계층의 블록으로 쪼개는 것부터 시작합니다.
블록의 크기가 그 윗 계층 블록 크기의 절반인 굉장히 아름다운 형태를 이루고 있습니다. 이제 프로세스가 메모리 할당을 요청하면 프로세스가 요구하는 메모리 크기보다 큰 적당한 크기의 블록을 프로세스에 할당해 줍니다. 예를 들어 30바이트의 메모리를 요구하는 프로세스에게는 32바이트의 메모리 블록을, 100바이트의 메모리를 요구하는 프로세스에게는 128바이트의 블록을 할당해줍니다. 이렇게 여러 프로세스에게 블록을 할당해 주다 보면 다음과 같은 상태가 될 것입니다.
주의할 점은 각 레벨이 모두 같은 메모리 공간을 지칭한다는 것입니다. 단지 레벨 0은 공간을 8개의 블록으로 나누었고 레벨 1은 4개의 블록으로 나누었을 뿐입니다. 만약 아래 그림과 같이 레벨 1의 1번째 블록을 할당하면 블록의 범위를 포함하는 상하위 레벨 블록들은 사용할 수 없습니다.
모든 프로세스가 블록 형태로 메모리를 가져다 쓰고 제자리에 갖다 놓기만 하면 외부 단편화를 해결할 수 있습니다. 물론 약간의(또는 클 수도 있지만) 내부 단편화를 감수해야 하지만 외부 단편화로 인한 문제에 비하면 감수할만한 수준입니다.
메모리 할당
이제 버디 블록을 구현해볼 차례입니다. 알고리즘은 크게 메모리를 할당하는 부분과 해제하는 부분으로 나뉩니다. 프로세스는 void *malloc(size_t size), void free(void *ptr) 함수를 이용해 동적 메모리를 할당, 해제합니다. malloc 은 메모리의 크기만을 매개변수로 받고 결과값으로 메모리의 주소를 반환합니다. 굉장히 제한된 정보만으로 적당한 크기의 블록과 그 주소를 알아내려 하니 조금 막막합니다. 어떻게 하면 구현할 수 있을지 다음 물음들을 살펴보겠습니다.
- 요구한 메모리 크기에 적당한 크기의 블록은 무엇일까
- 그 블록은 버디 블록 계층에서 어느 레벨에 있는 블록일까
- 그 블록은 속해 있는 레벨에서 몇 번째 블록일까
- 만약 해당 레벨에 할당 가능한 블록이 없다면 어떻게 해야 할까
첫번째 물음 "요구한 메모리 크기에 적당한 크기의 블록은 무엇일까" 의 적당한 크기란 요구한 메모리 크기보다는 크지만 내부 단편화는 최소화하는 크기를 의미합니다. 버디 블록 계층에서 가장 작은 블록의 크기를 알고 있다고 할 때 그 크기는 다음과 같이 구할 수 있습니다.
smallestBlockSize = 32
def getBlockSize(size):
blockSize = smallestBlockSize
while size > blockSize:
blockSize <<= 1
return blockSize두번째 물음 "그 블록은 버디 블록 계층에서 어느 레벨에 있는 블록일까" 는 위 코드를 조금만 변형하면 구할 수 있습니다. 최소 크기 블록의 레벨이 0임을 이용합니다.
smallestBlockSize = 32
def getBlockLevel(size):
level = 0
blockSize = smallestBlockSize
while size > blockSize:
blockSize <<= 1
level += 1
return level첫번째와 두번째 물음을 해결하면서 요구한 size 에 맞는 블록의 레벨을 구했습니다. 세번째 물음 "그 블록은 속해 있는 레벨에서 몇 번째 블록일까" 을 해결하기 위해 버디 블록 알고리즘은 각 블록의 상태를 관리할 메타 데이터를 이용합니다. 사실 여기서 관리할 상태란 블록을 사용할 수 있는지 없는지 여부만을 저장할 플래그 하나입니다. 아래 그림을 살펴보겠습니다.
각 블록마다 사용 가능 여부 true 또는 false 을 저장할 1바이트의 데이터를 할당해도 무리는 없지만 메모리를 더 아껴 쓰기 위해 각 블록의 상태를 1비트로 저장하겠습니다. 예를 들어 레벨 0 블록들의 개수는 8이므로 1바이트의 상태 관리용 비트맵을 아래와 같이 사용합니다.
만약 16개의 블록이 있다면 2바이트의 비트맵을, 100개의 블록이 있다면 100 / 8 = 12.5 를 올림한 13바이트의 비트맵을 사용합니다. 일반화하면 어떤 레벨의 블록의 개수가 n 일 때 ceil(n / 8)(소수점 첫번째 자리에서 올림) 바이트 크기의 비트맵이 상태 관리용으로 쓰이게 됩니다. 식에 의하면 블록 개수가 8 미만인 레벨에 대해서도 1바이트의 비트맵을 할당하므로 어떤 개수던지 ceil(n / 8) 을 이용해 충분한 비트맵을 할당할 수 있습니다. 아래는 blockCount 개의 블록을 가진 한 레벨의 비트맵을 할당하는 코드입니다.
bytes = blockCount // 8
if blockCount % 8 > 0:
bytes += 1
bitmap = bytearray(bytes)상위 레벨의 블록 개수는 바로 아래 레벨 블록 개수의 절반이므로 최하위 레벨의 블록개수를 초기값으로 아래 코드와 같이 전체 레벨에 대해 비트맵을 할당할 수 있습니다.
smallestBlockCount = # 가장 작은 블록의 개수
def createBitmaps():
bitmaps = []
blockCount = smallestBlockCount
while blockCount > 0:
bytes = blockCount // 8
if blockCount % 8 > 0:
bytes += 1
bitmap = bytearray(bytes) # e.g. bytearray[3] = [0, 0, 0]
bitmaps.append(bitmap)
blockCount //= 2
return bitmapscreateBitmaps 함수로 만들어진 비트맵 배열은 각 레벨을 인덱스로 해당 레벨의 비트맵을 읽을 수 있습니다. 예를 들어 bitmaps[0] 는 레벨 0의 비트맵이고 레벨 0의 0번째 블록의 상태는 bitmaps[0][0 // 8] & (1 << (0 % 8)), 19번째 블록의 상태는 bitmaps[0][19 // 8] & (1 << (19 % 8)) 와 같이 읽을 수 있습니다. 매번 인덱스에 대해 나눗셈과 나머지 연산을 하면 코드 가독성에 좋지 않으므로 하나의 함수로 작성하겠습니다.
def getBlockStat(level, idx):
bitmap = bitmaps[level]
return 0 if bitmap[idx // 8] & (1 << (idx % 8)) == 0 else 1비트맵을 이용해 세번째 물음 "그 블록은 속해 있는 레벨에서 몇 번째 블록일까" 를 해결했습니다.
블록의 상태는 1일 때 사용 가능, 0일 때 사용 불가능하다고 하면 위에서 작성한 함수 createBitmaps 는 모든 비트를 0으로 초기화하므로 비트맵은 만들었지만 사용할 수 있는 블록이 한 개도 없는 상태입니다. 네번째 물음 "만약 해당 레벨에 할당 가능한 블록이 없다면 어떻게 해야 할까" 역시 이 문제의 답을 요구하고 있습니다.
모든 블록을 사용 가능으로 표시하기 위해 비트맵의 값을 0xFF 로 초기화해야 할까요? 0xFF 로 초기화한다면 비트맵 상태가 가리키는 모습은 아래와 같습니다.
레벨 1의 1번째 블록을 사용한다고 하면 bitmaps[1][0] &= ~(1 << 1) 과 같이 비트를 0으로 만들어주고 블록을 할당하면 됩니다. 그리고 각 레벨은 사실 같은 메모리 공간을 가리키고 있으므로 레벨 1의 1번째 블록을 범위로 포함하는 상하위 레벨의 블록들 역시 대응하는 비트맵의 상태를 0으로 바꿔 주어야 합니다.
매번 할당할 때마다 상하위 레벨 블록들의 상태까지 신경 써 줘야 하는게 복잡하게 보입니다. 버디 블록은 이같이 복잡하고 비효율적인 방법 대신 짝이 없는 잉여 블록을 사용 가능한 상태로 초기화합니다. 그리고 원하는 레벨의 블록을 찾기 위해 상위 레벨의 블록을 쪼개는 방법을 이용합니다. 예를 들어 아래와 같이 초기화된 블록 계층이 있을 때 가장 상위 레벨의 블록은 한 개 뿐이므로 짝이 없는 잉여 블록입니다.
잉여 블록은 최상위 블록 뿐만 아니라 홀수 개의 블록을 갖는 모든 레벨에 존재합니다. 위 그림은 최상위 레벨을 제외한 각 레벨의 블록 개수가 이므로 잉여 블록이 없지만 만약 최하위 레벨이 7개의 블록을 가진다면 하위에서 상위 순으로 7 → 3 → 1 개의 블록을 가지게 되고 각 레벨에 모두 잉여 블록이 존재합니다.
잉여 블록을 적용하기 위해 함수 createBitmaps 를 수정해 보겠습니다.
smallestBlockCount = # 가장 작은 블록의 개수
def createBitmaps():
bitmaps = []
blockCount = smallestBlockCount
while blockCount > 0:
bytes = blockCount // 8
if blockCount % 8 > 0:
bytes += 1
bitmap = bytearray(bytes) # e.g. bytearray[3] = [0, 0, 0]
# 잉여 블록 처리 코드
if blockCount % 2 == 1:
# 마지막 비트맵의 8비트 중 마지막 비트를 1로 변경
bitmap[-1] |= (1 << (blockCount % 8 - 1))
bitmaps.append(bitmap)
blockCount //= 2
return bitmaps최상위 블록이 잉여 블록인 상태에서 100바이트의 메모리를 요구하는 프로세스가 있다고 하겠습니다. 100바이트의 메모리는 getBlockLevel(100) 을 통해 레벨 2임을 알 수 있습니다. 하지만 초기 상태의 레벨 2 비트맵은 전부 0인 상태입니다. 버디 블록 알고리즘은 상위 레벨에 사용 가능한 블록이 있는지 탐색합니다. 레벨 2의 상위 레벨인 레벨 3에는 사용 가능한 블록이 있습니다. 레벨 3의 블록의 크기는 레벨 2블록 크기의 두 배이므로 레벨 3블록을 반으로 쪼개 그 중 하나를 사용하면 됩니다. 레벨 3의 블록을 반으로 쪼개면 아래와 같습니다.
이제 레벨 2에 사용 가능한 블록이 존재하므로 이 중 하나를 사용하고 다른 하나는 사용 가능 블록으로 남겨 둡니다. 사용할 블록은 비트맵의 상태를 0으로 바꿔 줍니다. 남아 있는 사용 가능한 블록은 자연스럽게 잉여 블록이 됩니다.
100바이트의 메모리가 할당 된 후 이번엔 20바이트의 메모리를 요구하는 프로세스가 있다고 하겠습니다. 20바이트의 메모리는 getBlockLevel(20) 을 통해 레벨 0임을 알 수 있습니다. 현재 레벨 0에는 사용 가능한 블록이 없으니 레벨 1을 탐색해 보지만 레벨 1 역시 사용 가능한 블록이 없습니다. 따라서 레벨 2의 사용 가능한 블록을 쪼개 두 개의 레벨 1 블록을 사용 가능한 상태로 만들고, 다시 레벨 1 블록 중 하나를 쪼개 두 개의 레벨 0 블록을 사용 가능한 상태로 만듭니다.
이 과정을 코드로 작성해 보겠습니다.
bitmaps = # 각 레벨 별 블록의 상태를 저장하기 위한 비트맵 자료구조
smallestBlockSize = # 가장 작은 블록의 개수
def allocateBlock(size):
# size 에 맞는 블럭 레벨
level = getBlockLevel(size)
# 원하는 레벨의 사용 가능 블록 인덱스
idx = getAvailBlock(level)
availLevel = level
# 원하는 레벨에 사용 가능 블럭이 없다면 윗 레벨에서 탐색
if idx == -1:
highestLevel = len(bitmaps) - 1
while idx == -1 and availLevel < highestLevel:
availLevel += 1
idx = getAvailBlock(availLevel)
if idx == -1:
return None
# 상위 레벨에서 사용 가능 블록을 찾았다면 목표 레벨까지 블록 쪼개기
if level != availLevel:
idx = splitBlock(availLevel, level, idx)
# 블럭이 사용중임을 표시
setBlockStat(level, idx, 0)
...함수 allocateBlock 은 크게 네 부분으로 나눌 수 있습니다.
먼저 이전에 작성한 함수 getBlockLevel 을 이용해 size 에 맞는 블록의 레벨을 구하고 해당 레벨에 사용 가능한 블록이 있는지 확인합니다.
def allocateBlock(size):
level = getBlockLevel(size)
# 원하는 레벨의 사용 가능 블록 인덱스
idx = getAvailBlock(level)
...함수 getAvailBlock 은 비트맵을 이용해 level 에 속한 블록들 중 사용 가능한 블록이 있다면 그 인덱스를, 없다면 -1 을 반환합니다.
def getAvailBlock(level):
bitmap = bitmaps[level]
blockCount = smallestBlockCount >> level
byteCount = blockCount // 8
if blockCount % 8 > 0:
byteCount += 1
for i in range(byteCount):
if bitmap[i] != 0:
for j in range(8):
if bitmap[i] & (1 << j) != 0:
return 8 * i + j
return -1해당 레벨에 사용 가능한 블록이 없다면 레벨을 올려가며 사용 가능한 블록이 있는지 확인합니다. 만약 최상위 레벨까지 사용 가능한 블록이 없다면 현재 할당 가능한 블록이 전혀 없음을 뜻합니다.
def allocateBlock(size):
...
availLevel = level
# 원하는 레벨에 사용 가능 블럭이 없다면 윗 레벨에서 탐색
if idx == -1:
highestLevel = len(bitmaps) - 1
# 레벨을 하나씩 증가시키면서 사용 가능한 블록을 탐색
while idx == -1 and availLevel < highestLevel:
availLevel += 1
idx = getAvailBlock(availLevel)
if idx == -1:
return None
...사용 가능한 블록을 찾았다면 해당 블록이 원하는 레벨보다 상위 레벨인지 확인하고 상위라면 목표 레벨까지 블록들을 쪼갭니다.
def allocateBlock(size):
...
# 상위 레벨에서 사용 가능 블록을 찾았다면 목표 레벨까지 블록 쪼개기
if level != availLevel:
idx = splitBlock(availLevel, level, idx)
...함수 splitBlock 은 사용 가능한 블록이 있는 레벨의 idx 번째 블록을 목표 레벨까지 쪼개고 목표 레벨의 사용 가능 블록 인덱스를 반환합니다.
def splitBlock(from_, to, idx):
for i in range(from_, to, -1):
# 현재 블록의 상태를 "사용 중" 으로 바꿈
setBlockStat(i, idx, 0)
# 현재 블록의 왼쪽 하위 블록의 상태를 "사용 가능" 으로 바꿈
setBlockStat(i - 1, idx * 2, 1)
# 현재 블록의 오른쪽 하위 블록의 상태를 "사용 가능" 으로 바꿈
setBlockStat(i - 1, idx * 2 + 1, 1)
idx *= 2
return idx마지막으로 사용 가능 해진 목표 레벨의 블록 상태를 "사용 중" 으로 바꿔줍니다.
def allocateBlock(size):
...
# 블럭이 사용중임을 표시
setBlockStat(level, idx, 0)setBlockStat 함수는 블록의 상태를 바꾸는 간단한 함수입니다.
def setBlockStat(level, idx, flag):
bitmap = bitmaps[level]
if flag == 0:
bitmap[idx // 8] &= ~(1 << (idx % 8))
else:
bitmap[idx // 8] |= 1 << (idx % 8)allocateBlock 를 작성하면서 메모리 할당의 가장 중요한 부분을 완성했습니다. 지금까지 메모리 할당을 블록 할당 관점에서 살펴보았습니다. 실제 malloc 함수는 블록의 인덱스가 아닌 메모리 주소를 반환하므로 할당된 블록을 메모리 주소로 변환하는 작업이 필요합니다.
함수 allocateBlock 에서 변수 level 과 idx 는 할당한 블록이 속한 레벨과 인덱스를 저장하고 있습니다. 가장 작은 블록의 크기를 smallestBlockSize 이라 할 때 smallestBlockSize << level 은 level 에 속한 블록의 크기를 뜻합니다. 블록의 크기는 바이트 단위이므로 (smallestBlockSize << level) * idx 는 level 의 idx 번째 블록의 상대 주소가 됩니다. 여기서 상대 주소란 버디 블록이 속한 메모리 공간의 시작점을 0이라 할 때 시작점으로부터의 거리를 뜻합니다. 따라서 시작점의 절대 주소를 알고 있다면, 절대 주소에 (smallestBlockSize << level) * idx 를 더해 블록의 메모리 상 절대 주소를 알 수 있습니다. 정리하면 다음과 같습니다.
smallestBlockSize << level=level의 블록 크기(smallestBlockSize << level) * idx=level의idx번째 블록의 상대 주소- 버디 블록이 속한 메모리 공간의 시작점 절대 주소를
address라 할 때,address + (smallestBlockSize << level) * idx=level의idx번째 블록의 절대 주소 - 만약
idx가 0이라면address + (smallestBlockSize << level) * idx는address + 0 = address이고, 이는 모든 레벨의 0번째 블록의 상대 주소는 0, 절대 주소는address임을 뜻합니다.
함수 allocateBlock 이 할당 블록의 메모리 주소를 반환하도록 다음 코드를 추가하겠습니다.
address = # 0 번째 블록의 절대 주소
smallestBlockSize = # 가장 작은 블록의 개수
def allocateBlock(size):
...
blockSize = smallestBlockSize << level
relativeAddr = blockSize * idx
return address + relativeAddr💡 가장 작은 블록의 크기는 어떻게 정할까
블록 분할을 편하게 하기 위해 2의 지수승으로 정하는 것을 빼고는 프로그래머 마음입니다. 프로그램에서 작은 메모리를 빈번히 요구한다면 32바이트처럼 작은 크기도 괜찮지만 작을수록 비트맵 크기가 늘어나고 레벨이 많아져 블록 분할을 위한 연산이 많아짐을 고려해야합니다.
메모리 해제
메모리 할당 함수 void *malloc(size_t size) 은 메모리 크기를 매개 변수로 받아 메모리의 절대 주소를 반환했습니다. 함수 allocateBlock(size) 역시 메모리 크기를 매개 변수로 받아 메모리의 절대 주소를 반환합니다. 메모리 해제 함수 void free(void *ptr) 는 할당 함수의 반환값이었던 절대 주소를 매개 변수로 받습니다. 버디 블록에서 메모리 해제의 핵심은 절대 주소를 이용해 블록의 레벨과 인덱스를 찾는 것입니다. 찾아낸 레벨과 인덱스는 대응하는 비트맵을 0으로 만드는 데 사용할 수 있습니다.
함수 allocateBlock 의 마지막 과정에서 블록의 인덱스와 0번째 블록의 절대 주소를 이용해 블록의 절대 주소를 구할 수 있었습니다. 절대 주소는 0번째 블록의 절대 주소와 블록의 상대 주소를 더한 값이므로 0번째 블록의 절대 주소를 빼면 상대 주소를 구할 수 있습니다.
만약 상대 주소가 128이라면, 32바이트 블록으로 이루어진 레벨의 128 / 32 = 4번째, 64바이트 블록으로 이루어진 레벨의 128 / 64 = 2번째, 128바이트 블록으로 이루어진 레벨의 128 / 128 = 1번째 블록이 이 주소에 해당됩니다. 즉 블록이 속한 레벨만 알 수 있다면 인덱스는 나눗셈만으로 알 수 있습니다.
상대 주소가 어떤 레벨의 블록을 가리키는지 기록하기 위해 두번째 메타 데이터 자료구조 levelOfBlock를 도입하겠습니다. levelOfBlock 는 최하위 레벨 블록의 개수만큼 엔트리를 가지는 배열입니다.
그림에서 회색은 할당된 블록, 초록색은 사용 가능한 블록을 뜻합니다. 레벨 2의 할당된 블록을 살펴보겠습니다. 블록의 크기는 128 이고 1번째 블록이므로 상대 주소는 128 (128 x 1) 입니다. 상대 주소 128 은 최하위 레벨 블록 중 4번째 (128 / 32) 블록의 상대 주소와 같습니다.
어느 레벨에 속하든지 블록의 상대 주소를 최소 블록 크기로 나누면 항상 같은 인덱스를 갖습니다. 만약 레벨 2의 블록 대신 레벨 1의 2번째 블록이 할당되었다면 블록의 상대 주소는 128 (64 x 2) 이고 이를 최소 블록 크기로 나누면 4 (128 / 32) 입니다. 레벨 2의 1번째 블록과 레벨 1의 2번째 블록은 둘 다 같은 상대주소 128 를 가지고 있고 levelOfBlock 에서 4번째 엔트리를 가리킵니다. 이 점을 이용해 배열 levelOfBlock 에 할당된 블록의 레벨을 저장할 수 있습니다.
levelOfBlock 에서 -1 은 해당 상대 주소에 아무 블록도 할당되지 않았다는 것을 의미합니다. 메모리 해제 함수를 작성하기 전에 먼저 할당 함수 allocateBlock 에 levelOfBlock 를 적용해보겠습니다.
bitmaps = # 각 레벨 별 블록의 상태를 저장하기 위한 비트맵 자료구조
smallestBlockSize = # 가장 작은 블록의 개수
smallestBlockCount = # 가장 작은 블록의 개수
# levelOfBlock 초기화
levelOfBlock = [-1] * smallestBlockCount
def allocateBlock(size):
level = getBlockLevel(size)
idx = # level 의 할당 가능한 블록 인덱스
...
blockSize = smallestBlockSize << level
relativeAddr = blockSize * idx
# levelOfBlock 에 블록의 레벨 저장
levelOfBlock[ relativeAddr // smallestBlockSize ] = level
return address + relativeAddrallocateBlock 에서 블록을 할당할 때마다 levelOfBlock 에 레벨을 저장하므로 freeBlock 에서는 쉽게 상대 주소에 해당하는 블록의 레벨을 구할 수 있습니다.
smallestBlockSize = # 가장 작은 블록의 개수
address = # 버디 블록 메모리 공간의 시작점 절대 주소
def freeBlock(ptr):
relativeAddr = ptr - address
level = levelOfBlock[ relativeAddr // smallestBlockSize ]
...블록의 레벨을 알아냈으므로 블록의 인덱스를 구하는 것은 아주 쉽습니다. 레벨과 인덱스를 이용해 상대 주소를 구했던 과정을 역으로 풀면 됩니다.
smallestBlockSize = # 가장 작은 블록의 개수
address = # 버디 블록 메모리 공간의 시작점 절대 주소
def freeBlock(ptr):
relativeAddr = ptr - address
level = levelOfBlock[ relativeAddr // smallestBlockSize ]
blockSize = smallestBlockSize << level
# allocateBlock 에서는 상대 주소를 구하기 위해
# relativeAddr = blockSize * idx 와 같이 계산했다
idx = relativeAddr // blockSize
...만약 개발자가 실수로 freeBlock(ptr) 의 매개변수 ptr 를 할당받지 않는 임의의 주소값으로 전달하면 어떻게 될까요? C 코드에서 할당받지 않은 메모리 주소를 free 함수에 전달하면 pointer being freed was not allocated 에러를 내뿜습니다.
freeBlock 도 예기치 않은 에러를 방지하기 위해 조건문을 추가하겠습니다. 만약 할당한 블록의 주소라면 levelOfBlock 의 엔트리 값을 아무 레벨의 블록도 할당하지 않았다는 뜻에서 -1 로 변경해줍니다.
smallestBlockSize = # 가장 작은 블록의 개수
address = # 버디 블록 메모리 공간의 시작점 절대 주소
def freeBlock(ptr):
relativeAddr = ptr - address
level = levelOfBlock[ relativeAddr // smallestBlockSize ]
# 할당된 메모리인지 확인
if level == -1:
return
# levelOfBlock 의 엔트리 값을 -1 로 변경
levelOfBlock[ relativeAddr // smallestBlockSize ] = -1
blockSize = smallestBlockSize << level
idx = relativeAddr // blockSize
...allocateBlock 에서는 bitmaps 자료구조를 이용해 원하는 크기의 블록이 있는지 확인할 수 있었습니다. 만약 사용 가능한 블록이 없다면 상위 블록을 둘로 쪼갠 후 한 블록을 사용하고 나머지 하나는 잉여 블록으로 남겨 놓았습니다. freeBlock 에서는 이 과정을 역으로 진행합니다. 블록을 해제하면 bitmaps 의 대응하는 값이 0에서 1로 바뀌면서 사용 가능한 상태가 됩니다. 만약 해제한 블록의 짝 블록 역시 사용 가능한 상태라면 두 블록을 사용 불가 상태로 바꾸고 크기가 두 배인 상위 블록의 상태를 가능 상태로 만들어 줍니다. 마치 두 블록을 합쳐 하나의 블록으로 만드는 것과 같습니다.
위 과정을 함수 mergeBlock 로 만들어보겠습니다. 함수 mergeBlock 구현 과정에서 주의할 점은 짝 블록의 인덱스를 계산하는 방법입니다. 블록의 인덱스는 0부터 시작하므로 0-1, 2-3, 4-5 처럼 짝-홀 순으로 짝이 지어집니다. 블록의 인덱스를 idx 라 할 때 idx 가 홀수라면 짝 블록의 인덱스는 idx - 1 이고 idx 가 짝수라면 짝 블록의 인덱스는 idx + 1 입니다.
bitmaps = # 각 레벨 별 블록의 상태를 저장하기 위한 비트맵 자료구조
def mergeBlock(level, idx):
highestLevel = len(bitmaps) - 1
# 블록이 사용 가능하고 최상위 레벨이 아닐 때 까지 반복
while level < highestLevel and getBlockStat(level, idx):
# 짝 블록의 인덱스 계산
buddyIdx = idx + 1 if idx % 2 == 0 else idx - 1
# 짝 블록이 사용 가능 상태인지 확인
if getBlockStat(level, buddyIdx):
# 사용 가능하다면 현재 블록과 짝 블록의 상태를 불가능으로 전환
setBlockStat(level, idx, 0)
setBlockStat(level, buddyIdx, 0)
# 상위 블록의 상태를 가능으로 전환
setBlockStat(level + 1, idx // 2, 1)
else:
# 짝 블록이 사용 불가능 상태라면
# 현재 블록을 사용 가능 상태로 남겨 놓은 채 더 이상 상위 레벨을 탐색하지 않음
break
level += 1
idx //= 2마지막으로 함수 freeBlock 에 mergeBlock 코드 실행 구문을 넣겠습니다.
smallestBlockSize = # 가장 작은 블록의 개수
address = # 버디 블록 메모리 공간의 시작점 절대 주소
bitmaps = # 각 레벨 별 블록의 상태를 저장하기 위한 비트맵 자료구조
def freeBlock(ptr):
relativeAddr = ptr - address
level = levelOfBlock[ relativeAddr // smallestBlockSize ]
# 할당된 메모리인지 확인
if level == -1:
return
# levelOfBlock 의 엔트리 값을 -1 로 변경
levelOfBlock[ relativeAddr // smallestBlockSize ] = -1
blockSize = smallestBlockSize << level
idx = relativeAddr // blockSize
# 해제한 블록의 상태를 사용 가능으로 바꾼 뒤 mergeBlock
setBlockStat(level, idx, 1)
mergeBlock(level, idx)이렇게 해서 버디 블록 알고리즘 구현을 마쳤습니다. 알고리즘의 설명을 위해 상대 주소와 절대 주소, 잉여 블록 같은 다소 생소한 단어가 쓰였지만 알고 보면 더하고 곱하는 기본적인 사칙연산만으로 버디 블록 알고리즘은 구현 가능했습니다. 실제 동적 메모리 할당 구현은 C/C++ 과 같이 상대적으로 저수준 언어에서 필요하지만 코드의 간결성을 위해 python 으로 작성해보았습니다.
마지막으로 지금까지 작성한 코드를 BuddyBlockMemory 라는 클래스로 모듈화해 보았습니다. 각 메소드의 의미를 곱씹어 보며 정리해 보시기 바랍니다.
class BuddyBlockMemory:
def __init__(self, size, smallestBlockSize):
self.memory = bytearray(size)
self.address = id(self.memory)
self.smallestBlockSize = smallestBlockSize
self.smallestBlockCount = size // smallestBlockSize
self.levelOfBlock = [-1] * self.smallestBlockCount
self.bitmaps = self.createBitmaps()
def createBitmaps(self):
bitmaps = []
blockCount = self.smallestBlockCount
while blockCount > 0:
bytes = blockCount // 8
if blockCount % 8 > 0:
bytes += 1
bitmap = bytearray(bytes)
if blockCount % 2 == 1:
bitmap[-1] |= (1 << (blockCount % 8 - 1))
bitmaps.append(bitmap)
blockCount //= 2
return bitmaps
def allocateBlock(self, size):
# size 에 맞는 블럭 레벨
level = self.getBlockLevel(size)
# 원하는 레벨의 사용 가능 블록 인덱스
idx = self.getAvailBlock(level)
availLevel = level
# 원하는 레벨에 사용 가능 블럭이 없다면 윗 레벨에서 탐색
if idx == -1:
highestLevel = len(self.bitmaps) - 1
while idx == -1 and availLevel < highestLevel:
availLevel += 1
idx = self.getAvailBlock(availLevel)
if idx == -1:
return None
if level != availLevel:
idx = self.splitBlock(availLevel, level, idx)
# 블럭이 사용중임을 표시
self.setBlockStat(level, idx, 0)
blockSize = self.smallestBlockSize << level
relativeAddr = blockSize * idx
# 상대 메모리 주소를 이용해 해당 주소에 할당된 블록의 레벨 기록
self.levelOfBlock[ relativeAddr // self.smallestBlockSize ] = level
return self.address + relativeAddr
def freeBlock(self, ptr):
relativeAddr = ptr - self.address
level = self.levelOfBlock[ relativeAddr // self.smallestBlockSize ]
# 할당된 메모리인지 확인
if level == -1:
return
# 할당된 블록의 레벨 초기화
self.levelOfBlock[ relativeAddr // self.smallestBlockSize ] = -1
blockSize = self.smallestBlockSize << level
idx = relativeAddr // blockSize
self.setBlockStat(level, idx, 1)
self.mergeBlock(level, idx)
def mergeBlock(self, level, idx):
highestLevel = len(self.bitmaps) - 1
while level < highestLevel and self.getBlockStat(level, idx):
buddyIdx = idx + 1 if idx % 2 == 0 else idx - 1
if self.getBlockStat(level, buddyIdx):
self.setBlockStat(level, idx, 0)
self.setBlockStat(level, buddyIdx, 0)
self.setBlockStat(level + 1, idx // 2, 1)
else:
break
level += 1
idx //= 2
def getBlockLevel(self, size):
level = 0
blockSize = self.smallestBlockSize
while size > blockSize:
blockSize <<= 1
level += 1
return level
# level 의 블록 중 사용 가능한 블록의 인덱스를 반환
def getAvailBlock(self, level):
bitmap = self.bitmaps[level]
blockCount = self.smallestBlockCount >> level
byteCount = blockCount // 8
if blockCount % 8 > 0:
byteCount += 1
for i in range(byteCount):
if bitmap[i] != 0:
for j in range(8):
if bitmap[i] & (1 << j) != 0:
return 8 * i + j
return -1
def setBlockStat(self, level, idx, flag):
bitmap = self.bitmaps[level]
if flag == 0:
bitmap[idx // 8] &= ~(1 << (idx % 8))
else:
bitmap[idx // 8] |= 1 << (idx % 8)
def getBlockStat(self, level, idx):
bitmap = self.bitmaps[level]
return 0 if bitmap[idx // 8] & (1 << (idx % 8)) == 0 else 1
def splitBlock(self, from_, to, idx):
for i in range(from_, to, -1):
self.setBlockStat(i, idx, 0)
self.setBlockStat(i - 1, idx * 2, 1)
self.setBlockStat(i - 1, idx * 2 + 1, 1)
idx *= 2
return idx
