SJF

비선점형 SJF는 프로세스가 CPU를 할당받으면 그 프로세스의 실행이 완료될 때까지 CPU를 점유하는 방식이다. 이 방식에서는 한 번 실행이 시작된 프로세스는 중간에 다른 프로세스에게 CPU를 빼앗기지 않는다. 따라서 스케줄러는 준비 큐에 있는 프로세스들 중에서 실행 시간이 가장 짧은 프로세스를 선택하여 CPU에 할당하고, 해당 프로세스의 버스트 타임이 모두 소진될 때까지 기다린다.

작동 과정은 다음과 같다. 먼저, 모든 도착한 프로세스의 예상 실행 시간을 비교한다. 그 후 예상 실행 시간이 가장 짧은 프로세스를 준비 큐의 맨 앞에 위치시킨다. 현재 실행 중인 프로세스가 종료되면, 준비 큐의 맨 앞에 있는 (즉, 가장 짧은) 프로세스를 다음으로 실행한다. 만약 실행 시간이 동일한 프로세스가 여러 개 존재할 경우, 일반적으로 먼저 도착한 순서(FCFS)에 따라 처리한다.

이 표는 네 개의 프로세스가 시간 0에 동시에 도착했을 때 비선점형 SJF가 작동하는 예시를 보여준다. 가장 짧은 실행 시간(1)을 가진 P3는 P1의 긴 실행(7)이 완전히 끝난 후에야 실행될 수 있다. 이는 비선점형의 특징으로, 긴 프로세스가 실행 중일 때는 더 짧은 프로세스라도 기다려야 함을 의미한다.

이 방식의 주요 특징은 콘보이 효과를 일부 완화할 수 있다는 점이다. 실행 시간이 긴 프로세스 뒤에 매우 짧은 프로세스들이 대기하는 상황을 피할 수 있다. 그러나 프로세스의 정확한 실행 시간을 미리 알기 어렵다는 근본적인 문제와, 실행 중인 프로세스가 끝나기 전에 도착한 더 짧은 프로세스를 즉시 처리할 수 없다는 비선점적 제약이 존재한다.

선점형 SJF는 최단 작업 우선 알고리즘의 변형으로, 최단 잔여 시간 우선(Shortest Remaining Time First, SRTF)이라고도 불린다. 비선점형 SJF가 프로세스가 CPU를 점유하면 실행을 완료할 때까지 기다리는 반면, 선점형 SJF는 현재 실행 중인 프로세스의 남은 실행 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 준비 큐에 도착하면, 현재 프로세스를 중단시키고 새 프로세스를 먼저 실행한다.

이 방식의 핵심은 항상 시스템 내에서 남은 실행 시간이 가장 짧은 프로세스가 CPU를 선점하도록 하는 것이다. 새로운 프로세스 P_new가 도착했을 때, 시스템은 현재 실행 중인 프로세스 P_current의 잔여 실행 시간과 P_new의 총 실행 시간을 비교한다. P_new의 실행 시간이 더 짧다면, P_current는 선점되어 준비 큐로 돌아가고, P_new가 즉시 실행을 시작한다. 이 비교는 새로운 프로세스가 도착할 때마다 반복적으로 발생한다.

선점형 SJF의 성능은 일반적으로 비선점형 SJF보다 우수하다. 평균 대기 시간과 평균 반환 시간을 더욱 줄일 수 있기 때문이다. 다음은 간단한 예시로, 프로세스 A(실행 시간 8ms)가 실행을 시작한 직후 프로세스 B(실행 시간 4ms)가 도착하는 경우를 비교한 것이다.

그러나 선점형 SJF는 비선점형에 비해 구현 복잡도가 높다는 단점이 있다. 프로세스의 실행을 중단하고 문맥 교환을 자주 수행해야 하며, 무엇보다도 미래의 잔여 실행 시간을 지속적으로 추정하고 비교해야 한다. 이는 실행 시간 예측의 부정확성을 더욱 증폭시킬 수 있다. 또한, 선점이 빈번하게 발생하면 기아 현상이 발생할 가능성도 존재한다. 매우 긴 실행 시간을 가진 프로세스는 계속해서 더 짧은 프로세스들에게 선점당해 실행 기회를 얻지 못할 수 있다.

