6. CPU 스케줄링

이 글은 CPU 스케줄링 대해 다루겠습니다. 스케줄링이란 주어진 시점에서 어떤 프로세스가 이 자원을 사용할 수 있도록 해 줄 것인가를  결정하는 것을 뜻합니다. 전체적인 내용은 OS? Oh Yes! 서적 기반, 숙명여대 김주균 교수님 강의, 제타위키 등을 정리했습니다. 공부한 것을 정리하는 형식으로 작성되었으므로 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

스케줄링의 단계

스케줄링이 요구되는 시점에 스케줄링의 단계를 3가지로 분류할 수 있습니다. 하나씩 살펴보도록 하겠습니다.

• Long-term scheduling  (= Job scheduling , 장기 스케줄링 = 작업 스케줄링)
• Medium-term scheduling (중기 스케줄링)
• Short-term scheduling (단기 스케줄링)

 [ Long-term scheduling ] (장기 스케줄링) 

장기 스케줄링은 어느 작업을 커널에 등록시켜 프로세스로 만들어줄 것인가를 결정합니다. 그렇기 때문에 다르게 표현해서 다중 프로그래밍의 정도(Multiprogramming Degree)를 조절하는 역할을 한다고 볼 수 있겠습니다. 빈번하게 수행되지는 않고 주로 FIFO/FCFS방식(아래 스케줄링 기법에서 설명)을 사용합니다.

 [ Medium-term scheduling ] (중기 스케줄링) 

보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정합니다. 프로세스의 상태 변화와 관련된 글은 이전 글에 있습니다.

 [ Short-term scheduling ] (단기 스케줄링) 

단기 스케줄링은 프로세스 스케줄러(= 디스패쳐)에 의해 준비 상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지를 결정해줍니다. 앞서 1 ~ 5번 글에서 혹시 'CPU 스케줄링'이라는 단어를 보셨다면 전부 단기 스케줄링을 뜻했던 것이며, 일반적으로 부르는 프로세스 스케줄링이 이에 해당됩니다.

단기 스케줄링은 그 실행빈도도 잦으며 입출력 요청, 시간 종료, 시스템 콜 등과 같은 다양한 이유에 의해 가동되기 때문에 한 번 실행 할 때 드는 시간을 줄이는 것이 중요합니다. 이후로 다룰 스케줄링은 단기 스케줄링이 되겠습니다.

스케줄링의 목적

너무나도 당연하게 스케줄링의 목적은 (앞에도 언급되어 있듯이) CPU를 할당받을 프로세스를 잘 골라 실행시켜 결과적으로 시스템의 성능을 향상시키는 것입니다. 그런데 시스템의 성능이 좋은지 나쁜지를 어떻게 구별할 수 있을까요? 사용자의 관점에서, 시스템의 관점에서 알아보도록 하겠습니다.

사용자에게 성능이 우수한 시스템이란 응답 시간(response time)이 빠를 수록 좋을 것입니다. 여기서 응답 시간이란 프로세스의 요청에 대해 시스템이 최초로 출력을 내주기 시작할 때까지 걸린 시간을 뜻하는데, 이 외에도 요청한 일이 얼마 후 쯤에 완료 될 수 있을 것이라는 예측 가능성도 성능 평가의 지표로 쓸 수 있습니다.

시스템에게 뛰어난 성능으로 평가받으려면 처리량, 활용도, 응답시간 등을 평가 지표로 삼으면 됩니다. 대화형 시스템의 경우 응답 시간이 중요하고, 일괄처리 시스템에서는 처리량이 가장 중요한 지표입니다. 그러나 이 기준들은 서로 상충하는 것들도 있어 모든 기준에게 우수한 평가를 받을 수는 없습니다. 가령 응답시간을 높이기 위해 스케줄링을 자주 한다면 그때마다 CPU를 이용해서 문맥교환이 필요하기 때문에 결국 사용자 프로세스를 실행해 줄 시간이 줄어들어 전체 처리량은 감소하게 되는 것입니다. 반면 처리량을 높이기 위해 수행 시간이 짧은 프로세스들만 계속 처리한다면 수행 시간이 긴 프로세스는 처리가 늦어지거나 계속 기다려야 해서 응답 시간이 느려지는 것입니다. 이렇 듯 모든 기준을 만족시킬 수는 없으므로 시스템을 사용하는 목적과 환경에 맞게 설계하여 스케줄링을 해야합니다.

스케줄링 기법들

먼저 스케줄링이 사용되는 경우를 살펴보도록 하겠습니다.

1. 실행 상태 → 대기 상태 : ex. 입출력 요청에 의해 전환
2. 실행 상태 → 준비 상태 : ex. 시간 종료에 의한 인터럽트로 전환
3. 대기 상태 → 준비 상태 : ex. 입출력 종료 되었을 때
4. 프로세스가 수행을 마치고 종료 될 때

