메모리 할당

실제 OS는 부팅 시 펌웨어에서 메모리 맵이라는 것을 받는다. 거기서 usable 영역을 골라서 내부 allocator에 등록한다. 하지만 간단한 메모리 할당을 구현하기 위해서 여기서는 그렇게 하지 않고, 커널이 점유한 영역 이후의 물리 메모리를 usable 영역이라고 가정한다.

kernel.ld

링커 스크립트에서 stack 이후의 주소 공간에 64MB 크기의 free RAM 영역을 설정한다. . = ALIGN(4096)을 하여, 페이지 크기인 4KB를 경계로 맞췄다.

세상에서 가장 간단한 메모리 할당 알고리즘

메모리를 동적으로 할당하는 함수를 구현해보자. 여기서는 C의 malloc처럼 “바이트 단위"로 할당하는 대신, 더 큰 단위인 “페이지(page)” 단위로 할당한다. 일반적으로 한 페이지는 4KB이다.

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;
}
  • alloc_pages는 n개의 페이지를 할당한 뒤, 그 시작 주소를 반환하는 함수이다.
  • next_paddr는 static으로 정의되어서 프로그램이 시작할때 선언되고, 프로그램이 끝나야 사라진다. 초깃값은 __free_ram의 주소이며, 메모리를 순차적으로 할당하기 위해 사용되는 변수이다.
  • __free_ram_end을 넘어가면 커널 패닉을 일으킨다.
  • memset을 통해 할당된 페이지 영역을 0으로 초기화한다.
  • PAGE_SIZE는 4096으로, common.h에 다음과 같이 정의하였다.
common.h
#define PAGE_SIZE 4096

메모리 할당 테스트

구현한 메모리 할당 함수를 테스트해보기 위해 kernel_main에 다음 코드를 추가해보자.

kernel.c

첫 번째 할당 주소 paddr0가 __free_ram 주소와 같은지, 두 번째 주소 paddr1가 paddr0로부터 8KB(2페이지 = 8KB) 뒤인지를 확인해보면

./run.sh

alloc_pages test: paddr0=80221000
alloc_pages test: paddr1=80223000
PANIC: kernel.c:145: booted!

paddr1이 paddr0보다 0x2000(8KB) 앞에 있는걸 알 수있다.

그리고 실제 심볼 주소를 llvm-nm kernel.elf | grep __free_ram 명령어로 확인해보면

llvm-nm kernel.elf | grep __free_ram

80221000 R __free_ram
84221000 R __free_ram_end

__free_ram과 paddr0이 같은 주소에서 시작하는 것을 알 수 있다.

프로세스

프로세스(Process) 란 실행 중인 프로그램을 의미하며, 커널은 이 프로세스의 생명 주기(Life Cycle)를 여러 상태로 나누어 관리한다. 커널은 프로세스의 정보를 어딘가에 기록해두어야하고, 이 글에서는 process라는 구조를 정의하고, CPU 하나로 여러 프로그램을 멀티 태스킹처럼 보이게 하는 Context Switching 까지 구현하는 것이 목표다.

프로세스 제어 블록 (Process Control Block)

프로세스 제어 블록(PCB)라는 것은 프로세스의 정보를 모아놓은 구조체이다.
일반적인 OS에서는 pid, 현재 상태, 프로그램 카운터(pc), 레지스터 값, 메모리 정보, 할당된 I/O 장치 등의 다양한 정보를 가지고 있다.

이 글에서는 pid, 현재 상태(state), 커널 스택(stack)과 스택 포인터(sp)라는 최소한의 PCB를 구현을 한다. 이때, 커널 스택의 역할은 컨텍스트 스위칭 시 해당 프로세스의 callee-saved 레지스터함수가 호출되었을 때, 호출된 쪽(callee)이 값을 보존할 책임을 지는 레지스터. RISC-V에서는 s0~s11과 ra가 이에 해당한다.반대로 caller-saved 레지스터(a0~a7, t0~t6 등)는 호출하는 쪽이 필요하면 직접 저장해야 한다. 이 구분은 RISC-V Calling Convention에서 정의된다. 값들을 저장·복원하는 공간이 되는 것이다.

코드로 보면 다음과 같이 struct process를 정의할 수 있다.

kernel.c
#define PROCS_MAX 8       // 최대 프로세스 개수

#define PROC_UNUSED   0   // 사용되지 않는 프로세스 구조체
#define PROC_RUNNABLE 1   // 실행 가능한(runnable) 프로세스

struct process {
    int pid;             // 프로세스 ID
    int state;           // 프로세스 상태: PROC_UNUSED or PROC_RUNNABLE
    vaddr_t sp;          // 스택 포인터
    uint8_t stack[8192]; // 커널 스택
};

컨텍스트 스위칭 (Context Switching)

