연속 메모리 할당

운영체제가 여러 프로세스를 메모리에 올리는 가장 단순한 방법은, 앞 글의 베이스와 한계 레지스터처럼 프로세스마다 연속된 메모리 블록을 하나씩 주는 것입니다. 시작 위치와 크기만 알면 되므로 관리가 쉽습니다. 그런데 이 방식으로 오래 운영하면, 프로세스들이 생기고 사라지며 메모리 여기저기에 구멍이 생깁니다. 결국 빈 공간을 모두 합치면 충분한데도 새 프로세스를 올리지 못하는 상황이 옵니다.

이 글에서는 연속 할당에서 메모리를 나누는 방법과 빈 공간을 고르는 전략을 살펴보고, 그 과정에서 생기는 단편화(fragmentation) 문제와 해결 시도들을 다룹니다. 마지막으로 Linux 커널이 물리 메모리를 나누어 주는 데 쓰는 버디 시스템을 봅니다.

고정 분할과 가변 분할

초기의 다중 프로그래밍 시스템은 메모리를 미리 정한 크기의 칸, 곧 파티션(partition)으로 나누어 두는 고정 분할(fixed partitioning)을 썼습니다. 256MB 메모리를 32MB짜리 칸 8개로 나누었다면, 5MB짜리 프로세스도 32MB 칸 하나를 차지하고 나머지 27MB는 아무도 쓰지 못합니다. 이렇게 할당된 블록 안에서 쓰이지 않고 버려지는 공간을 내부 단편화(internal fragmentation)라고 합니다.

칸의 크기를 8MB, 16MB, 32MB, 64MB처럼 다르게 두면 내부 단편화를 줄일 수 있으며, IBM의 OS/360 MFT가 이런 방식이었습니다. 그래도 고정 분할에는 더 근본적인 한계가 있습니다. 가장 큰 칸보다 큰 프로세스는 실행할 수 없고, 동시에 실행할 수 있는 프로세스 수가 칸의 수로 묶입니다.

가변 분할(variable partitioning)은 프로세스가 요청한 크기만큼의 연속된 공간을 그때그때 잘라 줍니다. IBM의 OS/360 MVT가 이 방식이었습니다. 필요한 만큼만 주므로 정렬 단위나 관리 정보 때문에 생기는 작은 여유를 빼면 내부 단편화가 거의 없습니다. 하지만 프로세스가 끝날 때마다 그 자리가 구멍(hole)으로 남습니다.

예를 들어 메모리에 P1(40MB), 빈 공간 20MB, P2(70MB), 빈 공간 55MB, P3(50MB), 빈 공간 10MB가 차례로 놓여 있다고 합시다. 빈 공간은 모두 85MB이지만, 60MB짜리 프로세스는 올릴 수 없습니다. 가장 큰 구멍이 55MB이기 때문입니다. 이처럼 빈 공간의 합은 충분한데 연속되어 있지 않아 쓰지 못하는 것을 외부 단편화(external fragmentation)라고 합니다. 내부 단편화가 블록 안에서 버려지는 공간이라면, 외부 단편화는 블록 사이에 흩어져 쓰지 못하는 공간입니다.

빈 공간을 고르는 세 가지 전략

가변 분할에서 새 프로세스를 올릴 때는 여러 구멍 가운데 어디에 놓을지 골라야 합니다. 대표적인 전략은 세 가지입니다.

최초 적합(first fit)은 메모리를 앞에서부터 살펴, 요청이 들어가는 첫 구멍에 놓습니다. 맞는 구멍을 찾으면 바로 멈추므로 빠르지만, 메모리 앞쪽에 작은 조각들이 쌓이는 경향이 있습니다. 최적 적합(best fit)은 요청이 들어가는 구멍 가운데 가장 작은 것, 곧 놓은 뒤 남는 양이 가장 적은 구멍에 놓습니다. 큰 구멍을 아껴 두지만, 남는 조각이 너무 작아 아무도 쓰지 못하는 부스러기가 많이 생길 수 있습니다. 구멍 목록을 크기순으로 정리해 두지 않았다면 매번 모든 구멍을 살펴야 하는 비용도 있습니다. 최악 적합(worst fit)은 가장 큰 구멍에 놓습니다. 남는 조각이 커서 다른 요청이 쓸 수 있다는 생각이지만, 큰 구멍을 먼저 써 버리므로 나중에 큰 요청이 오면 들어갈 곳이 없어집니다.

