OS-week3 [Scheduling]

CH 7. CPU scheduling

keyword

- Round Robin

7.1 Workload Assumptions

- 시스템에서 실행 중인 프로세스에 대한 가정

1. 각각의 job은 같은 시간 동안 작동한다.

2. 모든 job들은 같은 시간에 도착한다.

3. 일단 시작하면, 각각의 job은 완전히 작동된다.

4. 각각의 job들의 런타임은 알 수 있다.

7.2 Scheduling Metrics

- metric : 무언가를 측정하는 것

  ㄴ스케쥴을 짜는 것에는 다양한 metric이 있다

- turnaround time(처리 시간) : (job이 완료된 시간) - (job이 시스템에 도착한 시간)

7.3 First In, First Out (FIFO)

- First Come, First Served (FCFS)

  ㄴ 오는 순서대로 job 실행

-> 문제점: 많은 시간이 걸리는 작업을 먼저 하면 평균 처리시간이 길어짐  (1번 가정 취소)

7.4 Shortest Job First (SJF)

- SJF : 작동 시간이 짧은 job부터 처리함

- scheduler는 context switch를 수행한다

                   ㄴ 실행하던 하나의 프로세스 일시적으로 멈추고 다른 것 진행

-> 문제점: 모든 job이 동시에 도착하지 않는다면 (가정 2 취소)

              작동 시간이 긴 작업이 먼저 도착할 때 FIFO 문제점처럼 평균 처리시간 길어짐

7.5 Shortest Time-to-Completion First (STCF)

- SJF는 non-preemptive하다

- STCF = SJF + preemptive

                      ㄴ CPU를 중간에 뺏어 올 수 있다.

   ㄴ 현재 도착한 작업이 하나면 그거 실행하고 현재보다 이전에 도착한 작업이 여러개이면 

       현재 작업 중인 일을 포함해서 남은 작업 시간이 짧은 것부터 실행

   ㄴ 많약 현재 작업 중인 일이 다른 일들보다 작업완료까지 남은 시간이 길면 이 작업을 멈추고 CPU를 다른 일에 할당

7.6 A New Metric: Response Time

- response time: (job이 작동한 첫 순간)-(job이 시스템에 도착한 시간)

   ㄴ 작업 시작될 때까지 기다린 시간

-> 어떻게 response time에 민감한 스케쥴러를 만들까?

7.7 Round Robin (RR) (= time-slicing)

- 위 문제 해결 -> Round Robin scheduling  (=time slicing scheduling)

- preemptive 함

- 프로세스들 사이에 우선순위를 두지 않고 순서대로 시간단위(Time Quantum)로 CPU를 할당하는 방식

- 한번에 작업을 완료하는 것이 아니라 각 작업을 조각 내서 작업을 조금 실행한 뒤 다음 실행 큐의 다음 작업으로 전환한다.

- SJF, STCF는 처리시간은 최적이나 반응 시간이 별로이다.

- RR은 반응시간(response time)은 최적이나 처리 속도가 별로이다. 

- context switch가 너무 자주 발생할 수도 있다

7.8 Incorporating I / O

- interactive job들이 I/O를 수행하는 동안 다른 CPU를 많이 사용하는 작업을 실행 -> 프로세서를 잘 활용하는 것

- 어떤 job이  I/O 작업을 수행하면 이 job은 block되고

  스케쥴러는 다른 job에 CPU를 할당한다. 

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