스케줄링 기법은 2가지로 나눌 수 있습니다. Non-preemptive scheduling(비선점 스케줄링)과 Preemptive scheduling(선점 스케줄링)으로 나눌 수 있는데 전자는 한 프로세스가 CPU를 할당 받았다면 스스로 반납할 때까지 계속 사용하도록 허용하는 방식이고 후자는 CPU를 할당 받아 실행 중인 프로세스로부터 CPU를 빼앗고 다른 프로세스에게 할당해 줄 수 있는 방식입니다. 위에서 본 스케줄링이 사용되는 경우 중 1번과 4번은 프로세스가 CPU를 직접 반납하기 때문에 비선점 방식이라고 볼 수 있고 2번은 빼았기기 때문에 선점 방식, 3번은 빼앗기 때문에 선점 방식이라고 부를 수 있습니다.

 [ FCFS 스케줄링 ] (First Come First Service) 

FIFO 스케줄링이라고도 불리는 FCFS 스케줄링은 비선점 방식으로 준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해주는 방식입니다. 이 기법은 한 프로세스가 CPU를 독점하기 때문에 긴 프로세스를 실행 시 오랫동안 다른 프로세스들이 준비 큐에서 기다려야 하므로 대화식 시스템에는 부적합합니다.

• 장점
  • 준비 상태의 프로세스들의 개수와 크기(시간)을 알면 각각의 프로세스들이 언제 실행될 수 있을지 예측 가능
  • 도착 순서에 따라 실행을 하므로 공평
• 단점 : 평균 응답 시간이 길어짐

프로세스	도착 시간	CPU 요구량(초)
P1	0	100
P2	0	10
P3	0	10
P4	0	10

위와 같이 간트차트가 주어졌을 때 모든 프로세스가 거의 동시에 P1, P2, P3, P4의 순서로 도착했다고 하면 프로세스가 아래 그림의 (A)와 같이 완료가 될 것입니다. (응답 시간을 프로세스가 끝나는 시간으로 간주하도록 하고 계산하겠습니다.) 반면 프로세스들이 P2, P3, P4, P1의 순서로 들어왔다면 (B)와 같이 완료가 될 것입니다. 이를 통해 알 수 있는 것은 FCFS는 프로세스의 순서에 따라 평균 응답시간이 매우 달라질 수 있다는 것입니다. 물론 평균 응답시간이 짧다고 해서 전체 프로세스의 응답시간이 빨라지는 것은 아니지만 확률적으로 가능성이 높으므로 평균 응답 시간을 줄이기 위한 노력은 해야합니다.

 [ SPN 스케줄링 ] (Shortest Process Next) 

SJF(Shortest Job First) 라고도 불리는 SPN 스케줄링은 비선점 방식으로 준비 큐에서 기다리고 있는 프로세스 중에서 CPU 요구량이 가장 작은 것은 먼저 실행 시켜주는 방식입니다.

• 장점
  • 평균 응답 시간 최소화 가능
  • 실행할 프로세스 수가 충분하다면 처리량에 관해 매우 훌륭한 성능
• 단점
  • 긴 프로세스의 무한 대기 현상
  • 실제 프로세스들의 크기를 정확히 알 수 없음에도 스케줄을 해야 함

SPN이 가진 첫 번째 단점인 긴 프로세스의 무한 대기 현상을 극복하기 위해 aging(에이징)이라는 방법을 통해 극복을 할 수 있습니다. 에이징이란 기다린 시간만큼 우선순위를 높여주는 방식으로 긴 프로세스지만 오래 기다렸으면 그 실행가능성을 높여주는 것입니다. 이 방법은 뒤에 나오는 HRRN 스케줄링 기법에서 살펴보실 수 있습니다. 두번째 단점이었던 미지의 실제 프로세스 크기는 프로세스 실행 전 지수 평균(exponential averaging) 방법을 통해 추정을 해봄으로서 극복할 수 있습니다.

프로세스	도착 시간	CPU 요구량(초)
P1	0	10
P2	0.5	5
P3	1	2

위와 같이 간트 차트를 그려보았고 P1에게 CPU가 주어진 다음 각각 P2와 P3가 0.5초, 1초 후에 도착했다면 평균 응답 시간은 다음과 같이 구할 수 있습니다. 비교를 위해 (A)는 FCFS 스케줄링을 쓴 방식이고, (B)가 SPN 스케줄링을 쓴 방식입니다.

 [ SRT 스케줄링 ] (Shortest Remaining Time) 

SRT는 선점 방식으로 준비 큐에서 완료까지 남은 CPU 요구량이 가장 짧은 것을 먼저 실행시켜주는 방식입니다. 하나의 프로세스를 실행 도중 준비 큐에 완료까지 남은 요구량이 더 적은 프로세스가 있다면 실행을 멈추고 CPU를 넘겨주게 됩니다. 그러나 계속해서 시간이 짧은 프로세스가 자주 도착하면 잦은 선점으로 문백교환의 부담이 있습니다. 이를 조금 완화하기 위해 SRT 스케줄링 시 임계 값을 정해 두고 두 프로세스의 남은 시간 차이가 임계 값 보다 작으면 선점이 되지 않는 방법을 쓸 수도 있습니다.

