학습 목표
- CPU and I/O Bursts in Program Execution
- CPU-burst Time의 분포,
- CPU Scheduler & Dispatcher,
- Scheduling Algorithms, Scheduling Criteria,
- FCFS(First- Come First-Served),
- SJF(Shortest-Job-First),
- Example of Non-Preemptive SJF,
- Example of Preemptive SJF,
- 다음 CPU Burst Time의 예측,
- Exponential Averaging,
- Priority Scheduling,
- Round Robin(RR),
- Example: RR with Time Quantum = 20,
CPU and I/O Bursts in Program Execution
-
컴퓨터 프로그램이 실행될 때는 이런 단계를 거친다.
1) cpu에서 instruction이 실행되는 단계 = cpu burst
2) 오래 걸리는 i/o 작업을 하는 단계
=> 번갈아가면서 실행 -
프로그램 종류마다 다르긴 하다 .
1) i/o가 빈번히 끼어들지 않는 프로그램에서는 cpu burst가 길게 나타난다.
2) 사람과 interaction이 빈번한 프로그램에서는 i/o burst가 길게 나타난다.
CPU-burst Time의 분포
-
i/o bound job : i/o 작업이 빈번해서 cpu burst가 짧게 나타나는 것
-
cpu bound job : cpu burst가 길게 나타나는 것.
=> 프로그램마다 cpu를 사용하는 시간이 다르다
=> cpu 스케줄링이 필요하다. -
cpu 스케줄링의 2가지 이슈
1) cpu burst에 들어온 프로그램 여러개가 있는데, 누구한테 당장 cpu를 줄 것인가?
2) 일을 다할 때까지 cpu를 주냐, 아니면 중간에 뺏어서 다른 프로세스한테 cpu를 줄 것인가?
=> cpu를 조금만 쓰면 되는 i/o bound job과 cpu를 길게 써야 하는 cpu bound job에게 cpu 스케줄링을 적절하게 해야한다. (공평성, 효율성)
CPU Scheduler & Dispatcher,
- 비선점형 nonpreemptive(강제로 빼앗지 않음)
- 선점형 preemptive(강제로 빼앗음)
Scheduling Algorithms, Scheduling Criteria,
-
시스템 입장에서 : cpu 이용률, 처리량
-
program 입장에서 : turnaround time, waiting time, response time
-
turnaround time: cpu burst를 시작해서 끝날 때까지의 총 시간 (cpu 기다린 시간 + cpu 쓴 시간 총합)
기준x: 프로세스가 시작돼서 프로세스가 종료 될 때까지의 시간이 아님
기준o: 이 프로세스가 cpu를 쓰러 들어와서 cpu를 하고, i/o를 하러 나갈 때까지 걸린 총시간을 의미한다. -
waiting time: cpu를 얻기위해 ready queue에서 기다린 순수한 시간 (선점형에서는 cpu를 쓰고, 반납하고, 쓰고, 반납하고를 여러번 한다. 그러니 여러번 기다리는 모든 시간을 waiting time)
-
response time: 최초의 cpu를 얻기까지의 기다린 시간
01. FCFS(First- Come First-Served)
- 먼저 온 순서대로 처리
- 두가지 스케줄링 분류에서 비선점형
- 간트 차트: x축은 시간축, cpu에 의해 스케줄링된 프로세스를 시간 순서대로 보여주고 있는 것.
- 좋은 스케줄링 방식은 아님 (간발의 차로 정말 많은 시간을 기다릴수도 있기 때문)
- 앞 프로세스가 cpu를 몇 초 쓰냐에 따라서 전체 기다리는 평균 시간이 크게 달라진다.
- Convoy effect: 짧은 프로세스가 긴 프로세스 뒤에서 기다리는 현상 (안좋음)
02.SJF(Shortest-Job-First)
cpu burst가 제일 짧은 프로그램한테 cpu를 주는 스케줄링
Example of Non-Preemptive SJF,
Example of Preemptive SJF,
- Starvation 문제(기아문제): long process는 영원히 cpu를 못잡을 수 있음.
다음 CPU Burst Time의 예측
- SJF의 문제점: CPU 사용시간을 미리 알 수 없음.
프로그램이란게 실행되다보면 input을 받아서 처리하기도 하고, if문을 만족하느냐 안하느냐에 따라서 branch가 일어난다.
=> 실제상황에서 SJF를 사용할 수 없음. - 하지만 CPU 사용시간을 추정할 수 있긴함. (과거 CPU 사용 흔적)
- exponential averaging : cpu burst time 추정하는 방법
Exponential Averaging
- exponential averaging : cpu burst time 추정하는 방법
01.티 : 실제 cpu 사용시간 (1부터 n까지의 실제 cpu 시간 주어짐)
02.타우 : cpu 사용 예측 시간 (n+1부터의 cpu 시간을 예측해야함)
03.a(알파)는 상수는 0과 1사이의 값이다.
04.예측하는 식: n+1 cpu 사용 예측 시간 = n번째 실제 cpu 사용 시간 + n번째 예측했던 cpu 사용시간을 일정비율 (1-a)을 곱한다.
04.Priority Scheduling
우선순위가 제일 높은 process한테 cpu를 주겠다.
- preemptive : 더 높은 우선순위 프로세스 오면 지금 프로세스한테서 cpu 빼앗는다.
- nonpreemptive : 더 높은 우선순위 프로세스 와도 지금 프로세스한테서 cpu 못 뺏는다.
- 가장 작은 정수가 높은 우선순위를 가짐.
- starvation을 해결하기 위한 방법으로 Aging 방법이 있음.
05.Round Robin(RR)
- 현대적인 컴퓨터 시스템에서 사용하는 cpu 스케줄링은 Round Robin에 기반함.
ex) 프로세스에 할당 시간을 세팅해서 cpu를 주고, 시간이 끝나면 timer interrupt가 걸려서 cpu를 빼앗기는 preemptive(선전형) 스케줄링 - 응답시간이 빨라지는 장점 : cpu를 최초로 얻기까지의 시간이 빨라. cpu를 줬다 뺏었다 줬다 뺏었다 하기 때문이다. 누가 cpu를 오래쓸지 모르는 상황에서 굳이 예측할 필요 없이, cpu를 짧게 쓰는 process가 빨리 쓰고 나갈 수 있게 해준다.
- n 길이의 quque에 각 프로세스마다 q라는 시간을 할당할 때, 각 프로세스는 적어도 (n-1)*q 시간안에서 cpu를 가질 수 있다. n에서 1을 빼는 이유는 자기 자신을 제외한 것임.
- cpu를 짧게 쓰는 process는 cpu를 길게 쓰는 process보다 대기시간이 짧다. 즉, 기다리는 시간이 본인이 cpu를 사용하려고 하는 시간과 비례하다. 왜냐하면, 길수록 cpu를 쓰려고 더 자주 기다려야 한다. round robin은 일정 시간 지나면 반납하게 만드니까 !
- 적당한 규모의 time Quantum을 주는 것이 바람직하다. q가 너무 길면 FCFS와 같은 기능을 하게 되고, q가 너무 짧으면 Round Robin의 이상과는 부합하지만 context switch가 빈번하게 일어나고 오버헤드가 발생하게 된다.
Example: RR with Time Quantum = 20
- turnaround time이나 waiting time은 길어질 수 있지만 최초로 cpu를 얻는데 걸리는 시간인 response time은 더 짧다.
- Round Robin : cpu 사용시간이 짧은 process랑 cpu 사용시간이 긴 process가 얼마나 cpu를 사용할지 모르는 상황에서 마구잡이로 섞여있을 때 쓰기에 좋은 스케쥴링이다. 반대로, cpu 사용시간이 모두 동일한 프로그램들이 있을 경우엔 거의 모든 프로세스들이 마지막까지 cpu를 조금씩 받으면서 wating time이 굉장히 길어진다. 이런 측면에선 Round Robin이 안좋음. 하지만 일반적으로 process의 cpu 시간들이 각기 다름. 따라서 일반적으로 Round Robin 스케줄링을 잘 활용함.
