이미지 로딩 중...
AI Generated
2025. 11. 14. · 5 Views
Rust로 만드는 나만의 OS 라운드 로빈 스케줄러 완벽 가이드
운영체제의 핵심인 라운드 로빈 스케줄링을 Rust로 직접 구현해봅니다. 태스크 관리부터 컨텍스트 스위칭까지, 실제 OS 개발에서 필요한 모든 개념을 실무 중심으로 다룹니다.
목차
- 라운드 로빈 스케줄러 기초 개념
- 태스크 추가와 제거
- 다음 태스크 선택 로직
- 태스크 컨텍스트 구조체
- 어셈블리로 컨텍스트 스위칭 구현
- 타이머 인터럽트 통합
- 태스크별 독립 스택 관리
- 전체 스케줄러 통합 예제
- 우선순위 확장 - 가중치 기반 라운드 로빈
- 멀티코어 확장 - Per-CPU 스케줄러
1. 라운드 로빈 스케줄러 기초 개념
시작하며
여러분이 여러 프로그램을 동시에 실행할 때, CPU가 어떻게 각 프로그램에게 공평하게 시간을 나눠주는지 궁금하신 적 있나요? 브라우저로 유튜브를 보면서 코드를 편집하고, 동시에 메신저로 대화를 나누는 것이 가능한 이유가 바로 여기에 있습니다.
이런 멀티태스킹은 운영체제의 스케줄러가 담당합니다. 스케줄러가 없다면 하나의 프로그램이 CPU를 독점하게 되고, 다른 프로그램들은 기아 상태에 빠지게 됩니다.
바로 이럴 때 필요한 것이 라운드 로빈(Round Robin) 스케줄러입니다. 각 태스크에게 정해진 시간(타임 슬라이스)만큼 CPU를 할당하고, 순서대로 돌아가며 실행하는 가장 공정한 스케줄링 방식입니다.
개요
간단히 말해서, 라운드 로빈 스케줄러는 모든 태스크를 큐에 넣고 순서대로 일정 시간씩 CPU를 할당하는 스케줄링 알고리즘입니다. 실제 운영체제 개발에서 가장 기본이 되면서도 강력한 방식입니다.
예를 들어, 서버에서 100개의 요청을 동시에 처리해야 할 때, 어느 하나가 독점하지 않고 모든 요청이 골고루 처리되도록 보장해야 합니다. 라운드 로빈은 이런 상황에서 매우 유용합니다.
기존에는 단순히 FIFO(First In First Out) 방식으로 처리했다면, 이제는 타임 슬라이스 기반으로 공평하게 CPU 시간을 분배할 수 있습니다. 이 개념의 핵심 특징은 세 가지입니다: 1) 모든 태스크가 동등한 우선순위를 가짐, 2) 정해진 시간(퀀텀)마다 컨텍스트 스위칭 발생, 3) 기아 상태 방지 보장.
이러한 특징들이 시스템의 공정성과 응답성을 동시에 확보하는 데 중요합니다.
코드 예제
// 라운드 로빈 스케줄러의 기본 구조
use alloc::collections::VecDeque;
pub struct RoundRobinScheduler {
// 실행 대기 중인 태스크들을 저장하는 큐
ready_queue: VecDeque<TaskId>,
// 현재 실행 중인 태스크
current_task: Option<TaskId>,
// 타임 슬라이스 (틱 단위)
time_slice: usize,
// 현재 태스크의 남은 시간
remaining_ticks: usize,
}
impl RoundRobinScheduler {
pub fn new(time_slice: usize) -> Self {
Self {
ready_queue: VecDeque::new(),
current_task: None,
time_slice,
remaining_ticks: time_slice,
}
}
}
설명
이것이 하는 일: 라운드 로빈 스케줄러는 여러 태스크가 CPU를 공평하게 나눠 사용할 수 있도록 관리하는 핵심 컴포넌트입니다. 첫 번째로, VecDeque<TaskId>를 사용해 실행 대기 중인 태스크들을 FIFO 큐로 관리합니다.
VecDeque는 양방향 큐로, 앞에서 태스크를 꺼내고(pop_front) 뒤에서 새 태스크를 추가(push_back)하는 작업이 O(1)로 매우 효율적입니다. 이는 스케줄러가 매 틱마다 호출되기 때문에 성능상 매우 중요합니다.
그 다음으로, current_task와 remaining_ticks 필드가 현재 실행 중인 태스크와 남은 시간을 추적합니다. 매 타이머 인터럽트마다 remaining_ticks를 감소시키고, 0이 되면 컨텍스트 스위칭을 트리거합니다.
이를 통해 어떤 태스크도 CPU를 독점할 수 없게 됩니다. time_slice 필드는 각 태스크가 실행될 수 있는 최대 시간을 정의합니다.
일반적으로 10100 틱(110ms) 정도로 설정하는데, 너무 짧으면 컨텍스트 스위칭 오버헤드가 커지고, 너무 길면 응답성이 떨어집니다. 여러분이 이 코드를 사용하면 멀티태스킹 운영체제의 기초를 만들 수 있습니다.
모든 태스크가 공평하게 CPU 시간을 받고, 시스템 전체의 처리량과 응답성을 균형있게 유지할 수 있습니다. 또한 우선순위 없이도 단순하고 예측 가능한 스케줄링이 가능합니다.
실전 팁
💡 타임 슬라이스는 10ms 정도가 적당합니다. 너무 짧으면 컨텍스트 스위칭 비용이 실제 작업 시간보다 커지고, 너무 길면 인터랙티브 애플리케이션의 응답성이 나빠집니다.
💡 VecDeque 대신 링 버퍼를 사용하면 동적 할당을 피할 수 있어 커널 개발에 더 적합합니다. no_std 환경에서는 메모리 할당이 제한적이므로 고정 크기 버퍼가 안전합니다.
💡 현재 태스크를 다시 큐에 넣을 때는 반드시 뒤쪽(push_back)에 추가해야 합니다. 앞쪽에 넣으면 다른 태스크들이 실행 기회를 잃어 기아 상태가 발생할 수 있습니다.
💡 인터럽트 핸들러 내에서 스케줄러를 호출할 때는 반드시 인터럽트를 비활성화해야 합니다. 그렇지 않으면 스케줄러 자체가 재진입되어 데이터 경쟁이 발생합니다.
💡 디버깅 시에는 각 태스크의 실행 시간을 측정해서 로그로 남기세요. 특정 태스크가 타임 슬라이스를 다 쓰지 않고 종료되는지, 아니면 항상 전체 시간을 소비하는지 파악할 수 있습니다.
2. 태스크 추가와 제거
시작하며
여러분이 운영체제를 만들 때 새로운 프로그램을 실행하거나 종료하는 상황을 어떻게 처리하시나요? 프로세스가 fork()를 호출하거나, 사용자가 프로그램을 닫을 때 스케줄러는 이를 즉시 반영해야 합니다.
이런 동적인 상황 처리가 없다면 시스템은 부팅 시 존재하던 태스크만 계속 실행하게 됩니다. 새로운 애플리케이션을 시작할 수도, 완료된 태스크를 정리할 수도 없죠.
바로 이럴 때 필요한 것이 태스크 추가/제거 메커니즘입니다. 런타임에 동적으로 스케줄러의 큐를 조작하여 시스템 상태를 정확히 반영합니다.
개요
간단히 말해서, 태스크 추가/제거는 스케줄러가 실행 중에 새로운 태스크를 큐에 넣거나 완료된 태스크를 제거하는 작업입니다. 실무에서는 이것이 매우 빈번하게 일어납니다.
예를 들어, 웹 서버에서 새로운 클라이언트 연결마다 태스크를 생성하고, 요청 처리가 끝나면 태스크를 정리해야 합니다. 이런 작업이 안전하고 효율적으로 이루어져야 메모리 누수나 데드락 없이 시스템이 장시간 안정적으로 동작합니다.
기존에는 정적으로 태스크 개수가 고정되어 있었다면, 이제는 동적으로 생성하고 삭제할 수 있습니다. 핵심 특징은: 1) 원자적 연산으로 동시성 안전성 보장, 2) 현재 실행 중인 태스크를 제거할 때의 특수 처리, 3) 큐가 비었을 때의 아이들 태스크 처리.
이러한 특징들이 멀티태스킹 시스템의 동적 특성을 안전하게 구현하는 데 필수적입니다.
코드 예제
impl RoundRobinScheduler {
// 새 태스크를 ready queue에 추가
pub fn add_task(&mut self, task_id: TaskId) {
self.ready_queue.push_back(task_id);
}
// 특정 태스크를 제거
pub fn remove_task(&mut self, task_id: TaskId) {
// 현재 실행 중인 태스크를 제거하는 경우
if self.current_task == Some(task_id) {
self.current_task = None;
self.remaining_ticks = 0;
}
// ready queue에서 제거
self.ready_queue.retain(|&id| id != task_id);
}
// 태스크가 스스로 yield하는 경우
pub fn yield_current(&mut self) {
if let Some(task_id) = self.current_task.take() {
// 다시 큐의 뒤에 추가
self.ready_queue.push_back(task_id);
self.remaining_ticks = 0;
}
}
}
설명
이것이 하는 일: 태스크의 생명주기를 관리하여 스케줄러가 항상 유효한 태스크만 실행하도록 보장합니다. 첫 번째로, add_task 메서드는 매우 단순합니다.
새 태스크를 큐의 맨 뒤에 추가하기만 하면 됩니다. 하지만 실제 OS에서는 이 호출 전에 태스크의 초기 컨텍스트(레지스터, 스택 포인터 등)를 설정하는 작업이 선행되어야 합니다.
스케줄러는 단지 태스크 ID만 관리하고, 실제 태스크 상태는 별도의 TaskManager가 담당하는 것이 일반적입니다. 그 다음으로, remove_task는 두 곳을 확인해야 합니다.
먼저 제거하려는 태스크가 현재 실행 중인지 검사합니다. 만약 그렇다면 current_task를 None으로 설정하고 remaining_ticks를 0으로 만들어 다음 스케줄링 시점에 새 태스크를 선택하도록 합니다.
그런 다음 retain 메서드로 ready_queue에서 해당 태스크를 필터링해 제거합니다. retain은 O(n)이지만 태스크 개수가 많지 않으면 충분히 빠릅니다.
yield_current는 협력적 멀티태스킹을 위한 메서드입니다. 태스크가 I/O 대기 같은 상황에서 자발적으로 CPU를 양보할 때 사용합니다.
현재 태스크를 큐의 뒤로 보내고 타임 슬라이스를 리셋하여 즉시 다음 태스크로 전환되도록 합니다. 여러분이 이 코드를 사용하면 프로세스 생성(fork), 종료(exit), 자발적 양보(yield) 같은 운영체제의 기본 동작들을 구현할 수 있습니다.
또한 태스크가 블로킹 I/O에 들어갈 때 다른 태스크에게 CPU를 넘겨주어 시스템 전체의 효율성을 높일 수 있습니다.
실전 팁
💡 remove_task를 호출한 직후에는 반드시 해당 태스크의 리소스(스택, 파일 디스크립터 등)를 정리해야 합니다. 스케줄러는 ID만 제거하므로 메모리 정리는 별도로 필요합니다.
💡 현재 실행 중인 태스크를 제거하는 것은 특수한 상황입니다. 이 경우 현재 코드가 리턴된 후 즉시 다른 태스크로 전환해야 하므로, remove_task 호출 후 반드시 schedule()을 호출하세요.
💡 yield는 락을 기다리는 스핀락보다 효율적입니다. 락을 획득하지 못했을 때 busy-wait 대신 yield를 호출하면 다른 태스크가 락을 해제할 기회를 줄 수 있습니다.
💡 태스크 ID는 재사용하지 마세요. 제거된 태스크의 ID를 즉시 재할당하면 늦게 도착한 메시지나 이벤트가 잘못된 태스크에게 전달될 수 있습니다. Generation counter를 사용하면 안전합니다.
💡 멀티코어 시스템에서는 각 코어마다 별도의 스케줄러를 유지하는 것이 일반적입니다. 태스크 추가 시 로드 밸런싱을 고려하여 가장 부하가 적은 코어의 스케줄러에 추가하세요.
3. 다음 태스크 선택 로직
시작하며
여러분이 스케줄러를 구현할 때 가장 중요한 순간이 언제일까요? 바로 현재 태스크의 타임 슬라이스가 끝났을 때, "다음에 누구를 실행할까?"를 결정하는 순간입니다.
이 결정이 잘못되면 특정 태스크가 계속 실행되지 못하거나, 시스템이 멈춘 것처럼 보이는 문제가 발생합니다. 타이머 인터럽트마다 호출되므로 성능도 매우 중요합니다.
바로 이럴 때 필요한 것이 효율적이고 공정한 태스크 선택 알고리즘입니다. 라운드 로빈에서는 큐의 맨 앞 태스크를 선택하는 단순한 방식이지만, 여러 엣지 케이스를 처리해야 합니다.
개요
간단히 말해서, 다음 태스크 선택은 타이머 인터럽트가 발생했을 때 ready queue에서 실행할 태스크를 골라내는 핵심 로직입니다. 실무에서는 이것이 시스템 성능과 응답성을 직접적으로 결정합니다.
예를 들어, 게임 엔진에서 렌더링 태스크와 물리 시뮬레이션 태스크를 적절히 교차 실행해야 60fps를 유지할 수 있습니다. 선택 로직이 비효율적이면 프레임 드롭이 발생합니다.
기존에는 단순히 큐에서 pop하기만 했다면, 이제는 현재 태스크를 다시 큐에 넣고, 빈 큐 처리, 아이들 태스크 관리 등 복잡한 상황을 모두 고려해야 합니다. 핵심 특징은: 1) O(1) 시간 복잡도로 매우 빠름, 2) 현재 태스크의 재배치 처리, 3) 큐가 비었을 때 아이들 상태 진입.
이러한 특징들이 인터럽트 핸들러 내에서 빠르게 실행되면서도 정확한 스케줄링을 보장합니다.
코드 예제
impl RoundRobinScheduler {
// 다음 실행할 태스크를 선택
pub fn schedule(&mut self) -> Option<TaskId> {
// 현재 태스크의 타임 슬라이스가 남았다면 계속 실행
if self.remaining_ticks > 0 {
return self.current_task;
}
// 현재 태스크를 큐의 뒤로 이동 (아직 실행할 것이 있다면)
if let Some(task_id) = self.current_task {
self.ready_queue.push_back(task_id);
}
// 큐에서 다음 태스크 선택
self.current_task = self.ready_queue.pop_front();
// 새 태스크의 타임 슬라이스 리셋
if self.current_task.is_some() {
self.remaining_ticks = self.time_slice;
}
self.current_task
}
// 타이머 틱 처리
pub fn tick(&mut self) {
if self.remaining_ticks > 0 {
self.remaining_ticks -= 1;
}
}
}
설명
이것이 하는 일: 매 타이머 인터럽트마다 현재 실행할 태스크를 결정하여 공정한 CPU 시간 분배를 실현합니다. 첫 번째로, schedule 메서드는 먼저 remaining_ticks를 확인합니다.
0보다 크다면 현재 태스크가 아직 타임 슬라이스를 다 쓰지 않은 것이므로 그대로 계속 실행합니다. 이는 불필요한 컨텍스트 스위칭을 막아 성능을 크게 향상시킵니다.
컨텍스트 스위칭은 레지스터 저장/복원, 캐시 무효화 등으로 수십~수백 사이클이 소요되는 비싼 연산입니다. 그 다음으로, 타임 슬라이스가 끝났다면 현재 태스크를 큐의 뒤에 다시 넣습니다.
if let Some(task_id)로 체크하는 이유는 현재 태스크가 없을 수도 있기 때문입니다(부팅 직후나 모든 태스크가 종료된 경우). 이렇게 뒤에 넣음으로써 다른 태스크들이 먼저 실행될 기회를 얻습니다.
pop_front로 큐의 맨 앞 태스크를 꺼내 새로운 current_task로 설정합니다. 큐가 비어있으면 None이 반환되고, 이는 시스템이 아이들 상태로 진입해야 함을 의미합니다.
실제 OS에서는 이때 HLT 명령으로 CPU를 저전력 상태로 만들어 배터리를 아낍니다. 마지막으로, 새 태스크가 선택되었으면 remaining_ticks를 time_slice로 리셋합니다.
tick 메서드는 매 타이머 인터럽트마다 호출되어 이 값을 감소시킵니다. 여러분이 이 코드를 사용하면 CPU 시간이 공정하게 분배되는 멀티태스킹 시스템을 만들 수 있습니다.
각 태스크는 정확히 time_slice만큼의 틱 동안 실행되고, 다른 태스크에게 차례를 넘깁니다. 또한 O(1) 시간 복잡도 덕분에 수백 개의 태스크가 있어도 스케줄링 오버헤드가 일정합니다.
실전 팁
💡 schedule()은 인터럽트 핸들러에서 호출되므로 절대 패닉하거나 무한루프에 빠지면 안 됩니다. 모든 엣지 케이스를 철저히 테스트하세요.
💡 remaining_ticks가 0이 되었을 때만 스케줄링하지 말고, 태스크가 블로킹 I/O에 들어갈 때도 명시적으로 schedule()을 호출하세요. 이를 위해 별도의 yield_and_schedule 메서드를 만드는 것이 좋습니다.
💡 멀티코어에서는 schedule()이 여러 코어에서 동시에 호출될 수 있습니다. ready_queue 접근을 SpinLock으로 보호하되, lock contention을 줄이기 위해 per-core 큐를 사용하는 것이 좋습니다.
💡 디버깅을 위해 각 태스크가 실제로 얼마나 실행되었는지 통계를 모으세요. TaskId별로 누적 실행 틱을 기록하면 어떤 태스크가 CPU를 많이 쓰는지 프로파일링할 수 있습니다.
💡 큐가 비었을 때(아이들 상태) None을 반환하는 대신 특별한 idle_task를 반환하는 방식도 있습니다. 이렇게 하면 스케줄러 코드가 단순해지고, idle_task에서 HLT 명령을 실행하거나 백그라운드 작업을 처리할 수 있습니다.
4. 태스크 컨텍스트 구조체
시작하며
여러분이 한 태스크에서 다른 태스크로 전환할 때 무엇을 저장해야 할까요? CPU의 모든 레지스터 값, 스택 포인터, 명령 포인터 등 태스크의 전체 실행 상태를 보존해야 합니다.
이 정보를 잃어버리면 태스크가 다시 실행될 때 완전히 엉뚱한 코드를 실행하거나 크래시가 발생합니다. x86_64에서는 16개의 범용 레지스터와 RFLAGS, 세그먼트 레지스터 등을 모두 저장해야 합니다.
바로 이럴 때 필요한 것이 TaskContext 구조체입니다. 컨텍스트 스위칭 시 모든 레지스터를 이 구조체에 저장하고, 복원할 때 다시 CPU로 로드합니다.
개요
간단히 말해서, TaskContext는 태스크의 실행 상태(레지스터, 스택 포인터 등)를 저장하는 데이터 구조입니다. 실무 OS 개발에서는 이것이 컨텍스트 스위칭의 핵심입니다.
예를 들어, 태스크 A가 실행 중일 때 타이머 인터럽트가 발생하면, 현재 모든 레지스터를 TaskContext에 저장하고, 태스크 B의 TaskContext에서 레지스터를 복원하여 태스크 B가 중단되었던 시점부터 계속 실행되도록 합니다. 기존에는 어셈블리로 수동으로 레지스터를 푸시/팝했다면, 이제는 구조화된 데이터 타입으로 안전하게 관리할 수 있습니다.
핵심 특징은: 1) CPU 아키텍처에 특화된 레이아웃, 2) #[repr(C)]로 메모리 레이아웃 보장, 3) 어셈블리 코드와의 정확한 오프셋 매칭. 이러한 특징들이 하드웨어와 소프트웨어의 경계에서 정확한 상태 전환을 보장합니다.
코드 예제
// x86_64 아키텍처의 태스크 컨텍스트
#[repr(C)]
#[derive(Debug, Clone, Copy)]
pub struct TaskContext {
// 범용 레지스터들 (callee-saved)
pub r15: u64,
pub r14: u64,
pub r13: u64,
pub r12: u64,
pub rbx: u64,
pub rbp: u64,
// 명령 포인터 (리턴 주소)
pub rip: u64,
}
impl TaskContext {
pub const fn new() -> Self {
Self {
r15: 0, r14: 0, r13: 0,
r12: 0, rbx: 0, rbp: 0,
rip: 0,
}
}
// 새 태스크를 위한 초기 컨텍스트 생성
pub fn new_task(entry_point: u64, stack_top: u64) -> Self {
let mut ctx = Self::new();
ctx.rip = entry_point; // 태스크 시작 주소
ctx.rbp = stack_top; // 스택 베이스
ctx
}
}
설명
이것이 하는 일: 태스크의 실행 상태를 메모리에 저장하여 나중에 정확히 같은 지점에서 실행을 재개할 수 있게 합니다. 첫 번째로, #[repr(C)] 어트리뷰트가 매우 중요합니다.
이것이 없으면 Rust 컴파일러가 필드 순서를 재배치할 수 있어, 어셈블리 코드에서 접근할 때 오프셋이 맞지 않게 됩니다. C 언어 레이아웃을 사용하면 순서가 보장되어 어셈블리에서 0(%rdi)는 r15, 8(%rdi)는 r14 식으로 정확히 접근할 수 있습니다.
그 다음으로, 왜 r15, r14 같은 레지스터만 저장할까요? x86_64 calling convention에서 이들은 "callee-saved" 레지스터입니다.
즉, 함수가 호출될 때 호출된 함수가 이 레지스터들을 보존할 책임이 있습니다. 반면 rax, rcx 같은 "caller-saved" 레지스터는 함수 호출 전에 호출자가 저장하므로 컨텍스트에 포함할 필요가 없습니다.
이렇게 하면 컨텍스트 크기를 줄여 메모리와 스위칭 시간을 절약합니다. rip 필드는 명령 포인터로, 태스크가 다시 실행될 때 어디서부터 시작할지를 가리킵니다.
새 태스크를 만들 때는 entry_point로 설정하고, 컨텍스트 스위칭 시에는 현재 call 명령의 리턴 주소가 자동으로 저장됩니다. new_task 메서드는 새로운 태스크의 초기 컨텍스트를 생성합니다.
entry_point는 태스크의 main 함수 주소이고, stack_top은 태스크 전용 스택의 최상단 주소입니다. 각 태스크는 독립된 스택을 가져야 하며, 보통 4KB~16KB 정도를 할당합니다.
여러분이 이 코드를 사용하면 안전한 멀티태스킹의 기초를 다질 수 있습니다. 각 태스크의 상태가 완전히 격리되어 서로 간섭하지 않으며, 컨텍스트 스위칭 후에도 정확히 중단되었던 시점부터 실행이 재개됩니다.
실전 팁
💡 실제 OS에서는 FPU/SSE 레지스터들도 저장해야 합니다. 하지만 이들은 크기가 크므로(512바이트 이상) lazy context switching을 사용하세요. 태스크가 실제로 FPU를 사용할 때만 저장하는 방식입니다.
💡 ARM 아키텍처에서는 r0-r15와 CPSR 레지스터를 저장해야 합니다. 아키텍처마다 다르므로 조건부 컴파일(#[cfg(target_arch)])로 분기하세요.
💡 디버깅 시 TaskContext를 프린트할 수 있도록 Debug trait을 구현하세요. 태스크가 크래시했을 때 마지막 레지스터 상태를 보면 원인을 파악하기 쉽습니다.
💡 보안을 위해 태스크 스택에 가드 페이지를 두세요. 스택 오버플로우가 발생하면 페이지 폴트로 즉시 탐지할 수 있습니다. 스택 상단 전에 보호 페이지를 배치하면 됩니다.
💡 new_task에서 스택에 초기 값을 푸시해두면 유용합니다. 예를 들어 태스크 종료 시 호출할 cleanup 함수의 주소를 리턴 주소로 푸시해두면, 태스크가 그냥 리턴해도 자동으로 정리됩니다.
5. 어셈블리로 컨텍스트 스위칭 구현
시작하며
여러분이 실제로 한 태스크에서 다른 태스크로 전환하려면 어떻게 해야 할까요? Rust만으로는 불가능합니다.
CPU 레지스터를 직접 조작하고, 스택 포인터를 바꾸는 작업은 반드시 어셈블리 코드가 필요합니다. 이 부분이 잘못되면 시스템이 즉시 크래시하거나 데이터가 손상됩니다.
레지스터 하나라도 잘못 저장하거나 복원하면 태스크가 완전히 다른 코드를 실행하게 됩니다. 바로 이럴 때 필요한 것이 인라인 어셈블리로 작성된 컨텍스트 스위칭 함수입니다.
현재 컨텍스트를 저장하고 새 컨텍스트를 로드하는 원자적 연산을 수행합니다.
개요
간단히 말해서, 컨텍스트 스위칭은 현재 태스크의 레지스터를 메모리에 저장하고, 다음 태스크의 레지스터를 메모리에서 CPU로 로드하는 저수준 연산입니다. 실무에서는 이것이 매 타임 슬라이스마다 발생하므로 성능이 매우 중요합니다.
예를 들어, 100Hz 타이머로 10ms 타임 슬라이스를 사용하면 초당 100번 컨텍스트 스위칭이 일어납니다. 각 스위칭이 10us 걸린다면 전체 CPU 시간의 0.1%가 스케줄링에 소모됩니다.
기존에는 외부 어셈블리 파일로 작성했다면, 이제는 Rust의 인라인 어셈블리로 타입 안전하게 통합할 수 있습니다. 핵심 특징은: 1) 원자적 연산으로 중간에 인터럽트 불가, 2) 정확한 레지스터 저장/복원 순서, 3) 스택 포인터 전환.
이러한 특징들이 멀티태스킹의 투명성을 보장하여 태스크는 전환이 일어난 것을 알 수 없습니다.
코드 예제
use core::arch::asm;
// 현재 컨텍스트를 저장하고 새 컨텍스트로 전환
#[naked]
pub unsafe extern "C" fn switch_context(
old_context: *mut TaskContext,
new_context: *const TaskContext,
) {
asm!(
// 현재 컨텍스트 저장 (old_context는 rdi에 있음)
"mov [rdi + 0x00], r15",
"mov [rdi + 0x08], r14",
"mov [rdi + 0x10], r13",
"mov [rdi + 0x18], r12",
"mov [rdi + 0x20], rbx",
"mov [rdi + 0x28], rbp",
// 리턴 주소를 rip로 저장
"mov rax, [rsp]",
"mov [rdi + 0x30], rax",
// 새 컨텍스트 복원 (new_context는 rsi에 있음)
"mov r15, [rsi + 0x00]",
"mov r14, [rsi + 0x08]",
"mov r13, [rsi + 0x10]",
"mov r12, [rsi + 0x18]",
"mov rbx, [rsi + 0x20]",
"mov rbp, [rsi + 0x28]",
// 새 태스크의 rip로 점프
"mov rax, [rsi + 0x30]",
"mov [rsp], rax",
"ret",
options(noreturn)
)
}
설명
이것이 하는 일: CPU의 실행 흐름을 한 태스크에서 다른 태스크로 원자적으로 전환하는 핵심 메커니즘입니다. 첫 번째로, #[naked] 어트리뷰트가 중요합니다.
이것은 Rust 컴파일러에게 함수 프롤로그/에필로그를 생성하지 말라고 지시합니다. 일반 함수는 스택 프레임 설정을 위해 push rbp; mov rbp, rsp 같은 코드를 자동 생성하는데, 컨텍스트 스위칭에서는 우리가 직접 스택과 레지스터를 완전히 제어해야 하므로 이를 방지합니다.
그 다음으로, 저장 부분을 보면 [rdi + offset] 형태로 old_context 구조체의 각 필드에 레지스터 값을 씁니다. x86_64 System V ABI에서 첫 번째 인자는 rdi, 두 번째 인자는 rsi에 전달됩니다.
오프셋(0x00, 0x08 등)은 TaskContext 구조체의 필드 순서와 정확히 일치해야 합니다. 8바이트씩 증가하는 것은 u64가 8바이트이기 때문입니다.
특히 중요한 부분은 리턴 주소 처리입니다. mov rax, [rsp]는 현재 스택 최상단의 값(switch_context를 호출한 곳의 리턴 주소)을 읽어 rip 필드에 저장합니다.
이렇게 하면 나중에 이 태스크가 다시 실행될 때 switch_context가 리턴하는 것처럼 보입니다. 복원 부분은 그 반대입니다.
new_context에서 모든 레지스터를 로드한 다음, 새 태스크의 rip 값을 스택에 푸시하고 ret을 실행합니다. ret은 스택에서 주소를 팝하여 그곳으로 점프하므로, 결과적으로 새 태스크의 저장된 위치로 실행이 이동합니다.
여러분이 이 코드를 사용하면 완전히 투명한 태스크 전환을 구현할 수 있습니다. 태스크 입장에서는 함수 호출처럼 보이지만, 실제로는 다른 태스크로 전환되었다가 나중에 돌아옵니다.
이것이 선점형 멀티태스킹의 핵심입니다.
실전 팁
💡 컨텍스트 스위칭은 인터럽트가 비활성화된 상태에서 호출되어야 합니다. 중간에 인터럽트가 발생하면 레지스터 값이 손상될 수 있습니다. cli/sti 명령으로 보호하세요.
💡 첫 번째 태스크 전환 시 old_context가 유효하지 않을 수 있습니다. 이 경우를 대비해 더미 컨텍스트를 사용하거나, 첫 전환용 별도 함수를 만드세요.
💡 ARM에서는 stmia/ldmia 명령으로 여러 레지스터를 한 번에 저장/로드할 수 있어 더 효율적입니다. 아키텍처별로 최적화된 코드를 작성하세요.
💡 디버깅 시 각 컨텍스트 스위칭을 로그로 남기면 유용합니다. 하지만 로깅 자체가 오버헤드가 크므로 조건부 컴파일로 디버그 빌드에만 포함하세요.
💡 TLS(Thread Local Storage)를 사용한다면 컨텍스트 스위칭 시 FS/GS 세그먼트 레지스터도 전환해야 합니다. wrfsbase/wrgsbase 명령을 사용하거나 MSR을 직접 조작하세요.
6. 타이머 인터럽트 통합
시작하며
여러분이 라운드 로빈 스케줄러를 만들었다면, 이제 "언제" 스케줄링을 트리거할 것인지 결정해야 합니다. 타이머 인터럽트 없이는 태스크가 자발적으로 양보하지 않는 한 영원히 실행됩니다.
이것이 없으면 선점형 멀티태스킹이 불가능합니다. 악의적이거나 버그가 있는 프로그램이 CPU를 독점하여 시스템 전체가 멈출 수 있습니다.
바로 이럴 때 필요한 것이 주기적인 타이머 인터럽트입니다. 하드웨어 타이머가 일정 간격(예: 10ms)마다 인터럽트를 발생시켜 스케줄러를 호출하고, 필요하면 컨텍스트 스위칭을 수행합니다.
개요
간단히 말해서, 타이머 인터럽트 통합은 하드웨어 타이머를 설정하고 인터럽트 핸들러에서 스케줄러를 호출하는 과정입니다. 실무에서는 이것이 운영체제의 심장박동과 같습니다.
예를 들어, Linux는 보통 100Hz1000Hz의 타이머를 사용하여 110ms마다 스케줄러를 실행합니다. 이 주파수가 시스템의 응답성과 오버헤드 간 균형을 결정합니다.
기존에는 PIT(Programmable Interval Timer)를 사용했다면, 이제는 더 정확한 LAPIC 타이머나 HPET를 사용할 수 있습니다. 핵심 특징은: 1) 하드웨어 타이머 초기화, 2) IDT에 인터럽트 핸들러 등록, 3) 핸들러에서 스케줄러 호출 및 컨텍스트 스위칭.
이러한 특징들이 시간 기반 스케줄링의 자동화를 실현합니다.
코드 예제
use x86_64::structures::idt::InterruptDescriptorTable;
// LAPIC 타이머 초기화 (100Hz = 10ms 간격)
pub fn init_timer() {
const TIMER_FREQUENCY: u64 = 100; // Hz
const LAPIC_TIMER_DIVIDE: u32 = 16;
unsafe {
// LAPIC 타이머 디바이더 설정
lapic_write(LAPIC_TDCR, LAPIC_TIMER_DIVIDE);
// 초기 카운트 값 계산 (CPU 주파수 기반)
let cpu_freq = get_cpu_frequency();
let count = cpu_freq / TIMER_FREQUENCY / LAPIC_TIMER_DIVIDE;
lapic_write(LAPIC_TICR, count as u32);
// 주기적 모드로 타이머 시작
lapic_write(LAPIC_TIMER, TIMER_VECTOR | TIMER_PERIODIC);
}
}
// 타이머 인터럽트 핸들러
extern "x86-interrupt" fn timer_interrupt_handler(
_stack_frame: InterruptStackFrame
) {
// 스케줄러 틱 처리
SCHEDULER.lock().tick();
// 스케줄링 수행
if let Some(new_task) = SCHEDULER.lock().schedule() {
// 필요하면 컨텍스트 스위칭
perform_context_switch(new_task);
}
// EOI 전송으로 인터럽트 완료 알림
unsafe { lapic_write(LAPIC_EOI, 0); }
}
설명
이것이 하는 일: 하드웨어 타이머와 스케줄러를 연결하여 선점형 멀티태스킹을 자동화합니다. 첫 번째로, init_timer 함수는 LAPIC(Local Advanced Programmable Interrupt Controller) 타이머를 설정합니다.
LAPIC은 각 CPU 코어마다 독립적인 타이머를 제공하여 멀티코어 시스템에 적합합니다. TIMER_FREQUENCY를 100Hz로 설정하면 10ms마다 인터럽트가 발생합니다.
이는 라운드 로빈의 타임 슬라이스와 일치시키는 것이 일반적입니다. 디바이더는 타이머 카운트 속도를 조정합니다.
CPU가 3GHz로 동작한다면 너무 빠르므로 16으로 나눠서 적절한 범위로 만듭니다. LAPIC_TICR(Timer Initial Count Register)에 계산된 카운트 값을 쓰면 타이머가 시작됩니다.
TIMER_PERIODIC 플래그는 카운트가 0이 되면 자동으로 초기값으로 리셋되어 주기적으로 인터럽트를 발생시킵니다. 그 다음으로, timer_interrupt_handler는 extern "x86-interrupt" calling convention을 사용합니다.
이는 Rust가 인터럽트 핸들러에 필요한 특별한 처리(스택 프레임 저장, iretq 등)를 자동으로 생성하게 합니다. 핸들러는 먼저 tick()을 호출하여 현재 태스크의 remaining_ticks를 감소시킵니다.
schedule()은 새로운 태스크를 선택합니다. 만약 현재 태스크와 다르다면 perform_context_switch를 호출하여 실제 전환을 수행합니다.
이 함수는 내부적으로 switch_context 어셈블리 함수를 호출합니다. 마지막으로 lapic_write(LAPIC_EOI, 0)로 End Of Interrupt를 전송해야 합니다.
이것이 없으면 LAPIC이 인터럽트가 아직 처리 중이라고 생각하여 다음 인터럽트를 보내지 않습니다. 여러분이 이 코드를 사용하면 완전 자동화된 선점형 멀티태스킹 시스템을 만들 수 있습니다.
태스크들은 타이머에 의해 자동으로 교체되며, 무한루프에 빠진 태스크도 타임 슬라이스가 끝나면 강제로 중단됩니다.
실전 팁
💡 타이머 주파수는 응답성과 오버헤드의 트레이드오프입니다. 데스크탑은 100~250Hz, 서버는 100Hz, 임베디드는 50Hz 정도가 적당합니다. 너무 높으면 인터럽트 처리만으로 CPU를 낭비합니다.
💡 인터럽트 핸들러는 가능한 한 빠르게 실행되어야 합니다. 무거운 작업은 bottom-half 핸들러로 미루세요. 스케줄링 자체는 보통 수십 나노초면 충분합니다.
💡 멀티코어에서는 각 코어가 독립적으로 타이머 인터럽트를 받습니다. 코어 0번에서만 글로벌 타이머를 업데이트하고, 나머지는 로컬 스케줄링만 수행하는 것이 일반적입니다.
💡 tickless 커널을 구현하려면 다음 스케줄링 이벤트 시간을 계산하여 타이머를 동적으로 프로그래밍하세요. 아이들 시 불필요한 인터럽트를 막아 전력 소모를 줄일 수 있습니다.
💡 디버깅 시 타이머 인터럽트 빈도를 낮추면 시리얼 출력이나 디버거 사용이 편해집니다. 1Hz 정도로 낮추면 로그를 천천히 관찰할 수 있습니다.
7. 태스크별 독립 스택 관리
시작하며
여러분이 여러 태스크를 동시에 실행할 때, 각 태스크가 같은 스택을 공유하면 어떻게 될까요? 태스크 A가 스택에 데이터를 푸시한 상태에서 태스크 B로 전환되면, B가 스택을 덮어써 A의 데이터가 손상됩니다.
이런 문제는 실제로 매우 치명적입니다. 함수 호출 시 리턴 주소나 로컬 변수가 다른 태스크에 의해 손상되면 즉시 크래시하거나 보안 취약점이 됩니다.
바로 이럴 때 필요한 것이 태스크별 독립 스택입니다. 각 태스크마다 전용 스택 영역을 할당하고, 컨텍스트 스위칭 시 스택 포인터를 전환하여 완전한 격리를 보장합니다.
개요
간단히 말해서, 태스크별 독립 스택은 각 태스크에게 고유한 스택 메모리 영역을 할당하여 서로의 실행 상태를 침범하지 않도록 하는 메커니즘입니다. 실무에서는 이것이 멀티태스킹의 필수 요소입니다.
예를 들어, 웹 서버에서 각 클라이언트 요청을 처리하는 태스크는 독립된 스택을 가져야 다른 요청의 데이터와 섞이지 않습니다. 스택 크기는 보통 4KB~16KB로, 깊은 재귀나 큰 로컬 변수가 있으면 더 크게 설정합니다.
기존에는 모든 스레드가 하나의 스택을 공유했다면, 이제는 각자의 영역을 가지므로 안전하고 독립적인 실행이 가능합니다. 핵심 특징은: 1) 힙에서 스택 메모리 동적 할당, 2) 스택 오버플로우 방지를 위한 가드 페이지, 3) TaskContext에 스택 포인터 저장.
이러한 특징들이 태스크 간 완전한 메모리 격리를 제공합니다.
코드 예제
use alloc::alloc::{alloc, dealloc, Layout};
const STACK_SIZE: usize = 16 * 1024; // 16KB 스택
const STACK_ALIGN: usize = 16; // 16바이트 정렬
pub struct TaskStack {
bottom: *mut u8,
size: usize,
}
impl TaskStack {
// 새 스택 할당
pub fn new() -> Result<Self, &'static str> {
let layout = Layout::from_size_align(STACK_SIZE, STACK_ALIGN)
.map_err(|_| "Invalid stack layout")?;
let bottom = unsafe { alloc(layout) };
if bottom.is_null() {
return Err("Failed to allocate stack");
}
Ok(Self {
bottom,
size: STACK_SIZE,
})
}
// 스택 최상단 주소 계산 (스택은 아래로 자라므로)
pub fn top(&self) -> u64 {
(self.bottom as u64) + (self.size as u64)
}
// 스택에 초기 값 푸시 (새 태스크 생성 시)
pub unsafe fn push(&self, offset: usize, value: u64) {
let addr = (self.top() as usize - offset) as *mut u64;
*addr = value;
}
}
impl Drop for TaskStack {
fn drop(&mut self) {
let layout = Layout::from_size_align(self.size, STACK_ALIGN).unwrap();
unsafe { dealloc(self.bottom, layout); }
}
}
설명
이것이 하는 일: 각 태스크에게 전용 메모리 공간을 제공하여 함수 호출, 로컬 변수, 리턴 주소 등이 다른 태스크에 의해 손상되지 않도록 보호합니다. 첫 번째로, TaskStack::new()는 alloc 함수로 힙에서 16KB 메모리를 할당합니다.
이 크기는 일반적인 태스크에 충분하지만, 깊은 재귀를 사용하거나 큰 로컬 배열을 선언하는 경우 더 크게 설정해야 합니다. Layout::from_size_align으로 16바이트 정렬을 요청하는 이유는 x86_64에서 스택 포인터가 16바이트 정렬되어야 ABI를 준수하기 때문입니다.
할당이 실패하면 is_null() 체크로 감지하고 에러를 반환합니다. 커널 개발에서는 메모리 부족 상황을 항상 고려해야 합니다.
실패 시 태스크 생성을 중단하거나 우선순위가 낮은 태스크를 종료하여 메모리를 확보합니다. 그 다음으로, top() 메서드는 스택의 최상단 주소를 반환합니다.
x86_64에서 스택은 높은 주소에서 낮은 주소로 자라므로(grows downward), 초기 스택 포인터는 할당된 영역의 끝을 가리켜야 합니다. push 연산은 스택 포인터를 감소시키고 그 위치에 값을 씁니다.
push 메서드는 새 태스크 생성 시 스택을 초기화하는 데 사용됩니다. 예를 들어, 태스크 종료 시 호출될 cleanup 함수의 주소를 리턴 주소 위치에 미리 푸시해두면, 태스크의 main 함수가 리턴할 때 자동으로 cleanup이 실행됩니다.
Drop trait 구현으로 TaskStack이 해제될 때 자동으로 메모리를 반환합니다. 이는 Rust의 RAII 패턴으로, 메모리 누수를 방지하는 안전한 방법입니다.
여러분이 이 코드를 사용하면 각 태스크가 독립적으로 함수를 호출하고 로컬 변수를 사용할 수 있습니다. 태스크 A가 100개의 함수를 중첩 호출해도 태스크 B의 스택에는 전혀 영향을 주지 않으며, 각 태스크는 마치 자신만 실행되는 것처럼 프로그래밍할 수 있습니다.
실전 팁
💡 스택 오버플로우를 감지하려면 스택 영역 아래에 가드 페이지를 추가하세요. 페이지 테이블에서 해당 페이지를 비허용으로 설정하면 오버플로우 시 페이지 폴트가 발생합니다.
💡 16KB가 부족한 경우 동적으로 스택을 확장하는 방법도 있습니다. 가드 페이지 폴트 핸들러에서 새 페이지를 할당하여 스택을 키우면 됩니다. 단, 최대 크기 제한은 필요합니다.
💡 디버깅 시 스택을 특정 패턴(예: 0xCC)으로 채워두면 스택 사용량을 측정할 수 있습니다. 태스크 종료 시 여전히 0xCC로 남아있는 영역이 미사용 영역입니다.
💡 커널 스택과 사용자 스택을 분리하는 것이 보안상 좋습니다. 사용자 태스크가 시스템콜을 호출할 때 커널 스택으로 전환하면 사용자 코드가 커널 데이터를 직접 조작할 수 없습니다.
💡 멀티코어에서는 스택이 해당 태스크가 실행되는 코어의 캐시에 있는 것이 유리합니다. 태스크를 특정 코어에 고정(pinning)하면 캐시 히트율이 올라가 성능이 향상됩니다.
8. 전체 스케줄러 통합 예제
시작하며
여러분이 지금까지 배운 모든 조각들을 어떻게 하나의 동작하는 시스템으로 조립할까요? 스케줄러, 컨텍스트 스위칭, 타이머, 스택 관리를 모두 통합하여 실제로 태스크를 생성하고 실행해야 합니다.
이 통합 과정에서 실수가 많이 발생합니다. 초기화 순서가 잘못되거나, 전역 변수 접근 시 동기화를 빼먹거나, 첫 태스크 전환 시 특수 처리를 하지 않으면 시스템이 크래시합니다.
바로 이럴 때 필요한 것이 전체 흐름을 보여주는 통합 예제입니다. 커널 초기화부터 태스크 생성, 스케줄러 시작까지 전 과정을 다룹니다.
개요
간단히 말해서, 전체 통합은 개별 컴포넌트들을 올바른 순서로 초기화하고 연결하여 멀티태스킹이 실제로 동작하도록 만드는 과정입니다. 실무에서는 이것이 운영체제 부팅 과정의 핵심입니다.
예를 들어, Linux는 init_task를 생성하고 스케줄러를 시작한 다음 나머지 커널 서비스들을 초기화합니다. 순서가 중요하며, 스케줄러가 준비되기 전에 멀티스레딩이 필요한 작업을 시작하면 안 됩니다.
기존에는 각 부분을 따로 테스트했다면, 이제는 모든 것을 함께 실행하여 실제 멀티태스킹 환경을 만듭니다. 핵심 특징은: 1) 올바른 초기화 순서, 2) 전역 스케줄러 인스턴스 관리, 3) 첫 태스크 전환의 특수 처리.
이러한 특징들이 복잡한 시스템을 안정적으로 부팅하고 실행하는 데 필수적입니다.
코드 예제
use spin::Mutex;
use lazy_static::lazy_static;
// 전역 스케줄러 인스턴스
lazy_static! {
static ref SCHEDULER: Mutex<RoundRobinScheduler> = {
Mutex::new(RoundRobinScheduler::new(10)) // 10틱 타임 슬라이스
};
}
// 간단한 태스크 함수들
fn task_a() {
loop {
println!("Task A running");
for _ in 0..100000 { unsafe { core::arch::asm!("nop"); } }
}
}
fn task_b() {
loop {
println!("Task B running");
for _ in 0..100000 { unsafe { core::arch::asm!("nop"); } }
}
}
// 스케줄러 초기화 및 태스크 생성
pub fn init_scheduler() {
// Task A 생성
let stack_a = TaskStack::new().expect("Failed to alloc stack");
let context_a = TaskContext::new_task(
task_a as u64,
stack_a.top()
);
let task_id_a = create_task(context_a, stack_a);
SCHEDULER.lock().add_task(task_id_a);
// Task B 생성
let stack_b = TaskStack::new().expect("Failed to alloc stack");
let context_b = TaskContext::new_task(
task_b as u64,
stack_b.top()
);
let task_id_b = create_task(context_b, stack_b);
SCHEDULER.lock().add_task(task_id_b);
// 타이머 시작
init_timer();
println!("Scheduler initialized with {} tasks", 2);
}
설명
이것이 하는 일: 모든 컴포넌트를 올바른 순서로 초기화하여 멀티태스킹 환경을 구축하고 자동으로 태스크가 교차 실행되게 합니다. 첫 번째로, lazy_static! 매크로로 전역 스케줄러를 생성합니다.
Mutex로 감싸는 이유는 여러 코어나 인터럽트 핸들러에서 동시에 접근할 수 있기 때문입니다. spin::Mutex는 no_std 환경에서 사용하는 스핀락 기반 뮤텍스로, 락을 획득할 때까지 busy-wait합니다.
lazy_static은 첫 접근 시에만 초기화되므로 부팅 시간을 줄입니다. 그 다음으로, init_scheduler 함수가 전체 초기화를 담당합니다.
먼저 각 태스크의 스택을 할당합니다. TaskStack::new()가 실패할 수 있으므로 expect로 패닉을 발생시켜 조기에 문제를 감지합니다.
프로덕션 코드에서는 적절한 에러 처리가 필요합니다. TaskContext::new_task로 초기 컨텍스트를 생성할 때 task_a as u64로 함수 주소를 얻고, stack_a.top()으로 스택 최상단을 전달합니다.
이렇게 하면 태스크가 처음 실행될 때 해당 함수의 처음부터 시작하고, 올바른 스택을 사용합니다. create_task는 컨텍스트와 스택을 전역 태스크 테이블에 저장하고 고유한 TaskId를 반환합니다.
이 ID를 스케줄러에 추가하면 스케줄러는 이 태스크를 실행 대상으로 인식합니다. 모든 태스크를 추가한 후 init_timer()를 호출하여 타이머를 시작합니다.
이 순서가 중요합니다. 타이머를 먼저 시작하면 스케줄러가 초기화되지 않은 상태에서 인터럽트가 발생할 수 있습니다.
여러분이 이 코드를 사용하면 완전히 동작하는 멀티태스킹 시스템을 만들 수 있습니다. Task A와 Task B가 자동으로 교차 실행되며, 각각 "Task A running", "Task B running"을 출력합니다.
nop 루프는 실제 작업을 시뮬레이션하여 타임 슬라이스가 소진되도록 합니다.
실전 팁
💡 첫 스케줄링 시에는 old_context가 유효하지 않을 수 있습니다. 부팅 코드에서 특별한 initial_context를 만들거나, schedule_first() 같은 별도 함수로 처리하세요.
💡 디버깅을 위해 각 태스크가 자신의 ID를 출력하도록 하세요. 스케줄링 순서를 시각적으로 확인하여 라운드 로빈이 제대로 동작하는지 검증할 수 있습니다.
💡 프로덕션 환경에서는 아이들 태스크를 추가하세요. 모든 태스크가 블로킹되었을 때 실행되며, HLT 명령으로 CPU를 절전 모드로 만들어 전력을 아낍니다.
💡 태스크 테이블은 벡터 대신 슬랩 할당자를 사용하는 것이 좋습니다. 태스크 생성/삭제가 빈번한 경우 고정 크기 슬랩이 단편화를 줄이고 성능을 향상시킵니다.
💡 멀티코어로 확장하려면 각 코어마다 별도의 스케줄러를 유지하거나, 글로벌 큐 + 로컬 큐 하이브리드 방식을 사용하세요. 로드 밸런싱을 위해 주기적으로 태스크를 다른 코어로 마이그레이션합니다.
9. 우선순위 확장 - 가중치 기반 라운드 로빈
시작하며
여러분이 라운드 로빈 스케줄러를 사용하다 보면, 모든 태스크가 동등하게 취급되는 것이 불편할 때가 있습니다. 중요한 시스템 서비스는 더 자주 실행되어야 하고, 백그라운드 작업은 덜 실행되어야 합니다.
이 문제는 실시간 시스템이나 인터랙티브 애플리케이션에서 특히 중요합니다. 렌더링 태스크는 60fps를 유지해야 하지만, 로그 쓰기 태스크는 그렇지 않아도 됩니다.
바로 이럴 때 필요한 것이 가중치 기반 라운드 로빈입니다. 각 태스크에 가중치를 부여하여 중요한 태스크가 더 많은 타임 슬라이스를 받거나 더 자주 선택되도록 합니다.
개요
간단히 말해서, 가중치 기반 라운드 로빈은 각 태스크에 우선순위 가중치를 할당하여 중요한 태스크가 더 많은 CPU 시간을 받도록 하는 스케줄링 방식입니다. 실무에서는 이것이 공정성과 우선순위의 균형을 맞춥니다.
예를 들어, 웹 서버에서 요청 처리 태스크는 가중치 10, 통계 수집 태스크는 가중치 1로 설정하면 요청 처리가 10배 많은 CPU 시간을 받습니다. 하지만 통계 수집도 완전히 무시되지 않고 주기적으로 실행됩니다.
기존에는 모든 태스크가 동등했다면, 이제는 중요도에 따라 차등적으로 CPU를 할당할 수 있습니다. 핵심 특징은: 1) 태스크별 가중치 저장, 2) 가중치에 비례한 타임 슬라이스 할당, 3) 기아 상태 방지를 위한 최소 보장.
이러한 특징들이 유연한 스케줄링 정책을 가능하게 합니다.
코드 예제
pub struct WeightedRoundRobinScheduler {
// 태스크 큐 (TaskId와 가중치 쌍)
ready_queue: VecDeque<(TaskId, u32)>,
current_task: Option<(TaskId, u32)>,
base_time_slice: usize,
remaining_ticks: usize,
}
impl WeightedRoundRobinScheduler {
pub fn new(base_time_slice: usize) -> Self {
Self {
ready_queue: VecDeque::new(),
current_task: None,
base_time_slice,
remaining_ticks: 0,
}
}
// 가중치와 함께 태스크 추가
pub fn add_task(&mut self, task_id: TaskId, weight: u32) {
let weight = weight.max(1); // 최소 가중치 1 보장
self.ready_queue.push_back((task_id, weight));
}
pub fn schedule(&mut self) -> Option<TaskId> {
if self.remaining_ticks > 0 {
return self.current_task.map(|(id, _)| id);
}
// 현재 태스크를 큐 뒤로
if let Some(task) = self.current_task {
self.ready_queue.push_back(task);
}
// 다음 태스크 선택
self.current_task = self.ready_queue.pop_front();
// 가중치에 비례한 타임 슬라이스 계산
if let Some((_, weight)) = self.current_task {
self.remaining_ticks = self.base_time_slice * weight as usize;
}
self.current_task.map(|(id, _)| id)
}
}
설명
이것이 하는 일: 태스크의 중요도를 반영하여 CPU 시간을 차등 분배하되, 모든 태스크가 최소한의 실행 기회를 보장받도록 합니다. 첫 번째로, 큐에 (TaskId, u32) 튜플을 저장하여 각 태스크의 가중치를 함께 관리합니다.
가중치는 1 이상의 정수로, 숫자가 클수록 더 중요한 태스크입니다. add_task에서 weight.max(1)로 최소값을 보장하는 것은 가중치 0으로 태스크가 완전히 무시되는 것을 방지합니다.
그 다음으로, schedule 메서드의 핵심은 타임 슬라이스 계산 부분입니다. base_time_slice * weight로 계산하면, 가중치가 1인 태스크는 기본 타임 슬라이스(예: 10틱)를 받고, 가중치가 5인 태스크는 50틱을 받습니다.
이는 가중치 5인 태스크가 5배 오래 실행됨을 의미합니다. 이 방식의 장점은 구현이 간단하면서도 효과적이라는 것입니다.
복잡한 우선순위 큐나 힙 자료구조 없이도 가중치 기반 스케줄링을 달성합니다. 단점은 가중치가 매우 높은 태스크가 있으면 다른 태스크들의 응답성이 떨어질 수 있다는 것입니다.
또 다른 접근법은 가중치에 비례해 큐에 여러 번 넣는 방식입니다. 가중치 3인 태스크를 큐에 3번 추가하면 3배 자주 선택됩니다.
이는 타임 슬라이스는 일정하게 유지하면서 선택 빈도를 조절합니다. 여러분이 이 코드를 사용하면 서로 다른 중요도의 태스크들을 효율적으로 관리할 수 있습니다.
시스템 핵심 서비스는 높은 가중치로 빠른 응답성을 유지하고, 부수적인 작업은 낮은 가중치로 백그라운드에서 천천히 실행됩니다.
실전 팁
💡 가중치 범위를 제한하세요. 1~10 정도면 충분하며, 너무 큰 값은 다른 태스크를 사실상 기아 상태로 만들 수 있습니다. 최대 가중치를 100 정도로 제한하는 것이 좋습니다.
💡 동적 우선순위 조정을 구현하면 더욱 공정합니다. 오랫동안 실행되지 못한 태스크의 가중치를 일시적으로 높여주는 aging 기법을 사용하세요.
💡 I/O 바운드 태스크와 CPU 바운드 태스크를 구분하세요. I/O 바운드 태스크는 자주 블로킹되므로 높은 가중치를 줘도 전체 CPU 시간은 많이 안 쓰면서 응답성이 좋아집니다.
💡 실시간 태스크는 별도의 우선순위 큐로 관리하고 라운드 로빈 큐보다 먼저 스케줄링하세요. 하드 리얼타임 보장이 필요한 경우 선점 가능한 최고 우선순위를 부여합니다.
💡 가중치를 너무 자주 변경하지 마세요. 매 스케줄링마다 재계산하면 오버헤드가 큽니다. 초당 한 번 정도 통계를 보고 조정하는 것이 적당합니다.
10. 멀티코어 확장 - Per-CPU 스케줄러
시작하며
여러분이 단일 코어용 스케줄러를 완성했다면, 이제 멀티코어 시스템으로 확장해야 합니다. 현대 CPU는 대부분 4개 이상의 코어를 가지며, 이를 활용하지 않으면 성능의 대부분을 낭비합니다.
단순히 전역 스케줄러를 여러 코어가 공유하면 락 경쟁(lock contention)이 심해집니다. 매 스케줄링마다 락을 획득해야 하므로 병렬성이 크게 떨어집니다.
바로 이럴 때 필요한 것이 Per-CPU 스케줄러 아키텍처입니다. 각 코어마다 독립된 스케줄러와 큐를 유지하여 락 경쟁을 최소화하고, 로드 밸런싱으로 코어 간 작업을 균등하게 분배합니다.
개요
간단히 말해서, Per-CPU 스케줄러는 각 CPU 코어마다 독립적인 스케줄러 인스턴스를 두고, 태스크를 코어별로 할당하여 병렬 실행을 최대화하는 방식입니다. 실무에서는 이것이 멀티코어 성능의 핵심입니다.
예를 들어, 8코어 시스템에서 전역 큐를 사용하면 모든 코어가 큐 락을 기다리며 시간을 낭비합니다. Per-CPU 큐를 사용하면 각 코어가 독립적으로 스케줄링하여 8배의 병렬성을 달성할 수 있습니다.
기존에는 하나의 전역 스케줄러를 공유했다면, 이제는 코어별로 분리하여 확장성을 확보합니다. 핵심 특징은: 1) CPU ID별 스케줄러 배열, 2) 태스크 생성 시 로드 밸런싱으로 코어 선택, 3) 주기적인 워크 스틸링으로 부하 재분배.
이러한 특징들이 멀티코어 시스템의 효율적 활용을 가능하게 합니다.
코드 예제
use core::sync::atomic::{AtomicUsize, Ordering};
const MAX_CPUS: usize = 64;
// CPU별 스케줄러 배열
static mut PER_CPU_SCHEDULERS: [Option<RoundRobinScheduler>; MAX_CPUS]
= [const { None }; MAX_CPUS];
static NEXT_CPU: AtomicUsize = AtomicUsize::new(0);
// 현재 CPU ID 가져오기 (LAPIC에서)
fn current_cpu_id() -> usize {
unsafe {
let apic_id: u32;
core::arch::asm!(
"mov {}, dword ptr [0xFEE00020]",
out(reg) apic_id
);
(apic_id >> 24) as usize
}
}
// 현재 CPU의 스케줄러 가져오기
fn get_scheduler() -> &'static mut RoundRobinScheduler {
let cpu_id = current_cpu_id();
unsafe {
PER_CPU_SCHEDULERS[cpu_id].as_mut()
.expect("Scheduler not initialized for this CPU")
}
}
// 새 태스크를 가장 부하가 적은 CPU에 할당
pub fn add_task_balanced(task_id: TaskId) {
// 라운드 로빈 방식으로 CPU 선택
let cpu_id = NEXT_CPU.fetch_add(1, Ordering::Relaxed) % num_cpus();
unsafe {
if let Some(scheduler) = &mut PER_CPU_SCHEDULERS[cpu_id] {
scheduler.add_task(task_id);
}
}
}
// 워크 스틸링: 다른 CPU의 태스크를 가져오기
fn steal_work() -> Option<TaskId> {
let my_cpu = current_cpu_id();
for cpu_id in 0..num_cpus() {
if cpu_id == my_cpu { continue; }
unsafe {
if let Some(scheduler) = &mut PER_CPU_SCHEDULERS[cpu_id] {
// 큐 크기가 2 이상이면 하나 훔치기
if scheduler.queue_size() > 1 {
return scheduler.steal_task();
}
}
}
}
None
}
설명
이것이 하는 일: 멀티코어 시스템에서 각 코어가 독립적으로 스케줄링하면서도 전체적으로 부하가 균등하게 유지되도록 관리합니다. 첫 번째로, PER_CPU_SCHEDULERS 배열이 각 코어의 스케줄러를 저장합니다.
최대 64개 코어를 지원하도록 고정 크기로 선언했으며, 초기에는 모두 None입니다. 부팅 시 각 코어가 활성화될 때 해당 인덱스에 스케줄러를 생성합니다.
static mut는 unsafe하지만, 각 코어가 자신의 인덱스만 접근하므로 안전합니다. current_cpu_id 함수는 LAPIC ID 레지스터(0xFEE00020)를 읽어 현재 코어 번호를 알아냅니다.
이를 통해 코드가 어느 코어에서 실행 중인지 식별할 수 있습니다. x86_64에서는 LAPIC ID가 고유하므로 코어 식별자로 사용됩니다.
그 다음으로, add_task_balanced는 새 태스크를 할당할 코어를 선택합니다. 가장 간단한 방법은 라운드 로빈으로 순서대로 돌아가며 할당하는 것입니다.
AtomicUsize를 사용하여 여러 코어가 동시에 태스크를 추가해도 충돌 없이 다음 CPU ID를 얻습니다. 더 정교한 방법은 각 코어의 현재 큐 길이를 확인하여 가장 짧은 큐에 추가하는 것입니다.
steal_work는 워크 스틸링을 구현합니다. 자신의 큐가 비었을 때 다른 코어의 큐를 순회하며 태스크를 훔쳐옵니다.
단, 큐 크기가 2 이상일 때만 훔쳐서 다른 코어의 큐를 완전히 비우지 않도록 합니다. 이는 캐시 친화성을 유지하면서도 아이들 코어를 활용합니다.
여러분이 이 코드를 사용하면 멀티코어 시스템의 성능을 최대한 활용할 수 있습니다. 8코어 시스템에서 8개의 CPU 바운드 태스크를 실행하면 이론적으로 8배의 처리량을 달성할 수 있습니다.
각 코어가 독립적으로 스케줄링하므로 락 경쟁이 거의 없어 확장성이 뛰어납니다.
실전 팁
💡 워크 스틸링은 너무 자주 하지 마세요. 매 스케줄링마다 시도하면 오버헤드가 큽니다. 큐가 비었을 때나, 일정 횟수(예: 10번) 아이들 루프를 돈 후에만 시도하세요.
💡 태스크를 특정 코어에 고정(CPU affinity)하는 기능을 추가하면 캐시 히트율이 올라갑니다. 데이터베이스 워커 같은 메모리 집약적 태스크에 유용합니다.
💡 NUMA 시스템에서는 태스크를 가까운 메모리 노드의 코어에 할당하세요. 원격 메모리 접근은 로컬보다 2~3배 느립니다. libnuma 같은 라이브러리를 참고하세요.
💡 코어별 통계를 수집하여 로드 밸런싱을 개선하세요. 각 코어의 실행 시간, 큐 길이, 컨텍스트 스위칭 횟수를 기록하면 병목 지점을 파악할 수 있습니다.
💡 하이퍼스레딩(SMT)이 활성화된 경우 물리 코어와 논리 코어를 구분하세요. 같은 물리 코어의 두 논리 코어는 실행 유닛을 공유하므로 각각을 독립 코어로 취급하면 성능이 오히려 떨어질 수 있습니다.