프로세스 스케줄링 (r1)

준비 큐는 프로세스 스케줄링에서 실행 준비가 완료된 프로세스들이 대기하는 메모리 내의 자료 구조이다. 이 큐에 위치한 프로세스들은 CPU를 할당받기만 하면 즉시 실행을 시작할 수 있는 상태에 있다. 운영체제의 스케줄러는 일반적으로 준비 큐의 프로세스들 중에서 특정 스케줄링 알고리즘에 따라 다음에 실행할 프로세스를 선택한다.

준비 큐는 보통 연결 리스트와 같은 형태로 구현된다. 각 프로세스의 프로세스 제어 블록(PCB)이 큐에 연결되어 있으며, 스케줄러는 큐의 헤드에서 프로세스를 꺼내어 디스패치하는 방식을 사용한다. 큐의 관리 방식은 사용하는 스케줄링 정책에 따라 달라진다. 예를 들어, 선입선처리(FCFS) 알고리즘에서는 단순한 FIFO 큐를 사용하지만, 우선순위 스케줄링에서는 우선순위에 따라 정렬된 큐를, 라운드 로빈에서는 순환 큐를 사용한다.

프로세스의 상태 변화에 따라 준비 큐의 구성은 지속적으로 변한다. 실행 중이던 프로세스가 타임 슬라이스를 모두 소모하거나 입출력 요청을 발생시키면, 해당 프로세스는 다시 준비 큐의 맨 뒤로 돌아가거나 대기 큐로 이동한다. 반대로, 대기 중이던 입출력 작업이 완료되면 그 프로세스는 대기 큐에서 준비 큐로 재진입하여 CPU 할당을 기다리게 된다.

대기 큐는 입출력 요청을 완료하기 위해 특정 입출력 장치를 기다리는 프로세스들이 대기하는 장소이다. 준비 큐에 있는 프로세스가 CPU를 할당받아 실행되다가 디스크 읽기나 키보드 입력과 같은 입출력 작업을 요청하면, 해당 프로세스는 CPU를 양도하고 요청된 입출력 작업이 완료될 때까지 대기 큐로 이동한다.

대기 큐는 종종 장치별로 별도로 구성된다. 예를 들어, 프린터를 기다리는 프로세스들의 큐, 하드 디스크를 기다리는 프로세스들의 큐 등이 독립적으로 존재할 수 있다. 이는 각 입출력 장치의 속도와 특성이 다르기 때문에 효율적인 관리를 가능하게 한다. 입출력 작업이 완료되면, 해당 장치의 인터럽트가 발생하고, 운영체제는 대기 큐에서 해당 프로세스를 찾아 준비 큐로 다시 옮긴다.

대기 큐에 있는 프로세스는 차단 상태에 있다고 표현한다. 이 상태에서는 CPU를 사용할 수 없으며, 오로지 외부 이벤트(입출력 완료)를 기다린다. 운영체제는 대기 큐를 관리하여 입출력 작업이 완료된 프로세스를 적시에 준비 큐로 전환함으로써 시스템의 전체적인 처리 효율을 유지한다.

장치 큐는 입출력 장치나 파일과 같은 시스템 자원을 기다리는 프로세스들이 대기하는 큐이다. 이 큐는 특정 입출력 장치나 자원에 대한 요청을 처리하기 위해 존재하며, 준비 큐나 대기 큐와는 구분되는 개념이다.

프로세스가 실행 중에 입출력 작업을 요청하면, 운영체제는 해당 프로세스를 실행 상태에서 중단시키고, 요청한 장치에 해당하는 장치 큐로 이동시킨다. 예를 들어, 디스크 읽기 작업을 요청한 프로세스는 디스크 컨트롤러에 연결된 장치 큐에 들어가게 된다. 장치 컨트롤러가 해당 입출력 작업을 완료하면, 프로세스는 장치 큐에서 제거되어 준비 큐로 돌아가 CPU 할당을 다시 기다리게 된다.

각 입출력 장치는 일반적으로 독립적인 장치 큐를 가진다. 이는 여러 프로세스가 동일한 자원(예: 프린터, 디스크 드라이브)을 동시에 요청할 때, 요청 순서에 따라 순차적으로 서비스를 받을 수 있도록 질서를 유지하기 위함이다. 장치 큐의 관리 방식은 스풀링 기술과 밀접한 관련이 있으며, 디스크 스케줄링 알고리즘과 같은 특정 장치별 스케줄링 정책의 적용 대상이 되기도 한다.