다음 코드는 크기가 100, 500, 200, 300, 600KB인 구멍 다섯 개에 212KB를 놓고, 이어서 600KB를 놓을 때 세 전략이 각각 어느 구멍을 고르는지 계산합니다. 구멍의 번호는 0부터 세고, -1은 놓을 곳이 없다는 뜻입니다.

def first_fit(holes, size):
    for i, hole in enumerate(holes):
        if hole >= size:                       # 처음 맞는 곳에서 멈춘다
            return i
    return -1

def best_fit(holes, size):
    fits = [(hole - size, i) for i, hole in enumerate(holes) if hole >= size]
    return min(fits)[1] if fits else -1        # 남는 양이 가장 적은 곳

def worst_fit(holes, size):
    fits = [(hole - size, -i) for i, hole in enumerate(holes) if hole >= size]
    return -max(fits)[1] if fits else -1       # 남는 양이 가장 많은 곳

def place(strategy, holes, size):
    i = strategy(holes, size)
    if i >= 0:
        holes[i] -= size
    return i

original = [100, 500, 200, 300, 600]           # 빈 공간의 크기(KB)
for strategy in (first_fit, best_fit, worst_fit):
    holes = original[:]                        # 전략마다 같은 출발점에서 시작한다
    first = place(strategy, holes, 212)
    after_first = holes[:]
    second = place(strategy, holes, 600)
    print(f"{strategy.__name__:9}: 212KB -> {first}번 {after_first}, 600KB -> {second}번")

first_fit: 212KB -> 1번 [100, 288, 200, 300, 600], 600KB -> 4번
best_fit : 212KB -> 3번 [100, 500, 200, 88, 600], 600KB -> 4번
worst_fit: 212KB -> 4번 [100, 500, 200, 300, 388], 600KB -> -1번

212KB 요청에 대해 최초 적합은 처음으로 들어가는 500KB 구멍을, 최적 적합은 남는 양이 88KB로 가장 적은 300KB 구멍을, 최악 적합은 가장 큰 600KB 구멍을 고릅니다. 세 경우 모두 빈 공간의 합은 1,700 − 212 = 1,488KB로 같지만, 남은 구멍들의 모양이 다릅니다. 그 차이가 다음 요청에서 드러납니다. 600KB를 요청하면 최초 적합과 최적 적합은 아직 남아 있는 600KB 구멍을 쓸 수 있지만, 최악 적합은 이미 600KB 구멍을 잘라 썼으므로 가장 큰 구멍이 500KB뿐이어서 실패합니다. 빈 공간의 합 1,488KB는 600KB보다 훨씬 큰데도 연속된 공간이 없어 실패한 것이므로, 외부 단편화의 예입니다.

이 결과로 어느 전략이 언제나 낫다고 말할 수는 없습니다. 요청의 크기가 어떤 분포를 따르느냐에 따라 결과가 달라지기 때문입니다. 시뮬레이션 연구들에서는 대체로 최초 적합과 최적 적합이 메모리 이용률에서 비슷하고 최악 적합보다 낫다는 결과가 나왔으며, 최초 적합은 탐색이 빨라 많이 쓰입니다.

외부 단편화는 얼마나 심각할까

외부 단편화의 규모에 대해서는 50% 규칙(50-percent rule)이라는 관찰이 알려져 있습니다. 최초 적합으로 할당과 해제가 오래 반복된 정상 상태에서는, 할당된 블록이 $N$개일 때 빈 구멍이 약 $0.5N$개 생긴다는 것입니다. 이는 블록 개수의 관계이므로, 구멍과 블록의 평균 크기가 같다고 가정하면 메모리의 약 3분의 1이 구멍으로 흩어져 쓰기 어려워진다는 뜻이 됩니다. 평균 크기가 다르다면 이 비율도 달라집니다.

압축: 흩어진 구멍을 모으기

외부 단편화를 직접 푸는 방법은 압축(compaction)입니다. 사용 중인 블록들을 메모리의 한쪽으로 몰아 붙여, 흩어진 구멍들을 하나의 큰 빈 공간으로 합치는 것입니다.