SJF 스케줄링의 가장 큰 이점은 주어진 프로세스 집합에 대해 평균 대기 시간을 이론적으로 최소화할 수 있다는 점이다. 이는 실행 시간이 짧은 작업을 먼저 처리함으로써, 많은 프로세스가 준비 큐에서 기다리는 시간을 줄일 수 있기 때문이다. 긴 작업이 뒤로 밀리더라도, 전체적으로 보면 모든 프로세스가 완료되기까지 걸리는 총 대기 시간의 합이 최소가 된다.

구체적인 예를 들어 설명하면, 도착 시간이 0이고 실행 시간이 각각 3, 6, 4인 세 개의 프로세스 P1, P2, P3가 있다고 가정한다. FCFS 방식으로 P1, P2, P3 순서로 실행하면 대기 시간은 P1=0, P2=3, P3=9로 평균 대기 시간은 (0+3+9)/3 = 4가 된다. 반면, SJF 방식으로 가장 짧은 실행 시간 순(P1, P3, P2)으로 실행하면 대기 시간은 P1=0, P3=3, P2=7이 되어 평균 대기 시간은 (0+3+7)/3 ≈ 3.33으로 감소한다.

이 알고리즘의 효율성은 다음 표를 통해 명확히 비교할 수 있다.

이러한 최적성은 모든 프로세스가 동시에 준비 상태가 되었을 때(도착 시간이 모두 0일 때) 특히 잘 드러난다. 프로세스의 도착 시간이 서로 다른 경우에도, 선점형 SJF를 통해 유사한 최적의 성능에 근접할 수 있다. 따라서 대화형 시스템에서 사용자 응답 시간을 개선하거나, 일괄 처리 시스템에서 전체 작업 처리 시간을 단축하는 데 이론적으로 유리한 알고리즘으로 평가받는다.

실행 시간을 미리 알 수 없다는 점은 SJF 스케줄링을 실시간 시스템에 적용하는 데 근본적인 장애물이 된다. 대부분의 실제 컴퓨팅 환경에서는 프로세스의 정확한 다음 CPU 버스트 시간을 사전에 예측하기가 매우 어렵다. 이는 알고리즘이 이론적으로는 최적의 성능을 보장하지만, 실제 구현에서는 추정치에 의존해야 함을 의미한다.

실시간 시스템은 작업이 정해진 데드라인 내에 반드시 완료되어야 하는 엄격한 시간적 제약을 가진다. SJF는 평균 대기 시간을 최소화하는 데 초점을 맞추지만, 이는 긴 작업이 계속해서 연기되어 기아 상태에 빠질 수 있음을 의미한다. 실시간 시스템에서는 특정 작업이 지연되는 것이 전체 시스템의 실패로 이어질 수 있으므로, 이러한 예측 불가능성과 긴 작업에 대한 불이익은 용인하기 어렵다.

따라서 SJF는 일괄 처리 시스템이나 실행 시간 패턴이 비교적 예측 가능한 특정 환경에서 더 유용하게 여겨진다. 실시간 스케줄링에는 RM 스케줄링이나 EDF 스케줄링과 같이 데드라인을 명시적으로 고려하는 알고리즘이 일반적으로 선호된다.

실행 시간을 정확히 예측하는 것은 SJF 스케줄링이 이론적인 장점을 실현하기 위한 핵심 과제이다. 운영체제는 일반적으로 프로세스의 총 실행 시간을 미리 알지 못하므로, 다양한 추정 기법을 사용하여 다음 CPU 버스트(CPU 사용 시간)의 길이를 예측한다.

