[OSTEP] Ch3.1. Scheduling: turnaround time, FIFO, SJF, STCF.

Operating Systems: Three Easy Pieces: Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau
https://pages.cs.wisc.edu/~remzi/OSTEP/
본 글은 위 교재을 주교재로 한 학교 '운영체제(Operating Systems)' 수업을 들으며 공부한 내용을 정리한 글입니다.

해당 글은 개인 공부 및 교육 목적으로 작성하였으며, 일부 교재에 첨부된 사진(또는 교재에서 강의노트로 첨부된 사진)들을 포함하고 있습니다.
교재 출처 사진을 최소화하고자 블로그에는 핵심 사진을 제외하곤 옮기지 않은 사진들도 있습니다. 따라서 고의로 누락한 사진들이 존재하며, 해당 사진들을 언급하는 내용이 있을 수 있습니다. 누락한 사진들은 직접 교재를 참고해 주세요.

혹시 문제가 있다면, 댓글 남겨주시면 빠른 시일 내에 확인 후 적절한 조치를 취하겠습니다.

---

Vocabulary

• 워크로드(Workload): 작업(Job)을 설명하는 것들의 집합(시스템 도착 시간, 실행 시간 등). 각 프로세스들이 얼만큼의 자원을 필요로 하느냐를 뜻함.
• 작업(Job): 현재 프로세스의 CPU 버스트(burst)라고 생각하면 됨.
  • CPU 버스트(Burst): 프로세스가 CPU에서 실행되는 연속적인 시간(기간), 또는 그 시간 동안의 작업(Job).
  • I/O 버스트(Burst): 프로세스가 I/O 장치를 사용하여 데이터를 읽거나 쓰는 시간(기간). 또는 그 시간 동안의 작업(Job).
• 프로세스는 이 CPU 버스트와 I/O 버스트를 번갈아 가며 실행함.
  • 프로세스가 레디 큐(ready queue)와 블락드 큐(blocked queue)를 왔다갔다 한다는 걸 의미.
• 스케쥴러(Scheduler): 준비된 작업(Job)들 중 어떤 작업을 실행할 지 결정하는 로직.
• 메트릭(Metric): 스케쥴링을 얼마나 잘 하고 있나 그 퀄리티를 측정하는 측도.
  • 스케쥴링을 할 때, 목적으로 하는 바(goals)(이후 설명)가 있음. 그럼, 그걸 해당 스케쥴링 폴리시가 타 스케쥴링 폴리시에 비해 얼마나 ‘잘’하고 있냐를 평가하는 측도가 필요함.
  • 교수) 이 메트릭은 우리가 나중에 뭘 하게 되냐에따라 달라질 수 있음. ml이면 accuracy 이런 게 메트릭.
• 스케쥴링(Scheduling): 운영체제가 어떤 프로세스를 실행할지 결정하는 과정. ‘스케쥴링하다’ 이렇게 나는 동사로 씀.
  • 스케쥴링을 하는 이유: 하나의 하드웨어 자원을 각각의 프로세스가 일정 시간 이용해야 하므로 각각에게 시간분배를 적절히 해주기 위함.
• 스케쥴러(Scheduler): 운영체제에서 프로세스들에게 CPU, 메모리, I/O 등의 자원을 할당하는 역할을 하는 모듈(프로그램).

Policy vs Mechanism

• 운영체제의 두 가지 중요한 설계 및 구현 원칙(principle)이 있음.
• Policy(폴리시, 정책)
  • what에 해당하는, 무엇을 어떻게 할지에 해당.
  • ‘설계 철학’이라고 보면 됨.
  • policy에서 하는 결정들은 자원 할당 문제에 있어서 중요함.
• mechanism(메카니즘, 기법)
  • how에 해당하는, 어떻게 할지에 해당.
  • ‘실제 구현’이라고 보면 됨.
  • policy들을 구현하기 위한 도구임.
• 저번 챕터에서 우리가 해온 건, context switch와 같은 저수준의 메커니즘들을 공부한 것임.
• 이제부터 우리는 OS 스케쥴러의 고수준의 폴리시를 공부할 것임.
  • 즉, 스케쥴링 폴리시를 공부할 것임.

