[운영체제] CPU 스케줄링

STUDY/운영체제

디리릭 2022. 1. 17. 01:00

CPU 스케줄링의 목표는 CPU 효용 극대화하기 위해서이다.

프로세스가 실행 될 때 CPU를 사용하는 시간과 I/O에 대한 응답을 기다리는 시간이 번갈아가면서 진행된다.

이 때, CPU를 사용하는 시간을 CPU burst, I/O 응답을 기다리는 시간을 I/Oburst라고 한다.

통상적인 프로세스는 CPUburst가 짧고 빈도수가 높다. 따라서 하나의 프로세스가 실행 될 때 CPU는 거의 놀고 먹으면서 실행 된다.

그래서 여러 프로세스를 실행할 때, CPU 스케줄링을 하면 CPU 효율을 극대화 할 수 있다.

그러면 CPU스케줄링은 언제 일어나는가?

아래와 같이 프로세스 상태가 변했을 때 이뤄진다.

1번 4번은 자발적인(비선점) 스케줄링(non-preemptive)이고 2번 3번은 강제적인(선점) 스케줄링(preemptive)이라고 한다.

Dispatcher

CPU를 선점한 프로세스에 대한 정보를 스위칭 시켜주는 역할을 한다.

(CPU 스케줄러는 프로세스 선택하는 것! Distpatcher는 정보 스위칭 해주는 것이다)

distpatcher는 4가지 기능이 있다.

다른 프로세스의 context로 스위칭 시키는 것
user mode 스위칭 시키는 것
프로세스의 레지스터를 적재하고(문맥교환), 운영체제 모드(Kernel Mode)에서 사용자 상태(User Mode)로 전환시켜주며 프로세스가 다시 시작할 때 사용자 프로그램이 올바른 위치를 찾을 수 있도록 하는 것. 이때, distpatcher는 latency가 가급적으로 짧아야한다.

스케줄링 기준

CPU Utilization : to keep the CPU as busy as possible
Throughput : the number of processes completed per time unit
Turnaround time : how long does it take to execute a process? from the time of submission to the time of completion.
Waiting time : the amount of time that a process spends waiting in the ready queue. the sum of periods spend waiting in the ready queue.
Response time : the time it takes to start responding

스케줄링 알고리즘

FCFS
First Come First Service의 약자로 선입 선출 알고리즘인 비 선점 스케줄링 기법이다. Ready 큐에 도착한 순서대로 처리하기 때문에 배치형 시스템에 적합하다.
SJF
Shortest Job First의 약자로 최소 작업 우선 스케줄링 기법으로 실행 시간이 가장 짧은 작업부터 할당하는 방법이다.
실행시간이 짧은 프로세서부터 실행되기 때문에 오래걸리는 프로세서는 계속 뒤로 밀리게 되는 문제점이 있다. 이러한 문제점을 해결하기 위해 aging을 할당 요소에 추가한다.(오래 기다렸는가를 고려)
이 기법의 장점은 FCFS보다 대기시간이 짧다점이다.
RR
Round Robin의 약자로 robin이라는 새의 이름을 딴 이름이다. 이 기법은 시간을 분배하여 각 프로세서가 순서대로 실행하도록 한다.
MLQ
Multi Level Queue의 약자로 Ready큐를 여러 종류로 구분 후 이를 스케줄링하는 기법이다. 각 큐마다 우선순위가 있어서 우선순위 높은 큐에 프로세서가 입장하면 CPU를 선점하는 선점형 알고리즘이다.
MLFQ
Multi Level Feedback Queue의 약자로 MLQ보다 더 고도화 된 알고리즘이다. MLQ의 문제점인 Starvation(우선순위가 낮은 task는 계속 Queue에 있음)을 보완해주는 기법이다.
이 기법은 우선순위 대로 Ready Queue를 구성하고 Queue마다 할당 시간을 부여하여 비선점형으로 운용하는 방식이다.