선점형 스케줄링

선점형 스케줄링에서 '선점'은 운영체제가 실행 중인 프로세스로부터 강제로 CPU 사용권을 회수하여 다른 프로세스에게 할당할 수 있는 권한을 의미한다. 이는 시분할 시스템의 핵심 원리로, 각 프로세스에 정해진 시간 할당량(Time Slice)이 지나면 현재 실행 중인 작업을 중단시키고 CPU를 다른 준비된 프로세스에게 넘겨주는 방식으로 작동한다.

이러한 선점의 핵심은 운영체제가 스케줄링 결정을 주도적으로 내릴 수 있는 시점에 있다. 주요 선점 시점으로는 프로세스의 시간 할당량이 만료되었을 때, 더 높은 우선순위를 가진 프로세스가 준비 큐에 도착했을 때, 또는 실행 중인 프로세스가 입출력 요청과 같은 이벤트를 기다리게 되어 자발적으로 CPU를 양도할 때 등이 있다. 이는 비선점형 스케줄링이 프로세스가 스스로 CPU를 반납할 때까지 기다리는 것과 대비되는 특징이다.

선점 방식을 통해 단일 프로세스가 CPU를 독점하는 것을 방지하고, 여러 프로세스가 짧은 시간 간격으로 번갈아 실행되도록 함으로써 시스템의 전체적인 반응성과 공정성을 높일 수 있다. 이는 대화형 시스템이나 실시간 시스템에서 빠른 응답 시간을 보장하는 데 필수적이다.

선점형 스케줄링에서 스케줄링 결정이 이루어지는 시점은 여러 가지가 있다. 가장 대표적인 시점은 할당된 시간 할당량(Time Slice)이 만료되었을 때이다. 라운드 로빈 알고리즘은 이 원리를 기반으로 하여, 각 프로세스가 정해진 시간 동안만 CPU를 사용한 후, 타이머 인터럽트에 의해 강제로 문맥 교환(Context Switch)이 발생하도록 한다.

또 다른 중요한 결정 시점은 더 높은 우선순위를 가진 프로세스가 준비 완료 상태가 되었을 때이다. 우선순위 선점 스케줄링에서는 현재 실행 중인 프로세스보다 우선순위가 높은 새로운 프로세스가 준비 큐(Ready Queue)에 들어오면, 즉시 선점이 발생하여 CPU가 더 높은 우선순위의 프로세스에게 할당된다. 이는 시스템의 응답성을 높이는 데 기여한다.

입출력 완료나 인터럽트 처리와 같은 이벤트 발생 후에도 스케줄링 결정이 이루어진다. 예를 들어, 대기 중이던 프로세스의 입출력 작업이 끝나면, 그 프로세스는 준비 완료 상태로 전환된다. 이때 스케줄러는 현재 실행 중인 프로세스와 새로 준비된 프로세스의 우선순위나 남은 실행 시간 등을 비교하여 선점 여부를 결정하게 된다. 최단 잔여 시간 우선 스케줄링은 이러한 시점에서 남은 실행 시간이 더 짧은 프로세스로 선점하는 방식이다.

라운드 로빈은 운영체제의 CPU 스케줄링 방식 중 가장 대표적인 선점형 스케줄링 알고리즘이다. 이 방식의 핵심은 각 프로세스에 고정된 시간 할당량, 즉 타임 슬라이스를 부여하고, 그 시간이 경과하면 현재 실행 중인 프로세스를 선점하여 준비 완료 큐의 다음 프로세스에게 CPU 사용권을 넘겨주는 것이다. 이 과정은 모든 프로세스가 순환하며 CPU 시간을 공평하게 나누어 사용하도록 설계되어 있다.

이 알고리즘은 특히 시분할 시스템에 매우 적합하며, 모든 프로세스가 정해진 시간 간격으로 CPU를 사용할 기회를 얻기 때문에 응답 시간이 짧고 대화형 시스템에서 사용자에게 빠른 피드백을 제공할 수 있다는 장점이 있다. 또한, FIFO 큐를 사용하여 구현되기 때문에 스케줄링 자체가 단순하고 공정하다는 특징을 가진다.

라운드 로빈의 성능은 타임 슬라이스의 크기에 크게 의존한다. 타임 슬라이스가 매우 크게 설정되면, 사실상 비선점형 스케줄링인 FCFS 방식과 유사해져 응답 시간이 길어질 수 있다. 반대로 타임 슬라이스가 지나치게 짧으면 문맥 교환이 빈번하게 발생하여 시스템의 오버헤드가 증가하고 전체적인 처리 효율이 떨어지는 문제가 발생한다. 따라서 시스템의 특성과 요구 사항에 맞춰 적절한 타임 슬라이스 값을 설정하는 것이 중요하다.

