메모리 관리

메모리는 주소로 접근하는 바이트들의 배열이다(C에서 주소를 직접 다루는 모습은 포인터와 메모리). 여러 프로세스가 한정된 물리 메모리를 나눠 쓰려면, 프로세스가 보는 주소를 실제 메모리 위치로 바꿔 주고 서로의 영역을 보호해야 한다. 이 노트는 프로세스 전체 또는 일부를 어떻게 메모리에 배치하는지를 다룬다. 필요한 부분만 올리는 방법은 가상 메모리에서 이어진다.

논리 주소와 물리 주소

주소 바인딩 (Address Binding)

주소가 심볼릭 주소(변수·함수 이름) → 논리 주소 → 물리 주소로 결정되는 과정이다. 논리 주소가 물리 주소로 정해지는 시점에 따라 세 가지로 나뉜다.

앞의 두 방식은 한 번 정해지면 바뀌지 않아 정적 바인딩, 실행 타임 바인딩은 실행 중에 주소가 정해지고 바뀔 수 있어 동적 바인딩(dynamic binding) 이라고도 부른다. 현대 컴퓨터는 실행 타임 바인딩을 쓴다. 컴파일·로드 타임 바인딩에서는 논리 주소와 물리 주소가 같고, 실행 타임 바인딩에서만 둘이 달라진다. 객체 지향 언어에서 말하는 동적 바인딩(오버라이딩된 메서드를 실행 시점의 실제 객체 타입으로 고르는 것, Java 기초)은 「결정을 실행 시점으로 미룬다」는 발상만 같고 다른 개념이다.

MMU (Memory-Management Unit)

논리 주소를 물리 주소로 바꿔 주는 하드웨어다. 가장 단순한 방식은 프로세스의 물리 시작 주소를 담은 relocation(base) 레지스터와 주소 공간 크기를 담은 limit 레지스터를 쓴다. 쓸 수 있는 물리 주소는 base 이상, base + limit 미만이고, 벗어나면 트랩으로 막는다(메모리 보호).

flowchart TB
    q{"논리 주소 #lt; limit ?"}
    q -->|"아니오"| trap["trap(addressing error)<br/>운영체제가 원인을 확인"]
    q -->|"예"| ok["물리 주소 = 논리 주소 + relocation 레지스터"]

예: 논리 주소 공간이 0~3000인 프로세스가 물리 메모리 14000번지에 올라가 있다면, 논리 주소 346은 14346이 된다. 사용자 프로그램은 논리 주소만 다루고 실제 물리 주소는 볼 수도, 알 필요도 없다.

관련 기법

스와핑

backing store는 프로세스 이미지를 담을 만큼 빠르고 큰 디스크 공간이다. 중기 스케줄러가 보통 우선순위가 낮은 프로세스를 내보낸다. 컴파일·로드 타임 바인딩이면 원래 위치로 swap in 해야 하지만, 실행 타임 바인딩이면 빈 곳 어디에나 올릴 수 있다. 스왑 시간의 대부분은 데이터 양에 비례하는 전송 시간이다. 100MB 프로세스를 초당 50MB를 옮기는 디스크로 내보내면 2초, 다시 올리는 데 2초가 더 들어 한 번 맞바꾸는 데 4초다. 그래서 실제로 쓰는 메모리만큼만 옮겨야 하고, 프로세스를 통째로 옮기는 스와핑 대신 페이지 단위로 옮기는 방식이 자리 잡았다.

스와핑을 쓰면 프로세스들의 크기 합이 물리 메모리보다 커도 동시에 실행할 수 있다. A, B, C를 올린 상태에서 D가 필요하면 당장 쓰지 않는 B를 swap out 하고 D를 올리고, 다시 B가 필요하면 A를 내보내고 B를 올리는 식이다. 페이징에서는 같은 일을 페이지 단위로 하며 page out, page in이라고 부른다. 스왑 영역의 크기와 사용량은 Linux에서 free -h의 Swap 줄이나 top으로, macOS에서 sysctl vm.swapusage로 확인한다.

메모리 관리 정책

운영체제가 메모리를 나눠 줄 때 정해야 하는 것은 셋이다. 아래 할당 방식과 가상 메모리의 알고리즘은 모두 이 셋 중 하나에 대한 답이다.

물리 메모리 할당

메모리는 보통 낮은 주소의 OS 상주 영역(인터럽트 벡터 포함)과 높은 주소의 사용자 프로세스 영역으로 나뉜다. 사용자 영역을 프로세스에 나눠 주는 방법은 두 가지다.

