[1000줄 OS 구현하기] 메모리 할당

2025. 2. 11. 17:04ㆍCS/OS

 

 

메모리 할당 | OS in 1,000 Lines

 

operating-system-in-1000-lines.vercel.app

 

1. 이론

 

가. 가상 메모리 (Virtual Memory)

 

사용자에게 보조 메모리의 총량에 해당하는 대형 주소 공간을 제공.

 

훨씬 더 큰 공간의 보조 메모리를 가상의 메인 메모리로 사용하는 방식.

 

가상의 주소를 물리 주소와 매핑한다.

 

CPU는 가상의 주소를 사용한다.

 

가상 주소 공간은 메모리 관리 장치(MMU)에 의해서 물리 주소로 변환된다. (address translation)

 

이 덕분에 프로그래머는 가상 주소 공간상에서 프로그램을 짜게 되어 프로그램이나 데이터가 주메모리상에 어떻게 존재하는지를 의식할 필요가 없어진다.

 

 

💡swap 동작 순서

  1. 메인 메모리에서 내려갈 페이지의 내용을 임시 버퍼에 복사
  2. 보조 메모리의 해당 페이지 영역에 버퍼의 내용을 기록 (write-back)
  3. 새로운 페이지를 메인 메모리로 로드
  4. 페이지 테이블 업데이트

 

나. 페이지

 

  • 블록(Block)
    : 기억 공간을 나누는 단위
  • 페이지(Page)
    : 고정된 크기의 블록으로, 가상 메모리를 이 페이지들로 나뉜다.
    : 각각의 페이지는 메인 메모리의 물리적 주소로 매핑된다.
    : 이 매핑은 페이지 테이블이라는 데이터 구조를 통해 관리된다.

 

운영체제 페이지 크기
Windows 64KB
Unix 1KB

 

 

가상 주소는 페이지 번호와 오프셋으로 나누어지며, 페이지 테이블은 페이지 번호를 사용하여 해당 페이지의 물리 주소를 찾아낸다.

 

이렇게 찾아낸 물리 주소와 처음에 주어진 오프셋을 합쳐서 최종적인 물리 주소를 얻게 된다.

 

페이지 매핑 외에도 가상 주소를 물리 주소로 변환하는 다른 방법이 존재함.

 

  • 어소시에이티브 메모리(Associative Memory)
    : 특정 '키'에 대한 '값'을 바로 찾아낼 수 있는 특성을 가진 메모리.
    : CPU가 특정 주소를 찾기 위해서는 그에 상응하는 키를 메모리에 보내고, 메모리는 그 키에 일치하는 워드를 반환합니다.

 

메모리 방식 장점 단점
어소시에이티브 메모리 빠른 액세스 시간 (키를 통해 워드를 직접 찾아냄) 메모리 공간이 효율적으로 사용되지 않음 (각 워드는 고유한 키를 가져야 함)
페이지 테이블 메모리 공간을 효율적으로 활용 (동일한 크기의 페이지로 나누어 관리함) 가상 주소를 물리 주소로 변환하는 데 시간이 걸림 (페이지 테이블을 조회하고, 그 결과를 바탕으로 최종적인 물리 주소를 계산해야 함)

 

다. 페이지 교체 (Page Replacement)

 

블록들이 모두 사용 중이면서 새로운 페이지가 필요할 때. → page fault

 

페이지 교체라는 방법을 사용.

 

현재 메모리에 올라와 있는 페이지 중 하나를 선택하여 보조 메모리(디스크 등)로 이동시킨다.

 

이러한 페이지 교체를 위한 알고리즘은 여러 가지가 있다:

 

페이지 교체 전략 설명
FIFO (First-In, First-Out) 가장 먼저 메모리에 로드된 페이지를 교체합니다.
LRU (Least Recently Used) 가장 최근에 사용되지 않은 페이지를 교체합니다.
LFU (Least Frequently Used) 가장 적게 사용된 페이지를 교체합니다.
OPT (Optimal) 미래에 가장 오랫동안 사용되지 않을 페이지를 교체합니다. 이 방법은 모든 페이지 참조 정보를 알고 있어야 하므로 실제 시스템에서는 구현이 어렵습니다.

 

