RM (Rate Monotonic) 스케줄링

핵심 인사이트 (3줄 요약)

본질: RM (Rate Monotonic) 스케줄링은 하드 실시간(Hard Real-time) 시스템에서 **"주기(Period)가 가장 짧은(자주 실행되는) 태스크에 가장 높은 정적 우선순위(Static Priority)를 부여"**하는 선점형 스케줄링 알고리즘이다.

가치: 스케줄러가 런타임에 복잡한 계산을 할 필요 없이 실행 전에 우선순위가 고정되므로 구현이 극도로 단순(오버헤드 최소화)하며, 정적 스케줄링 알고리즘 중에서는 가장 완벽한 수학적 최적(Optimal) 모델로 증명되었다.

융합: 하지만 모든 태스크가 데드라인을 놓치지 않으려면 시스템의 총 CPU 이용률 상한선이 약 **69.3%**를 넘지 않아야 한다는 이론적 한계점(Liu & Layland Bound)을 가지며, 이를 넘는 고부하 환경에서는 동적 스케줄링인 EDF로 전환해야 한다.

Ⅰ. 개요 및 필요성 (Context & Necessity)

개념: "빈도(Rate)가 높을수록 단조롭게(Monotonic) 우선순위를 높인다"는 이름 그대로의 뜻이다. 즉, 10ms마다 한 번씩 실행해야 하는 작업은 100ms마다 실행하는 작업보다 무조건 높은 우선순위를 갖게 되며, 이 순위는 시스템이 켜져 있는 내내 절대 변하지 않는 정적(Static) 알고리즘이다.
필요성: 우주선이나 공장 제어 시스템에는 센서 값을 읽어오는 수십 개의 주기적(Periodic)인 태스크들이 돈다. 스케줄러가 매번 "누가 더 급하지?"를 계산(동적 스케줄링)하려 들면, 그 계산 시간(오버헤드) 자체 때문에 데드라인을 놓치는 참사가 벌어진다. 따라서 아예 컴파일/배포 단계에서 무식하고 확고한 번호표(우선순위)를 붙여주고 런타임에는 꺼내 쓰기만 하는 초경량 스케줄러가 필요했다.
💡 비유: 회사에서 **'매일 아침 보고하는 일일 회의(주기 짧음)'**를 무조건 1순위로 처리하고, **'한 달에 한 번 내는 월간 보고서(주기 긺)'**를 가장 후순위로 미뤄두는 직장인의 **'고정된 업무 우선순위 철칙'**과 같다.
등장 배경: 1973년, 리우(Liu)와 레이랜드(Layland)라는 학자가 발표한 논문에서 기원했다. 그들은 "정적 우선순위 방식 중에서 어떤 규칙으로 순위를 매겨야 데드라인 펑크가 가장 안 날까?"를 수학적으로 파고들었고, 그 결과 "주기가 짧은 놈에게 높은 순위를 주는 것(RM)"이 모든 정적 방식 중 유일한 정답(Optimal)임을 증명해 내며 실시간 OS의 바이블이 되었다.

  [RM 스케줄링의 우선순위 부여 메커니즘]

  [태스크 명세서]
  ▶ 태스크 A: 주기(Period) = 20ms  (자주 함)
  ▶ 태스크 B: 주기(Period) = 50ms  (보통)
  ▶ 태스크 C: 주기(Period) = 100ms (가끔 함)

  [RM 스케줄러의 강제 서열 정리 (배포 시 고정됨)]
  1순위 (VIP): 태스크 A (주기가 제일 짧으니까!)
  2순위      : 태스크 B
  3순위      : 태스크 C (주기가 제일 기니까 양보해)

  >> 실행 중 A의 주기가 돌아오면? B와 C가 뭘 하든 즉시 모가지를 치고(선점) A 실행!

[다이어그램 해설] RM의 철학은 아주 심플하다. 자주 와서 빨리 끝내고 가야 하는 녀석들을 밍기적거리는 큰 놈들 때문에 늦어지게 놔두지 않겠다는 것이다. 이 룰은 시스템이 구동되는 내내 절대 바뀌지 않는다. B가 아무리 데드라인이 1ms 남아서 죽기 직전이라도, 주기가 돌아온 VIP A가 나타나면 무조건 비켜주어야 한다. (이 경직성이 RM의 장점이자 한계다.)

📢 섹션 요약 비유: 매일 먹는 밥 짓기(주기 짧음)는 무조건 청소보다 우선순위가 높습니다. 대청소(주기 긺)를 하다가도 밥 먹을 시간이 되면 무조건 청소기를 내려놓고 밥부터 차려야 가정이 평화롭게 돌아간다는, 변하지 않는 생활 규칙입니다.

