Scheduling

Basic Concepts

• Resource는 두가지 종류로 나눌 수 있음
  • Preemptible Resource : 한 Process가 점유한 상태에서 다른 Process에게 양보할 수 있는 자원 (ex. Main memory)
  • Non-Preemptible Resource : 한 Process가 점유하면 사용을 마칠 때 까지 다른 Process에게 양보할 수 없는 자원 (ex. Printer)
• Resource allocation의 2가지 문제 :
  1. 여러 Process가 한 Resource를 잡을려고 할 때 누구한테 줄것인가?
  2. 일단 한 Process가 한 Resource를 잡으면 게한테 얼마만큼 오래 Resource를 부여해줄까?
• Resource allocation 문제에 대한 의사결정이 시스템의 성능에 큰 영향을 미침

CPU Burst

• Job Process
  • Batch Monitor에서의 Job : 한번 수행이 시작되면 완료될 때 까지 계속 수행되는 작업
  • Process : 끝나지 않은 Job들이 여러개 있음

• CPU Burst : Program의 수행 중에 연속적으로 CPU를 사용하는 단절된 구간

  • CPU Burst가 Scheduling의 단위가 됨

• I/O Burst : Program의 수행 중의 I/O의 완료를 기다리며 Block되는 구간

  

• CPU Burst의 Size : 이 Size에 따라서 Scheduling 기법이 달라진다

  

  • CPU Burst의 Size가 큰 것 : 과학 기술의 연산
  • CPU Burst의 Size가 작은 것 : I/O Interactive 한 것

CPU Scheduler

• CPU Scheduler가 결정하는 작업 :

1. 어떤 이유에선가 현재 Process가 수행을 더 이상 하지 않아야될 때, 다음에 어떤 Process에게 CPU를 줄까를 결정하는 작업
2. 그 Process가 CPU를 할당 받으면 얼마나 오래동안 수행할 것인가를 결정하는 작업

• CPU Scheduler는 언제 일어나나?

  

  • Ready ➡️ Running : Dispatcher가 돌아서 상태 변환
  • Running ➡️ Ready : Hardware Interrupt가 걸려서 Scheduler가 개입되고 강제로 CPU를 뺏음
  • Running ➡️ Waiting : Non-Preemptive scheduling
  • Running ➡️ Terminated : Non-Preemptive scheduling
  • Waiting ➡️ Ready : 어떤 Process가 Waiting에서 Ready로 갈려면 Asynchronous 이벤트가 발생해야된다. Asynchronous 이벤트는 Preemptive scheduling을 촉발하는 것이다.
  • scheduling는 Process state transition에서 state transition를 촉발하는 행위들이다

Scheduling Policies

• Scheduling을 통해서 성취하고자 하는 것들 :

  • Resource Utilization을 극대화

    • Utilization : 어떤 Resource가 존재하면 전체 컴퓨터 Up time중에 얼마 만큼의 시간동안 의미있는 수행을 했느냐를 나타냄

  • Overhead를 최소화 시키기

    • 즉, OS가 참여하는데 Code양이 적어야된다

  • Context switching를 최소화 시키기

    • 빈번하게 Scheduler가 뜨게되면 context switching이 많아지게 됨

  • Fairness

    • CPU time을 여러 Process에게 골고루 나눠줘야됨

    • Fairness는 상황에 따라 달라짐 :

      💁🏻 범용 System에서 Fairness :

      • 1/n 의 Share

      💁🏻 우선순위 기반 System에서 Fairness :

      • 높은 우선순위의 Process에게 CPU를 주는 것이 Fair함
      • 어떤 경우에는 Fair하지만 방치하게 되면 문제가 생김
      • 해결방법 : Aging - Task가 CPU를 기다리는 시간에 비례하여 우선순위를 점차적으로 높이는 기법

• Metric들 :

  • waiting time MIN
  • response time MIN
    • response time에 민감한 Application : User Interactive한 Application, Foreground App
  • turnaround time MIN
  • throughput MAX
  • throughput : 단위시간에 컴퓨터 시스템이 수행을 종료시키는 Process의 개수
  • throughput에 민감한 Application : CPU intensive한 것
  • 현대 OS는 throughput과 response time의 Balance를 맞추는 것이 중요한 문제

Scheduling 기법들

1. First In First Out (FIFO)

   • 먼저 들어온놈 먼저 처리

   • CPU Burst 단위로 FIFO : 한 Process가 I/O를 할 때 까지 CPU를 점유함

   • 장점 :

     1. 단순하고 직관적임

   • 단점 :

     1. CPU를 독점할 수 있음 (ex. 어떤 Process의 CPU Burst안에 무한 loop가 존재 할 경우)

        💁🏻 해결 방안 : Timer register 사용

   • FIFO에서 가장 최적의 Waiting time을 가질 수 있는 방법 :

     • scheduling sequence가 shortest job first 를 따르게 계속 순서를 바꿈