가장 흔한 방법은 과거의 CPU 버스트 기록을 바탕으로 지수 평균(Exponential Averaging)을 적용하는 것이다. 이 방법은 최근 버스트 시간에 더 높은 가중치를 부여하면서도 과거 전체 이력을 반영한다. 예측값은 다음 공식으로 계산된다.

τₙ₊₁ = α tₙ + (1-α) τₙ

여기서 τₙ₊₁은 다음 CPU 버스트의 예측 길이, tₙ은 가장 최근에 관측된 실제 CPU 버스트 길이, τₙ은 이전 예측값, α는 0과 1 사이의 평활화 계수이다. α 값이 1에 가까울수록 최근 관측치만을 반영하며, 0에 가까울수록 과거 예측 이력에 더 의존한다.

실제 시스템에서는 지수 평균 기법이 효율적이고 구현 부담이 적어 널리 채택된다. 그러나 이 방법도 예측 오차를 완전히 제거할 수는 없으며, 예측이 빗나갈 경우 기아 현상이 발생하거나 평균 대기 시간이 이론값보다 늘어날 수 있다.

준비 큐는 SJF 스케줄링에서 실행 대기 중인 프로세스들을 보관하는 핵심 자료 구조이다. 일반적으로 프로세스는 도착 시간 순서대로 큐에 삽입되지만, 스케줄러는 이 큐를 프로세스의 예상 또는 실제 실행 시간에 따라 재정렬하여 관리한다. 비선점형 SJF에서는 프로세스가 준비 큐에 들어온 시점에서 예상 실행 시간이 가장 짧은 프로세스를 선택하여 실행하며, 그 프로세스가 완전히 종료될 때까지 큐의 순서는 변하지 않는다. 선점형 SJF(SRTF)에서는 새 프로세스가 도착하거나 실행 중인 프로세스의 남은 실행 시간이 갱신될 때마다, 준비 큐에 있는 모든 프로세스(현재 실행 중인 프로세스 포함)의 남은 실행 시간을 비교하여 가장 짧은 프로세스를 선점적으로 선택한다. 이로 인해 준비 큐의 순서는 빈번히 재조정될 수 있다.

준비 큐를 효율적으로 관리하기 위해 주로 최소 힙(Min-Heap)이나 우선순위 큐(Priority Queue) 자료 구조가 사용된다. 이는 예상 실행 시간(또는 남은 실행 시간)을 키(Key)로 하여, 가장 짧은 시간을 가진 프로세스를 O(log n)의 시간 복잡도로 빠르게 추출하고 삽입할 수 있게 한다. 표준적인 FCFS 큐를 사용하고 매번 전체 검색을 한다면 O(n)의 시간이 소요되어 효율성이 떨어진다.

준비 큐 관리에서 중요한 또 다른 요소는 프로세스의 실행 시간을 어떻게 예측하거나 측정하는지이다. 과거 실행 기록을 바탕으로 지수 평균(Exponential Averaging) 등의 방법으로 예측 시간을 계산하여 큐에 반영하거나, 실제로는 실행 시간을 알 수 없는 경우에는 사용자 제공 예상치나 기본값을 사용하기도 한다. 이 예측치의 정확도는 준비 큐의 순서와 스케줄링 효율성에 직접적인 영향을 미친다.

FCFS는 프로세스가 준비 큐에 도착한 순서대로 실행하는 방식이다. 이 방식은 구현이 단순하고 공정해 보이지만, 평균 대기 시간이 길어질 수 있는 단점이 있다. 특히 실행 시간이 긴 프로세스가 먼저 도착하면, 뒤에 도착한 짧은 프로세스들이 오랫동안 기다려야 하는 호위 효과가 발생한다.

반면 SJF는 실행 시간이 가장 짧은 프로세스를 먼저 실행한다. 이론적으로 SJF는 평균 대기 시간을 최소화하는 최적의 알고리즘으로 알려져 있다[4]. 다음은 동일한 프로세스 집합에 대해 두 알고리즘을 적용했을 때의 대기 시간을 비교한 예시이다.