Ⅱ. 아키텍처 및 핵심 원리 (Deep Dive)

RM의 깐깐한 간트 차트 (Gantt Chart) 증명

RM이 어떻게 데드라인을 방어하는지 선점형 동작을 살펴본다. (전제: 주기(P) = 데드라인(D)으로 가정)

[시나리오 조건]

태스크 1 (T1): 주기 50, 실행 시간 20 ─▶ 우선순위 High (주기가 짧음)
태스크 2 (T2): 주기 100, 실행 시간 35 ─▶ 우선순위 Low (주기가 긺)

  ┌────────────────────────────────────────────────────────────────────┐
  │         RM 스케줄링 기반의 완벽한 실시간 데드라인 방어 시뮬레이션  │
  ├────────────────────────────────────────────────────────────────────┤
  │                                                                    │
  │  0        20         50        70       85       100 ms            │
  │  │██ T1 ██│░░ T2 ░░░░│██ T1 ██│░░ T2 ░░│        │                  │
  │  (T1 먼저)   (남은시간)  (T1 2주기) (T2 마저) (CPU휴식)            │
  │                                                                    │
  │  [시간별 추적]                                                     │
  │  - 0ms: T1(High)과 T2(Low) 동시 도착. T1 선점 실행 (20ms 완료).    │
  │  - 20ms: T1 끝남. 이제 T2가 실행 시작 (35ms 중 30ms 실행).         │
  │  - 50ms: 🚨 T1의 두 번째 주기가 도래하여 도착!                     │
  │          T2는 아직 5ms 남았지만, T1(VIP)이 왔으므로 강제 쫓겨남.   │
  │  - 70ms: T1 두 번째 실행(20ms) 완료. 다시 T2가 CPU 복귀.           │
  │  - 75ms: T2 마저 5ms 끝내고 총 35ms 완료!                          │
  │                                                                    │
  │  ✅ 결과: T1은 50ms, 100ms 데드라인 안에 여유롭게 완료!            │
  │          T2 역시 100ms 데드라인이 오기 전인 75ms에 무사 완료!      │
  └────────────────────────────────────────────────────────────────────┘

[다이어그램 해설] T2 입장에서는 T1이 올 때마다 비켜줘야 하는 서러운 신세지만, 결국 T2의 마감 시간(100ms)이 오기 전인 75ms 시점에 무사히 자신의 작업을 완료했다. T1의 잦은 인터럽트를 다 받아주고도 시스템이 터지지 않은 것이다.

수학적 한계선: 리우와 레이랜드의 상한 (Liu & Layland Bound)

그렇다면 RM으로 아무 태스크나 다 방어할 수 있을까? 절대 아니다. CPU가 견딜 수 있는 한계 이용률(Utilization) 공식이 존재한다.

CPU 이용률 ($U$) = $\sum \frac{실행시간(C)}{주기(P)}$
RM의 성공 보장 공식: $U \le N(2^{1/N} - 1)$ (N은 태스크의 개수)

태스크 개수 (N)	RM이 데드라인 100% 보장하는 최대 CPU 이용률
N = 1	1.0 (100%)
N = 2	0.828 (82.8%)
N = 3	0.779 (77.9%)
N → $\infty$	0.693 (약 69.3%)

[해석] 이것이 RM 스케줄링의 위대한 발견이자 뼈아픈 족쇄다. 시스템 설계자가 CPU를 70% 미만으로 널널하게 쓰도록 태스크를 배치했다면, RM은 무조건 100% 데드라인 방어를 수학적으로 개런티한다. 하지만 CPU를 80%, 90%까지 쥐어짜려 든다면 RM은 가차 없이 데드라인을 펑크 내며 시스템을 붕괴시킨다.

📢 섹션 요약 비유: RM이라는 가방(스케줄러)은 참 튼튼하고 가볍지만, 가방 용량의 딱 69%까지만 짐(CPU 부하)을 넣었을 때 절대 안 찢어진다는 품질 보증서가 붙어있습니다. 80%를 넣으면 찢어질 수도 있고 안 찢어질 수도 있는 도박이 됩니다.

Ⅲ. 융합 비교 및 다각도 분석 (Comparison & Synergy)

정적 우선순위 (RM) vs 동적 우선순위 (EDF)

가장 완벽한 라이벌이자 실시간 스케줄링의 양대 산맥이다.

