CPU 스케줄링 알고리즘

CPU 스케줄링 알고리즘

CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU 에게 할당한다.

 

스케줄링 알고리즘의 목표 

CPU 이용률은 높게,

주어진 시간에 많은 일을 하게,

준비 큐 에 있는 프로세스는 적게,

응답 시간은 짧게

 

 

비선점형 방식 (non-pre-emptive)

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식, 강제로 프로세스를 중지하지 않는다.

따라서 컨텍스트스위칭으로 인한 부하가 적다.

 

FCFS (First Come, First Served)

가장 먼저 온 것을 가장 먼저 처리하는 알고리즘.

길게 수행되는 프로세스 때문에 '준비 큐에서 오래 기다리는 현상 (convoy effect)' 이 발생할수 있다.

 

SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘.

긴 시간을 가진 프로세스가 실행 되지 않는 현상 (starvation) 이 일어나며 평균 대기 시간이 가장 짧다.

하지만 실제로는 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 참고해서 사용한다.

 

우선순위

SJF 는 긴 시간을 갖는 프로세스가 실행되지 않는 현상이 있다.

우선순위는 오래된 작업일 수록 우선순위를 높이는 방법 (aging) 을 통해 단점을 보완.

 

 

선점형 방식 (pre-emptive)

현대 운영체제가 사용하는 방식.

지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 cpu 소유권을 할당하는 방식.

 

라운드 로빈

각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐 뒤로가는 알고리즘.

 

예를들어 q 만큼의 시간이 부여되었고 N 개의 프로세스가 운영된다고 하면 (N-1) * q 시간 후에 다시 자기 차례가 온다.

할당 시간이 너무 크면 FCFS(First come first served)가 되고 짧으면 컨텍스트 스위칭이 잦아져 오버헤드가 커진다.

 

일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아지는 특성.

 

SRF (Shortest remaining time)

프로세스의 남은 수행 시간이 짧은 순서에 따라 처리.

SJF 는 중간에 실행 시간이 더 짧은 프로세스가 들어와도 기존 짧은 작업을 모두 수행하고 그다음 짧은 프로세스를 이어나간다.

SRF는 중간에 더 짧은 프로세스가 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행한다.

 

다단계 큐

우선순위에 따른 준비 큐를 여러개 사용하고, 큐마다 라운드 로빈이나 FCFS 등 다른 스케줄링 알고리즘을 적용한 것.

큐 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특성.