이번 시간에는 각 프로세스가 어떤 시점에서 자원을 사용할 수 있게 결정해주는 CPU 스케줄링에 대해서 알아보겠습니다.
1. 스케줄링(Scheduling)의 단계
➡️ 프로세스 스케줄링은 수행 단계에 따라 장기, 중기, 단기 스케줄링으로 나눌 수 있습니다.
-
장기 스케줄링 : 어느 작업을 커널에 등록시켜 프로세스로 만들어 줄 것인가를 결정하는 것
-
중기 스케줄링 : 보류 상태의 프로세스들 중에서 어느 프로세스에게 메모리를 할당해 줄 것인가를 결정
=> 이는 다른 말로 표현하면 Swapped out 된 프로세스들 중 어떤 프로세스를 Swapped In 해줄 것인지 결정하는 것입니다.
-
단기 스케줄링 : 준비 상태에 있는 프로세스들 중에서 어느 프로세스에게 CPU를 할당할지 결정하는 것
2. 스케줄링 기법들
➡️ 스케줄링은 다음과 같은 상황에 필요합니다.
-
프로세스가 실행 상태에서 대기 상태로 전환될 때 (ex. 입출력 요청)
-
프로세스가 실행 상태에서 준비 상태로 전환될 때 (ex. 시간 종료와 같은 인터럽트 발생)
-
프로세스가 대기 상태에서 준비 상태로 전환될 때 (ex. 입출력의 종료)
-
프로세스가 수행을 마치고 종료될 때
✅ 스케줄링의 기법들은 비선점(NonPreemiptive)과 선점(Preemptive) 스케줄링으로 분류할 수 있습니다.
- 비선점 스케줄링 : 한 프로세스가 CPU를 할당받았을 때 스스로 반납할 때까지 계속 사용하도록 허용하는 방법
- 선점 스케줄링 : CPU를 할당받아 실행 중인 프로세스로부터 CPU를 선점하여(빼앗아) 다른 프로세스에 할당할 수 있는 방법
앞에서 1, 4번의 경우는 비선점 방식으로 스케줄링을 하게 되고 2, 3번은 선점 스케줄링 방식이 적용됩니다.
2-1. FCFS (First Come First Sevice) 스케줄링
이 스케줄링 방식은 FIFO(First In First Out) 스케줄링이라고도 합니다.
준비 큐에 먼저 도착한 프로세스에게 먼저 CPU를 할당해 주며 CPU를 할당받은 프로세스는 스스로 CPU를 반납할 때까지 CPU를 독점하여 사용하는 비선점 방식입니다.
다음은 FCFS 스케줄링에 의한 칸트(Gantt) 차트입니다. 여기서 평균 응답 시간은 평균 완료 시간으로 생각하시면 됩니다.
프로세스가 들어오는 순서에 따라서 응답 시간이 달라지는 것을 확인할 수 있습니다.
2-2. SJF(Shortest Job First) or SPN(Shortest Process Next) 스케줄링
준비 큐에서 기다리고 있는 프로세스 중에서 가장 짧은(CPU 요구량이 가장 적은) 프로세스를 먼저 실행시켜 주는 비선점 방식입니다.
이 방식은 평균 응답 시간을 최소화할 수 있지만 실행 시간이 긴 프로세스가 CPU를 할당받지 못하는 무한 대기 현상이 발생할 수 있습니다.
2-3. SRT(Shortest Remaining Time) or SRTF 스케줄링
바로 앞의 SPN 스케줄링 방식을 선점 방식으로 운영하는 것이 SRT 스케줄링입니다.
준비 큐에서 완료까지 남은 CPU 요구량이 가장 짦은 것을 먼저 실행시켜주는 방식입니다.
실행 도중 남은 실행 시간이 더 적은 프로세스가 준비 큐에 들어올 경우 현재 실행 중인 것을 중단하고 새 프로세스에게 CPU를 할당하는 선점 방식입니다.
이 스케줄링 방식은 계속해서 현재 실행 프로세스보다 짧은 시간의 프로세스가 들어온다면 잦은 선점이 일어나 문맥교환의 부담이 있다는 단점이 있습니다.
2-4. HRRN(Highest Response Ratio Next) 스케줄링
이 스케줄링 기법은 응답률(Response Ratio)이 가장 높은 프로세스에게 높은 우선순위를 주면, 비선점 방식입니다.
2-5. 라운드 로빈(Round-Robin) 스케줄링
라운드 로빈 방식은 FCFS 스케줄링을 기반으로 CPU를 프로세스에게 할당하지만, 각 프로세스는 한 번에 쓸 수 있는 시간 할당량(Time Quantum)이 지나면 시간 종료 인터럽트에 의해 CPU를 뺏기는 선점 방식입니다.
라운드 로빈 방식을 살펴 보면 연산 위주의 프로세스들은 시간 할당량을 모두 소진하고 큐의 맨 뒤로 가게 되지만 입출력 위주의 프로세스들은 시간 할당량을 모두 사용하지 못하고 큐의 맨 뒤로 가는 것을 확인할 수 있습니다.
이를 방지하기 위해 입출력을 마치 프로세스가 들어가는 준비 큐를 따로 하나 만들어 줍니다.
이 큐에서 프로세스들은 CPU를 할당 받을 때 전에 쓰지 못하고 남긴 시간 할당량을 받게 됩니다.
✅ 이 방식을 가상(Virtual) 라운드 로빈 기법이라고 합니다.
2-6. 다단계 큐(Multi-level Queue, MLQ) 스케줄링
MLQ 스케줄링 방식은 정적 우선순위를 사용하는 스케줄링 방식입니다.
같은 우선순위 값을 가진 프로세스들을 위한 큐가 필요하고 서로 다른 우선순위의 프로세스들을 구별하기 위해서 우선순위의 개수만큼 큐가 필요합니다.
MLQ 스케줄링은 선점 방식으로 운영됩니다.
2-7. 다단계 피드백 큐(Multi-level Feedback Queue, MFQ) 스케줄링
MFQ 스케줄링 방식은 동적 우선순위를 기반으로 하는 선점 방식으로 운영됩니다.
우선 순위만큼 큐가 존재하고 각 단계마다 서로 다른 CPU 시간 할당량을 가집니다. 우선순위가 높은 단계의 큐일수록 시간 할당량은 작도록 합니다.
[방식]
- 프로세스는 CPU를 할당받아 실행되다가 시간 할당량(Time Quantum)을 다 소모하면 한 단계 아래의 큐에 들어가 우선순위가 낮아지게 됩니다.
- 시간 할당량이 끝나기 전에 입출력(I/O)으로 인해 CPU를 내놓게 되면 다시 준비 상태가 되었을 때 한 단계 위의 큐에 들어가게 하여 우선순위를 높여줍니다.
3. 실시간(Realtime) 스케줄링
실시간 스케줄링에 대해서 알아보기 전에 실시간 시스템에 대해서 간단이 짚고 넘어가야 합니다.
실시간 시스템이란 실행될 때 모든 프로세스들이 정해진 시간 내에 완료되어야 하는 시스템을 말합니다.
이 실시간 시스템에서의 스케줄링은 모든 프로세스들이 정해진 마감시한 내에 완료되도록 해야 하는 것이 중요합니다.
3-1. RM(Rate Monotinic) 알고리즘
RM 알고리즘은 대표적인 정적 스케줄링 방식입니다. 크기와 개수가 알려진 프로세스들이 각자 주기적으로 발생되는 환경에서 사용됩니다.
프로세스의 주기가 짧을수록 높은 우선순위를 받게 되고 선점 방식으로 운영됩니다.
3-2. EDF(Earliest Deadline First) 알고리즘
EDF 알고리즘은 프로세스의 마감시한이 가까울수록 우선순위를 높게 부여하는 선점 방식의 동적 스케줄링입니다.
이 기법은 우선순위에 의해 실행 중 CPU를 뺏길 수 있고, 한 프로세스의 실행이 완료될 경우에는 마감시한이 가장 가까운 프로세스를 찾아 스케줄링합니다.
마무리
오늘은 여러가지 CPU 스케줄링 기법에 대해서 알아보았습니다. 각 스케줄링 기법이 어떻게 동작하고 어떤 특징을 가지고 있는지 파악하는 것이 중요합니다.
다음 시간에는 병행 프로세스와 동기화에 대해서 살펴보겠습니다.
