RSoC 2026: Redox OS를 위한 새로운 CPU 스케줄러

글쓴이: Akshit Gaur

2026년 4월 2일

안녕하세요! 저는 Akshit Gaur입니다. 현재 Redox Summer of Code 프로그램의 지원을 받아 Redox OS의 프로세스 스케줄링 서브시스템을 현대화하는 작업을 진행 중입니다.

요약

기존의 Round Robin 스케줄러를 Deficit Weighted Round Robin 스케줄러로 교체했습니다. 덕분에 프로세스 컨텍스트에 우선순위를 할당할 수 있게 되었어요. 가벼운 부하에서는 차이가 거의 드러나지 않지만, 높은 부하 상황에서는 구형 스케줄러보다 훨씬 잘 작동합니다. 예를 들어 Redox의 pixelcannon 3D 데모에서는 약 150 FPS의 성능 향상을 보였고, CPU 집약적 작업의 처리량은 약 1.5배 증가했으며, 반응성도 비슷한 수준으로 개선되었습니다(schedrs로 측정함).

Round Robin 스케줄러의 한계

Redox OS는 현재 단순한 Round Robin(RR) 스케줄러를 사용하고 있습니다.

이걸 이렇게 생각해보세요. 여러분이 술집에 친구들과 앉아있는데, 오늘 밤 모든 음료가 무료라고 합시다. 그 결과 바텐더 수가 손님에 비해 크게 부족한 상황이 되었어요. 바텐더들은 왼쪽부터 시작해서 손님을 한 명씩 서빙하고 오른쪽으로 움직입니다.

어떤 손님들은 음료를 천천히 마셔서 바텐더가 돌아올 때도 여전히 잔이 남아있어요. 결국 모든 손님이 매번 새로운 음료를 원하지는 않음에도 불구하고, 바텐더들은 여전히 그들을 확인해야 하고 이는 시스템 비효율을 낳습니다.

이 방식도 그럭저럭 작동합니다. 손님들은 기다리긴 하지만 모두가 같은 시간만큼 기다리니까요. 그래서 누구나 어느 정도는 만족합니다. 최소한 동등하게 불만족하죠.

그런데 문제는 지역 정치인 한 명이 오늘 손님으로 와있다는 겁니다. 성격은 까칠하고 자존심은 엄청 큰 사람이죠. 불쌍한 바텐더들이 평소대로 이 VIP를 다른 손님과 똑같이 대하면, 이 정치인은 바텐더들에게 sigterm을 날릴 겁니다. 하지만 프로토콜에 얽혀서 바텐더들은 다른 선택지가 없고, 결국 이 VIP가 분노로 끓어오르는 동안 무한 루프에 갇힙니다.

운영체제로 비유하면, 이 VIP 손님은 우선순위가 높은 I/O 바운드 대화형 프로세스입니다(예: 오디오 스택처럼 아주 작은 지연도 청각적 왜곡을 야기할 수 있는 것들이죠). 만약 이런 프로세스가 CPU를 집어먹는 백그라운드 작업 뒤에서 RR 큐에서 대기하면, 사용자는 시스템이 반응하지 않는다고 느껴져 결국 자식 프로세스들을 sigkill로 죽입니다.

Deficit Weighted Round Robin 스케줄러 등장

술집에서의 대참사 이후, 무료 음료 행사는 끝났습니다. 하지만 바텐더들은 무료 음료를 정말 주고 싶어 하는 사람들이라 새로운 솔루션을 생각해냈어요!

그들은 3개의 토큰 자판기를 설치했습니다. 각각 초당 1개, 2개, 4개의 토큰을 배출합니다. 이 자판기마다 큐(A, B, C)가 형성되고, 보안요원이 각 손님을 적절한 큐로 배정합니다. 맥주의 가격이 토큰 2개로 정해졌으니까, A 큐에 선 손님은 2틱을 기다려야 떠날 수 있고, C 큐에 선 손님은 단 1틱 안에 맥주 2잔을 구매할 수 있어요. 그 다음 손님은 큐에서 나가 맥주를 "구매"합니다!

VIP 문제는 이제 해결됐어요! VIP가 도착하면 보안요원이 즉시 C 큐로 보내고, 다른 두 큐의 모든 사람들은 나중으로 미뤄집니다.

하지만 새로운 문제가생겼습니다. 바로 기아 상태(starvation)인데요. C 큐가 출구에 가장 가깝고, B가 그 다음, A가 가장 멀거든요. 모든 큐의 사람들이 잔액을 충분히 쌓아서 떠나고 싶어 하면, 항상 C에 있는 사람이 가장 먼저 나갑니다. 이게 문제죠! C 큐에 사람이 많으면, A와 B 큐의 사람들은 영원히 맥주를 사지 못하고 기아로 죽게 됩니다!

Deficit Weighted Round Robin(DWRR) 스케줄러는 프로세스들을 여러 큐로 그룹화하고 각 큐에 우선순위를 부여합니다. 컨텍스트 스위치가 일어날 때마다, 스케줄러는 가장 높은 우선순위 큐부터 시작해서 그 큐의 가중치를 잔액에 더합니다. 그리고 잔액이 기본 가격 이하로 떨어질 때까지 그 큐의 작업들을 계속 실행한 후, 다음 큐로 넘어갑니다.

이 방식은 높은 우선순위 프로세스를 올바르게 우선시하지만, 낮은 우선순위 프로세스의 기아 상태와 높은 지연시간을 초래할 수 있습니다.

인터리빙(Interleaving)으로 균형 맞추기

VIP의 필요를 해치지 않으면서 기아 문제를 해결하려면, 인터리빙 방식으로 옮겨가야 합니다. 한 큐가 잔액을 전부 소진하는 대신, 스케줄러가 작업을 "인터리빙"합니다.

바텐더들이 VIP 큐에 한 라운드를 서빙하고, 그 다음 즉시 낮은 우선순위 큐의 누군가가 단 한 잔이라도 살 수 있는 충분한 토큰을 가지고 있는지 확인한 후, 다시 VIP에게 돌아가는 식이라고 생각하면 됩니다.

이 방식은 컨텍스트 스위치 오버헤드가 약간 증가하지만, 지연시간 개선 효과는 무시할 수 없습니다.

자세한 내용은 [Wikipedia에서 비교 글을 읽어보세요](https://en.wikipedia.org/wiki/Deficit_Round_Robin).

설정 방법

스케줄러

Redox OS를 설정한 후 빌드되는지 확인했다면, [이 커널 MR](https://github.com/redox-os/kernel/pulls)을 체크아웃하세요. 첫 번째 댓글에 언급된 모든 관련 MR들도 함께 봐야 합니다.

테스트해보려면 redox_syscall과 libredox 라이브러리 저장소(관련 MR에 명시되어 있음)를 recipes/core에 클론해야 합니다.

디렉토리 구조는 다음과 같아야 해요:

akshit@laptop ~/w/r/r/r/core> ls
base/ binutils/ contain/ dash/ findutils/ ion/ libredox/ netutils/ pkgutils/ redoxfs/