운영체제 6-2강 (CPU 스케줄링 알고리즘)

늘보·2021년 7월 6일

OS

목록 보기

11/25

본 글은 이전에 사용하던 영상 강의 필기 앱인 'Slid'에서 필기 했던 내용을 Velog로 옮긴 내용입니다.
본 글은 이화여대 반효경 교수님 2017학년도 1학기 운영체제 강의를 기반으로 작성되었습니다.
강의 링크 : http://www.kocw.net/home/search/kemView.do?kemId=1226304

이번 강에서는 CPU 스케줄링 알고리즘에 대해 설명한다. 이를 설명하기에 앞서 스케줄링의 성능의 기준을 알아보자.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

FCFS(First-Come First-Served)

FCFS(Non-preemptive 알고리즘이다.)는 우리가 자료 구조 시간에 배운 큐(FIFO)와 같은 개념이다. 먼저 온 프로세스가 먼저 CPU를 차지한다. 그러나 결론부터 말하면 Job Scheduling에 있어서는 매우 비효율적인 알고리즘이다.

다음 두 가지 케이스를 생각해보자. 프로세스 1, 프로세스 2, 프로세스 3이 거의 동시에 왔지만 1, 2, 3번의 순서대로 CPU를 배정받았다고 가정하고 다음 그림 3을 살펴보자. 프로세스 1의 Burst time이 24, 2번이 3, 3번이 3이라면 평균적으로 프로세스들이 기다리는 시간은 (0 + 24 + 27)/3 = 17이다.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

이제 같은 프로세스이지만 간발의 차로 2, 3, 1의 순서로 배정받았다고 가정하고 그림 4를 살펴보자. 평균적으로 프로세스가 기다리는 시간은 (6 + 0 + 3)/3 = 3으로 위의 예시 1보다 눈에 띌 정도로 waiting time이 줄어든 것을 확인할 수 있다. 이건 너무 운빨 게임이 아닌가? 고작 0.000 몇 초로 기다리는 시간의 합이 이렇게나 차이가 날 수 있다니...

이렇든 앞의 긴 프로세스가 먼저 도착해서 CPU를 오래 쓰는 바람에 뒤에 있는 짧은 프로세스가 오래 기다려야 하는 상황을 Convoy effect(호위 효과)라고 한다. CPU 스케줄링에 있어서는 부정적인 효과이다.

-----------------------------------------------------------------------------------------------------------------------------------------------------------

SJF(Shortest-Job-First) & SRTF(Shortest-Remaining-Time-First)

FCFS를 살짝 보완한 것이 SJF(Shortest-Job-First)이다. SJF는 CPU를 가장 짧게 쓰려는 프로세스에게 CPU를 먼저 주는 것이다. Greedy Algorithm에서 보았을지 모르나 Waiting time 측면에서 본다면 가장 짧은 waiting time을 갖는 Optimal 한 방법이다. 즉, 다른 어떤 스케줄링 방법을 쓰더라도 SJF보다 waiting time 측면에서 더 나은 방식으로 스케줄링할 수 없다. 즉, minimum average waiting time을 보장한다. 이 SJF도 preemptive한 버전과 nonpreemptive 버전이 있다. Nonpreemptive는 프로세스가 실행되는 도중에 ready queue에 현재 수행 중인 프로세스의 남은 CPU burst time보다 더 짧은 CPU burst time을 갖는 프로세스가 들어오더라도, 현재 프로세스의 CPU를 빼앗지 않고 남은 시간을 수행하는 것을 말한다. 반면 preemptive는 그런 상황에서 강제로 CPU를 빼앗아 버리는데 이것을 Shortest-Remaining-Time-FIrst(SRTF)라고 한다.

그렇다면 둘 중 어느 것이 더 Optimal한 방법일까? 직관적으로도 알 수 있지만 당연히 빼앗는 방법이다.

다음 예시 두 개로 nonpreemptive SJF와 preemptive SJF(SRTF)의 차이를 살펴보자. 그림과 같이 프로세스 네 개가 각각 도착시간이 다르고 Burst time도 다르다고 하자.

Non-preemptive SJF 스케줄링에 따르면 Average waiting time 은 (0 + 6 + 3 + 7)/4 = 4 가 된다.

반면 Preemptive SJF(SRTF) 스케줄링일 때를 고려하자.

처음 0초에 P1이 CPU를 7초 쓰고자 하는데 Ready queue에 아무도 없기 때문에 CPU를 점유한다.
그러던 중 2초가 지났을 때 Burst time이 4인 P2가 들어왔다. 그러나 P1은 2초가 지났더라도 Burst time이 5가 남았기 때문에 후순위로 밀리게 된다.
이런 식으로 스케줄링이 되면 다음 그림 5와 같은 양상이 되며 Average waiting time은 (9+ 1 + 0 + 2)/4 = 3으로 Nonpreemptive SJF 보다 줄어든 waiting time을 얻을 수 있다.

그러나 이 방법에는 아주 치명적인 두 가지 약점이 있다.

