선점형 vs 비선점형 스케줄링
| 항목 | 선점형 (Preemptive) | 비선점형 (Non-preemptive) |
|---|
| CPU 회수 | 강제 회수 가능 | 자발적 양보만 (I/O, 종료) |
| 응답성 | 높음 | 낮음 |
| 오버헤드 | 높음 (컨텍스트 스위칭) | 낮음 |
| 적합 | 현대 OS, 시분할 | 배치 시스템 |
| 알고리즘 | RR, SRTF, MLFQ | FCFS, SJF |
스케줄링 알고리즘 비교
| 알고리즘 | 선점 | 기아 | 평균대기시간 | 적합 환경 |
|---|
| FCFS | 비선점 | 없음 | 길 수 있음 (Convoy Effect) | 배치 |
| SJF/SRTF | 비선점/선점 | 가능 | 최적 | 이론적 |
| Priority | 선택 | 가능 (Aging으로 해결) | 가변 | 실시간 |
| RR | 선점 | 없음 | 중간 | 시분할 |
| MLFQ | 선점 | 가능 (Boosting) | 우수 | 범용 |
MQ vs MFQ vs RR
| 항목 | MQ (다단계 큐) | MFQ (다단계 피드백 큐) | RR (라운드 로빈) |
|---|
| 큐 이동 | 불가 (고정 배정) | 가능 (승격/강등) | 단일 큐 |
| 적응성 | 없음 | 있음 (프로세스 특성 학습) | 없음 |
| 복잡도 | 단순 | 복잡 | 단순 |
| 기아 | 하위 큐 기아 가능 | Boosting으로 방지 | 없음 |
RM vs EDF (실시간 스케줄링)
| 항목 | Rate Monotonic (RM) | Earliest Deadline First (EDF) |
|---|
| 우선순위 | 정적 (주기 짧을수록 높음) | 동적 (데드라인 가까울수록 높음) |
| 최적성 | 정적 우선순위 중 최적 | 단일 프로세서에서 최적 |
| 이용률 | ≤ 69.3% (n→∞) | ≤ 100% |
| 오버헤드 | 낮음 | 높음 (동적 우선순위) |
| 적합 | 단순/분석 용이 시스템 | 최대 이용률 필요 시스템 |
CFS vs O(1) vs EEVDF
| 항목 | CFS | O(1) | EEVDF |
|---|
| 기반 | 가상 런타임 (vruntime) | 우선순위 배열 | 가상 데드라인 |
| 자료구조 | Red-Black Tree | 비트맵+배열 | Red-Black Tree |
| 공정성 | 높음 | 중간 | 높음 |
| 적용 | Linux 2.6.23+ | Linux 2.6 이전 | Linux 6.6+ |
PIP vs PCP (우선순위 역전 해결)
| 항목 | PIP (Priority Inheritance) | PCP (Priority Ceiling) |
|---|
| 동작 | 대기 발생 시 우선순위 상속 | 자원별 Ceiling 사전 설정 |
| 데드락 | 방지 불가 | 방지 가능 (차단 최대 1회) |
| 오버헤드 | 상속/복원 비용 | Ceiling 관리 비용 |
| 구현 | 단순 | 복잡 (Ceiling 사전 분석) |
| 적합 | 범용 RTOS | 안전 필수 시스템 |
기아 vs 교착상태 vs 라이브락
| 항목 | 기아 (Starvation) | 교착상태 (Deadlock) | 라이브락 (Livelock) |
|---|
| 상태 | 대기 (Ready/Waiting) | 블록 (Blocked) | 실행 중이나 진전 없음 |
| 원인 | 우선순위 편중/불공정 | 순환 대기 (4조건) | 상호 양보 반복 |
| 자원 | 할당받지 못함 | 점유하며 대기 | 점유/해제 반복 |
| 해결 | 에이징, 공정 스케줄링 | 예방/회피/탐지/복구 | 랜덤 백오프, 우선순위 |