스케줄링 알고리즘 (r1)

공정성은 모든 프로세스가 공정하게 CPU 시간을 할당받아야 한다는 원칙이다. 이는 특정 프로세스가 무한정 대기하는 기아 상태를 방지하는 것을 포함한다. 그러나 절대적인 공정성은 종종 시스템의 전체적인 효율성을 저하시킬 수 있다. 예를 들어, 매우 긴 작업과 짧은 작업이 동일한 시간을 할당받으면 짧은 작업의 응답 시간이 나빠질 수 있다. 따라서 스케줄러는 공정성과 다른 성능 지표 사이에서 균형을 찾아야 한다.

처리량은 단위 시간당 완료되는 프로세스의 수를 의미한다. 이는 시스템의 생산성을 측정하는 핵심 지표이다. 처리량을 높이기 위해서는 컨텍스트 스위칭의 오버헤드를 최소화하고, CPU를 가능한 한 바쁘게 유지하며, 효율적으로 작업을 완료하는 것이 중요하다. 일반적으로 짧은 작업을 우선 처리하는 알고리즘이 평균적으로 더 높은 처리량을 보인다.

공정성과 처리량은 종종 상충 관계에 있다. 모든 프로세스에 동일한 시간을 할당하는 공정한 방식은 짧은 작업이 빨리 끝날 수 있는 기회를 줄여 전체 처리량을 낮출 수 있다. 반대로, 처리량만을 극대화하기 위해 짧은 작업만 계속 처리하면, 긴 작업은 영원히 실행되지 못하는 불공정한 상황이 발생할 수 있다. 따라서 효과적인 스케줄링 알고리즘은 이 두 목표 사이에서 적절한 타협점을 찾도록 설계된다.

응답 시간은 프로세스가 생성되어 처음으로 CPU를 할당받기까지 걸리는 시간을 의미한다. 구체적으로는 프로세스가 준비 완료 상태가 되어 준비 큐에 들어간 시점부터 실제로 실행을 시작하는 시점까지의 간격이다. 이는 대화형 시스템에서 사용자가 명령을 입력한 후 시스템이 반응을 보이기까지의 지연을 느끼는 시간과 직접적으로 연관된다. 따라서 응답 시간이 짧을수록 시스템의 반응성이 좋다고 평가된다.

대기 시간은 프로세스가 준비 큐에서 대기하는 총 시간을 가리킨다. 즉, 프로세스가 실행 준비를 마쳤음에도 불구하고 다른 프로세스들이 CPU를 사용하고 있어 기다려야 하는 시간의 합이다. 스케줄링 알고리즘의 효율성을 평가하는 중요한 지표 중 하나로, 평균 대기 시간을 최소화하는 것이 많은 스케줄링 기법의 주요 목표가 된다. 대기 시간이 길면 전체 시스템의 처리 효율이 떨어지고, 사용자나 다른 프로세스의 작업이 지연되는 결과를 초래한다.

응답 시간과 대기 시간은 밀접하게 관련되어 있지만 미묘한 차이가 존재한다. 응답 시간은 프로세스의 첫 번째 응답에 초점을 맞춘 반면, 대기 시간은 프로세스의 전체 생애 동안 준비 큐에서 보낸 누적 시간을 측정한다. 예를 들어, 라운드 로빈 스케줄링과 같은 시분할 시스템에서는 각 프로세스가 짧은 시간 간격(타임 슬라이스)으로 CPU를 번갈아 사용하므로, 첫 응답 시간은 매우 짧게 유지될 수 있다. 그러나 전체 작업 완료까지 여러 번의 대기 구간이 발생하므로, 대기 시간은 작업의 길이와 시스템 부하에 따라 달라질 수 있다.

이 두 지표는 서로 트레이드오프 관계에 있을 수 있다. 예를 들어, 모든 작업을 매우 짧은 시간 조각으로 분할하여 응답 시간을 극단적으로 줄이면, 문맥 교환 오버헤드가 증가하여 실제 작업 완료는 더디어지고 전체적인 대기 시간이 늘어날 수 있다. 따라서 운영체제 설계자는 시스템의 주요 용도(예: 일괄 처리, 실시간 처리, 대화형 처리)에 따라 적절한 스케줄링 정책을 선택하여 이들 지표 사이의 균형을 맞춘다.

