CPU 스케줄링 개요
프로세스(Process)가 구동하려면 다양한 시스템 자원이 필요하다. 대표적으로 CPU(중앙처리장치)와 입출력장치가 있는데, 최고의 성능을 내기 위해 자원을 어떤 프로세스에 얼마나 할당하는지 정책을 만드는 것을 CPU스케줄링이라고 한다.
CPU스케줄링에 대해 알아보기 전에, 왜 필요한지 짚고 넘어갈 필요가 있다. (스케줄링 기법에 어떤 것들이 있는지 외우는 것보다 중요하다.)
라면을 끓일 때, 물이 끓을 때까지 멍하니 기다리지는 않을 것이다. 라면 봉투를 미리 뜯어 놓기, 스프 미리넣기, 각종 재료를 미리 준비하기 등을 물이 끓는 것을 기다리면서 할 것이다. 여기서 CPU스케줄링을 착안하면 되겠다. 프로세스는 작업(Job)을 완료할 때까지 다양한 상태가 되는데, 우리가 주목해야할 것은 'Waiting'이다.
프로세스가 CPU를 점유하여 작업을 수행하는 도중 I/O 또는 Interrupt가 발생하면 일시적으로 프로세스는 CPU를 사용하지 않게 된다. 하지만 계속 점유하고 있다. 이러한 상황을 줄여, CPU를 최대한 활용하면 시스템의 성능 개선을 꾀할 수 있다. 결국, "어떻게 프로세스들이 CPU를 효율적으로 사용하게 할 것인가?" 라는 고민에서 CPU 스케줄링이 출발한다고 할 수 있다.
CPU 스케줄링은 크게 두 가지로 분류되는데, 선점(Preemptive)스케줄링과 비선점(Non-Preemptive)스케줄링이다.
CPU 스케줄링의 목적
CPU 스케줄러는 프로세스가 생성된 후 종료될 때까지 모든 상태 변화를 조정하는 일을 한다. 이 스케줄러가 하는 CPU 스케줄링은 어떤 프로세스에 CPU를 배정할지 결정하고, 이 작업은 컴퓨터 시스템의 효율에 직결되는 중요한 일이다.
CPU 스케줄링의 본 목적은 모든 프로세스가 공평하게 작업할 수 있도록 하는 것이다. 하지만 안정성과 효율성을 높이기 위해 공평성의 일부분을 희생해야 한다. 다음은 스케줄링이 추구하는 목적들이다.
-
공평성 : 모든 프로세스가 자원을 공평하게 배정받아야 하며, 특정 프로세스가 배제되어서는 안 된다.
-
효율성 : 시스템 자원을 놀리는 시간 없이 스케줄링해야 한다.
-
안정성 : 우선순위를 사용하여 중요한 프로세스가 먼저 처리되도록 해야 한다.
-
반응 시간 보장 : 응답이 없는 경우 사용자는 시스템이 멈춘 것으로 가정하기 때문에 시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.
-
무한 연기 방지 : 특정 프로세스의 작업이 무한히 연기되어서는 안 된다.
CPU 스케줄링의 단계
1. 고수준 스케줄링(long-term scheduling, job scheduling, admissin scheduling)
가장 큰 틀에서 이루어지는 CPU 스케줄링으로 시스템 내의 전체 작업 수를 조절한다. 시스템 과부하를 막기 위해 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정하므로 시스템 내에서 동작 시에 실행 가능한 프로세스의 총개수가 정해진다.
2. 중간 수준 스케줄링
중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조절한다. 이로 인해 저수준 스케줄링이 원만하게 이루어지도록 완충하는 역할을 한다.
3. 저수준 스케줄링(short-term scheduling)
가장 작은 단위의 스케줄링으로 어떤 프로세스에 CPU를 할당할지, 어떤 프로세스를 대기 상태로 보낼지 등을 결정하는 역할이다. 중간 수준의 스케줄링은 프로세스를 보류 상태로 보내고, 저수준 스케줄링은 대기 상태로 보낸다. 스케줄링에 대해 공부하는 대부분의 내용이 이 저수준 스케줄링에 해당한다.
선점 스케줄링
-
CPU가 어떤 프로세스에 의해 점유 중일 때, 우선 순위가 높은 프로세스가 CPU를 차지할 수 있음
-
우선 순위가 높은 프로세스를 빠르게 처리해야할 경우 유용.
-
선점이 일어날 경우, 오버헤드가 발생하며 처리시간을 예측하기 힘들다.
-
잦은 Context Switching이 일어날 경우 오버헤드가 많이 발생한다.
선점 스케줄링의 경우 위와 같은 특징이 있으며, 비선점 스케줄링은 선점 스케줄링과 반대이다. 선점 스케줄링의 경우에는 I/O요청, I/O응답, Interrupt발생, 작업완료 등의 상황에서 스케줄링이 일어날 수 있다. 하지만 비선점 스케줄링의 경우 프로세스가 스스로 CPU를 놓아주는 시점(작업이 완료되는 시점)에만 스케줄링이 일어난다.
SRTF(Shortest Remaining Time First) 스케줄링
SJF의 선점형 방식이다. 먼저 온 프로세스가 CPU를 할당받고 있더라도 남은 처리 시간이 뒤에 온 프로세스의 처리 시간보다 길면 CPU를 빼앗긴다.
어떤 알고리즘보다 평균 대기 시간이 가장 짧은 알고리즘이다.
하지만 이 방식은 기본적으로 선점형 방식이기 때문에 잦은 문맥교환이 일어나고 그에 따른 오버헤드가 커진다. 그리고 starvation 현상이 더 심각하게 발생할 수 있다.
또한 CPU의 예상 시간을 예측하기가 너무 힘들기 때문에 실제로 사용되기가 매우 어렵다. (exponential averaging을 통해 예측을 할 수는 있다)
라운드로빈(Round-Robin)스케줄링
각 프로세스는 같은 크기의 CPU 시간을 할당 받고 선입선출에 의해 행된다. 할당시간이 너무 크면 선입선출과 다를 바가 없어지고, 너무 작으면 오버헤드가 너무 커진다.
다단계 큐(Multi-level Queue) 스케줄링
다단계 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 당연히 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행될 수 있다. 그리고 한 번 우선순위가 매겨저 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다.
각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있는데, 보통 전면 프로세스들이 속해있는 큐는 우선순위고 높고 라운드 로빈 스케줄링을 사용해 타임 슬라이스를 작게한다.
후면 프로세스에는 사용자와의 상호작용이 없으므로 가장 간단한 FCFS 방식으로 처리한다. 보통 총 CPU 시간이 전면 프로세스의 처리에 80%, 후면 프로세스 처리에 20%가 할당된다.
이 다단계 큐 알고리즘 역시 문제는 starvation 현상과 공평성 문제다.
다단계 피드백 큐 스케줄링
다단계 큐의 공평성 문제를 완화하기 위해 신분 하락이 가능한 알고리즘이다. 이 알고리즘에서는 우선순위가 변동되기 때문에 큐 사이의 이동이 가능하다.
한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아진다. 따라서 더 낮은 큐로 이동하게 된다. (우선순위가 높아져 상위 큐로 이동할 수도 있다)
그리고 더 보완하기 위해 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 준다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용하게 해주기 위함이다.
비선점 스케줄링
프로세스가 CPU를 점유하고 있다면 이를 빼앗을 수 없는 방식
- 필요한 Context Switching 만 일어나기 때문에 오버헤드가 상대적으로 적지만 프로세스의 배치에 따라 효율성 차이가 많이 난다.
HRN(Highest response ratio next) 스케줄링
긴 작업과 짧은 작업간의 지나친 불평등을 어느 정도 보완한 기법.
수행시간의 길이와 대기 시간을 모두 고려해 우선순위를 정한다.
SJF 스케줄링에 Aging 기법을 합친 비선점형 알고리즘이다.
Aging이란 나이를 먹는다는 의미 그대로 starvation을 해결하기 위해 대기 시간이 길어지면 우선순위를 높여주는 방법이다.
SJF와 마찬가지로 실행 시간이 적은 프로세스의 우선 순위가 높지만 대기 시간이 너무 길어지면 실행 시간이 길더라도 CPU를 할당받을 수 있다. 하지만 여전히 공평성이 말끔히 해결되지는 않는다.
SJF(Shortest Job First) 스케줄링
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있다. 때문에 콘보이 효과를 완화할 수 있다.
단, 비선점형 방식이기 때문에 CPU를 사용중인 프로세스보다 처리 시간이 짧더라도 빼앗지는 못한다.
위의 그림은 만약 모든 프로세스가 0초에 동시 도착했다는 가정이다. 그럴 경우 P4가 버스트 타임이 가장 짧기 때문에 먼저 실행되고, P1이 가장 나중에 실행된다. 평균 대기 시간을 위의 FCFS와 비교해보면 월등히 짧은 것을 알 수 있다.
하지만 만약 P1이 가장 먼저 도착했다면 어쩔 수 없이 P1이 먼저 CPU를 점유하게 된다.
FCFS보다 효울성이 매우 높지만 그에 따른 단점도 존재한다.
일단 가장 중요한 공평성에 어긋난다. 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어온다면 대기 큐에서 영영 CPU를 할당받지 못할 수 있다. 이를 starvation 현상이라고 한다.
그리고 중간에 입출력 버스트가 빈번하게 요구되는 프로세스의 경우 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵다.
우선순위(priority) 스케줄링
프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 한다. 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘긴다. 빼앗긴 프로세스는 준비 큐의 맨 뒤로 간다. 따라서 선점형 방식이다.
따로 CPU 처리 시간을 계산하지 않아도 돼서 선점형 방식의 가장 단순하고 대표적인 방법이다. 우선 순위도 없기 때문에 매우 공평하다.
라운드 로빈 알고리즘의 경우, 만약 할당 시간이 q고 대기 중인 프로세스가 n개라면 어떤 프로세스도 (n-1)q 이상을 기다리지 않아도 된다. 이는 곧 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 큰 장점을 가지게 된다. 자연히 콘베이 효과 역시 줄어든다.
위의 경우 time quantum = 5인 경우다. 타임 퀀텀(타임 슬라이스)동안 처리를 다 하지 못한 P1은 CPU를 빼앗기고 대기 큐의 맨 뒤로 간 다음 P2에게 넘겨준다. P2는 3ms만에 처리를 완료하고 바로 P3에게 CPU를 넘겨준다.
라운드 로빈 방식에서 가장 중요한 부분은 타임 슬라이스의 크기 결정이다.
타임 슬라이스가 큰 경우 처리 시간이 긴 프로세스에 의해 CPU의 효율성이 떨어질 수 있다. 비디오 플레이어와 워드 프로세서를 동시에 실행했을 때 타임 슬라이스가 크다면 비디오가 약간 씩 끊겨서 재생될 것이다. 그리고 만약 타임 슬라이스가 무한대로 설정되면 FCFS 스케줄링과 다를 바 없어진다.
타임 슬라이스가 작은 경우 여러 프로그램이 동시에 실행되는 효과를 볼 수 있다. 하지만 너무 작으면 잦은 문맥 교환이 일어나 오버헤드가 상당히 커진다.
때문에 적당한 타임 슬라이스를 설정하는 것이 중요하다. 보통 10-100 ms로 설정한다.
기한부(Deadline) 스케줄링
작업을 명시된 시간이나 기한 내에 완료하도록 계획.
FCFS(First Come First Served) 스케줄링
말 그대로 선입선출 방식으로, 준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식이다. 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법이다.
하지만 CPU 처리 시간이 긴 프로세스가 앞에 올 경우 뒤의 프로세스가 한없이 기다려야 하기 때문에 비효율적이게 된다. 이를 콘보이 효과라고 한다.
그림에서 보이듯이 CPU 버스트 타임이 2ms인 P4는 잠깐만 CPU를 얻으면 빠르게 처리하고 나갈 수 있지만 4번 째로 도착했기 때문에 30ms나 대기해야 한다.
스케줄링 성능 척도
스케줄링 알고리즘의 효율성을 파악하는 판단 기준이 있다. 주의해야 할 점은 작업을 마친다는 것이 하나의 프로세스가 종료된다는 것이 아니라 CPU의 입장에서 프로세스가 들어와 작업을 처리하고 나갔을 때를 말하는 것이다.
<CPU의 입장>
1. CPU utilization(CPU 사용률)
시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법으로 최대한 CPU를 바쁘게 만드는 것이다. 가장 이상적인 수치는 물론 100%다.
2. Throughput(처리량)
단위 시간당 작업을 마친 프로세스의 수다. 즉, CPU 버스트를 처리한 수다.
<프로세스의 입장>
1. Trun-around time(반환 시간)
프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는 데까지 걸리는 시간이다. 프로세스의 대기 시간 + 실행시간이다. 여기서 대기 시간은 없을 수도 있고, 1 번일 수도, 여러 번일수도 있다.
2.Waiting time(대기 시간)
프로세스가 CPU를 할당받아 실행되기 전 대기 상태일 때의 시간이다. 보통 준비 큐에서 대기를 하는 시간이다.
3.Response time(응답 시간)
프로세스가 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간이다. 대기 시간과의 차이점은 대기 시간은 반환 시간과 마찬가지로 여러 번 있을 수 있다. 그 총합이 대기 시간이고, 응답 시간은 최초의 한 번이다. 이 응답 시간은 프로세스 입장에서 CPU를 한 번도 못 얻은 것과 한 번이라도 얻는 것은 사용자 응답에 있어서 중요한 차이가 있기 때문에 중요하다.
쉽게 설명해보면 매우 배고픈 사람에게 메인 음식이 나오기 전 간단한 단무지나 반찬을 주는 것이 손님의 입장에서는 매우 반가운 것과 같은 느낌이다.
출처
