RTOS Kernel Scheduling Mechanics

1. Overview

RTOS 커널 스케줄링 메커니즘(RTOS Kernel Scheduling Mechanics)은 범용 OS(리눅스/윈도우)의 '완벽한 공정성(Fairness)'이라는 환상을 집어 던지고, 사람이 죽고 사는 하드 리얼타임(Hard Real-Time) 환경에서 **"우선순위가 가장 높은 단 하나의 태스크(스레드)에게 모든 CPU 권력을 몰아주는 물리적 폭정(Tyranny)"**을 관철하는 코어 역학입니다.

학습자는 RTOS 커널이 타이머 인터럽트(Tick)마다 개입하여 TCB(Task Control Block)를 뒤지고 스택 레지스터를 강제로 덮어씌우는 **선점형 컨텍스트 스위칭(Preemptive Context Switching)**의 어셈블리 궤적을 뜯어봅니다. 나아가 모든 태스크의 상태 머신(Ready, Running, Blocked)을 O(1) 시간 복잡도로 빠르게 검색하는 비트맵 스케줄러(Bitmap Scheduler) 알고리즘과 타임 슬라이싱(Time-Slicing)의 타협점을 해부하여, 로봇 팔과 비행 제어 시스템의 흔들림 없는 두뇌(Kernel)를 직접 컴파일하는 아키텍트 역량을 확보합니다.

2. Scope & Boundaries

In-Scope

• 커널 오브젝트(Kernel Objects): 태스크 제어 블록(TCB), 스레드 개별 스택(Stack) 영역 할당, 문맥 저장(Context Save).
• 선점형 스케줄러 알고리즘: 비트맵 우선순위 큐(Bitmap Priority Queue), O(1) 스케줄링 찾기(Count Leading Zeros).
• 상태 전이(State Machine): Ready(대기), Running(실행), Blocked(봉쇄/지연), Suspended(정지) 구조.
• 틱 인터럽트(Tick Interrupt): SysTick을 기반으로 커널이 강제 진입(Trap)하여 라운드 로빈(Round Robin)과 슬립 타이머를 차감하는 물리적 심장 박동.

Out-of-Scope

• 멀티코어 비대칭 스케줄링: big.LITTLE 프로세서 간의 스레드 마이그레이션(Migration) $\rightarrow$ 02-05-03. System-on-Chip (SoC) Architecture 영역.
• 뮤텍스 및 메시지 통신: 태스크 간의 큐(Queue) 통신과 우선순위 역전 문제 $\rightarrow$ 02-06-02. Priority Inversion & Inheritance Physics 영역.

Boundaries

• RTOS vs. Linux Scheduler (03-01-01): 리눅스의 CFS(03-01-01) 스케줄러가 "모든 프로세스가 CPU를 똑같이 1/N씩 나눠 갖게 하려는 우파/좌파 밸런스 정치"라면, RTOS 스케줄러는 "1순위 장군이 일이 끝날 때까지 99명의 쫄병은 단 1클럭의 CPU도 받지 못하고 굶어 죽어도(Starvation) 상관없는 완벽한 계급 독재"입니다.

3. Counterexample

• 빠른 속도에 대한 착각 (Throughput Fallacy): "RTOS를 올리면 베어메탈(while(1) 루프)보다 내 코드가 훨씬 빨리 돌겠지?"라고 믿는 초보자의 망상. RTOS 커널이 1밀리초마다 틱(Tick)을 발생시키고 스레드 상태를 점검하며 TCB를 뒤지는 연산 자체가 엄청난 오버헤드입니다. 즉, 전체 연산량(Throughput)은 깡통 루프보다 무조건 박살 납니다. RTOS의 존재 이유는 스피드가 아니라 "중요한 일이 터지면 하던 걸 즉각 버리고 0.01초 안에 반응하겠다"는 타이밍 결정성(Determinism)입니다.
• 블로킹 없는 무한 루프의 재앙 (Starvation Attack): 가장 우선순위가 높은 센서 태스크(Priority 1) 안에서 delay()나 큐 대기(QueueReceive) 같은 블로킹(OS 양보) 함수를 호출하지 않고, 쌩 C언어 배열 계산을 돌리며 while(1)을 빙빙 도는 치명적 폭주. RTOS 철칙에 따라 1순위 태스크가 Ready 상태로 살아있는 한, 하위(2순위, 3순위) 통신 태스크나 화면 그리기 태스크는 영원히 CPU를 선점(Preemption)하지 못하고 시스템 전체가 센서 연산에 갇혀 완전히 멈춰버립니다(Starvation).