선입선처리(FCFS, First-Come, First-Served)는 가장 단순한 CPU 스케줄링 알고리즘이다. 이 방식은 이름 그대로 준비 큐에 도착한 순서대로 프로세스에 CPU를 할당한다. 즉, 먼저 요청한 프로세스가 먼저 처리된다. 이 알고리즘은 일반적으로 비선점형 스케줄링 방식으로 구현되어, 한 프로세스가 CPU를 점유하면 그 프로세스의 실행이 완료되거나 입출력 요청으로 인해 자발적으로 CPU를 양도할 때까지 다른 프로세스가 CPU를 빼앗지 못한다.

FCFS 알고리즘의 성능은 작업의 도착 순서와 실행 시간에 크게 의존한다. 긴 실행 시간을 가진 프로세스가 먼저 도착하면, 그 뒤에 도착한 짧은 작업들은 긴 대기 시간을 겪게 된다. 이 현상을 '호위 효과'(convoy effect)라고 부른다. 예를 들어, 실행 시간이 매우 긴 P1 프로세스 뒤에 실행 시간이 짧은 P2, P3 프로세스가 대기하고 있다면, P2와 P3는 P1이 끝날 때까지 오랜 시간을 기다려야 하며, 이로 인해 평균 대기 시간과 평균 반환 시간이 크게 증가한다.

위 표는 P1(24ms), P2(3ms), P3(3ms) 순서로 도착했을 때의 FCFS 스케줄링 예시이다. 평균 대기 시간은 (0 + 23 + 26) / 3 = 16.33ms, 평균 반환 시간은 (24 + 26 + 29) / 3 = 26.33ms가 된다. 만약 도착 순서가 P2, P3, P1이라면 평균 대기 시간과 반환 시간은 현저히 줄어들게 된다.

이 알고리즘의 주요 장점은 구현이 매우 간단하고 공정하다는 점이다. 그러나 호위 효과로 인해 처리량이 감소하고, 대화형 시스템에서의 응답시간이 매우 나빠질 수 있어 현대의 시분할 시스템에는 적합하지 않다. 따라서 FCFS는 종종 다른 복잡한 스케줄링 알고리즘의 일부 구성 요소로 사용되거나, 특정 다단계 큐 스케줄링의 일부 큐에서 적용된다.

최단작업우선 스케줄링(SJF, Shortest Job First)은 이름 그대로 CPU 버스트 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 알고리즘이다. 비선점형 방식으로 구현되는 경우가 일반적이며, 이때는 프로세스가 CPU를 점유한 후 작업을 완료할 때까지 다른 프로세스가 선점하지 못한다. 이 알고리즘의 핵심 아이디어는 평균 대기 시간을 최소화하는 것이다. 짧은 작업을 먼저 처리함으로써 많은 프로세스가 빠르게 완료되어 전체 시스템의 평균 반환 시간과 대기 시간이 줄어든다.

SJF 스케줄링의 성능은 이상적인 조건에서 다른 알고리즘들보다 우수한 경우가 많다. 하지만 실제 시스템에서 적용하기에는 심각한 문제점을 안고 있다. 가장 큰 문제는 다음에 실행될 프로세스의 CPU 버스트 시간을 정확히 예측하기가 매우 어렵다는 점이다. 이를 해결하기 위해 과거의 CPU 버스트 기록을 바탕으로 지수 평균(exponential averaging) 등의 방법을 사용해 미래 버스트 시간을 추정하지만, 이는 근사치에 불과하다.

SJF의 또 다른 문제는 기아 현상(Starvation)이 발생할 수 있다는 것이다. 만약 짧은 작업이 계속해서 준비 큐에 들어오면, CPU 버스트 시간이 긴 프로세스는 무한정 CPU를 할당받지 못하고 대기하게 될 수 있다. 이 문제를 완화하기 위해 에이징(Aging) 기법을 도입하는 경우가 있다.

선점형 형태의 SJF는 최소잔여시간우선(SRTF, Shortest Remaining Time First)이라고도 불린다. SRTF는 새 프로세스가 도착할 때마다 현재 실행 중인 프로세스의 잔여 시간과 새 프로세스의 총 실행 시간을 비교하여 더 짧은 작업을 즉시 실행한다. 이는 이론적으로 평균 대기 시간을 더욱 줄일 수 있지만, 빈번한 문맥 교환으로 인한 오버헤드가 커질 수 있다.

