소개 (Introduction)
스케줄링의 단위: 스레드
-
스레드를 지원하는 운영체제에서는, 실제로 스케줄링되는 실행 단위는 프로세스가 아니라 스레드이다.
-
현대 OS(Linux, Windows)는 모두 스레드를 지원하며, CPU 스케줄러가 실제로 선택하는 것은 스레드이다.
-
하나의 프로세스 안에 여러 스레드가 있을 수 있고, 각 스레드가 독립적으로 스케줄링된다.
-
프로세스 스케줄링과 스레드 스케줄링이라는 용어는 종종 혼용된다.
- 일반적인 스케줄링 개념을 논의할 때는 프로세스 스케줄링이라는 용어를 선호한다.
다중프로그래밍 (Multiprogramming)
- CPU 활용률을 최대로하기 위해
- 프로세스가 I/O 요청으로 대기해야 할 때, CPU의 제어권은 준비 큐의 다른 프로세스에게 넘어간다.
핵심 포인트: 실제 스케줄링 단위는 스레드이지만, 개념 설명에서는 프로세스라는 용어를 사용한다. 스케줄링의 궁극적 목표는 CPU가 놀지 않도록(idle 상태를 최소화) 하는 것이다.
CPU-I/O 버스트 사이클 (CPU-I/O Burst Cycle)
기본 개념
- 프로세스 실행은 CPU 실행과 I/O 대기의 반복(cycle)으로 구성된다.
| 용어 | 설명 | |
|---|---|---|
| CPU burst | Cycle of CPU execution | CPU가 명령어를 연속적으로 실행하는 구간 |
| I/O burst | Cycle of I/O wait | I/O 작업이 완료되기를 기다리는 구간 |
- 프로세스 실행은 CPU 버스트로 시작하고, 그 뒤에 I/O 버스트가 따라온다.
CPU-I/O 버스트 사이클 상세
load,store,add같은 CPU 명령어가 실행되는 구간이 CPU burstread from file이 호출되면 디스크에서 데이터를 가져오는 동안 CPU는 기다린다 → I/O burst- 이 패턴이 프로세스가 종료될 때까지 반복된다.
CPU 버스트 시간 분포
그래프 설명:
- X축: burst duration (밀리초 단위, 0~40ms)
- Y축: frequency (빈도)
I/O bound process (I/O 바운드 프로세스) — 파란색 곡선:
- 왼쪽에 높은 봉우리 → 짧은 CPU 버스트가 매우 많다
- 예: 텍스트 에디터, 웹 브라우저. 잠깐 CPU를 쓰고 바로 I/O(키보드 입력, 네트워크) 대기
CPU bound process (CPU 바운드 프로세스) — 빨간색 곡선:
- 오른쪽에 낮고 넓은 분포 → 긴 CPU 버스트가 적게 나타남
- 예: 과학 계산, 영상 인코딩. 오랫동안 CPU만 집중적으로 사용
| 프로세스 유형 | 설명 | CPU 버스트 특성 |
|---|---|---|
| I/O bound | 짧은 CPU 버스트가 많다 | 자주 I/O를 요청하여 CPU를 금방 반납 |
| CPU bound | 긴 CPU 버스트가 적다 | I/O 없이 CPU를 오래 점유 |
핵심 포인트: 대부분의 프로세스는 짧은 CPU 버스트를 많이 가진 I/O 바운드 특성을 보인다. 스케줄링 알고리즘은 이런 특성을 고려하여 설계된다.
프로세스 스케줄러 (Process Scheduler)
스케줄러의 역할
- 스케줄링 결정: 준비 큐에서 실행 준비된 프로세스 중 하나를 선택한다.
- 디스패처가 선택된 프로세스에 CPU를 할당한다.
스케줄링 결정이 발생하는 3가지 경우
- 실행 → 대기 상태 전환 (예: I/O 요청) | 프로세스가 자발적으로 CPU를 놓음
- 실행 → 준비 상태 전환 (타임 슬라이스 만료) | OS가 강제로 CPU를 빼앗음
- 종료 | 프로세스가 끝남
비선점 vs 선점 스케줄링
비선점 스케줄링 (Non-preemptive scheduling) — (Proccess scheduling decision) 1번과 3번만 해당
-
프로세스가 종료되거나 대기 상태로 전환하여 자발적으로 CPU를 해제할 때까지 CPU에서 실행된다.
-
핵심: OS가 강제로 CPU를 빼앗지 않는다. 프로세스가 스스로 놓을 때까지 기다린다.
-
비유: 놀이터 그네에서 탄 아이가 스스로 내릴 때까지 기다리는 것
선점 스케줄링 (Preemptive scheduling) — (Proccess scheduling decision) 1, 2, 3번 모두 해당
-
실행 중인 프로세스를 강제로 일시 중단시키는 전략이다.
-
핵심: OS가 타이머 인터럽트 등으로 강제로 CPU를 빼앗을 수 있다 (2번 상황).
-
비유: 놀이터 관리인이 시간이 되면 그네에서 내리라고 하는 것
-
현대 OS는 거의 모두 선점 스케줄링을 사용한다.
그림 설명
- P0(CPU 바운드)가 실행 → P1(I/O 바운드)이 I/O 요청으로 대기 → P0이 다시 실행 → P2가 실행
- 비선점이면: P0가 끝날 때까지 기다려야 함
- 선점이면: P0의 타임 슬라이스가 만료되면 강제로 P1이나 P2에게 CPU를 넘길 수 있음
핵심 포인트: 비선점 = 프로세스가 자발적으로 CPU 반납, 선점 = OS가 강제로 CPU를 빼앗을 수 있음. 선점 스케줄링이 더 공정하고 응답성이 좋지만, 문맥 전환 오버헤드가 발생한다.
디스패처 (Dispatcher)
- 디스패처 모듈은 스케줄러가 선택한 프로세스에 CPU의 제어권을 넘긴다.
디스패처가 수행하는 작업
| 작업 | 설명 |
|---|---|
| 문맥 전환 | 현재 프로세스의 PCB 저장 + 새 프로세스의 PCB 로드 |
| 사용자 프로그램의 적절한 위치로 점프 → 프로그램 카운터 | PCB에 저장된 PC(프로그램 카운터) 값으로 점프하여 중단된 지점부터 재개 |
| 사용자 모드로 전환 | 커널 모드에서 사용자 모드로 전환하여 프로그램 실행 |
디스패치 지연시간 (Dispatch Latency)
-
디스패처가 한 프로세스를 멈추고 다른 프로세스를 시작하는 데 걸리는 시간이다.
-
디스패치 지연시간 = 문맥 전환 시간 + 모드 전환 시간 + 점프 시간
-
이 시간 동안 CPU는 유용한 작업을 하지 못한다 (순수 오버헤드).
핵심 포인트: 스케줄러는 "누구를 실행할지 결정"하고, 디스패처는 "실제로 전환을 수행"한다. 스케줄러 = 의사결정자, 디스패처 = 실행자.
스케줄링 기준 (Scheduling Criteria)
5가지 스케줄링 기준
| 상세 설명 | 최적화 방향 | ||
|---|---|---|---|
| CPU utilization | CPU 활용률 | CPU가 유용한 작업을 하는 시간의 비율 | 최대화 |
| Throughput | 처리량 | 단위 시간당 완료되는 프로세스의 수 | 최대화 |
| Turnaround time | 총 처리 시간 | 프로세스 제출부터 완료까지의 총 경과 시간 | 최소화 |
| Waiting time | 대기 시간 | 준비 큐(ready queue)에서 대기한 시간의 합 (대기 큐(waiting queue) 시간은 제외!) | 최소화 |
| Response time | 응답 시간 | 요청 제출부터 첫 번째 응답이 생성될 때까지의 시간 | 최소화 |
Turnaround time 예시
예시 1: CPU만 사용하는 프로세스
0────────CPU────────40──ready──60────CPU────100
Turnaround time = 100 - 0 = 100예시 2: I/O도 포함된 프로세스
0──CPU──I/O waiting──────────────────CPU──200
Turnaround time = 200 - 0 = 200- Turnaround time에는 실행 시간(CPU burst) + 대기 시간(ready queue) + I/O 대기 시간이 모두 포함된다.
- Waiting time에는 ready queue에서 기다린 시간만 포함된다 (I/O 대기 시간 제외).
Waiting time vs Response time
Waiting time (대기 시간):
-
프로세스가 준비 큐에서 대기한 시간이지, 대기 큐나 대기 상태에서의 시간은 아니다.
-
Blocked(waiting) 상태에서 어떤 wait queue(device queue 포함)에 머문 시간은 waiting time에 포함되지 않는다
-
프로세스가 준비 큐에 여러 번 들어갈 수 있으므로, 각 준비 큐 대기 시간의 합이다.
Response time (응답 시간):
-
요청이 제출된 시점부터 첫 번째 응답이 생성될 때까지의 시간이다. 출력(output)까지가 아니다. (시분할 환경용)
-
ex : 사용자가 키보드를 눌렀을 때, 화면에 첫 글자가 나타나기까지의 시간
-
Turnaround time과의 차이: turnaround은 작업이 완전히 끝날 때까지, response는 첫 반응까지
핵심 포인트: 중요한 것은 평균 대기 시간(Average waiting time)이다. 대기 시간에는 ready queue에서의 시간만 포함되고, I/O 대기 시간은 포함되지 않는다.
스케줄링 알고리즘 목록 (Scheduling Algorithms)
- 준비 큐에 있는 프로세스 중 어떤 프로세스에게 CPU를 할당할지 결정하는 전략이다.
| 알고리즘 | |
|---|---|
| First-Come, First-Served (FCFS) | 선입선출 |
| Shortest-Job-First (SJF) | 최단 작업 우선 |
| Priority Scheduling | 우선순위 스케줄링 |
| Round-Robin (RR) | 라운드 로빈 |
| Multilevel Queue | 다단계 큐 |
| Multilevel Feedback-Queue | 다단계 피드백 큐 |
FCFS 스케줄링 (First-Come, First-Served)
정의
-
CPU를 먼저 요청한 프로세스가 CPU를 먼저 할당받는다. (queue?)
-
FCFS 스케줄링은 비선점 방식이다. 한 번 CPU를 받으면 자발적으로 놓을 때까지 계속 실행된다.
구현
- 먼저 도착한 프로세스가 큐의 head에, 나중에 도착한 것이 tail에 위치한다.
P1, P2, P3 순서로 도착
대기 시간 계산:
- P1 = 0 (도착하자마자 실행)
- P2 = 24 (P1이 끝날 때까지 대기)
- P3 = 27 (P1+P2가 끝날 때까지 대기)
- 평균 대기 시간 = (0 + 24 + 27) / 3 = 17
P2, P3, P1 순서로 도착 (같은 프로세스, 다른 순서)
대기 시간 계산:
-
P1 = 6
-
P2 = 0
-
P3 = 3
-
평균 대기 시간 = (6 + 0 + 3) / 3 = 3
-
이전 경우보다 훨씬 좋다 (17 → 3으로 대폭 감소!)
-
FCFS에서는 도착 순서에 따라 평균 대기 시간이 크게 달라진다. 긴 프로세스(P1=24)가 먼저 오면 뒤의 짧은 프로세스들이 오래 기다려야 한다. 이를 호위 효과(Convoy Effect)라고 한다.
핵심 포인트: FCFS는 가장 단순하지만, 긴 프로세스 뒤에 짧은 프로세스가 오면 평균 대기 시간이 크게 증가한다 (호위 효과). 비선점 방식이라 공정성이 떨어질 수 있다.
SJF 스케줄링 (Shortest-Job-First)
스케줄링 방법론
-
각 프로세스에 다음 CPU 버스트의 길이를 연관시킨다.
-
CPU가 사용 가능하면, 다음 CPU 버스트가 가장 작은 프로세스에 할당된다.
두 가지 방식
| 방식 | 한국어 |
|---|---|
| Nonpreemptive | CPU가 주어지면 CPU 버스트가 완료될 때까지 빼앗을 수 없다 (강의 자료에서는 이것 만 설명) |
| Preemptive | 새 프로세스의 CPU 버스트 길이가 현재 실행 중인 프로세스의 남은 시간보다 짧으면 선점한다 |
- 선점 SJF는 SRTF (Shortest Remaining Time First)라고도 부른다.
SJF의 최적성
- SJF는 최적이다 — 주어진 프로세스 집합에 대해 최소 평균 대기 시간을 제공한다.
SJF의 현실적 어려움
-
다음 CPU 버스트의 길이를 알 수 있는 방법이 없다.
-
프로세스가 언제 종료되는지, 언제 I/O를 발생시키는지 알 수 없다.
-
실제로는 과거 CPU 버스트 기록을 바탕으로 다음 버스트를 예측(predict)한다 (지수 평균 등).
비선점 SJF 예제
왜 이 순서인가?
- 시간 0: P1만 도착 → P1 실행 시작 (비선점이므로 끝까지 실행)
- 시간 8: P1 완료. P2(burst=4), P3(burst=9), P4(burst=5) 중 가장 짧은 P2 선택
- 시간 12: P2 완료. P3(9), P4(5) 중 가장 짧은 P4 선택
- 시간 17: P4 완료. P3 실행
- 시간 26: P3 완료
대기 시간 계산:
- P1: 0 (도착 시간 0, 시작 시간 0)
- P2: 8 - 1 = 7 (도착 시간 1, 시작 시간 8)
- P3: 17 - 2 = 15 (도착 시간 2, 시작 시간 17)
- P4: 12 - 3 = 9 (도착 시간 3, 시작 시간 12)
- 평균 대기 시간 = (0 + 7 + 15 + 9) / 4 = 7.75
핵심 포인트: SJF는 이론적으로 최적이지만, 다음 CPU 버스트 길이를 미리 알 수 없다는 치명적 한계가 있다.
우선순위 스케줄링 (Priority Scheduling)
스케줄링 방법론
-
각 프로세스에는 우선순위 번호(정수)가 할당되며, 이 값은 사용자가 외부에서 설정하거나 scheduler가 내부적으로 계산한다. Scheduler는 이 우선순위를 기반으로 다음 실행할 프로세스를 선택한다
-
가장 높은 우선순위(가장 작은 정수 = 가장 높은 우선순위)를 가진 프로세스에 CPU가 할당된다.
-
주의: 숫자가 작을수록 우선순위가 높다! (1 > 2 > 3 > ...)
선점 vs 비선점
- 프로세스가 준비 큐에 도착하면, 그 우선순위가 현재 실행 중인 프로세스의 우선순위와 비교된다.
| 방식 | 동작 |
|---|---|
| 선점 (Preemptive) | 새 프로세스의 우선순위가 더 높으면 현재 프로세스를 빼앗고 새 프로세스를 실행 |
| 비선점 (Non-preemptive) | 새 프로세스를 준비 큐의 적절한 위치에 삽입만 하고, 현재 프로세스는 계속 실행 |
비선점 우선순위 스케줄링과 선점 우선순위 스케줄링 예시
[비선점의 경우]
tail → P4(10) → P3(8) → P2(6) → P1(4) → head → [CPU: P0(3)]
P5(1) 도착!
→ P5는 큐의 head에 삽입 (우선순위 1이 가장 높으므로), CPU의 P0은 계속 실행
[선점의 경우]
tail → P4(10) → P3(8) → P2(6) → P1(4) → head → [CPU: P0(3)]
P5(1) 도착!
→ P5(1)의 우선순위가 P0(3)보다 높으므로 P0을 빼앗고 P5가 CPU를 차지!우선순위 스케줄링 예제
SJF와의 관계
-
SJF는 우선순위가 예측된 다음 CPU 버스트 시간인 우선순위 스케줄링이다.
-
즉, SJF는 우선순위 스케줄링의 특수한 경우이다!
문제점: 기아 (Starvation)
-
기아(Starvation) — 낮은 우선순위의 프로세스가 영원히 실행되지 않을 수 있다.
-
높은 우선순위 프로세스가 계속 도착하면, 낮은 우선순위 프로세스는 영원히 CPU를 받지 못한다.
-
1973년 MIT에서 IBM 7094 시스템이 중단되었을 때, 1967년에 제출된 프로세스가 아직 실행을 기다리고 있었다는 일화가 있다.
해결책: 에이징 (Aging)
-
에이징(Aging) — 시간이 지남에 따라 프로세스의 우선순위를 높인다.
-
오래 기다린 프로세스의 우선순위를 점진적으로 높여, 결국에는 실행될 수 있도록 보장한다.
-
예: 매 1초마다 대기 중인 모든 프로세스의 우선순위를 1씩 높인다.
핵심 포인트: 우선순위 스케줄링의 핵심 문제는 기아(starvation)이며, 해결책은 에이징(aging)이다. SJF는 우선순위 스케줄링의 특수한 경우이다.
라운드 로빈 스케줄링 (Round Robin, RR)
동기
- RR은 특히 시분할 시스템을 위해 설계되었다.
스케줄링 방법론
- FCFS 스케줄링에 (preemption) 선점을 추가한 것이다.
- 같은 우선순위의 각 프로세스에 작은 단위의 CPU 시간(타임 퀀텀 또는 타임 슬라이스, 보통 10~100밀리초)을 할당한다. 이 시간이 경과하면, 프로세스는 선점되어 준비 큐의 끝에 추가된다.
공정성 보장
-
준비 큐에 n개의 프로세스가 있고 타임 퀀텀이 q이면, 각 프로세스는 최대 q 시간 단위씩 CPU 시간의 1/n을 얻는다.
-
어떤 프로세스도 (n-1)q 시간 단위 이상 기다리지 않는다.
-
예: 4개 프로세스, 퀀텀 20ms → 각 프로세스는 최대 (4-1)×20 = 60ms만 기다리면 반드시 CPU를 받는다.
퀀텀 크기의 영향
| 퀀텀 크기 | 원문 | 설명 | 결과 |
|---|---|---|---|
| 매우 큼 | FIFO or FCFS scheduling | FCFS와 동일 | 퀀텀이 모든 프로세스의 burst보다 크면, 선점이 일어나지 않아 FCFS와 같아진다 |
| 매우 작음 | Processor sharing | 프로세서 공유 | 각 프로세스가 자기만의 프로세서를 가진 것처럼 보이지만, 1/n 속도로 동작 |
- q는 문맥 전환 시간에 비해 충분히 커야 한다. 그렇지 않으면 오버헤드가 너무 높아진다.
RR 예제 (Time Quantum = 20)
실행 과정 상세:
| 시간 | 실행 | 남은 burst | 설명 |
|---|---|---|---|
| 0~20 | P1 | 53→33 | P1이 20ms 실행, 33ms 남음 → 큐 끝으로 |
| 20~37 | P2 | 17→0 | P2가 17ms 실행, 완료 (17 < 20이므로 퀀텀 전에 끝남) |
| 37~57 | P3 | 68→48 | P3이 20ms 실행 |
| 57~77 | P4 | 24→4 | P4가 20ms 실행 |
| 77~97 | P1 | 33→13 | P1이 20ms 실행 |
| 97~117 | P3 | 48→28 | P3이 20ms 실행 |
| 117~121 | P4 | 4→0 | P4가 4ms 실행, 완료 |
| 121~134 | P1 | 13→0 | P1이 13ms 실행, 완료 |
| 134~154 | P3 | 28→8 | P3이 20ms 실행 |
| 154~162 | P3 | 8→0 | P3이 8ms 실행, 완료 |
-
일반적으로 SJF보다 평균 총 처리 시간은 높지만, 응답 시간은 더 좋다.
-
RR은 모든 프로세스에 공정하게 CPU를 나눠주므로, 첫 응답까지의 시간(response time)이 짧다.
문맥 전환의 영향
process time = 10인 프로세스에 대해:
| 퀀텀 | 문맥 전환 횟수 | 설명 |
|---|---|---|
| 12 | 0 | 퀀텀(12) > process time(10)이므로 전환 없이 완료 |
| 6 | 1 | 0~6 실행 → 전환 → 6~10 실행, 총 1회 전환 |
| 1 | 9 | 1ms마다 전환 → 9번 전환! 오버헤드 매우 큼 |
-
현대 OS에서 퀀텀은 10~100밀리초 범위이고, 문맥 전환 오버헤드는 10마이크로초 미만이다.
-
퀀텀 10ms, 전환 시간 10μs이면 → 오버헤드 비율 = 10μs / 10ms = 0.1%로 무시할 수 있을 정도로 작다.
핵심 포인트: RR은 공정성과 응답성이 좋지만, 평균 총 처리 시간은 SJF보다 길다. 퀀텀이 너무 작으면 문맥 전환 오버헤드가 증가하고, 너무 크면 FCFS와 같아진다. 적절한 퀀텀 선택이 중요하다.
다단계 큐 스케줄링 (Multilevel Queue Scheduling)
스케줄링 방법론
- 준비 큐가 여러 개의 독립된 큐로 분할된다.
- 프로세스는 속성(우선순위, CPU 버스트, 메모리 크기 등)에 따라 하나의 큐에 할당된다.
각 큐는 고유한 스케줄링 알고리즘을 가진다.
- ex : 전경(foreground) 큐 — RR, 배경(background) 큐 — FCFS
큐 간 스케줄링 (두 가지 방법)
방법 1: 고정 우선순위 (Fixed priority)
- 전경 큐의 모든 프로세스를 먼저 서비스하고 그 다음 배경 큐를 서비스한다. 기아 가능성이 있다.
방법 2: 시간 분할 (Time slice)
-
각 큐가 일정량의 CPU 시간을 받아 자신의 프로세스들 사이에서 스케줄링한다.
-
ex : 전경 큐에 80% (RR), 배경 큐에 20% (FCFS)
Example : Priority-based multilevel queue scheduling
-
각 큐는 하위 우선순위 큐에 대해 절대적 우선권을 가진다.
-
스케줄러는 큐 집합을 최고에서 최저 우선순위 순으로 순회하며 실행 준비된 스레드를 찾는다.
-
Priority 0에 프로세스가 있으면 그것을 실행. Priority 0이 비면 Priority 1을 확인. 이런 식으로 내려간다.
핵심 포인트: 다단계 큐는 프로세스를 우선순위별로 분류하되, 한 번 배정된 큐에서 다른 큐로 이동할 수 없다. 이것이 다단계 피드백 큐와의 핵심 차이점이다.
다단계 피드백 큐 스케줄링 (Multilevel Feedback-Queue Scheduling)
동기
-
(기존 다단계 큐에서) 프로세스에 우선순위가 할당되면, 한 큐에서 다른 큐로 이동하지 않는다.
-
따라서 대화형이나 I/O 바운드 프로세스가 필요할 때 적절한 양의 CPU 시간을 사용하지 못한다.
-
문제: I/O 바운드 프로세스가 낮은 우선순위 큐에 배정되면, CPU가 필요한 짧은 순간에도 대기해야 한다.
해결: 다단계 피드백 큐
- 프로세스가 다른 우선순위의 큐 사이를 이동할 수 있게 한다.
- 프로세스의 이동은 CPU 버스트의 특성에 따라 결정된다.
이동 규칙
Priority 0 (최고) ──→ P0, P10, P2, P7
↑ I/O 바운드 프로세스 승격
Priority 1 ──→ P11
↕ 이동 가능
Priority 2 ──→ P20, P5, P9, P21
↓ CPU 많이 쓴 프로세스 강등
Priority 3 (최저) ──→ P15, P16실제 동작 예시:
| 규칙 | 설명 |
|---|---|
| 강등 | 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위 큐로 이동 |
| 승격 | 대화형 또는 I/O 바운드 프로세스는 높은 우선순위 큐로 이동 |
구체적 시나리오:
1. 새 프로세스가 최고 우선순위 큐(Priority 0)에 진입
2. 타임 퀀텀 안에 CPU 버스트가 끝나면 (= I/O 바운드) → 같은 큐에 유지 또는 승격
3. 타임 퀀텀을 다 사용하면 (= CPU 바운드) → 한 단계 낮은 큐로 강등
4. 이 과정이 반복되면, CPU 바운드 프로세스는 점점 아래 큐로 내려가고, I/O 바운드 프로세스는 위에 머물게 된다.
핵심 포인트: 다단계 피드백 큐는 가장 일반적인 CPU 스케줄링 알고리즘이다. 프로세스의 행동(CPU 사용량)에 따라 동적으로 우선순위를 조정하므로, I/O 바운드 프로세스에게 빠른 응답을, CPU 바운드 프로세스에게는 긴 퀀텀을 제공할 수 있다.
Windows XP 스케줄링 (Windows XP Scheduling)
- 우선순위 기반, 선점, 다단계 피드백 큐 스케줄링
우선순위 클래스
| 클래스 | 원문 | 범위 |
|---|---|---|
| Variable class | Variable classes ranging from 1 to 15 priority | 우선순위 1~15 |
| Real-time class | Real-time classes ranging from 16 to 31 priority | 우선순위 16~31 |
Windows XP 우선순위 매트릭스
행(row) = 상대적 우선순위 (time-critical ~ idle)
열(column) = 프로세스 기본 우선순위 클래스 (real-time, high, above normal, normal, below normal, idle priority)
-
스케줄러는 CPU 바운드 스레드의 CPU 소비를 제한하기 위해 상대 우선순위를 조정한다.
-
가변 클래스(1~15)의 스레드는 I/O 완료 후 우선순위가 일시적으로 올라갔다가, CPU를 많이 쓰면 내려간다.
-
실시간 클래스(16~31)의 스레드는 우선순위가 변하지 않는다.
┌──────────────────────────────────────────────┐
│ Priority Level 31 ← 가장 높은 우선순위 │
│ ... │
│ Priority Level 16 ← Real-Time 시작 │
├──────────────────────────────────────────────┤
│ Priority Level 15 │
│ ... │
│ Priority Level 1 ← Variable 시작 (최하) │
│ Priority Level 0 ← Idle 스레드 전용 │
└──────────────────────────────────────────────┘
숫자 커질수록 ↑ 우선순위 높아짐Linux 스케줄링 (Linux Scheduling)
- 우선순위 기반, 선점, 다단계 피드백 큐 스케줄링 (Windows XP와 동일한 기본 구조!)
우선순위 범위
| 범위 | 원문 | 설명 |
|---|---|---|
| 0 ~ 99 | Real-time range | 실시간 태스크용. 숫자가 작을수록 우선순위 높음 |
| 100 ~ 140 | Nice (value) range | 일반 태스크용. nice 명령으로 조절 가능 |
- Unix/Linux의 nice 값은 -20 ~ 19 총 41 단계입으로 100 ~ 140 = 41개의 nice 레벨을 표현하는 것이다.
nice -20 → priority 100 (일반 프로세스 중 가장 높은 우선순위)
nice 0 → priority 120 (기본값)
nice +19 → priority 139 (일반 프로세스 중 가장 낮은 우선순위)우선순위와 타임 퀀텀의 관계
- 높은 우선순위(0) → 긴 퀀텀(200ms): 실시간 태스크에 충분한 CPU 시간 보장
- 낮은 우선순위(140) → 짧은 퀀텀(10ms): 낮은 우선순위 태스크에는 짧은 시간만 할당
- 퀀텀이 우선순위에 따라 가변적(variable)이다.
스케줄링 오버헤드
-
버전 2.5에서는 오버헤드가 시스템의 스레드 수에 비례했다 (O(n)).
-
(개선 후) 스레드 수에 관계없이 O(1)이다.
-
O(n)에서 O(1)으로의 개선은 Linux 커널 2.6에서 이루어진 중요한 발전이다.
Active/Expired 배열
- 실행 큐(runqueue)는 active 배열과 expired 배열로 구성된다.
동작 방식:
- 스케줄러는 active 배열에서만 프로세스를 선택하여 실행한다.
- 프로세스가 타임 퀀텀을 소진(exhausted)하면, expired 배열로 이동한다.
- expired 배열로 이동한 프로세스는 다른 모든 스레드가 퀀텀을 소진할 때까지 실행되지 않는다.
- active 배열이 비게 되면, active와 expired 배열을 교환(exchange)한다.
- 이전의 expired가 새로운 active가 되어 프로세스들이 다시 실행된다. O(1)인 이유
- 비유: 놀이기구 줄서기. 한 바퀴 탄 사람(expired)은 아직 안 탄 사람(active)이 모두 탈 때까지 기다린다. 모두 타면 줄을 교체한다.
동적 우선순위 기반 스케줄링
-
I/O 바운드 스레드는 높아진 동적 우선순위, 즉 더 높은 우선순위를 받는다.
-
반대로, CPU 바운드 스레드는 낮아진 동적 우선순위를 받는다.
| 프로세스 유형 | 동적 우선순위 변화 | 이유 |
|---|---|---|
| I/O 바운드 | 상승 (우선순위 높아짐) | 짧은 CPU 버스트 후 금방 CPU를 반납하므로 보상 |
| CPU 바운드 | 하강 (우선순위 낮아짐) | CPU를 오래 점유하므로 불이익 |
핵심 포인트: Linux O(1) 스케줄러는 active/expired 배열 교환으로 O(1) 시간에 다음 프로세스를 선택하며, I/O 바운드 프로세스에 높은 우선순위를, CPU 바운드 프로세스에 낮은 우선순위를 동적으로 부여한다.
전체 스케줄링 알고리즘 비교표
| 알고리즘 | 선점 여부 | 기아 가능성 | 평균 대기시간 | 응답 시간 | 특징 |
|---|---|---|---|---|---|
| FCFS | 비선점 | 없음 | 나쁨 (호위 효과) | 나쁨 | 가장 단순, 도착 순서대로 |
| SJF | 비선점/선점 | 있음 | 최적 (이론적) | 보통 | 다음 CPU 버스트 예측 불가능 |
| Priority | 비선점/선점 | 있음 | 보통 | 보통 | 에이징으로 기아 해결 |
| RR | 선점 | 없음 | 보통 | 좋음 | 시분할에 적합, 퀀텀 크기가 핵심 |
| Multilevel Queue | 선점 | 있음 | 보통 | 보통 | 큐 간 이동 불가 |
| Multilevel Feedback Queue | 선점 | 에이징으로 해결 | 좋음 | 좋음 | 가장 유연, 현대 OS에서 사용 |