운영체제는 복수의 페이지 교체 알고리즘을 사용한다.

 

순수 LRU를 구현하면 오버헤드가 크다.

  • 모든 메모리 접근을 추적해야 함
  • 각 페이지마다 마지막 참조 시간을 기록하고 유지해야 함
  • 페이지 교체 시 모든 페이지의 참조 시간을 비교해야 함

 

실제 운영체제에서는 LRU의 근사치인 CLOCK 알고리즘 등이 사용된다.

  • 각 페이지에 단순한 참조 비트(Reference Bit)만을 사용하여 최근 사용 여부를 기록
  • 원형 구조(Clock hand)를 사용해 페이지들을 순회하면서, 참조 비트가 0인(0에 가장 가까운) 페이지를 교체 대상으로 선택하는 방식으로, LRU의 특성을 근사한다.
  • 이 방식은 구현이 단순하고 오버헤드가 적어 실제 운영체제에서 자주 사용된다.

 

라. 메모리 관리 하드웨어 (Memory Management Hardware)

 

MMU(Memory Management Unit)는 컴퓨터 시스템에서 주 메모리를 관리하는 하드웨어 장치다.

 

  • 논리 메모리 메모리 참조를 물리 메모리 주소로 변환, 동적 저장 장소 재배치.
  • 메모리 내에 서로 다른 사용자들이 하나의 프로그램을 공유하도록 지원.
  • 사용자의 허가되지 않은 접근 방지.
  • 사용자가 운영체제의 기능을 변경하지 못하도록 정보를 보호.
  • 세그먼트, 동적 저장 장소 재배치 수행
  • 멀티프로그래밍 시스템. 여러 사용자들 간의 프로그램 세그먼트를 공유.

 

마. 동적 저장 장소 재배치

 

절대 재배치는 프로그램이 메모리에 로드될 때 한 번만 수행되는 재배치 방식.

 

이 방식에서는 프로그램이 메모리의 어느 위치에든지 로드될 수 있지만, 한 번 메모리에 로드된 후에는 프로그램의 위치를 변경할 수 없다.

 

이는 메모리 내의 빈 공간을 효율적으로 사용하기 어렵다.

 

메모리가 할당되고 해제되는 작업이 반복적으로 일어날 때 외부 단편화 발생되는데 절대 재배치에선 해결하기 어렵다.

 

동적 저장 장소 재배치는 프로그램이 실행되는 동안 그 프로그램이 위치하는 메모리의 주소를 변경할 수 있게 하는 기술이다.

 

이를 통해 메모리 공간을 효율적으로 활용할 수 있으며, 다양한 작업을 동시에 처리하는 멀티태스킹 환경을 구현할 수 있다.

 

또한, 외부 단편화 문제를 해결하는데도 효과적이다. (아래에서 설명)

 

바. 단편화

 

단편화는 메모리 공간이 이상적인 사용을 못하게 되어 비효율적으로 되는 상황을 의미.

 

이는 주로 메모리를 할당하고 반환하는 과정에서 발생한다.

 

단편화는 크게 외부 단편화와 내부 단편화로 나뉩니다.

 

 

단편화 유형 설명
외부 단편화 메모리 할당과 해제의 반복으로 불연속적인 빈 메모리 공간('홀')이 여러 개 생김. 홀들이 흩어져 있어 충분한 크기의 메모리가 필요할 때, 각 홀의 크기는 충분하지 않아 할당을 할 수 없는 상황 발생
내부 단편화 할당된 메모리 내부에 사용되지 않는 공간이 생김. 메모리를 일정 크기의 블록으로 나누어 관리하면, 요청 크기가 블록 크기보다 작을 때, 할당된 블록 내에 사용되지 않는 공간이 생김

 

좌-외부 단편화, 우-내부 단편화

사. 세그먼트

 

세그먼트는 가상 메모리를 서로 다른 크기의 논리적 단위로 나눈 것입니다.

 

