CPU 스케줄링
CPU 스케줄링의 목적
일반적으로 사용자 프로그램이 수행되는 과정은 CPU 작업과 I/O 작업의 반복으로 구성된다. CPU 작업은 레지스터 간의 연산 및 메모리 접근 등으로 이루어지기 때문에 빠르게 수행될 수 있다. 반면 I/O 작업의 경우, CPU의 제어권이 운영체제 커널로 넘어갈 뿐 아니라 상대적으로 매우 느린 입출력 장치의 접근이 필요하게 된다. 전자를 CPU 버스트라고 하고, 후자를 I/O 버스트라고 한다.
- CPU 버스트(burst) : 사용자 프로그램이 직접 CPU를 가지고 빠른 명령을 수행하는 일련의 단계
- I/O 버스트(burst) : 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계
각 프로그램마다 CPU 버스트와 I/O 버스트가 차지하는 비율이 균일하지는 않다. CPU 버스트가 길게 나타나는 프로세스를 CPU 바운드 프로세스(CPU bound process)라 하고, I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스를 I/O 바운드 프로세스(I/O bound process)라 한다.
- CPU 바운드 프로세스 : 소수의 긴 CPU 버스트로 구성 → 계산 위주의 프로그램
- I/O 바운드 프로세스 : 다수의 짧은 CPU 버스트로 구성 → 대화형(interactive) 프로그램
우리가 사용하는 시분할 시스템에서는 이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일한 시스템 내부에서 함께 실행되기 때문에 효율적인 CPU 스케줄링 기법이 필요한 것이다.
일반적으로 대부분의 프로세스들은 짧은 CPU 버스트를 가지는 I/O 바운드 프로세스다. 이는 다시 말해서 CPU를 한 번에 오래 사용하기보다는 잠깐 사용하고 I/O 작업을 수행하는 프로세스들이 많다는 것이다. 이런 프로세스의 경우 대화형 작업이 많기 때문에, CPU 스케줄링 시 우선순위를 높여 사용자에 대한 빠른 응답이 중요하다.
또한, 위에서 설명했듯이 상대적으로 CPU 작업 시간보다는 I/O 작업 시간이 훨씬 길다. 때문에 CPU 이용률을 높이는 것 만큼 중요한게 I/O 장치의 이용률을 높여주는 것이다. I/O 바운드 프로세스에게 먼저 CPU를 할당해 주면, CPU를 잠깐 사용한 후 곧바로 I/O 작업을 수행할 수 있으므로 I/O 장치의 이용률을 높여줄 수 있다.
CPU 스케줄링 성능 평가
스케줄링 기법의 성능을 평가하기 위해 여러 지표들이 사용되는데, 이 지표들은 크게 시스템 관점의 지표와 시용자 관점의 지표로 나누어볼 수 있다.
- 시스템 관점
- CPU 이용률(CPU Utilization)
- 처리량(Throughput)
- 사용자 관점
- 대기 시간(Waiting Time)
- 소요 시간(Turnaround Time)
- 응답 시간(Response Time)
CPU 이용률(CPU Utilization)
전체 시간 중에서 CPU가 일을 한 시간의 비율을 나타낸다. 사실상 시스템 전체의 성능과 밀접하게 관련되므로, CPU가 일을 하지 않고 휴면 상태에 머무르는 시간을 최대한 줄여 CPU 이용률을 높이는게 스케줄링의 중요한 목표가 된다.
처리량(Throughput)
주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 끝마쳤는지를 나태난다. 여기서 프로세스를 끝마친다는 것은 프로세스가 완전히 종료 상태로 되는 것이 아닌, 하나의 CPU 버스트를 완료했다는 것이다. 즉, CPU 버스트를 완료한 프로세스의 개수를 나타낸다. 이 처리량을 높이기 위해서는 CPU 버스트가 짧은 프로세스에게 우선적으로 CPU를 할당하는 것이 유리하다.
대기 시간(Waiting Time)
CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합이다. 시분할 시스템에서는 일반적으로 타이머를 사용해서 하나의 프로세스가 CPU를 연속적으로 사용할 수 있는 시간을 제한하기 때문에, 한 번의 CPU 버스트 중에도 여러 번 준비 큐에서 기다리는 상황이 발생할 수 있다.
소요 시간(Turnaround Time)
프로세스가 CPU를 요청한 시점부터 자신이 원하는 만큼 CPU를 다 쓰고 CPU 버스트가 끝날 때까지 걸린 시간이다. 즉, 준비 큐에서 기다린 시간(대기 시간) + 실제로 CPU를 사용한 시간이다. 이는 한 번의 CPU 버스트 시간이지, 해당 프로세스가 시작되고 종료될 때까지의 시간이 아니다. 따라서 하나의 프로세스가 여러 개의 CPU 버스트를 가지고 있다면, 소요시간도 여러 개가 될 수 있다.
응답 시간(Response Time)
프로세스가 준비 큐에 들어온 후 처음으로 CPU를 획득하기까지 기다린 시간이다. 응답 시간은 대화형 시스템에 적합한 성능 척도로, 사용자 입장에서 가장 중요한 성능 척도라 할 수 있다.
위 성능 지표들을 가지고 실 생활 예시를 들어보자. 중국집이 있고, 그 중국집에는 주방장과 손님이 있다. 여기서 중국집은 컴퓨터를 나타내고, 주방장은 CPU, 손님은 프로세스다.
- 중국집 == 컴퓨터
- 주방장 == CPU
- 손님 == 프로세스
먼저 중국집 입장에서 CPU 이용률을 높이려면 주방장이 최대한 쉬지 않고 일해야 한다. 주방장을 여러 명 고용하면 CPU 이용률은 당연히 높아진다. 만약 손님은 기다리는데 주방장이 조금이라도 쉬면, 중국집의 전체 회전율에 영향이 가게 된다. 이 회전율은 처리량과 일맥상통한다. 밖에서 대기 인원이 있는 맛집이라고 가정했을 때, 마감 직전까지 최대한 많은 사람들에게 음식을 판매해야 매출이 올라간다.
이번에는 손님 입장에서 여러 개의 메뉴를 시켰다고 가정해 보자. 손님은 전체 음식을 기다리는 대기 시간이 적을수록 좋다. 음식을 먹는 시간은 어느정도 정해져 있고, 손님마다 다르기 때문에, 손님이 음식을 기다리는 손님의 대기 시간을 줄여줘야 손님의 소요시간도 줄어들게 된다. 또한, 응답 시간이 중요한 이유가, 손님 입장에서 메인요리가 나오기까지 그냥 기다리는 것보다 먼저 단무지같은 반찬이 빠르게 나오면 아무래도 더 좋을 것이다.
CPU 스케줄링 알고리즘
CPU 스케줄링의 유형
CPU 스케줄링 방식에는 크게 2가지가 있다.
비선점형 스케줄링(Non-Preemptive Scheduling)
- 프로세스가 CPU를 할당받으면, 해당 프로세스가 종료되거나 I/O 작업을 요청할 때까지 CPU를 반환하지 않는다.
- 대표적인 알고리즘: FCFS(First-Come, First-Served), SJF(Shortest Job First)
선점형 스케줄링(Preemptive Scheduling)
- 현재 실행 중인 프로세스가 있더라도 더 높은 우선순위의 프로세스가 도착하거나 특정 조건을 만족하면, CPU를 강제로 반환하게 한다.
- 대표적인 알고리즘: Round Robin (RR), Priority Scheduling, SRTF (Shortest Remaining Time First)
선입선출(First-Come First-Served: FCFS)
준비 큐에 도착한 시간 순서대로 CPU를 할당하는 비선점형 방식이다. 모든 프로세스의 우선순위가 동일하고, 프로세스의 CPU 처리 시간을 따로 고려하지 않기 때문에 매우 단순하고 공평한 방법이다.
하지만 CPU 처리 시간이 긴 프로세스가 앞에 올 경우 뒤의 프로세스가 한없이 기다려야 하므로 평균 대기 시간이 길어지게 된다. 또한 CPU 버스트가 짧은 I/O 바운드 프로세스들의 길어진 대기 시간으로 I/O 장치들의 이용률까지도 동반 하락하게 된다. 이런 현상을 콘보이 효과(Convoy effect)라고 한다.
위 그림을 보면 프로세스 P1, P2, P3, P4가 준비 큐에 차례로 도착했고, 도착한 순서대로 CPU에서 처리된다. 위 순서로 CPU를 할당하게 되면, P1 때문에 나머지 프로세스들의 대기시간이 늘어나게 된다. 게다가 CPU 버스트 타임이 2ms인 P4는 잠깐만 CPU를 얻으면 빠르게 처리하고 나갈 수 있지만, 앞에 있는 프로세스들을 기다리느냐 30ms나 대기해야 한다.
최단작업 우선(Shortest-Job First: SJF)
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식이다. 늦게 도착하더라도 CPU 처리 시간이 앞에 대기중인 프로세스보다 짧으면 먼저 CPU를 할당받을 수 있다. 때문에 콘보이 효과를 완화할 수 있다.
단, 비선점형 방식이기 때문에 CPU를 사용중인 프로세스보다 처리 시간이 짧더라도 빼앗지는 못한다.
위의 그림은 만약 모든 프로세스가 0초에 동시 도착했다는 가정이다. 그렇다면 P4가 CPU 버스트 타임이 가장 짧기 때문에 먼저 실행되고, P1이 가장 나중에 실행된다. 그 결과 평균 대기 시간이 4.5 ms로 측정되는데, 위 FCFS 에서는 평균 대기 시간이 18.75 ms로 측정된걸 생각해 보면 월등히 짧아진 것을 확인할 수 있다. 이처럼 SJF 스케줄링 알고리즘은 평균 대기 시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.
하지만 만약 P1이 가장 먼저 도착했다면 어쩔 수 없이 P1이 먼저 CPU를 점유하게 된다. 또한 보통의 경우, 프로세스들이 동시에 도착하는 경우는 거의 없다. 때문에 이를 개선한 선점형 방식이 있다.
SRTF(Shortest Remaining Time First)
SJF의 선점형 구현 방식으로, 현재 CPU에서 실행 중인 프로세스의 남은 CPU 버스트 시간보다 짧은 CPU 버스트 시간을 가지는 프로세스가 준비 큐에 도착할 경우 CPU를 빼앗는 방식이다.
위 그림에서는 프로세스 P1, P2, P3, P4가 차례로 도착하는 상황이다. 가장 먼저 도착한 P1이 일단 CPU를 점유하게 된다. 하지만 뒤이어 도착한 P2의 CPU 버스트 시간이 짧으므로 P1이 점유하고 있던 CPU를 빼앗아 선점하게 된다. 이런 방식으로 모든 프로세스를 처리하고 나면 평균 대기 시간이 4.25 ms로 가장 짧게 된다.
일반적인 시분할 환경에서는 중간중간에 새로운 프로세스가 도착하는 경우가 발생하므로 이러한 선점형 방식이 평균 대기 시간을 가장 많이 줄일 수 있는 방식이 된다.
물론 단점도 존재한다. 처리 시간이 긴 프로세스의 경우 처리 시간이 짧은 프로세스가 계속해서 들어온다면 대기 큐에서 영영 CPU를 할당받지 못할 수 있다. 이를 기아(starvation) 현상이라고 하며, 중요한 문제다.
그리고 중간에 입출력 버스트가 빈번하게 요구되는 프로세스의 경우 운영체제가 프로세스의 종료 시간을 정확하게 예측하기 어렵고, 잦은 프로세스의 문맥 교환(context switch)이 발생하는 등의 오버헤드도 무시할 수는 없다.
우선순위 스케줄링(Priority Scheduling)
준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 우선순위를 결정하는 방식에는 여러 가지가 있을 수 있으며, 구현 방식에 따라 선점형과 비선점형으로 나눌 수 있다. 하지만 보통은 선점형 방식으로 구현된다.
우선순위 스케줄링 방식에서도 기아 현상이 발생할 수 있다. 이를 해결하기 위해 보통 노화(Aging) 기법을 사용한다. 기다리는 시간이 길어진 프로세스에게 우선순위를 높여주는 방법으로, 언젠가는 CPU를 할당받을 수 있게 해주는 방법이다.
라운드 로빈(Round Robin)
프로세스에게 각각 동일한 CPU 할당 시간(타임 슬라이스, quantum)을 부여해서 이 시간 동안만 CPU를 이용하게 한다. 만약 할당 시간동안 처리를 다 하지 못하면 CPU를 빼앗고 다음 프로세스에게 넘긴다. 빼앗긴 프로세스는 준비 큐의 맨 뒤로 간다. 따라서 선점형 방식이다. 따로 CPU 처리 시간을 계산하지 않아도 돼서 선점형 방식의 가장 단순하고 대표적인 방법이다. 우선 순위도 없기 때문에 매우 공평하다.
만약 할당 시간이 q고 대기 중인 프로세스가 n개라면 어떤 프로세스도 (n-1)q 이상을 기다리지 않아도 된다. 이는 곧 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 큰 장점을 가지게 된다. 자연히 콘보이 효과도 줄어든다.
위의 경우 타임 슬라이스를 5로 설정했다. 타임 슬라이스 동안 CPU 버스트 처리를 다 하지 못한 P1은 CPU를 빼앗기고 대기 큐의 맨 뒤로 간 다음 P2에게 넘겨준다. P2는 3ms만에 처리를 완료하고 바로 P3에게 CPU를 넘겨준다. 평균 대기 시간이 11 ms로 SJF 보다 길지만, 각 프로세스의 평균 응답 시간은 짧아졌다.
라운드 로빈 방식에서 가장 중요한 부분은 타임 슬라이스의 크기 결정이다. 타임 슬라이스가 큰 경우 처리 시간이 긴 프로세스에 의해 CPU의 효율성이 떨어질 수 있다. 비디오 플레이어와 워드 프로세서를 동시에 실행했을 때 타임 슬라이스가 크다면 비디오가 약간 씩 끊겨서 재생될 것이다. 그리고 만약 타임 슬라이스가 무한대로 설정되면 FCFS 스케줄링과 다를 바 없어진다.
타임 슬라이스가 작은 경우 여러 프로그램이 동시에 실행되는 효과를 볼 수 있다. 하지만 너무 작으면 잦은 문맥 교환이 일어나 오버헤드가 상당히 커진다.
때문에 적당한 타임 슬라이스를 설정하는 것이 중요하다. 보통 10-100 ms로 설정하면, 사용자(사람)의 입장에서는 충분히 빠른 시간이기 때문에, 프로세스가 빠르게 응답하는 것처럼 보일 수 있다.
멀티레벨 큐(Multi-level Queue)
멀테레벨 큐 스케줄링은 우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 당연히 우선순위가 높은 큐에 먼저 CPU가 할당되어 큐에 속한 모든 프로세스가 처리되야 다음 우선순위 큐가 실행될 수 있다. 그리고 한 번 우선순위가 매겨저 준비 큐에 들어가면 이 우선순위는 바뀌지 않는다.
각 큐는 독립적인 스케줄링 알고리즘을 가질 수 있다. 보통 대화형 작업이 많은 전면 프로세스들이 전위 큐(foreground queue)에 속하므로 우선순위가 높고, 응답 시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용한다.
반면, 계산 위주의 후면 프로세스는 후위 큐(background queue)에 배치되어, 사용자와의 상호작용이 없어 응답 시간이 큰 의미를 가지지 못한다. 따라서 가장 간단하면서도 문맥 교환 오버헤드를 줄일 수 있는 FCFS 방식으로 처리한다. 보통 총 CPU 시간이 전면 프로세스의 처리에 80%, 후면 프로세스 처리에 20%가 할당된다.
멀티레벨 피드백 큐(Multi-level Feedback Queue)
멀테레벨 큐에서는 프로세스가 큐에 들어가면 우선순위가 고정되어 다른 큐로 이동할 수 없었다. 이때 발생하는 기아 현상을 완화하기 위해, 이 알고리즘에서는 우선순위를 상황에 맞게 변동시켜 다른 큐로 이동할 수 있게 한다.
한 번 CPU를 할당받은 프로세스는 우선순위가 조금 낮아진다. 따라서 더 낮은 큐로 이동하게 된다. (반대로 우선순위가 높아져 상위 큐로 이동할 수도 있다)
그리고 우선순위가 높은 큐보다 우선순위가 낮은 큐에 타임 슬라이스 크기를 크게 준다. 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있게 배려해 주는 것이다.
Reference
운영체제와 정보기술의 원리 - 저자 반효경