프로세스를 연속된 공간에 올리는 연속 할당(고정·가변 분할)과, 여러 영역에 나눠 올리는 불연속 할당(페이징, 세그멘테이션, 페이지드 세그멘테이션)이 있다. 오늘날 쓰는 것은 불연속 할당이다.

연속 할당

단편화와 대응

가변 분할에서는 크기가 제각각인 빈 공간(hole)이 흩어지고, 운영체제는 할당 공간과 hole 목록을 관리한다.

예를 들어 hole이 순서대로 A 30MB, B 60MB, C 20MB이고 20MB짜리 프로세스를 올린다면 First-fit은 처음 맞는 A, Best-fit은 크기가 딱 맞는 C, Worst-fit은 가장 큰 B를 고른다.

실험적으로 First-fit과 Best-fit이 Worst-fit보다 속도와 공간 이용률이 낫다.

Worst-fit은 큰 hole을 쪼개 남는 조각도 쓸 만한 크기로 남기려는 발상이라, 요청 크기가 고르고 아주 작은 조각이 쌓이는 것을 피하고 싶을 때만 의미가 있다. 대신 큰 요청이 들어갈 자리를 먼저 써 버려서 실제로는 거의 쓰지 않는다.

외부 단편화가 생기는 과정은 다음과 같다. 사용자 영역 200MB에 A 50MB, B 30MB, C 100MB, D 20MB를 차례로 빈틈없이 올렸다가 B와 D가 끝나면, 빈 공간은 B 자리 30MB와 D 자리 20MB로 합쳐 50MB다. 그런데 두 hole이 떨어져 있어 50MB짜리 프로세스는 어디에도 올릴 수 없다.

[ A 50 | 빈 30 | C 100 | 빈 20 ]   빈 공간 합 50MB, 가장 큰 hole 30MB

컴팩션으로 hole을 모을 수는 있지만, 옮기는 동안 프로세스들이 일을 멈춰야 하고, 어떤 순서로 옮겨야 비용이 가장 적은지도 정하기 어렵다. 그래서 현대 운영체제는 연속 할당 대신 페이징을 쓴다. 연속 할당은 프로세스 전체를 올려야 하므로 물리 메모리보다 큰 프로세스를 실행할 수 없다는 한계도 있다.

페이징 (Paging)

프로세스의 논리 주소 공간을 같은 크기의 페이지(page) 로 자르고, 물리 메모리도 같은 크기의 프레임(page frame) 으로 나눈 뒤 페이지를 아무 빈 프레임에나 올린다. 외부 단편화가 생기지 않는다(마지막 페이지에 약간의 내부 단편화는 생길 수 있다).

flowchart TB
  la["논리 주소 = [ 페이지 번호 p | 오프셋 d ]"] -->|"페이지 테이블[p] = 프레임 번호 f"| pa["물리 주소 = [ 프레임 번호 f | 오프셋 d ]"]

• 프로세스마다 별도의 페이지 테이블이 있고, 엔트리 수는 논리 주소 공간의 페이지 수와 같다(배열의 인덱스 = 페이지 번호).
• 페이지 크기는 보통 4KB이고, 페이지 테이블은 메인 메모리에 있다. 실제 크기는 getconf PAGESIZE로 확인한다.

주소의 비트 수는 페이지 크기와 개수에서 바로 나온다. 페이지가 1024B(2¹⁰)이고 프로세스 하나가 최대 8개(2³) 페이지를 가지며 물리 메모리가 32개(2⁵) 프레임이라면, 오프셋이 10비트이므로 논리 주소는 페이지 번호 3비트를 더해 13비트, 물리 주소는 프레임 번호 5비트를 더해 15비트다. 논리 주소 공간과 물리 메모리의 크기가 서로 달라도 되는 이유가 여기서 보인다.

페이지가 물리 메모리 곳곳에 흩어져 있어도 CPU는 논리 주소의 0번 페이지부터 차례로 실행하면 된다. 페이지 테이블이 각 페이지가 어느 프레임에 있는지 알려 주므로, 물리적으로는 흩어져 있어도 CPU에게는 연속된 것처럼 보인다. 페이지와 프레임의 크기가 같으므로 오프셋 d는 변환 전후가 같다. 예를 들어 페이지 크기가 4바이트이고 페이지 테이블에서 5번 페이지가 1번 프레임에 있다면, 논리 주소 (5, 2)는 1번 프레임의 시작(4번지)에서 2만큼 떨어진 6번지가 된다.

페이지 테이블 구현과 TLB

