CS377: Scheduling Algorithms

이번 시간에는 스케줄링에 대해서 공부해보도록 하겠다.

 

하나 이상의 프로세스를 동시에 운영하고자 할 때, CPU와 I/O에서는 오버랩이 발생할 수 있다. 따라서, 모든 프로세스는 OS에 의해서 관리되어야 한다.

커널은 인터럽트가 발생할 때, 프로세스가 생성 또는 종료될 때, 프로세스가 실행에서 대기 상태로 돌아갈 때 스케줄러를 동작한다.

이 때, Non-preemtive System의 경우 스케줄러는 해당 이벤트가 종료될 때까지 기다렸다가 동작하게 되고, Preemtive System의 경우 스케줄러가 실행중인 프로세스를 일시 정지하고 동작하게 된다.

 

스케줄링에는 다양한 알고리즘이 존재하고 이를 비교하기 위한 비교자는 다음과 같다.

• CPU Utilization (CPU 사용률) : 시스템 동작 시간 중 CPU가 사용된 시간을 측정하는 방법
• Throughput (처리량) : 단위 시간 당 작업을 마친 프로세스의 수
• Turnaround time (반환 시간) : 프로세스가 생성된 후 종료되어 사용하던 자원을 모두 반환하는데 걸리는 시간
• Waiting time (대기 시간) : 프로세스가 CPU를 할당 받아 실행되기 전 대기 상태의 시간
• Response time (응답시간) : 대기 상태에 들어와 CPU를 최초로 얻기까지 걸리는 시간

이상적으로 CPU 스케줄러는 모든 조건이 최적인 경우가 가장 좋겠지만, 실제로는 가능하지 않다. 따라서 스케줄링 알고리즘은 스케줄링 정책에 부합하는 알고리즘으로 선택하도록 한다.

 

스케줄링 알고리즘의 종류는 다음과 같다.

• FCFS (First Come, First Served): State Queue에 먼저 도달한 프로세스에게 CPU를 할당하는 비선점형 방식이다.
• Round Robin : 프로세스에게 각각 동일한 time slice를 할당하여 이 시간 동안만 CPU를 이용하게 한다. 만약 할당 시간동안 처리를 다 하지 못하면 CPU는 다음 차례의 프로세스에게 넘어가게 된다. 이 알고리즘의 경우 모든 프로세스가 최초 응답 시간을 빠르게 보장받을 수 있다는 장점을 가진다.
• SJF (Shortest Job First) : 실행 시간이 가장 짧은 작업부터 CPU를 할당한다. 앞 순서에 실행 시간이 긴 프로세스가 있다면 오래 기다려야 하는 문제를 완화했지만, 시간이 짧은 프로세스가 계속해서 들어온다면 State Queue에서 영영 기다리게 되는 Starvation 문제가 발생한다.
• Multilevel Feedback Queue : Multilevel Queue의 경우 우선순위에 따라 여러 개의 Queue를 사용하는 방식으로 우선 순위가 높은 Queue에 먼저 CPU가 할당되는 방식이다. 각 Queue 내에서는 독립적인 알고리즘을 사용할 수 있다. 그러나 Multilevel Queue에서도 역시 공평성과 Starvation 문제가 발생하게 되는데 이를 해결한 것이 해당 알고리즘이다. 이와 같은 경우에는 한 번 CPU를 할당받은 프로세스는 우선 순위가 낮아지게 되고, 우선 순위가 낮은 큐로 이동하게 된다. 또한 우선 순위가 낮은 Queue에 time slice가 더 길게 주어지게 되는데 이는 공평성 문제를 해결하기 위함이다.

Multilevel Feedback Queue