프로세스의 실행 컨텍스트를 바꾸는 것을 컨텍스트 스위칭이라고 한다. CPU는 한 번에 하나의 프로세스만 실행할 수 있기 때문에, 여러 프로세스를 번갈아 실행하려면 현재 프로세스의 상태(레지스터 값들)를 저장하고, 다음 프로세스의 상태를 복원하는 과정이 필요하다. 이러한 저장 및 복원의 대상이 되는 것이 프로세스의 커널 스택이다.

코드는 다음과 같다.

kernel.c
__attribute__((naked))
void switch_context(uint32_t *prev_sp, uint32_t *next_sp) {
    __asm__ __volatile__(
        // 현재 프로세스의 스택에 callee-saved 레지스터를 저장
        "addi sp, sp, -13 * 4\n" // 13개(4바이트씩) 레지스터 공간 확보
        "sw ra,  0  * 4(sp)\n"   // callee-saved 레지스터만 저장
        "sw s0,  1  * 4(sp)\n"
        "sw s1,  2  * 4(sp)\n"
        "sw s2,  3  * 4(sp)\n"
        "sw s3,  4  * 4(sp)\n"
        "sw s4,  5  * 4(sp)\n"
        "sw s5,  6  * 4(sp)\n"
        "sw s6,  7  * 4(sp)\n"
        "sw s7,  8  * 4(sp)\n"
        "sw s8,  9  * 4(sp)\n"
        "sw s9,  10 * 4(sp)\n"
        "sw s10, 11 * 4(sp)\n"
        "sw s11, 12 * 4(sp)\n"

        // 스택 포인터 교체
        "sw sp, (a0)\n"         // *prev_sp = sp
        "lw sp, (a1)\n"         //  sp = *next_sp

        // 다음 프로세스 스택에서 callee-saved 레지스터 복원
        "lw ra,  0  * 4(sp)\n"  
        "lw s0,  1  * 4(sp)\n"
        "lw s1,  2  * 4(sp)\n"
        "lw s2,  3  * 4(sp)\n"
        "lw s3,  4  * 4(sp)\n"
        "lw s4,  5  * 4(sp)\n"
        "lw s5,  6  * 4(sp)\n"
        "lw s6,  7  * 4(sp)\n"
        "lw s7,  8  * 4(sp)\n"
        "lw s8,  9  * 4(sp)\n"
        "lw s9,  10 * 4(sp)\n"
        "lw s10, 11 * 4(sp)\n"
        "lw s11, 12 * 4(sp)\n"
        "addi sp, sp, 13 * 4\n" 
        "ret\n"
    );
}

위 사진을 보면, sp, s0-s11가 callee-saved register인 것을 알 수 있는데, sp는 process struct에서 저장하고 있기 때문에 s0-s11까지만 저장/복원하는 것을 알 수 있다.
ra는 caller-saved register임에도 저장/복원하는 이유는 프로세스 별로 복귀 주소를 결국 저장해야하기 때문이다.

ret은 jalr zero, ra, 0라는 뜻을 가진 의사 명령어이다.

프로세스 생성 함수

프로세스 생성 함수 create_process는 프로세스의 시작 함수 주소를 매개변수로 받아서, 빈 프로세스 슬롯을 찾아 초기화하여 해당 프로세스 구조체의 포인터를 반환한다. 코드는 다음과 같다.

kernel.c
struct process procs[PROCS_MAX]; // 모든 프로세스 제어 구조체 배열

struct process *create_process(uint32_t pc) {
    // 미사용(UNUSED) 상태의 프로세스 구조체 찾기
    struct process *proc = NULL;
    int i;
    for (i = 0; i < PROCS_MAX; i++) {
        if (procs[i].state == PROC_UNUSED) {
            proc = &procs[i];
            break;
        }
    }

    if (!proc)
        PANIC("no free process slots");

    // 커널 스택에 callee-saved 레지스터 공간을 미리 준비
    // 첫 컨텍스트 스위치 시, switch_context에서 이 값들을 복원함
    uint32_t *sp = (uint32_t *) &proc->stack[sizeof(proc->stack)];
    *--sp = 0;                      // s11
    *--sp = 0;                      // s10
    *--sp = 0;                      // s9
    *--sp = 0;                      // s8
    *--sp = 0;                      // s7
    *--sp = 0;                      // s6
    *--sp = 0;                      // s5
    *--sp = 0;                      // s4
    *--sp = 0;                      // s3
    *--sp = 0;                      // s2
    *--sp = 0;                      // s1
    *--sp = 0;                      // s0
    *--sp = (uint32_t) pc;          // ra (처음 실행 시 점프할 주소)

    // 구조체 필드 초기화
    proc->pid = i + 1;
    proc->state = PROC_RUNNABLE;
    proc->sp = (uint32_t) sp;
    return proc;
}