표에서 보듯, SJF는 짧은 작업(P4)을 먼저 처리함으로써 전체 평균 대기 시간을 줄인다. 그러나 SJF는 실행 시간을 미리 알아야 한다는 실질적인 문제와, 실행 시간이 매우 긴 프로세스가 영원히 실행되지 않을 수 있는 기아 현상의 위험이 존재한다. FCFS는 이러한 예측이나 기아 현상에 대한 걱정 없이 공정한 순서를 보장하지만, 전체 시스템의 평균 응답 시간은 SJF에 비해 일반적으로 더 길다.

라운드 로빈 스케줄링은 각 프로세스에 고정된 시간 할당량(타임 퀀텀)을 부여하고, 그 시간 동안만 실행한 후 준비 큐의 맨 뒤로 보내는 방식으로 작동한다. 이는 모든 프로세스가 공정하게 CPU 시간을 나누어 가지게 하여 응답 시간을 개선하는 데 중점을 둔다. 반면, SJF는 실행 시간이 가장 짧은 프로세스를 우선적으로 선택하여 전체 시스템의 평균 대기 시간을 최소화하는 것을 목표로 한다.

두 알고리즘의 핵심 차이는 선점성에 있다. 라운드 로빈은 본질적으로 선점형 스케줄링이며, 타임 퀀텀에 의해 실행 중인 프로세스가 강제로 중단된다. 이는 대화형 시스템에서 사용자에게 빠른 응답을 제공하는 데 유리하다. SJF는 기본적으로 비선점형이지만, 선점형 형태인 SRTF도 존재한다. SRTF는 새로 도착한 프로세스의 남은 실행 시간이 현재 실행 중인 프로세스의 남은 실행 시간보다 짧으면 선점이 발생한다.

성능 측면에서 비교하면 다음과 같은 특징을 보인다.

라운드 로빈은 타임 퀀텀을 무한대로 설정하면 FCFS와 동일하게 동작하며, 매우 짧게 설정하면 프로세스 간 전환이 빈번해져 문맥 교환 오버헤드가 커진다. SJF는 이론적으로 평균 대기 시간을 최소화하지만, 실제로는 프로세스의 정확한 실행 시간을 미리 알 수 없어 예측 기법에 의존해야 한다는 실용적인 어려움이 있다. 또한 긴 작업이 계속해서 뒤로 밀리는 기아 상태가 발생할 수 있다.

우선순위 스케줄링은 각 프로세스에 우선순위를 할당하고, 가장 높은 우선순위를 가진 프로세스를 먼저 실행하는 방식이다. 이는 SJF가 실행 시간이라는 단일 기준을 사용하는 것과 근본적으로 다르다. 우선순위는 실행 시간 외에도 프로세스의 중요도, 자원 요구량, 마감 시간 등 다양한 요소를 반영하여 결정될 수 있다.

두 알고리즘의 핵심 차이는 스케줄링의 기준에 있다. SJF는 다음 표와 같이 예측된 실행 시간만을 기준으로 하여, 가장 짧은 작업을 선호한다. 반면, 우선순위 스케줄링은 숫자로 표현된 우선순위 값이 기준이 되며, 이 값이 작을수록(또는 클수록[5]) 높은 우선순위를 의미한다.

실행 시간이 가장 짧은 프로세스가 사실상 가장 높은 우선순위를 가지는 경우로 볼 수 있으므로, SJF는 우선순위 스케줄링의 특수한 형태라고 설명할 수 있다. 그러나 일반적인 우선순위 스케줄링에서는 실행 시간이 짧더라도 우선순위가 낮으면 뒤로 밀릴 수 있다. 두 알고리즘 모두 낮은 우선순위(또는 긴 실행 시간)를 가진 프로세스가 계속해서 실행 기회를 얻지 못하는 기아 상태 문제를 공유한다. 이를 해결하기 위해 에이징 기법이 사용된다.