/untyped

가상 메모리 이야기

2025-10-17

태그: dev essay

모든 프로그램은 메모리가 필요하다.

현대 컴퓨터는 폰 노이만 아키텍쳐를 기반으로 한다. 모든 계산은 CPU에서 이루어지는데, 프로그램과 데이터는 메모리에 저장되어 있다. 그래서 계산을 하려면 이걸 레지스터까지 가져와야 한다. 혹은 반대로, CPU가 계산한 결과를 현실 세계에 반영하려면, 레지스터로부터 출발해서 메모리(혹은 디스크)까지 가지고 가야 한다. 이 과정을 더 효율적으로 하기 위해서 이 사이에 수많은 보조적인 단계가 생기게 되었고, 그 결과 우리가 아는 메모리 계층구조(Memory Hierarchy)가 탄생하게 되었다.

CPU (register) <-> L1 Cache <-> L2 (<-> L3) <-> RAM <-> SSD or HDD

프로그램마다 필요한 메모리 크기가 다르다. 어떤 애는 몇 메가만 있어도 충분하지만 컴파일러를 컴파일하거나 커다란 데이터를 분석하는 등의 작업에는 수십, 수백, 수 테라의 메모리가 필요할 때도 있다. 하지만 물리적인 메모리(RAM)의 용량은 한계가 있다. 그리고 운영체제는 수많은 프로그램들을 동시에 실행해야 한다. 아무리 메모리를 잘 쪼개서 프로그램마다 잘 할당한다고 해도, 어떤 프로그램이 얼만큼의 메모리가 필요한지를 항상 알아낼 수는 없기 때문에 (정지 문제), 이는 꽤 골치아프다.

모든 컴퓨터 과학 문제는 새로운 수준의 추상화를 추가해서 해결할 수 있다1. 가상 메모리는 이러한 문제를 해결하기 위한 추상화로, 모든 프로세스에게 자기만의 독립적인 가상 주소 공간을 제공한다. 이 추상화 덕분에 커널은 진정한 의미의 동시성을 얻을 수 있었고, 더 나아가 메모리 보호(다른 프로세스의 가상 메모리에 접근 불가), 효율적인 메모리 관리, 그리고 스왑 공간을 통해 실제 필요한 메모리가 물리적인 메모리보다 더 큰 프로그램도 실행할 수 있는 등의 추가적인 이득도 얻었다.

현대의 가상 메모리 기법은 소프트웨어와 하드웨어 모두의 도움을 받는다. 소프트웨어 적으로는 가상 주소의 구성이라던지 페이징 기법, 페이지 교체 알고리즘 등이 있고, 하드웨어 적으로는 MMU(Memory Management Unit; 가상 주소를 물리 주소로 변환하는 걸 도와줌)이나 TLB(Translation Lookaside Buffer; MMU를 위한 특수한 캐시) 등이 있다. 1950년대 초창기 컴퓨터에는 현대적인 의미의 동시성이라는 개념은 없었고, 배치 처리(Batch Processing)를 통해서 여러 프로그램을 순차적으로 하나씩 실행할 수는 있었다. 그러다가 고정 파티션과 같은 제한적인 멀티 태스킹이 도입되기 시작했고, 역사에 따르면 여러 다양한 시도가 있었지만 각각 발목을 잡는 문제들, 예를 들면 심각한 단편화(Fragmentation)라던지 성능의 이슈라던지 하는 것들이 있었고, 이를 해결하기 위해서 수많은 연구자와 개발자들이 고군분투한 끝에 1970년대에 들어서는 지금의 우리가 아는 가상 메모리 시스템의 기본이 잡혔다.

아무튼간에 프로그램이 보는 모든 메모리 주소는 가상 메모리 주소이다. 좀더 정확히는, MMU의 도움을 받아 64비트 플랫폼 위에서 구현된 페이지 기반 가상 메모리 시스템에서, 메모리 주소는 일반적으로 다음과 같은 인코딩을 갖는다.