비교 항목	RM (Rate Monotonic)	EDF (Earliest Deadline First)
우선순위 결정	배포 전 고정 (정적, Static)	런타임 매 순간 계산 (동적, Dynamic)
선택 기준	주기가 무조건 짧은 놈	지금 당장 데드라인이 제일 코앞인 놈
구현 오버헤드	극도로 낮음 O(1). 우선순위 큐 1개면 됨	높음 O(N) 또는 O(log N). 매번 재정렬 필요
CPU 이용률 한계	약 69% (자원 낭비 30% 발생)	이론상 100% (자원을 극한까지 쥐어짬)
과부하 시 동작	예측 가능 (Predictable). 무조건 주기가 긴 하위 태스크부터 희생됨	도미노 붕괴 현상 (Domino Effect). 누가 죽을지 예측 불가능하며 다 같이 죽을 수도 있음

과부하(Overload) 상황에서의 RM의 압도적 승리

이용률 한계가 69%밖에 안 되는 바보 같은 RM이 왜 산업계의 절대적 지지를 받을까? 장애가 났을 때 예측이 가능하기 때문이다. 시스템이 폭주하면 RM은 무조건 "주기가 가장 긴(우선순위가 제일 낮은) 녀석"부터 펑크가 난다. 항공기 설계자는 주기가 긴 '실내 온도 조절기'가 꺼지는 한이 있더라도, 주기가 짧은 '엔진 제어기(VIP)'는 절대 살릴 수 있다는 확신을 가질 수 있다. 반면 EDF는 다 같이 데드라인이 코앞으로 몰리며 우르르 도미노처럼 펑크를 내버려 엔진 제어기마저 죽일 위험이 있다.

📢 섹션 요약 비유: 비행기에 구멍이 나서 짐을 버려야 할 때(과부하), RM은 짐에 미리 1, 2, 3등급 스티커(정적 순위)가 붙어 있어서 고민 1초도 안 하고 3등급 짐부터 확 버립니다. EDF는 그 급박한 상황에 "어떤 짐이 당장 상할까?"를 짐마다 다시 계산하다가 비행기째로 추락합니다.

Ⅳ. 실무 적용 및 기술사적 판단 (Strategy & Decision)

실무 시나리오

임베디드 RTOS (FreeRTOS)의 태스크 설계: 마이크로컨트롤러(MCU) 레벨의 초소형 기기(드론, 스마트워치)를 개발할 때, 개발자는 FreeRTOS에서 xTaskCreate 함수로 태스크를 만들며 직접 우선순위 정수(1~40)를 하드코딩해야 한다.
- 아키텍처 결단: 이때 개발자 맘대로 "이게 중요해 보이니까 1등!"이라고 적으면 시스템이 무너진다. 반드시 RM 철학에 입각하여, 1ms마다 자이로 센서를 읽는 태스크에 최우선순위(40)를 주고, 100ms마다 화면을 갱신하는 태스크에 중간 순위(20)를 주며, 1초마다 로그를 남기는 작업에 바닥 순위(1)를 하드코딩해야만 시스템 데드라인이 수학적으로 꼬이지 않는다. (RM을 따르지 않으면 데드락과 펑크 지옥이 열린다).
리눅스 SCHED_FIFO와 RM의 매핑: 현대 범용 리눅스에서 실시간 태스크를 띄울 때 사용하는 정책인 SCHED_FIFO나 SCHED_RR은 근본적으로 '정적 우선순위 스케줄링'이다. 즉, 개발자가 커널 공간에 RM 알고리즘을 흉내 내어 구축하고 싶다면, 주기적 태스크들의 주기를 계산한 다음, 주기가 짧은 데몬(프로세스)에게 chrt 명령어로 더 높은 우선순위(Priority 99)를 수동으로 매핑해 주면 리눅스 스케줄러가 알아서 RM처럼 동작하게 된다.

  ┌─────────────────────────────────────────────────────────────────┐
  │     실시간 시스템(RTOS)의 수학적 승인 제어 (Admission Control)  │
  ├─────────────────────────────────────────────────────────────────┤
  │                                                                 │
  │   [신규 기능 추가: 카메라 프레임 분석 (주기 30ms, 연산 10ms)]   │
  │                                                                 │
  │   1. 아키텍트의 수식 검증 (RM Bound 확인)                       │
  │      기존 CPU 이용률: 55%                                       │
  │      신규 태스크 이용률: (10 / 30) = 33%                        │
  │      총합 이용률 = 88% ( 🚨 69.3% 한계선 돌파! )                │
  │                                                                 │
  │   2. 의사결정 분기 (Decision)                                   │
  │      ├─▶ "안돼! 88%면 RM의 100% 방어선(69%)이 깨져!"            │
  │      │   기능 배포 거부(Reject) 또는 CPU 클럭 강제 업그레이드.  │
  │      │                                                          │
  │      └─▶ "그래도 돌려보고 싶으면, 오버헤드 감수하고 EDF로 바꿔" │
  │          (EDF는 이론상 100% 방어 가능. 단, 장애 시 도미노 위험) │
  └─────────────────────────────────────────────────────────────────┘