SPN 스케줄링 때 썼던 예시로 SRT 평균 응답 시간을 계산해보도록 하겠습니다.

 [ HRRN 스케줄링 ] (Highest Response Ratio Next) 

HRRN 스케줄링은 비선점 방식으로 준비 큐에 있는 프로세스들 중 응답률이 가장 높은 프로세스에게 높은 우선순위를 주는 방식입니다. 위에서 살펴본 SRT와 SPN의 단점인 긴 프로세스의 무한 대기 현상을 방지할 수 있습니다. 여기서 응답률은 다음과 같이 계산됩니다.

응답률 = (대기 시간 + CPU 요구량) / CPU 요구량

이 기법을 사용하면 프로세스가 기다리는 시간이 길어질 수록 우선 순위가 높아지므로 곧 CPU를 할당 받게 되고, 평균 응답 시간의 단축도 이룰 수 있습니다.

 [ Round-Robin 스케줄링 ] 

선점 방식으로 시간 할당량이 지나면 시간 종료 인터럽트에 의해 CPU를 뺴앗기는 방식입니다. FCFS 스케줄링을 기반으로 한 Round-Robin 스케줄링은 실행이 완료되지 않은 채 CPU를 뺴앗기면 준비큐의 맨 뒤로 들어가게 됩니다.

거의 동시에 도착한 4개의 프로세스들에 대한 간트차트가 아래와 같고 시간 할당량이 10ms일 때 평균 응답 시간은 다음과 같습니다.

프로세스	CPU 요구량(ms)
P1	30
P2	8
P3	15
P4	10

 [ Multi-level Queue 스케줄링 ] (다단계큐) 

다단계큐는 선점 방식으로 프로세스들을 정해져 있는 숫자만큼의 그룹별 큐로 분류하는 스케줄링 방식입니다. 즉 우선순위의 개수만큼 큐가 필요한 것입니다. 정해진 알고리즘에 따라 프로세스는 처음에 어떤 그룹으로 가게 될지 정해지고 프로세스는 큐들 간 이동을 하지 못합니다. 하위 우선 순위를 가진 프로세스를 실행하던 중 자신 보다 높은 우선순위를 가진 프로세스가 해당 우선순위 큐에 삽입되면 CPU를 선점당합니다.

 [ MFQ 스케줄링 ] (Multi-level Feedback Queue, 다단계 피드백 큐) 

MFQ 스케줄링은 선점 방식으로 운영되는데, 우선 순위 개수만큼의 큐가 존재하며 각 단계마다 서로 다른 CPU 시간 할당량을 가집니다. 우선순위가 높은 단계의 큐일수록 주어진 시간 할당량은 작습니다. 따라서 처음 프로세스가 들어오면 제일 높은 우선순위의 큐에서 실행을 하다 시간 할당량이 끝나면 한 단계씩 아래로 떨어집니다. 단 시간 할당량이 끝나기 전에 입출력으로 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐로 들어갑니다.(입출력 위주 프로세스들이 선호됨을 알 수 있음)

MFQ

Realtime(실시간) 스케줄링

실시간 시스템이란 실행될 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템으로서 Hard Realtime(경성)과 Soft Realtime(연성)으로 나눌 수 있습니다. 전자의 경우 마감 시한 내에 완료하지 못하면 시스템에 치명적인 결과를 초래하고 후자의 경우 피해는 발생하지만 계속 시스템을 운영은 가능합니다. 주로 실시간이라는 말은 경성을 뜻합니다.

실시간 시스템에서의 스케줄링은 모든 프로세스들이 정해진 마감 시한 내에 완료되도록 하는 것이 관건입니다. 정적인 방법은 프로세스들의 특징과 개수를 알 수 있는 경우 유용하고 동적인 방법은 프로세스의 생성 시간이나 특성을 알 수 없는 경우에 사용되지만 실시간 시스템은 특수한 환경이라 실행 될 일들의 서역이나 개수는 사전에 알 수 있는 경우가 많습니다.

 [ RM 알고리즘 ] (Rate Monotonic) 

정적 스케줄링 방식으로 낮은 우선순위의 프로세스가 더 높은 우선순위의 프로세스가 도착할 경우 CPU를 뺴앗기는 선점 방식입니다. RM 알고리즘은 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용되는데, 이 때 주기가 짧을 수록 우선순위가 높습니다. 장점은 스케줄링 비용이 적게든다는 것이고, 단점은 새로운 프로세스가 추가되면 전체 스케줄링을 다시 해야한다는 것입니다. 

 [ EDF 알고리즘 ] (Earliest Deadline First) 

동적 스케줄링 방식으로 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식입니다. 한 프로세스의 실행이 완료될 때 마감 시한이 가장 임박한 것을 찾아 스케줄하게 됩니다. 이 기법은 프로세스의 동적이 수용이 허용되나 가능한 스케줄을 찾기 위해 계산을 해야하는 부담이 있습니다.