CPU 활용도는 스케줄링 알고리즘의 주요 평가 기준 중 하나로, 전체 시간 중 CPU가 유용한 작업을 수행한 시간의 비율을 의미한다. 이는 시스템의 자원 사용 효율성을 직접적으로 나타내는 지표이다. 높은 CPU 활용도는 시스템이 유휴 상태에 머무르는 시간이 적고, 주어진 하드웨어 자원을 최대한으로 활용하고 있음을 시사한다.

이론적으로 CPU 활용도는 0%에서 100% 사이의 값을 가지며, 100%에 가까울수록 바람직하다. 그러나 실제 시스템에서는 입출력 작업 대기, 프로세스 간 문맥 교환 오버헤드, 그리고 모든 프로세스가 입출력을 기다리는 등의 상황으로 인해 100%를 달성하기는 어렵다. 특히 대화형 시스템에서는 사용자 응답을 위해 의도적으로 CPU를 일부 유휴 상태로 유지하기도 한다.

다음 표는 CPU 활용도에 영향을 미치는 일반적인 요인을 보여준다.

CPU 활용도는 처리량과 밀접한 관련이 있지만, 항상 비례하는 것은 아니다. 예를 들어, 매우 짧은 시간 할당량을 사용하는 라운드 로빈 스케줄링은 문맥 교환 오버헤드가 증가하여 CPU 활용도는 높을 수 있지만, 실제 유용한 작업의 처리량은 오히려 떨어질 수 있다. 따라서 운영체제 설계자는 높은 CPU 활용도와 응답 시간, 공정성 등의 다른 목표 사이에서 균형을 찾아야 한다.

FCFS는 가장 단순한 형태의 CPU 스케줄링 알고리즘이다. 이 방식은 준비 큐에 도착한 순서대로 프로세스에 CPU를 할당한다. 즉, 먼저 요청한 프로세스가 먼저 처리되는 방식으로, 은행 창구의 대기 줄과 유사한 구조를 가진다. 알고리즘의 구현이 매우 간단하며, 선입선출 큐를 사용하여 관리된다.

FCFS의 주요 특징은 비선점형 스케줄링 방식이라는 점이다. 한 프로세스가 CPU를 할당받으면 그 프로세스의 실행이 완료될 때까지(입출력 대기 상태에 들어가거나 종료될 때까지) CPU를 점유한다. 이로 인해 평균 대기 시간이 길어질 수 있으며, 특히 실행 시간이 긴 프로세스가 먼저 도착하면 뒤에 있는 짧은 프로세스들의 대기 시간이 크게 증가하는 호위 효과가 발생할 수 있다.

다음은 세 개의 프로세스가 도착 순서대로 처리될 때의 대기 시간을 보여주는 예시이다. 도착 시간은 모두 0이라고 가정한다.

위 표에서 알 수 있듯이, P1이 먼저 실행되어 24시간 동안 CPU를 점유하면, 짧은 작업인 P2와 P3는 각각 24, 27만큼 긴 대기 시간을 가지게 된다. 이 경우 평균 대기 시간은 (0 + 24 + 27) / 3 = 17이 된다. 만약 도착 순서가 P2, P3, P1이었다면 평균 대기 시간은 크게 개선될 수 있다.

따라서 FCFS는 구현이 쉽고 공정해 보이지만, 전체 시스템의 처리량을 최적화하거나 평균 응답 시간을 줄이는 데는 비효율적일 수 있다. 이 단점을 보완하기 위해 라운드 로빈이나 SJF 같은 다른 알고리즘이 개발되었다.

SJF는 실행 시간이 가장 짧은 작업을 가장 먼저 처리하는 비선점형 스케줄링 알고리즘이다. 이 알고리즘의 핵심은 모든 작업이 도착한 상태에서, 전체 대기 시간의 합을 최소화하는 최적의 순서를 선택하는 것이다. 이는 평균 대기 시간을 최소화하는 이론적으로 이상적인 알고리즘으로 평가된다.

SJF는 실행 시간을 미리 알고 있어야 한다는 근본적인 문제를 안고 있다. 실제 시스템에서는 작업의 실행 시간을 정확히 예측하기 어렵다. 이를 해결하기 위해 과거 실행 시간의 평균을 이용한 추정 기법이 사용된다. 예를 들어, 다음 실행 시간을 예측할 때 이전 실행 시간과 이전 예측값의 가중 평균을 계산하는 방법이 있다.

