CPU 스케쥴링 및 스케쥴링 알고리즘

 

CPU 스케쥴링.

CPU 스케줄링(CPU Scheduling)은 운영체제에서 여러 프로세스들이 CPU를 공유하여 실행될 때, 
어떤 프로세스가 CPU를 할당받을지 결정하는 작업입니다. 
CPU 스케줄링은 시분할 시스템에서는 작은 시간 단위로 스위칭되는 인터랙티브한 환경부터 
배치 처리 시스템에서의 장기 스케줄링까지 다양한 상황에서 필요합니다.

** 관련 용어 알아보기 

CPU 스케쥴러.
CPU가 유휴 상태가 되면 준비완료 큐에 있는 프로세스를 하나 선택해서 실행합니다.
이 선택은 CPU 스케쥴러(또는 단기 스케쥴러)가 합니다.

Dispatcher.
스케쥴러가 선택한 프로세스를 CPU에 할당해주는 요소를 디스패처라고 합니다.
디스패처는 문맥 전환, 모드 전환 등의 업무를 담당하고
하나의 프로세스를 중단하고 다른 프로세스를 실행하기까지 소요되는 시간을 디스패치 지연 시간이라고 합니다.


CPU 스케줄링 알고리즘은 다음과 같은 기준을 가지고 선택됩니다.

CPU 사용 효율(CPI utilization).
가능한 CPU가 계속 유용한 작업을 하도록 해야합니다.
만약 어떤 정해진 시간 동안 계속 CPU가 유용한 작업을 했다면 
CPU 사용 효용은 100%가 됩니다.

처리율(throughput).
시간당 완료되는 프로세스의 수

반환시간(turnaround time).
하나의 프로세스가 제시된 시점에서 그 프로세스가 종료 될 때까지 걸린 시간

대기시간(waiting time).
한 프로세스가 준비완료 큐에서 대기한 총 시간

응답시간(response time).
서비스를 요청한 후에 그 서비스에 대한 첫 반응이 나오기까지 걸린 시간

위 기준은 사용자 관점(반환시간,  응답시간 등)과 시스템 관점(CPU 사용 효율, 처리율) 등으로 나눌 수 있습니다.
CPU 사용 효율과 처리율은 최대화하고 반환시간, 대기시간, 응답시간은 최소화하는 알고리즘이 가장 이상적이다.
응답시간의 경우에는 평균 응답시간을 최소화하는 것보다 편차를 최소화하는 것이 더 우수한 알고리즘이라고 보는 경향도 있습니다.

 

스케쥴링 알고리즘.

FCFS 스케줄링(First-Come First-Served).

FCFS 스케줄링(First-Come First-Served Scheduling)은 가장 간단하고 직관적인 CPU 스케줄링 알고리즘 중 하나입니다. 이 알고리즘은 프로세스가 도착한 순서대로 CPU를 할당하는 방식으로 동작합니다. 즉, 먼저 도착한 프로세스가 먼저 실행되고, 그 다음으로 도착한 프로세스가 실행되는 방식입니다.

FCFS 스케줄링의 주요 특징은 다음과 같습니다:

비선점 스케줄링: FCFS 스케줄링은 비선점 스케줄링(non-preemptive scheduling) 알고리즘입니다. 한 번 CPU를 할당받으면 해당 프로세스가 종료되거나 대기 상태로 전환될 때까지 계속해서 CPU를 점유합니다.

대기 시간: 프로세스는 도착한 순서대로 실행되기 때문에, 먼저 도착한 프로세스가 먼저 CPU를 할당받으므로, 대기 시간이 상대적으로 길어질 수 있습니다. 도착 시간이 빠른 프로세스가 먼저 실행되기 때문에, 대기 시간이 긴 프로세스의 경우 평균 대기 시간이 증가할 수 있습니다.

공정성: FCFS 스케줄링은 공정한 스케줄링 알고리즘이라고 할 수 있습니다. 먼저 도착한 프로세스부터 순서대로 실행되기 때문에, 각 프로세스는 동일한 실행 기회를 가집니다.

선점 불가능: 한 번 CPU를 할당받으면 해당 프로세스가 종료되거나 대기 상태로 전환될 때까지 CPU를 점유하기 때문에, 다른 프로세스가 높은 우선순위를 가지더라도 선점할 수 없습니다. 따라서, 우선순위나 실행 시간에 따른 동적인 프로세스 관리가 어렵습니다.

FCFS 스케줄링은 구현이 간단하고 공정성이 보장되는 장점이 있으나, 평균 대기 시간이 길어지는 문제가 있습니다. 따라서, 프로세스의 도착 시간과 실행 시간을 예측하여 사용하는 시스템에서는 더 효율적인 스케줄링 알고리즘을 고려해야 합니다.

SJF 스케쥴링(Shortest-Job-First).
SJF 스케쥴링 알고리즘은 다음 CPU 버스트 시간이 가장 짧은 프로세스 순으로 스케쥴링합니다.
만약 프로세스가 같은 CPU 버스트 시간을 가지면 FCFS 정책을 따릅니다.
SJF 알고리즘은 평균 대기 시간 측면에서는 최적에 가깝습니다.

