[Operating System] Scheduling: Introduction

Workload Assumptions

---

글을 들어가기 전에, 시스템에서 실행중인 프로세스(작업)에 대해 이와 같은 가정을 한다.

 

가정 1. 각각의 작업은 동일한 시간동안 실행된다.

가정 2. 모든 작업들은 동시에 도착한다.

가정 3. 시작하면 각 작업은 완료될 때까지 실행된다.

가정 4. 모든 작업은 CPU만 사용한다. (I/O를 수행하지 않는다.)

가정 5. 각 작업의 실행 시간을 알고 있다.

 

 

Scheduling Metrics

---

Turnaround Time을 위와 같이 단순하게 가정한다.

 

 

 

 

First In, First Out (FIFO)

---

FCFS라고도 불린다.

FIFO는 위 두 그림으로 설명이 가능하다.

 

First In, First Out은 먼저 온 사람에게 먼저 제공한다는 뜻으로, 먼저 할당 요청을 한 프로세스에게 CPU를 할당한다.

비선점형 스케줄링이며 효율적이지 않다. 여기서 비선점적이라는 것(Non-Preemptive)은 CPU를 할당받으면 자신의 작업을 모두 마치기 전까지, CPU를 반환하지 않는다는 의미이다.

 

FIFO의 치명적인 단점은 Convoy Effect이다. 이는 상대적으로 짧은 다수의 리소스 잠재적 소비자(수행 시간이 짧은)가 헤비급 리소스 소비자(수행 시간이 긴) 뒤에 대기하는 현상이다.

 

 

 

Shortest Job First (SJF)

---

이름 그대로 최단 작업을 우선적으로 실행한다. FIFO와 동일하게 비선점형 스케줄링이다.

 

모든 작업이 동시에 도착한다는 가정이 있다면 가장 효율적인 알고리즘이라고 볼 수 있다. 그러나, 모든 작업들이 한꺼번에 도착하는 것이 아니라 언제든지 도착할 수 있다고, 위의 가정 2를 제거한다면 SJF 알고리즘 또한 문제가 많다.

 

 

 

 

Shortest Time-to-Completion First (STCF)

---

위에서의 문제를 해결하기 위해, 가정 3을 제거하고 스케줄러에 타이머 인터럽트(timer interrupt)와 컨텍스트 전환(context switching)을 적용한다면 비선점형 스케줄러(non-preemptive scheduler)인 SJF의 문제를 선점형 스케줄러인 STCF로 어느정도 해결할 수 있다. 즉, SJF에 preemption(선점)을 추가한 Shortest Time-to-Completion First (STCF)  또는 Preemptive Shortest Job First (PSJF)이 그것이다.

새 작업이 시스템에 들어갈 때마다 STCF 스케줄러는 새 작업을 포함하여 남은 작업 중 가장 적은 시간이 남아 있는 작업을 결정하고 이 작업을 예약한다.

 

SJF가 모든 작업이 동시에 도착한다는 위의 가정하에서 최적의 알고리즘이었다는 것을 기반으로, 해당 가정만을 제거했을 때는 현재까지  STCF가 최적의 알고리즘이라는 것을 알 수 있다.

 

 

 

 

A New Metric: Response Time

---

따라서, 우리가 모든 작업의 길이를 알고, 그 작업은 오로지 CPU만을 사용하며, 유일한 metric인 turnaround time(소요 시간)만을 고려했다면 STCF는 훌륭한 정책이다. 실제로, 배치 컴퓨팅 시스템(batch computing system)에서는 이러한 방식의 스케줄링 알고리즘이 타당할 수 있다. 하지만 Time-shared machine(시분할 머신)의 등장으로 모든 것을 바꾸어 놓았다. 이제 사용자는 터미널을 사용하며 시스템에 대화형 성능(interactive performance from system)을 필요로 한다.

 

이제 우리는 응답 시간을 작업이 시스템에 도착하는 시간부터 작업이 예약된 첫 번째 시간까지로 정의한다.

응답 시간을 충분히 고려한 스케줄러를 생각해보자.

 

 

 

 

 

Round Robin

---

라운드 로빈(RR) 스케줄링의 기본적인 아이디어는 간단하다. RR은 작업을 완료하기 위해 실행하는 대신에 Time Slice(Scheduling Quantum)에 대한 작업을 실행한 다음 실행 대기열의 다음 작업으로 전환한다. 작업들이 마무리될 때까지 해당 방식을 반복한다. 이러한 이유로, RR은 때때로 Time-Slicing이라고 불린다. Time slice의 길이는 타이머 인터럽트 주기의 배수여야 하므로 타이머가 10밀리초마다 중단되는 경우 시간 조각은 10, 20 또는 10ms의 다른 배수가 될 수 있다.

 

