[OS] Process Scheduling I (Intro, FIFO, SPN)

Types of Process Scheduling

Process를 스케줄링하는 것은 크게 세 가지로 분류된다. 먼저 Long-Term Scheduling이 있다. 이를 Job Scheduler라고도 하는데 이는 단순하게 시스템에 Program을 올릴지 말지를 결정하는 Scheduling이다. 다음으로는 Medium-Term Scheduling이 있다. 이를 Swapper라고도 부르는데 우리는 이전에 우리가 배운 Swapping 기법을 수행하는 Scheduler이다. 또한 Short-Term Scheduling이 있다. 이것이 우리가 초점을 두고 있는 CPU Scheduler이다. Processor가 어떤 Process를 수행할지 결정하는 Scheduling이다. 마지막으로 I/O Scheduling이 있다. 보류 중인 I/O Request를 Available 한 I/O Device에게 적절히 배분해주는 역할을 한다. 

Terminologies

본격적인 Scheduling Algorithm을 배워보기 전에 간단한 용어를 정리하고 가겠다. Selection Function이라 함은 Ready Processes 중 다음에 실행할 프로세스를 결정한다. Selection Function에서 사용하는 단어가 몇 개 있는데, W는 시스템이 지금까지 사용한 시간을 의미한다. 반면 E는 Execution에 실행된 시간을 의미한다. 마지막으로 S는 실제 Process가 서비스된 시간을 의미하며 이는 당연하게도 E를 포함하는 개념이다. 예를 들어 max [W]라고 하면 FIFO가 바로 나와야 하는 관계를 지니고 있다. 이에 대해서는 Scheduling Algorithm을 배워가면서 알아가 보자. 

 

또한 Decision Mode를 이해하고 넘어가야 한다. Selection Function이 호출된다고 해도 어떤 Process는 바로 교체가 되고, 어떤 Process는 수행 중이던 걸 끝내고서야 바꾼다. 정리하자면 Selection Function은 Nonpreemptive 하거나 Preemptive 하다. 각각을 번역하면 비선점 모드와 선점 모드이다. Nonpreemptive는 비선점으로서 어떤 Process가 Running State에 있다면 terminate 될 때까지 기다리거나, 선택된 Process를 일시적으로 Block 시킨다. 반면 Preemptive는 선점으로서 OS에 의해 Process가 Interrupt 되는 경우를 의미한다. 주로 Process가 새로 들어올 때, 혹은 Interrupt가 발생되거나 Time Out이 되거나 하는 등의 이유로 선점되어 들어갈 수 있다. 

FIFO (First in, First out)

FIFO라는 단어를 많이 들어보았을 것이다. 선입선출하면 떠오르는 자료구조는 바로 Queue이다. 이 방식은 Ready Queue에 있는 Process 중 대기시간인 가장 긴 Process를 선택한다. 따라서 Selection Function은 Max[W]가 된다. 이때 Decision Mode는 Non-Preemption이다. 이 방식은 쉽게 구현할 수 있다는 장점을 가지고 있다. Overhead도 적으며, Service Time이 길다면 이 방식을 채택하는 것이 좋을 수도 있다. 그러나 이 방식의 치명적인 단점은 Convoy Effect가 발생할 수 있다는 것이다. Convoy Effect란 긴 Process가 먼저 대기하는 경우 짧은 Process들의 Average Turn Around Time이 높아지며 Response Time도 높아질 수 있게 된다. 

위의 예시를 보면서 이해해보자. Service Time은 Process가 실행되는 실제 시간이다. 초록색 칸은 현재 해당 알파벳의 Process가 Running 하고 있다는 뜻이다. 먼저 0번 시간대를 보자. 0번 시간에는 A가 Ready Queue에 있기 때문에 A를 선택한다. 2에 와서는 A는 Service Time을 다 소진했으니 끝났고, B가 대기하고 있으니 B를 선택해 수행한다. 4 시점에는 C가 기다리고 있고, 6 시점에는 CD가 8 시점에는 B가 끝났지만 CDE가 대기하고 있다. 이때 비선점 모드이기 때문에 Process가 전환되지 않고 계속 B를 수행하는 것이다. 다시 돌아와서 8 시점에서 보면 CDE가 Ready Queue에 있다. 이때 Selection Function은 Max[W]이므로 가장 대기시간이 길었던 C를 선택한다. C가 13 시점에서 끝나면 다음으로 오래 기다린 D를, 마지막에는 E를 선택해 수행한다. 

