질문의 핵심
- CPU 스케쥴링이란?
- CPU 스케쥴링 알고리즘의 종류와 특징은?
- 어떤 기준으로 CPU 스케쥴링을 선택해야 하는지?
- 스케쥴링의 효율을 분석하는 기준은?
- CPU 스케쥴러를 사용하는 이유는?
- 선점형/비선점형 스케쥴링은?
1. CPU 스케쥴링
CPU 스케쥴링이란?
CPU 스케쥴링은 다중 프로그래밍(=멀티 프로그래밍)을 가능하게 하는 운영체제 동작 기법이다.
다중 프로그래밍이란?
- 다수의 작업(ex. 프로세스)이 CPU 및 공용자원을 나누어 사용하는 것.
- 멀티 프로세싱, 멀티태스킹이라고도 한다.
한 번에 하나의 작업을 하는 CPU가 동시에 여러 작업을 하는 것처럼 보이게 한다. 다중 프로그래밍을 하려면 어떤 작업을 해야할지 선택하는 CPU 스케쥴링이 필요하다.
CPU-I/O 버스트 사이클(CPU-I/O Burst Cycle)
프로세스의 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다. CPU 버스트로 실행된 프로세스는 I/O 버스트와 CPU 버스트가 번갈아가며 발생하다가 마지막 CPU 버스트와 함께 끝난다.
[그림 출처] Opearting System Concepts
2. CPU 스케쥴러
CPU 스케쥴러(CPU Scheduler)
CPU 스케쥴러는 Ready 큐에 있는 어떤 프로세스를 CPU에 할당할 것인지 결정한다.
규모에 따라 CPU 스케쥴러의 종류를 나눌 수 있다.
장기 스케쥴러(Long-Term Scheduler)
- 가장 큰 틀에서 이루어지는 CPU 스케쥴링.
- 어떤 프로세스가 시스템의 자원을 차지할 것인지를 결정해 Ready 큐로 보내는 작업.
- 수행 빈도가 적고 느림.
- 최근 운영체제는 프로그램을 실행시키면 곧바로 Ready 상태로 돌입하기 때문에 장기 스케쥴러가 없음.
중기 스케쥴러(Medium-Term Scheduler, Swapper)
- 어떤 프로세스들이 CPU를 할당 받을 것인지, 어떤 프로세스들을 중지할지 결정하는 작업.
- 프로세스가 많을 경우, 프로세스를 Waiting 시킨 후 활성화해서 부하를 조절.
- 메모리가 부족하면 프로세스를 통째로 메모리에서 디스크로 추방(swap out), 메모리가 남으면 swap in 결정.
단기 스케쥴러(Short-Term Scheduler, CPU Scheduler)
- 프로세스가 실행되기 위해 CPU를 할당받는 시기와 특정 프로세스를 지정하는 작업.
- 가장 작은 단위의 스케쥴링.
- 자주 수행되고 빠름.
디스패쳐(Dispatcher)
- CPU의 제어권을 CPU 스케쥴러에 의해 선택된 프로세스에게 넘겨주는 모듈.
- Context Switch를 수행하는 모듈.
- 커널 모드에서 유저 모드로 변경.
Context Switch가 일어날 때마다 호출되기 때문에 디스패쳐는 최대한 빨라야 한다. 즉, 디스패쳐 Latency가 작아야 한다.
- 디스패쳐 Latency: 디스패쳐가 한 프로세스를 멈추고 다른 프로세스에게 CPU의 제어권을 넘기는 데 걸리는 시간.
3. CPU 스케쥴링 방식
선점 스케쥴링(Preemptive Scheduling)
프로세스가 스케쥴러에 의해 CPU를 선점하는 방식. 다른 프로세스가 CPU를 강제로 점유할 수 있다. Context Switch로 인한 오버헤드가 발생할 수 있다.
비선점 스케쥴링(Non-preemptive Scheduling)
프로세스가 자율적으로 반납할 때까지 CPU를 선점하는 방식. I/O(프로세스는 Waiting 상태가 됨)나 프로세스가 종료될 때까지 다른 프로세스는 CPU를 점유하지 못한다. 전체 시스템의 처리율이 선점 스케쥴링에 비해 떨어진다.
스케쥴링 결정
CPU 스케쥴링의 결정은 다음 네 가지 상황에서 발생할 수 있다. 각 상황에서 스케쥴링 방식은 다음과 같다.
- 한 프로세스가 Running 상태에서 Waiting 상태로 전환될 때(ex. I/O) - 비선점 스케쥴링
- 프로세스가 Running 상태에서 Ready 상태로 전활될 때(ex. 인터럽트 발생) - 선점/비선점 스케쥴링
- 프로세스가 Waiting 상태에서 Ready 상태로 전환될 때(ex. I/O 종료) - 선점/비선점 스케쥴링
- 프로세스가 종료될 때 - 비선점 스케쥴링
두 가지 방식을 모두 사용할 수 있을 경우 선점 스케쥴링이 효율적이므로 선점 스케쥴링을 선택하는 것이 좋다.
4. CPU 스케쥴링 알고리즘
스케쥴링 기준(Scheduling Criteria)
CPU 스케쥴링 알고리즘 중 하나를 선택하기 위해 스케쥴링의 효율을 분석하는 기준이다.
- CPU 이용률(Utilization): 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 최대화가 목적.
- 처리량(Throughput): CPU가 단위 시간당 처리하는 프로세스의 개수. 최대화가 목적.
- 반환시간(Turnaround Time): 프로세스가 시작해서 끝날 때까지 걸리는 시간.
작업 종료 시간-도착 시간으로 계산. 최소화가 목적. - 대기시간(Waiting Time): 프로세스가 Ready 큐에서 대기한 시간의 총합.
마지막 작업 시작 시간-도착 시간으로 계산. 최소화가 목적. - 응답시간(Response Time): 요청 후 응답이 오기 시작할 때까지의 시간. 최소화가 목적.
스케쥴링 알고리즘(Scheduling Algorithm)
First-Come, First-Served(FCFS)
- 먼저 CPU 사용을 요청한 프로세스에게 CPU를 할당해주는 방식.
- 가장 간단한 알고리즘.
- 비선점 스케쥴링.
- 프로세스 별 점유 시간(Burst Time)의 차이가 큰 경우, 평균 대기시간이 최소가 아닐 수 있다.
- 호송 효과(Convoy Effect): 소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 현상.
Shortest-Job-First(SJF)
- CPU 점유 시간이 가장 짧은 프로세스에 CPU를 할당해주는 방식.
- 두 개 이상의 프로세스의 점유 시간이 같다면 FCFS 방식으로 처리.
- 최소 평균 대기 시간을 위해 최적화된 알고리즘.
- 선점 스케쥴링과 비선점 스케쥴링 모두 가능.
- 선점 스케쥴링이 더 효율적임.
- 다음 CPU의 소요시간을 알 수 있는 방법이 없어 현실성이 떨어짐.
- 측정된 과거의 CPU 소요시간의 지수 이동 평균(Exponential Moving Average)으로 다음 CPU 소요 시간 예측.
- 이동 평균(Moving Average): 전체 데이터 집합의 여러 하위 집합에 대한 일련의 평균을 만들어 데이터 요소를 분석하는 계산.
Shortest-Remaining-Time-First(SRTF)
- 남은 소요 시간이 가장 짧은 프로세스에 CPU를 할당해주는 방식.
- 현재 수행 중인 프로세스보다 더 짧은 소요 시간을 가진 새로운 프로세스가 도착할 경우 CPU를 강제로 할당함.
- 선점 스케쥴링.
Round-Robin(RR)
- 시분할(Time Sharing) 방식.
- 스케쥴러가 준비 대기열을 돌며 프로세스들 사이에 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식.
- 시간 단위(Time Quantum): Time Slice. 프로세스에게 할당되는 최대 CPU 시간.
- 선점 스케쥴링.
- Ready 큐는 원형 큐 형태로 구현됨.
- 프로세스가 시간 단위 미만의 소요 시간을 가지는 경우 프로세스가 자율적으로 반납하거나 스케쥴러가 Ready 큐의 다음 프로세스 실행.
- 종종 평균 대기시간이 길 수 있음.
- 성능은 시간 단위의 크기에 따라 결정됨.
- 디스패쳐 Latency가 늘어나서 성능 저하될 수 있음.
- 시간 단위가 너무 크면 FCFS가 됨.
Priority-base
- 우선 순위가 가장 높은 프로세스에 CPU를 할당하는 방식.
- 우선 순위는 내부적/외부적으로 정의될 수 있음.
- 우선 순위를 나타내는 정수값이 작을 수록 우선순위가 높음.
- 선점 스케쥴링과 비선점 스케쥴링 모두 가능.
- 우선 순위가 같은 프로세스끼리는 FCFS 순서로 스케쥴링.
- 우선 순위가 낮은 일부 프로세스가 무기한 대기 상태에 있는 기아(Starvation) 문제가 발생할 수 있음.
- 에이징(Aging): 시스템에서 오랫동안 대기하는 프로세스의 우선 순위를 점차 높이는 방법. 기아 문제를 해결할 수 있음.
Multi-Level Queue(MLQ)
- 우선 순위에 따라 Ready 큐를 여러개 사용해서 우선 순위가 높은 큐에 CPU를 먼저 할당하는 방식.
- 큐에 속한 모든 프로세스가 처리된 후 다음 우선 순위 큐 실행.
- 각 큐에는 자체 스케쥴링 알고리즘을 구현할 수 있음.
- 선점 스케쥴링.
- 기아 문제 발생할 수 있음.
Multi-Level Feedback Queue(MLFQ)
- MLQ를 보완한 방식.
- Ready 큐 간 승격/강등의 개념이 존재하여 프로세스의 큐 이동 가능.
- 할당된 시간 안에 수행이 안 되면 우선 순위가 하락하여 다음 큐로 강등.
- 모든 프로세스가 첫 번째 Ready 큐에 놓인 후 수행.
- 우선 순위가 낮은 큐에 시간 단위 크기를 크게 할당.
참조
Hans Jo