스캐줄링 소개

• Workload(작업량) 가정

1. 각 작업들은 같은 시간동안 작동한다.
2. 모든 작업들은 같은 시간에 도착한다.
3. 모든 작업은 CPU만을 이용한다.(I/O(disk, network)이용하지 않는다.)
4. 각 작업의 run-time은 알려져있다.

스캐줄링 Metrics

• Performance metric : Turnaround time
  • 작업의 완수시간에서 작업의 도착 시간을 뺀 시간
    Tturnaround = Tcompletion - Tarriaval
• fairness
  • 성능과 공정성은 종종 스캐줄링에서 상충한다.

First IN, First Out(FIFO)

• First Come First Served(FCFS)
  • 아주 간단하고 실행하기 단순하다.
• 예시
  A가 B바로 전에 도착했고, B는 C바로 전에 도착했다. 각 작업들은 10초동안 실행된다. 평균 turnaround time은?

Tturnaroundtime = Tcompletion - Tarriaval
TAturnaroundtime = 10 - 0 = 10s
TBturnaroundtime = 20 - 0 = 20s
TCturnaroundtime = 30 - 0 = 30s

TAVGturnaroundtime = (10+20+30) / 3 = 20s

왜 FIFO가 좋지 않냐 - Convoy effect

• 가정1을 한번 빼보자 : 각 작업은 더이상 같은 시간동안 동작하지 않는다.
• 예시
  A가 B바로 전에 도착했고, B는 C바로 전에 도착했다. A는 100s 동안 실행, B,C는 각각 10s 동안 실행된다.
  Tturnaroundtime = Tcompletion - Tarriaval
  TAturnaroundtime = 100 - 0 = 100s
  TBturnaroundtime = 110 - 0 = 110s
  TCturnaroundtime = 120 - 0 = 120s

TAVGturnaroundtime = (100+110+120) / 3 = 110s
=> CPU사용시간이 너무 긴 프로세스 때문에 사용시간이 짧은 프로세스의 대기시간이 너무 길어진다.

Shortest job First(SJF)

• 가장 짧은 작업을 먼저하고, 다음 짧은 작업,.. 순으로 실행시킨다.

  • 비선정형 스케줄러(선정형 : 끝나기 전에 다른 프로그램 사용 가능)

• 예시
  A가 B바로 전에 도착했고, B는 C바로 전에 도착했다. A는 100s 동안 실행, B,C는 각각 10s 동안 실행된다.
  Tturnaroundtime = Tcompletion - Tarriaval
  TAturnaroundtime = 120 - 0 = 120s
  TBturnaroundtime = 10 - 0 = 10s
  TCturnaroundtime = 20 - 0 = 20s

TAVGturnaroundtime = (120+10+20) / 3 = 50s

SJF의 문제: 만일 B,C가 늦게 오면?

• 가정 2를 한번 빼보자 : 작업은 어느 시간이나 올 수 있다.
• 예시
  A는 t = 0에서 도착했고, B,C가 10s에 도착했다. A는 100s 동안 실행, B,C는 각각 10s 동안 실행된다.

Tturnaroundtime = Tcompletion - Tarriaval
TAturnaroundtime = 100 - 0 = 100s
TBturnaroundtime = 110 - 10 = 100s
TCturnaroundtime = 120 - 10 = 110s

TAVGturnaroundtime = (100+100+110) / 3 = 103.33s

Shortest Time-to-Completion First(STCF)

• 선정성을 SJF에 추가해 주자

  • Preemptive Shortest Job First(PSJF)라고도 알려져있음

• 새로운 작업이 시스템에 들어올때.

  • 새로운 작업을 포함하여 남아있는 작업들 중에서 최소의 시간이 걸리는 작업을 스케줄링한다.

• 예시
  A는 t = 0에서 도착했고, B,C가 10s에 도착했다. A는 100s 동안 실행, B,C는 각각 10s 동안 실행된다.

Tturnaroundtime = Tcompletion - Tarriaval
TAturnaroundtime = 120 - 0 = 120s
TBturnaroundtime = 20 - 10 = 10s
TCturnaroundtime = 30 - 10 = 20s