Examples: Policy vs Mechanism

• ex1. 차향 주행 보조 시스템을 우리가 개발하고자 함.
  • 목적: 안전 주행을 도와주는 거임.
  • 폴리시: 전방 추돌 방지 보조 알고리즘
    • 알고리즘1 : 센서로 전방에 있는 모든 객체를 감지해서 거리를 측정해 그에 따라 속도를 조절
    • 알고리즘2 : 좀더 향상된 건데, 센서를 통해서 주변 객체와 거리를 갖는데, 그 객체가 가진 이동거리를 가지고, 어떻게 움직일 거라 예측해서 그에 따라 속도를 조절
    • 이런, OS가 작동하기 위한 알고리즘을 폴리시라고 부름.
  • 메카니즘: 브레이크, 엑셀
    • 브레이크: 차량의 속도를 늦춤.
    • 엑셀: 차량의 속도를 높임.
  • 이들의 기능은 이미 메카니즘으로 구현돼있기 때문에, 1 알고리즘에서 2 알고리즘으로 옮겨도, 난 그냥 센서값 제어만 신경쓰면 됨. → 폴리시와 메커니즘이 잘 구분된 사례.
  • 근데, 만약 둘이 잘 구분이 안돼 있다면 (= 브레이크, 엑셀 기능이 각 알고리즘에 귀속돼 있음) 알고리즘 바꿀 때 새로 메커니즘을 구현해야함.
• ex2. CPU queue에 일들을 할당해주고 싶음.
  • 폴리시: 스케쥴링 알고리즘들
    • FIFO: First In First Out
    • SJF: Shortest Job First
    • priority scheduling
  • 메커니즘 : CPU dispatcher
    • 스케쥴링 결과에 따라 특정 작업을 CPU에게 할당하는 것을 실제로 수행하는 녀석임.
  • 둘이 분리가 잘 돼있으면, queue에 실을 순서를 바꾸더라도 cpu dispatcher를 새로 구현하지 않아도 됨.

Separation of Policy and Mechanism?

• 교수 사담) 폴리시랑 메커니즘을 분리하면 성능이 떨어질 수밖에 없음.
  • 예를 들어, 브레이크도 어떨 때는 부드럽게 누르고, 어떨 때는 세게 눌러야 하는데 뭐 그런 걸 폴리시랑 붙여서 구현하면, 이 알고리즘에 맞게 적합하게 구현할 수 있는데, 분리시켜서 구현하면 단일 기능으로 해야돼서 성능이 떨어짐.
  • 그래서 이걸 분리시키면 프로그래머가 좋아하고, 붙이면 user가 좋아함(성능이 좋음).
    • 그래서 실제 제품은 많이들 붙여 놓음. 윈도우, 리눅스 등등, 전부 다 프로그래머 쉽게 하는 건 다 무시하고, 프로그래머들 겁나 힘들지만 성능 겁나 좋은 게 시장을 지배하고 있음.

Scheduling: Introduction

• 우선, 워크로드에 대해 몇 가지를 가정하고 들어가자.(워크로드의 뜻은 위에서 설명했다.)
• 다음 가정들은 비현실적이긴 하나, 당장 우리가 논의하는 데에는 아무 문제가 없다. 앞으로 논의가 진행됨에 따라 가정을 완화시킬 것이고, 최종적으로 제대로 동작하는 스케쥴링 폴리시를 만들 것이다.
  • 가정1: 모든 작업은 같은 시간 동안 실행된다.
    • ‘동시에’가 아님! 같은 시간(기간) 동안.
  • 가정2: 모든 작업은 같은 시간에(동시에) 시스템에 도착한다.
    • 실제론, 동시에 도착하지 않음. 왜냐면 스케쥴러는 여러 개가 아니라 한 개이기 때문.
  • 가정3: 각 작업은 시작되면 완료될 때까지 실행된다.
    • 한번 CPU를 차지한 작업은 CPU를 절대 뺏기지 않는다는 가정.
    • (이건 강의노트에는 없지만 교재에는 있음)
  • 가정4: 모든 작업은 CPU만을 사용한다.
    • (다시 말해, 그들은 I/O를 수행하지 않는다. → I/O burst는 무시한다.)
  • 가정5: 각 작업의 런타임(실행 시간)은 사전에 알려져 있다.
    • (이건 특히나 더 비현실적임. 스케쥴러가 각 프로세스들에 대해 모든 걸 다 알고 있다는 게 얼마나 비연실적인가!)