이는 프로그램의 구조(예: 코드, 데이터, 스택)와 맞추어 메모리를 분할합니다.

 

세그먼트는 각각 독립적으로 관리되며, 주소 지정 및 보호를 위한 정보를 포함하는 세그먼트 테이블에 의해 관리됩니다.

 

  페이지 세그먼트
정의 고정된 크기의 메모리 블록 가변 크기의 논리적 메모리 단위
메모리 관리 방식 가상 메모리를 고정된 크기의 블록으로 나눔 가상 메모리를 서로 크기가 다른 논리적 단위로 분할
크기 고정 가변

 

페이지와 세그먼트의 주요한 차이점은 메모리 관리 방식과 그 크기다.

 

페이지는 가상 메모리를 고정된 크기의 블록으로 나누는 반면에, 세그먼트는 가상 메모리를 서로 크기가 다른 논리적 단위로 분할한다.

 

이때 동적 재배치 기술을 활용하여 가상 메모리를 논리적 단위인 세그먼트로 나눈다.

 

각 세그먼트는 독립적으로 관리되며, 그 크기는 동적으로 변경될 수 있다.

 

따라서 세그먼트는 동적 저장 장소 재배치를 통해 메모리를 효율적으로 활용하면서, 프로그램의 구조에 따라 메모리를 관리하는 방식을 제공한다.

 

아. TLB (Translation Look-aside Buffer)

 

CPU와 가상메모리를 공부하다보면 TLB라는 단어가 많이 사용된다.

 

 

TLB (Translation Look-aside Buffer)는 CPU에 내장된 빠른 메모리로, 가상 주소를 물리 주소로 변환하는 과정에서 페이지 테이블 참조의 속도를 향상하는 역할을 한다.

 

이는 일종의 주소 변환 캐시로 가장 최근에 참조된 페이지 테이블 항목들을 캐시에 저장함으로써 동작.

 

TLB가 없으면, 메모리 참조마다 페이지 테이블을 검색해야 하므로 성능이 저하될 수 있습니다.

 

현대의 컴퓨터 시스템에서는 TLB를 통해 이러한 부하를 크게 줄일 수 있습니다.

 

현재 모든 데스크탑 및 서버용 프로세서는 하나 또는 그 이상의 TLB를 메모리 관리 하드웨어에 가지고 있다.

 

페이지 단위나 세그먼트 단위로 처리하는 가상 메모리를 사용하는 거의 모든 하드웨어는 TLB를 사용한다.

 

CPU는 1차적으로 TLB에 접근하여 원하는 페이지가 존재하는지 탐색하고, TLB에 존재하지 않을 경우 MMU의 페이지 테이블을 참조한다.

 

2. 메모리 할당

 

세상 간단한 방법으로 메모리를 할당해 보자.

 

현대 컴퓨터 시스템은 주로 페이징(Paging)을 사용하여 메모리를 관리한다.

 

세그먼트은 과거에 많이 사용했었다.

 

세그먼트의 외부 단편화, 메모리 관리의 복잡성, 메모리 할당과 해제의 비효율성 등 단점 때문.

 

반면 페이징은 고정 크기 단위로 메모리를 관리하기 때문에 외부 단편화가 없고, 간단하게 메모리를 관리할 수 있으며, 가상 메모리 구현이 쉽다.

 

x86-64 아키텍처에서도 페이징을 통해 메모리를 관리한다.(레거시 호환성을 위해 세그먼트 일부 존재)

 

x86-64 아키텍처에서는 기본적으로 4KB(4096 Bytes)를 페이지로 사용한다.

 

가. 링커 스크립트

 

  • kernel.ld
        ...

    . = ALIGN(4);
    . += 128 * 1024; /* 128KB */
    __stack_top = .;

    . = ALIGN(4096);
    __free_ram = .;
    . += 64 * 1024 * 1024; /* 64MB */
    __free_ram_end = .;
}
  • . = ALIGN(4096); : 페이지 크기인 4KB 경계에 맞춤.
  • 64MB는 임의로 정한 값.

 

