CPU 스케줄링 알고리즘 총정리
1️⃣ CPU Scheduling Performance Metrics and Non-Preemptive Algorithms
2️⃣ Preemptive Scheduling and Expansion Algorithms
3️⃣ CPU Scheduling Performance Comparison Practice
1️⃣ CPU Scheduling Performance Metrics and Non-Preemptive Algorithms
이번 주의 주제는 CPU 스케줄링의 성능과 확장이다.
지난 시간에는 CPU 스케줄링의 개념에 대해 살펴보며, 여러 프로세스가 동시에 실행을 요청하는 상황에서 운영체제가 어떤 프로세스에게 CPU를 먼저 할당할 것인지를 결정하는 문제, 즉 CPU 스케줄링의 필요성에 대해 배웠다.
이번 시간에는 이런 개념을 바탕으로 실제로 CPU를 어떤 방식으로 할당할지, CPU 스케줄링의 알고리즘에 대해 공부한다. 또한 CPU 스케줄링의 성능을 평가하기 위한 대기시간, 반환시간, 응답시간과 같은 성능 지표도 살펴보고, 각 스케줄링 방식이 시스템에서의 성능에 어떤 차이를 만드는지 분석해볼 것이다.
대용량 영상 인코딩 작업이 실행되고 있는 동안 메시지 알람이 뜨고 웹페이지 클릭에 바로 반응하지 않는다면 어떻게 될까? 사용자는 컴퓨터가 느리다거나 버벅거린다고 느낄 것이다. 그렇다면 이런 현상이 일어나는 이유는 무엇일까?
CPU는 한 순간에 하나의 작업만 처리한다. 하지만 실제로는 음악을 재생하고, 웹 브라우저를 열고, 메신저를 사용하는 것처럼 여러 프로그램이 동시에 CPU를 요구한다. 이럴 때 각 작업은 일정한 순서에 따라 CPU를 사용하게 되며, 이 실행 순서에 따라 사용자가 느끼는 시스템의 반응 속도도 달라진다. 따라서 여러 작업이 CPU를 요구할 때 운영체제가 어떤 기준으로 실행 순서를 결정하는지 알아볼 것이다.
또 다른 상황을 생각해보자. 대용량 작업 1개와 짧은 작업 10개가 동시에 실행 요청을 한다면, 운영체제는 큰 작업을 먼저 처리해야 할까, 아니면 작은 작업들을 먼저 처리해야 할까? 어떤 선택을 하느냐에 따라 전체 시스템의 응답 속도와 사용자가 느끼는 반응 속도가 달라질 수 있다.
운영체제는 어떤 기준으로 이러한 실행 순서를 결정하는 것일까? 오늘 수업에서는 CPU 스케줄링 알고리즘을 통해 지금까지 제기한 문제들의 답을 찾아보도록 하자.
우리가 어떤 시스템을 사용할 때 "이 컴퓨터 빠르다", "이 시스템 느리다"라는 표현을 자주 사용한다. 그렇다면 여기서 말하는 "빠르다"는 것은 정확히 무엇을 의미하는 걸까?
CPU가 아주 바쁘게 일한다는 뜻일까? 아니면 단위 시간 동안 많은 작업이 처리된다는 것을 의미하는 걸까? 또 사용자 입장에서는 클릭하면 즉시 반응이 오는 것을 빠르다고 느끼는 걸까? 혹은 여러 작업이 있을 때 특정 작업만 계속 실행되는 것이 아니라, 모든 작업이 골고루 처리되는 것을 빠르다고 느끼는 걸까?
이처럼 시스템의 성능을 평가하는 기준은 하나만 있는 것이 아니다. 그래서 CPU 스케줄링의 성능은 여러 가지 기준을 통해 평가하게 되며, 어떤 지표를 중요하게 보느냐에 따라 좋은 알고리즘의 기준도 달라지게 된다.
CPU 스케줄링의 성능을 볼 때 보통 시스템 관점과 사용자 관점으로 나뉜다.
시스템 관점에서는 CPU가 얼마나 효율적으로 사용되는지가 중요하다. 대표적인 지표는 CPU 사용률(CPU Utilization)로, CPU가 얼마나 바쁘게 사용되는지를 0%~100%로 표현한다. 또 하나는 처리량(Throughput)으로, 단위 시간 동안 얼마나 많은 작업이 완료되었는지를 나타낸다.
반면 사용자 관점에서는 조금 다른 기준이 적용된다. 사용자는 시스템이 얼마나 바쁘게 돌아가는지보다 자신이 얼마나 오래 기다리는지가 더 중요하다. 그래서 사용자 관점에서는 이 기다림을 어떻게 정의할 것인지가 중요한 기준이 된다.
그림을 보면서 CPU 스케줄링에서 사용하는 시간 지표를 알아보자. 프로세스 하나가 실행되는 과정을 살펴보면 다음과 같다.
먼저 작업이 시스템에 도착한다. 하지만 도착했다고 해서 바로 작업이 시작되지는 않는다. 실행 시작까지 일정 시간 대기를 하게 된다. 그 다음 실행이 시작되면 프로그램이 실제로 CPU를 사용하면서 작업을 수행하게 된다. 그리고 작업이 완료되면 프로세스의 실행이 종료된다.
이 과정에서 반환시간, 대기시간, 응답시간이라는 세 가지 시간 지표가 발생하게 되는데, 다음에서 더 자세히 알아보도록 하자.
사용자 체감과 관련된 시간 지표
세 가지 시간 지표는 모두 사용자가 느끼는 시스템 성능과 직접적인 연관이 있다.
반환시간(Turnaround Time) 은 작업이 요청되는 "도착" 시점부터 완료되는 "실행 종료"까지 걸리는 전체 시간을 의미한다.
대기시간(Waiting Time) 은 프로세스가 준비 큐에 들어와서 CPU를 할당받기 전까지 기다리는 시간을 의미한다.
응답시간(Response Time) 은 작업을 요청한 후 첫 번째 실행 또는 출력이 나타날 때까지 걸리는 시간을 의미한다.
이 세 가지 시간 지표는 사용자가 느끼는 시스템 성능과 직접적인 연관이 있는 지표라고 할 수 있다.
대기시간과 반환시간은 어떻게 계산될까?
프로세스 P1, P2, P3가 동시에 도착하고, P1 → P2 → P3 순으로 실행된다고 가정해보자.
먼저 P1이 CPU를 할당받아 실행된다. 도착하자마자 바로 실행되기 때문에 P1의 대기시간은 0이 된다. 그동안 P2와 P3는 CPU를 할당받지 못하고 기다리게 된다.
P1의 실행이 끝나면 P2가 CPU를 할당받아 실행된다. P2는 P1이 실행되는 시간 동안 기다렸기 때문에 대기시간이 발생한다.
마지막으로 실행되는 P3는 P1과 P2가 모두 실행되는 동안 계속 기다려야 한다. 그렇기 때문에 P3의 대기시간이 가장 길어지는 것을 알 수 있다.
이처럼 스케줄링 순서에 따라 각 프로세스의 대기시간과 반환시간이 달라질 수 있다. 즉, 어떤 순서로 프로세스를 실행하느냐에 따라 전체 시스템의 성능도 달라질 수 있다는 의미이기도 하다.
CPU 스케줄링 알고리즘: "FCFS" 비선점 알고리즘
그래서 운영체제는 여러 프로세스 중에서 무엇을 먼저 실행할지 결정하는 규칙, 즉 CPU 스케줄링 알고리즘을 적용하게 된다. 이 알고리즘은 크게 선점 방식과 비선점 방식으로 나뉜다.
먼저 비선점 방식의 알고리즘부터 살펴보자. 그 중에서도 가장 기본적이고 단순한 방식인 FCFS(First Come, First Served), 즉 선입 선처리 스케줄링이다. 이름 그대로 먼저 도착한 프로세스를 먼저 실행하는 방식으로, 도착하는 순서가 곧 실행 순서가 된다. 한 번 CPU를 할당받은 프로세스는 자신의 작업이 끝날 때까지 계속 실행되기 때문에 비선점 방식에 해당한다. 구조가 단순하고 이해하기 쉬워 가장 기본적인 스케줄링 방식으로 꼽힌다.
FCFS 선입선처리 스케줄링의 구조
준비 큐에서 어떻게 동작하는지 자세히 살펴보자. 새로운 프로세스가 도착하면 준비 큐의 맨 마지막 꼬리에 추가된다. CPU는 준비 큐의 맨 앞에 있는 프로세스부터 실행을 시작하며, 먼저 들어온 프로세스를 먼저 처리한다. 나중에 들어온 프로세스는 앞의 프로세스가 끝날 때까지 기다리게 된다. FCFS 선입선처리 스케줄링은 말 그대로 먼저 들어오면 먼저 처리하는 방식으로 동작한다.
FCFS 선입선처리 스케줄링 예제1
다섯 개의 프로세스가 있다고 가정해보자. 각 프로세스에는 도착시간과 실행시간이 주어진다. 도착시간은 프로세스가 준비 큐에 도착하는 시간을 의미하고, 실행시간은 프로세스가 CPU에서 처리되기 위해 필요한 시간을 의미한다.
FCFS 스케줄링은 먼저 도착한 프로세스를 실행하는 비선점 방식이기 때문에, 한 번 CPU를 할당받은 프로세스는 작업이 끝날 때까지 계속 실행된다. 중간에 다른 프로세스에게 CPU를 빼앗기지 않는다는 의미이다. 따라서 P1이 먼저 실행되고 실행시간이 모두 끝난 후에 P2가 시작되며, 이후 같은 방식으로 P3, P4, P5 순으로 실행된다. 이러한 실행 순서는 간트 차트(Gantt Chart) 로 표시된다.
간트 차트를 참조한 예제1의 반환시간, 대기시간 계산
간트 차트를 통해 각 프로세스가 언제 실행을 시작하고 언제 끝나는지를 확인하면 반환시간과 대기시간을 계산할 수 있다.
P1은 도착시간이 0이고 실행시간이 10이므로 10초에 실행이 끝난다. 반환시간은 10 - 0 = 10이 된다. 도착하자마자 바로 실행되었기 때문에 대기시간은 0이다.
P2는 도착시간이 1이고 38초에 실행이 끝난다. 반환시간은 38 - 1 = 37이 된다. 10초 시점에서 실행이 시작되었기 때문에 대기시간은 10 - 1 = 9가 된다.
P3는 도착시간이 2이고 44초에 실행이 끝난다. 반환시간은 44 - 2 = 42가 된다. 38초 시점에서 실행이 시작되었기 때문에 대기시간은 38 - 2 = 36이 된다.
이와 같은 방식으로 P4, P5도 실행 시작 시점과 도착시간을 이용해 계산하면 된다. 이를 정리하면 아래와 같다.
선입선처리 스케줄링 예제 2 - 반환시간, 대기시간 계산
도착시간과 실행시간을 기준으로 반환시간과 대기시간을 계산해보자.
P3는 도착시간이 0이고 실행시간이 6이다. 간트 차트를 참조하면 6초에 실행이 끝나므로 반환시간은 6 - 0 = 6이 된다. 도착하자마자 바로 실행되었기 때문에 대기시간은 0이다.
P1은 도착시간이 1이고 16초에 실행이 끝난다. 반환시간은 16 - 1 = 15가 된다. 6초부터 실행되었기 때문에 대기시간은 6 - 1 = 5가 된다.
P4는 도착시간이 2이고 20초에 실행이 끝난다. 반환시간은 20 - 2 = 18이 된다. 16초부터 실행되었기 때문에 대기시간은 16 - 2 = 14가 된다.
이와 같은 방식으로 P5, P2도 간트 차트의 실행 시작 시점과 도착시간을 이용해 계산하면 된다.
예제 1과 비교해보면 평균 반환시간이 38.4, 평균 대기시간이 26이었다. 예제 2에서는 실행시간이 짧은 작업이 먼저 실행되었기 때문에 뒤에 있는 프로세스들의 대기시간이 상대적으로 줄어들었고, 결과적으로 평균 반환시간과 평균 대기시간이 모두 줄어들었음을 확인할 수 있다.
FCFS의 특징
도착 순서대로 처리하는 방식이기 때문에 구현이 매우 단순하다. 도착 순서가 그대로 실행 순서가 되기 때문에 실행 순서가 미리 결정된다는 것도 특징이다.
하지만 문제도 있다. 앞쪽에 실행시간이 긴 작업이 오게 되면 뒤에 있는 짧은 작업들이 오랫동안 기다려야 한다. 예제 1에서 확인했던 것처럼 실행시간이 긴 작업 하나만으로도 전체 대기시간을 크게 증가시키게 된다. 결과적으로 평균 대기시간과 응답시간이 늘어나는 문제가 발생한다.
콘보이 현상(Convoy Effect)
이러한 현상을 콘보이 현상이라고 한다. 실행시간이 긴 CPU 작업 하나 때문에 여러 짧은 작업들이 오래 기다리게 되는 현상이다. 긴 작업이 앞에 있으면 뒤에 있는 짧은 작업들이 빨리 끝날 수 있음에도 불구하고 계속 대기해야 하는 상황이 발생한다. 그 결과 평균 대기시간이 증가하고 사용자가 느끼는 응답시간도 늘어나게 된다.
이처럼 선입선처리 스케줄링은 사용자의 반응이 중요한 대화형 시스템에는 부적합하다고 볼 수 있다.
CPU 스케줄링 알고리즘: "SJF" 비선점 알고리즘
FCFS를 살펴보면서 긴 작업이 앞에 오면 평균 대기시간이 크게 증가하는 문제점을 발견하였다. 그렇다면 이 평균 대기시간을 줄일 수 있는 방법은 없을까?
있다. 바로 SJF(Shortest Job First), 최단 작업 우선 스케줄링이다. 실행시간이 가장 짧은 작업을 먼저 실행하는 방식이다. SJF 스케줄링도 FCFS처럼 한 번 실행하면 끝날 때까지 계속 실행하는 비선점 방식으로 동작한다.
왜 짧은 작업을 먼저 처리하면 좋을까?
짧은 작업을 먼저 처리하면 작업들이 빠르게 완료되기 시작한다. 그 결과 뒤에 있는 작업들의 대기시간이 줄어들게 되고, 결과적으로 전체 평균 대기시간이 감소하게 된다. 또한 사용자 입장에서는 작업이 더 빨리 처리되기 때문에 응답시간도 개선된다.
즉, SJF 스케줄링은 대기시간이 짧은 작업부터 먼저 완료시킴으로써 전체적인 평균 대기시간을 줄이는 데 효과적인 스케줄링 방식이라고 할 수 있다.
SJF 스케줄링 예제
간단한 예제를 통해 SJF 스케줄링을 살펴보자. 실행시간이 5, 11, 7, 3인 네 개의 작업이 있다고 가정하자.
도착 순서대로 실행하면 첫 번째 작업은 바로 실행되기 때문에 대기시간이 0이다. 두 번째 작업인 11은 첫 번째 작업이 끝날 때까지 기다려야 하므로 대기시간이 5이다. 세 번째 작업은 앞의 두 작업이 끝날 때까지 기다려야 하므로 대기시간이 5 + 11 = 16이 된다. 마지막 작업인 3은 앞의 세 작업이 모두 끝날 때까지 기다려야 하므로 5 + 11 + 7 = 23만큼 기다리게 된다. 이때 전체 대기시간의 합은 44가 된다.
그렇다면 실행 순서를 바꾸면 어떻게 될까? 아래 표를 보면 실행시간이 짧은 작업을 먼저 실행할수록 전체 대기시간의 합이 점점 줄어드는 것을 확인할 수 있다.
이처럼 실행시간이 가장 짧은 작업부터 실행하는 3 → 5 → 7 → 11 순서에서 전체 대기시간의 합이 26으로 가장 작아지는 것을 볼 수 있다. 즉, 짧은 작업을 먼저 실행할수록 전체 대기시간을 줄일 수 있으며, 이 아이디어를 실제 스케줄링에 적용한 것이 바로 SJF 스케줄링이다.
SJF 스케줄링 예제 - 앞선 프로세스 예제 적용
앞에서 사용했던 프로세스 예제를 SJF 방식으로 적용해보자. 각 프로세스의 도착시간과 실행시간은 아래와 같다.
P1이 0초에 도착했기 때문에 초기에는 P1만 존재하므로 P1이 먼저 실행된다. P1이 실행되는 동안 P2, P3, P4, P5는 모두 준비 큐에 도착하게 된다. P1이 끝나는 시점에서 준비 큐에 있는 프로세스들의 실행시간을 비교하면 P4(4) → P3(6) → P5(14) → P2(28) 순으로 실행시간이 커지는 것을 볼 수 있다. SJF 방식에서는 실행시간이 가장 짧은 P4가 먼저 실행된다. 이후에도 같은 방식으로 준비 큐에서 가장 짧은 작업을 선택하기 때문에 최종 실행 순서는 P1 → P4 → P3 → P5 → P2가 된다. 이를 간트 차트로 나타내면 아래와 같다.
간트 차트를 참고한 반환시간, 대기시간 계산
간트 차트를 참고하여 반환시간과 대기시간을 계산해보자.
P1은 0초에 도착해서 10초에 끝나므로 반환시간은 10 - 0 = 10, 대기시간은 0이다. P4는 3초에 도착해서 14초에 끝나므로 반환시간은 14 - 3 = 11, 대기시간은 10 - 3 = 7이다. P3는 2초에 도착해서 20초에 끝나므로 반환시간은 20 - 2 = 18, 대기시간은 14 - 2 = 12이다.
이와 같은 방식으로 P5, P2도 계산하면 아래와 같다.
이처럼 실행시간이 짧은 작업을 먼저 처리하면 평균 대기시간을 줄일 수 있다는 것을 이 계산 결과를 통해 확인할 수 있다.
SJF 스케줄링의 성능 특성
이러한 결과를 바탕으로 SJF 스케줄링의 성능 특성을 정리하면 다음과 같다.
SJF는 실행시간이 짧은 작업을 먼저 처리하기 때문에 전체 대기시간이 줄어들며, 평균 대기시간을 최소화할 수 있다. 이처럼 SJF 스케줄링은 짧은 작업에 유리한 구조를 가지고 있다.
하지만 문제점도 존재한다. SJF를 적용하려면 각 작업의 실행시간을 미리 예측할 수 있어야 한다. 또한 실행시간이 긴 작업은 짧은 작업들 뒤로 계속 밀리는 문제가 발생할 수 있다. 이런 경우 특정 프로세스가 영원히 실행되지 못하는 기아 상태(Starvation) 가 발생할 가능성도 있다.
기아 상태(Starvation)
기아 상태란 특정 프로세스가 오랫동안 CPU를 할당받지 못하는 현상을 의미한다. SJF에서는 특히 실행시간이 긴 작업에서 이런 문제가 발생한다.
짧은 작업이 계속 들어오게 되면 스케줄러는 짧은 작업을 먼저 선택하게 되고, 그 결과 실행시간이 긴 작업은 계속 뒤로 밀리면서 실행되지 못하는 상황이 발생할 수 있다. 이렇게 되면 스케줄링의 공정성이 떨어지고, 특정 작업이 지나치게 오랫동안 기다리는 문제가 생기게 된다.
CPU 스케줄링 알고리즘: "HRN" 비선점 알고리즘
앞서 살펴본 SJF는 실행시간이 짧은 작업을 먼저 선택하는 방식이었다. 반면 HRN(Highest Response Ratio Next), 최고 응답비율 우선 스케줄링은 작업을 선택할 때 실행시간만 보는 것이 아니라, 얼마나 오래 기다렸는지도 함께 고려하는 방식이다.
각 작업에 대한 응답 비율(Response Ratio) 값을 계산하고, 그 값이 가장 큰 작업을 선택해서 실행하게 된다. HRN 스케줄링 역시 한 번 시작되면 끝날 때까지 진행되는 비선점 방식이다.
HRN 응답 비율 계산 방법
응답 비율은 대기시간과 실행시간의 합을 실행시간으로 나눈 값이다.
응답 비율 = (대기시간 + 실행시간) / 실행시간
이를 정리하면 1 + (대기시간 / 실행시간) 의 형태로도 표현할 수 있다.
여기서 각 용어를 정리하면 다음과 같다. 대기시간(Waiting Time)은 준비 큐에서 기다린 시간을 의미하고, 실행시간(Burst Time)은 CPU를 실제로 사용하는 시간을 의미한다. 그리고 반환시간(Turnaround Time)은 대기시간과 실행시간의 합이 된다.
참고로 응답 비율(Response Ratio)과 응답시간(Response Time)은 다른 개념이다. 응답시간은 작업 요청 후 첫 응답이 오기까지 걸리는 시간 지표이고, 응답 비율은 HRN 스케줄링에서 실행 순서를 결정하기 위해 계산하는 값이다.
HRN 스케줄링에서 기아 상태가 완화되는 이유
HRN 스케줄링에서는 대기시간이 길어질수록 응답 비율이 증가하게 된다. 응답 비율 공식을 떠올려보면 대기시간이 커질수록 분자가 커지기 때문에 응답 비율도 함께 높아지는 구조이다.
따라서 실행시간이 긴 작업이더라도 오랫동안 기다리면 응답 비율이 점점 커지게 되고, 결국 CPU를 할당받을 가능성이 높아지게 된다. 즉 HRN 스케줄링에서는 오래 기다리는 작업이 점점 더 유리해지는 구조이기 때문에, SJF에서 발생하는 기아 상태를 완화할 수 있다.
HRN 스케줄링 예제
HRN 스케줄링의 실행 예제를 살펴보자. 이번 예제에서는 HRN의 계산 결과가 SJF와 동일한 실행 순서를 만들어내고 있다. 일반적으로 대기시간이 길어질수록 우선순위가 올라가기 때문에 SJF와 다른 결과가 나올 수 있지만, 여기서는 우연히 동일한 실행 순서가 만들어졌다는 점을 알아두자.
P1은 0초에 도착하여 가장 먼저 실행되며 0에서 10까지 실행된다. 10초 시점이 되면 준비 큐에는 P2, P3, P4, P5가 존재하는데, HRN에서는 이 시점에서 각 프로세스의 응답 비율을 계산하여 가장 큰 값을 가진 작업을 선택하게 된다.
예를 들어 P4의 응답 비율을 계산해보면, 대기시간은 10 - 3 = 7이고 실행시간은 4이므로 응답 비율은 (7 + 4) / 4 = 2.75가 된다. 같은 방식으로 나머지 프로세스의 응답 비율을 계산하면 아래와 같다.
이 중 응답 비율이 가장 큰 P4가 선택되어 10 ~ 14초까지 실행된다. 이후에도 같은 방식으로 응답 비율을 계산하여 작업을 선택하게 되며, 최종 실행 순서는 간트 차트와 같이 P1 → P4 → P3 → P5 → P2가 된다.
HRN 스케줄링 - 반환시간, 대기시간 계산
간트 차트를 이용해 반환시간과 대기시간을 계산해보자.
P1은 0초에 도착해서 10초에 실행이 끝나므로 반환시간은 10, 대기시간은 0이다. P4는 3초에 도착해서 14초에 실행이 끝나므로 반환시간은 14 - 3 = 11, 대기시간은 10 - 3 = 7이다. 이와 같은 방식으로 나머지 프로세스를 계산하면 아래와 같다.
평균 반환시간은 (10+61+18+11+30)/5 = 26, 평균 대기시간은 (0+33+12+7+16)/5 = 13.6으로 SJF 스케줄링과 동일한 결과가 나오는 것을 확인할 수 있다.
HRN 스케줄링의 특징
앞서 계산된 결과를 통해 HRN 스케줄링의 특징을 정리할 수 있다.
먼저 장점으로는 짧은 작업이 비교적 먼저 실행되는 경향이 있어 평균 대기시간을 줄일 수 있다. 또한 대기시간이 길어질수록 응답 비율이 증가하기 때문에 오래 기다린 작업도 결국 CPU를 할당받게 되어 SJF에서 발생하는 기아 상태를 완화할 수 있다.
하지만 단점도 존재한다. HRN 스케줄링도 응답 비율을 계산하기 위해 실행시간 정보를 미리 알아야 하기 때문에 실행시간 예측이 필요하다. 또한 매 시점마다 응답 비율을 계산해야 하기 때문에 SJF 스케줄링보다 계산 복잡도가 증가한다는 특징도 있다.
비선점 스케줄링 알고리즘 특징 정리
지금까지 살펴본 비선점 스케줄링 알고리즘의 특징을 표로 정리하면 다음과 같다.
2️⃣ Preemptive Scheduling and Expansion Algorithms
선점 스케줄링과 확장된 알고리즘
앞서 살펴본 비선점 방식의 스케줄링에는 한계가 있다. 실행시간이 긴 작업이 먼저 실행되면, 그 뒤에 짧고 급한 작업이 도착하더라도 기다려야 한다. 이렇게 되면 응답시간이 늦어질 수 있다. 특히 사용자와 상호작용하는 대화형 시스템에서는 더욱 적합하지 않다. 사용자가 체감하는 시스템 성능은 얼마나 빠르게 응답하느냐에 따라 크게 영향을 받기 때문이다.
이런 문제를 해결하기 위해서는 실행 중인 작업을 중단하고 다른 작업을 먼저 실행할 수 있는 방식이 필요하다.
선점 스케줄링이란?
이러한 비선점 방식의 한계를 해결하기 위해 등장한 방식이 바로 선점 스케줄링이다. 이는 실행 중인 프로세스를 강제로 중단하고 다른 작업을 먼저 실행할 수 있는 방식이다. 더 중요한 작업이 도착하면 현재 실행 중인 작업을 중단하고 그 작업을 먼저 실행할 수 있게 된다. 이렇게 되면 응답시간을 줄일 수 있기 때문에 대화형 시스템처럼 빠른 응답이 중요한 환경에 적합한 스케줄링 방식이다.
선점 스케줄링의 단점
하지만 선점 스케줄링에도 단점이 존재한다.
먼저 문맥 교환이 자주 발생할 수 있다. 프로세스를 중단하고 다른 프로세스를 시작하려면 CPU 상태를 저장하고 다시 복원해야 하는데, 이 과정에서 추가적인 오버헤드가 발생하게 된다. 또한 선점이 너무 자주 발생하게 되면 CPU를 실제 작업에 사용하는 시간이 줄어들어 전체 성능이 떨어질 수 있다. 그리고 선점 스케줄링은 비선점 방식보다 스케줄링 정책이 더 복잡해지는 특징도 있다.
따라서 선점 스케줄링은 응답성을 높이는 장점을 가지고 있지만, 과도하게 사용하면 오히려 성능을 떨어뜨릴 수 있다는 점도 알아두어야 한다.
CPU 스케줄링 알고리즘: "SRTF" 선점 알고리즘
대표적인 선점 스케줄링 알고리즘 중 하나는 SRTF(Shortest Remaining Time First), 최단 잔여시간 우선 스케줄링이다. SRTF 스케줄링은 남은 실행시간이 가장 짧은 작업을 선택하는 방식으로, 현재 실행 중인 작업이 있더라도 새로운 작업이 도착했을 때 그 작업의 남은 실행시간이 더 짧다면 현재 작업을 중단하고 새로운 작업을 먼저 실행한다. 이러한 이유로 SRTF 스케줄링은 SJF의 선점 버전이라고 할 수 있다.
SRTF 스케줄링의 성능 특성
SRTF 스케줄링의 성능 특성을 정리하면 다음과 같다.
먼저 평균 대기시간이 매우 작다. 항상 남은 실행시간이 가장 짧은 작업을 먼저 실행하기 때문에 짧은 작업을 오래 기다리지 않고 빠르게 처리할 수 있고, 그 결과 평균 대기시간이 작아지는 경향이 있다. 또한 짧은 작업이 도착하면 현재 실행 중인 작업보다 남은 시간이 짧은 경우 즉시 CPU를 할당받을 수 있기 때문에 응답시간도 우수하다.
하지만 단점도 존재한다. SJF와 마찬가지로 짧은 작업이 계속 도착하면 실행시간이 긴 작업은 뒤로 밀릴 수 있기 때문에 기아 상태가 발생할 수 있다. 또한 새로운 작업이 도착할 때마다 현재 실행 중인 작업과 남은 시간을 비교해야 하기 때문에 문맥 교환이 증가할 수 있다는 특징도 있다.
SRTF 스케줄링 예제
SRTF 스케줄링의 예를 간트 차트와 함께 살펴보자.
0초에는 P1만 존재하므로 P1이 실행을 시작한다. 1초에 P2가 도착하지만 현재 실행 중인 P1의 남은 시간은 9이고 P2의 실행시간은 28이므로, P1의 남은 실행시간이 더 짧아 P1이 계속 실행된다.
2초에 P3가 도착하면 P1의 남은 실행시간은 8이 된다. P3의 실행시간은 6으로 P1보다 짧기 때문에 P1이 중단되고 P3가 실행된다. 이것이 바로 선점이 발생하는 순간이다.
3초에 P4가 도착하면 P3의 남은 실행시간은 5가 된다. P4의 실행시간은 4로 P3보다 짧기 때문에 P3가 중단되고 P4가 실행된다.
이러한 과정을 반복하면 간트 차트와 같이 P1 → P3 → P4 → P3 → P1 → P5 → P2 순서로 실행된다.
SRTF 스케줄링 - 반환시간, 대기시간 계산
간트 차트를 이용해 반환시간과 대기시간을 계산해보자.
P1은 0초에 도착해서 20초에 실행이 끝나므로 반환시간은 20 - 0 = 20이 된다. P1은 2초에 선점당한 뒤 12초까지 기다리게 되므로 대기시간은 12 - 2 = 10이 된다. 이와 같은 방식으로 나머지 프로세스를 계산하면 아래와 같다.
평균 반환시간은 (20+61+10+4+30)/5 = 25, 평균 대기시간은 (10+33+4+0+16)/5 = 12.6이 된다.
CPU 스케줄링 알고리즘: "우선순위 스케줄링" 선점 알고리즘
우선순위 스케줄링은 각 작업에 우선순위를 부여해서 우선순위가 높은 작업을 먼저 실행하는 방식이다. 준비 큐에 여러 작업이 있을 때 우선순위가 가장 높은 작업이 CPU를 먼저 할당받게 된다.
선점 방식에서는 현재 실행 중인 작업이 있더라도 더 높은 우선순위를 가진 작업이 도착하면 현재 작업을 중단하고 새로운 작업이 CPU를 사용하게 된다.
하지만 이 방식에서는 우선순위가 낮은 작업이 계속해서 CPU를 할당받지 못하고 오랫동안 실행되지 못하는 기아 상태가 발생할 수 있다. 이 문제를 해결하기 위한 방법으로 에이징(Aging) 기법이 있는데, 이는 뒤에서 자세히 살펴볼 예정이다.
우선순위 스케줄링 - 선점 방식과 비선점 방식 비교
각 프로세스의 도착시간, 실행시간, 우선순위는 아래와 같다. 여기서 숫자가 클수록 우선순위가 높다고 가정한다.
선점 방식에서는 0초에 P1이 실행을 시작한다. 1초에 P2가 도착하지만 P1의 우선순위(3)가 P2의 우선순위(2)보다 높기 때문에 P1이 계속 실행된다. 2초에 P3가 도착하면 P3의 우선순위(4)가 가장 높기 때문에 현재 실행 중인 P1이 중단되고 P3가 실행된다. 3초에 P4가 도착하지만 우선순위가 1로 가장 낮기 때문에 P3가 계속 실행된다. P3가 끝나면 준비 큐에 남아있는 P1, P2, P4, P5 중 우선순위가 가장 높은 P1이 다시 실행된다. 이처럼 선점 방식에서는 더 높은 우선순위 작업이 도착할 때마다 현재 작업이 중단되고 새로운 작업이 CPU를 할당받는다.
비선점 방식에서는 현재 실행 중인 작업이 있으면 더 높은 우선순위 작업이 도착하더라도 중간에 교체되지 않고 현재 작업이 끝난 뒤에 다음 작업을 선택하게 된다. 따라서 P1이 먼저 시작해서 끝날 때까지 계속 실행되는 것을 볼 수 있다.
이처럼 선점 방식과 비선점 방식에서 실행 순서가 서로 다르게 나타나는 것을 간트 차트를 통해 확인할 수 있다.
선점 우선순위 스케줄링 - 반환시간, 대기시간 계산
간트 차트를 이용해 반환시간과 대기시간을 계산해보자.
P1은 0초에 도착해서 16초에 끝나므로 반환시간은 16 - 0 = 16이 된다. 중간에 선점되었다가 다시 실행되기 때문에 대기시간은 8 - 2 = 6이 된다. P3는 2초에 도착해서 8초에 끝나므로 반환시간은 8 - 2 = 6, 대기시간은 2 - 2 = 0이 된다. 이와 같은 방식으로 나머지 프로세스를 계산하면 아래와 같다. 평균 반환시간은 (16+43+6+59+54)/5 = 35.6, 평균 대기시간은 (6+15+0+55+40)/5 = 23.2가 된다.
비선점 우선순위 스케줄링 - 반환시간, 대기시간 계산
비선점 방식에서는 한 번 시작된 작업이 끝까지 실행되기 때문에 선점 방식과는 계산 결과가 달라진다.
P1은 도착하자마자 실행되어 10초에 끝나므로 반환시간은 10, 대기시간은 0이다. P3는 2초에 도착했지만 바로 실행되지 못하고 10초부터 실행되었기 때문에 반환시간은 16 - 2 = 14, 대기시간은 10 - 2 = 8이 된다. 이와 같은 방식으로 나머지 프로세스를 계산하면 아래와 같다.
선점 방식과 비선점 방식을 비교해보면 아래와 같다.
선점 방식이 비선점 방식보다 평균 반환시간과 대기시간이 조금 더 작게 나타나는 것을 볼 수 있다. 다만 이는 항상 적용되는 것은 아니며, 작업의 도착시간과 우선순위 구성에 따라 결과는 달라질 수 있다.
에이징(Aging) 기법
우선순위 스케줄링의 기아 현상을 해결하기 위해 사용하는 방법이 바로 에이징(Aging) 기법이다. 오랫동안 기다리는 프로세스의 우선순위를 점진적으로 높여주는 방식으로, 우선순위가 낮은 작업이더라도 대기시간이 길어지면 점점 우선순위가 올라가게 되고 결국에는 CPU를 할당받을 수 있게 된다. 즉 낮은 우선순위의 작업이 영구적으로 CPU를 할당받지 못하는 문제를 방지하는 방법이다. 이런 방식으로 우선순위 스케줄링에서 발생할 수 있는 기아 문제를 효과적으로 완화할 수 있다.
에이징의 동작 원리
에이징은 프로세스의 대기시간이 증가할수록 우선순위를 일정 간격으로 높여주는 방식이다. 처음에는 우선순위가 낮더라도 시간이 지날수록 점점 높은 우선순위를 확보하게 되어 결과적으로 기아 상태를 방지할 수 있게 된다.
이는 시스템 전체의 공정성을 향상시키고, 특정 작업이 오랫동안 기다리는 응답 왜곡 현상을 완화시킨다. 결과적으로 시스템 안정성을 높이는 효과가 있다. 이를 그래프로 나타내면 시간이 지날수록 우선순위가 점진적으로 증가하는 모습을 확인할 수 있다.
CPU 스케줄링 알고리즘: "라운드 로빈(Round Robin)" 선점 알고리즘
라운드 로빈 스케줄링은 각 프로세스에 일정한 시간 단위를 할당해서 CPU를 순환 방식으로 사용하는 방식이다. 이때 사용하는 시간 단위를 타임 퀀텀(Time Quantum) 이라고 한다. 각 프로세스는 정해진 시간 동안 CPU를 사용하고, 그 시간이 끝나면 CPU를 반납한 뒤 준비 큐의 맨 뒤로 이동하게 된다. 모든 프로세스가 차례대로 CPU를 사용하기 때문에 CPU를 공평하게 분배할 수 있는 방식이다.
여기서 타임 퀀텀의 크기는 시스템 성능에 매우 중요한 영향을 미친다. 타임 퀀텀이 너무 작으면 프로세스 전환이 자주 발생하여 문맥 교환의 오버헤드가 증가한다. 반대로 너무 커지면 프로세스가 오랫동안 CPU를 독점하게 되어 선입선처리인 FCFS 방식과 유사하게 동작하게 된다.
라운드 로빈 스케줄링의 특징
라운드 로빈 스케줄링의 특징을 정리하면 다음과 같다.
먼저 응답시간이 우수하다. 모든 프로세스가 일정 시간마다 CPU를 할당받기 때문에 대화형 시스템에서 빠르게 응답할 수 있다. 평균 대기시간은 보통 중간 수준으로 나타난다. 짧은 작업이 항상 먼저 실행되는 방식이 아니기 때문에 최소 대기시간을 보장하지 않기 때문이다. 그리고 모든 프로세스가 준비 큐를 순환하면서 결국 CPU를 할당받기 때문에 기아 현상이 발생하지 않는다는 특징도 있다.
라운드 로빈 스케줄링 예제
타임 퀀텀이 5라고 가정하자. 라운드 로빈 스케줄링은 각 프로세스에 타임 퀀텀만큼의 시간을 할당해서 CPU를 순환 방식으로 사용하는 방식이다.
0초에 P1이 도착해서 먼저 실행을 시작한다. P1의 실행시간은 10이지만 타임 퀀텀은 5이므로 5만큼 실행한 후 준비 큐의 맨 뒤로 이동한다. 그다음 P2가 실행되는데 실행시간이 28이지만 마찬가지로 5만큼만 실행한 뒤 다시 큐로 이동한다. 이처럼 실행시간이 긴 P1, P2, P3 같은 작업들은 타임 퀀텀만큼만 실행된 뒤 준비 큐의 뒤로 이동하는 과정을 반복한다.
반면 P4는 실행시간이 4로 타임 퀀텀인 5보다 작다. 간트 차트를 보면 15초부터 19초까지 실행된 뒤 바로 종료되는 것을 확인할 수 있다. 즉 타임 퀀텀을 모두 사용하지 않고 남은 시간만큼만 실행되고 종료되는 경우이다. 라운드 로빈 스케줄링에서는 남은 실행시간이 타임 퀀텀보다 작으면 그 시간만큼만 실행한 뒤 바로 종료된다.
이러한 과정을 반복하면 아래와 같은 간트 차트가 만들어진다.
라운드 로빈 스케줄링 - 반환시간, 대기시간 계산
반환시간과 대기시간을 계산해보자. P1은 0초에 도착해서 29초에 끝나므로 반환시간은 29 - 0 = 29가 된다. CPU를 실제로 사용하지 않고 기다리는 시간은 29 - 10 = 19가 된다. 이와 같은 방식으로 나머지 프로세스를 계산하면 포함된 사진과 같다.라운드 로빈 스케줄링은 모든 프로세스가 순환하면서 CPU를 사용하기 때문에 공정성은 높지만, 짧은 작업을 우선적으로 처리하는 방식이 아니기 때문에 평균 대기시간이 최소는 아니다. 즉 응답시간은 우수하지만 평균 대기시간 측면에서는 최적의 방식이 아닐 수 있음을 알수있는 부분이다.
확장 스케줄링 알고리즘이란?
지금까지 살펴본 스케줄링 알고리즘들은 기본적인 CPU 스케줄링 방법이다. 하지만 실제 운영체제에서는 이러한 기본 알고리즘을 그대로 사용하기보다는 여러 가지 문제를 보완하고 개선하여 사용하는 경우가 많은데, 이런 방식을 확장 알고리즘이라고 한다. 즉 기본 스케줄링을 보완하고 개선해서 현실적인 형태에 맞게 발전시킨 알고리즘이라고 할 수 있다. 이를 통해 기아 문제, 응답 지연 문제, 공정성 문제를 개선할 수 있게 된다.
기존 단일 준비 큐의 한계
기존의 기본 스케줄링 알고리즘들은 대부분 하나의 준비 큐를 기준으로 작업을 관리하였다. 모든 작업이 동일한 준비 큐 안에서 관리되는 구조이다. 하지만 이렇게 되면 작업의 특성을 구분하기 어렵다는 문제가 있다. 예를 들어 대화형 작업과 배치 작업은 성격이 서로 다르지만 같은 기준으로 처리되기 때문에 각 작업의 특성을 충분히 반영하기 어렵다.
이러한 한계를 해결하기 위해 준비 큐를 하나만 사용하는 대신 여러 개의 큐로 나누어서 관리하는 방법이 제안된다. 즉 큐 구조 자체를 분리해서 작업의 특성에 맞게 관리하는 방식이다. 이런 아이디어를 바탕으로 다음에 살펴볼 다단계 큐 스케줄링과 같은 알고리즘이 등장하게 된다.
확장 알고리즘: 다단계 큐 스케줄링(Multilevel Queue, MLQ)
다단계 큐 스케줄링은 하나의 준비 큐를 사용하는 대신 준비 큐를 여러 개로 분리해서 관리하는 방식이다. 작업의 유형에 따라 서로 다른 큐에 프로세스를 배치하게 된다. 예를 들어 대화형 작업, 배치 작업, 시스템 작업과 같이 작업의 성격에 따라 서로 다른 큐에 분리해서 관리한다는 의미이다.
각 큐마다 서로 다른 스케줄링 방식을 적용할 수 있다. 예를 들어 어떤 큐에서는 라운드 로빈, 다른 큐에서는 선입선처리 방식을 사용하는 식이다. 그리고 큐 사이에는 고정된 우선순위가 존재하며, 각 프로세스는 하나의 큐에 고정되어 다른 큐로 이동하지 않는 구조를 가지게 된다.
다단계 큐 스케줄링의 구조
다단계 큐 스케줄링에서는 보통 아래와 같이 우선순위에 따라 큐가 구성된다.
CPU는 이러한 큐들 중에서 우선순위가 높은 큐를 먼저 선택해서 실행하게 된다. 즉 상위 큐에 프로세스가 존재하면 하위 큐의 작업은 실행되지 않는다. 이처럼 다단계 큐 스케줄링은 작업의 특성에 따라 서로 다른 큐에서 관리할 수 있다는 점이 핵심이다.
다단계 큐 스케줄링의 한계
다단계 큐 스케줄링에도 몇 가지 한계가 존재한다.
먼저 우선순위가 낮은 큐에서 기아 현상이 발생할 수 있다. 상위 큐에 작업이 항상 존재한다면 하위 큐의 작업은 CPU를 할당받지 못하는 상황이 생기기 때문이다. 또한 이 구조에서는 프로세스가 하나의 큐에 고정되어 있기 때문에 큐 간의 이동이 불가능하다. 따라서 작업의 성격이 바뀌더라도 이를 반영하기 어렵다는 문제도 있다.
이러한 한계를 해결하기 위해 큐 사이를 이동할 수 있는 스케줄링 방식이 제안된다.
확장 알고리즘: 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue, MLFQ)
다단계 피드백 큐 스케줄링은 다단계 큐 스케줄링을 발전시킨 형태의 알고리즘이다. 기존 다단계 큐 스케줄링에서는 프로세스가 하나의 큐에 고정되어 이동할 수 없었지만, 다단계 피드백 큐 스케줄링에서는 프로세스가 큐 사이를 이동할 수 있다. 즉 프로세스의 실행 패턴에 따라 우선순위가 동적으로 조정되는 방식이다.
구체적으로는 CPU를 오래 사용하는 작업은 낮은 큐로 이동하고, 짧게 실행되는 작업은 높은 큐를 유지하게 된다. 또한 오래 기다리는 작업은 다시 상위 큐로 이동하는 에이징 기법도 적용이 가능하다. 이를 통해 작업의 특성에 따라 자연스럽게 구분해서 처리할 수 있는 유연한 스케줄링 방식이라고 할 수 있다.
다단계 피드백 큐 스케줄링의 구조
다단계 피드백 큐 스케줄링은 여러 개의 큐로 구성된다. 아래쪽에 있는 큐일수록 우선순위가 높고, 위로 올라갈수록 우선순위가 낮아지는 구조이다. 일반적으로 우선순위가 높은 하위 큐에서는 짧은 시간 할당을 사용하는 라운드 로빈 방식을 적용하고, 위쪽의 낮은 우선순위 큐로 갈수록 시간 할당량이 점점 길어지게 된다.
프로세스가 CPU를 오래 사용하게 되면 우선순위가 낮아지면서 위쪽 큐로 이동하게 된다. 반대로 짧은 시간 안에 작업이 끝나는 프로세스는 아래쪽의 높은 우선순위 큐에 유지된다. 또한 오랫동안 기다리는 프로세스는 다시 아래쪽의 높은 우선순위 큐로 이동할 수 있는데, 이때 에이징 기법을 활용할 수 있다.
다단계 피드백 큐 스케줄링의 장단점
다단계 피드백 큐 스케줄링의 장점을 살펴보면, 먼저 대화형 작업에 유리하다. 짧은 작업이 높은 우선순위를 유지하기 때문에 빠른 응답을 제공할 수 있다. 또한 오래 기다리는 프로세스를 상위 큐로 이동시키는 방식으로 기아 현상을 완화할 수 있다. 이러한 장점 덕분에 실제 운영체제에서도 널리 사용되는 스케줄링 방식이다.
하지만 단점도 존재한다. 여러 개의 큐와 이동 규칙을 사용하기 때문에 구조가 복잡하다. 또한 큐의 개수, 시간 할당량과 같은 파라미터 설정이 시스템 성능에 큰 영향을 줄 수 있다는 점도 단점으로 꼽힌다.
라운드 로빈과 다단계 피드백 큐 스케줄링 비교
준비 큐에는 3개의 프로세스가 있으며 실행시간은 P1 = 30, P2 = 20, P3 = 10이다.
다단계 피드백 큐 스케줄링이 적용되었을 때 간트 차트를 살펴보면 다음과 같다. 처음에는 모든 프로세스가 가장 높은 우선순위 큐에서 실행을 시작한다. 짧은 시간 할당을 번갈아가며 실행하기 때문에 처음에는 P1 → P2 → P3 순으로 실행된다. 하지만 세 프로세스 모두 정해진 시간 안에 실행을 끝내지 못하기 때문에 모두 다음 단계의 큐로 이동하게 된다.
이 과정이 반복되면서 프로세스들은 점점 더 아래 큐로 이동하게 되고, 시간 할당량도 점점 길어지게 된다. 마지막 단계의 큐에서는 시간 할당 제한이 없기 때문에 남은 실행시간을 종료할 때까지 계속 실행된다. 그 결과 간트 차트의 마지막 부분에서 실행시간이 가장 짧은 P3가 먼저 종료되고, 이어서 P2, P1 순으로 종료되는 모습을 확인할 수 있다.
이 방식의 핵심은 두 가지이다. 짧은 작업인 P3가 먼저 끝나고 긴 작업인 P1이 가장 늦게 끝난다는 점, 그리고 프로세스가 실행 패턴에 따라 큐를 이동하며 처리된다는 점을 기억하자.
라운드 로빈과 다단계 피드백 큐 - 반환시간 비교
타임 퀀텀이 10일 때 라운드 로빈 방식의 실행 순서를 살펴보자. P1은 010까지 실행되어 20이 남고, P2는 1020까지 실행되어 10이 남으며, P3는 20~30까지 실행되어 남은 시간이 0이 되어 30초에 종료된다. 이런 방식으로 반복하면 P1은 60초, P2는 50초, P3는 30초에 종료된다. 다단계 피드백 큐 스케줄링에서는 P1 = 60, P2 = 53, P3 = 32로 평균 반환시간은 48 1/3이 된다.
결론적으로 라운드 로빈 방식의 평균 반환시간이 더 작다는 것을 확인할 수 있다.
라운드 로빈과 다단계 피드백 큐 - 대기시간 비교
이번에는 대기시간을 비교해보자.
라운드 로빈의 평균 대기시간은 (30 + 30 + 20) / 3 = 30이고, 다단계 피드백 큐의 평균 대기시간은 (30 + 33 + 22) / 3 = 28 1/3이다.
이 예제에서는 다단계 피드백 큐의 평균 대기시간이 더 작다는 것을 확인할 수 있다.
두 결과를 종합하면 다음과 같은 의미가 된다.
라운드 로빈(RR) 은 평균 반환시간이 더 작다. 즉 작업이 시작부터 완료까지 걸리는 전체 시간은 RR이 더 짧다.
다단계 피드백 큐(MLFQ) 는 평균 대기시간이 더 작다. 즉 CPU를 기다리는 시간 자체는 MLFQ가 더 짧다.
결국 이 두 결과가 의미하는 것은 어떤 성능 지표를 중요하게 보느냐에 따라 더 좋은 알고리즘이 달라진다는 것이다. 전체 작업 완료 속도가 중요하다면 RR이 유리하고, CPU를 기다리는 시간을 줄이는 것이 중요하다면 MLFQ가 유리하다. 즉 스케줄링 알고리즘은 절대적으로 좋고 나쁜 것이 없으며, 시스템의 목적과 환경에 따라 적합한 알고리즘을 선택하는 것이 중요하다는 것을 이 비교를 통해 확인할 수 있다.
RR과 MLFQ 비교 정리
라운드 로빈은 모든 프로세스를 동일한 시간 할당으로 순환해서 실행하는 방식으로, 모든 작업이 동일한 비율로 CPU를 사용하는 구조이다. 구조가 비교적 단순하다는 장점이 있다. 하지만 긴 작업도 계속 순환해야 하기 때문에 평균 대기시간이 커질 수 있다는 단점이 있다.
반면 다단계 피드백 큐 스케줄링은 프로세스의 특성에 따라 우선순위를 동적으로 조정하는 방식이다. 짧은 작업은 높은 우선순위를 유지하여 빠르게 처리되고, CPU를 오래 사용하는 작업은 점점 하위 큐로 이동하게 된다. 따라서 작업의 특성을 반영하여 응답성과 CPU 효율을 함께 고려한 스케줄링 방식이라고 할 수 있다.
정리하자면 MLFQ는 응답성과 효율성의 균형을 목표로 설계된 확장 스케줄링 구조이다.
3️⃣ CPU Scheduling Performance Comparison Practice
CPU 스케줄링 알고리즘 코드 구현 및 비교
알고리즘의 개념과 실행 흐름을 이해했다면, 이제 실제 코드로 평균 대기시간과 평균 반환시간이 어떻게 계산되는지 확인해보자. 동일한 프로세스 집합에 대해 서로 다른 스케줄링 방식을 적용했을 때 성능이 어떻게 달라지는지를 평균 대기시간과 평균 반환시간을 기준으로 비교해보자.
실습 프로세스 설정
이번 실습에서는 총 4개의 프로세스를 사용한다. 모든 프로세스의 도착시간은 0으로 동일하게 설정하였고, 실행시간은 각각 8, 4, 9, 5이다. 도착시간을 모두 0으로 통일한 이유는 도착시간의 영향을 제거하고 스케줄링 선택 방식의 차이점만 순수하게 비교하기 위해서이다.
성능 지표
대기시간은 프로세스가 준비 큐에서 기다린 시간을 의미하고, 반환시간은 프로세스가 도착한 시점부터 실행이 완료될 때까지의 전체 시간을 의미한다. 이번 실습에서는 모든 프로세스의 도착시간이 0이기 때문에 대기시간은 실행이 시작되는 시점과 동일하게 계산된다.
FCFS, SJF, 라운드 로빈 요약 정리
FCFS(선입선처리 스케줄링) 은 먼저 도착한 작업을 먼저 실행하는 방식으로, 실행 중인 작업을 중단하지 않는 비선점 방식이다. 따라서 실행시간이 긴 작업이 앞에 오면 평균 대기시간이 증가할 수 있다.
SJF(최단 작업 우선 스케줄링) 은 실행시간이 가장 짧은 작업부터 먼저 실행하는 방식이다. 이론적으로는 평균 대기시간을 최소화하는 알고리즘이다.
라운드 로빈(Round Robin) 은 일정한 시간 할당 단위로 CPU를 순환하면서 실행하는 방식으로 응답성이 좋다는 장점이 있다. 반면 시간 할당량이 너무 작으면 문맥 교환이 증가한다는 단점도 있다.
FCFS 예제 코드
#include <stdio.h>
#define N 4
int main() {
int burst[N] = {8, 4, 9, 5};
int wait = 0, total_wait = 0, total_turn = 0;
for(int i = 0; i < N; i++){
total_wait += wait; // 대기시간 누적
total_turn += wait + burst[i]; // 반환시간 누적
wait += burst[i];
}
printf("FCFS Avg Waiting = %.2f\n", (double)total_wait / N);
printf("FCFS Avg Turnaround = %.2f\n", (double)total_turn / N);
return 0;
}
#define N 4 는 4개의 프로세스를 사용한다는 의미이다. 각 프로세스의 실행시간은 burst[N] = {8, 4, 9, 5} 로 설정되어 있다. FCFS 스케줄링은 도착한 순서대로 실행되기 때문에 배열에 저장된 순서 그대로 실행된다. 반복문에서는 각 프로세스의 대기시간과 반환시간을 계산하고, 모든 프로세스의 값을 합산한 뒤 평균 대기시간과 평균 반환시간을 출력하도록 구성되어 있다.
실행 결과는 평균 대기시간 10.25, 평균 반환시간 16.75이다.
SJF 예제 코드
#include <stdio.h>
#define N 4
int main() {
int burst[N] = {8, 4, 9, 5};
// SJF: burst 오름차순 정렬(아주 단순 정렬)
for(int i = 0; i < N-1; i++)
for(int j = i+1; j < N; j++)
if(burst[i] > burst[j]) { int t=burst[i]; burst[i]=burst[j]; burst[j]=t; }
int wait=0, total_wait=0, total_turn=0;
for(int i=0; i<N; i++){
total_wait += wait;
total_turn += wait + burst[i];
wait += burst[i];
}
printf("SJF Avg Waiting = %.2f\n", (double)total_wait / N);
printf("SJF Avg Turnaround = %.2f\n", (double)total_turn / N);
return 0;
}
SJF 스케줄링은 실행시간이 가장 짧은 작업부터 먼저 실행하는 방식이다. 따라서 FCFS 코드와 달리 앞부분에 실행시간을 기준으로 오름차순 정렬하는 과정이 추가되었다. 정렬이 이루어지면 실행 순서는 4 → 5 → 8 → 9가 되고, 이 순서대로 대기시간과 반환시간을 계산하게 된다.
실행 결과는 평균 대기시간 7.50, 평균 반환시간 14.00이다. 같은 프로세스를 사용하더라도 SJF 방식이 FCFS보다 평균 대기시간이 더 작게 나타나는 것을 확인할 수 있다.
라운드 로빈 예제 코드
#include <stdio.h>
#define N 4
int main() {
int burst[N] = {8, 4, 9, 5};
int rem[N], q = 3;
for(int i = 0; i < N; i++) rem[i] = burst[i];
int time=0, total_wait=0, total_turn=0;
while(1){
int done = 1;
for(int i = 0; i < N; i++){
if(rem[i] > 0){
done = 0;
if(rem[i] > q){
time += q;
rem[i] -= q;
} else {
time += rem[i];
total_turn += time; // 반환시간 (도착시간=0)
total_wait += time - burst[i]; // 대기시간
rem[i] = 0;
}
}
}
if(done) break;
}
printf("RR(q=%d) Avg Waiting = %.2f\n", q, (double)total_wait / N);
printf("RR(q=%d) Avg Turnaround = %.2f\n", q, (double)total_turn / N);
return 0;
}
타임 퀀텀 값은 q = 3으로 설정되어 있다. rem 배열은 각 프로세스의 남은 실행시간을 저장한다. while 반복문은 프로세스를 계속 순환하면서 실행하는 구조로, 내부 for 문에서 타임 퀀텀인 3만큼 실행하고 남은 시간을 줄이는 방식으로 라운드 로빈이 구현되었다.
실행 결과는 평균 대기시간 15.00, 평균 반환시간 21.50이다. 같은 프로세스 집합이더라도 스케줄링 방식에 따라 평균 대기시간과 반환시간이 달라진다는 것을 확인할 수 있다. 참고로 다만 라운드 로빈의 평균 대기시간(15.00)과 평균 반환시간(21.50)이 FCFS(10.25 / 16.75), SJF(7.50 / 14.00)보다 크게 나타나는데, 이는 타임 퀀텀이 3으로 작게 설정되어 문맥 교환이 자주 발생하고 순환 횟수가 많아졌기 때문이다. 타임 퀀텀 값에 따라 결과가 달라질 수 있다는 점을 참고로 알아두면 좋다.
스케줄링 알고리즘 성능 비교
세 가지 알고리즘의 실행 결과를 정리하면 아래와 같다.
SJF는 실행시간이 짧은 작업부터 처리하기 때문에 평균 대기시간이 7.50으로 가장 작게 나타난다. 반면 라운드 로빈은 타임 퀀텀 3 기준으로 프로세스를 계속 순환하며 실행하기 때문에 평균 대기시간과 반환시간이 상대적으로 크게 나타난다. 타임 퀀텀 값을 바꿔서 실습해보면 결과가 어떻게 달라지는지 직접 확인해볼 수 있다. 이번 예제에서는 SJF 방식이 평균 대기시간과 반환시간 측면에서 가장 좋은 결과를 보인다는 것을 알 수 있다.
우분투 환경에서의 실습
지금까지 살펴본 알고리즘의 동작 원리를 이해하기 위한 예제 코드를 우분투 환경에서 직접 실습해본다. 코드의 실행 결과를 통해 각 알고리즘이 어떻게 동작하는지 확인하는 데 초점을 둔다.