Scheduling Metrics

T_turnaround = T_completion - T_arrival

• 성능 측면에서의 메트릭(Performance Metric): 반환 시간(Turnaround Time)
  • 작업이 완료되는 시간에서 작업이 (CPU queue에) 도착한 시간을 빼면 된다.
  • 여기서, 우리는 모든 작업이 동시에 도착한다고 가정했으므로, T_arrival = 0이라고 생각할 수 있다.
  • 따라서, 아직까지의 가정으로는 T_turnaround = T_completion이다.
• 또 다른 메트릭: 공정성(Fairness)
  • cpu의 자원을 얼마나 여러 프로세스들이 형평성있게 분배받았냐.
  • 성능과 공정성은 스케쥴링에서 자주 상충되는 목표이다.
  • 예를 들어, 스케쥴러는 성능을 극대화하기 위해 몇몇 작업의 실행을 강제로 중지할 수 있지만, 이 경우 공정성이 악화되게 된다.
• 대략적으로, 스케쥴러의 performance이 좋은 건 turnaround time이 짧다는 것에 대응되고, 스케쥴러의 fairness가 높은 건 response time이 짧다는 것에 대응된다 생각해도 됨.

First In, First Out(FIFO)

• First Come, First Served(FCFS)라고도 불림.
• 단순하고 구현하기 쉬운, 가장 기초적인 스케쥴링 알고리즘이다.
• Example:

  

   
  • 우리가 A B C 3개의 작업을 가지고 있고, 세 작업이 (거의) 동시에 (아주 약간의 차이를 두고) 순서대로 시스템에 도착했다고 생각해 보자.
    • 실제로 정말 동시에 세 작업이 시스템에 도착할 순 없으니, 저렇게 표현한 것.
  • 그러면, FIFO 알고리즘에 따라 각 작업들이 순서대로 스케쥴링된다.
  • 모든 작업들이 가정1에 따라 동일하게 10초씩 실행된다고 하면, Arerage Turnarount Time = (10 + 20 + 30) / 3 = 20초가 된다.

 

Why FIFO is not that great? - Convoy effect

• 그러나, 이러한 FIFO 알고리즘은 그다지 좋지 못하다.
• 이제 가정1(모든 작업은 같은 시간 동안 실행된다.)을 완화해 보자.
  • → 이제 모든 작업은 더 이상 같은 시간동안 실행되지 않는다.
• Example:

  

   
  • 아까처럼 A B C 순서대로 거의 동시에 도착했고,
  • A가 100초 동안, B와 C는 10초동안 실행되어야 하는 상황.
  • 이제, Arerage Turnarount Time = (100 + 110 + 120) / 3 = 110초 로 아까 20초보다 상당히 길어진 걸 볼 수 있다.
• 이처럼 CPU 사용시간이 긴 프로세스에 의해 사용시간이 짧은 프로세스들이 오래 기다리는 현상을 Convey effect 라고 부름.

• 

  
  
  • FIFO 알고리즘에서 첫 번째 작업이 긴 실행 시간을 갖는 경우, 뒤따르는 작업들이 기다리게 되어 Arerage Turnarount Time이 길어지는 문제 또한 Convey effect의 사례라고 할 수 있음.
  • → 이걸 해결하기 위해, SJF를 도입함.

 

 

Passing the Tractor: Shortest Job First(SJF)(최단 작업 우선)