RR에 있어 Time Slice의 길이는 매우 중요하다. 짧을수록 응답 시간 측면에서 RR의 성능이 우수하다. 그러나 Time Slice를 너무 짧게 만드는 것은 문제가 된다. Context Switching(컨텍스트 전환) 비용이 과도하게 증가해 전체 성능을 저하시킬 것이다. 따라서 time slice의 길이를 결정하는 것은 시스템 설계자에게 Trade-Off이며, 시스템이 반응하지 않을 정도로 길게 만들지 않고 Context Switching 비용을 감당할 수 있을 만큼 충분히 길어야 한다. Context Switching(컨텍스트 전환) 비용은 일부 레지스터를 저장하고 복원하는 OS 작업으로부터의 발생 뿐만 아니라, 프로그램이 실행될 때 CPU 캐시, TLB, Branch Predictors(분기 예측 변수) 및 하드웨어에서 많은 상태를 구축하며 발생합니다. 다른 작업으로 전환하면 현재 실행 중인 작업과 관련된 이 상태가 flush되고 현재 실행할 작업을 가져오기 위한 새 상태가 발생하므로, 상당한 성능 비용이 발생할 수 있다.

 

따라서 Response Time(응답 시간)이 유일한 Metric(메트릭)인 경우, 합리적인 Time Slice를 가진 RR은 우수한 스케줄러이다. 하지만 Turnaround time(소요 시간) 측면에서는 최악의 스케줄링 정책 중 하나다. Turnaround Time 측면에서 RR은 단순한 FIFO보다 훨씬 더 심각하다. 일반적으로, 작은 Time Scale로 활성 프로세스 간에 CPU를 균등하게 분배하는 모든 정책(RR 등)은 Turnaround Time과 같은 메트릭에서 저조한 성능을 보일 것이다. 실제로, 이것은 내재적인 Trade-off다. 만약 불공평한 스케줄링을 감수한다면, 더 짧은 작업의 실행을 먼저 완료할 수 있지만, Response Time을 희생해야 한다. 대신에 공정성을 중시한다면, Response Time은 짧아지지만, Turnaround Time을 희생해야 한다. 이런 종류의 Trade-off는 시스템에서 흔히 볼 수 있다.

 

우리는 두 가지 유형의 스케줄러를 살펴보았다. 첫 번째 유형(SJF, STCF)은 Turnaround Time을 최적화하지만 Response Time에는 좋지 않다. 두 번째 유형(RR)은 Response Time을 최적화하지만 Turnaround Time에 좋지 않다. 그리고 우리는 여전히 고려해보아야할 필요가 있는 두 가지 가정을 다루지 못했다. 가정 4(작업에 I/O가 없다는 가정)와 가정 5(각 작업의 런타임이 알려져 있다는 가정). 그 가정들을 다음에 다루자.

 

 

 

 

Incorporating I/O

---

가정 4를 제거해보자. 모든 프로그램은 물론 I/O를 수행한다. 어떠한 입력도 받지 않는다면, 프로그램은 늘 동일한 출력을 생성할 것이다. 출력이 없다면, 아무도 프로그램의 산출물을 볼 수 없으며 실행하는 의미가 없어진다.

 

작업이 I/O를 요청(request)하면 현재 실행중인 해당 작업은 I/O 도중 CPU를 사용하지 않을 것이며 I/O가 완료되길 기다리며 Blocked 상태가 될 것이다. I/O가 Hard disk drive로 보내지는 경우 I/O load에 따라 몇 밀리초 이상 걸릴 수 있고, 따라서 스케줄러는 그 시간 동안 다른 작업을 CPU에 할당하도록(schedule) 결정할 수 있다.

 

I/O가 완료되면 인터럽트가 발생하고 OS가 실행되어 I/O를 실행한 프로세스를 Blocked 상태에서 Ready 상태로 다시 이동합니다. 그리고, 스케줄러는 그 시점에서 그 작업을 언제 할당할 지를 결정할 수 있다.

 

Poor Use of Resource

 

Overlap allows better use of resource

이를 통해 스케줄러가 I/O를 어떻게 통합하는지 확인할 수 있다. 스케줄러는 각각의 CPU Burst를 작업으로 처리하여 대화형(interactive) 프로세스가 자주 실행되도록 한다. 이러한 대화형 작업이 I/O를 수행하는 동안 다른 CPU-Intesive(CPU 집약적) 작업이 실행되므로 프로세서를 더 잘 활용할 수 있다.

 

 

No More Oracle

---

I/O에 대한 기본적인 접근 방식을 배웠고, 이제 우리는 스케줄러가 각 작업의 길이를 알고 있다는 최종 가정을 제거해야 한다. 실제로, 범용적인 OS에서 OS는 일반적으로 각 작업의 길이에 대해 거의 알지 못합니다. 따라서, 그러한 사전 지식 없이 어떻게 SJF/STCF와 같은 방식을 구축할 수 있을까? 또한 RR 스케줄러와 함께 본 몇 가지 아이디어를 통합하여 Response Time 측면에서도 높은 성능을 내려면 어떻게 해야 할까? 다음 장에서 배우도록 하자.

 

 

 

 

---

 

 

출처 : pages.cs.wisc.edu/~remzi/OSTEP/ 

Operating Systems: Three Easy Pieces