5. CPU Scheduling
프로그램을 실행하는 과정을 2가지로 나눠보면 cpu와 i/o로 나눠볼 수 있음.
CPU 버스트와 I/O 버스트의 교대 순서
프로세스마다 cpu burst가 길기도 하고 짧기도 하고 다르다.
계산을 열심히 하는 프로그램은 cpu를 주로 쓸것임.
y축인 frequency는 cpu를 달라고 하는 빈도임.
x축은 cpu를 사용하는 시간 정도임.
CPU Scheduler
실행할 준비가 되어 있는 프로세스들 중에서 프로세스 하나를 선택한다.
cpu말고도 disk라던가 network라던가 queue를 사용하며 유사 문제가 있다.
- CPU scheduling은 언제 프로세스를 교체하겠다고 결정하는걸까?
- ex) I/O request될 때, running state → waiting state(blocked)로 스위치할때
- ex) time slice expiration(만료)될 때, running → ready state로 스위치할때
- ex) I/O completion, waiting → ready state로 스위치할 때
- 프로세스가 terminate 될 때
→ 1, 4번은 자발적으로 cpu를 내놓는 상황이다. 따라서 non-preemptive 비선점적이다.
→ 2, 3번은 강제로 뺏는 것이므로 preemptive 선점적이다.
# Scheduling Criteria 스케쥴링 평가척도
**CPU Utilization**: cpu 유용성- cpu의 사용량을 최대한 유지한다. as busy as possible (0% ~ 100%)
**Throughput**: 작업 처리량- 시간 단위 당 완료되는 프로세스의 수
Turnaround time: 소요시간- 요청을 제출한 후 완료 될 때까지의 시간
**Waiting time**: Queue에 줄 서있는 대기 시간- 프로세스가 ready queue에서 대기한 시간의 합계
Response time: Queue에 처음 들어와서 첫번째 응답이 오기까지의 시간- 요청한 후 첫번째 응답이 나올 때까지의 시간
Scheduling algorithm’s goals 스케쥴링 알고리즘의 목표
- CPU utilization의 극대화
- throughput 극대화
- turnaround time 최소화
- waiting time 최소화
- response time 최소화
-
response time의 평균보다 평균편차를 최소화하는 것이 더 중요할 지도 모른다.
-
E.g. interactive system
-
Introduction
Workload assumptions
몇가지를 가정하고 알고리즘에 대해 알아보자.
- 각각의 일은 same amount of time 동안 일한다.
- 모든 일은 같은 시간에 arrive(도착)한다.
- 시작되면, 각 작업이 완료될 때까지 실행된다. (non-preemptive)
- 각 작업은 오직 CPU만 사용한다. (i.e., 그들은 I/O를 수행하지 않는다.)
- 각 작업의 run-time은 알 수 있다.
# Scheduling Metrics
Performance metric : Turnaround Time
Turnaround Time은 프로세스가 Queue에 들어와서 수행이 완료될 때까지의 시간이다.
즉, 완료된 시간에서 시스템에 도착한 시간을 빼면 된다.
### Another metric is **fairness(공정성)**
성능과 공정성은 종종 shceduling에 있어서 상충된다.
First In, First Out (FIFO)
- 먼저 오면 먼저 제공되는 First Come, First Served (FCFS)라고도 부름. → 매우 간단하고 구현하기 쉽다.
- 예시:
- A가 B전에 도착했고, B는 C 전에 도착했다. 즉 A→B→C 순서로 도착.
- 각 작업은 10 seconds동안 실행한다
단점은? Convoy effect
만약 프로세스 실행 시간이 다 다르면?
if, A는 100초, B,C는 10초라고 한다면? 대기는 똑같이 0초부터 함.
→ 먼저 온 프로세스가 오랫동안 사용한다면 평균 대기 시간이 길어진다.
Shortest Job First (SJF)
a→b→c 순서로 들어왔는데, a=100, b,c=10초 걸리니까
b와 c를 먼저 하고 그 다음 A를 하는거임.
→ shortest job 먼저 수행하자는 것임.
Late Arrivals
A는 똑같이 0초에 들어와 100초 동안 수행함.
근데 B, C는 10초에 들어와서 10초동안 수행함.
처음엔 아무것도 없으니까 A가 계속 실행하는 도중에 B, C가 들어와도
A가 실행중이니까 끝날때까지 계속 기다림.
Shortest Time-to-Completion First (STCF)
- SJF는 non-preemption이라 문제였음.
- 그러면 preemption이라면?
SJF = STCF = PSJF(Preemtive Shortest Job First) = SRTF(Shortes Remaining Time First)
- 새로운 작업이 들어오면 남아있는 시간이랑 새로 들어온 프로세스 시간이랑 비교해서 짧은 것부터 실행한다.
즉, 이번 예제는 preemtive한 버전, 뺏을 수 있는 버전이다.
A는 90이 남아 있는 상태에서 10초 걸리는 B, C가 들어왔으므로
주도권 뺏어서 B, C 수행한 후 A 실행함.
SJF Implementation
구현하는데 있어서 고민해야할 부분은? CPU burst가 가장 짧은 걸 고르는거였는데, 그러면 그 시간을 어떻게 알아낼 수 있을까?
CPU burst time을 알아내는게 어렵다.
→ cpu → i/o → 이런 반복이 있으므로 history를 살펴봐서 예측해서 알 수 있다.
ex) exponential averaging
지난번 예측치와 실측치를 적당히 한다.
검은색이 실제값, 파란색이 예측값.
어느정도 따라갈 수 있다.
# Response time
job이 처음 들어왔을 때부터 처음 실행될 때까지의 시간
응답시간을 줄이는것도 중요하다.
Round Robin(RR) Scheduling
time slice, 즉 shceduling quantum을 줘서 계속 빠르게 돌아가면서 실행시킴.
timer interrupt 를 줘서 예를 들어 100번 발생 됐으면 다음 프로세스에게 주는 방식
fair하지만 turnaround time에서는 성능이 좋지 않음.
### 예제
A, B, C가 동시에 도착했고 각각 5초 실행된다고 해보자.
SJF로 한다면 응답시간(처음 요청 이뤄진 시간) = 5s
RR은 time quantum을 1s라 한다면 응답시간 = 1s가 된다.
- turnaround time 입장에서는 좋지 않음.
## Time slice의 길이를 잘 정하는게 중요함.
너무 짧게 하면?
response time은 좋아지지만 문맥 교환하면서 생기는 오버헤드 비용이 늘어 성능이 떨어진다.
너무 길게 하면?
문맥 교환의 오버헤드는 줄일 수 있지만, 응답 시간이 나빠진다.
Incorporating I/O
지금까지는 cpu만 사용한다고 했지만, 이제는 I/O도 사용하는 경우를 살펴봐야함.
예시
A, B 는 50초 필요함.
A는 10초 지나고 I/O 요청하고 이 요청은 10초 걸림
B는 cpu만 수행하고 I/O 수행 안함.
A부터 실행하고 B를 실행하는 스케쥴러임.
A가 CPU를 안쓰는 시간에 B를 사용하면 CPU utilization을 극대화할 수 있음.
I/O 요청을 하게되면 프로세스 상태를 본다.
block 해둬야 다른 프로세스에게 기회가 온다.
끝나면 blocked → ready state로 다시 바꾼다.
