CPU 스케줄링

1. 목적과 평가 기준

CPU 스케줄링은 준비 큐의 프로세스 중 다음 실행 대상을 선택한다.

• CPU 이용률·처리량: 높을수록 좋다.
• 반환시간: 도착부터 완료까지의 시간
• 대기시간: 준비 큐에서 기다린 총 시간
• 응답시간: 도착부터 최초 CPU 할당까지의 시간

반환시간 = 완료시간 - 도착시간
대기시간 = 반환시간 - CPU 실행시간
응답시간 = 최초 실행시간 - 도착시간

2. 선점과 비선점

• 비선점: 실행 중인 프로세스가 종료하거나 대기 상태가 될 때까지 CPU를 유지한다.
• 선점: 운영체제가 실행 중인 프로세스에서 CPU를 회수할 수 있다.

3. 주요 알고리즘

FCFS

먼저 도착한 프로세스를 먼저 실행한다. 단순하고 공정하지만 긴 작업 뒤에 짧은 작업이 기다리는 호위 효과가 생길 수 있다.

SJF·SRTF

SJF는 실행시간이 가장 짧은 작업을 선택하는 비선점 방식, SRTF는 남은 시간이 가장 짧은 작업을 선택하는 선점 방식이다. 평균 대기시간을 줄일 수 있지만 실행시간 예측이 필요하고 긴 작업이 기아 상태에 빠질 수 있다.

우선순위

우선순위가 높은 프로세스를 먼저 실행한다. 낮은 우선순위의 무한 대기를 막기 위해 기다린 시간에 따라 우선순위를 올리는 aging을 사용할 수 있다.

Round Robin

각 프로세스에 시간 할당량을 주고 끝나지 않으면 준비 큐 뒤로 보낸다. 시간 할당량이 너무 크면 FCFS와 비슷하고, 너무 작으면 문맥교환 오버헤드가 커진다.

HRRN

비선점 방식으로 다음 응답률이 가장 큰 작업을 선택한다.

응답률 = (대기시간 + 실행시간) / 실행시간

짧은 작업을 우대하면서 오래 기다린 작업의 우선순위도 높인다.

다단계 큐·다단계 피드백 큐

다단계 큐는 작업 유형별로 고정된 큐를 사용한다. 다단계 피드백 큐는 프로세스가 큐 사이를 이동하며 대화형·입출력 중심 작업에 높은 응답성을 줄 수 있다.

4. 계산 예시

세 프로세스가 모두 시각 0에 도착하고 실행시간이 P1=5, P2=3, P3=2라면 FCFS 순서 P1→P2→P3에서 완료시간은 5, 8, 10이다.

• 대기시간: P1=0, P2=5, P3=8
• 평균 대기시간: (0+5+8)/3 = 13/3

SJF라면 P3→P2→P1 순서가 되어 대기시간은 0, 2, 5로 감소한다.

5. 도착시간이 다른 스케줄링 계산 절차

다음 프로세스를 예로 든다.

FCFS

0        5        8   9
|   P1   |   P2   |P3|

• 완료시간: P1=5, P2=8, P3=9
• 반환시간: 5, 7, 7
• 대기시간: 0, 4, 6
• 응답시간: 0, 4, 6

비선점 SJF

시각 0에는 P1만 도착했으므로 P1을 실행한다. 시각 5에 준비된 P2·P3 중 P3를 선택한다.

0        5  6        9
|   P1   |P3|   P2   |

“전체 버스트가 가장 짧은 순서”로 처음부터 정렬하면 도착하지 않은 작업을 선택하는 오류가 생긴다.

SRTF

0  1  2  3     5        9
|P1|P2|P3| P2  |   P1   |

새 프로세스가 도착할 때마다 현재 남은 시간과 비교한다. P1의 응답시간은 0이지만 완료까지 여러 번 나뉠 수 있다.

6. Round Robin 상태 추적

모두 시각 0에 도착하고 P1=5, P2=3, P3=1, 시간 할당량 q=2라면 다음과 같다.

0  2  4 5  7 8 9
|P1|P2|P3|P1|P2|P1|

완료시간은 P3=5, P2=8, P1=9이다. 도착·재삽입 시점이 같은 경우 큐에 넣는 순서는 문제 정의를 따라야 한다. 문맥교환 비용이 c이고 실제 전환이 m번이면 총 완료시각에 대략 m×c가 추가될 수 있다.

7. CPU 버스트 예측

SJF는 미래 버스트를 정확히 알 수 없으므로 지수평균으로 예측할 수 있다.

τ(n+1) = α·t(n) + (1-α)·τ(n)

α가 크면 최근 측정값에 민감하고, 작으면 과거 평균을 더 많이 반영한다. 예측값 6, 실제 버스트 10, α=0.25이면 새 예측값은 0.25×10+0.75×6=7이다.

8. 디스패처와 선점 비용

디스패처는 선택된 프로세스에 CPU를 넘기며 문맥복원, 사용자 모드 전환, 적절한 위치로 분기한다. 디스패치 지연과 캐시·TLB 상태 손실은 짧은 시간 할당량의 숨은 비용이다. 따라서 RR의 q는 응답성을 높일 만큼 작되, 대부분의 CPU 버스트가 여러 번 쪼개져 오버헤드가 지배하지 않도록 정한다.

9. 우선순위 역전과 실시간 스케줄링

낮은 우선순위 작업이 락을 보유하고, 높은 우선순위 작업이 그 락을 기다리는 동안 중간 우선순위 작업이 계속 실행되면 우선순위 역전이 발생한다. 우선순위 상속은 락 보유자에게 대기 중인 높은 우선순위를 임시로 부여해 완화한다.

실시간 시스템에서는 마감시간 충족 여부가 핵심이다.

• Rate Monotonic: 주기가 짧을수록 높은 고정 우선순위
• EDF(Earliest Deadline First): 절대 마감시간이 가장 이른 작업 우선

일반 평균 대기시간 최적화와 실시간 마감 보장은 서로 다른 목표이다.

10. 비교 시 반드시 확인할 조건

1. 도착시간과 CPU 버스트
2. 선점 여부와 선점 시점
3. RR 시간 할당량과 문맥교환 비용
4. 같은 우선순위·동시 도착의 타이브레이크
5. I/O 버스트가 포함되는지
6. 평균을 완료된 모든 프로세스 기준으로 계산하는지

최종 확인 문제

1. P가 도착 2, 최초 실행 6, 완료 15, CPU 버스트 합 8일 때 응답시간·반환시간·대기시간을 구하시오.
2. 모두 시각 0에 도착한 P1=4, P2=2, P3=1을 비선점 SJF로 실행할 때 평균 대기시간을 구하시오.
3. 예측 버스트가 8, 실제 버스트가 4, α=0.25일 때 다음 예측값을 구하시오.
4. Round Robin의 시간 할당량을 지나치게 작게 했을 때 응답성 외에 악화될 수 있는 두 가지를 쓰시오.
5. 낮은 우선순위 작업이 보유한 락 때문에 높은 우선순위 작업이 지연되는 현상과 대표 완화법을 쓰시오.