하지만 프로세스의 다음 CPU버스트 시간을 예측하는 것이 어려워
이전의 CPU버스트들의 길이를 지수 평균하여 구합니다.

우선순위 스케쥴링(Priority Scheduling).
우선순위 스케줄링(Priority Scheduling)은 CPU 스케줄링 알고리즘 중 하나로, 프로세스에 우선순위를 부여하여 해당 우선순위에 따라 CPU를 할당하는 방식입니다. 각 프로세스는 특정 우선순위 값을 가지며, 더 높은 우선순위를 가진 프로세스가 먼저 실행되는 특징을 가지고 있습니다.

우선순위 스케줄링의 주요 특징은 다음과 같습니다:

선점과 비선점: 우선순위 스케줄링은 선점(preemptive) 또는 비선점(non-preemptive) 방식으로 구현될 수 있습니다. 선점 우선순위 스케줄링은 현재 실행 중인 프로세스보다 높은 우선순위를 가진 프로세스가 도착하면 CPU를 선점하여 실행 중인 프로세스를 중단시킬 수 있습니다. 반면, 비선점 우선순위 스케줄링은 한 번 CPU를 할당받은 프로세스는 실행을 완료하거나 대기 상태로 전환될 때까지 CPU를 점유합니다.

우선순위 부여: 각 프로세스는 특정 우선순위 값을 가지며, 우선순위는 다양한 요소에 기반하여 할당될 수 있습니다. 예를 들어, 긴급한 작업 또는 중요한 작업에 높은 우선순위를 부여할 수 있습니다. 우선순위는 정수 값으로 표현되며, 일반적으로 높은 값이 더 높은 우선순위를 의미합니다.

대기 시간: 우선순위 스케줄링에서는 우선순위가 높은 프로세스가 먼저 실행되기 때문에 상대적으로 낮은 우선순위를 가진 프로세스의 대기 시간이 증가할 수 있습니다. 따라서, 우선순위 스케줄링에서는 평균 대기 시간이 길어질 수 있습니다.

정적 및 동적 우선순위: 우선순위는 정적(static) 또는 동적(dynamic)으로 할당될 수 있습니다. 정적 우선순위는 프로세스가 생성될 때 미리 할당되며, 실행 중에는 변경되지 않습니다. 동적 우선순위는 실행 중인 프로세스의 상태나 동작에 따라 우선순위가 동적으로 조정될 수 있습니다.

우선순위 스케줄링은 중요한 작업에 더 많은 CPU 시간을 할당하거나 긴급한 작업을 빠르게 처리할 수 있는 장점이 있습니다. 그러나 우선순위 스케줄링에서는 우선순위의 부여 방법과 변경 시기를 신중하게 고려해야 합니다. 또한, 우선순위 인버전(priority inversion)이라는 문제가 발생할 수 있어 이를 해결하기 위한 기법도 필요합니다.

라운드 로빈 스케줄링(Round Robin Scheduling).
라운드 로빈 스케줄링(RR)은 CPU 스케줄링 알고리즘 중 하나로, 여러 프로세스가 동시에 실행 가능한 환경에서 공정한 CPU 할당을 위해 사용됩니다. 각 프로세스는 일정한 시간 간격으로 CPU를 할당받아 실행되며, 할당된 시간이 지나면 다음 프로세스에게 CPU를 넘겨주는 방식입니다.

라운드 로빈 스케줄링의 주요 특징은 다음과 같습니다:

시분할 시스템: 라운드 로빈 스케줄링은 시분할 시스템에 적합한 알고리즘입니다. 시분할 시스템은 CPU를 여러 프로세스들이 동시에 사용할 수 있도록 작은 단위로 시간을 분할하여 할당하는 방식을 의미합니다.

할당 시간 (Time Quantum): 각 프로세스는 미리 정해진 할당 시간(타임 슬라이스 또는 타임 퀀텀) 동안 CPU를 사용합니다. 할당 시간이 지나면 해당 프로세스는 다른 프로세스에게 CPU를 양도하고, 대기 상태로 전환됩니다.

선점 스케줄링: 라운드 로빈 스케줄링은 선점 스케줄링(preemptive scheduling) 알고리즘입니다. 각 프로세스는 할당 시간이 지나기 전에 CPU를 선점당할 수 있습니다. 이를 통해 우선순위가 높은 프로세스가 빠르게 실행될 수 있습니다.

공정성: 라운드 로빈 스케줄링은 공정한 CPU 할당을 제공합니다. 모든 프로세스는 동일한 할당 시간을 받으며, 순환적으로 CPU를 사용하므로 모든 프로세스가 동등한 실행 기회를 가집니다.

대기 시간: 프로세스의 도착 순서와 상관없이 할당 시간이 지나면 CPU를 양도하므로, 대기 시간을 균등하게 분산시키는 효과가 있습니다. 하지만 각 프로세스가 할당 시간을 초과하는 경우, 성능 저하와 응답 시간 지연이 발생할 수 있습니다.

라운드 로빈 스케줄링은 다양한 운영체제에서 사용되며, 시분할 시스템에서 멀티태스킹을 구현하는 데에 자주 활용됩니다