개발 공부
[운영체제][OSTEP] CPU 스케줄링
운영체제의 다양한 스케줄링 정책에 대해 공부해봅니다.
![[운영체제][OSTEP] CPU 스케줄링](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?auto=format&w=860)
1️⃣ 워크로드에 대한 가정
워크로드(workload): 일련의 프로세스들이 실행하는 상황
설명을 위해 시스템에서 실행 중인 프로세스 혹은 작업(job)에 대해 다음과 같이 가정한다.(비현실적)
모든 작업은 같은 시간 동안 실행된다.
모든 작업은 동시에 도착한다.
각 작업은 시작되면 완료될 때까지 실행된다.
모든 작업은 CPU만 사용한다.(I/O 수행 안함)
각 작업의 실행 시간은 사전에 알려져 있다.
2️⃣ 스케줄링 평가 항목
스케줄링 평가 항목(scheduling metric): 스케줄링 정책의 비교를 위한 평가 기준
반환 시간(turnaround time): 작업이 완료된 시각 - 작업이 시스템에 도착한 시각
T_turnaround = T_completion - T_arrival
성능 측면에서의 평가 기준
공정성(fairness)
Jain's Fairness Index 등에 따라 측정
스케줄링에서 성능과 공정성은 서로 상충되는 목표
예시) 스케줄러가 성능 극대화를 위해 몇몇 작업의 실행 중지 ➡️ 공정성 약화
1️⃣의 가정을 토대로 한 반환 시간
[가정 2] 모든 작업은 동시에 도착: T_arrival = 0 ➡️ T_turnaround = T_completion
3️⃣ 선입선출(First In First Out, FIFO)
선도착선처리(First Come First Served, FCFS) 스케줄링이라고도 불린다.
장점
단순하고 구현하기 쉽다.
1️⃣의 가정 하에서는 매우 잘 동작한다.
동작 방식
시스템에 순서대로 3개의 작업 A, B, C가 거의 동시에 도착했다고 가정(각 작업은 10초 동안 실행)
[ A(10) ][ B(10) ][ C(10) ]
| | | |
0 10 20 30 ...
시간의 흐름 →이때 이 작업들의 평균 반환 시간은?
A는 10, B는 20, C는 30에 종료 ➡️ (10 + 20 + 30)/3 = 20
이번에는 1️⃣의 "가정 1"을 완화하여 실행 시간이 모두 같지 않다고 가정
[ A(100) ][B(10)][C(10)]
| | | |
0 100 110 120 ...
시간의 흐름 →이때 이 작업들의 평균 반환 시간은?
A는 100, B는 110, C는 120에 종료 ➡️ (100 + 110 + 120)/3 = 110
문제점
convoy effect: 위와 같이 실행 시간이 짧은 프로세스들이 실행 시간이 긴 프로세스의 종료를 기다리는 현상
4️⃣ 최단 작업 우선(Shortest Job First, SJF)
짧은 실행 시간을 가진 작업을 먼저 실행시킨다.
장점
모든 작업이 동시에 도착(비현실적)한다면 최적(optimal)의 스케줄링 알고리즘이다.
동작 방식
3️⃣의 두 번째 예시 상황을 바탕으로 동작 방식을 살펴보자.
[B(10)][C(10)][ A(100) ]
| | | |
0 10 20 120 ...
시간의 흐름 →이때 이 작업들의 평균 반환 시간은?
B는 10, C는 20, A는 120에 종료 ➡️ (10 + 20 + 120)/3 = 50
이 예시에서 SJF는 FIFO에 비해 스케줄링(평균 반환 시간) 성능을 2배 이상 향상시켰다.
이번에는 1️⃣의 "가정 2"를 완화하여 작업이 임의의 시간에 도착할 수 있다고 가정
[10에 B, C 도착]
↓
[ A(100) ][B(10)][C(10)]
| | | | |
0 10 100 110 120 ...
시간의 흐름 →이때 이 작업들의 평균 반환 시간은?
A는 100, B는 110, C는 120에 종료 ➡️ (10 + (100 - 10) + (120 - 10))/3 = 103.33...
즉, B와 C의 실행 시간이 짧더라도 A가 끝날 때까지 기다려야 함 ➡️ convoy effect 발생
문제점
위와 같이 현실적으로는 작업의 도착 시간이 제각각이고, 실행 시간이 짧은 작업이 먼저 들어온다는 보장이 없으므로 convoy effect가 발생할 가능성이 있다.
5️⃣ 최소 잔여시간 우선(STCF)
STCF는 Shortest Time-to-Completion First의 약자이며, 선점형 최단 작업 우선(Preemptive Shortest Job First, PSJF) 스케줄링이라고도 불린다.
4️⃣의 문제점을 해결하기 위해 1️⃣의 "가정 3"을 완화하여 작업이 중간에 중단될 수 있도록 해야한다.
비선점형 스케줄러 vs. 선점형 스케줄러
비선점형 스케줄러(non-preemptive scheduler): 각 작업이 종료될 때까지 계속 실행하는 스케줄러로 과거에 많이 개발되어 사용되었었고, 종류로는 FIFO(FCFS), SJF 등이 있다.
선점형 스케줄러(preemptive scheduler): 필요에 따라 문맥 교환을 수행하여 현재 프로세스의 실행을 중단하고 다른 프로세스를 실행시키는 스케줄러로 현대의 거의 모든 스케줄러가 이 방식을 채택하고 있으며, 종류로는 STCF, RR 등이 있다.
STCF 스케줄러는 SJF에 선점 기능을 추가한 스케줄러이다.
동작 방식
3️⃣의 두 번째 예시 상황을 바탕으로 동작 방식을 살펴보자.
[10에 B, C 도착]
↓
[A(10/100)][ B(10) ][ C(10) ][ A(90/100) ]
| | | | |
0 10 20 30 120 ...
시간의 흐름 →위와 같이 STCF 스케줄러는 새로운 작업이 시스템에 들어오면, 남아 있는 작업과 새로운 작업의 잔여 실행 시간을 계산하고 그 중 가장 적은 잔여 실행 시간을 가진 작업을 실행한다.
이때 이 작업들의 평균 반환 시간은?
A는 120, B는 20, C는 30에 종료 ➡️ ((120 - 0) + (20 - 10) + (30 - 10))/3 = 50
작업이 동시에 도착할 때 SJF가 최적의 결과를 냄 ➡️ 작업의 임의 도착 & 작업 선점 가능: 최적의 스케줄링
6️⃣ 새로운 평가 기준: 응답 시간
응답 시간(response time): 작업이 도착할 때부터 처음 스케줄 될 때까지의 시간
T_response = T_firstrun - T_arrival
5️⃣의 예시와 같은 상황의 경우,
[10에 B, C 도착]
↓
[A(100)][B(10)][C(10)][ A(90/100) ]
| | | | |
0 10 20 30 120 ...
시간의 흐름 →응답 시간은 A는 0, B는 0, C는 10 ➡️ (0 + 0 + (20 - 10))/3 = 3.33...
STCF와 같은 류의 정책들은 응답 시간이 짧다고 할 수 있다.
반환 시간이 훌륭하다고 해도 응답 시간 및 상호작용 측면의 성능은 또 다른 이야기
7️⃣ 라운드 로빈(Round-Robin, RR)
작업을 일정 시간 동안 실행한 후 실행 큐의 다음 작업으로 전환한다.
타임 슬라이스(time slice)
작업이 실행되는 일정 시간을 의미하며 스케줄링 퀀텀(scheduling quantum)이라고도 불린다.
위와 같은 이유로 RR은 때때로 타임 슬라이싱이라고 불림.
타임 슬라이스의 길이는 타이머 인터럽트 주기의 배수여야한다.
동작 방식
시스템에 순서대로 3개의 작업 A, B, C가 동시에 도착했다고 가정(각 작업은 5초 동안 실행)
또한 시스템의 RR 스케줄러가 1 단위의 타임 슬라이스를 가진다고 가정
SJF 스케줄러의 경우
[ A(5) ][ B(5) ][ C(5) ]
| | | |
0 5 10 15 ...
시간의 흐름 →응답 시간은 A는 0, B는 5, C는 10 ➡️ (0 + 5 + 10)/3 = 5
RR 스케줄러의 경우
[A][B][C][A][B][C][A][B][C][A][B][C][A][B][C]
| | | |
0 5 10 15 ...
시간의 흐름 →응답 시간은 A는 0, B는 1, C는 2 ➡️ (0 + 1 + 2)/3 = 3
타임 슬라이스의 길이는 어느 정도가 적당한가?
타임 슬라이스가 짧을 수록 응답 시간 기준으로 RR의 성능은 좋아짐.
But, 타임 슬라이스가 너무 짧은 경우 ➡️ 문맥 교환 비용이 전체 성능에 큰 영향
예시
타임 슬라이스: 100 msec & 문맥 교환 비용: 1 msec ➡️ 약 1%의 시간이 문맥 교환에 낭비
타임 슬라이스: 10 msec & 문맥 교환 비용: 1 msec ➡️ 약 10%의 시간이 문맥 교환에 낭비
즉, 문맥 교환 비용 상쇄(긴 타임 슬라이스) vs. 빠른 응답 시간(짧은 타임 슬라이스)
RR의 특징 조금 더 살펴보기
반환 시간이 유일한 측정 기준인 경우 RR은 최악의 정책
대부분의 경우 단순한 FIFO보다 성능이 좋지 않음.
일반적으로 RR과 같은 공정한 정책(작은 시간 단위로 모든 프로세스에게 CPU 분배)은 반환 시간과 같은 평가 기준에서 성능이 나쁨.
8️⃣ 입출력 연산의 고려
1️⃣의 "가정 4"를 완화하여 모든 프로세스가 I/O 작업을 수행한다고 해보자.
프로세스 A가 I/O 작업을 요청한 경우 ➡️ A는 I/O 완료 시까지 대기 상태
A의 I/O 완료 시 ➡️ 인터럽트 발생(운영체제 실행) ➡️ A는 준비 상태로 이동 또는 실행
예를 들어, 50시간 단위의 프로세스 A, B가 있고 A는 10마다 10 크기의 I/O 요청을 한다고 가정했을 때, STCF 스케줄러의 경우 다음과 같이 작동한다.
CPU [ A ][ B ][ A ][ B ][ A ][ B ][ A ][ B ][ A ][ B ]
DISC [I/O] [I/O] [I/O] [I/O]
| | | | | | | | | | |
0 10 20 30 40 50 60 70 80 90 100 ...
시간의 흐름 →시스템 측면에서는 50 크기의 두 프로세스가 아닌 5개의 10 크기로 나뉜 독립 프로세스들(A1, A2, ..., A5)과 50 크기의 프로세스 B를 다루는 것이 일반적인 접근 방식이다.
이러한 경우 STCF의 동작 방식인 "남아 있는 작업들 중 가장 적은 잔여 실행 시간을 가진 작업을 실행"에 따라 운영체제는 A의 I/O 작업이 이루어질 동안 B를 실행시키게 된다. ➡️ 연산의 중첩
이후 I/O 작업이 끝날 때마다 인터럽트가 발생되며 STCF 정책에 따라 A와 B가 번갈아가며 실행되게 될 것이다.
즉, I/O를 고려한 스케줄링 방식은
대화형 프로세스가 더 자주(유리하게) 실행되는 것을 보장
각 CPU burst를 하나의 작업으로 간주
CPU의 이용률이 높아짐
대화형 작업이 I/O를 실행 ➡️ 다른 CPU burst 작업이 실행
9️⃣ 만병통치약은 없다(No More Oracle)
1️⃣의 마지막 가정: 각 작업의 실행 시간은 사전에 알려져 있다. ➡️ 가정 중 가장 비현실적
범용 운영체제에서 작업의 길이에 대해서 알 수 있는 방법은 없다.
이러한 상황에서 SJF/STCF 처럼 행동하는 알고리즘을 구축할 수 있을까?
여기에 응답 시간 개선을 위한 RR 스케줄러의 아이디어까지 포함이 가능할까?
멀티 레벨 피드백 큐(multi-level feedback queue)를 통해 해결을 시도해볼 수 있음!
📚 참고 문헌
Operating Systems: Three Easy Pieces ― 7: Scheduling: Introduction
![[운영체제][OSTEP] 제한적 직접 실행 원리](https://www.datocms-assets.com/66479/1686988115-ostep.jpg?ar=1&auto=format&crop=focalpoint&dpr=0.47&fit=crop&fp-x=0.5&fp-y=0.5&w=430)