CPU 스케쥴링 알고리즘

스케줄링

스케줄링이란  CPU의 자원을 효율적으로 사용하기 위해 프로세스들의 순서를 정해주는 정책.

다음에 실행할 프로세스를 고르는 기준은

1.CPU 이용률.

2.처리량(throughput) : 단위시간 실행을 완료한 프로세스의 수.

3.소요시간(turnaround time) : 프로세스의 시간부터 종료까지 걸리는 시간.

4.응답시간(response time) : 요청을 보낸 시간부터 처음 응답받을 때까지 걸리는 시간.

5.대기시간(wait time) : 준비 큐에서 대기하는 시간.

스케줄러의 점유 방식에는

1.선점(Preemptive)방식은 프로세스가 CPU 점유 도중에 다른 프로세스가 CPU를 점유 가능.

응답이 빠르고 모바일에서 많이 사용하는 방식.대화형에 적합. 하지만 오버헤드가 발생한다.

ex)Round-Robin,SRT

2.비선점(non Preemptive)방식은 프로세스가 끝나기전까지 계속 CPU 점유하는 방식.

응답시간을 예측할 수 있고,batch process에 적합하다. 하지만 짧은 작업도 오래걸릴 수 있다.

ex)FCFS,SJF,HRN

스케줄링 기법은

(1)FCFS(First Come First Service)

대기 큐에 도착한 순서로 CPU에 할당. 긴 작업이 먼저 선점할 경우 짧은 작업은 오래 기다려야 함. 

(2)SJF(Shortest Job First)

수행 시간이 짧다고 판단되는 것 먼저 수행한다.

긴 작업에 대해서는 대기시간 예측이 어렵다.

(3)RR(Round-Robin)

같은 크기의 CPU 점유 시간을 할당 한 후, 시간이 다 될때 까지 끝내지 못하면 다음 프로세스를 할당함. 실행중이던 프로세스는 준비 큐로 들어간다.

(4)SRT(Shortest Remaining Time)

처리가 완료되는 데까지 가장 짧은 시간이 소요된다고 판단되는 프로세스 먼저 수행.

실행 중인 프로세스가 있어도 짧은 시간의 프로세스가 생기면 교체된다.

실시간 시스템에 유리.

(5)Multilevel Queue

여러 큐 사이에 우선순위가 존재하며 각 큐들은 서로 다른 스케줄링을 통해 CPU 할당.

(6)Multilevel Feedback Queue

여러 큐가 존재하는 상태에서 Round-Robin 방식으로 작동. 각 큐마다 할당 시간이 다름. 첫 큐에서 끝내지 못하면 다음 큐로 이동. 또 못하면 그 다음큐로 이동. 마지막은 FCFS 방식임.