2. Shortest Job First

   • Shortest Job First는 Optimal algorithm

   • Shortest job first를 할 경우의 문제점 : OS가 Task의 남은 CPU Burst Size를 예측할 수 없음

   • Preemptive Shortest Job First :

     • 현재는 가장 짧은 CPU Burst Size의 process을 수행하고 있는데 새로운 CPU Burst Size가 더 짧은 process가 왔을 경우 rescheduling 하게됨
     • a.k.a Shortest-Remaining-Time-First (SRTF)

   • Non-Preemptive Shortest Job First :

     • 존재하지 않는 알고리즘
     • 우리가 CPU Burst Size를 다 안다는 가정 하의 알고리즘

   • CPU Burst Size를 예측하는 방법 :

     • Exponential averaging :

       

       🔺 a = 0로 설정 할 경우, 과거의 approximation 값만 고려, 최근 history는 고려 ❌

       🔺 a = 1로 설정 할 경우, 바로 지난 번의 Burst Size를 이번의 Burst Size로 받아드리겠다

       🔺 0<a<1 의 값을 통해서 최근 history와 지난 번의 예측한 값의 비율을 결정할 수 있음

       🔺 a의 설정이 케바케이기 때문에 실제 OS에 적용시키긴 어려움

3. Round Robin

   • FIFO로 scheduling을 하되 Time out 값을 둔다

     • 자기의 CPU Burst Size가 Time out 값보다 크면 수행을 강제로 종료 당하고 Ready Queue 가장 뒤로 간다

   • Round Robin 문제 :

     • Time out 값을 얼마로 둘것인지?
     • Time Slice (Time Quantum) : Task에게 CPU가 할당된 후 다음 schduling을 위한 timer interrupt가 발생할 때 까지의 시간

   • Round Robin이 FIFO보다 항상 성능이 좋은 건 아니다

     • FIFO == Round Robin ( Time Quantum = ∞ms )

   • CPU Bound Process : 대부분 시간을 CPU 연산을 하면서 보내는 Process

     • CPU Utilization 과 Thoughtput 이 높을 수록 좋음

   • I/O Bound Process : 대부분 시간을 I/O를 보낸 다음 waiting 하면서 보내고 실제 CPU 연산 시간을 짧게가지는 Process

     • Response time이 짧을 수록 좋음

   • Example.

     Process No	Characteristic
     1	- 1ms 동안 CPU연산 한 다음 I/O 유발시켜서 10ms동안 노는 Process - I/O Bound Process
     2	- I/O 없이 CPU연산만 하는 Process - CPU Bound Process

     Senario 1 : Round Robin ( Time Quantum = 100ms )

     • Process 1가 먼저 수행 할 경우

       

     Senario 2 : Round Robin ( Time Quantum = 1ms )

     • Process 1가 먼저 수행 할 경우

       

     💁🏻 CPU Utilization 과 I/O Utilization을 모두 고려해서 볼 때 Senario 2가 좋음

     💁🏻 Process 1입장에서는 Senario 2처럼 time slice가 적은 것이 좋지만 Process 2한테 있어서는 Penalty가 있음 ( Overhead 문제 : Process 2의 time slice boundary 마다 time interrupt가 발생해서 interrupt service routine이 돌게된다 )

     💁🏻 결과적으로 두 Senario 모두가 우리가 원치않는 모습들을 가지고 있다

     💁🏻 그럼 이 문제의 극복하기 위해선

     ​ 🔺 CPU Bound Process 한테는 긴 Time Quantum를 주고

     ​ 🔺 I/O Bound Process 한테는 짧은 Time Quantum를 주고 우선순위를 높여준다

4. Multi-level Feedback Queue

   • Adaptive Scheduling :

     • Workload(즉, process)의 특성에 따라 Time Quantum의 크기를 동적으로 바꿔주는Scheduling 기법
     • Process별로 Process의 특징에 따라서 Scheduling방식에 변화를 줄 수 있음

   • Multi-level Feedback Queue : Run Queue가 Multi-level로 되어있음

     • 가장 위에 있는 Queue는 우선순위가 높고 Time Quantum는 짧음

     • 밑의 level Queue일 수록 우선순위는 낮고 Time Quantum는 길다

       

     • 새로운 Process가 생성이 되면, 그 Process는 무조건 가장 우선순위 높은 Queue에 들어가 Round Robin을 한다

     • 그런데 Round Robin하다가 자기의 Time Quantum보다 더 빨리 끝났으면 그 Queue에 머물러 있고 그렇지 않으면 밑에 level의 Queue로 강등하게됨

5. Fair Share Scheduling

   • a.k.a Bandwidth Scheduling, Proportional Share Scheduling
   • 대기 중인 Process들에게 정해진 비율에 따라 CPU의 Bandwidth를 분배하는 Scheduling 기법
   • 최근에는 1/n Scheduling도 아니고 우선순위 Scheduling도 아닌 Bandwidth Scheduling이 부각하기 시작함
   • Performance isolation 할 때도 Bandwidth Scheduling이 필요함
     • Performance isolation : CPU를 많이 차지할 꺼 같은 APP이 들어왔을 때 그 APP의 영향을 격리시키는 것
   • Linux에는 CFS (Completely Fair Scheduler)이라하는 Bandwidth Scheduling Algorithm이 포함되어 있음

---

《Reference》

1. SNUON Youtube

---