[운영체제] CPU 스케줄링 알고리즘

CS/운영체제

[운영체제] CPU 스케줄링 알고리즘

1eehyunji 2023. 9. 1. 20:52

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당한다.

프로그램이 실행될 때 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정한다.

이 알고리즘은 CPU 이용률을 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다.

CPU 스케줄링 알고리즘 종류는 다음과 같다.

비선점형
- FCFS(First come, First Served)
- SJF(Shortest Job First)
- 우선순위
선점형
- 라운드 로빈(RR, Round-Robin)
- SRF(Shortest Remaining Time First)
- 다단계 큐

비선점형 방식(non-preemptive)

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이며, 강제로 프로세스를 중지하지 않는다.

따라서 컨텍스트 스위칭으로 인한 부하가 적다.

FCFS

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘이다.

먼저 온 길게 수행되는 프로세스 때문에 '준비 큐에서 오래기다리는 현상(convoy effect)'이 발생하는 단점이 있다.

SJF

SJF는 실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘이다.

긴 실행 시간을 가진 프로세스가 실행되지 않는 기아 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧다.

하지만 실제로는 실행 시간을 알 수 없기 때문에 과거에 실행됐던 시간을 토대로 추측해서 사용한다.

우선순위

기존 SJF 스케줄링의 경우 긴 시간을 가진 프로세스가 실행되지 않는 현상이 있었다.

이는 오래된 작업일수록 '우선 순위를 높이는 방법(aging)'을 통해 단점을 보완한 알고리즘이다.

선점형 방식(preemptive)

선점형 방식은 현대 운영체제가 쓰이는 방식으로, 지금 사용하고 있는 프로세스을 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식을 말한다.

라운드 로빈

라운드 로빈은 현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링의 일종으로 각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘이다.

예를 들어, 10만큼의 할당 시간이 부여되었고, 3개의 프로세스가 운영된다고 하면 2*10만큼의 시간이 지나면 자신의 차례가 돌아오게 된다. 즉, 할당 시간이 q이고, 프로세스 개수가 N개 일 때, (N-1)*q 시간만큼 지나면 다시 자신의 차례로 돌아오는 것이다.

위 예시의 경우, p1이 들어오고 10ms동안 진행된다. 그리고 10ms가 끝나게되면 p1은 인터럽트에 걸리게 되어 ready qeueu 맨 뒤로 가고 p2에게 CPU 자원이 할당된다. p2는 10ms 동안 실행되어 20ms에 CPU자원을 반환하고 ready queue에 들어간다. p3가 CPU 자원을 이어받지만 P3는 작업 시간이 9ms이기 때문에 타임 슬라이스보다 시간이 적다. 때문에 p3는 10ms인 타임슬라이스 동안 실행이 완료되고 종료된다. p1은 20ms, p2는 8ms가 남은 시점에서 p1의 차례가 되어 10ms동안 실행된다. 이후 p2가 실행되고 10ms보다 적게 실행되기 때문에 8ms만 실행된다. 때문에 39~47ms 까지만 시간을 사용하고 p1에게 차례를 넘긴다. p1은 10ms만큼 남았으므로 타임 슬라이스 10ms가 끝나면 종료된다. 이후에 ready queue에는 아무것도 없게 된다.

할당 시간이 너무 크면 모든 프로세스가 할당 시간 안에 모두 수행할 수 있게 되면서 가장 먼저 들어온 작업을 가장 먼저 실행하는 FCFS 알고리즘이 되고, 너무 작으면 컨텍스트 스위칭이 너무 잦아져서 오버헤드가 발생한다.

일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있다.

참고로, 이 알고리즘은 로드밸런서에서 트래픽 분산 알고리즘으로 쓰인다.

SRF(Shortest Remaining Time First)

SJF는 중간에 실행 시간이 더 짧은 작업이 들어오더라도 기존에 수행하던 작업을 완료하고 그 다음 짧은 작업을 이어가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘이다.

p1은 아무 프로세스가 없기 때문에 바로 실행된다.
시간이 흐르고 실행 시간이 1일때 p2가 들어오는데, p2의 실행 시간(28)보다 p1의 실행 시간(10-1=9)가 더 짧기 때문에 계속 진행한다.
또 시간이 흐르고 실행 시간 2일 때 p3가 들어오는데 p1의 실행 시간(10-2=8)보다 p3의 실행 시간(6)이 더 짧기 때문에 p1의 실행을 잠시 중단하고 p3를 실행시킨다.
시간이 흐르고 실행 시간 3일때 p4가 들어오는데 p3의 실행 시간(6-1=5)보다 p4의 실행 시간(4)가 더 짧기 때문에 p3를 잠시 중단시키고 p4를 실행 시킨다.
시간이 흐르고 실행 시간이 4일 때 p5가 들어오는데, p4의 실행 시간(4-1=3) 보다 p5의 실행 시간(14)이 길기 때문에 p4를 그대로 유지시킨다.
시간이 흐르고 실행 시간이 7일 때 p4의 실행을 끝내고 그 다음으로 짧은 p3를 실행시킨다.
이와 같은 과정을 반복한다.

다단계 큐

다단계 큐는 우선 순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것을 말한다.

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있다.