코드 흐름을 분석하자면 다음과 같다.

  1. 빈 process 찾기. 빈 슬롯이 없다면 커널 패닉
  2. sp를 stack의 최상단, 여기서는, stack[8192]의 주소값으로 설정
  3. switch_context가 기대하는 레이아웃에 맞춰 13개(ra, s0-s11)의 초기값을 스택에 채움. ra에는 pc를, 나머지는 0으로 설정
  4. 프로세스 필드 초기화 후 반환

컨텍스트 스위칭 테스트

process A와 process B를 실행시켜서 컨텍스트 스위칭을 테스트해보자.

kernel.c

proc_a_entry와 proc_b_entry는 각각 프로세스 A와 B의 시작 함수를 뜻하지만, 컨텍스트 스위칭이 발생하는지 테스트해보기 위해서 proc_a_entry에서는 다음 실행할 프로세스로 B를, proc_b_entry에서는 다음 실행할 프로세스로 A를 직접 골랐다. 하지만 실제로는 스케쥴러가 실행 순서를 지정해준다.

스케줄러

우리는 switch_context라는 함수에서 다음에 호출할 프로세스를 직접 지정했는데, 이런 방법은 프로세스가 직접 다음 프로세스를 지정해야 한다. 실제 OS는 이렇게 동작하지 않고, 커널이 다음에 실행할 프로세스를 결정해주는데, 이 역할을 하는 커널 코드를 스케줄러(scheduler)라고 한다.

아래 yield 함수가 간단한 스케줄러 코드이다.

kernel.c
struct process *current_proc; // 현재 실행 중인 프로세스
struct process *idle_proc;    // Idle 프로세스

void yield(void) {
    // 실행 가능한 프로세스를 탐색
    struct process *next = idle_proc;
    for (int i = 0; i < PROCS_MAX; i++) {
        struct process *proc = &procs[(current_proc->pid + i) % PROCS_MAX];
        if (proc->state == PROC_RUNNABLE && proc->pid > 0) { // pid > 0 은 idle_proc 제외한 proc
            next = proc;
            break;
        }
    }

    // 현재 프로세스 말고는 실행 가능한 프로세스가 없으면, 그냥 리턴
    if (next == current_proc)
        return;

    // 컨텍스트 스위칭
    struct process *prev = current_proc;
    current_proc = next;
    switch_context(&prev->sp, &next->sp);
}

여기서 idle_proc라는게 등장하는데, 이것은 아무런 process가 돌아가지 않을 때, cpu를 점유하고 있는 역할을 하고, 커널을 부팅할 때, 이 프로세스의 pid를 0으로 설정한다.

kernel.c

여기서의 핵심은 current_proc = idle_proc이다. idle 프로세스(pid=0)는 실행 가능한 프로세스가 없을 때의 폴백이다. CPU는 전원이 켜져 있는 한 항상 무언가를 실행해야 하므로, 아무 프로세스도 RUNNABLE이 아닐 때 대신 실행할 프로세스가 필요하다. 이 튜토리얼에서는 kernel_main의 실행 흐름 자체가 idle 프로세스의 컨텍스트 역할을 하며, idle로 돌아오면 커널 패닉이 발생한다.

마지막으로 proc_a_entry함수와 proc_b_entry함수에서 yield함수를 호출하게 한다.

kernel.c

예외 처리기 수정

예외 핸들러가 예외 발생 시점의 실행 상태를 스택에 저장하는데, 이제 프로세스마다 별도의 커널 스택을 사용하므로 약간의 수정을 해야 한다.

kernel.c

컨텍스트 스위칭 직전에, 다음에 실행될 프로세스(next)의 커널 스택 top 주소를 sscratch에 미리 저장한다. 이렇게 해야 next 프로세스 실행 중 예외가 발생했을 때 올바른 커널 스택으로 전환할 수 있다.

kernel_entry의 코드도 약간 수정하면 다음과 같다.

kernel.c

이전과 다른점을 보자면 다음과 같이 나타낼 수 있다.

이전현재
스택 상황sp가 항상 커널 스택sp가 유저 스택일 수 있음
필요한 동작sp를 sscratch에 백업만sp ↔ sscratch 교환
명령어csrw sscratch, spcsrrw sp, sscratch, sp
sscratch 리셋없음addi a0, sp, 4*31 + csrw sscratch, a0

기존 챕터 8에서는 커널 스택이 하나뿐이라 csrw(단순 백업)로 충분했지만, 이제는 유저 스택에서 예외가 발생할 수 있으므로 csrrw(swap)로 커널 스택 전환이 필요하다. sscratch 리셋은 같은 프로세스에서 다음 예외가 발생했을 때를 대비한 것이다.

참고 자료