이 알고리즘은 멀티태스킹이 필요한 현대 운영체제의 기본 스케줄링 정책의 토대를 제공하며, 최단 잔여 시간 우선이나 다단계 피드백 큐 같은 더 복잡한 선점형 알고리즘들도 라운드 로빈의 기본 원리를 확장하거나 조합하여 사용한다.

최단 잔여 시간 우선 스케줄링은 선점형 스케줄링의 대표적인 알고리즘 중 하나이다. 이 방식은 최단 작업 우선 스케줄링의 선점형 버전으로, 현재 실행 중인 프로세스의 남은 실행 시간과 준비 큐에 도착한 다른 프로세스의 실행 시간을 비교하여 가장 짧은 잔여 시간을 가진 프로세스에게 CPU를 할당한다. 따라서 새로운 프로세스가 도착하거나 실행 중인 프로세스의 잔여 시간이 갱신될 때마다 스케줄링 결정이 이루어진다.

이 알고리즘의 핵심 목표는 평균 대기 시간을 최소화하는 것이다. 실행 시간이 짧은 작업을 우선적으로 처리함으로써 시스템 전체의 처리 효율을 높이고, 대기 중인 프로세스들의 응답 시간을 개선할 수 있다. 이론적으로는 최단 작업 우선 스케줄링과 동일한 성능을 보이지만, 선점이 가능하기 때문에 더 짧은 작업이 중간에 도착했을 때 즉시 대응할 수 있어 실시간 시스템 환경에 더 유리한 특징을 가진다.

그러나 최단 잔여 시간 우선 방식은 프로세스의 정확한 실행 시간을 미리 알아야 한다는 근본적인 한계가 있다. 실제 시스템에서는 프로세스의 총 실행 시간을 예측하기 어려운 경우가 많아, 추정치를 사용하게 되면 오히려 스케줄링 효율이 떨어질 수 있다. 또한, 실행 시간이 긴 프로세스는 계속해서 선점당할 가능성이 높아 기아 상태에 빠질 위험이 존재한다.

이러한 특성 때문에 최단 잔여 시간 우선 스케줄링은 주로 배치 처리 시스템이나 실행 시간을 비교적 정확히 예측할 수 있는 특수한 환경에서 이론적 모델로 연구되며, 일반적인 시분할 시스템에서는 실행 시간 예측의 어려움을 보완한 라운드 로빈이나 다단계 피드백 큐 같은 다른 선점형 알고리즘이 더 널리 사용된다.

우선순위 선점 스케줄링은 각 프로세스에 미리 부여된 우선순위에 따라 CPU를 할당하는 선점형 스케줄링 방식이다. 이 방식에서는 높은 우선순위를 가진 프로세스가 준비 큐에 들어오면, 현재 실행 중인 낮은 우선순위의 프로세스를 선점하여 CPU를 빼앗을 수 있다. 우선순위는 일반적으로 정수 값으로 표현되며, 숫자가 작을수록 높은 우선순위를 의미하거나 그 반대의 경우도 있다. 우선순위는 프로세스의 중요도, 실행 시간, 자원 요구량 등의 요소를 바탕으로 정적 또는 동적으로 결정될 수 있다.

이 알고리즘의 주요 구현 방식에는 두 가지가 있다. 첫째는 우선순위가 프로세스 생성 시 결정된 후 변경되지 않는 정적 우선순위 방식이다. 둘째는 시스템 상황에 따라 프로세스의 우선순위를 실행 중에 동적으로 조절하는 동적 우선순위 방식이다. 동적 조절은 에이징 기법을 통해 구현될 수 있는데, 이는 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여 기아 상태를 완화하는 방법이다.

우선순위 선점 스케줄링의 가장 큰 장점은 중요한 작업이 빠르게 처리될 수 있다는 점이다. 그러나 단점도 명확한데, 우선순위가 낮은 프로세스는 CPU를 할당받지 못하고 무한정 대기하는 기아 현상이 발생할 수 있다. 또한, 우선순위가 높은 프로세스가 지속적으로 들어오는 경우, 다른 프로세스들의 실행이 지연되어 전체 시스템의 처리율이 떨어질 수도 있다. 따라서 실제 시스템에서는 에이징과 같은 보완 기법을 함께 적용하여 이러한 문제점을 해결한다.

다단계 큐 스케줄링은 운영체제의 CPU 스케줄링 방식 중 하나로, 준비 상태의 프로세스들을 서로 다른 특성이나 우선순위에 따라 여러 개의 독립적인 큐로 분류하여 관리하는 선점형 알고리즘이다. 각 큐는 고유한 스케줄링 알고리즘을 가질 수 있으며, 큐 간에는 고정된 우선순위가 존재하여 상위 우선순위 큐의 프로세스들이 먼저 실행된다. 이 방식은 시스템 작업과 사용자 작업, 대화형 작업과 배치 작업 등 서로 다른 성격의 작업을 효율적으로 구분하여 처리할 수 있게 한다.

