Chap 3.

CPU Scheduling
- 실행 가능한 프로세스 집합이 주어졌을 때 다음에 실행할 프로세스를 결정하는 것
=> 자주 발생하므로 아주 빨리 수행되어야한다

• Non-preemptive scheduling
- 스케줄러는 실행 중인 프로세스가 자발적으로 CPU를 양보할 때까지 기다림

• Preemptive scheduling
- 대부분의 스케줄러가 Preemptive scheduling이다
- 스케줄러가 현 프로세스를 중단하고 강제로 실행시킨다

용어
Workload
- 작업 설명
EX) 도착 시간, 실행 시간 등
Scheduler
- 작업 실행 시기를 결정하는 로직
Metric
- 스케줄링 품질 측정
EX) 처리 시간, 응답 시간, 공정성 등

스케쥴링 (Scheduling)
일단 가정 몇개를 하고간다.
1. 각 작업이 동일한 시간 동안 실행됨
2. 모든 작업이 동시에 도착
3. 시작되면 각 작업이 완료될 때까지 실행됨
4. 모든 작업은 CPU만 사용(즉, I/O를 수행하지 않음)
5. 각 작업의 런타임을 알 수 있음

Scheduling Metrics (스케줄링 지표)
Performance metric(성능 지표) : Turnaround time
Turnaround time 이란? 작업이 완료된 시간에서 시스템에 작업이 도착한 시간을 뺀 값

Fairness Metrics (공정함 지표)
- Performance랑 fairness 는 종종 상충됨

FIFO (First In First Out)
=> First Come, First Served (FCFS)
- 매우 간단하고 구현하기 쉬움
- 줄을 서 있는 사람들의 "실제" 스케줄링이라고 생각하면 됨
- Non-preemptive
- 모든 작업들이 똑같이 취급됨(우선순위 없음, 미리 온 순서 ㅇㅇ)
=> starvation이 없음

예시 문제
- A arrived just before B which arrived just before C.
- Each job runs for 10 seconds.

그렇다면 FIFO가 완벽한가?
이제 첫번째 가정을 무시한다
=> 1. 이제 각 작업이 동일한 실행 시간을 가지지않음 (기존 10초)
Example:
- A arrived just before B which arrived just before C.
- A runs for 100 seconds, B and C run for 10 each.

=> A가 실행시간이 너무 길어버리니 B와 C는 A가 끝날때까지 무한정으로 기다려버리면서 turnaround time이 길어져버렸다
~~이럴수가 배울게 더 늘어버렸잖아~~

SJF (Shortest Job First)
: 짧은 작업부터 실행
- 각 작업에는 실행 시간이 가변적임
- Non-preemptive scheduler
Example:
- A arrived just before B which arrived just before C.
- A runs for 100 seconds, B and C run for 10 each.

=> 이제 B와 C가 먼저 실행될수있어서 turnaround time이 확 줄어버렸다
==> 그러면 SJF는 완벽한가??

SJF with Late Arrivals from B and C
두번째 가정을 무시해버려보자
2: 작업들은 언제나 도착할수있다
• Example:
• A arrives at t=0 and needs to run for 100 seconds.
• B and C arrive at t=10 and each need to run for 10 seconds

=> A보다 B와 C가 늦게 도착하면서 A가 먼저 실행되어버리는 ~~불상사~~사건이 일어나버렸다
~~안돼..시험범위가 늘고있어...~~

Shortest Time-to-Completion First (STCF) (or Preemptive Shortest Job First (PSJF) )
• SJF에 preemption 추가
• 가정 2 무시, 작업은 동시에 시작되지않을수있음
• 가정 3 무시, 작업은 완료되지않았어도 중단될수있음
=>
• 새 작업이 시스템에서 시작됨
• 남아있는 작업과 실행해야할 작업들을 비교
• 남은 시간이 가장 짧은 작업을 스케줄링

• Example:
• A arrives at t=0 and needs to run for 100 seconds.
• B and C arrive at t=10 and each need to run for 10 seconds

=> A가 실행되는 중간에 아예 중단시키고 늦게 도착한 B와 C를 실행한후 다시 A를 실행한다
=> Preemptive scheduling

여기서 새로운 지표를 알아보자
Response time
- 작업이 도착한 시점부터 처음 스케쥴링된 시점까지의 시간

STCF는 response time 지표에서 봤을때 그리 좋지않은 알고리즘임

Round Robin (RR) Scheduling
- Time slicing Scheduling
• 슬라이싱된 일정 시간 동안 작업을 실행한 다음 작업이 완료될 때까지 Run queue의 다음 작업으로 전환
• Run queue 는 circular FIFO queue 로 취급
• Time slice는 scheduling quantum으로도 불림
• 작업이 완료될때까지 수행
• 타임 슬라이스의 길이는 타이머 인터럽트 시간의 배수여야함
• Preemptive, starvation 없음
=> RR 는 fair (no starvation)이지만, turnaround time 성능이 좋지않음
=> 완료까지의 시간이 길어지기 때문