예를 들어, malloc으로 얻은 메모리 주소가 0x5555555552a0라면, 이중에서 상위 52비트인 0x555555555는 페이지 번호이고 하위 12비트인 0x2a0은 페이지 오프셋을 나타낸다. MMU는 이 인코딩에 따라 먼저 캐시(TLB)에 이 페이지 번호를 본 적이 있으면 그걸 가져다 쓰고, 없으면 페이지 테이블을 뒤져서 PTE를 찾은 다음 여기 든 정보를 이용해서 실제 물리 메모리의 주소 정보를 계산하여 돌려준다.

좀 더 구체적으로 보면 MMU는 페이지 테이블 엔트리 정보를 이용해서 주소를 변환하고, 메모리 구역의 권한을 검사하고, 페이지 폴트가 발생하면 OS 인터럽트를 발생시키고, TLB 정보를 효율적으로 관리하는 등의 작업을 보조한다. 이런 걸 커널(소프트웨어) 레벨에서 지원해도 되지만 해야 할 일이 명확한 덕분에 마치 FPGA와 같이 특화된 하드웨어의 도움을 받아 훨씬 더 효율적이고 빠르게 관리할 수 있는 것이다.

PTE는 다음과 같은 정보들을 갖고 있다:

페이지 테이블은 보통 커널에 의해서 관리되며 RAM의 한 구역을 차지한다. 근데 앞서 말했듯 64비트 플랫폼에서 페이지 테이블 번호가 52비트인데, 이 크기만큼을 단순하게 다 할당하면 \(2^{52} \times 8B = 32PB\) (여기서 8바이트는 PTE의 크기)라는 엄청나게 큰 메모리가 필요하게 되고 이러면 가상 메모리를 도입한 의미가 없어진다. 그래서 실제로는 52비트를 다 쓰지 않고, 추가로 Multi-Level Page Table이라는 걸 도입해서 필요한 만큼만 로딩해서 쓴다. 현재 x86-64에서는 주로 아래와 같은 4단계의 페이지 테이블을 이용한다.

이런 식으로 52비트 중 일부인 48비트(9비트 4개 + 12비트)만 쓰고 나머지는 나중을 위해 예약해두었다. 남은 16비트는 최상위 비트의 부호를 확장한다. 48비트만 쓰더라도 표현 가능한 가상 메모리 공간의 크기가 256TB씩이나 되어서 당분간은 걱정이 없다. 더 큰 가상 메모리 공간이 필요하게 되면 페이지 번호에 쓰일 비트를 더 늘리고 페이지 테이블 단계를 하나 더 추가하거나 하면 된다. 실제로 인텔에서는 57비트 주소 체계와 5단계 페이지 테이블을 통해 최대 128PB 메모리를 표현할 수 있는 주소 체계를 시도해보고 있다.

아무튼 이런 배경으로 현대의 64비트 플랫폼 Unix 기반 OS에서 돌아가는 프로그램은 독립적으로 최대 256TB의 연속적인 가상 메모리 공간을 갖게 되었다. 보통 이걸 반으로 잘라서 128TB는 커널이 쓰고 나머지 절반은 사용자 프로그램이 쓴다. 그래서 예를 들면 데비안 문서를 보면 “64비트 유저랜드에서는 프로세스마다 최대 128TiB의 가상 주소 공간을 갖게 된다”는 설명이 있다.

그런데 이렇게 연속적으로 만든 가상 메모리 공간과 매칭되는 물리 메모리 공간은 당연하지만 크기가 제한적이다. 물리적인 한계도 있지만 커널, BIOS, 펌웨어, 페이지 테이블 등 많은 부수적인 정보들이 RAM에 함께 위치하기 때문이다. 그래서 언젠가는 메모리가 부족한 상황이 올 수 밖에 없다. 이때는 어떻게든 페이지(프레임)를 잠깐 다른 데로 내보내야 하는데, 이렇게 “어떤 페이지를 내보낼지” 결정하는 것을 페이지 교체(Page Replacement) 알고리즘이라고 하며 다음과 같은 것들이 있다:

