5. Scheduling : Introduction

1.  Scheduling

  (1) Workload assumtions : 

    1. 각 작업은 같은 시간동안 수행됨

    2. 모든 작업은 같은 시간에 도착함

    3. 모든 작업은 오직 cpu를 사용 (즉, I/O를 수행하지 않음)

    4. 각 작업에 대한 런타임은 알려져 있음

 

 (2) 성능 측정항목

  : Turnaround time - 들어가서 나올 때까지의 시간

 : Waiting time - 프로세스가 준비상태인 큐에서 waiting하는 시간

 

(3) fairness : 성능과 fairness는 스케듈링에서 tradeoff가 있음

 

** interactive한 operation일 경우 fairness가 중요함

 

 

2. Algorithm 1 : FIFO

(1) First Come, First Served (FCFS)

  - ex. 도착 순서 : A -> B -> C(근데 거의 동시에 도착, 왜냐면 강의자료에 just before이라고 표기돼 있음) , 각 작업은 10초 동안 수행

=> Turnaround time ->  A : 10 - 0 = 10 , B : 20 - 0 = 20, C = 30 - 0 = 30

=> Average turnaround time = (10 + 20 + 30) / 3 = 20 sec

 

(2) Why FIFO is not that great? - Convoy Effect

  - 가정 1 : 프로세스의 수행 시간이 모두 다름

  - ex) A -> B -> C (Just before)

Turnaround time : A = 100 - 0 = 100, B = 110 - 0 = 110, C = 120 - 0 = 120

Average Turnaround time = (100 + 110 + 120) / 3 = 110 sec

**Turnaround time이 길어지는 이유는 먼저 수행되는 프로세스가 길게 들어와서 잡고있기 때문에 뒤차례 애들이 수행할 수 없음

B->C->A의 순서일 경우,

Turnaround time = (10 + 20 + 120) / 3 = 50 sec

**어떤 프로세스가 먼저 들어와서 수행되느냐에 따라 Turnaround time의 길이가 달라짐

 

(3) What is Convoy effect and Why is Convoy effect bad?

  - Convoy effect : ready queue 안에 집약적인 cpu 프로세스가 있고 (large burst time), 상대적으로 적은 burst time을 가졌지만 I/O bound (I/O 작업이 자주 필요함)인 여러 프로세스가 있음

**I/O burst - I/O를 요청한 뒤 기다리는 시간

I/O bound process - I/O burst가 큰 프로세스

 

 - 다음이 발생

   : I/O bound 프로세스는 처음에 할당된 cpu 시간. cpu 사용량이 적기 때문에 빠르게 실행된 다음 I/O 큐로 이동

   : cpu 집약 프로세스는 이제 cpu time을 할당. burst time이 길기 때문에 완료 시간도 긺

   : cpu 집약 프로세스가 실행되는 동안, I/O bound 프로세스는 I/O 작업을 완료하고 ready queue로 다시 돌아감

   : cpu 집약 프로세스는 여전히 끝나지 않았기 때문에 I/O bound process는 wait해야함 -> I/O 장치가 이상하게 돌아감

 

  : cpu 집약 프로세스가 끝났을 때, 이 프로세스는 I/O 장치에 접근하도록 I/O 큐로 보내짐

  : 그동안, I/O bound process는 필요한 cpu time을 얻고, 다시 I/O 큐로 돌아감

  : 그러나 cpu 집약 프로세스는 여전히 I/O 장치에 접근하고 있기 때문에 I/O bound proces는 wait해야함 -> cpu는 이상해짐

 

**I/O bound - cpu를 조금 쓰고 I/O를 많이 씀, 프로세스를 수행할 때의 대부분의 시간이 I/O를 사용할 때 쓰임 -> cpu burst의 길이가 짦음

**CPU bound - cpu burst의 길이가 긺

cpu와 i/o는 각각 큐를 갖고 대기하다가 해당 큐로 들어가서 기능

 

- Problem with FIFO scheduler

 : FIFO - Turnaround time과 waiting time은 짧은 작업이 긴 작업을 위해 기다릴 때 더 커짐 (convoy effect)

 

- Think about a new scheduler?

 : SJF (Shortest Job First) - 가장 작은 run time을 가진 job을 고름

 

 

3. Algorithm 2 : Shortest Job First (SJF)

(1) 수행 시간이 짧은 순서대로 수행 : Non-preemptive scheduler

(2) 예시

 A->B->C

A는 100초 동안 수행, B와 C는 10초동안 수행

Average Turnaround time : (10 + 20 + 120) / 3 = 50 sec

 

(3) SJF with Late Arrivals from B and C

  - 작업은 언제든지 도착할 수 있다고 가정

  - 예시 : A는 t = 0에 도착하고 100초의 수행시간을 가짐, B와 C는 t = 10에 도착하고 각각 10초의 수행시간을 가짐

-> Turnaround time : A = 100 - 0 = 100,

B = 110 - 10 = 100

c = 120 - 10 = 110

Average : (100 + 100 + 110) / 3 = 103.33 sec

 

 

4. Algorithm 3 : Shortest Time-to-Completion First (STCF)

(1) SJF + preemption -> STCF (Preemptive Shortest Job First (PSJF) 또는 Shortest Remaining Time First(STRF))

(2) 새로운 작업은 시스템 안으로 들어감

  - 남은 작업과 새 작업을 결정

  - 시간이 가장 적게 남은 작업을 스케듈링

(3) 예시

  - A는 t = 0에 도착하고 100초 동안 수행, B와 C는 t = 10에 도착해서 10초동안 수행

  => Average turnaround time = ((120 - 0) + (20 - 10) + (30 - 10))  / 3 = 50 sec

