[Operating Systems] Scheduling

스케쥴링은 멀티프로세싱 환경에서 다음에 실행될 프로세스가 무엇인지 결정하는 알고리즘이다.

CPU 사용률, 스루풋, Turnaround time(특정 프로세스를 실행하는 시간), Waiting time(프로세스가 ready queue에서 대기하는 시간), Response Time(요청시간과 처리시간의 차이) 등의 기준에 따라서 스케쥴링의 성능을 판단하게 된다.

스케쥴링의 목적이라 함은 CPU사용률과 스루풋을 최대화 하면서 turnaround time, waiting time, response time을 최소화 하는 것이다. 스케쥴링 알고리즘의 종류로는 FCFS(First come First served), SJF(shortest job first), RR(round-robin), Priority based scheduling, Multi level scheduling 등등이 있다.

우선 FCFS는 말 그대로 온 순서대로 실행되는 것이다. 이것은 프로세스에 대해 어떠한 기준을 적용하지 않기 때문에 공평할 수는 있겠지만 효율적이지는 못할 것이다.
둘째로 SJF는 CPU burst time이 가장 짧은 순서대로 실행하는 것이다. 이 방법이 당연히 가장 최적의 알고리즘이지만 실제로 CPU시간의 길이를 알 수 없다는 단점이 있다.
그 다음으로 RR는 각각의 프로세스에게 균등한 길이(time quantum, time slice)만큼의 실행 시간을 부여하고 그 시간이 다 끝나면 다시 프로세스를 대기 큐에서 대기 시키고 다음 프로세스를 실행하는 방식으로 스케쥴링한다. RR에서는 time quantum의 길이를 적절히 부여하는 것이 중요하다. 만약 퀀텀을 크게 하면 FIFO와 거의 같은 형태일 것이고 너무 작게 하면 context switch시 발생하는 오버헤드가 커지게 된다. 따라서 보통 10~100 밀리초를 퀀텀으로 지정한다.

Priority 기반 스케쥴링은 각 프로세스에 우선순위를 부여하고 우선순위에 따라 스케쥴링 될 수 있도록 하는 것이다.
새로운 프로세스가 생성되었을 때 기존의 프로세스의 실행권한을 뺏는지 안뺏는지에 따라 세부적으로 선점형과 비선점형으로도 나뉘며 SJF는 CPU burst time에 우선순위를 부여했다고도 볼 수 있다.
우선순위 기반 스케쥴링의 문제는 우선순위가 높은 프로세스가 CPU를 거의 독점하게되는 starvation 문제인데 시간이 지남에 따라 우선순위를 증가시키는 Aging 기법을 이용해서 해결할 수 있다.

Multilevel Queue 스케쥴링 기법은 Foreground queue와 background queue를 가지고
foreground는 라운드로빈으로, background는 FCFS로 실행되도록 하며
전체적으로 포어그라운드에 시간의 80%, 백그라운드에 시간의 20%를 주며
포어그라운드를 먼저 처리하고 백그라운드를 처리할 수 있도록 한다. 스타베이션 문제가 발생할 가능성이 있다.