실제 x86-64 운영체제들은 부팅 시 UEFI를 통해 메모리 맵 정보(GetMemoryMap)를 받아서 사용 가능한 메모리 영역을 동적으로 파악한다고 한다.

 

나. 메모리 할당 알고리즘

 

세상 간단한 방법으로 메모리를 할당해 보자.

 

  • common.h
#define PAGE_SIZE 4096

C언어의 malloc은 바이트 단위로 메모리를 할당한다.

 

우리는 더 간단하게 페이지 단위로 메모리를 할당한다.

 

  • kernel.c
extern char __free_ram[], __free_ram_end[];

paddr_t alloc_pages(uint32_t n) {
    static paddr_t next_paddr = (paddr_t) __free_ram;
    paddr_t paddr = next_paddr;
    next_paddr += n * PAGE_SIZE;

    if (next_paddr > (paddr_t) __free_ram_end)
        PANIC("out of memory");

    memset((void *) paddr, 0, n * PAGE_SIZE);
    return paddr;
}

__free_ram_end를 넘어서지 않는다면 문제없이 메모리가 할당된다.

 

next_paddr는 static 변수다.

 

  • next_paddr = (paddr_t) __free_ram
    : static 변수의 초기화는 프로그램이 시작될 때 단 한 번만 수행된다.
    : 프로그램 시작 시 한 번만 실행.
    : 함수 호출이 끝나도 값이 계속 유지.
    : 이후 alloc_pages 함수가 호출될 때마다 이전 값을 재사용.

 

만약 __free_ram_end를 넘어가서 커널 패닉을 유도.

 

할당된 메모리 영역은 memset을 통해 0으로 초기화한다.

 

이러한 방식을 Bump Allocator 또는 Linear Allocator라고 한다.

 

간단해서 좋지만 메모리 반환이 안 되는 문제가 있습니다.

 

메모리를 해제하는 기능까지 구현하려면, bitmap 방식이나 buddy system 같은 좀 더 복잡한 알고리즘을 사용해야 한다.

 

다. 테스트

 

  • kernel.c
void kernel_main(void) {
    memset(__bss, 0, (size_t) __bss_end - (size_t) __bss);

    paddr_t paddr0 = alloc_pages(2);
    paddr_t paddr1 = alloc_pages(1);
    printf("alloc_pages test: paddr0=%x\n", paddr0);
    printf("alloc_pages test: paddr1=%x\n", paddr1);

    PANIC("booted!");
}

저장 후 실행한다.

 

$ run.sh
alloc_pages test: paddr0=80221000
alloc_pages test: paddr1=80223000
PANIC: kernel.c:140: booted!

paddr0가 __free_ram 주소와 같은지 확인하고, paddr1가 paddr0로부터 8KB 뒤인지를 확인한다.

 

$ llvm-nm kernel.elf
802004f4 B __bss
802004f4 B __bss_end
80221000 B __free_ram
84221000 B __free_ram_end
802204f4 B __stack_top
802000e4 T alloc_pages
802004f0 d alloc_pages.next_paddr
80200000 T boot
8020002a T handle_trap
80200054 T kernel_entry
80200132 T kernel_main
802001fc T memcpy
80200218 T memset
80200280 T printf
80200016 T putchar
80200010 T sbi_call
80200252 T strcmp
8020022e T strcpy

4KB는 16진수로는 0x1000입니다.

 

페이지 경계로 맞춰진 주소는 16진수로 딱 맞게 떨어진다.

 

 

저작자표시

'CS > OS' 카테고리의 다른 글

[1000줄 OS 구현하기] 예외  (0) 2025.02.05
[1000줄 OS 구현하기] 커널 패닉  (0) 2025.02.03
[1000줄 OS 구현하기] C 표준 라이브러리  (0) 2025.02.03
[1000줄 OS 구현하기] Hello World!  (1) 2025.02.03
[1000줄 OS 구현하기] Boot  (0) 2025.01.21

관련글

티스토리툴바