[OS] CPU 스케줄링

CPU 스케줄링

개인적으로 공부하면서 정리하는 글입니다. 내용에 오류가 있는 경우 댓글 달아주시면 수정하도록 하겠습니다.

CPU 스케줄링이란?

CPU는 한 번에 한 가지 일(프로세스)만 수행할 수 있습니다. 주기억 장치에 적재되어 있는 프로세스 중 하나의 프로세스에 할당되어 작업을 수행하는데요.

그럼 CPU를 할당받기 기다리고 있는 많은 프로세스들 중 어느 프로세스에 CPU를 할당할 것인가? 하는 것이 바로 CPU 스케줄링 이고, 스케줄링을 해주는 커널 프로그램을 스케줄러라고 합니다.

사실, 프로세스 스케줄링은 3가지 단계가 있는데요.

1. 어느 프로그램을 주기억장치에 적재하여 프로세스로 만들 것인가를 결정하는 장기 스케줄링

2. 주기억장치에 있는 프로세스를 보류 상태로 만들거나, 보류 상태인 프로세스를 주기억 장치에 적재하는 중기 스케줄링

3. 주기억장치에 적재되어 있는 프로세스 중 어느 프로세스에 CPU를 할당할 것인가를 결정하는 단기 스케줄링

요즘에는 장기, 중기 스케줄링은 많이 쓰이지 않아서 '프로세스 스케줄링 == CPU 스케줄링' 으로 많이 말합니다.

스케줄링을 하는 이유, 기준

스케줄링을 하는 목적은 실행시킬 프로세스를 잘 골라 전체적인 시스템 성능을 높이는 것입니다. 그렇다면 시스템 성능이 좋다는 기준은 뭐가 있을까요?

응답 시간(Response Time) : 프로세스의 요청에 대한 응답이 걸리는 시간

예측 가능성(Predictability) : 프로세스의 요청한 일이 얼마 후 쯤에는 완료될 수 있을 것

처리량(Throughput) : 단위 시간에 완료된 프로세스의 수

활용도(Utilization) : 주어진 시간 동안 특정 자원이 실제로 가동된 시간의 비율

대화형 시스템은 응답 시간이, 일괄 처리 시스템에서는 처리량이 가장 중요한 지표로 인식되는데요. 응답 시간과 처리량은 서로 상충되는 부분이 있기 때문에 시스템을 사용하는 환경과 목적에 맞게 스케줄링을 해주어야 합니다.

단일 큐 스케줄링 기법

CPU 스케줄링(단기 스케줄링)은 주기억장치에 적재된 프로세스 중 하나에 CPU를 할당하는 것이라고 했는데요. CPU 스케줄링이 가동되는 상황은 CPU를 할당받아 실행 중이던 프로세스가 준비,대기,종료 상태가 될 때입니다. CPU는 준비 큐에 있는 다른 프로세스를 할당받게 되겠죠. 이 때 준비 큐가 동작하는 방식을 스케줄링 기법이라고 합니다.

스케줄링 기법들은 크게 선점(Preemptive)스케줄링과, 비선점(Nonpreemptive)스케줄링으로 분류할 수 있습니다.

• 선점(Preemptive)스케줄링 : 실행 도중 다른 프로세스에게 CPU를 뺏길 수 있음
• 비선점(Nonpreemptive)스케줄링 : 프로세스가 스스로 반납할 때 까지 CPU를 뺏기지 않음

프로세스가 스스로 CPU를 반납한다는 것은, 작업이 모두 완료되어 종료 상태가 되거나 I/O 등으로 인해 대기 상태가 되는 것을 말합니다. 선점 스케줄링으로 동작한다고 해도 I/O가 발생하면 프로세스는 스스로 CPU를 반납하고 대기 상태가 되어 I/O가 완료되면 준비 큐의 끝으로 들어가게 됩니다.

1. FIFO(Firt in First out)

FCFS(First Come First Service)라고도 부르는 FIFO 스케줄링은 준비 큐에 가장 먼저 들어온 프로세스가 CPU를 할당받아 스스로 CPU를 반납할 때 까지 작업을 수행하는 비선점 방식 스케줄링입니다.

FIFO 기법은 대화식 시스템에 적합하지 않고, 가장 단순한 형태로 실제 시스템에서 바로 사용되기는 힘들지만 다른 스케줄링 기법의 보조 장치로서 활용이 가능합니다.

2. SJF(Shortest Job First)

SPN(Shortest Process Next)라고도 부르는 SJF 스케줄링은 준비 큐에서 기다리고 있는 프로세스 중 가장 짧은(CPU 요구량이 가장 적은) 프로세스에게 CPU를 할당하는 비선점 방식 스케줄링입니다.

SJF 기법은 평균 응답 시간을 최소화할 수 있지만, 실행 시간이 긴 프로세스가 계속 대기하는 무한 대기 현상이 발생할 수 있습니다. 또한, 각 프로세스의 총 CPU 요구량(총 실행시간)은 실행 전에 정확히 알 수 없는 문제도 있습니다.

3. SRT(Shortest Remaining Time)

SRT 스케줄링은 남은 CPU 요구량(남은 실행시간)이 가장 짧은 프로세스에 CPU를 할당하는 선점 방식 스케줄링입니다. 현재 실행중인 프로세스보다 남은 시간이 더 짧은 프로세스가 준비 큐에 있다면, 실행 중이던 프로세스는 CPU를 뺏기고 준비 큐로 돌아가게 됩니다.