페이지 테이블의 위치와 크기는 PTBR(Page-Table Base Register)과 PTLR(Page-Table Length Register)이 가리킨다. 페이지 테이블은 프로세스마다 있으므로 PTBR 값은 프로세스의 PCB에 저장되고, 문맥 교환 때 실행할 프로세스의 값으로 바뀐다. 테이블이 메모리에 있으므로 데이터 하나를 읽는 데 메모리 접근이 두 번(테이블 + 데이터) 필요하다.

이를 줄이려고 TLB(Translation Look-aside Buffer) 라는 고속의 주소 변환용 캐시(associative register)를 둔다.

• TLB에는 자주 참조되는 페이지 테이블 엔트리 일부만 들어 있고, 병렬 검색(parallel search)이 가능하다.
• 페이지 번호가 TLB에 있으면 바로 프레임 번호를 얻고, 없으면 메모리의 페이지 테이블에서 찾는다.
• 프로세스마다 주소 변환 정보가 다르므로, 기본적으로는 문맥 교환 때 TLB를 비운다(flush). 다만 현대 CPU는 TLB 엔트리에 주소 공간 식별자(ARM의 ASID, x86의 PCID)를 붙여 여러 프로세스의 엔트리를 함께 담아 둘 수 있어, 매번 전체를 비우지 않아도 된다.

MMU와 TLB는 CPU 코어 안에 있다. 코어마다 명령어용·데이터용 L1 TLB와 그보다 큰 공용 L2 TLB를 두고, TLB 미스가 나면 x86·ARM은 하드웨어 페이지 테이블 워커가 메모리의 페이지 테이블을 직접 따라가 채운다. 운영체제는 테이블을 만들어 둘 뿐 미스 처리에 끼지 않는다. MIPS처럼 TLB 미스를 운영체제 트랩으로 처리하는 구조도 있다. 코어가 여럿이면 TLB도 코어마다 따로라서, 매핑을 바꿀 때 다른 코어의 옛 항목을 지우는 TLB shootdown이 필요하다(캐시를 고려한 코드).

TLB 접근 시간을 ε, 메모리 접근 시간을 1, TLB에서 찾을 확률(hit ratio)을 α라고 하면 실질 접근 시간(EAT)은 다음과 같다.

EAT = (1 + ε)α + (2 + ε)(1 - α) = 2 + ε - α

α가 1에 가까울수록 페이지 테이블만 쓸 때(2)보다 훨씬 빠르다.

실제 시간으로 넣어 보면 차이가 분명하다. TLB 검색이 50ns, 메모리 접근이 750ns라면 TLB 적중 시 50 + 750 = 800ns, 실패 시 테이블까지 한 번 더 읽어 50 + 750 + 750 = 1550ns다.

TLB 실패 한 번의 추가 비용이 메모리 접근 한 번(750ns)이므로, 적중률이 10%p 오를 때마다 실효 접근 시간이 75ns씩 줄어든다.

2단계 페이지 테이블

32비트 주소면 주소 공간이 2³² B = 4GB다. 페이지가 4KB면 페이지가 1M(2²⁰)개, 엔트리 하나가 4B면 페이지 테이블 하나에 4MB가 필요하다. 페이지가 1KB라면 오프셋이 10비트, 페이지 번호가 22비트라 엔트리가 2²² = 약 420만 개(4B 엔트리면 16MB)로 늘어난다. 페이지가 작을수록 테이블이 커진다. 프로세스마다 이만큼을 연속으로 잡는 것은 낭비인데, 실제 프로그램은 주소 공간의 일부만 쓴다.

2단계 페이지 테이블은 페이지 테이블 자체를 페이지로 나누고, 바깥 페이지 테이블이 안쪽 페이지 테이블을 가리킨다. 사용하지 않는 주소 영역에 대한 바깥 테이블 엔트리는 NULL로 두어 안쪽 테이블을 만들지 않는다. 또 바깥 페이지 테이블만 항상 메모리에 두고, 안쪽 테이블은 지금 필요한 것만 메모리에 올려 둘 수 있다. 공간은 줄지만 주소 변환 시간은 늘어난다.

flowchart TB
  la["논리 주소 [ p1 | p2 | d ]"] --> p1["p1 → 바깥 페이지 테이블에서 안쪽 페이지 테이블의 위치를 찾는다"]
  p1 --> p2["p2 → 안쪽 페이지 테이블에서 프레임 번호를 찾는다"]
  p2 --> d["d → 프레임 번호에 오프셋을 붙여 물리 주소를 만든다"]

32비트 논리 주소 = [ p1 (10비트) | p2 (10비트) | d (12비트) ]