우선순위 스케줄링은 각 프로세스에 우선순위를 부여하고, 준비 상태 큐에서 가장 높은 우선순위를 가진 프로세스를 먼저 실행하는 CPU 스케줄링 방식이다. 우선순위는 일반적으로 정수로 표현되며, 숫자가 작을수록 높은 우선순위를 의미하거나 그 반대의 경우도 있다[1]. 이 방식의 핵심은 시스템의 요구사항에 따라 중요한 작업이 먼저 CPU를 할당받도록 하는 것이다.

우선순위는 내부적 또는 외부적으로 결정될 수 있다. 내부적 우선순위는 시간 제한, 메모리 요구량, 열린 파일 수 등 프로세스 자체의 특성을 기반으로 시스템이 정한다. 외부적 우선순위는 프로세스의 중요도, 사용자 등급, 비용 등 운영체제 외부의 요소에 의해 결정된다. 우선순위 스케줄링은 선점형과 비선점형 방식 모두로 구현 가능하다. 선점형에서는 더 높은 우선순위의 프로세스가 도착하면 현재 실행 중인 프로세스를 선점한다.

이 방식의 주요 문제점은 기아 상태가 발생할 수 있다는 점이다. 낮은 우선순위를 가진 프로세스는 준비 큐에 계속 남아 있어 영원히 실행되지 못할 수 있다. 이 문제를 해결하기 위한 일반적인 방법은 에이징이다. 에이징은 시스템이 대기 중인 프로세스의 우선순위를 시간이 지남에 따라 점진적으로 높여, 결국에는 실행될 기회를 보장하는 기법이다.

라운드 로빈 스케줄링은 선점형 스케줄링 방식의 대표적인 알고리즘이다. 이 방법은 각 프로세스에 고정된 시간 할당량, 즉 타임 퀀텀을 부여하고, 준비 큐를 순환하는 방식으로 CPU를 할당한다. 프로세스는 자신에게 주어진 타임 퀀텀 동안만 CPU를 사용할 수 있으며, 시간이 만료되면 CPU를 강제로 선점당하고 준비 큐의 맨 뒤로 이동한다. 만약 프로세스가 타임 퀀텀을 다 쓰기 전에 입출력 작업 등으로 CPU를 자발적으로 양도하면, 대기 상태에서 준비 상태로 돌아올 때 다시 준비 큐의 맨 뒤에 배치된다.

이 알고리즘의 핵심 매개변수는 타임 퀀텀의 크기이다. 타임 퀀텀이 매우 크면 선입선처리 스케줄링과 유사하게 동작하며, 반대로 매우 작으면 프로세스 간의 전환이 매우 빈번해져 문맥 교환 오버헤드가 커진다. 따라서 적절한 크기의 타임 퀀텀을 설정하는 것이 성능에 결정적이다. 일반적으로 타임 퀀텀은 문맥 교환에 소요되는 시간의 수십 배 정도로 설정하여 시스템 효율성을 유지한다.

라운드 로빈 스케줄링의 성능 특징은 다음과 같다.

이 방식은 특히 시분할 시스템이나 대화형 시스템에서 널리 사용된다. 모든 프로세스가 정기적으로 CPU 시간을 공평하게 나누어 받기 때문에 사용자에게 빠른 응답을 제공할 수 있다는 장점이 있다.

다단계 큐 스케줄링은 프로세스를 여러 개의 준비 큐로 분리하여 각 큐마다 서로 다른 스케줄링 알고리즘과 우선순위를 적용하는 방식이다. 이 방법은 프로세스의 특성(예: 시스템 프로세스, 대화형 프로세스, 배치 프로세스 등)에 따라 구분하여 관리할 수 있게 한다. 각 큐는 고정된 우선순위를 가지며, 일반적으로 상위 큐의 모든 프로세스가 실행을 완료한 후에야 하위 큐의 프로세스가 CPU를 할당받을 수 있다. 큐 간의 이동은 일반적으로 제한적이거나 특정 규칙에 의해서만 허용된다.