이 알고리즘들을 왜 “페이지 교체”라고 부를까? 실제로는 물리 메모리가 꽉 차서 발생하고 물리 메모리 관리 단위인 프레임이 교체되는데 말이다. 크게 두 가지 이유가 있을 것이다. 대부분 “논리적으로 메모리가 어떻게 쓰이고 있는지”를 가지고 판단하는데, 이걸 확인하는 방법은 커널이 프레임이 아니라 페이지를 살펴보는 수 밖에 없다. 그리고 페이지는 프레임과 매칭되어 있어서 페이지를 비우면 결국 프레임도 비워진다. 아무튼 간에, 이렇게 메모리가 부족하게 되면 페이지를 스왑 공간으로 방출해서 잠깐 저장해두고, 나중에 필요할 때 다시 로딩하게 된다.

그리고 물리 메모리 공간은 비연속적이다. 동시성을 위해 수많은 프로그램들이 메모리에 같이 올라와 있는데, 가상 메모리와 물리 메모리를 페이지와 프레임이라는 덩어리로 관리하기 때문에 페이지(프레임) 크기인 4KB 만큼 엇갈려서 배치되기 때문이다. “동시성”은 프로그램 조각을 번갈아서 실행하는 (Interleaving) 방식으로 구현되어 왔다. 하나의 프로세스가 CPU를 점유해서 실행되다가 일정 시간이 지나면 다른 프로세스에게 차례를 넘긴다. 근데 결국 나중에 다시 실행되어야 하니까, 일단 하던 작업을 다 정리해서 어딘가에 잠시 옮겨두고, 다음 차례에 실행될 프로세스가 해야 할 작업을 어딘가에서 가져와 메모리에 실어야 한다. 이 작업을 흔히 컨텍스트 스위칭(Context Switching) 이라고 부른다.

페이지 기반 가상 메모리 덕분에 진정한 의미의 동시성이 가능해진 이유 중 하나가 바로 효율적인 컨텍스트 스위칭이다. 페이지 테이블 덕분에 컨텍스트 스위칭을 할 때 전체 메모리를 조작할 필요가 없다. 역사적으로 페이지 테이블 포인터를 CR3 레지스터에 담아왔는데, 컨텍스트를 스위칭할 때 이 레지스터 값만 바꾸면 되므로 매우 효율적이다. 그리고 일관된 캐시 데이터를 위해 TLB도 비워줘야 하는데, 다 비워버리면 그 다음 프로세스가 실행될 때 모든 메모리 작업에 TLB 미스가 나기 때문에 너무 비효율적이다. 그래서 현대의 TLB는 PCID(Process Context ID) 또는 ASID(Address Space ID) 라고 불리는 컬럼을 추가하여 각 캐시 항목마다 “어떤 프로세스가 사용 중인지”도 같이 기록한다. 덕분에 컨텍스트 스위칭 시에 캐시 전체를 비우지 않아도 된다. 만약 이런 페이지 기반의 가상 메모리 시스템이 없다면, 컨텍스트 스위칭에 말 그대로 수 초가 걸릴 수도 있을 것 같다2.

정리하면, malloc을 호출해서 메모리에 어떤 값을 쓰는 다음 코드는:

int *ptr = malloc(sizeof(int));
*ptr = 42;