오프셋 d는 페이지 크기 4KB = 2¹²에서, p2는 안쪽 테이블 한 장(4KB)에 4B 엔트리가 2¹⁰개 들어가서, p1은 나머지 32 − 12 − 10에서 나온다.

32비트 운영체제가 메모리를 4GB까지만 쓰는 것도 같은 계산에서 나온다. 가상 주소가 32비트라 한 프로세스가 가리킬 수 있는 주소는 2³² = 4GB가 끝이고, 그중 일부(Linux 32비트는 보통 1GB, Windows는 2GB)는 커널 영역이라 사용자 프로그램은 그보다 적게 쓴다. 물리 주소의 한계는 페이지 테이블 엔트리의 프레임 번호 폭이 정하므로, x86의 PAE(Physical Address Extension)는 엔트리를 8바이트로 키우고 3단계 테이블을 써 물리 메모리를 64GB(36비트 주소)까지 늘렸다. 그래도 프로세스 하나의 가상 주소 공간은 4GB 그대로라서, 결국 64비트로 넘어갔다. 32비트와 64비트의 레지스터·포인터·주소 공간 비교는 데이터의 표현에 있다.

단계가 늘수록 메모리 접근이 많아지지만, TLB 덕분에 다단계 페이지 테이블도 실제 오버헤드는 크지 않다. 64비트 시스템은 더 많은 단계를 쓴다. 예를 들어 x86-64는 가상 주소 48비트에 4단계 페이지 테이블을 쓰고, 이를 57비트·5단계로 늘린 방식도 지원한다.

페이지 테이블 엔트리와 변형

쓰기 시 복사 (Copy-on-Write)

페이징이 주는 이점은 외부 단편화 해결만이 아니다. 여러 페이지 테이블이 같은 프레임을 가리킬 수 있으므로 프로세스 사이에 페이지를 공유할 수 있고, 그 대표적인 쓰임이 fork()의 쓰기 시 복사다.

프로세스는 원래 자원을 공유하지 않으므로, 이론대로라면 fork()는 부모의 메모리를 다른 프레임에 통째로 복사해야 한다. 그러면 자식을 만드는 데 오래 걸리고 같은 내용이 메모리에 두 벌 올라간다. 쓰기 시 복사는 이를 다음처럼 피한다.

fork() 직후 : 자식의 페이지 테이블이 부모와 같은 프레임을 가리킨다 (복사 없음)
              공유된 페이지는 둘 다 읽기 전용으로 표시해 둔다
누군가 쓰기 : 읽기 전용 페이지라 트랩이 나고, 커널이 그 페이지만 새 프레임에 복사해
              쓴 쪽의 페이지 테이블이 새 프레임을 가리키게 한다 (쓰기 가능으로 바꿔 둔다)
              나머지 페이지는 계속 공유한다

예를 들어 부모와 자식이 프레임 5, 4, 6을 함께 가리키다가 자식이 2번 페이지에 쓰면, 2번 페이지의 사본만 새 프레임에 만들어지고 자식만 그쪽을 가리킨다. 부모는 영향을 받지 않는다. 읽기만 하는 동안에는 한 벌만 있으므로 생성이 빠르고 메모리도 아낀다. fork() 직후 바로 exec()로 다른 프로그램을 올리는 흔한 경우에는 복사가 거의 일어나지 않는다(프로세스와 스레드).

페이징도 마지막 페이지에는 내부 단편화가 남는다. 페이지가 10KB, 프로세스가 108KB면 마지막 페이지의 2KB가 낭비된다. 그래서 페이지 크기는 내부 단편화와 페이지 테이블 크기 사이에서 정한다.

세그멘테이션 (Segmentation)

프로세스의 주소 공간을 의미 단위(segment) 로 나눈다. 작게는 함수 하나, 크게는 프로그램 전체가 하나의 세그먼트가 될 수 있고, 보통 code·data·stack을 각각 하나의 세그먼트로 둔다. 예: main(), 함수, 전역 변수, 스택, 심볼 테이블, 배열. 의미 단위이므로 세그먼트 크기는 제각각이다.

논리 주소 = [ 세그먼트 번호 s | 오프셋 d ]
세그먼트 테이블[s] = (base: 시작 물리 주소, limit: 세그먼트 길이)

세그먼트 테이블의 위치는 STBR, 세그먼트 수는 STLR이 담는다. s < STLR이고 d < limit이어야 유효하며, 아니면 trap이 발생한다. 통과하면 물리 주소 = base + d.

의미 단위라서 공유와 보호가 페이징보다 자연스럽고, 세그먼트 수가 적어 테이블 낭비도 적다.

