CPU 스케줄링 알고리즘이란 운영체제가 하나의 프로세스 작업이 끝나고 나면, CPU 자원을 사용할 다음 프로세스를 선택하여 작업해야 합니다. 이때, 다음 프로세스를 선택하는 알고리즘을 말합니다.
CPU 스케줄링 알고리즘의 종류는 매우 다양합니다. 운영체제 마다 다른 스케줄링 알고리즘을 채택하여 사용합니다.
선입 선처리 스케줄링
선입 선처리 스케줄링은 FCFS(First Come First Served Scheduling) 스케줄링 이라고도 부릅니다.
FCFS 영어 해석대로 먼저 온 프로세스가 CPU를 먼저 점유하는 비선점형 스케줄링 방식입니다
언뜻 보기에는 가장 공정해 보이고 단순한 방식이지만, 프로세스들이 기다리는 시간이 매우 길어질 수 있다는 점에서 효율적인 방식은 아닙니다.
FCFS가 어떤 알고리즘인지 예제를 통해 확인해 보겠습니다.
아래의 표는 3개의 프로세스와 각 프로세스가 CPU를 사용한 시간(burst time)을 나타냅니다.
| Process | Burst Time(msec) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
이제 위 표의 내용대로 FCFS 방식으로 표현하면 아래와 같습니다.
이제 평균대기시간(Average Waiting Time)을 계산하면 (0+24+27)/3 = 17 msec으로 나타낼 수 있습니다.
이 FCFS 스케줄링 알고리즘은 순차적으로 먼저 큐에 들어온 작업부터 실행하기 때문에 호위 효과(Convoy Effect, 콘보이 현상)가 발생할 수 있습니다.
호위 효과(Convoy Effect)란 ?
작업 시간이 긴 프로세스가 먼저 큐에 도착해서, 다른 프로세스의 실행시간이 전부 늦춰져 효율성을 떨어뜨리는 현상을 말합니다.
최단 작업 우선 스케줄링
SJF(Shortest Job First Scheduling)이라고 하며, 가장 짧은 점유 시간을 지닌 프로세스를 먼저 점유하는 방식으로 기본적으로 비선점형으로 분류됩니다. 하지만 선점형으로 구현될 수 있습니다.
이 SJF 알고리즘은 호위 효과를 방지하기 위해 CPU 사용 시간이 짧은 간단한 프로세스를 먼저 실행합니다.
SJF가 어떤 알고리즘인지 예제를 통해 확인해 보겠습니다.
| Process | Burst Time(msec) |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
이제 위 표의 내용대로 SJF 방식으로 표현하면 아래와 같습니다.
이제 평균대기시간(Average Waiting Time)을 계산하면 (3+16+9+0)/4 = 7 msec으로 나타낼 수 있습니다.
이를 FCFS 방식으로 나타내면 어떤 결과가 나올까요?
먼저 온 프로세스가 점유하는 방식이므로 (0+6+14+21)/4 = 10.25 msec로 계산되며, SJF의 평균 대기시간보다 FCFS의 평균 대기시간이 긴 것을 확인할 수 있습니다.
이 SJF 방식이 효율적인 방식인 것을 이 문제를 통해 알았지만 사실 이 방법은 비현실적인 방식입니다.
왜냐하면 한 프로세스가 실행 중에는 많은 변수가 존재하기 때문에 CPU 점유 시간(Burst Time)을 알 수 없습니다.
점유 시간을 알기 위해서는 실제로 측정하는 방식이 있지만 매우 부담이 큰 작업이므로 잘 사용되지 않습니다.
라운드 로빈(Round-Robin) 스케줄링
이 라운드 로빙 스케줄링 방식은 선입 선처리 스케줄링에 타임 슬라이스(Time Slice)이라는 개념이 더해집니다.
타임 슬라이스는 타임 퀀텀(Time Quantum)이라고도 부르며, 각 프로세스가 CPU를 사용할 수 있는 정해진 시간을 의미합니다.
그래서 라운드 로빈 방식은 일정 시간을 각 프로세스에 부여하여, 하나의 프로세스가 이 일정 시간만큼 작업을 수행 후, 대기 상태로 돌아갑니다. 그 후 다음 프로세스가 일정 시간만큼 작업을 수행하고 다시 대기 상태로 돌아가는 방식으로 모든 프로세스가 돌아가면서 반복합니다.
예제를 통해 라운드 로빈에 대해서 설명해 보겠습니다.
| Process | Burst Time(msec) |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
- Time Slice : 4 msec
이제 위 표의 내용대로 라운드 로빈 방식으로 표현하면 아래와 같습니다.
위 문제에서 주어진 Time Slice 시간만큼만 점유합니다.
P2와 P3는 Time Slice가 끝나기전에 작업 수행이 끝났으며, 마지막 남은 P1이 남아있는 프로세스가 없기 때문에 Time Slice가 끝났다고 하더라도 프로세스가 종료할 때까지 계속 수행합니다.
평균대기시간(Average Waiting Time)을 계산하면 (6+4+7)/3 = 5.66 msec으로 나타낼 수 있습니다
이 라운드 로빈 방식은 Time Slice에 의존적이며, 이에 따라 스케줄링의 척도가 바뀝니다.
Time Slice 크기가 무한에 가깝다면 FCFS와 동일하게 동작하며, 0에 가깝게 설정하면 문맥 교환 오버헤드가 발생하여 비효율적일 수 있습니다.
우선순위(Priority) 스케줄링
우선순위 스케줄링은 우선순위가 높은 프로세스가 먼저 점유되는 것을 말합니다.
운영체제에서 보통 우선순위는 정수 값으로 나타내며, 작은 값이 우선순위가 높습니다.
우선순위 스케줄링이 어떤 방식으로 동작하는지 예제를 통해 확인해 보겠습니다.
| Process | Burst Time(msec) | Priority |
|---|---|---|
| P1 | 10 | 3 |
| P2 | 1 | 1 |
| P3 | 2 | 4 |
| P4 | 1 | 5 |
| P5 | 5 | 2 |
이제 위 표의 내용대로 우선순위 방식으로 표현하면 아래와 같습니다. 표에서 우선순위의 값이 낮은 것부터 점유합니다.
이제 평균대기시간(Average Waiting Time)을 계산하면 (6+0+16+18+1)/5 = 8.2 msec으로 나타낼 수 있습니다.
이 우선순위 방식의 문제점은 기아(Starvation) 문제가 발생할 수 있습니다.
기아라는 것은 어떤 특정 프로세스가 굉장히 오랫동안 CPU의 점유를 받지 못하는 상태를 뜻합니다.
실제 컴퓨터 환경에서 새로운 프로세스가 준비 큐(Ready Queue)에 들어오기 때문에 새로운 프로세스가 우선순위가 높다면 낮은 우선순위의 프로세스는 계속 기다릴 수 밖에 없습니다.
이를 해결하는 방법은 에이징(Aging)이 있습니다.
에이징이라는 것은 말 그대로 준비 큐(Ready Queue)에 대기하고 있는 동안 일정 시간이 지나면 프로세스의 우선순위를 높여주는 것입니다.
그러면 대기하는 시간동안 우선순위가 높아져 점유할 가능성이 높아질 것입니다.
다단계 큐(Multilevel Queue) 스케줄링
우선순위 스케줄링의 발전된 형태입니다.
우선순위 별로 준비 큐를 여러 개 사용하는 스케줄링 방식입니다.
다단계 큐 스케줄링 하에서는 우선순위가 가장 높은 큐에 있는 프로세스들을 먼저 처리하고, 우선순위가 가장 높은 큐가 비어있으면 그 다음 우선순위 큐에 있는 프로세스들을 처리합니다.
큐를 여러 개 두면 프로세스 유형별로 우선순위를 구분하여 실행하는 것이 편리해집니다.
또한, 큐에 따라 여러 기준을 들 수 있습니다. 큐마다 CPU 시간을 다르게 줄 수도, 다른 스케줄링 방식을 사용할 수 있습니다.
다단계 피드백 큐(Multilevel Feedback Queue) 스케줄링
다단계 큐 스케줄링의 발전된 형태입니다.
다단계 큐 스케줄링 방식은 프로세스들이 큐 사이를 이동할 수 없습니다. 이러면 우선순위가 낮은 프로세스는 계속 미뤄질 가능성이 있기 때문에 기아 현상이 발생할 수 있습니다.
이를 방지하기 위해 다단계 피드백 큐 스케줄링은 프로세스들이 큐 사이를 이동할 수 있다는 점입니다.
다단계 피드백 큐가 동작하는 방식을 간단하게 설명해 보겠습니다.
프로세스들은 맨 위의 큐에서 CPU 점유하기를 대기합니다.
작업을 진행하다가, 이 큐에서 기다리는 시간이 너무 오래 걸린다면 아래의 큐로 프로세스를 옮깁니다.
이와 같은 방식으로 대기하는 시간을 조정할 수 있습니다.
만약, 우선순위순으로 큐를 사용하는 상황에서 우선순위가 낮은 아래의 큐에 있는 프로세스에서 기아 상태가 발생하면, 우선순위가 높은 큐로 옮길 수 있습니다.
대부분의 운영체제는 여러 개의 큐를 사용하고 각 큐마다 다른 스케줄링 방식을 사용합니다.
이상으로 CPU 스케줄링 알고리즘에 대해서 간단히 알아봤습니다.
참고
- KOCW - 운영체제, 양희재 교수님
- 혼자 공부하는 컴퓨터구조 + 운영체제