다단계 큐 스케줄링의 핵심은 큐 간의 스케줄링과 큐 내부의 스케줄링을 분리하는 것이다. 일반적으로 시스템 프로세스나 실시간 프로세스와 같은 높은 우선순위를 가진 작업들은 별도의 큐에 배치되며, 라운드 로빈이나 우선순위 스케줄링과 같은 빠른 응답이 가능한 알고리즘으로 관리된다. 반면, 계산 중심의 배치 작업들은 다른 큐에 배치되어 FCFS와 같은 알고리즘으로 처리될 수 있다. 상위 큐가 비어 있을 때만 하위 큐의 프로세스들이 실행 기회를 얻는다.

이 방식의 주요 장점은 시스템의 다양한 작업 유형에 맞춤형 스케줄링 정책을 적용할 수 있어 전체 시스템 성능을 최적화할 수 있다는 점이다. 또한, 우선순위가 높은 중요한 작업이 지연 없이 신속히 처리될 수 있다. 그러나 단점으로는 우선순위가 낮은 큐에 배치된 프로세스들은 상위 큐에 계속해서 작업이 들어오는 경우 기아 상태에 빠질 수 있으며, 프로세스가 한 번 특정 큐에 할당되면 다른 큐로 이동하지 않는 경직성을 보인다는 점이 있다.

이러한 경직성을 보완하기 위해 개발된 변형 알고리즘이 다단계 피드백 큐 스케줄링이다. 다단계 피드백 큐는 프로세스의 행동(예: CPU 버스트 시간)을 관찰하여 그에 따라 프로세스가 속한 큐의 우선순위를 동적으로 조정하거나 다른 큐로 이동시킬 수 있어, 다단계 큐의 단점을 상당 부분 해결한다.

선점형 스케줄링의 가장 큰 장점은 빠른 응답 시간을 보장한다는 점이다. 운영체제가 실행 중인 프로세스로부터 CPU 사용권을 강제로 회수할 수 있기 때문에, 짧은 시간 안에 여러 프로세스가 번갈아 실행될 수 있다. 이는 특히 시분할 시스템이나 대화형 시스템에서 사용자에게 즉각적인 반응을 제공해야 할 때 매우 중요하다. 모든 작업이 조금씩 빠르게 처리되므로, 시스템 전체의 반응성이 향상된다.

또한, 이 방식은 공정성 측면에서도 유리하다. 라운드 로빈과 같은 알고리즘을 사용하면 각 프로세스에 고정된 시간 할당량이 주어지기 때문에, 하나의 프로세스가 CPU를 독점하여 다른 프로세스의 실행을 무한정 기다리게 하는 기아 상태를 방지할 수 있다. 모든 프로세스가 정해진 순서와 시간에 따라 CPU를 사용할 기회를 얻으므로, 시스템 자원의 공정한 분배가 가능해진다.

마지막으로, 선점형 스케줄링은 실시간 시스템의 요구사항을 충족시키는 데 필수적이다. 최단 잔여 시간 우선 스케줄링이나 우선순위 선점 스케줄링을 활용하면, 더 긴급한 작업이나 처리 시간이 짧은 작업을 즉시 중단된 작업보다 먼저 실행할 수 있다. 이를 통해 데드라인이 중요한 작업이나 높은 우선순위를 가진 인터럽트 처리를 신속하게 수행할 수 있어, 시스템의 예측 가능성과 신뢰성을 높이는 데 기여한다.

선점형 스케줄링은 문맥 교환이 빈번하게 발생한다는 근본적인 단점을 가진다. 실행 중인 프로세스를 강제로 중단하고 CPU를 다른 프로세스에 할당할 때마다 현재 프로세스의 상태를 저장하고 새 프로세스의 상태를 복원하는 오버헤드가 수반된다. 이 오버헤드는 시스템 자원을 소모하며, 특히 타임 슬라이스가 지나치게 짧게 설정된 경우 전체 시스템 성능을 저하시킬 수 있다.

또한, 높은 우선순위의 프로세스가 지속적으로 도착할 경우, 우선순위 스케줄링에서 발생할 수 있는 기아 현상과 유사하게, 낮은 우선순위의 프로세스는 CPU를 할당받지 못하고 오랜 시간 대기할 수 있다. 다단계 피드백 큐와 같은 복잡한 알고리즘은 이러한 문제를 완화하려고 설계되지만, 그만큼 스케줄러의 구현과 관리가 복잡해진다.

마지막으로, 실시간 시스템과 같은 특정 환경에서는 예측 불가능한 선점으로 인해 시간적 제약 조건을 보장하기 어려울 수 있다. 중요한 임계 구역을 처리 중인 프로세스가 갑자기 선점당하면 공유 자원의 일관성이 깨질 위험이 있으며, 이는 시스템의 신뢰성에 직접적인 영향을 미친다. 따라서 동기화 메커니즘을 추가로 설계하여 보호해야 하는 부담이 있다.