면접을 위한 CS 전공 지식 노트-[3.4 CPU 스케줄링 알고리즘]

위 사진처럼 여러 알고리즘이 있지만 이중 일부만 살펴보고자 한다. 

 

CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정을 한다. 이 알고리즘은 CPU 이용률은 높게, 주어진 시간에 많은 일을 하게, 준비 큐에 있는 프로세스는 적게, 응답 시간은 짧게 설정하는 것을 목표로 한다. 

 

3.4.1 비선점형 방식(non-preemptive) 

비선점형 방식은 프로세스가 스스로 CPU 소유권을 포기하는 방식이다. 강제로 프로세스를 종료하지 않기 때문에 context switching에 따른 부하 적다.

 

FCFS(First Come, First Served)

가장 먼저 온 것을 가정 먼저 처리하는 알고리즘이다. 길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생하는 단점이 있다. 

 

SJF (Shortest  Job First)

실행 시간이 가장 짧은 프로세스를 먼저 실행하는 알고리즘이다. 긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧다. 하지만 실제로 실행 시간을 알 수 없기 때문에 과거의 실행했더 시간을 토대로 추측해서 사용한다. 

 

우선순위

오랜된 작업일 수록 우선순위를 높이는 방법을 통해 SJF의 프로세스가 길면 실행되지 않는 단점을 보완한 것이다. 

 

3.4.2  선점형 방식(preemptive) 

선점형 방식(preemptive)은 지금 사용하고 있는 프로세스를 알고리즘에 의해 중단시켜 버리고 강제로 다른 프로세스에 CPU 소유권을 할당하는 방식이다. (현대 운영체제에서 사용하고 있는 방식)

 

라운드 로빈 (RR, Round Robin)

현대 컴퓨터가 쓰는 스케줄링인 우선순위 스케줄링(priority scheduling)의 일종이다. 각 프로세스는 동일한 할당 시간을 주고 그 시간에 끝나지 않으면 다시 준비 큐(ready queue)의 뒤로 가는 알고리즘이다. 

 

ex) x 만큼의 할당 시간이 부여되고, N 개의 프로세스가 운영된다고 하면 (N -1) * x 시간이 지나면 차례가 오게 된다. 

 

단점

할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 비용이 커진다. 전체 작업 시간은 길지만 응답 시간은 짧다. 

 

로드벨런서에서 트래피 분산 알고리즘으로도 쓰인다. 

 

SRF

SJF와 달리 중간에 더 짧은 프로세스가 들어오면 실행을 중단하고 해당 프로세스를 수행하는 알고리즘이다. 

 

다단계 큐

우선순위에 따른 준비 큐를 여러 개 사용하고, 큐마다 라운드 로빈이나 FCFS 드 다른 스케줄링 알고리즘을 적용한 것을 말한다. 큐 간 프로세스 이동은 X, 스케줄링 부담이 적음, 그래서 유연성이 떨어진다.