[다이어그램 해설] 이것이 일반 웹 개발(IT)과 임베디드 실시간 개발(OT)의 좁힐 수 없는 격차다. 웹 백엔드는 서버가 80% 차면 "조금 느려지겠네" 하고 넘기지만, 실시간 세계에서는 RM 공식 한계치인 69%를 넘기는 순간 그것을 명백한 '살인 무기(언제든 통제 불능이 될 수 있음)'로 간주하여 코드 배포 자체를 원천 봉쇄(Admission Fail)해 버린다.

📢 섹션 요약 비유: 엘리베이터(CPU) 정원이 100명이어도, RM 규칙은 "혹시 모를 뚱뚱한 사람(최악 실행 시간)이나 돌발 행동을 대비해 무조건 69명까지만 태워라. 그래야 절대 안 끊어지는 완벽한 밧줄 보증서가 유효하다"라고 못 박는 철저한 안전제일주의입니다.

Ⅴ. 기대효과 및 결론 (Future & Standard)

기대효과

RM 스케줄링을 채택하면 운영체제 커널의 코드를 단 몇 백 줄의 단순한 '우선순위 기반 큐'로 극한의 다이어트를 시킬 수 있으며, 이로 인해 디스패치 지연 시간이 마이크로초 단위로 고정되어 시스템의 결정론(Determinism)과 강건성(Robustness)이 우주항공 레벨로 극대화된다.

결론 및 미래 전망

RM (Rate Monotonic)은 1970년대에 증명된 오래된 공식이지만, "오버헤드가 없고, 장애 시 피해 태스크를 명확히 꼬리 자르기 할 수 있다"는 압도적 실무적 강점 덕분에 현재 화성에 떠 있는 로버(큐리오시티)와 여러분 차에 달린 ECU(엔진 제어기)의 90% 이상을 지배하고 있는 진정한 실시간의 황제다. 미래의 멀티코어 환경에서는 코어별로 RM 스케줄링을 격리 파티셔닝(Partitioned RM)하여 캐시 파괴를 막는 기술이 최신 자동차의 통합 제어기(APU) 아키텍처로 연구 및 상용화되고 있다.

📢 섹션 요약 비유: RM은 화려한 인공지능이나 복잡한 계산식 없이, "제일 자주 오는 놈 무조건 1등!"이라는 초등학생도 이해할 단순한 룰 하나로 수십 년간 인류의 우주선과 미사일의 멱살을 잡고 추락 없이 이끌어온 가장 위대하고 투박한 지혜입니다.

📌 관련 개념 맵 (Knowledge Graph)

개념 명칭	관계 및 시너지 설명
EDF (Earliest Deadline First)	RM의 영원한 라이벌로, CPU를 100% 쥐어짜는 효율을 가졌으나 런타임 계산이 너무 무거워(동적) 실무에서 RM에게 밀린 비운의 천재다.
우선순위 스케줄링 (Priority)	RM이 시스템을 통제하기 위해 사용하는 껍데기(Mechanism). 즉 RM은 주기를 기준으로 우선순위를 매기는 '정책(Policy)'이다.
선점형 커널 (Preemptive)	주기가 짧은 VIP가 도착했을 때 즉각 모가지를 치고 들어갈 수 있게 해주는 RM의 핵심 행동대장이다.
리우-레이랜드 상한 (Liu-Layland Bound)	RM이 데드라인을 완벽히 막아줄 수 있는 CPU 점유율의 마지노선(약 69%)으로, 실시간 시스템 설계자들의 암기 필수 공식이다.
최악 실행 시간 (WCET)	RM 공식을 계산할 때 분자 값(C)으로 들어가는 값. 평균 시간이 아니라 천재지변이 일어났을 때 걸리는 최악의 시간을 넣어야 보증이 성립한다.

👶 어린이를 위한 3줄 비유 설명

숙제를 할 때, RM 스케줄링은 "매일매일 제출해야 하는 일기 쓰기(주기 짧음)"를 무조건 1등으로, "한 달에 한 번 내는 독후감(주기 긺)"을 무조건 꼴찌로 순서를 딱 고정해버려요.
매일 고민할 필요 없이 정해진 이 규칙대로만 착착 기계처럼 숙제를 하면, 머리 아프게 생각할 시간(오버헤드)이 아껴져서 절대 펑크 낼 일이 없어요.
단, 이 규칙이 완벽하게 통하려면 내 전체 시간의 69% 정도까지만 숙제가 꽉 차 있어야 해요. 숙제가 너무 많으면 이 규칙만으론 결국 독후감 제출 날짜를 놓쳐버리게 된답니다!