이제 응답성 측면에서 바라보자. 각 Process의 Turn Around Time은 (Process가 끝난 시간 - Arrival Time)으로 정의된다. 각각의 Process의 Turnaround Time은 A: 2, B: 6, C: 9, D: 12, E: 12로 계산이 되고, Average Turnaround Time은 (2+6+9+12+12) / 5 = 8.2이다. 응답성이 상당히 낮은 편이라고 할 수 있겠다. 

SPN (Shortes-Process-Next)

다음으로 살펴볼 Scheduling Algorithm은 SPN이다. 여러 컴퓨터 공학자들이 보았을 때 FIFO 알고리즘을 선택하는 경우에 Long Process를 먼저 선택하는 경향이 있다고 판단이 되었다. 반면에 SPN은 가장 짧은 Expected Service Time을 가진 Process를 먼저 선택하는 방식이다. 따라서 Selection Function은 min[S]가 되고, Decision Mode는 FIFO와 동일하게 Non-preemption을 채택하고 있다. 짧은 Job을 먼저 수행하기 때문에 SJF (Shortes Job First)라고 불리기도 한다. 

위의 예시를 보자. Process A는 0 시간에 아무도 없으니 실행되고, Process B도 마찬가지이다. 이제 우리가 주목해야 할 곳은 B가 끝나는 9의 시간이다. 4, 6, 8시간에 이미 CDE의 Process가 들어와 있다. FIFO였으면 대기시간이 가장 긴 C를 선택했겠지만 우리는 SPN의 min[S]를 봐야 한다. 따라서 들어와 있는 Queue에 있는 Service Time 중 최소는 Process E이다. 따라서 E가 수행되고 나서 Queue의 min[S]는 C이기 때문에 C수행 후 남아있는 D를 실행한다. 이제 아까와 마찬가지로 Turnaround Time을 계산해보자. 각 Process의 Turnaround Time은 A: 2, B: 7, C: 11, D: 14, E: 3이다. 따라서 Average Turnaround Time은 (2+7+11+14+3) / 5 = 7.4로 FIFO보다 개선이 되었다. E의 Turnaround Time이 개선됨에 따라 전체적인 Turnaround Time 역시 개선되는 것이다. 따라서 SPN은 Overall Performace를 증가시킬 수 있다. 각각의 Process의 Turnaround Time과 Average Turnaround Time의 두 마리의 토끼를 한 번에 잡은 셈이다. 그러나 이 방식의 문제점은 Long Process에 대한 Starvation이 발생할 수 있다는 것이다. 만약 하나의 Process가 극단적으로 긴 Service Time을 가지고 있다면 SPN을 선택한 CPU에서는 해당 Process를 영영 수행하지 못할 수도 있다는 것이다. 또한 가장 중요한 문제는 인간이 어떻게 Process의 Required Service Time을 알 수 있느냐이다. 이는 예측의 영역이다. 실행되지도 않은 Process의 Service Time은 우리가 어떻게 예측할 수 있겠는가? 물론 시스템이 계산해주거나, 사용자의 Input으로 주어질 수 있겠지만 이는 구현의 난이도가 매우 높다. 그렇기에 OS는 History를 보고 이를 근사 시키는 방식을 선택한다.

n개의 Process들의 Weight가 동일하다고 가정할 때 Simple Average를 위 공식으로 유도할 수 있다. 하지만 Weight는 Process별로 항상 동일할 수가 없다. 따라서 우리는 Exponential Average를 통해서 다시 예측을 해야 한다. Exponential Average는 최근 Instance들에 대해 더 많은 Weight를 부여하는 방식이다. 이는 Make Sense 한데, 최근에 접근한 Process를 우리가 더 자주 사용하기 때문이다. 이 방식은 미래의 값을 예측하는 기본으로 사용이 된다. 사실 위에 있는 식과 별 다를 것은 없지만 공식을 아래에 적어보면 다음과 같다. 

 실제 이렇게 Exponentail Weight를 사용하면 관측합과 상당히 유사한 그래프가 나온다. 이 그래프에 대한 참조는 책에 있는 그림을 참고하면 좋겠다. SNP은 사실상 구현의 난이도 때문에 구현보다는 Analysis용으로 많이 사용이 된다. 어떤 Scheduling Algorithm에 대한 Optimal이 SPN이 되므로 SPN을 비교의 척도로서 많이 사용이 된다. 

Reference

William Stallings. (2018). Operating Systems: Internals and Design Principles (8th Edition): Pearson.