대충 다음과 같은 단계를 따라간다고 볼 수 있다:

  1. 커널이 가상 주소를 생성한다.
  2. 48비트 주소 시스템에 따라 가상 주소를 VPN과 Offset으로 분해한다.
  3. 프로세스 아이디와 VPN을 가지고 TLB를 쿼리해서 최근에 조회된 적이 있는지 살펴본다. 있으면 그걸 가져다 쓴다.
  4. 없으면 TLB 미스가 발생하고 페이지 테이블을 직접 조회한다.
    1. 먼저 CR3 레지스터를 통해서 PML4 주소를 따라간다.
    2. PML4 -> PDP -> PD -> PTE 순으로 차례대로 접근해서 PTE를 얻는다.
  5. MMU가 이 PTE 항목을 검증하고 물리 주소를 만든다.
    1. Valid 하면 메모리에 있으니 바로 쓰기 시도를 하고, 아니면 페이지 폴트를 일으켜서 메모리에 적재한다.
    2. 모드와 권한도 확인한다. 쓰기 가능하고 사용자 모드 접근이 가능하면 계속 진행한다.
    3. 유효하다고 판단되면 PTE에 있는 PFN을 이용해 물리 주소를 계산한다.
    4. 여기까지 검증한 최신 내용을 TLB에다가 업데이트한다.
  6. 이제 물리 주소를 가지고 물리 메모리에 접근할 수 있다. 여기에 값을 쓴다.
  7. 값을 썼기 때문에 PTE가 업데이트 된다. Dirty 비트를 수정한다. TLB도 업데이트 된다.

여기까지 가상 메모리에 대해서 아는 내용을 정리하며 마구잡이로 적어 보았다. 이제는 이걸 바탕으로 생기는 다양한 엔지니어링 프랙티스에 대해서 좀더 얘기를 해볼까 한다.

페이지 크기 튜닝

워크로드에 따라 페이지 크기를 바꿀 수 있다.

페이지 크기가 커지면 페이지가 한번에 커버하는 메모리 영역이 커지므로, 전체 페이지 테이블 크기는 줄어들고 대용량 데이터를 처리하는데 유리해지면서 TLB 미스가 덜나지만, 내부 단편화가 증가하고 페이지 폴트 시에 비용이 증가하게 된다. 반면 페이지 크기가 작아지면 더 작은 단위로 (Find-Grained) 메모리를 할당하므로 내부 단편화가 줄어들어 메모리 낭비를 덜하게 되고 더 세밀하게 메모리를 관리할 수 있지만, 하나의 페이지가 커버하는 영역이 작아져서 페이지 테이블 크기가 말 그대로 폭증하고 이로 인해 TLB 미스가 증가하고 디스크 I/O에 비효율이 발생한다. 이렇듯 트레이드 오프가 있긴 하지만, 현대적인 컴퓨팅 환경에서는 주로 페이지 크기를 늘리는 방향만을 고려한다.

그럼 얼마나 늘릴 수 있을까? 일단 리눅스에는 Huge Pages라는 기능을 지원하는데, 보통 2MB(=21비트 오프셋) 또는 1GB(=30비트 오프셋) 두 가지 크기를 지원한다. /sys/kernel/mm/hugepages/ 디렉토리에 hugepages-2048kB 과 hugepages-1048576kB 디렉토리가 있는데 여기에 각각 2MB와 1GB의 페이지 크기와 관련된 설정을 담고있다. 이 설정 파일을 직접 쓰거나 아니면 sysctl 커맨드를 이용해서 Huge Pages 관련 설정을 정적으로 설정할 수도도 있고 (HugeTLB), 아니면 THP(Transparent HugePages)라는 기능을 통해 커널이 동적으로 관리하도록 할 수도 있다.

HugeTLB와 THB는 정적/동적인 것 외에도 몇 가지 차이점들이 있다.

  HugeTLB THP
할당 방식 부팅시 또는 런타임에 미리 예약 (Static) 필요할 때 자동으로 할당 (Dynamic)
누가 켜나 서버 관리자, 개발자 커널이 알아서 관리함
메모리 유연성 절대로 스왑되지 않음. 다른 용도로 사용 불가 필요없으면 자동으로 일반 페이지로 전환 가능
어플리케이션 수정 필요한지? ㅇㅇ. hugetlbfs 마운트 및 명시적인 사용이 필요함. 없음, 그냥 켜기만 하면 됨.
할당 보장 미리 예약되어 있어서 항상 사용 가능 메모리 상황에 따라서 실패할 수 있음
장점 일관되고 예측 가능, 메모리 압축 오버헤드 없음 켜기만 하면 되고 관리할 필요가 없음, 메모리를 유연하게 쓸 수 있음
단점 메모리가 고정되어서 유연하지 않음, 메모리가 갑작스럽게 가득 찰 수 있음, 소스 코드 수정해야 됨 메모리 압축 오버헤드가 있고, 예측 불가능한 지연이 발생할 수 있음.