4. Prerequisites

• 인터럽트와 스택 역학 (Basic): 틱 타이머(SysTick) 인터럽트가 터졌을 때 R0~R15 레지스터가 스택 메모리에 Push/Pop 되는 기하학적 이미지를 알아야 컨텍스트 스위칭을 이해할 수 있습니다. (02-05-03 Interrupt Latency)
• 자료구조 (Recommended): 태스크들을 관리하는 큐(Queue)와 비트 연산(Bitwise) 기법을 알아야 O(1) 스케줄러를 장악할 수 있습니다.

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 스레드의 자아 분열, TCB와 스택 물리 (TCB & Stack Memory)

• Why to Learn: 무한 루프 1개로 돌던 베어메탈에서 벗어나, 3개의 함수가 마치 3개의 CPU를 가진 것처럼 멈춘 곳에서 다시 시작하는 독립적 시공간(스레드)을 창조하기 위함입니다.
• What to Learn:
  • Concepts: 스레드(Thread), TCB(Task Control Block), 태스크 스택(Task Stack).
  • Skills: 스택 할당(Stack Allocation), 스택 오버플로우 트래킹(Watermark).
  • Tools: 램(RAM) 맵핑 분석, FreeRTOS xTaskCreate().
  • Trade-offs: 태스크를 10개 만들면 모듈화가 극에 달해 코드가 아름다워지지만, 각 태스크마다 상태(함수 지역변수, 리턴 주소)를 백업할 독립된 스택(최소 256Byte~1KB)을 램에서 강제로 뜯어내어 쥐여줘야 하므로, 32KB짜리 MCU 램(RAM)이 단 며칠 만에 고갈되는 치명적인 메모리 지출.
• How to Learn:
  • 1단계: 태스크 A가 함수 안에서 int a=5;를 선언하고 대기(Block) 상태로 빠질 때, 그 a=5라는 값과 "내가 어디까지 실행했었지?(PC 주소)"를 온전히 보존하기 위해, OS 커널이 램 공간 일부를 떼어내어 TCB 구조체 안의 Stack Pointer로 묶어두는 개인 금고(Stack) 물리를 해부합니다.
  • 2단계: 태스크 스택을 너무 작게 잡으면 배열 하나 선언하는 순간 램 경계를 뚫고 나가 다른 태스크의 메모리를 덮어써서(Stack Overflow) 디버깅 불가능한 우주 급 충돌이 일어나는 재앙을 뜯어봅니다.
• Implement: 파이썬으로 가상의 램 버퍼 배열을 만들고, 3개의 TCB 딕셔너리를 생성하여 각자 Stack_Base와 Stack_Pointer 범위를 할당. 태스크 1번이 스택 범위를 초과해(SP > Limit) 2번 태스크의 램 구역을 침범(Corruption)했을 때 커널 스레드가 워터마크를 검사하여 STACK_OVERFLOW_PANIC을 때리는 메모리 폭파 시뮬레이션.

Recommended

Core Topic 02: 멱살잡이와 레지스터 덮어쓰기, 컨텍스트 스위칭 (Context Switching)

• Why to Learn: CPU 코어는 1개인데 태스크가 3개일 때, OS가 어떻게 수만 번 찰나의 순간마다 태스크의 '뇌(레지스터)'를 바꿔치기하여 완벽한 멀티태스킹 환상을 만들어내는지 그 어셈블리 궤적을 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 컨텍스트 스위칭(Context Switching), 선점(Preemption), 트랩(Trap / PendSV 인터럽트).
  • Skills: 레지스터 PUSH/POP(R0~R15), 프로그램 카운터(PC) 스와핑(Swapping).
  • Tools: ARM 어셈블리 덤프 분석.
  • Trade-offs: 컨텍스트 스위칭 주기를 0.1밀리초(10KHz)로 극단적으로 짧게 잡으면 스레드 간 전환이 솜털처럼 부드러워지지만, 스위칭에 들어가는 PUSH/POP 연산 오버헤드 때문에 정작 유효한 비즈니스 로직(실제 수학 계산)을 돌릴 CPU 시간이 통째로 증발해 버리는(Thrashing) 오버헤드 붕괴.