SJF의 주요 변형으로는 선점형 스케줄링 방식인 SRTF가 있다. SRTF는 새로운 더 짧은 작업이 도착하면 현재 실행 중인 작업을 중단시키고 새 작업을 먼저 실행한다. 이 방식은 평균 대기 시간을 SJF보다 더 줄일 수 있지만, 문맥 교환 오버헤드가 증가하고 기아 상태가 발생할 가능성이 있다.

SJF는 일괄 처리 시스템에서의 이론적 모델로 자주 인용되지만, 실행 시간 예측의 어려움 때문에 순수한 형태로 현대 운영체제에 구현되지는 않는다. 대신 그 원리는 다른 스케줄러의 일부 요소로 통합되어 활용된다.

라운드 로빈 스케줄링은 선점형 스케줄링 방식의 대표적인 예시이다. 각 프로세스는 고정된 시간 단위인 타임 슬라이스 또는 타임 퀀텀 동안만 CPU를 할당받아 실행된다. 할당된 시간이 경과하면, 실행 중이던 프로세스는 선점되어 준비 큐의 맨 뒤로 이동하고, 큐의 맨 앞에 대기 중인 다음 프로세스에게 CPU가 넘어간다. 이 과정을 모든 프로세스가 완료될 때까지 순환적으로 반복한다.

이 알고리즘의 핵심 장점은 모든 프로세스에게 공평하게 CPU 시간을 나누어 주어 기아 상태를 방지한다는 점이다. 특히 대화형 시스템에서 짧은 응답 시간을 보장하는 데 효과적이다. 그러나 타임 슬라이스의 크기는 성능에 결정적인 영향을 미친다. 슬라이스가 지나치게 크면 FCFS와 유사해져 응답성이 떨어지고, 반대로 너무 작으면 문맥 교환 오버헤드가 과도하게 증가하여 전체적인 처리 효율이 저하된다.

라운드 로빈의 성능은 주로 평균 대기 시간으로 평가된다. 일반적으로 CPU 버스트 시간이 비슷한 프로세스들로 구성된 경우 효율적이지만, CPU 집중적인 긴 작업과 짧은 대화형 작업이 혼재되어 있을 경우에는 평균 대기 시간이 길어질 수 있다. 다음은 세 개의 프로세스(P1, P2, P3)가 도착 시간 0에 있고, 타임 슬라이스가 4일 때의 간단한 실행 예시이다.

실행 순서는 P1(4) -> P2(3) -> P3(3) -> P1(4) -> ... 와 같이 진행되며, P2와 P3는 첫 번째 순환에서 완료된다. 이 방식은 모든 작업이 완료될 기회를 얻지만, 긴 작업의 완료 시간은 상대적으로 지연된다.

우선순위 스케줄링은 각 프로세스에 우선순위를 할당하고, 준비 완료 큐에서 가장 높은 우선순위를 가진 프로세스를 먼저 실행하는 방식이다. 우선순위는 정수 값으로 표현되며, 일반적으로 숫자가 작을수록 높은 우선순위를 의미하는 경우가 많다. 이 방식은 프로세스의 중요도, 작업의 긴급성, 자원 요구량 등 다양한 기준에 따라 우선순위를 결정할 수 있다.

우선순위 스케줄링은 선점형과 비선점형 방식으로 모두 구현될 수 있다. 비선점형 방식에서는 높은 우선순위의 프로세스가 도착해도 현재 실행 중인 프로세스가 자발적으로 CPU를 양도할 때까지 기다린다. 반면, 선점형 방식에서는 실행 중인 프로세스보다 높은 우선순위의 프로세스가 준비 큐에 들어오면 즉시 선점하여 CPU를 할당받는다. 이는 더 중요한 작업에 대한 응답성을 높이는 효과가 있다.

이 알고리즘의 주요 문제점은 기아 상태가 발생할 수 있다는 것이다. 낮은 우선순위를 가진 프로세스는 높은 우선순위의 프로세스가 계속 들어오는 경우 무한정 대기하게 될 수 있다. 이를 해결하기 위해 에이징 기법이 사용된다. 에이징은 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여, 결국에는 실행될 기회를 보장하는 방법이다.