그래서 언제 뭘 써야할까? 선조들의 지혜는 다음과 같다.

정말 특수한 워크로드에서 고성능이 필요한 경우가 아니라면, 보통은 그냥 기본 설정을 가져다 쓰기만 해도 충분하다. 만약 성능을 극한까지 쥐어짜내야 하는 경우가 오면 한번 쯤 이 설정을 들여다보면 되겠다.

COW (Copy-on-Write)

다음 프로그램을 보자.

int main() {
    int* data = malloc(1000000000 * sizeof(int));
    for (int i=0; i<1000000000; i++) data[i] = i*i;

    pid_t pid = fork();
    if (pid == 0) { // child
        printf("%d\n", data[0]);
    } else { // parent
        printf("%d\n", data[0]);
    }
}

큰 데이터 덩어리를 할당한 다음 프로세스를 fork 떠서 자식과 부모 프로세스로 분화되었다. 가상 메모리 시스템에서는 프로세스마다 가상 메모리 공간이 분리되어 있어서 서로의 메모리에 접근 불가능하므로, 얼핏 생각하기에 4GB(10억개의 정수) 메모리를 점유한 프로세스가 두 개 생겨야 하니까 총 8GB의 메모리를 쓰게 될 것 같다. 하지만 실제로는 4GB만 쓴다! 왜냐하면 두 프로세스가 모두 데이터를 읽기만 하기 때문이다. 실제로 메모리 공간이 분리되는 시점은 쓰기가 발생할 때인데, 그래서 이런 최적화를 COW(Copy-on-Write)라고 부르며, 데이터를 쓰는 시점에 복사가 이루어진다는 뜻이다.

그래서 예를 들어 다음 코드에서는 예상한 대로 메모리를 8GB 쓰게 된다.

int main() {
    int* data = malloc(1000000000 * sizeof(int));
    for (int i=0; i<1000000000; i++) data[i] = i*i;

    pid_t pid = fork();
    if (pid == 0) { // child
        data[0] = 99;  // write!
    } else { // parent
        printf("%d\n", data[0]);
    }
}

이때는 대략 다음과 같은 과정을 거친다.

  1. malloc() 을 통해서 가상 메모리를 할당할 때, 이 구역의 권한은 Read-Write이다.
  2. fork()가 호출되는 순간, 모든 메모리의 권한이 Read-Only로 바뀌고, 부모와 자식 프로세스의 가상 메모리 페이지들은 서로 같은 물리 메모리 주소를 가리키게 된다.
  3. 자식이 읽기만 하는 것은 그래서 전혀 문제가 없다. Read-Only 권한이 있으니까.
  4. 그런데 자식이 데이터를 쓰려고 하는 순간, MMU는 Write 권한이 없다는 사실을 발견하고 페이지 폴트를 발생시킨다.
  5. 커널이 새로운 페이지와 프레임을 할당하고, 데이터를 복사한 다음, 쓰기를 시도한 프로세스의 페이지 테이블 권한을 Read-Write로 업데이트 하고 쓰기 작업을 완료한다.

한 마디로 정말 쓰기 작업이 필요할 때까지 최대한 불필요한 복사를 미루는 것이다. 그래서 멀티 프로세스로 공유된 데이터를 읽기만 하면 아주 효율적이다. 하지만 어떤 프로그래밍 언어에서는 데이터를 읽기만 하는 작업이 없는 경우도 있어서 주의를 요한다.

캐시 친화적인 프로그래밍