앞의 예에서 P1, P2, P3를 한쪽으로 모으면 사용 중인 160MB가 연속으로 놓이고, 나머지 85MB가 하나로 합쳐집니다. 전체 245MB는 그대로이지만, 가장 큰 연속 빈 공간이 55MB에서 85MB로 커져 60MB 요청을 받을 수 있게 됩니다.

하지만 압축에는 큰 비용과 조건이 따릅니다. 첫째, 프로세스의 메모리를 통째로 복사해야 하므로, GB 단위의 메모리를 옮기면 그동안 시스템이 멈추다시피 합니다. 둘째, 옮긴 뒤에도 프로세스가 같은 데이터를 가리키도록 주소를 맞추어야 합니다. 실행할 때 바인딩하는 시스템이라면 베이스 레지스터만 바꾸면 되지만, 적재할 때 주소를 고정한 시스템이라면 압축할 수 없습니다. 셋째, 장치가 DMA로 데이터를 쓰고 있는 입출력 버퍼처럼 옮길 수 없는 영역이 있으면 그 영역을 피해 가며 모아야 하므로, 기대만큼 큰 공간이 생기지 않을 수 있습니다.

결국 연속 할당의 단편화를 근본적으로 풀려면, 프로세스의 메모리가 연속이어야 한다는 전제 자체를 버려야 합니다. 9장의 페이징은 프로세스의 메모리를 같은 크기의 작은 조각으로 나누어 물리 메모리 아무 곳에나 흩어 놓을 수 있게 해, 프로세스 전체를 위한 큰 연속 공간을 요구하지 않습니다. 다음 글의 세그먼테이션은 프로그램을 코드, 데이터, 스택 같은 논리적인 단위로 나누지만, 단위의 크기가 제각각이므로 외부 단편화가 여전히 남습니다.

버디 시스템

페이징을 쓰더라도 연속된 물리 메모리가 필요한 경우는 남아 있습니다. 장치가 DMA로 큰 버퍼를 쓰거나 커널이 큰 자료구조를 만들 때가 그렇습니다. Linux 커널은 물리 메모리를 페이지 단위로 나누어 주면서 연속된 큰 블록도 만들어 줄 수 있도록 버디 시스템(buddy system)을 씁니다. 고정 분할과 가변 분할의 중간에 있는 방법입니다.

버디 시스템은 블록의 크기를 2의 거듭제곱으로만 다룹니다. 요청이 오면 크기를 2의 거듭제곱으로 올린 뒤, 그 크기의 빈 블록이 있으면 주고, 없으면 더 큰 블록을 반으로 나눕니다. 반으로 나눈 두 블록을 서로의 버디(buddy)라고 하며, 하나는 요청에 쓰거나 더 나누고 다른 하나는 빈 목록에 둡니다. 블록을 돌려받으면 그 버디도 비어 있는지 확인해, 비어 있으면 둘을 합쳐(coalescing) 원래 크기의 블록으로 되돌리고, 합친 블록의 버디도 비어 있는지 다시 확인합니다. 크기가 같고 붙어 있더라도 같은 블록에서 나뉜 짝이 아니면 합치지 않습니다. 다음 코드는 256KB 메모리에서 이 과정을 따라갑니다.

class Buddy:
    def __init__(self, total):
        self.total = total
        self.free = {total: [0]}               # 블록 크기 -> 빈 블록의 시작 주소들

    def alloc(self, size):
        block = 1
        while block < size:
            block *= 2                         # 요청을 2의 거듭제곱으로 올린다
        s = block
        while s <= self.total and not self.free.get(s):
            s *= 2                             # 빈 블록이 있는 가장 작은 크기를 찾는다
        if s > self.total:
            return None
        addr = self.free[s].pop(0)
        while s > block:                       # 반으로 나누고 뒤쪽 반(버디)은 빈 목록에 둔다
            s //= 2
            self.free.setdefault(s, []).append(addr + s)
        return addr, block

    def release(self, addr, block):
        while block < self.total:
            buddy = addr ^ block               # 버디의 주소는 블록 크기의 비트 하나만 다르다
            if buddy not in self.free.get(block, []):
                break
            self.free[block].remove(buddy)     # 버디도 비어 있으면 합친다
            addr, block = min(addr, buddy), block * 2
        self.free.setdefault(block, []).append(addr)

    def state(self):
        return {s: sorted(a) for s, a in sorted(self.free.items()) if a}

