cpu 스케줄링은 운영체제가 여러 프로세스의 cpu 할당을 결정하는 핵심 기능으로 크게 비선점형과 선점형으로 나눠진다.
비선점형 cpu 스케줄링 (Non-Preemptive)
비선점형은 한 프로세스가 cpu를 할당받으면 자발적으로 종료하거나 블록될 때 까지 cpu를 점유한다. 즉, 다른 프로세스가 강제로 cpu를 빼앗을 수 없다.
FCFS (First-come, First-Served)
FCFS 스케줄링은 도착한 순서대로 실행하는 비선점형 스케줄링 알고리즘이다.
예제)
실행 순서
p1 - p2 - p3
평균 대기 시간 (Average Waiting Time) : (0 + 4 + 6) / 3 = 3.3m/s (실행 시작 시간 - 도착 시간)
평균 반환 시간 (Turnaround Time, 프로세스가 요청된 후 완료까지 걸린 시간 ) : (5 + 7 + 8) / 3 =6.67m/s (대기시간 + 실행시간)
- 가장 간단한 알고리즘
- 긴 프로세스가 먼저 오면 전체 성능 저하 (Convoy Effect)
- 실시간 시스템에는 적합하지 않음
SJF (Shortest Job First)
실행시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘이다.
예제)
실행 순서
p1 - p3 - p4 - p2
평균 대기 시간(AWT) : ( 0 + 9 + 3 +3 ) / 4 =3.75m/s (시작 시간 - 도착 시간)
평균 반환 시간(TAT) : ( 7 +13 + 4 + 6)/4 = 7.5m/s (대기시간 + 실행 시간)
- 실행 시간이 긴 프로세스는 계속 뒤로 밀려서 실행되지 않을 수 있음 (Starvation 발생)
- 비선점형이므로 실시간 환경에 적합하지 않음
- 평균 대기 시간을 줄일 수 있음
선점형 cpu 스케줄링 (Preemptive)
선점형은 실행 중인 프로세스가 있더라도, 더 높은 우선순위 프로세스가 오면 cpu를 빼앗을 수 있다. 멀티태스킹 및 실시간 시스템에서 많이 사용된다.
RR (Round Robin)
RR 스케줄링은 각 프로세스에 동일한 시간 할당량(Quantum)을 주고 순차적으로 실행하는 선점형 알고리즘이다.
예제 ) Time Quantum =3m/s 이라 하자
실행 과정
| P1 (0-3) | P2 (3-6) | P3 (6-9) | P4 (9-12) |
| P1 (12-15) | P2 (15-16) | P3 (16-18) | P1 (18-22) |
평균 대기 시간 (AWT) : (12 + 11 + 11 + 6) / 4 =10m/s
평균 반환 시간 (TAT) : (22 + 15 + 16 + 9) /4 =15.5m/s
- 모든 프로세스가 공평하게 cpu를 사용 (starvation 방지)
- 빠른 응답 시간 보장
- Quantum이 너무 클 경우 FCFS와 유사해져 응답 속도 저하
- Quantum이 너무 작을 경우 context-swtiching 이 자주 발생하여 오버헤드 증가
SRTH (Shortest Remaining Time First)
SJF의 선점형 버전으로 실행 중인 프로세스보다 남은 실행 시간이 더 짧은 프로세스가 도착하면 cpu를 즉시 선점한다.
예제)
실행 순서
| P1 (0-1) | P2 (1-2) | P3 (2-4) | P4 (4-5) | P2 (5-8) | P1 (8-16) |
평균 대기 시간(AWT) : (8 + 3 + 0 + 1) / 4 =3m/s
평균 반환 시간(TAT) : (16 + 7 + 2 +2) / 4 = 6.75m/s
- 평균 대기 시간이 가장 짧다 (효율적 cpu 사용)
- 실시간 시스템에 적합
- context-switching 오버헤드 증가
- 긴 프로세스가 계속 밀려남 (starvation) 발생 가능
Priority Scheduling
priority scheduling은 각 프로세스에 우선순위를 부여하고 높은 우선순위를 가진 프로세스가 먼저 실행되는 알고리즘이다.
예제)
실행 순서
| P1 (0-1) | P2 (1-4) | P1 (4-5) | P4 (5-11) | P3 (11-19) |
평균 대기 시간 (AWT) : ( 3 + 0 + 9 + 2 ) / 4 = 3.5m/s
평균 반환 시간(8 + 3 + 17 + 8) / 4 = 9m/s
- 긴급한 프로세스를 빠르게 실행 가능
- 우선순위를 조정하여 다양한 환경에 적응 가능
- 낮은 우선순위의 프로세스가 실행되지 않을 경우가 있음 (starvation)