우선순위 스케줄링은 실시간 시스템이나 일괄 처리 시스템에서 특정 작업에 우선적인 자원 할당이 필요할 때 유용하게 적용된다.

다단계 큐 스케줄링은 준비 큐를 여러 개의 독립적인 큐로 분할하여, 각 큐마다 서로 다른 스케줄링 알고리즘과 우선순위를 적용하는 방식이다. 이 방법은 프로세스들을 특성에 따라 그룹화하여 관리할 수 있다는 장점을 가진다. 예를 들어, 대화형 프로세스, 배치 작업, 시스템 프로세스 등을 별도의 큐에 배치하고, 각 큐에 가장 적합한 스케줄링 정책을 할당한다. 일반적으로 높은 우선순위를 가진 큐의 프로세스들이 먼저 실행되며, 큐 간의 스케줄링은 고정 우선순위 방식이나 타임 슬라이스를 할당하는 방식 등으로 이루어진다.

큐 간의 프로세스 이동을 허용하지 않는 고정형 다단계 큐와, 프로세스가 큐 사이를 이동할 수 있는 다단계 피드백 큐로 구분된다. 다단계 피드백 큐는 에이징 기법의 일종으로, 너무 오래 기다린 프로세스의 우선순위를 높여 기아 상태를 완화한다. 반대로 CPU 시간을 많이 사용한 프로세스는 우선순위가 낮아지는 페널티를 받을 수 있다. 이 방식은 여러 알고리즘의 장점을 결합하고 시스템의 복잡한 요구 사항을 반영할 수 있어, 역사적으로 IBM OS/360, UNIX 시스템 등 여러 운영체제에서 변형된 형태로 구현되었다.

다단계 큐 스케줄링의 주요 파라미터와 그 역할은 다음과 같다.

이러한 유연성에도 불구하고, 설계가 복잡하고 각 큐에 대한 파라미터(예: 타임 퀀텀 크기, 우선순위)를 적절히 설정해야 하는 튜닝 부담이 존재한다.

RM 스케줄링은 주기가 짧은 실시간 태스크에 높은 우선순위를 부여하는 정적 우선순위 기반의 실시간 스케줄링 알고리즘이다. 이 알고리즘의 핵심 원칙은 태스크의 주기가 더 짧을수록, 즉 데드라인이 더 자주 도래할수록 더 높은 우선순위를 할당하는 것이다. 이는 시스템 설계 단계에서 모든 태스크의 주기가 알려져 있어야 하므로 정적 우선순위 방식으로 분류된다.

RM 스케줄링의 스케줄 가능성은 LLF 스케줄링과 같은 동적 알고리즘보다 낮지만, 구현이 간단하고 런타임 오버헤드가 작다는 장점이 있다. 가장 잘 알려진 스케줄 가능성 검사 방법은 모든 태스크의 CPU 사용률 합이 태스크 수 n에 대해 n(2^(1/n) - 1) 이하일 때 스케줄 가능하다는 것이다[2]. 이 값은 태스크 수가 많아질수록 약 69.3%에 수렴한다.

이 알고리즘은 주기적인 센서 데이터 읽기나 제어 루프 실행과 같이 반복 주기가 엄격하게 정의된 임베디드 시스템에 널리 적용된다. 그러나 모든 태스크가 주기적이라는 가정 하에 동작하므로, 비주기적 또는 연성 실시간 태스크가 혼재된 환경에서는 다른 알고리즘과 결합하여 사용되기도 한다.

EDF는 실시간 운영체제에서 사용되는 동적 우선순위 스케줄링 알고리즘이다. 이 알고리즘의 핵심 원칙은 마감 기한이 가장 빠른 작업, 즉 '가장 급한' 작업을 가장 높은 우선순위로 스케줄링하는 것이다. 작업의 실행 시간이나 주기보다는 절대적인 마감 시간이 우선순위를 결정하는 유일한 기준이 된다. 따라서 시스템은 주기적으로 또는 새로운 작업이 도착할 때마다 모든 준비 완료 상태 작업의 마감 시간을 비교하여 가장 이른 마감 시간을 가진 작업에 CPU를 할당한다.

