CPU 스케줄링
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야하는 일을 쓰레드 단위로 CPU에 할당하고, CPU 소유권을 결정한다. CPU 스케줄러는 선점형 방식과 비선점형 방식으로 나눈다.
이 알고리즘은 CPU는 최대한 많이 사용하면서, 대기 중인 프로세스는 적게 만드는 것을 목표로 한다.
선점형 방식(preemptive)
선점형 방식은 운영체제가 쓰고있는 방식으로, 실행중인 프로세스를 강제로 중단시키고 CPU 소유권을 할당하는 방식을 의미한다. 라운드로빈, SRF, 다단계 큐 등이 있다.
RoundRobin(RR)
우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고, 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 들어가는 알고리즘이다. 따라서 x만큼 할당 시간이 부여되고 N개의 프로세스가 운영된다면, (N-1) * x의 대기 시간을 갖게 된다.
할당 시간이 너무 크면 FCFS가 되고, 짧으면 컨텍스트 스위칭이 잦아져 오버헤드가 발생한다. 일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.
트래픽을 분산하기 위해 스케일 아웃을 적용할 때 사용하는 로드밸런서가 RR 알고리즘을 사용한다.
- 다음과 같은 프로세스들이 있고, 할당 시간이 4일 때 대기 시간을 구해보자.
반환 시간 (프로세스가 시작해서 끝날 때까지 걸리는 시간)
- A : 20 - 0 = 20
- B : 8 - 1 = 7
- C : 26 - 2 = 24
- D : 25 - 3 = 22
- 평균 반환 시간 = (20 + 7 + 24 + 22) / 4
대기 시간 (프로세스가 준비 큐에서 대기한 시간)
- A : 16 -4 = 12
- B : 4 - 1 = 3
- C : (20 - 12) + (8 - 2) + (25 - 24) = 15
- D : (24 - 16) + (12 - 3) = 17
SRF(Shortest Remaining Time First)
SJF(Shortest Job First)는 실행 시간이 더 짧은 작업이 와도 순서대로 처리하지만, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 프로세스를 수행하는 알고리즘이다.
다단계 큐
다단계 큐는 우선 순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 RR이나 FCFS 등 다른 스케줄링 알고리즘을 적용하는 기법을 의미한다. 큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적은 장점이 있지만, 유연성이 떨어지는 단점이 있다.
비선점형 방식(non-preemptive)
비선점 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는 방식이다. 강제성이 없기 때문에 프로세스간 교류가 적어지므로 컨텍스트 스위칭으로 인한 부하가 적다.
SJF(Shortest Job First)
SJF는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않는 현상이 일어나며, 평균 대기 시간이 가장 짧다.
FCFS(First Come, First Served)
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다. 길게 수행하는 프로세스가 먼저 도착한다면 준비 큐에서 오래 기다리는 현상이 발생하는 단점이 있다.
우선순위
기존의 SJF 스케줄링의 경우 긴 프로세스가 실행되지 않는 현상이 있을 수 있었다. 이 문제점을 보완하기 위해 오래된 작업일 수록 우선순위를 높이는 에이징 기법을 사용하여 단점을 보완한 알고리즘이다.