첫 번째는 Starvation problem, 즉, 굶어죽는 문제가 발생한다. 그러니까 CPU burst time long 프로세스는 영원히 후순위로 밀리며 CPU를 얻지 못하게 되는 문제가 발생할 수 있다는 것이다.
두 번째는 프로세스의 정확한 CPU burst time을 측정할 수 없기 때문에 burst time을 추정해야 하는데 (그림 9를 참고하자) '추정'하는 과정에서 발생하는 문제가 발생한다. 현재 n + 1 번째 CPU burst time을 예측한다고 한다면, n번째 CPU burst time과 n번째를 위해 예측했던 cpu burst time의 가중 평균으로 예측한다. 이것의 점화식을 연결하여 수식으로 전개하면 그림 6, 그림 7과 같을 것이다. 현재와 가까운 CPU burst의 CPu burst time을 더 많이 반영하고, 현재에서 멀어질수록 적게 반영한다는 것인데 이를 Exponential averaging이라 한다. 어찌 되었든 이러한 추정을 통해 스케줄링을 하기 때문에 정확한 CPU burst time을 알 수 없다. 따라서 짧은 CPU burst time을 예상했지만 CPU를 훨씬 길게 점유할 수도 있게 되는 문제가 발생할 수 있다. (과거를 통해 예측)

Priority scheduling (우선 순위 스케줄링)

사실 이전의 SJF나 SRTF도 Priority scheduling이다. Priority가 predicted next CPU burst time인 셈이다. Priority scheduling도 Nonpreemptive와 preemptive 버전으로 구현 가능하며 SJF와 마찬가지로 starvation problem이 발생할 수 있다.

이를 해결할 수 있는 방법이 존재하는데 그것은 바로 'Aging'기법이며 쉽게 말하면 경로사상이다. 시간이 지날수록 우선순위를 높여주는 것이며 그러다 보면 언젠가 문제가 될 수 있는 프로세스의 우선순위가 가장 높아지는 순간이 올 것이라는 발상에서 도입한 것이다.

Round Robin (RR Scheduling)

RR Scheduling은 현대 preemptive 운영체제의 근간이 되는 스케줄링이다. 그 동안 우리가 프로세스를 운영체제가 어떻게 관리하는지 설명을 들었던 방식이다. Timer가 존재하여 timer의 시간을 세팅하고 프로세스에게 넘기며 timer interrupt로 프로세스의 CPU 독점을 막는 방법이다. I/O bound job의 경우, 짧은 시간 동안 빠르게 I/O를 요청하며 빠른 응답 시간을 기대할 수 있고, CPU bound job의 경우, 무작정 오래 CPU를 점유하는 것이 아니라 적절히 CPU를 내주고 받으며 수행된다. 이 방법은 n개의 프로세스가 ready queue에 있고 할당 시간이 q time unit인 경우 각 프로세스는 최대 q time unit으로 CPU 시간의 1/n을 얻게 된다. 즉 모든 프로세스들이 (n-1)*q time 이상 기다리지 않게 된다. 만약 q time(할당 시간)이 무한정 길어지게 되면 FCFS와 똑같은 방법이 되며 q time이 작아지게 되면 context switch 오버헤드가 굉장히 커지게 되어 비효율적이 된다.

다음 그림 10의 예시를 통해 살펴보자. 할당 시간을 20이라고 설정한다면 P1, P2, P3, P4 모두 최대 20만큼의 시간 동안 CPU를 사용할 수 있으며 총 4개의 프로세스가 있기 때문에 아무리 밀려도 60 time 내에서는 CPU를 맛볼 수 있게 된다(Response time).

그러면 Round Robin의 장점은 무엇인가? SJF는 대기 시간의 총합이 가장 적다고 했다. RR은 대기 시간의 총합은 SJF보다 길지 모르나 Response time(최초로 CPU를 만나는 시간)은 더 짧다는 장점이 있다. Time sharing OS에서 사용자와 interact하는 job이 많을 때 유리하다. Interactive job은 짧은 응답 시간이 대단히 중요하기 때문이다. RR이 좋은 이유는 Long job과 Short job이 섞여 있기 때문이다. 모든 job이 homogeneous 하다면 오히려 Context switch의 오버헤드가 더 커질 것이다. 가령 10분씩 은행 업무를 처리해야 하는 사람이 100명이라 하자. FCFS를 쓰게 된다면 그냥 10분마다 한 사람씩 집에 갈 수 있지만, RR로 10초마다 한 사람씩 바꿔가며 처리해주게 되면 맨 마지막에 모든 사람이 같이 집에 가게 되는 비효율적인 상황 (이해 잘 된다!)이 된다. Response time은 빠를 수 있으나 꼭 좋은 양상은 아니라는 것이 핵심이다. 요컨대 RR은 일반적으로 SJF보다 average turnaround time이 길지만 response time이 더 짧으며, Homogeneous(비슷할 때 또는 동일할 때) job들이 있는 상태보다는 Heterogeneous(다양할 때) job들이 queue를 이루고 있을 때 더 효과적이 된다.