• How to Learn:
  • 1단계: 1순위 태스크 B가 깨어나는 순간, 스케줄러 인터럽트(PendSV)가 Nap을 자르듯 강제 개입하여 현재 돌고 있던 2순위 태스크 A의 심장(R0~R15 상태)을 모조리 A의 스택에 백업(PUSH)해 버리는 폭력적인 선점(Preemption) 물리를 해부합니다.
  • 2단계: 그런 다음, 커널이 TCB 배열을 뒤져 태스크 B의 스택 주소를 찾아내고, 거기 잠들어 있던 옛날 레지스터 상태들을 다시 뽑아내어(POP) 실제 CPU 코어에 덮어쓴 뒤 Return을 갈겨 B가 멈췄던 주소로 점프해 버리는 기하학을 뜯어봅니다.
• Implement: 16칸짜리 배열(CPU 레지스터 R0~R15)을 가진 파이썬 클래스에서, Switch_Context(TaskA, TaskB) 함수가 호출될 때 CPU 배열의 데이터를 TaskA.stack_array로 copy() 하고, 즉시 TaskB.stack_array 데이터를 CPU 배열로 overwrite() 하여 스레드 흐름이 완전히 B로 넘어가 텍스트를 출력하는 메모리 스왑 데모 작성.

Practical

Core Topic 03: 극강의 결정성 탐색, O(1) 비트맵 스케줄러 (Bitmap Scheduler)

• Why to Learn: 태스크가 64개나 떠 있을 때, OS가 가장 우선순위가 높은 놈을 찾기 위해 배열 루프를 돌며 검색하면 O(N)의 시간이 걸려 지터(Jitter)가 박살 나므로, 단 1클럭 만에 1등을 찾아내는 기적의 알고리즘을 쥐기 위함입니다.
• What to Learn:
  • Concepts: 준비 큐(Ready Queue), 비트맵(Bitmap), O(1) 스케줄링.
  • Skills: CLZ(Count Leading Zeros) 어셈블리 명령어, 비트 연산 마스킹.
  • Tools: 스케줄러 알고리즘 효율성 프로파일러.
  • Trade-offs: C언어 배열(List)로 레디 큐를 짜면 구현이 편하고 태스크를 무한정 만들 수 있지만, 비트맵 스케줄러를 쓰면 O(1) 결정성은 극강으로 잡는 대신 32비트 CPU에서는 우선순위 레벨을 딱 32단계(0~31)까지만 제한적으로 쪼갤 수 있는(Word size bound) 수학적 한계.
• How to Learn:
  • 1단계: 각 우선순위(0~31)마다 대기 중인 태스크가 있으면 1, 없으면 0을 표시하는 32비트짜리 정수 변수(비트맵 Ready_Bit) 하나로 시스템 전체의 대기 상태를 압축(Compression)하는 자료구조를 해부합니다.
  • 2단계: Ready_Bit = 0b00100100 (우선순위 5번과 2번이 대기 중)일 때, ARM 칩에 내장된 하드웨어 덧셈기(CLZ 명령어)를 딱 1번 호출하면 가장 앞의 1(즉, 5번) 위치를 1클럭 만에 찾아내어 O(1) 레이턴시를 완성해 버리는 흑마법을 뜯어봅니다.
• Implement: 64비트 정수를 활용하는 파이썬 스케줄러 탐색 엔진 시뮬레이션. Tasks = [Priority 3, Priority 12, Priority 63]이 레디(Ready)되었을 때, for 루프 탐색(O(N))과 64 - len(bin(bitmap))를 활용한 비트 연산 탐색(O(1))의 수행 소요 시간(Tick)을 극단적으로 대조하여 출력하는 알고리즘 벤치마크.

Advanced

Core Topic 04: 심장 박동과 라운드 로빈 통제망 (Tick & Time-Slicing)