큐 내부에서는 독립적인 스케줄링이 이루어진다. 예를 들어, 시스템 프로세스가 속한 최상위 큐는 우선순위 스케줄링을, 대화형 프로세스 큐는 라운드 로빈 알고리즘을, 백그라운드 배치 작업 큐는 선입선처리 방식으로 스케줄링할 수 있다. 또한, 프로세스가 너무 오래 CPU를 점유하는 것을 방지하기 위해 각 큐마다 다른 타임 슬라이스를 부여할 수도 있다.

이 방식의 변형으로 다단계 피드백 큐 스케줄링이 있다. 다단계 피드백 큐는 프로세스가 큐 간에 이동할 수 있는 동적인 구조를 가진다. 예를 들어, CPU 사용 시간이 긴 프로세스는 낮은 우선순위의 큐로 강등되고, 입출력 대기 시간이 많은 프로세스는 높은 우선순위의 큐로 승격될 수 있다. 이는 에이징 기법을 구현하여 기아 상태를 완화하는 데 도움을 준다.

다단계 큐 스케줄링의 장단점은 다음과 같이 정리할 수 있다.

이 방식은 현대 운영체제에서 프로세스의 특성에 따른 차별화된 서비스가 필요할 때 널리 활용된다.

CPU 이용률은 프로세스 스케줄링의 성능을 평가하는 핵심 기준 중 하나로, 주어진 시간 동안 중앙처리장치가 실제로 작업을 처리한 시간의 비율을 의미한다. 이는 시스템 자원의 효율성을 나타내는 지표로, 일반적으로 백분율(%)로 표현된다. 이상적으로는 CPU가 유휴(idle) 상태에 머무르지 않고 항상 유용한 작업을 수행하여 이용률을 100%에 가깝게 유지하는 것이 바람직하다.

CPU 이용률은 시스템의 전반적인 처리 능력과 직결된다. 낮은 CPU 이용률은 프로세서가 작업을 기다리는 시간이 많음을 의미하며, 이는 입출력 작업이 빈번하거나 프로세스 간 동기화 문제로 인해 대기 시간이 길어지는 경우 등에서 발생할 수 있다. 반대로, 이용률이 지나치게 높으면 시스템의 여유가 부족해져 새로운 작업이나 긴급한 작업의 처리가 지연될 수 있다. 따라서 스케줄링 알고리즘은 단순히 이용률만을 극대화하기보다는 다른 기준들과의 균형을 고려하여 설계된다.

실제 시스템에서는 멀티태스킹 환경에서 여러 프로세스가 시분할 방식으로 CPU를 공유하며, 인터럽트 처리, 컨텍스트 스위칭 오버헤드, 입출력 대기 시간 등의 요소로 인해 이론적인 100% 이용률에 도달하는 것은 불가능하다. 스케줄러는 이러한 요소들을 최소화하면서 가능한 한 CPU를 바쁘게 유지하는 방향으로 동작한다. 성능 모니터링 도구를 통해 CPU 이용률을 지속적으로 관찰함으로써 시스템의 병목 현상을 파악하고 튜닝의 근거로 활용할 수 있다.

처리량은 단위 시간당 시스템이 완료한 프로세스의 수를 나타내는 지표이다. 일반적으로 초당 또는 분당 완료된 프로세스의 개수로 측정된다. 처리량은 시스템의 전체적인 생산성과 효율성을 평가하는 핵심 기준 중 하나이다.

높은 처리량은 시스템이 많은 작업을 빠르게 처리하고 있음을 의미한다. 처리량은 스케줄링 알고리즘의 효율성, CPU의 성능, 입출력 작업의 빈도와 속도 등 여러 요인에 의해 영향을 받는다. 예를 들어, 최단작업우선 (SJF) 알고리즘은 평균적으로 선입선처리 (FCFS) 알고리즘보다 더 높은 처리량을 보이는 경향이 있다[2].

다음 표는 서로 다른 스케줄링 정책이 동일한 작업 집합에 적용되었을 때의 처리량 비교 예시를 보여준다.

그러나 처리량만을 극대화하는 것은 다른 성능 지표를 악화시킬 수 있다. 예를 들어, 처리량을 높이기 위해 항상 가장 짧은 작업을 먼저 실행하면, 긴 작업의 대기시간이 매우 길어져 기아 상태가 발생할 수 있다. 따라서 시스템 설계자는 처리량, 반환시간, 응답시간 등을 종합적으로 고려하여 적절한 스케줄링 정책을 선택해야 한다.