• 가장 짧은 실행 시간을 가진 작업을 먼저 실행하는 방식.
  • 이거는 나올 선점 스케쥴링 방식이 아닌, 비선점 스케쥴링 방식임.
  • 모든 작업이 시스템에 동시에 도착한다면, SJF가 항상 최적의 스케쥴링 해를 도출함을(최적의 스케쥴링 알고리즘임을) 증명할 수 있음(다만 하진 않을 거임).
• Example:

  

  • 아까처럼 A B C 순서대로 거의 동시에 도착했고,
  • A가 100초 동안, B와 C는 10초동안 실행되어야 하는 상황.
  • 이제, A B C 순서대로 스케쥴링되지 않고, 가장 짧은 순서대로 B, C, A 순서대로 스케쥴링되면서,
  • Arerage Turnarount Time = (10 + 20 + 120) / 3 = 50초 로 FIFO에 비해 더 짧은 시간을 보이는 걸 볼 수 있다.

SJF with Late Arrivals from B and C

• 이제 가정2(모든 작업은 같은 시간에(동시에) 시스템에 도착한다.)를 완화해보자.
  • → 이제 모든 작업은 더 이상 같은 시간에(동시에) 시스템에 도착하지 않는다.
• Example:

  

  • A가 t=0에 도착했고, 100초 동안 실행되어야 하고,
  • B와 C는 t=10에 도착했고, 각각 10초동안 실행되어야 하는 상황.
  • 이 경우, B와 C가 A보다 실행 시간이 짧지만, A가 시스템에 먼저 도착했기에 A가 100초 동안 먼저 실행돼버림.
  • Arerage Turnarount Time = (100 + 100 + 110) / 3 = 103.33초 로 시간이 확 느려진 걸 볼 수 있다.

선점 스케쥴링 방식(Preemptive Scheduling)

• 이전의 스케쥴러들
  • FIFO와 SJF는 비선점적(non-preemptive)임.
  • OS는 이전의 작업이 CPU를 자진해서 포기했을 때만 새로운 작업을 스케쥴함.
• 새로운 스케쥴러
  • 선점적(Preemptive): 언제든지 잠재적으로 실행 중인 작업에서 CPU를 뺏어와서 다른 작업을 스케쥴할 수 있음.
    • 번역어가 ‘선점적인’이긴 한데, 직관적으론 ‘뺏어올 수 있는’정도의 의미임.
  • 예시로는 STCF(Shortest Time-to-Completion First)가 있음.
  • 언제나 더 빨리 작업을 완료할 작업만을 실행시킴.
  • 이론적으로 모든 현대 스케쥴러들은 선점적임.

Shortest Time-to-Completion First(STCF)(최소 잔여 시간 우선)

• 이제 가정3(각 작업은 시작되면 완료될 때까지 실행된다.)을 완화해보자.
  • → 이제 각 작업은 완료되기 전에 실행이 정지(pause)될 수 있다.
• SJF에 선점적인 특성을 추가한 스케쥴링 방식이다.
  • 그래서 Preemptive Shortest Job First(PSJF)라고도 불린다.
  • 이건, 가정3(각 작업의 런타임(실행 시간)은 사전에 알려져 있다) 덕분에 가능한 스케쥴링 방식임. 끝나는 시간을 실제론 우린 모름.
• 새로운 작업이 시스템에 들어오면?
  • 스케쥴러는 남아 있는 작업들과 새로운 작업의 잔여 시간(time-to-completion)을 계산하고,
  • 그 중 최소 잔여 시간(Shortest Time-to-Completion)을 가진 작업을 스케쥴한다.
• Example:

  

  • 아까 그 예시를 다시 가져와보자.
    • 즉, A가 t=0에 도착했고, 100초 동안 실행되어야 하고,
    • B와 C는 t=10에 도착했고, 각각 10초동안 실행되어야 하는 상황.
  • 이제, A가 실행되다가 B가 시스템에 도착한 순간, OS는 A를 정지시키고 B를 실행시킴.
  • Arerage Turnarount Time = (120 + 10 + 20) / 3 = 50초 로 시간이 확 짧아진 걸 볼 수 있음.