memory = Buddy(256)                            # 단위: KB
a = memory.alloc(33)
print(f"33KB 요청 -> 주소 {a[0]}, {a[1]}KB 블록 | 빈 블록 {memory.state()}")
b = memory.alloc(20)
print(f"20KB 요청 -> 주소 {b[0]}, {b[1]}KB 블록 | 빈 블록 {memory.state()}")
memory.release(*a)
print(f"주소 {a[0]}의 {a[1]}KB 해제 | 빈 블록 {memory.state()}")
memory.release(*b)
print(f"주소 {b[0]}의 {b[1]}KB 해제 | 빈 블록 {memory.state()}")

33KB 요청 -> 주소 0, 64KB 블록 | 빈 블록 {64: [64], 128: [128]}
20KB 요청 -> 주소 64, 32KB 블록 | 빈 블록 {32: [96], 128: [128]}
주소 0의 64KB 해제 | 빈 블록 {32: [96], 64: [0], 128: [128]}
주소 64의 32KB 해제 | 빈 블록 {256: [0]}

33KB 요청은 64KB로 올림 됩니다. 처음에는 256KB 블록 하나뿐이므로, 이를 128KB 두 개로 나누어 뒤쪽(128)을 빈 목록에 두고, 앞쪽을 다시 64KB 두 개로 나누어 뒤쪽(64)을 빈 목록에 두고, 앞쪽(0)을 줍니다. 20KB 요청은 32KB로 올림 되고, 빈 64KB 블록(64)을 나누어 앞쪽(64)을 주고 뒤쪽(96)을 남깁니다. 0번의 64KB를 돌려받을 때는 그 버디인 64번 64KB 블록이 20KB 요청에 쓰이고 있어 합치지 못합니다. 마지막으로 64번의 32KB를 돌려받으면, 버디인 96번 32KB가 비어 있어 64KB로 합치고, 그 버디인 0번 64KB도 비어 있어 128KB로, 다시 버디인 128번 128KB와 합쳐 처음의 256KB 블록으로 돌아옵니다.

버디의 주소를 계산하는 방법이 이 구조의 핵심입니다. 크기가 $2^k$인 블록은 언제나 $2^k$의 배수 위치에서 시작하므로, 버디의 주소는 자기 주소에서 $2^k$에 해당하는 비트 하나만 뒤집으면 됩니다. 그래서 합칠 짝을 찾는 데 목록 전체를 뒤질 필요가 없고, 나누고 합치는 횟수도 크기 단계의 수를 넘지 않습니다. 이렇게 빠르게 합칠 수 있어 큰 연속 블록을 다시 만들기 쉽고, 외부 단편화가 줄어듭니다. 대신 요청을 2의 거듭제곱으로 올리므로 내부 단편화가 생깁니다. 33KB 요청은 64KB 블록에서 31KB를, 20KB 요청은 32KB 블록에서 12KB를 버립니다.

실제 Linux의 버디 할당자는 바이트가 아니라 페이지를 단위로 하며, 크기를 차수(order)로 나타냅니다. 차수가 $k$인 블록은 연속된 페이지 $2^k$개이고, 4KiB 페이지라면 차수 10이 4MiB입니다. 지금 각 차수의 빈 블록이 몇 개인지는 /proc/buddyinfo에서 볼 수 있어, 큰 연속 블록이 부족해지는 외부 단편화를 진단할 때 씁니다. 몇십 바이트짜리 작은 커널 객체를 페이지 단위로 주면 낭비가 크므로, Linux는 버디 할당자에게서 받은 페이지를 다시 같은 크기의 작은 칸으로 나누어 쓰는 슬랩 할당자(slab allocator)를 그 위에 둡니다.

더 깊이: 페이지를 옮겨 큰 블록을 다시 만드는 메모리 압축

버디 할당자를 쓰더라도 오래 실행한 시스템에서는 빈 페이지가 흩어져, 빈 메모리는 많은데 높은 차수의 블록은 없는 상황이 생깁니다. 그래서 Linux는 앞에서 비용이 크다고 했던 압축을 페이지 단위로 다시 씁니다. 연속 할당과 달리 페이징에서는 페이지의 물리 위치를 옮기고 페이지 테이블만 고치면 프로세스가 보는 가상 주소가 바뀌지 않으므로, 옮길 수 있는 페이지를 골라 한쪽으로 모을 수 있습니다. 이렇게 프로세스가 실행되는 중에 페이지의 물리 위치를 바꾸는 기능을 페이지 이주(page migration)라고 합니다.