반환시간은 특정 프로세스가 시스템에 제출된 시점부터 실행이 완료되어 결과를 반환할 때까지 걸린 총 시간을 의미한다. 이는 대기시간과 실제 CPU에서 실행된 시간(실행 시간)을 합한 값이다. 반환시간은 사용자 관점에서 작업이 완료되기까지 얼마나 기다려야 하는지를 나타내는 가장 직접적인 지표 중 하나이다.

반환시간은 시스템의 전반적인 반응성을 평가하는 데 중요한 기준이 된다. 예를 들어, 대화형 시스템에서는 짧은 반환시간이 사용자 경험에 긍정적인 영향을 미친다. 반환시간을 계산하는 일반적인 공식은 '완료 시간 - 도착 시간'이다. 여기서 도착 시간은 프로세스가 준비 큐에 들어온 시점을, 완료 시간은 프로세스의 실행이 종료된 시점을 가리킨다.

위 표는 세 개의 프로세스에 대한 반환시간 계산 예시를 보여준다. 평균 반환시간은 (5 + 7 + 14) / 3 = 8.67이 된다. 스케줄링 알고리즘은 평균 반환시간을 최소화하는 것을 주요 목표 중 하나로 삼는다. 일반적으로 최단작업우선 스케줄링 알고리즘이 평균 반환시간을 최소화하는 데 가장 효과적이다[3].

대기시간은 프로세스가 준비 상태에 머무르며 CPU를 할당받기 위해 기다린 시간의 총합을 의미한다. 이는 준비 큐에서의 대기 시간만을 포함하며, 입출력 작업을 위한 대기나 다른 이벤트를 기다리는 시간은 포함하지 않는다. 대기시간은 스케줄링 알고리즘의 효율성을 평가하는 핵심 지표 중 하나이다.

대기시간은 각 프로세스의 개별 대기시간을 계산한 후, 모든 프로세스의 대기시간을 평균하여 구한다. 예를 들어, 세 개의 프로세스 P1, P2, P3가 각각 10ms, 1ms, 2ms 동안 대기했다면, 평균 대기시간은 (10 + 1 + 2) / 3 = 4.33ms가 된다. 짧은 평균 대기시간은 프로세스가 준비 큐에서 불필요하게 오래 머무르지 않았음을 의미하며, 이는 시스템의 반응성이 좋고 자원 활용이 효율적임을 시사한다.

표에서 볼 수 있듯이, 최단작업우선 알고리즘은 일반적으로 평균 대기시간을 최소화하는 데 가장 효과적이다. 반면, 선입선처리 알고리즘은 긴 프로세스가 먼저 도착할 경우 뒤의 짧은 프로세스들의 대기시간을 크게 증가시키는 호위 효과를 일으켜 평균 대기시간이 나빠질 수 있다.

응답시간은 프로세스 스케줄링 성능을 평가하는 중요한 기준 중 하나이다. 이는 시스템에 작업을 제출한 시점부터 첫 번째 응답이 발생할 때까지 걸리는 시간을 의미한다. 특히 대화형 시스템이나 시분할 시스템에서 사용자 경험과 시스템의 반응성을 직접적으로 나타내는 지표로 사용된다.

응답시간은 일반적으로 요청을 보낸 후, 첫 번째 출력이 나오거나 결과의 일부가 사용자에게 전달되는 데까지 걸리는 시간으로 정의된다. 이는 작업이 완료될 때까지의 총 시간을 의미하는 반환시간과 구별되는 개념이다. 예를 들어, 긴 작업을 실행할 때 사용자는 최종 결과를 얻기 전에 작업이 시작되었음을 나타내는 초기 피드백을 빠르게 받기를 원한다.

응답시간을 최소화하는 것은 사용자에게 빠른 피드백을 제공하여 시스템이 반응적이라고 느끼게 하는 데 중요하다. 라운드 로빈과 같은 스케줄링 알고리즘은 짧은 시간 할당량을 사용함으로써 응답시간을 개선하는 데 초점을 맞춘다. 반면, 최단작업우선 알고리즘은 평균 대기시간을 최소화할 수 있지만, 긴 작업이 짧은 작업을 계속해서 대기시킬 경우 응답시간이 나빠질 수 있다.