EDF는 선점형 스케줄링 방식을 사용하며, 주로 주기적 태스크와 비주기적 태스크가 혼합된 환경에서 적용된다. 이 알고리즘의 가장 큰 장점은 높은 CPU 활용도를 달성할 수 있다는 점이다. RM 스케줄링과 같은 정적 우선순위 알고리즘이 단일 CPU에서 최대 약 69%의 활용도 한계를 가지는 반면, EDF는 주기적 작업 집합이 다음 조건을 만족하면 100%까지 활용도를 높일 수 있다[3]. 이 조건은 모든 작업의 CPU 사용률 합이 1(또는 100%)을 초과하지 않아야 한다는 것이다.

그러나 EDF는 구현과 분석이 상대적으로 복잡하며, 시스템이 과부하 상태에 빠지면 마감 시간을 지키지 못하는 작업이 다수 발생할 수 있다는 단점이 있다. 또한 마감 시간을 주기적으로 모니터링하고 우선순위를 재계산하는 오버헤드가 존재한다. 이러한 특성으로 인해 EDF는 항공 전자 시스템이나 산업용 제어 시스템과 같이 엄격한 시간 제약을 가진 경성 실시간 시스템보다는, 멀티미디어 처리나 통신 프로토콜과 같이 일정 수준의 마감 시간 누락이 허용되는 연성 실시간 시스템에서 더 널리 사용되는 경향이 있다.

시뮬레이션은 다양한 스케줄링 알고리즘의 성능을 평가하는 가장 일반적인 방법이다. 이 방법은 실제 시스템이나 가상의 프로세스 집합에 대한 모델을 구축하고, 알고리즘을 적용하여 성능 지표를 측정한다. 시뮬레이션은 실제 시스템에 구현하기 전에 알고리즘의 특성과 잠재적 문제점을 비교 분석하는 데 유용하다. 시뮬레이션 모델은 도착 시간, 실행 시간, 입출력 요구 패턴 등 프로세스의 특성을 정의하는 파라미터를 사용하여 구축된다.

시뮬레이션 평가의 핵심은 워크로드를 생성하는 것이다. 워크로드는 평가에 사용될 프로세스들의 시퀀스를 의미하며, 과거 시스템의 실제 로그를 사용하거나 확률 분포(예: 지수 분포나 균등 분포)를 기반으로 인위적으로 생성할 수 있다. 생성된 워크로드에 대해 FCFS, 라운드 로빈, SJF 등 비교 대상 알고리즘을 차례로 적용하여 평균 대기 시간, 평균 반환 시간, 처리량 등의 성능 메트릭을 계산하고 비교한다.

이 방법의 주요 장점은 비교적 저렴한 비용과 안전성이다. 실제 운영체제 커널을 수정하거나 중요한 업무 시스템에 테스트하는 것보다 훨씬 효율적이다. 또한, 시뮬레이션을 통해 극단적인 조건이나 특정 패턴의 워크로드에 대한 알고리즘의 반응을 집중적으로 관찰할 수 있다. 그러나 시뮬레이션 결과의 정확성은 입력 모델의 정확도에 크게 의존한다는 한계가 있다. 실제 시스템의 동작을 완벽히 반영하지 못한 모델은 오해의 소지가 있는 결과를 낳을 수 있다[5].

수학적 분석은 스케줄링 알고리즘의 성능을 이론적으로 평가하는 방법이다. 이 방법은 주어진 작업 부하와 시스템 모델에 대해 알고리즘의 성능 지표(예: 평균 대기 시간, 평균 반환 시간)를 정확한 수학적 공식으로 도출한다. 분석은 일반적으로 확률론적 모델(예: 작업 도착을 포아송 과정으로 가정)이나 결정론적 최악의 시나리오를 기반으로 이루어진다. 이를 통해 알고리즘의 근본적인 특성과 한계를 이해할 수 있으며, 시뮬레이션만으로는 얻기 어려운 일반적인 결론을 이끌어낼 수 있다.

