CPU Scheduling Algorithm

CPU 스케줄링 알고리즘은 여러 프로그램이 실행됐을 때, 프로그램이 유휴상태에 들어가 CPU가 대기하는 동안 다른 프로그램을 실행하는데 실행할 프로그램을 선택하는 방법입니다.

 

CPU 스케줄링 알고리즘에는 여러 방법이 있는데 대표적으로 다음 방법들이 있습니다.

• FCFS (First Come First Service)
• SJF (Shortest Job First)
• Priority
• Round - Robin
• Multi Level Queue
• Multi Level Feedback Queue

각 알고리즘에서 CPU Burst Time과 Turn Around Time을 통해 성능평가를 하여 최적의 알고리즘을 선택합니다.

(Cpu burst time = Cpu 사용 시간, Turn Around Time = Cpu 사용시간 + 대기시간)

 

여기서 스케줄링이란, 순서를 정하는 스케줄링과, 실행할 수 있도록 준비하는 Dispatching이 합쳐진 내용입니다.

 

EX) Algorithm A로 순서를 정함 → P0 ~ Pn 순으로 진행 → Save PCB0, Restore PCB1 .... (Context Switch) → ....

 

성능평가는 3가지 방법으로 Turn Around Time과 Waiting Time, 두번째로 Through Put, 마지막으로 Response Time 으로 성능평가를 진행하는데 주로 1번방법을 사용합니다.

 

SJF와 Priority는 각각 Preemptive와 Non - Preemptive로 나누어서 계산 할 수 있습니다.

Preemptive는 선점이라는 뜻으로, SJF에서 Job 길이가 더 짧은게 있다면, CPU 점유를 뺏아서 사용 가능합니다.

Priority에서도 마찬가지로 우선순위가 더 우선인게 있다면, CPU 점유를 뺏아서 사용 가능합니다.

 

따라서, Non - preemptive, Preemptive에 따라 성능평가 결과가 다르게 도출될 수 있습니다.

 

Round - Robin 방법은 △t의 시간으로 돌아가면서 CPU 점유를 합니다. 그러므로 △t의 크기가 성능을 좌우합니다. 만일 △t가 ∞라면, FCFS랑 동치이고, △t가 0이라면, 너무 빈번한 문맥교환이 발생합니다. 따라서, △t는 적당히 크게 잡는것이 유리합니다.

 

Multi Level Queue는 I/O 위주의 프로세스를 대화식 처리하는 큐와, CPU 위주의 일괄처리 하는 큐를 나누어 진행합니다.

Multi Level Feedback Queue는 우선 순위에 따라 High Queue, Low Queue로 이동하여 다른 알고리즘으로 실행합니다.

 

단, 이 방법은 Queue의 개수나 각 Queue의 Scheduling Algorithm 선정, Low 및 High Queue로의 이동 조건, 어느 Queue로 진입할 건지 등 고려해야할 요소가 있습니다.

 

Priority와 SJF의 문제점으로는, 우선순위나 Job의 길이로 CPU를 점유하기 때문에 어떤 프로그램은 할당을 받지 못하는 경우가 생길 수 있습니다.(Indefinite Waiting) 따라서, Starvation(기아 현상)이 발생하기 때문에 시간이 지날수록 Priority를 높여주는 방식 등으로 기아 현상을 해결해 주어야합니다.