TLB는 하드웨어 캐시라서 히트한다면 1 싸이클 정도로 엄청나게 빠르다. CPU 캐시와 마찬가지로, 메모리에 저장된 것이 데이터일 수도 있고 코드일 수도 있어서, 이를 위해서 iTLB(for Instruction)과 dTLB(for Data)로 나뉘기도 하고, L1, L2와 같은 레벨이 추가되기도 한다. 그리고 TLB 미스가 발생하면 RAM에 접근해야 하는 오버헤드가 발생하는데, 이를 미스 패널티라고 한다.

TLB 히트율은 통상적으로 95-99% 라고 한다. 이게 얼마나 중요한 성능 개선인지 한번 알아보자. 미스 패널티를 대략 100 싸이클이라고 하자. TLB 히트율을 98%라고 하면 평균적인 메모리 접근 시간을 다음과 같이 계산해볼 수 있다.

그러니까 98%의 히트율을 갖는 TLB가 있으면 메모리 접근 성능이 거의 두배가 좋아진다. 10, 20% 이런 수준이 아니라 엄청난 성능 개선이다.

L1, L2 캐시 히트는 더 드라마틱하다. 얘는 맵핑 방식이 좀더 복잡하긴 한데, 아무튼 중요한 것은 데이터가 캐시에 있고 없고는 엄청나게 큰 성능 차이를 보인다는 점이다. L1 캐시 속도를 4 싸이클, 메모리 접근을 100 싸이클이라고 하자. L1 캐시 히트율은 통상적으로 95-98% 라고 하는데, 역시 히트율 98%를 가정하면:

98%의 히트율을 갖는 L1 캐시가 있으면, 성능이 약 17배 좋아진다. 심지어 이건 L1의 속도를 느리게(4), 메모리 속도를 빠르게(100) 가정한 것인데도 그렇다. 두 메모리의 속도가 더 차이나면 성능 갭은 더 벌어질 것이다.

그러니까 우리가 아는 지역성, 즉 최근에 쓰인 데이터(메모리) 영역은 금방 다시 쓰이며, 그 데이터와 인접한 다른 데이터들도 함께 쓰일 확률이 높다는 관찰은 정말 중요한 것이다. 덕분에 메모리 접근 속도를 빠르게 할 수 있는 다양한 최적화를 고려해볼 수 있는데, 종종 시간 복잡도를 압도하는 수준으로 성능이 개선되기도 한다.

이런 최적화 방법에는 여러가지가 있다.

TLB 지역성 활용

같은 페이지 내에서 오프셋을 통해서 데이터를 연속적으로 접근하게 되면, 서로 다른 페이지 간의 데이터를 접근하는 것보다 TLB 히트가 많아져서 최적화를 할 수 있다. 가장 많이 알려진 경우는 바로 2차원 배열을 행 우선으로 접근할지 열 우선으로 접근할지 일 것이다.

// TLB Miss 너무 많음 - 열 우선 접근
for (int col = 0; col < SIZE; col++) {
    for (int row = 0; row < SIZE; row++) {
        matrix[row][col];
    }
}

// TLB Hit 높음 - 행 우선 접근
for (int row = 0; row < SIZE; row++) {
    for (int col = 0; col < SIZE; col++) {
        matrix[row][col];
    }
}

연속적인 메모리 구역에 접근할 때 어떤 식으로 접근하는지 한번 쯤 고민해보면 좋다.

페이지 폴트를 줄이도록 힌트주기

어떤 메모리가 계속해서 쓰일 거라는 사실을 알면, madvise() 시스템 콜을 이용해서 힌트를 줄 수 있다.

void* ptr = malloc(SIZE);
madvise(ptr, SIZE, MADV_WILLNEED);

MADV_WILLNEED 플래그는 ptr 가상 주소 공간에 임시로 더 높은 우선순위를 부여한다. 그래서 이미 메모리에 있으면 되도록 방출되지 않게 해준다. 이미 메모리에 있는 페이지들은 즉시 프로세스에 맵핑시켜서 페이지 폴트 과정을 거치는 오버헤드를 줄인다.

메모리를 페이지 크기에 알맞게 할당하기