TAVGturnaroundtime = (120+10+20) / 3 = 50s

새로운 스캐줄링 metric : response time

• 작업이 도착한 시간부터 그것이 스캐줄링된 시간까지의 시간
  Treseponse = Tfirstrun - Tarrival

• STCF과 관련된 기술들은 response time에 특히 좋지 않다.

• 우리가 response time에 민감한 스케줄러를 만드는 방법은 뭐가 있을까?

• 예시
  A는 t=0에 도착했고 B는 바로 다음에 도착했다. A는 10s 동안 실행되고 B는 9s동안 실행된다. A와 B의 response time은?(SJF를 이용하라)

Treseponse = Tfirstrun - Tarrival
TAreseponse = 9 - 0 = 9s
TBresponse = 0-0 = 0s

Round Robin(RR) Scheduling

• Time slicing Scheduling

  • run queue에서 작업이 끝날 때까지 time slice(1ms, 10ms)동안 작업을 수행하고 다음 작업을 수행한다.
    • Time slice는 가끔 scheduling quantum이라고도 불린다.
  • 작업이 끝날 때까지 반복적으로 작업을 수행한다.
  • time slice의 길이는 timer interrupt 주기의 배수여야 한다.

• RR은 공정하지만 turnaroundtime과 같은 메트릭스에서 좋지않은 성능을 낸다.

• 예시
  A,B,C는 동시에 도착했다. 각각은 5초동안 실행된다.

1. SJF이용(turnaround time good, response time bad)
   Treseponse = Tfirstrun - Tarrival
   TAreseponse = 0 - 0 = 0s
   TBresponse = 5 - 0 = 5s
   TCresponse = 10 - 0 = 10s

TAVGresponse = (0+ 5 + 10) / 3 = 5s

Tturnaroundtime = Tcompletion - Tarriaval
TAturnaroundtime = 5 - 0 = 5s
TBturnaroundtime = 10 - 0 = 10s
TCturnaroundtime = 15 - 0 = 15s

TAVGturnaroundtime = (5 + 10 + 15) / 3 = 10s

2. RR이용(time slice 1s) (turnaround time bad, response time good)
   Treseponse = Tfirstrun - Tarrival
   TAreseponse = 0 - 0 = 0s
   TBresponse = 1 - 0 = 1s
   TCresponse = 2 - 0 = 2s

TAVGresponse = (0 + 1 + 2)/3 = 1s

Tturnaroundtime = Tcompletion - Tarriaval
TAturnaroundtime = 13 - 0 = 13s
TBturnaroundtime = 14 - 0 = 14s
TCturnaroundtime = 15 - 0 = 15s

TAVGturnaroundtime = (13 + 14 + 15) / 3 = 14s

time slice의 길이는 중요하다.

• time slice가 작을 수록(1~10ms보다 작은 0.1ms)

  • response time이 좋다
  • context switching의 비용이 전체적인 성능을 지배할 것이다.

• time slice가 클수록

  • switching의 비용을 줄여준다.
  • response time이 나쁘다.

• time slice의 길이를 결정하는 것은 시스템 디자이너에게 trade off를 보여준다.

Incorporating I/O

• 가정3을 빼보자 : 모든 프로그램이 I/O를 수행한다.
• 예시
  A,B는 50ms의 CPU를 필요로 한다. A는 10ms동안 작동하고 I/O 요청을 수행한다.각 I/O 요청은 10ms가 걸리고 B는 단순히 CPU를 50ms동안 이용하고 I/O요청을 수행하지 않는다. 스캐줄러는 A를 먼저, B를 나중에 수행한다.

• 작업이 I/O 요청을 시작하면
  • 작업은 I/O 완료를 기다리는 동안 block된다.
  • 스케줄러는 CPU에서 다른 작업을 스캐줄 해야한다.
• I/O가 완료되면
  • interrupt가 발생한다.
  • OS는 프로세스를 blocked에서 ready상태로 옮긴다.