예를 들어, FCFS 알고리즘의 평균 대기 시간은 작업 도착률과 서비스 시간 분포를 사용해 큐잉 이론의 공식을 적용하여 계산할 수 있다. 라운드 로빈 알고리즘의 경우, 시간 할당량의 크기와 문맥 교환 오버헤드를 고려한 평균 반환 시간에 대한 공식을 유도할 수 있다. RM 스케줄링과 같은 실시간 알고리즘의 분석은 주로 스케줄 가능성 판별에 초점을 맞춘다. 주기적 작업 집합이 주어졌을 때, 유틸리켈션의 상한값(예: RM의 경우 n(2^(1/n)-1))을 계산하여 모든 작업이 데드라인 내에 실행될 수 있는지 여부를 수학적으로 증명한다.

수학적 분석의 장점과 한계는 다음과 같이 정리할 수 있다.

따라서 수학적 분석은 종종 시뮬레이션 평가와 상호 보완적으로 사용된다. 이론적 분석으로 기본 원리를 규명한 후, 보다 현실적인 조건에서 시뮬레이션을 통해 검증하는 접근 방식이 일반적이다.

리눅스 커널의 기본 스케줄러는 2.6.23 버전부터 완전 공정 스케줄러(Completely Fair Scheduler, CFS)로 교체되었다. CFS는 이전의 O(1) 스케줄러를 대체하며, "공정성"을 핵심 설계 철학으로 삼았다. 이는 각 프로세스가 균등하게 CPU 시간을 받을 수 있도록 보장하는 것을 목표로 한다.

CFS는 실행 가능한 모든 프로세스들을 하나의 레드-블랙 트리라는 자가 균형 이진 탐색 트리로 관리한다. 트리의 키 값은 각 프로세스의 vruntime(가상 실행 시간)이다. vruntime은 프로세스가 실제로 CPU를 사용한 시간을 보정한 값으로, 우선순위가 높은 프로세스일수록 vruntime이 느리게 증가한다. 스케줄러는 항상 vruntime이 가장 작은, 즉 CPU를 가장 적게 받은 프로세스를 선택하여 실행한다. 이 방식을 통해 CFS는 이상적인 멀티태스킹 프로세서에서의 실행과 유사한 공정성을 달성하려고 한다.

CFS는 선점형 스케줄링을 사용하며, 시간 할당의 기본 단위는 타임 슬라이스가 아니라 목표 지연 시간(target latency)이다. 이는 모든 실행 가능한 프로세스가 한 번씩 실행될 수 있도록 하는 기간을 의미한다. 실행 가능한 프로세스 수에 따라 각 프로세스가 받는 시간 할당량이 동적으로 조정된다. 또한, 대화형 프로세스의 응답성을 높이기 위해 슬리프 평균(sleep average) 등의 메커니즘을 활용한다.

Windows 운영체제의 스케줄러는 선점형, 우선순위 기반의 다단계 큐 스케줄링 방식을 사용한다. 스레드의 우선순위는 0부터 31까지의 32단계로 구분되며, 높은 숫자가 더 높은 우선순위를 나타낸다. 우선순위 16 이상은 실시간(real-time) 클래스, 15 이하는 동적(dynamic) 클래스로 관리된다. 스케줄러는 실행 가능한 스레드 중 가장 높은 우선순위를 가진 스레드를 선택하여 실행한다.

실시간 우선순위(16-31)의 스레드는 일반적으로 시간 제약이 엄격한 작업에 할당되며, 준비 상태가 되면 즉시 낮은 우선순위 스레드를 선점한다. 동적 우선순위(0-15)의 스레드는 우선순위 스케줄링과 유사하게 동작하지만, 운영체제가 상황에 따라 우선순위를 동적으로 조절한다. 예를 들어, 입출력 작업을 자주 수행하는 대화형 스레드의 우선순위는 높아지고, CPU를 오래 점유하는 계산 중심 스레드의 우선순위는 낮아질 수 있다. 이를 통해 전반적인 시스템 응답성을 향상시킨다.

Windows 스케줄러는 또한 라운드 로빈 방식의 시간 할당량(time quantum) 개념을 사용한다. 동일한 우선순위를 가진 여러 스레드가 준비 상태일 경우, 각 스레드는 정해진 시간 할당량 동안 실행된 후 다음 스레드로 전환된다. 시간 할당량의 길이는 시스템 설정과 스레드의 특성(예: 전면/배치 처리)에 따라 달라질 수 있다. 이 구조는 다중 코어 및 다중 프로세서 시스템을 효율적으로 지원하도록 설계되었다.