[OS] Process Scheduling III (Burst, Bound, FIFO vs SPN/RR, Round Robin Detail)

Terminologies

Burst라는 용어가 있다. 직역을 하면 파열 정도로 해석이 되는데 OS에서의 의미는 시간이라는 뜻이다. 즉 Operation을 수행하는 시간이라는 것을 발한다. OS에서 다루는 Burst는 두 가지의 종류가 있다. 하나는 CPU Burst이다. 이는 CPU가 실제 Operation을 수행하는 시간을 의미한다. 다른 하나는 I/O Burst인데 이는 CPU가 I/O를 위해 대기하는 시간을 의미한다. Process는 CPU Burst와 I/O Burst를 필연적으로 반복하면서 수행한다. 이러한 구조를 CPU - I/O Burst Cycle이라고 한다. 예를 들어 명령어를 수행하는 것은 CPU Burst인데 read, write 등의 Operation이 발생하면 필연적으로 I/O Wait이 발생하기 때문에 이를 Execution Phase of Process라고도 한다. 

다음으로 살펴볼 용어는 Process의 Type 혹은 Program의 Behavior라고 하는 것이다. 이 역시 두 가지로 나뉘는데, 첫 번째로는 I/O Bound가 있다. 이는 CPU Burst가 짧고 I/O Burst가 긴 것을 의미한다. 반대로 CPU Bound는 CPU Burst가 길고 I/O Burst가 짧은 것을 의미한다. 물론 이 개념들은 상대적인 것인 것을 알아두자. 각각을 그림으로 그려보면 아래와 같다. 

Scheduling Metrices

지난시간까지 스케줄링 알고리즘들에 대해 다루었다. 이제 우리는 어떤 척도를 가지고 Scheduling Algorithm을 선택할 것인지 파악해야 한다. Optimization Crieteria에는 다음과 같은 것들이 있다. 

• CPU Utilization: IDLE하지 않게 CPU를 사용하는 것
• Throughput: 시간 당 몇개의 Process가 수행되는지
• Turnaround Time: Process가 수행하는데 걸린 시간
• Response Time: 응답시간. Request가 제출되고 처음 CPU가 해당 Process를 수행하여 응답을 처리한 시간
• Deadline: 마감시간. Deadline Ratio라는 Deadline을 얼마나 잘 지키는지에 대한 비율 -> Realtime System
• Fairness: Process가 얼마나 공평하게 수행되는지. 1/n을 지향하지만 Service Time Error가 발생하기에 이를 보장

이 말고도 Crieteria는 더 있을 수 있다. 그러나 분명한 것은 이 척도들을 전부다 만족시킬 수는 없다. 따라서 System과 OS에서 이 척도들을 선택하는 것도 다르다. 따라서 아래의 사례들을 보면서 어떤 상황에서는 어떤 Criteria를 선택하는지 살펴보자

• Supercomputer: 슈퍼컴퓨터는 CPU Burst가 매우 높다. 대부분 연산과 계산만을 담당하기 때문에 I/O가 별로 필요하지도 않다.
• Personal Computer: Interactive한 Process를 많이 수행한다. 카톡을 하면서 유튜브를 틀고 VSC를 열어 코딩을 한다는 등 Interactivity가 상당히 높기 때문에 I/O Bound Process의 양이 상당히 높다. 
• Embed System: Interrupt Handling과 Task Dispatch가 빨라야한다. 임베디드에서는 따라서 Deadline과 Response Time이 빨라야 한다.
• Server Computer: 각 작업들이 자신의 할당량에 맞게 CPU Resource를 가져가게 해야한다. 따라서 Fairness와 Response Time이 가장 중요한 척도가 될 것이다.

이렇게 간단한 사례만 봐도 각각의 시스템에서 요구하는 Crieteria가 다르기 때문에 위에 있는 척도를 전부다 만족한다는 것은 불가능한다. 따라서 시스템에 맞게끔 OS를 구현하는 것이 개발자의 목표가 될 것이다. 

Case Study - FIFO vs. SPN/RR

그렇다면 이제 Scheudling Algorithm들에 대한 실질적인 비교를 해보자. FIFO와 SPN, 그리고 Round Robin(RR)까지 한번에 비교를 할 것이다. 

위의 Case를 보자. 모든 Process들의 Arrival Time을 0으로 보고 있는 것이다. 일반적으로 FIFO는 CPU Burst가 높은 Process들의 집합에서 좋은 성능을 보인다. SPN은 세 알고리즘 중 Superior Turnaround Time을 제공해준다. SPN을 고려할 때 SPN, HRRN도 같은 부류로 생각하면 좋겠다. 어차피 예측값인 S를 사용하기에 비슷한 범주로 묶을 수 있기 때문이다. 

두 번째 Case에서는 FIFO와 SPN이 동일한 Turnaround Time을 가지고 있는것을 볼 수 있다. 그래서 SPN도 여기서 효율적이라고 생각을 할 수 있지만, 고민을 해봐야 하는 것은 SPN은 min값을 찾는 것이다. 따라서 Process가 끝날때마다 min을 계산 하기 때문에 O(n)을 Process의 개수만큼 반복해야 하기 때문에 총 시간 복잡도는 O(n^2)이 될 것이다. 반면 FIFO는 단순히 front와 pop Operation만 수행하면 된다. 따라서 전체적인 시간 복잡도는 O(1)이 걸릴 것이다. 이렇게 Time이 전부 다 같다면 FIFO를 선택해서 사용하는 것도 고려할만 하다는 것이다. 

 

위 케이스들에서 Round Robin은 Worst Turnaround Time을 보여주었다. 이때쯤인면 RR은 뭐하는 알고리즘인지 궁금해할만하다. Round Robin 알고리즘은 Turnaround Time에 초점을 맞춘 것이 아니라 Response Time에 초점을 맞춘 알고리즘이다. 

세 번째 Case의 두 알고리즘 모두 RR이며 각각 Quantum을 10, 5로 설정해놓은 것이다. Quantum과 Slice는 같은 의미이다. 위 예시를 통해 Time Slice가 작아질수록 Response Time도 작아지는 것을 볼 수 있다. 따라서 Quantum과 Response Time은 정비례 관계이다. FIFO나 SPN은 Preemption이 아니기 때문에 Response Time은 RR보다 현저히 떨어진다.

이번에는 Service Time이 모두 같을때이다. 극단적이기는 하지만 Time Quantum을 15, 5로 각각 설정해놓았다. (15일때가 사실 FIFO와도 같은데.....) 먼저 Time Slice가 15일때 Turnaround Time은 작지만 Response Time은 매우 느리다. 반면 Quantum이 5일때의 Turnaround Time은 매우 크지만 Response Time은 매우 빠른 것을 볼 수 있다. 즉, Time Slice를 줄이게 되면 Response Time은 낮아지지만 Turnaround Time은 줄어들거나 오히려 늘어날 수도 있다. 줄어드는 경우는 Dynamic한 Job들이 들어왔을 때 가능하고, 위의 예시 처럼 비슷한 길이의 Job들에 대해서는 늘어나는 경향을 보여준다. 따라서 이는 결과가 Guarantee할 수 없는 방식이기에 Work Load에 따라 정해야 하는 것이다. 

 

Reference

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