Linux의 가상 메모리 설정 문서에 따르면 CONFIG_COMPACTION을 켠 커널에서 /proc/sys/vm/compact_memory에 1을 쓰면 모든 메모리 영역(zone)을 압축해 빈 메모리를 되도록 연속된 블록으로 만듭니다. 큰 페이지(huge page)를 할당할 때 특히 쓸모가 있으며, 이렇게 명령하지 않아도 메모리를 할당하려는 프로세스가 필요하면 그 자리에서 직접 압축합니다. 배경에서 미리 압축하는 정도는 0부터 100까지의 compaction_proactiveness로 정하고, 기본값은 20입니다. 문서는 압축이 여러 프로세스의 페이지를 옮기는 일이어서 시스템 전체에 영향을 주고, 상관없는 응용 프로그램의 지연이 갑자기 늘어날 수 있다고 경고합니다.

정리

• 연속 할당은 프로세스마다 연속된 메모리 블록 하나를 주는 방식입니다. 고정 분할은 미리 나눈 칸을 주어 내부 단편화가 생기고, 가변 분할은 필요한 만큼 주지만 구멍이 생겨 외부 단편화가 생깁니다.
• 빈 공간을 고르는 전략에는 처음 맞는 곳을 고르는 최초 적합, 남는 양이 가장 적은 곳을 고르는 최적 적합, 가장 큰 곳을 고르는 최악 적합이 있으며, 결과는 요청의 분포에 따라 달라집니다.
• 외부 단편화는 빈 공간의 합이 충분해도 연속된 공간이 없어 할당하지 못하는 문제이며, 최초 적합에서는 블록 수의 절반 정도의 구멍이 생긴다는 50% 규칙이 알려져 있습니다.
• 압축은 블록을 모아 구멍을 합치지만, 복사 비용이 크고 실행할 때 바인딩이 필요하며 옮길 수 없는 영역이 있으면 효과가 줄어듭니다. 근본적인 해결은 연속이라는 전제를 버리는 페이징입니다.
• 버디 시스템은 2의 거듭제곱 크기로 블록을 나누고 합쳐 큰 연속 블록을 빠르게 되살리며, Linux는 이를 페이지 단위로 쓰고 그 위에 슬랩 할당자를 둡니다.

연습 문제

1. 고정된 블록이 있는 압축

메모리 245MB에 P1(40MB), 빈 공간 20MB, P2(70MB), 빈 공간 55MB, P3(50MB), 빈 공간 10MB가 차례로 놓여 있고, 70MB 요청이 왔습니다. 모든 블록을 옮길 수 있을 때와, P2가 DMA 버퍼라서 지금 위치(60MB에서 130MB까지)를 떠날 수 없을 때 각각 압축으로 요청을 받을 수 있는지 판단하세요. P1과 P3는 P2를 넘어가지 않고 각자 자기 쪽 안에서만 옮길 수 있습니다.

2. 최악 적합의 실패

본문의 구멍 [100, 500, 200, 300, 600]KB에 최악 적합으로 212KB를 놓은 뒤 600KB 요청이 실패했습니다. 이때 빈 공간의 합은 얼마이고, 실패한 이유는 무엇인가요? 같은 두 요청에서 최초 적합과 최적 적합이 성공한 것만 보고 "최악 적합은 언제나 나쁘다"고 결론 내릴 수 있을까요?

3. 버디 시스템의 할당과 합치기

512KB 메모리를 버디 시스템으로 관리합니다. 100KB 요청 A가 오고, 이어서 60KB 요청 B가 왔습니다. 각 요청이 받는 블록의 크기와 주소, 그때의 빈 블록 목록을 구하세요. 그다음 A를 해제하면 빈 블록 목록은 어떻게 되나요? 두 요청의 내부 단편화도 구하세요.

다음 글 세그먼테이션에서는 프로그램을 코드, 데이터, 스택 같은 논리적인 단위로 나누어 메모리에 놓는 방법을 살펴봅니다.