CPU 스케줄링
CPU는 각 프로세스를 어떻게 효율적이게 선택해서 실행하게 할 것인가. OS는 스케줄링 알고리즘을 통해 효율적이게 프로세스를 실행시킨다.
효율적인 스케줄링
그렇다면 효율적인 스케줄링임을 정의하는 메트릭스는 무엇인가. 크게 2가지를 나타내고 있다.
- 반환 시간: 프로세스가 도착해서 끝날 때 까지의 시간
- 응답 시간: 프로세스가 도착해서 실행 되기 까지의 시간
프로세스가 빨리 끝나는 것(반환 시간), 프로세스가 얼마나 빨리 사용자에게 피드백을 주는지(응답 시간) 이렇게 2가지가 주 된 평가 메트릭이 된다.
그럼 각 메트릭을 고려한 스케줄링 알고리즘과 그 외에 대해서 설명하겠다.
FIFO
선입선출 방식으로 자료구조의 Queue와 비슷하게 동작한다.
예시
프로세스 A(100ms), B(10ms), C(10ms)가 순서대로 도착했다고 가정:
시간: 0 10 20 30 40 50 60 70 80 90 100 110 120
|----A(100ms)------------------------------------|B(10)|C(10)|- A의 반환 시간: 100ms
- B의 반환 시간: 110ms (100ms 대기 + 10ms 실행)
- C의 반환 시간: 120ms (110ms 대기 + 10ms 실행)
- 평균 반환 시간: 110ms
장점
- 구현이 쉽다
단점
- 작업시간이 오래걸리는 프로세스가 먼저 오면 짧은 작업시간을 가진 프로세스의 대기시간이 오래걸린다. (Convoy Effect)
SJF(Shortest Job First)
가장 짧은 작업시간을 가진 프로세스를 실행 시킨다.
예시
프로세스 A(100ms), B(10ms), C(10ms)가 동시에 도착했다고 가정:
시간: 0 10 20 30 40 50 60 70 80 90 100 110 120
|B(10)|C(10)|----A(100ms)------------------------------------|- B의 반환 시간: 10ms
- C의 반환 시간: 20ms
- A의 반환 시간: 120ms
- 평균 반환 시간: 50ms (FIFO의 110ms보다 훨씬 개선!)
장점
- 동시에 프로세스 도착시 최적의 반환 시간을 보여줌
단점
- 작업 시간을 미리 알아야함
- 비선점형(non-preemptive)이므로 긴 프로세스가 먼저 들어오면 성능이 좋지 않음
STCF(Shortest Time-To-Completion First)
선점형(preemptive) 방식으로, 남은 작업 시간이 짧은 프로세스를 우선 실행한다.
예시
프로세스 A(100ms)가 t=0에, B(10ms)가 t=10에, C(10ms)가 t=10에 도착:
시간: 0 10 20 30 40 50 60 70 80 90 100 110 120
|A(10)|B(10)|C(10)|----A(나머지 90ms)--------------------------|- A가 10ms 실행 후 B, C가 도착
- B, C가 더 짧으므로 A를 선점하고 먼저 실행
- B, C 완료 후 A가 나머지 90ms 실행
결과:
- B의 반환 시간: 10ms (10에 도착 → 20에 완료)
- C의 반환 시간: 20ms (10에 도착 → 30에 완료)
- A의 반환 시간: 120ms
- 평균 반환 시간: 50ms (SJF와 동일하지만, 순차 도착에도 최적!)
장점
- 반환 시간 측면에서 최적의 성능 제공
- 새로운 짧은 프로세스 도착 시 기존의 긴 프로세스를 선점 가능
단점
- 응답 시간 측면에서 좋은 성능을 기대하기 어려움
- 긴 작업은 계속 선점되어 완료까지 시간이 걸릴 수 있음 (Starvation 가능성)
RR(Round Robin)
각 프로세스에 **타임 슬라이스(time slice)**만큼 시간을 순환적으로 제공
예시
프로세스 A(50ms), B(50ms), C(50ms)가 동시 도착, 타임 슬라이스 10ms:
시간: 0 10 20 30 40 50 60 70 80 90 100 110 120 130 140 150
|A(10)|B(10)|C(10)|A(10)|B(10)|C(10)|A(10)|B(10)|C(10)|A(10)|B(10)|C(10)|A(10)|B(10)|C(10)|- A의 응답 시간: 0ms (즉시 실행)
- B의 응답 시간: 10ms
- C의 응답 시간: 20ms
- 평균 응답 시간: 10ms (STCF에서는 50ms 이상!)
반환 시간:
- A: 145ms, B: 150ms, C: 150ms
- 평균 반환 시간: 148.3ms (STCF의 50ms보다 나쁨)
장점
- 응답 시간 개선
- 공정성 증가
단점
- 컨텍스트 스위칭 오버헤드 증가
- 평균 반환 시간이 SJF/STCF 보다 나쁨
타임 슬라이스의 딜레마
Round-Robin 스케줄러에서 타임 슬라이스 크기는 중요한 설계 결정이다.
| 타임 슬라이스 크기 | 장점 | 단점 |
|---|---|---|
| Short (예: 1ms) | 응답 시간 개선 | 컨텍스트 스위칭 오버헤드 증가 |
| Long (예: 100ms) | 컨텍스트 스위칭 감소 | 응답 시간 저하, FIFO처럼 동작 |
작업 전환(컨텍스트 스위칭, Context Switching)은 레지스터 저장 외에 많은 시간이 필요하기에 타임 슬라이스를 작업 전환에 걸리는 시간을 고려하면서 설정해야한다.
입출력 연산의 고려
지금까지는 모든 프로그램이 입출력 없이 CPU만 사용한다고 가정했습니다. 하지만 현실의 프로그램은 완전히 다릅니다.
입출력이 있는 환경의 특징
실제 작업은 다음과 같이 동작합니다:
- 잠깐 CPU를 사용하여 계산 수행
- 입출력 요청을 발생시켜 디스크나 네트워크를 기다림
- 입출력이 완료될 때까지 CPU를 사용하지 않음 (블로킹)
- 완료되면 다시 CPU 사용
입출력을 고려한 스케줄링 전략
핵심 아이디어: 한 프로세스가 입출력을 기다리는 동안, 다른 프로세스에게 CPU를 할당하여 시스템 자원을 효과적으로 활용합니다.
예시 시나리오
- 작업 A: 각각 10ms의 5개 CPU 버스트 (총 50ms CPU 사용)
- CPU 10ms → I/O 10ms → CPU 10ms → I/O 10ms → …
- 작업 B: CPU만 50ms 연속 사용
STCF 방식 (I/O를 고려하지 않는 경우)
작업 A와 B가 동시에 도착했을 때, 둘 다 50ms가 필요하므로 먼저 온 순서대로 실행:
시간: 0 10 20 30 40 50 60 70 80 90 100
A: |CPU |idle|CPU |idle|CPU |idle|CPU |idle|CPU | |
B: | wait.. |CPU---| ...- A의 완료 시간: 90ms (I/O 대기 시간 포함)
- B의 완료 시간: 100ms
- CPU 유휴 시간: 40ms (A가 I/O 대기 중)
I/O를 고려한 스케줄링
A가 I/O를 시작하면 즉시 B에게 CPU를 할당:
시간: 0 10 20 30 40 50 60 70 80 90 100
A: |CPU |idle|CPU |idle|CPU |idle|CPU |idle|CPU | |
B: | |CPU-| |CPU-| |CPU-| |CPU-| |CPU- |
범례: CPU = CPU 사용, idle = I/O 대기더 자세한 타임라인:
0-10ms: A CPU 사용
10-20ms: A I/O 대기 → B CPU 사용
20-30ms: A CPU 사용, B 대기
30-40ms: A I/O 대기 → B CPU 사용
40-50ms: A CPU 사용, B 대기
50-60ms: A I/O 대기 → B CPU 사용
60-70ms: A CPU 사용, B 대기
70-80ms: A I/O 대기 → B CPU 사용
80-90ms: A CPU 사용, B 대기결과:
- A의 완료 시간: 90ms (동일)
- B의 완료 시간: 60ms (100ms → 60ms로 개선!)
- CPU 유휴 시간: 0ms (완벽한 활용!)
- 시스템 전체 처리량(Throughput) 증가
위 스케줄링에서 생각하지 못한 것들
SJF/STCF 는 작업시간을 알고 있다는 전제하에 반환 시간이 좋은 알고리즘 임을 나타내고 있다. 하지만 과연 프로세스가 얼마나 시간이 필요한 지 알 수 있을 까? 아마 이전 작업들을 어디 캐시에 저장해서 예측하고 하는 것이 아닐까.
미래를 알고 있는 게 아닌 이상 최고의 스케줄링은 없다는 생각이 든다. 그리고 이것이 만약 병렬적으로 동작했을 때는 과연 어떻게 될까. 비동기 큐처럼 저장했다가 남아 있는 CPU에 부여해서 병렬을 유지하는 걸지도..