CPU 스케줄링 알고리즘의 선점 여부와 특징

핵심 정리

CPU 스케줄링은 준비 상태에 있는 여러 프로세스 중 어느 프로세스에 CPU를 배정할지 정하는 운영체제의 기능이다. 운영체제가 준비 상태의 프로세스 가운데 하나를 선택해 실행 상태로 보내는 것을 디스패치라 한다. 스케줄링 알고리즘은 프로세스를 선택하는 순서를 정하는 규칙이며, 알고리즘마다 평균 대기 시간이나 응답 시간 등 서로 다른 목표를 둔다.

스케줄링 알고리즘을 설계할 때는 일괄 처리인지 대화형인지, CPU와 입출력 장치의 사용 비율이 어떠한지, 우선순위를 부여할지와 부여한다면 해당 프로세스의 선점 정도를 어떻게 할지 고려한다. 이러한 요소는 서로 상반되는 목적을 낳기도 하므로, 하나의 알고리즘이 모든 목적을 동시에 만족시키기는 어렵다.

스케줄링은 실행 중인 프로세스의 CPU를 빼앗을 수 있는지에 따라 선점 방식과 비선점 방식으로 나뉜다. 선점은 실행 중인 프로세스의 CPU를 빼앗는 것 라운드 로빈은 선점형 스케줄링 기법이다. RR 스케줄링은 선점 방식이므로 할당 시간이 끝났는데도 종료되지 않은 프로세스를 준비 큐로 보낸다.

할당량이 작으면 오버헤드 증가 시간 할당량은 스케줄링 성능을 좌우하는 요소이다. 시간 할당량이 작으면 문맥교환 횟수와 오버헤드가 증가한다. 시간 할당량을 크게 잡으면 문맥교환은 줄지만 응답은 느려지는 경향이 있다.

평균 대기 시간을 줄이려면 실행 시간이 짧은 작업부터 먼저 실행하는 기법이 유리하다. SJF 스케줄링은 실행 시간이 짧은 작업을 먼저 실행하므로 평균 대기 시간이 FCFS보다 짧다. 다만 실행 시간이 긴 프로세스가 짧은 프로세스에 계속 양보하면 기아 상태가 생길 수 있고, 대기 중인 프로세스의 요구 시간에 관한 정확한 자료를 얻기 어렵다는 문제도 있다.

자세히

라운드 로빈의 시간 할당량

라운드 로빈 스케줄링은 여러 프로세스에 일정한 시간을 할당하는 기법이다. 준비 큐에 있는 프로세스들이 차례로 같은 길이의 CPU 시간을 받으므로 한 프로세스가 CPU를 독점하기 어렵다. 할당 시간이 끝나도 작업이 완료되지 않은 프로세스는 CPU를 빼앗기고 준비 큐의 맨 뒤로 돌아간다.

RR 스케줄링은 시간 할당량을 기준으로 CPU를 빼앗는 선점형 스케줄링 기법이다. 할당량이 선점의 기준이므로, 할당량의 크기가 RR의 동작을 결정한다. 할당량이 너무 작으면 문맥교환이 잦아져 실제 작업에 쓰이는 시간이 줄고, 너무 크면 선점 효과가 약해져 짧은 작업의 응답이 늦어진다.

RR 스케줄링은 우선순위를 적용하지 않는 단순한 선점형 방식이다. 우선순위가 없으므로 프로세스의 중요도에 따라 CPU를 더 배정하는 방식과 구분된다. 같은 선점형 스케줄링이라도 다음 프로세스를 선택하는 기준이 다르다는 점을 기억해야 한다.

FCFS와 비선점의 의미

FCFS 스케줄링은 FCFS 스케줄링은 비선점형 스케줄링 기법이다. 먼저 도착한 프로세스가 끝날 때까지 CPU를 사용하게 하는 것이 FCFS의 핵심이다. FCFS는 도착 순서와 대기 시간을 기준으로 선택하므로 실행 시간의 길이는 고려하지 않는다. FCFS 스케줄링은 비선점 방식이며, 실행 중인 프로세스가 끝나면 준비 큐에서 가장 오래 기다린 프로세스를 선택한다. 비선점 방식이므로 프로세스 선택은 실행 중인 프로세스가 끝나는 시점에만 이루어진다.

비선점 방식은 실행 중인 프로세스를 중간에 멈추지 않으므로 문맥교환이 적게 일어난다는 장점이 있다. 그러나 긴 작업이 CPU를 오래 점유하면 뒤에 있는 프로세스들이 그동안 모두 기다려야 하므로 장점과 단점을 함께 살펴야 한다.