타임 슬라이스의 길이가 중요함
짧은 타임 슬라이스
- 오버헤드 높아짐
- 더 나은 response time
- context switching cost가 전체 성능을 좌우
더 긴 타임 슬라이스
- 오버헤드 낮아짐
• context switching cost의 영향을 덜 받음
• 더 나빠진 response time

I/O 통합 (Incorporating I/O)
• 가정 4 무시, 이제 모든 프로그램들이 I/O 요청을 한다.
작업이 I/O 요청을 하는 경우
- 작업은 I/O가 완료될때까지 block됨
- 스케쥴러는 그동안 CPU가 다른 작업을 할수있도록 스케쥴링함
I/O가 완료된 경우
- 인터럽트 발생
- OS는 프로세스가 block된 상태에서 ready state로 전환

CPU Schedular
목표
- turnaround time (처리 시간) 최적화
- workload : 프로세스가 생겨서 그 프로세스의 정보 or 무엇인지 로드하는 것
=> SJF, STCF : workloads 에 대해 사전지식이 없음 ( = 각 작업의 런타임을 알수없음) (가정 5)
- 상호적인 작업에서의 response time을 최소화
=> RR : bad turnaround time

==> 그렇다면 스케줄러는 어떻게 작업의 특징(characteristic) 을 알고 더 나은 결정을 내릴수있을까?
-> 과거를 통해 미래를 예상
EX) branch predictor, cache algolrithm

MLFQ
- MLFQ에는 여러 개의 다른 큐가 있음
=> 각 큐에는 서로 다른 우선 순위 레벨이 할당
- 상위 대기열에 있는 작업을 실행하도록 선택
- 동일한 큐에 있는 작업 간에 RR 사용

- MLFQ 는 작업 우선순위를 작업의 동작에 따라(observed behavior) 바꿈
=>
- 상호작용하는 작업
짧은 실행시간을 가지고, 빠른 response time을 필요로 함
I/O 작업을 기다리는 동안 작업은 반복해서 CPU를 사용함 (짧게 여러번 사용, 요청을 기다리는 동안 작업은 blocked 상태가 되기 때문)
=> 우선 순위를 높게 유지함

- CPU-intensive jobs
CPU를 굉장히 오랜 기간동안 사용하는 작업
response time에 구애받지않음 (don't care)
=> 우선 순위를 낮게 유지함

MLFQ 우선순위 조정 알고리즘에 의해 바뀐 가정
가정 3 시작되면 각 작업이 완료될 때까지 실행됨
-> 규칙 3. 각 작업이 시스템에 enter하면 최우선 순위에 위치함
가정 4 모든 작업은 CPU만 사용(즉, I/O를 수행하지 않음)
-> 규칙 4.a. 만약 작업이 실행되는 동안 타임 슬라이스를 모두 사용한다면 우선순위를 낮춘다.
-> 규칙 4.b. 만약 작업이 타임 슬라이스 이내에 CPU를 사용을 끝마쳤다면 (I/O처럼) 우선순위는 그대로 유지함
==> 이런 점에서 MLFQ는 SJF와 유사하다

EX)

조건
타임 슬라이스 : 10ms
작업 A : CPU를 오래 사용하는 긴 작업
작업 B : 짧은 작업 (20ms 런타임)
=> A가 먼저 작업되어지다가 B가 100ms에 도착

조건
타임 슬라이스 : 10ms
작업 A : CPU를 오래 사용하는 긴 작업
작업 B : 1ms 마다 I/O를 수행하는 작업
=> 작업 B의 I/O가 타임 슬라이스보다 짧게 수행되기에 규칙 4.b에 의해 B는 계속해서 우선순위가 유지된다.

MLFQ의 문제점
- Starvation
만약 너무 많은 상호작용 작업들 (I/O작업, interactive job)이 시스템에 있을때
오랫동안 실행되는 작업들은 정해진 타임슬라이스를 모두 사용하고 우선순위가 낮아지면서 I/O 작업들의 우선순위에 밀려 CPU를 할당받지못한다
- Game the scheduler ~~스케쥴러 농락~~
99%의 타임 슬라이스를 사용하고 I/O작업을 수행하게 한다
이렇게되면 작업은 계속해서 높은 우선순위를 유지하고, higher percentage of CPU time을 얻는다
- 프로그램이 시간에 따라 동작을 바꿀수있다
CPU bound process -> I/O bound process
=> 얘도 마찬가지로 I/O로 높은 우선순위 유지

해결
- 규칙 5 추가 : 일정 시간(S, 부두상수)마다 모든 작업들을 시스템의 최상단 큐로 이동시킨다