예를 들어 디폴트 페이지 크기인 4KB를 사용하는 플랫폼에서 애매하게 4100 바이트를 할당한다거나 해서 두 페이지에 걸치도록 메모리를 할당하기 보다는, 차라리 데이터 구조를 좀 다이어트해서 4KB 안에 들어오도록 하는 것이 좋다. 그러면 가상 메모리 뿐만 아니라 물리적인 메모리 공간에서도 연속적인 순차 접근이 가능해지고 TLB 히트도 누릴 수 있다.

그리고 페이지 크기와 비슷한 만큼의 메모리가 필요하면 posix_memalign() 시스템 콜을 고려해보는 것도 하나의 방법이다. 예를 들어 다음과 같이

char *ptr = malloc(4090);

요렇게 메모리를 할당한 경우, 얼핏 생각하기엔 4KB보다 작은 4090 바이트를 할당했으니 한 페이지 안에 들어갈 것 같다. 그럴 수도 있고 아닐 수도 있다. malloc의 문제점은 할당된 메모리가 어디서 시작하는지를 모른다는 점이다. 즉, 4KB보다 작은 4090 바이트의 메모리가 한 페이지 안에 할당될지, 아니면 애매하게 두 페이지에 걸쳐서 할당되는지 알 수 없다.

이럴 때는 다음과 같이 할 수 있다:

char *ptr;
posix_memalign((void**)&ptr, 4096, 4090);

페이지 경계인 4KB에 맞춰서 4090 바이트 크기의 메모리를 할당해달라는 의미이다. 이러면 정확하게 하나의 페이지 경계에 맞춰서 메모리가 할당되어서 페이지 폴트가 1번만 발생한다.

메모리 프리페치

데이터 구조는 메모리 레이아웃을 기준으로 크게 두 종류로 나눌 수 있다.

이때까지 살펴본 캐시 친화적인 프로그래밍은 주로 배열 기반 데이터를 위한 것이다. 얘네들은 메모리를 덩어리 째로 가져오면 지역성 효과를 제대로 볼 수 있어서 캐시 히트를 마음 껏 누릴 수 있다. 반면에 비연속적이라고 분류된 데이터 구조들은 대부분 “다음 원소”를 알아 내려면 특정 메모리 영역을 뒤져야 한다. 그래서 메모리를 덩어리째 가져와도 그 근처에는 다음 원소가 없을 수 있고, 마찬가지로 (특히 전체를 훑을 때) 방금 쓰인 주소 값은 다시 쓰일 일이 잘 없다. 한마디로 지역성이 깨진다.

그러면 비연속적인 메모리 레이아웃을 가진 데이터 구조는 어떻게 캐시 친화적인 프로그래밍을 할 수 있을까?

모든 경우에 가능한 것은 아니지만, 이 경우에도 방법은 있다. Arm 컴파일러에는 __builtin_prefetch 라는 명령어가 있는데, 이걸 통해서 데이터를 미리 페칭하여 캐시 미스 레이턴시를 줄일 수 있다. 다음 접근할 원소의 순서가 정해져 있고, 하나의 원소에 대해서 해야할 작업이 크다면, 활용을 고민해볼 수 있다. 물론 이걸 아무 생각없이 써버리면 캐시에 의미 없는 데이터만 꽉 차버려서 안하느니만 못하게 되니 전략적인 접근이 필요하다.

이와 관련해서 그래프 탐색 시에 메모리 프리페치를 이용해서 엄청난 성능 개선을 얻은 사례가 있는데, 이는 다음 기회에.

time 커맨드가 알려주는 것들