** 기존에 돌고 있던 애들이 언제 끝나는지 계산하고 새로 들어온 애의 시간을 비교해서 더 짧은 애를 돌림

 

 

 

5. Problem of SJF : Determining next CPU burst length

(1) SJF는 주어진 프로세스 세트들에 대해서 최소 평균 turnaround time과 waiting time을 가진다는 점에서 최적

  - 짧은 프로세스를 긴 프로세스보다 먼저 이동시키면 긴 프로세스의 waiting time이 늘어나는 것보다 짧은 프로세스의 waiting time이 더 짧아짐

  - 단점은 cpu burst의 길이를 알아야함 -> 길이를 예측할 수 있음

(2) 이전 cpu의 길이를 사용하여 예측할 수 있음 = exponential averaging (과거의 데이터 자료로 예측)

(3) 예시

  - α = 0

   : Tn+1 = Tn

  - α = 1

   : Tn+1 = tn

 

  - 공식:

- α와 α - 1이 둘다 1보다 작거나 같기 때문에, 각 연속 항은 이전 항보다 weight이 작음

 

 

 

 

6. New Scheduling Metric : Response Time

(1) 작업이 도착한시간 부터 처음 스케듈링된 시간까지의 시간

  : STCF와 이와 관련된 규칙들은 response time에 좋지 않음

=> 어떻게 우리는 response time에 예민한 스케듈러를 만들 수 있을까?

 

 

 

7. Algorithm 4 : Round Robin (RR) Scheduling

** 프로세스 사이에 우선순위를 두지 않고 순서대로 time quantum으로 cpu time을 할당

-> 일정 시간이 지나면 프로세스를 멈추고 다른 프로세스에게 실행할 기회를 줌

 

(1) Time-slicing Scheduling

  - 각 프로세스는 작은 단위의 cpu time을 얻음 (time quantum) , 이 시간이 지나면, 프로세스는 선점되어 ready queue에 추가됨

  - time slice의 길이는 time-interrupt 기간의 배수여야함

 

(2) 만약 ready queue에 n개의 프로세스가 있고, time quantum이 q라면, 한 번에 최대 q time unit의 청크로 cpu time의 1/n을 얻음

프로세스는 (n-1) * q time unit보다 더 많은 시간을 wait하지 않음

 

(3) Performance

  - q large => FCFS

  - q small => q는 context switch 관련하여 커야 함

 

=> RR은 fair하지만, turnaround time이나 waiting time에 대한 metric에서는 제대로 수행하지 않음

(fair하기 위해 하나씩 돌리고 있기 때문에 자기의 순서가 계속 밀리게 되고 turnaround/waiting time에서는 나쁘게 동작)

 

**타이머가 세팅이 되면 cpu한테 인터럽트를 걸어주고 메모리에서 벡터를 통해 타이머 핸들러가 동작

카운터가 1 증가 == 인터럽트가 얼마 만에 발생했는지

1/n <= q (q는 time quantum)

q가 짧아지면 context switch에 문제가 생김 -> context switch의 오버헤드가 1ms인데 프로세스에 할당된 quantum이 1ms보다 작으면 문제가 생김

context switch보다 길게 퀀텀을 잡아야함

 

(4) 예시

  - A, B, C가 동시에 도착

  - 각각 5초동안 수행하기를 원함

 

 

Response time: A = 0 - 0 = 0, B = 5 - 0 = 5, C = 10 - 0 = 10

Average response time = (0 + 5 + 10) / 3 = 5 sec

 

Response time: A = 0 - 0 = 0, B = 1 - 0 = 1, C = 2 - 0 = 2

Average = (0 + 1 + 2) / 3 = 1 sec

 

(5) The length of time slice is critical

 

  - The shorter time slice

   : 더 좋은 response time

   : context switching 의 값은 전체 성능에 영향을 줌

  

  - The longer time slice

   : cost of switching을 분할해서 분석? (Amortize the cost of switching이 대체 뭔데,,)

   : Worse response time

 

 => time slice의 길이를 결정하는 것은 시스템 디자이너에게 trade-off을 제공

**큐가 짧을 수록 response time이 줄어듦

 

 

 

8. Time quantum vs Turnaround time

 

(1) Average turnaround time은 time quantum 사이즈가 증가할 때 반드시 증가하지 않음

(2) 만약 time quantum이 너무 크다면, RR 스케듈링은 FCFS가 됨

(3) cpu burst의 80프로는 time quantum보다 짧아야함

 

**Turnaround를 줄이려면 짧은 게 먼저 들어오고 들어와서 나가면 안됨

Turnaround를 줄이기 위해 퀀텀을 늘렸더니 더 늘어났을 경우 -> 중간에 큰 게 먼저 도는 경우가 생김

 

 

9. Incorporating I/O

(1) 가정 : 모든 프로그램은 I/O를 수행

(2) 예시

  - A와 B는 각각 cpu time의 50ms가 필요함

  - A는 10ms동안 수행하고 나서 I/O request를 발행 (각 I/O는 10초가 걸림)

  - B는 단순하게 50초동안 cpu를 사용하고 I/O를 사용하지 않음

  - 수행 순서 : A -> B

 

안좋은 예시

 

B Overlap

 

(3) 작업이 I/O request를 초기화할 때,

  - 작업은 블럭되고 I/O가 완료될 때까지 기다림

  - 스케쥴러는 cpu의 다른 작업을 스케쥴링

 

(4) I/O가 완료될 때,

  - 다른 인터럽트가 발생

  - OS는 블럭된 프로세스를 다시 ready state로 돌려둠

 

**I/O request와 프로세스 수행이 같은 시간에 일어나기 때문에 오버랩이 일어날 수 밖에 없음