세그멘테이션으로도 가상 메모리를 만들 수 있다. 세그먼트 테이블 엔트리에 valid 비트를 두고, 메모리에 없는 세그먼트를 참조하면 트랩을 내 디스크에서 올리는 요구 세그멘테이션이다(Burroughs B5000, 80286의 OS/2 1.x). 다만 세그먼트 크기가 제각각이라 올릴 자리를 찾다 외부 단편화가 쌓이고, 큰 세그먼트는 일부만 필요해도 통째로 오가야 한다. 그래서 실제 가상 메모리는 페이징이나 페이지드 세그멘테이션 위에서 구현한다.

페이징과 세그멘테이션 비교

페이징:

flowchart LR
  pl["[페이지 번호 p | 오프셋 d]"] -->|"페이지 테이블[p] = 프레임 f"| pp["물리 주소 = f × 페이지 크기 + d"]

세그멘테이션:

flowchart LR
  sl["[세그먼트 번호 s | 오프셋 d]"] -->|"세그먼트 테이블[s] = (base, limit)"| sp["d #lt; limit 이면 base + d"]

Segmentation fault는 세그멘테이션과 상관있나

이름만 남았다. 세그먼트의 limit을 넘는 접근을 잡던 시절의 용어이고, x86-64 Linux는 세그먼트를 사실상 쓰지 않고(base 0인 평면 모델) 페이징만으로 메모리를 보호한다. 지금의 segfault는 페이지 테이블에 매핑이 없는 주소(NULL 역참조, 해제된 메모리, 스택 끝의 가드 페이지)나 권한을 어긴 접근(읽기 전용인 문자열 리터럴에 쓰기, 실행 금지 페이지 실행)에서 MMU가 페이지 폴트를 내고, 운영체제가 이를 정상 요청이 아니라고 판정해 SIGSEGV를 보내는 것이다. 아직 메모리에 올라오지 않은 페이지에 접근하는 정상 페이지 폴트와 하드웨어 경로는 같고 판정만 다르다(가상 메모리의 「페이지 폴트 처리」 1단계). 디버깅은 C 디버깅 도구에 있다.

페이지드 세그멘테이션 (Paged Segmentation)

세그멘테이션과 페이징을 합친 방식이다. 세그먼트 하나를 여러 페이지로 구성한다.

• 세그먼트 테이블 엔트리가 세그먼트의 시작 주소 대신 그 세그먼트의 페이지 테이블 시작 주소를 가진다. 즉 세그먼트마다 페이지 테이블이 있다.
• 메모리에는 페이지 단위로 올라가므로 할당(외부 단편화) 문제가 사라진다.
• 공유·보안처럼 의미 단위로 해야 하는 일은 세그먼트 테이블에서 처리한다.

주소 변환은 모두 하드웨어(MMU)가 하며, 이 과정에 운영체제는 관여하지 않는다. 운영체제는 페이지 폴트처럼 메모리에 없는 페이지를 참조할 때 개입한다(가상 메모리). MMU의 역할(재배치·공유·보호)과 보호 필드는 캐시 메모리와 MMU에 있다.

커널 메모리 할당: 버디와 슬랩

사용자 프로세스의 메모리는 페이징으로 흩어 놓아도 되지만, 커널은 장치 I/O 버퍼처럼 물리적으로 연속된 메모리가 필요하고 수십~수백 바이트짜리 작은 구조체를 아주 자주 만들고 버린다. 그래서 커널은 별도 할당자를 쓴다.

리눅스는 페이지 단위는 버디 할당자로, 그 위의 작은 객체는 슬랩 계열 할당자(지금은 SLUB)로 나눠 준다. /proc/buddyinfo, /proc/slabinfo(또는 slabtop)로 상태를 볼 수 있다.

핵심 정리

• CPU는 논리 주소를 보고, MMU가 실행 시간에 물리 주소로 바꾼다(base + offset, limit으로 보호).
• 연속 할당은 단편화가 문제다. 외부 단편화는 컴팩션으로 해결할 수 있지만 비싸다.
• 페이징은 같은 크기로 잘라 외부 단편화를 없애고, TLB로 주소 변환을 빠르게, 다단계 테이블로 테이블 공간을 줄인다.
• 세그멘테이션은 의미 단위라 공유·보호에 유리하지만 외부 단편화가 생기고, 페이지드 세그멘테이션이 둘의 장점을 합친다.

관련 노트: 가상 메모리, 캐시 메모리와 MMU, 프로세스와 스레드, 포인터와 메모리