스케줄링 알고리즘 분류 (Typology of Real-Time Scheduling Algorithms) — 실시간 스케줄링 알고리즘을 실행 시점(Offline/Online)과 우선순위 부여 방식(Task-level / Job-level · Fixed / Dynamic)에 따라 체계화하는 분류 체계.
스케줄링의 두 축
스케줄링은 워크로드(Task, Message)를 자원(CPU, Network)에 할당하는 일. 단일 자원이냐 다중 자원이냐에 따라 할당 축이 달라진다.
| 자원 상황 | 할당 축 |
|---|---|
| 단일 자원 | Time-domain scheduling — 워크로드에 시간 슬롯만 배정 |
| 다중 자원 | Space-domain (워크로드 → 자원 배정) + Time-domain scheduling 동시 |
Real-Time vs Non-Real-Time 스케줄링
| 구분 | 목표 | 예시 |
|---|---|---|
| Real-Time | 태스크의 데드라인 만족 | RTOS 스케줄링 |
| Non-Real-Time | N개 프로세스에 N개의 가상 CPU 환상 제공 (공정한 분배) | Linux CFS (Completely Fair) |
스케줄링 목표 (Objectives of Scheduling)
여러 목표가 서로 상충한다. 어떤 목표를 우선할지에 따라 알고리즘이 달라진다.
| 목표 | 의미 |
|---|---|
| Fairness | 모든 프로세스에 동등한 분배 |
| No starvation | 모든 프로세스가 최소한의 CPU는 받음 |
| High throughput | 단위 시간당 완료 Job/instruction 최대화 |
| High utilization | CPU 사용률 100%에 근접 |
| Small latency | 입력→출력 지연 최소화 |
| High interactivity | 사용자 체감 지연 없음 |
| Deadline guarantee | 약속된 시간 내 완료 — 실시간 시스템의 핵심 목표 |
| Predictability | 이해 가능한 스케줄링 동작 |
| Flexibility | 워크로드 변경에도 잘 동작 |
어느 알고리즘이 좋은가?
주기 태스크에 대해,
- 알고리즘 A: 거의 모든 Job을 10ms에 완료
- 알고리즘 B: 모든 Job을 99ms에 완료
실시간 관점에서는 B가 더 우수하다. 데드라인(100ms)을 항상 만족하고 예측 가능하기 때문이다. A는 평균 성능은 좋지만 drift가 가능.
전체 분류 체계
Real-Time Scheduling Algorithms
├── Offline
│ └── Cyclic scheduling
└── Online
├── Weighted Round-Robin
└── Priority-driven
├── Task-level Fixed Priority (TFP) ... RM, DM
├── Job-level Fixed Priority (JFP) ... EDF, LLF, FIFO
└── Job-level Dynamic Priority (JLDP) ... LST추가로 이론적 상한으로서 Clairvoyant Scheduling(미래를 전부 아는 가상 스케줄러)을 둘 수 있다. 주기 태스크 모델은 도착 패턴이 사전에 알려져 있어 clairvoyant에 준한다.
Offline: Cyclic Scheduling
빌드 타임에 Job 시작 시각 테이블을 작성. Cyclic executive(단순 SW 모듈)가 테이블대로 Job을 디스패치한다. 각 Job은 비선점 실행.
예: , , → 최소 공통 주기 30 내에서 테이블 작성.
| 장점 | 단점 |
|---|---|
| Simplicity — 구현 용이 | 1,000개 태스크 테이블 작성 난이도 급증 |
| Predictability — 시스템이 완전 결정적 | 최적성 보장이 어려움 |
| 적은 컨텍스트 스위치 오버헤드 | 워크로드 변경에 유연하지 않음 |
Online: FIFO 및 Weighted Round-Robin
Online 스케줄링의 기본 틀: 자원이 풀렸을 때 실행할 Job을 ready queue에서 고른다 (Waiting queue는 I/O·타이머 등 이벤트 대기 중인 태스크용). 여기서는 모든 Job이 대기하지 않는다(I/O 없음)고 가정하여 ready queue 관리에 집중.
FIFO (First-In, First-Out / FCFS)
- 단일 FIFO ready queue
- Queue 머리의 Job을 선택, 완료까지 비선점 실행
- 예측 가능하지만 짧은 Job이 긴 Job 뒤에서 대기 → 평균 응답 시간 악화
Weighted Round-Robin
- UNIX/Windows 같은 time-sharing 시스템에서 널리 사용
- 머리의 Job을 time slice(time quantum)만큼만 실행, 미완이면 꼬리로 이동
- Weight를 달리하여 Job별 slice 크기 차등
| Job | Weight | Execution Time |
|---|---|---|
| J1 | 2 | 6 |
| J2 | 1 | 2 |
| J3 | 1 | 4 |
Online: Priority-Driven Scheduling
- 각 Job에 우선순위 부여
- Ready queue는 우선순위 순으로 정렬 (최고 우선순위가 머리)
- 항상 최고 우선순위 Job을 선택
- 스케줄링 결정 시점은 이벤트 기반: Job 릴리스 / Job 완료
Work-Conserving 속성
Priority-driven scheduling은 work-conserving이다.
ready job이 하나라도 있으면 CPU를 idle하게 둘 수 없다.
이 속성이 FIFO(Priority-driven 관점에서 도착 시각이 우선순위)가 priority-driven에 포함되는 근거이기도 하다.
우선순위 차원 3종
| 차원 | 의미 | 대표 알고리즘 |
|---|---|---|
| Task-level Fixed (TFP) | 태스크별 우선순위가 영구 고정 | RM, DM |
| Job-level Fixed (JFP) | Job 릴리스 시 우선순위 확정, 이후 Job 수명 동안 고정 | EDF, LLF, FIFO |
| Job-level Dynamic (JLDP) | Job 실행 중에도 우선순위가 변할 수 있음 | LST (Least Slack) |
대부분의 RTOS는 Fixed Priority Scheduling을 지원한다 (구현이 단순). 고정 우선순위 스케줄링에서 상세.
우선순위 vs 중요도
우선순위는 태스크의 기능적 중요도(criticality)를 반영할 수 있지만, 스케줄 가능성이 보장되면 중요도는 별개다. 덜 중요한 태스크에 높은 우선순위를 부여하는 편이 전체 스케줄 가능성을 높일 수 있다 (예: RM은 주기가 짧은 태스크를 높게 주는데, 주기 ≠ 중요도). 상세.