프로그램을 프로파일링하는 방법 중 하나로 \time -v <command> 명령어가 있다. 예를 들어 \time -v ls 를 실행하여 ls 커맨드를 프로파일링 하면 다음과 같은 결과가 나온다.

	Command being timed: "ls"
	User time (seconds): 0.00
	System time (seconds): 0.00
	Percent of CPU this job got: 100%
	Elapsed (wall clock) time (h:mm:ss or m:ss): 0:00.00
	Average shared text size (kbytes): 0
	Average unshared data size (kbytes): 0
	Average stack size (kbytes): 0
	Average total size (kbytes): 0
	Maximum resident set size (kbytes): 2560
	Average resident set size (kbytes): 0
	Major (requiring I/O) page faults: 0
	Minor (reclaiming a frame) page faults: 115
	Voluntary context switches: 2
	Involuntary context switches: 1
	Swaps: 0
	File system inputs: 0
	File system outputs: 0
	Socket messages sent: 0
	Socket messages received: 0
	Signals delivered: 0
	Page size (bytes): 4096
	Exit status: 0

이제 우리는 여기 나오는 자세한 내용 중에서 특히 메모리 사용량과 관련된 항목에 대해서 조금 더 잘 이해할 수 있다. 예를 들면…

주소는 항상 짝수

커널이 돌려주는 모든 메모리 주소는 가상 메모리 주소라는 것을 이제 알 것이다. 그리고 이 주소는 VPN과 Offset으로 구성되어 있다. 하지만 이것 외에도 추가적인 요구사항이 있는데 바로 정렬(Alignment)이다. 정렬을 알려면 일단 워드(Word)의 개념을 먼저 알아야 한다.

모든 프로세서는 데이터를 자연스럽게 처리하는 기본 단위가 있는데 이걸 워드(Word)라고 한다. 32비트 플랫폼에서는 4바이트(=32비트), 64비트에서는 8바이트(=64비트)가 기본이다3.

C 표준에서는 이를 따라, malloc이 리턴하는 메모리는 모든 표준 데이터 타입에 대해서 적절하게 정렬된 메모리를 돌려주도록 강제한다. 그래서 8바이트 (32비트 플랫폼) 또는 16바이트 (64비트 플랫폼) 경계로 정렬된 메모리를 돌려준다. 이렇게 플랫폼의 기본 워드의 두배 크기로 정렬하는 이유에는 여러가지가 있다.

결론적으로 malloc이 돌려주는 가상 메모리 주소는 항상 정렬 요구사항을 만족한 값이다. 다르게 말하면 모든 메모리 주소는 짝수, 정확히는 8의 배수 (32비트 플랫폼) 또는 16의 배수 (64비트 플랫폼) 라는 말과 같다. 이 말은 곧 모든 메모리 주소의 최하위 비트는 항상 0이라는 뜻이다. 어떤 언어에서는 이 성질을 이용해서 메모리 주소와 정수를 효율적으로 구분하기도 한다. 사실 이 글을 쓰게 된 동기 중 하나가 “진짜 메모리 주소는 항상 0으로 끝나는건가?” 라는 사소한 궁금증이었다.

모던 컴퓨팅 환경의 근간이 되는 페이지 기반 가상 메모리는 이렇듯 하드웨어와 소프트웨어의 협력을 통해서 구현되는 엄청난 시스템이었다. 다음에는 이거보다 한 단계 위의 추상화 레벨, 즉 어플리케이션 레벨에서 메모리를 관리하는 방법에 대해서 써봐야지.

  1. “We can solve any problem by introducing an extra level of indirection.” 이른바 FTSE (Fundamental Theorem of Software Engineering) 이라고 불리는 내가 좋아하는 문구다. ↩

  2. 예전에 게임 업계에 있을 때, 플레이어들이 “랙”을 인지하는 게 보통 레이턴시가 100ms를 넘어갈 즈음부터 이고 200ms를 넘으면 확실하게 랙임을 인지한다는 얘기를 들었었는데, 그런 의미에서 수 초의 컨텍스트 스위칭은 동시성이라고 부를 수 없는 수준이 아닐까. ↩

  3. 인텔은 1 워드를 16비트(2바이트)로 규정하고 여기에 배수로 Double Word (DWORD; 32비트)와 Quad Word (QWORD; 64비트)를 정의해놨다. 이건 원래 x86 아키텍쳐가 16비트 프로세서로 시작했기 때문에 생긴 하위 호환성 같은 것이라고 한다. ↩