단기 스케줄러(short term scheduler, CPU 스케줄러)가 프로세스를 스케줄링 하는 방법에 대해 알아보자.
1. CPU 스케줄링 개요
CPU란?
- CPU란 프로그램의 기계어 명령을 실제로 수행하는 중앙처리장치이다.
- 프로그램이 시작되어 메모리에 올라가면, 프로그램 카운터(PC)라는 레지스터가 현재 CPU에서 수행할 코드의 메모리 주소값을 가진다.
- CPU는 프로그램 카운터가 가리키는 주소의 기계어 명령을 하나씩 수행한다.
프로그램 실행과 관련된 기계어 명령
[1] 일반 명령
- CPU 내에서 수행되는 명령
Add명령: CPU 내의 레지스터에 있는 두 값을 더해 레지스터에 저장한다.
- 메모리 접근을 필요로 하는 명령
Load명령: 메모리에 있는 데이터를 CPU로 읽어들인다.Store명령: CPU에서 계산된 결과 값을 메모리에 저장한다.
[2] 특권 명령
- 입출력을 동반하는 명령 (ex. 키보드, 화면, 디스크 등)
- 다른 명령에 비해 오랜 시간이 소요된다.
- 사용자 프로그램이 직접 수행할 수 없도록 하고 운영체제를 통해 서비스를 대행하도록 한다.
CPU Burst & I/O Burst
| 구분 | 설명 | 구간 |
|---|---|---|
| CPU burst | 사용자 프로그램이 CPU를 직접 가지고 빠른 명령을 수행하는 일련의 단계 | I/O를 한 번 수행한 후 다음 번 I/O를 수행하기까지 |
| I/O burst | I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계 | I/O 작업이 요청된 후 완료되어 다시 CPU burst로 돌아가기까지 |
CPU Bound Process & I/O Bound Process
각 프로그램마다 CPU burst와 I/O burst가 차지하는 비율이 균일하지는 않다.
| 프로세스 종류 | 설명 | 예시 | CPU burst의 양상 |
|---|---|---|---|
| CPU Bound Process | I/O 작업을 거의 수행하지 않아 CPU burst가 길게 나타나는 프로세스 | 계산 위주 프로그램 | 소수의 긴 CPU burst |
| I/O Bound Process | I/O 요청이 빈번해 CPU burst가 짧게 나타나는 프로세스 | 대화형 프로그램 | 다수의 짧은 CPU burst |
CPU 스케줄링의 필요성
- CPU를 사용하는 패턴이 상이한(= CPU burst가 균일하지 않은) 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 효율적으로 CPU를 스케줄링하는 것이 필요하다.
- 대부분의 프로세스들의 CPU burst는 짧고, 극히 일부만 긴 CPU burst를 가진다.
CPU 스케줄링 시 I/O bound process의 우선순위를 높여주는 것이 바람직하다.
I/O bound process = CPU burst가 짧다 = 대화형 작업이다 = 빠른 응답이 중요하다!
- 대화형 프로세스의 빠른 응답성 제공
- I/O 장치의 효율성 향상
2. CPU 스케줄러
ready상태(= 준비 큐)에 있는 프로세스들 중 어떠한 프로세스에게 CPU를 할당할지 결정하는 운영체제 코드
CPU 스케줄러가 필요한 경우
running상태에 있던 프로세스가 I/O 요청 등에 의해blocked상태로 바뀌는 경우running상태에 있던 프로세스가 timer interrupt 발생에 의해ready상태로 바뀌는 경우- I/O 요청으로
blocked상태에 있던 프로세스의 I/O 작업이 완료되어 interrupt가 발생하고, 그 결과 해당 프로세스의 상태가ready상태로 바뀌는 경우 - CPU에서
running상태에 있는 프로세스가 terminate 되는 경우
CPU 스케줄링 방식
| 스케줄링 방식 | 설명 |
|---|---|
| nonpreemptive (비선점형) | CPU를 획득한 프로세스가 CPU를 스스로 반납하기 전까지는 CPU를 빼앗기지 않는 방식 |
| preemptive (선점형) | CPU를 프로세스로부터 강제로 빼앗을 수 있는 방식 → time quantum을 부여하여 timer interrupt 발생 |
3. 디스패처 (Dispatcher)
CPU 스케줄러에 의해 선택된 프로세스가 CPU를 할당 받고 작업을 수행할 수 있도록 환경설정을 하는 운영체제 코드
디스패처의 동작
- 현재 수행 중이던 프로세스의 context를 그 프로세스의 PCB에 저장한다.
새롭게 선택된 프로세스의 context를 PCB로부터 복원한다.
사용자 프로그램은 복원된 context 중 PC로부터 현재 수행할 주소를 찾을 수 있다.
- 선택된 프로세스에게 CPU를 넘기고, 시스템의 상태를 user mode로 전환한다.
디스패치 지연시간 (dispatch latency)
- 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간이다.
- 대부분은 문맥교환 오버헤드에 해당된다.
4. 스케줄링 성능 평가
[1] 시스템 관점의 지표
최대일수록 좋다.
CPU 이용률 (CPU Utilization)
- 전체 시간 중 CPU가 일을 한 시간의 비율
- CPU가 idle 상태에 머무르는 시간을 최대한 줄이는 것이 스케줄링의 중요한 목표이다.
처리량 (Throughput)
주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 마쳤는지
= CPU burst를 완료한 프로세스의 개수
CPU burst가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
[2] 사용자 관점의 지표
최소일수록 좋다.
소요시간 (Turnaround Time)
프로세스가 CPU를 요청한 시점부터 CPU burst가 끝날 때까지 걸린 시간
= 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간
프로그램이 종료되기까지 걸리는 시간이 아니다. 프로그램 실행 중 CPU burst는 여러 차례 있을 수 있으므로, 소요시간은 CPU burst의 수만큼 각각 별도로 측정된다.
대기시간 (Waiting Time)
- 이번 CPU burst 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 총합
- 시분할 시스템에서는 일반적으로 timer를 통해 하나의 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한한다.
응답시간 (Response Time)
- 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간
- timer interrupt가 빈번히 발생할수록 각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 짧아지므로, 응답시간이 향상된다.
- 대화형 시스템에 적합한 성능 척도이다. (사용자 입장에서 가장 중요)
5. 스케줄링 알고리즘
[1] 선입선출 스케줄링 (FCFS; First-Come First-Served)
프로세스가 준비 큐에 도착한 순서대로 CPU를 할당하는 방식
- nonpreemptive - 프로세스가 CPU를 자발적으로 반납할 때까지 CPU를 빼앗지 않는다.
먼저 도착한 프로세스의 성격에 따라 평균 대기시간이 크게 달라진다.
콘보이 현상 (Convoy effect)
- CPU burst가 짧은 프로세스가 CPU burst가 긴 프로세스보다 나중에 도착해 오랜 시간을 기다려야 하는 현상
- FCFS 스케줄링의 대표적인 단점
- 이후에 도착한 CPU burst가 짧은 프로세스가 여러 개인 경우의 문제점
- 평균 대기시간이 길어지게 된다.
- I/O 장치의 이용률이 낮아진다.
[2] 최단작업 우선 스케줄링 (SJF; Shortest-Job First)
CPU burst가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식
nonpreemptive & preemptive 두 가지 방식으로 구현될 수 있다.
구현 방식 스케줄링 알고리즘 이름 설명 nonpreemptive SJF (Shortest Job First) 실행 중인 프로세스가 CPU를 자진 반납하기 전까지는
CPU를 빼앗지 않는다.preemptive SRTF (Shortest Remaining Time First) 프로세스 실행 중에 CPU burst가 더 짧은 프로세스가
도착할 경우 CPU를 빼앗아 더 짧은 프로세스에게 부여한다.preemptive 방식의 SRTF는 다음과 같은 특징을 가진다.
일반적인 시분할 환경에서 평균 대기시간을 가장 짧게하는 optimal algorithm이다.
프로세스들이 준비 큐에 도착하는 시간이 불규칙한 환경이 아닌, 준비 큐에 프로세스들이 한꺼번에 도착하는 환경에서는 nonpreemptive(SJF) 방식과 preemptive 방식이 같은 결과를 나타내기도 한다.
(1) 프로세스가 새롭게 도착하거나 (2) 작업이 끝날 때마다 CPU burst time을 비교하게 된다.
- 프로세스의 CPU burst time을 미리 알 수 없으므로, 과거의 CPU burst time을 이용한 예측을 통해 CPU burst time을 구한다.
(n+1) 번째 CPU burst의 예측 시간 $T_{n+1}$은 다음과 같다.
\[T_{n+1}=\alpha t_n+(1-\alpha)T_n\]- $t_n$: n번째 실제 CPU burst time
- $T_n$: n번째 CPU burst의 예측 시간
- $\alpha$ 값을 (0, 1) 사이의 값으로 설정하면 실제 CPU burst time과 예측된 CPU burst time을 가중 평균하여 다음 CPU burst time의 예측치를 계산하게 된다.
최근의 CPU burst time일수록 오래전의 CPU burst time에 비해 가중치가 높아진다.
\[T_{n+1}=\alpha t_n+(1-\alpha)at_{n-1}+...+(1-\alpha)^j\alpha t_{n-j} +...\]
평균 대기시간을 최소화하는 알고리즘이지만, 기아 현상이라는 심각한 문제점을 가지고 있다.
기아 현상 (starvation)
CPU burst가 짧은 프로세스에게만 CPU를 할당할 경우, CPU burst가 긴 프로세스는 준비 큐에 줄을 서서 무한정 기다려야 하는 현상이다.
[3] 우선순위 스케줄링 (Priority Scheduling)
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식
우선순위 값(priority number)이 작을수록 높은 우선순위를 가진다.
CPU burst time을 우선순위 값으로 정하면 SJF 알고리즘과 동일해진다.
- nonpreemptive & preemptive 방식으로 구현할 수 있다.
기아 현상(starvation)이 발생할 수 있다는 문제점을 가지고 있다.
노화 기법(aging)을 통해 해결할 수 있다.
→ 기다리는 시간이 길어지면 우선순위를 조금씩 높여주어 언젠가는 가장 높은 우선순위가 되도록 한다.
[4] 라운드 로빈 스케줄링 (Round Robin Scheduling)
각 프로세스가 CPU를 연속적으로 사용할 수 있는 시간이 특정 시간으로 제한되어, 해당 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 있는 다른 프로세스에게 CPU를 할당하는 방식
- 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식이다.
- time quantum - 각 프로세스마다 한 번에 CPU를 연속적으로 사용할 수 있는 최대시간
너무 길면 FCFS와 같은 결과를 내게 되며, 너무 짧으면 문맥교환 오버헤드가 커진다.
문맥교환 오버헤드가 커지면 CPU 이용률이 낮아진다. (전체 시간 중 일부는 CPU가 작업을 수행하지 못하므로)
- 일반적으로 수십 ms 정도로 설정한다.
- CPU burst time 시 time quantum이 만료되면 timer interrupt를 통해 CPU를 회수하며, CPU burst time이 time quantum보다 짧으면 CPU를 스스로 반납한다.
- 장점
여러 종류의 이질적인 프로세스가 같이 실행되는 환경에서 효과적이다.
n개의 프로세스가 준비 큐에 있고 할당 시간이 q라고 할 때, 모든 프로세스는 적어도 $(n-1)q$ 시간 내에 한 번은 CPU를 할당받게 된다.
- 대화형 프로세스의 빠른 응답시간을 보장할 수 있다.
각 프로세스의 대기시간이 그 프로세스의 CPU burst time에 비례해서 길어진다.
CPU burst time이 균일하지 않은 일반적인 시스템에서 적합한 스케줄링 방식이다.
- 공정한 스케줄링 방식이다.
- CPU burst time이 짧은 프로세스가 빨리 CPU를 얻는 동시에, CPU burst time이 긴 프로세스가 불이익을 당하지 않도록 하는 것이 목적이다.
- CPU burst time에 비례하여 소요시간과 대기시간이 결정된다.
- 일반적으로 SJF 방식보다 평균 대기시간은 길지만 응답시간은 더 짧다.
FCFS 스케줄링 vs. RR 스케줄링
- 동일한 CPU burst time을 가지는 프로세스들이 동시에 도착한 경우, 다음과 같은 특징이 있다.
- FCFS 스케줄링 - CPU를 먼저 쓰고 나가는 프로세스의 소요시간/대기시간이 짧아진다.
- RR 스케줄링 - CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 소요시간/대기시간이 가장 오래 기다린 프로세스에 맞춰진다. 따라서 평균 대기시간/소요시간은 더 길어지고, 평균 응답시간은 더 짧아진다.
장점 단점 FCFS 스케줄링 평균 대기시간, 소요시간 측면에서 좋다. - 프로세스 간 대기시간, 소요시간의 편차가 매우 크다.
- 평균 응답시간이 지나치게 길어진다.RR 스케줄링 - 대기시간, 소요시간의 편차가 크지 않다.
- 평균 응답시간이 짧아진다.평균 대기시간, 소요시간이 길어진다. - 하지만 일반적인 시스템에서는 프로세스의 CPU burst time이 균일하지 않다.
- FCFS 스케줄링 - CPU burst가 긴 프로세스가 먼저 도착하면 소요시간의 편차가 클 뿐 아니라 그 평균값도 극단적으로 증가한다.
- RR 스케줄링 - 프로세스의 CPU 사용량에 비례하여 소요시간이 증가하여 합리적이다.
[5] 멀티레벨 큐 (Multi-Level Queue)
준비 큐를 여러 개로 분할해 관리하는 스케줄링 기법
- 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 각 성격에 맞는 스케줄링을 적용하기 위함이다.
멀티레벨 큐의 구성
큐 종류 작업 종류 스케줄링 기법 전위 큐 (foreground queue) 대화형 작업 RR 스케줄링 (응답시간 ⬇️) 후위 큐 (background queue) 계산 위주의 작업 FCFS 스케줄링 (문맥교환 오버헤드 ⬇️) - 큐 자체에 대해서도 스케줄링을 해야 한다.
- 고정 우선순위 방식 (fixed priority scheduling)
- 큐에 고정적인 우선순위를 부여하여 우선순위가 높은 큐를 먼저 서비스하고, 우선순위가 낮은 큐는 높은 큐가 비어있을 때에만 서비스한다.
- 전위 큐 & 후위 큐를 사용하는 방식에서는 우선순위가 전위 큐 > 후위 큐이다.
- 타임 슬라이스 방식 (time slice)
- 큐에 대한 기아 현상(starvation)을 해소할 수 있다.
- 각 큐에 CPU 시간을 적절한 비율(ex. 전위 큐 80%, 후위 큐 20%)로 할당한다.
- 고정 우선순위 방식 (fixed priority scheduling)
[6] 멀티레벨 피드백 큐 (Multi-Level Feedback Queue)
멀티레벨 큐와 동일하나 프로세스가 하나의 큐에서 다른 큐로 이동 가능한 방식
멀티레벨 큐의 기아 현상(starvation)을 해결하기 위해 노화 기법(aging)을 구현할 수 있다.
우선순위가 낮은 큐에서 오래 기다렸으면 우선순위가 높은 큐로 승격시킨다.
- 멀티레벨 피드백 큐를 정의하는 요소
- 큐의 개수
- 각 큐의 스케줄링 알고리즘
- 프로세스를 상위 큐로 승격시키는 기준
- 프로세스를 하위 큐로 강등시키는 기준
- 프로세스 도착 시 들어갈 큐를 결정하는 기준
- 상위 큐일수록 우선순위가 높으며, 각 큐에서 CPU burst time이 끝나지 않은 프로세스는 하위 큐로 이동하게 된다.
- CPU 작업시간이 짧은 프로세스의 경우(ex. 대화형 프로세스), 더욱 빠른 서비스가 가능하다.
- CPU 작업시간이 긴 프로세스의 경우(ex. 계산 위주 프로세스), 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 스케줄링을 적용할 수 있다.
- 큐에 대한 스케줄링 방식
- 최상위 큐가 우선적으로 CPU를 배당받는다.
- 상위 큐가 비었을 때만 하위 큐에 있는 프로세스들이 CPU를 할당받을 수 있다.
[7] 다중처리기 스케줄링 (Multi-Processor)
- 다중처리기 시스템(multi-processor system)이란, CPU가 여러 개인 시스템이다.
- 다중처리기 시스템에서는 크게 두 가지 방식으로 스케줄링을 수행할 수 있다.
- 하나의 준비 큐에 프로세스를 줄 세워, 각 CPU가 알아서 다음 프로세스를 꺼내어가도록 한다.
- 각 CPU 별로 프로세스를 줄 세운다.
- 반드시 특정 CPU에서 수행되어야 하는 프로세스가 있는 경우에 필요한 방식이다.
- 이와 같이 여러 줄로 줄을 세우는 경우, 일부 CPU에 작업이 몰릴 수 있으므로 load balancing 메커니즘이 필요하다.
다중처리기 스케줄링 방식
구분 동작 대칭형 (symmetric multi-processing) 각 CPU가 각자 알아서 스케줄링을 결정한다. 비대칭형 (asymmetric multi-processing) 하나의 CPU가 다른 모든 CPU의 스케줄링 및 데이터 접근을 책임진다.
[8] 실시간 스케줄링 (Real-Time)
각 작업마다 주어진 데드라인이 있어 그 안에 반드시 작업을 처리해야 하는 실시간 시스템(real-time system)에 필요한 스케줄링이다.
일반적인 시분할 시스템에서는 작업에 데드라인이 존재하지 않는다.
실시간 시스템의 분류
구분 설명 경성 실시간 시스템
(hard real-time system)정해진 시간 안에 반드시 작업이 완료되도록 스케줄링해야 한다. (ex. 미사일 발사 등) 연성 실시간 시스템
(soft real-time system)데드라인이 존재하기는 하나 데드라인을 지키지 못하더라도 위험한 상황이 발생하지는 않는다.
(ex. 멀티미디어 스트리밍 시스템)실시간 시스템에서는 빠른 서비스도 중요하지만 데드라인을 지키는 서비스가 더 중요하다.
- EDF(Earlist Deadline First) 스케줄링 - 데드라인이 얼마 남지 않은 요청을 먼저 처리하는 방식
- 연성 실시간 시스템과 같은 환경(ex. 일반 작업과 VOD 작업이 혼합된 환경) 에서는 데드라인이 존재하는 프로세스에게 일반 프로세스보다 높은 우선순위를 할당하는 방식도 사용된다.
6. 스케줄링 알고리즘의 평가
[1] 큐잉 모델 (Queueing Model)
- 주로 이론가들이 수행하는 방식이다.
- 확률분포를 통해 프로세스들의 도착률, CPU의 처리율을 입력값으로 주면 수학적 계산을 통해 각종 성능 지표(ex. CPU 처리량, 평균 대기시간 등)를 산출한다.
[2] 구현 및 실측 (Implementation & Measurement)
- 구현가들이 수행하는 방식이다.
- 동일한 프로그램을 원본 커널과 CPU 스케줄러를 수정한 커널에서 각각 수행시켜보고 성능을 평가한다.
[3] 시뮬레이션 (Simulation)
- 가상으로 CPU 스케줄링 프로그램을 작성한 후, 프로그램의 CPU 요청을 입력값으로 넣어 결과를 확인하는 방식이다.
입력값은 가상으로 생성할 수도 있고, 트레이스를 사용할 수도 있다.
트레이스 (trace)
- 실제 시스템에서 추출한 CPU 요청 내역이다.
- 몇 초에 어떤 프로세스가 도착하고, 각 CPU burst time을 얼마로 하는지에 대한 정보가 시간순으로 기록된 파일이다.
References
- “운영체제와 정보기술의 원리(반효경 저)”, 6장 CPU 스케줄링