• Why to Learn: "3초 뒤에 이 모터를 꺼라"라는 지시를 내렸을 때, 커널이 어떻게 그 '3초'를 인식하고 자고 있던 태스크를 깨우는지, 시스템의 물리적 심장인 '틱(Tick)'의 생명 유지 장치를 장악하기 위해서입니다.
• What to Learn:
  • Concepts: 커널 틱(Kernel Tick), 타임 슬라이스(Time-Slice), 라운드 로빈(Round Robin 스케줄링), 틱리스 대기(Tickless Idle).
  • Skills: 하드웨어 타이머(SysTick) 세팅, 딜레이 리스트(Delayed List) 갱신 연산.
  • Tools: RTOS Tick Hook, 전력 분석기.
  • Trade-offs: 틱(Tick)을 1초에 1,000번(1ms 주기) 울리게 세팅하면 시간 단위가 정밀해져 반응성이 끝내주지만, CPU가 1초에 1,000번씩 강제로 하던 일을 멈추고 OS 커널로 불려 들어가 딜레이 리스트(차감 연산)를 계산하느라 시스템 낭비가 터짐 vs 틱을 10ms로 늘리면 랙이 걸려 로봇 팔이 덜덜 떨리는 주파수 딜레마.
• How to Learn:
  • 1단계: 태스크가 vTaskDelay(500)을 선언하고 블록(Blocked) 상태로 자러 가면, 커널은 이 놈을 '딜레이 리스트'에 박아놓고 매 1ms(Tick) 타이머 인터럽트가 터질 때마다 이 카운터를 1씩 깎다가 0이 되는 순간 Ready 큐로 강제 귀환시키는 역학을 해부합니다.
  • 2단계: 우선순위 1등인 태스크가 하필 2개(A와 B)가 동시에 떠 있을 때, OS가 매 틱(Tick) 인터럽트마다 A의 멱살을 잡고 B를 덮어씌우며 서로 평등하게 시분할(Time-Slicing, 라운드 로빈)해 버리는 공산주의적 타협 모드를 뜯어봅니다.
• Implement: 메인 Tick_Timer 쓰레드가 0.1초마다 펄스를 발생시키고, TaskA(우선순위 1, 3틱 대기), TaskB(우선순위 1, 5틱 대기) 객체들이 틱을 맞을 때마다 내부 sleep_counter를 깎는 이벤트 루프 구축. 카운터가 0이 되어 Ready 상태로 복귀하면 우선순위에 따라 스케줄러가 콘솔에 [Tick 30] TaskA Wakeup!을 비동기적으로 터트리는 RTOS 심장 박동 모사.

7. Terminology

8. References

Primary

• [P2] SWEBOK v4.0 - Computing Foundations / Real-Time Systems — Standard categories.
• [P1] CS2023 - AR/Embedded Systems & RTOS — Core requirements.

Secondary

• [MicroC/OS-II: The Real-Time Kernel] Jean Labrosse — The definitive kernel mechanics book.
• [Real-Time Concepts for Embedded Systems] Qing Li — Practical RTOS implementation.

Industry

• [FreeRTOS: Implementation & Scheduling internals] — The industry standard open-source logic.
• [POSIX 1003.1b: Real-time Extensions] — The formal API and behavioral standard.

9. Final Checklist

Primary

• RTOS 커널이 선순점 우선순위 작업을 찾기 위해 'Ready List'를 탐색할 때, 태스크 수에 상관없이 시간 복잡도가 일정해야 하는 물리적 이유를 설명 가능한가? (P1)
• 하드웨어 타이머(SysTick)의 주기가 너무 짧아지면 전체 연산 속도(Throughput)가 왜 물리적으로 급감하는지 오버헤드 관점에서 입증할 수 있는 가? (P1)

Secondary

• '문맥 교환' 중 인터럽트가 수 밀리초 동안 비활성화된다면, 외부 센서 신호의 누락(Lost Event) 가능성을 수리적으로 도출할 수 있는 가?
• 태스크의 'Blocked' 상태가 왜 CPU 자원을 전혀 소모하지 않는 물리적 휴지기로 이어지는지 스케줄러의 태스크 스킵 로직을 소통 가능한가?

Industry

• 무인 드론의 비행 제어 시스템 설계 시, 범용 Linux 대신 RTOS를 사용해야 하는 물리적 '반응성 확정성(Predictability)' 근거를 제안할 수 있는 가? (SFIA)
• 전력 소모가 극도로 적은 웨어러블 기기에서 'Tick리스' 커널이 배터리 수명을 물리적으로 연장하는 원리를 전압 신호 관점에서 기술할 수 있는 가?