SRT 스케줄링은 SJF 스케줄링보다 평균 응답 시간이 수치상으로 빠르지만, 잦은 선점으로 인한 문맥교환 횟수 증가로 실제 평균 응답 시간은 수치상으로 나타나는 시간보다 더 깁니다. 두 프로세스 간 남은 시간의 차이가 임계 값을 넘지 않는 경우 선점되지 않는 방법을 통해 문맥교환 횟수를 줄일 수 있습니다.

4. HRRN(Highest Response Ratio Next)

SJF 스케줄링과 SRT 스케줄링은 수행 시간이 긴 프로세스의 무한 대기 현상이 발생할 수 있는 단점이 존재합니다. 이 것을 방지하기 위한 기법이 바로 HRRN 스케줄링입니다.

HRRN 스케줄링은 준비 큐에 있는 프로세스 중 응답률(Response Ratio)가 가장 높은 프로세스에게 CPU를 할당하는 비선점 방식 스케줄링인데요. 여기서 응답률은 아래와 같이 계산할 수 있습니다.
$$
응답률 = {(대기시간+CPU요구량) \over CPU요구량}
$$
준비 큐에서 대기하는 시간이 길어질수록 응답률은 높아지므로 수행시간이 긴 프로세스도 CPU를 할당받을 수 있게 됩니다. (Aging 기법)

5. 라운드 로빈(Round-Robin)

라운드 로빈 스케줄링은 FIFO 방식을 기반으로 CPU를 할당하는데, 각 프로세스가 한 번에 CPU를 사용할 수 있는 시간의 크기(시간 할당량)을 정해놓습니다. 프로세스는 CPU를 할당받아 실행하던 중 정해진 시간할당량을 채우면 시간 종료 인터럽트에 의해 CPU를 뺏기게 됩니다.(선점 방식)

라운드 로빈 스케줄링은 FIFO 기법처럼 수행 시간이 긴 프로세스가 CPU를 독점하는 것을 방지할 수 있으나 선점에 따른 문맥교환의 오버헤드를 감수해야 합니다. 이러한 오버헤드에도 불구하고 라운드 로빈 방식은 대화식 시스템이나 시분할 시스템에 적합한 방식으로 알려져 있습니다.

라운드 로빈 기법은 시간 할당량(Time Quantum)의 크기에 따라 시스템의 성능이 좌우되는데요. 시간 할당량이 너무 크면 FIFO와 같아지고, 너무 작으면 문맥교환이 자주 발생하게 됩니다. 일반적으로 시간 할당량의 크기는 10~100ms 정도가 적당하다고 알려져 있습니다.

다중 큐 스케줄링 기법

위에서 소개한 단일 큐 스케줄링 기법들은 모두 하나의 큐 안에서 프로세스를 선택하는 스케줄링 기법인데요. 실제로는 준비 큐를 여러 개로 구성하여 스케줄링을 하게 됩니다. 각각의 준비 큐 내에서 동작하는 우선순위는 큐 안에서 부여되는 우선순위이고, 프로세스는 생성될 때 각각 우선순위를 부여받아 PCB(프로세스 제어 블록)에 저장하게 됩니다.

프로세스가 생성된 후 종료될 때 까지 우선순위가 변하지 않으면 정적 우선순위, 중간에 우선순위가 변할 수 있으면 동적 우선순위라고 합니다.

1. 다단계 큐(Multi-level Queue)

다단계 큐는 프로세스의 우선순위가 변하지 않는 정적 우선순위를 사용합니다. 각 프로세스는 생성될 때 부여받은 우선순위에 해당하는 준비 큐에 들어갑니다. 각각의 준비 큐는 별도의 스케줄링을 사용할 수 있습니다.(ex. FIFO, Round-Robin, etc...)

우선순위가 낮은 큐의 프로세스가 CPU를 할당받아 실행중이더라도, 상위 단계 큐에 프로세스가 도착하면 CPU를 선점당하게 됩니다. 정적 우선순위를 사용하기 때문에 프로세스의 고유 우선순위는 변하지 않고, 준비 큐 간의 프로세스 이동 역시 불가능합니다.

2. 다단계 피드백 큐(Multi-level Feedback Queue, MFQ)

다단계 큐는 큐 사이의 이동이 불가능하고, 높은 우선순위 준비 큐의 프로세스들이 계속 들어오면 낮은 우선순위 큐의 프로세스들이 계속 대기해야하는 문제가 있습니다. 이런 문제를 해결하기 위해 등장한 기법이 다단계 피드백 큐 스케줄링입니다.

다단계 피드백 큐는 동적 우선순위를 사용합니다. 우선순위 별로 준비 큐가 있는 것은 다단계 큐와 동일하지만, 다단계 피드백 큐는 준비 큐 간의 프로세스 이동이 가능합니다.

가장 낮은 우선순위를 제외한 준비 큐는 라운드 로빈 방식으로 동작합니다. 각 단계의 큐에서 시간 할당량을 채운 프로세스는 한 단계 낮은 큐로 이동하게 됩니다. 최종적으로 가장 낮은 단계로 이동한 프로세스는 더 이상 내려갈 곳이 없기 때문에 FIFO 방식으로 동작하게 됩니다.

우선순위가 높은 큐는 시간 할당량이 적고, 우선순위가 낮아질수록 시간 할당량이 많아집니다. 그리고 CPU를 할당받아 수행하던 중 입출력으로 인해 CPU를 반납한 프로세스는 입출력 종료 후 한 단계 높은 우선순위의 큐로 들어가게 됩니다. 큐 안에서 오랜 시간 대기하는 프로세스 역시 한 단계 높은 우선순위의 큐로 들어가도록 하여 수행시간이 짧은 프로세스와 입출력 프로세스를 우대하면서, 프로세스가 무한 대기하는 현상을 방지할 수 있게 해줍니다.