CPU 스케줄링(CPU Scheduling)
개요
CPU 스케줄링은 프로세스에 CPU의 자원을 할당하는 작업을 말하며, 이러한 작업을 수행하는 것이 CPU 스케줄러이다. CPU 스케줄러는 프로세스들이 다음과 같은 상태에 있을 때 스케줄링을 실시한다.
- 실행(running) 상태에서 대기(waiting) 상태로 전환(switching)될 때(I/O 발생)
- 실행 상태에서 준비 상태로 전환될 때(Intterupt 발생)
- 대기 상태에서 준비 상태로 전환될 때((I/O 완료)
- 프로세스가 종료될 때
I/O
입력(Input)과 출력(Output)을 아울러 말하는 것으로, 입력 장치로는 키보드나 마우스, 출력 장치로는 모니터나 스피커 등이 대표적인 예이다. 그러나 I/O는 데이터의 입출력도 포함하며, 하드디스크 등의 보조기억장치도 데이터의 입출력이 발생하는 대표적인 장치라 할 수 있다.
즉, 프로세스에서 I/O가 발생한다는 것은 사용자의 입력을 필요로 하거나 특정 장치로의 출력을 수행하는 작업이 필요하다는 것을 의미하며, 또한 어떤 데이터의 저장이나 로드 역시 포함된다.
스케줄링의 구분
스케줄링은 크게 비선점형(non-preemtive)과 선점형(preemtive)으로 구분할 수 있는데, 앞선 상황 중 1번과 4번 상황에서만 스케줄링을 수행하는 방식, 즉 프로세스의 실행과 종료 시에만 스케줄링을 수행하는 방식을 비선점형 스케줄링이라고 한다. 반대로 선점형 스케줄링은 4가지 상황 모두에서 스케줄링을 수행하는 방식이다.
- 비선점형 스케줄링
프로세스가 CPU를 점유하고 있을 경우 이를 빼앗을 수 없는 방식으로, 프로세스의 실행과 종료 시에만 문맥 교환이 일어나므로 오버헤드(Overhead)의 발생이 상대적으로 적으나 프로세스의 배치에 따른 효율성 차이가 크게 나타난다.오버헤드는 어떤 처리를 하기 위해 필요한 간접적인 처리 시간이나 사용 메모리 등의 자원을 말한다. 예컨대 어떤 프로세스 A를 처리하기 위해 10초가 걸리지만 안정성이나 기타 사항으로 고려한 처리를 포함할 경우 15초가 소요된다면, 5초의 오버헤드가 발생하는 것이다. 문맥 교환 역시 시간과 메모리를 필요로 하며, 오버헤드의 원인이 될 수 있다.
- 선점형 스케줄링
프로세스가 CPU를 할당받아 실행 중이더라도 OS가 이를 빼앗을 수 있는 방식으로, 처리 시간이 긴 프로세스가 CPU 자원을 독점하는 것을 막을 수 있어 효율적인 운영이 가능하다. 다만 문맥 교환이 잦아질 경우 오버헤드가 커질 수 있다.
CPU 스케줄링의 평가 기준
- CPU 이용률(Cpu utilization)
- 시간당 CPU를 사용한 시간의 비율
- 이를 높이기 위해서는 프로세서가 항상 실행 상태로 유지되도록 해야 한다.
- 처리율(Throughput)
- 시간당 처리한 작업의 비율
- 이를 높이려면 단위 시간당 완료되는 작업의 수가 많도록 해야 한다.
- 반환 시간(Turnaround time)
- 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간
- 작업이 준비 큐(ready queue)에서 기다린 시간과 CPU에서 실행된 시간과 I/O 작업 시간의 합(즉, 프로세스의 총 실행 시간)
- 대기 시간(Waiting time)
- 대기열에 들어와 CPU 자원을 할당받기까지 기다린 시간
- 준비 큐에서 기다린 시간의 총합
- 반응 시간(Response time)
- 대기열에서 '최초로' CPU 자원을 할당받을 때까지 걸린 시간
- 대기 시간과 유사하나 대기 시간은 준비 큐에서 기다린 시간의 총합이라면 반응 시간은 CPU 자원을 할당받을 때까지 기다린 '최초의 시간'만을 말하는 것이다.
CPI 이용률과 처리율은 최대로, 반환 시간과 대기 시간, 반응 시간 등은 최소로 하는 것이 좋으며, CPU 스케줄링 알고리즘의 평가에는 반환 시간과 대기 시간을 기준으로 하는 것이 일반적이다.
CPU 스케줄링 알고리즘
First In First Out(FIFO)
- First Come First Served(FCFS)라고도 함
- 비선점형으로서 요청된 순서대로 CPU를 할당하는 방식(동시에 요청이 들어올 경우 임의로 순서 할당)
- 간단하고 이해하기 쉬운 방식
- 반환 시간 면에서는 좋을 수 있으나 평균 대기 시간과 응답 시간이 길어질 수 있음
- 호위 효과(Convoy effect) 발생 가능
Shortest Job First(SJF)
- 비선점형과 선점형이 각각 존재하며, 비선점형의 경우 현재 실행 중인 프로세스는 끝까지 실행함
- 수행 시간(CPU burst time)이 짧은 프로세스를 먼저 처리하는 방식
- 평균 대기 시간을 줄일 수 있으나 다음 프로세스의 CPU burst time을 예측하는 것은 사실상 어려운 일이므로 활용이 쉽지 않음
- 처리 시간이 긴 프로세스가 먼저 들어올 경우 반환 시간이 길어지는 문제가 발생함
Shortest Time to Completion First(STCF)
- 수행 시간이 짧은 프로세스를 먼저 처리하는 것은 SJF와 동일하나, 새로운 요청이 들어오면 프로세스 간 수행 시간의 비교를 실시하여 CPU를 할당하는 방식
- 따라서 선점형에 해당함
- 모든 요청이 동시에 들어오지 않더라도 최적의 반환 시간을 도출할 수 있음
단, SJF나 STCF 등은 현실적으로 불가능한 정책에 가까운데, CPU burst time을 예측하는 것이 어렵기 때문이다.
Round-Robin(RR)
- 선점형 스케줄러로 응답 시간에 강점
- CPU를 활용할 수 있는 시간(Time slice)을 정해 두고 각 프로세스가 돌아가며 해당 시간만큼 CPU를 활용하도록(작업을 수행하도록) 하는 방식
- CPU의 활용 순서는 FIFO 방식을 활용
- Time slice가 너무 커질 경우 FIFO와 같이 동작하며, 따라서 마찬가지로 호위 효과 발생 가능
- Time slice를 너무 작게 할 경우 응답 시간은 빨라지나 문맥 교환 등으로 인한 오버헤드 발생
Incorporating I/O
Incorporating I/O는 크게 두 가지로 구분 가능하다.
일반적으로 I/O 작업이 수행되는 동안 CPU는 차단된다. 이처럼 I/O를 수행할 때 CPU를 차단하는 방식을 Busy waiting 방식이라고 한다.
그런데 이 경우 I/O 작업이 오래 걸린다면 CPU가 오랜 시간 일을 하지 않는 상태가 된다. 이러한 비효율성을 해결하기 위해 I/O 작업이 수행되는 동안 CPU가 다른 작업을 수행하도록 하는 것을 Blocked 방식이라고 한다.
Blocked 방식은 다음과 같이 정리할 수 있다.
- CPU의 사용률을 극대화하기 위하여 I/O 연산을 고려하는 선졈형 스케줄러
- 프로세스가 write()와 같은 system call을 호출하여 block이 되면 그 사이에 ready 상태인 다른 프로세스를 스케줄링하는 방법
- CPU와 IO가 오버랩되는 것을 허용함으로써 CPU를 효율적으로 사용
Blocked 방식의 과정을 조금 더 자세히 살펴보자.
우선 CPU가 메모리에서 값을 읽어오거나 값을 쓸 때는 각각 Load, Store라는 명령을 이용한다. 또, CPU에 있는 레지스터의 값을 IO processor로 이동할 때는 Out, IO processor에서 상태 정보를 읽어올 때는 In 명령을 사용한다. 이를 바탕으로 Blocked 과정을 정리하면 다음과 같다.
- 실행 중인 프로세스 A가 write() 등 I/O 명령을 호출한다.
- CPU는 이 명령을 IO processor로 보내는 out() 명령을 수행하고, 이후 대기 상태가 된다(프로세스 A는 blocked 상태가 된다).
- OS는 스케줄링을 통해 ready 상태인 다른 프로세스(B)와 프로세스 A를 스위칭한다.
- 프로세스 A의 IO 작업이 끝나면 IO processor가 CPU에 인터럽트(Interrupt)를 발생시키고, 이 인터럽트가 처리되면 blocked 되었던 프로세스 A는 다시 ready 상태로 변환된다.
- OS는 프로세스 B를 중단하고 프로세스 A와 스위칭하여 다시 프로세스 A를 실행한다.
Priority scheduling
- 각 프로세스에 우선순위가 할당되어 가장 높은 우선순위를 가진 프로세스에 CPU가 할당되는 방식
- 우선순위가 동일한 프로세스는 FIFO 방식으로 스케줄링됨
- 무한 봉쇄(Indefinite blocking) 또는 기아 상태(Starvation) 발생 가능
- 무한 봉쇄 : 실행 준비는 되어 있으나 CPU를 사용하지 못하는 프로세스가 CPU를 기다리면서 봉쇄된 것으로 간주됨
- 기아 상태 : 우선순위가 높은 프로세스들이 계속해서 들어와 우선순위가 낮은 프로세스들이 CPU를 할당받지 못하게 됨
Multilevel Queue Scheduling(MQS)
- Priority scheduling을 Round-Robin과 결합한 방식
- 준비 큐(Ready queue)를 여러 개의 큐로 다시 나누고, 각 큐마다 각자의 스케줄링 알고리즘을 설정
- 일반적으로 Foreground 프로세스들은 RR 방식을, Background 프로세스는 FIFO 방식을 이용
- 각 큐 간 프로세스의 이동은 불가
- 기아 문제 발생 가능
Multi-Level Feedback Queue(MLFQ) Scheduling
- 프로세스가 시스템 진입 시 영구적으로 하나의 큐에 할당되는 MQS와 달리 프로세스가 큐 사이를 이동하는 것이 가능한 스케줄링
- 특정 시스템에 부합하도록 구성하는 것이 가능하며, 따라서 현대의 CPU 스케줄링 알고리즘 중 가장 일반적인 알고리즘
- 그러나 구현이 가장 복잡한 알고리즘이기도 함
참고 자료
