CPU 스케줄링 알고리즘

CPU 스케줄러는 CPU 스케줄링 알고리즘으로 프로세스에게 일을 스레드 단위로 할당한다. 즉, 어떤 프로그램이 CPU 소유권을 가질 것인지 결정한다. CPU 스케줄링 알고리즘 방식으로는 크게 비선점형과 선점형 방식이 있다.

 

-CPU 스케줄러의 목표

1. CPU 이용률을 최대치로 사용

2. 주어진 시간에 최대한 많은 일을 하도록 함

3. ready queue에 프로세스가 적도록 함

4. 응답 시간을 짧게 설정함

비선점형 방식(non-preemptive)

프로세스가 스스로 CPU 소유원을 포기할 수 있고 강제로 프로세스를 종료할 수 없다. 그렇기에 컨텍스트 스위칭으로 인한 부하가 적다.

비선점형 방식에는 FCFS, SJF, 우선순위가 있다.

FCFS(First Come, First Served)

가장 먼저 들어온 프로세스를 먼저 처리한다. 하지만 가장 먼저 들어온 프로세스의 처리량이 많다면 ready queue에 다른 프로세스들이 많이 대기하고 있는 단점이 있다. 이를 convoy effect라고 한다.

SJF(Shortest Job First)

실행 시간이 가장 짧은 프로세스를 가장 먼저 처리하는 알고리즘이다. 하지만 실제 실행 시간을 알 수 없어 이전 실행 시간을 이용해 추측하여 처리한다.

그리고 긴 실행 시간을 가진 프로세스는 처리되지 않는 starvation이 일어난다. 평균 대기 시간은 가장 짧다.

우선순위

SJF에서 실행 시간이 긴 프로세스는 처리되지 못했다. 이를 해결하기 위해 오래된 작업이면 우선 순위를 높이는 방식 aging를 사용하는 알고리즘이 우선순위이다.

선점형 방식(preemptive)

선점형 방식은 현대 OS가 사용하고 있는 방식이며 지금 사용하고 있는 프로세스를 강제로 중지 시키고 다른 프로세스에 CPU 소유권을 넘기는 방식이다.

라운드 로빈(RR, Round Robin)

라운드 로빈은 각 프로세스에 동일한 시간을 부여하고 시간 내에 처리하지 못하면 다시 ready queue의 뒤로 돌려보내는 알고리즘이다.

ex) n개의 프로세스가 있고 m만큼 시간이 부여되었다면 (n-1) * m 시간이 지나면 다시 자기 차례가 온다.

 

단점으로는 시간 설정을 너무 크게 하면 FCFS가 되고, 너무 짧게 하면 컨텍스트 스위칭이 너무 많이 일어나서 오버헤드가 발생해 비용이 커진다.

특징은 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다. 로드밸런서에서 트래픽 분산 알고리즘으로 사용된다.

SRF

SJF는 실행 중 더 작은 프로세스가 들어와도 기존 작업을 그냥 수행한다.

하지만 SRF는 실행 중 더 작은 프로세스가 들어오면 그 프로세스부터 처리한다.

다단계 큐

다단계 큐는 큐를 여러 개 사용한다. 큐마다 적합한 알고리즘을 적용한 알고리즘이다.

하지만 한 번 큐에 들어가면 이동할 수 없어서 스케줄링에 부담이 적지만 유연성이 떨어진다.