본 자료는 인하대학교 정진만 교수님의 Operating System 강의 자료를 참고하여 제작되었습니다.
주요 용어
| 용어 | 의미 |
|---|---|
| CPU Burst | CPU 실행 시간이다. |
| I/O Burst | I/O 실행 시간이다. |
| CPU-I/O burst cycle | CPU 실행과 I/O wait이 반복되는 cycle이다. |
| Processor(CPU) bound | CPU를 자주 사용하는 process 특성이다. |
| I/O bound | I/O를 자주 사용하는 process 특성이다. |
Processor Scheduling 종류
| 종류 | 역할 |
|---|---|
| Long-term scheduling | 처음 초기화할 때 어떤 process를 시스템에 받아들일지 결정한다. |
| Medium-term scheduling | multi-programming 정도를 조절하고 load balancing을 수행한다. |
| Short-term scheduling | 다음에 CPU를 사용할 process를 선택한다. |
Scheduling Criteria
| 관점 | 기준 | 의미 |
|---|---|---|
| System Oriented | Throughput | 단위 시간당 수행한 일의 양이다. |
| System Oriented | Processor Utilization | CPU를 얼마나 효율적으로 사용하는지 나타낸다. |
| System Oriented | Fairness | process들이 공정하게 CPU를 받는지 나타낸다. |
| User Oriented | Turnaround time | 작업이 끝날 때까지 걸린 전체 시간이다. |
| User Oriented | Response time | 요청 후 첫 응답까지 걸리는 시간이다. |
| User Oriented | Deadlines | 정해진 시간 안에 작업을 끝내는지 나타낸다. |
Selection Function
다음에 수행할 프로세스를 선택하는 함수
| 기호 | 의미 |
|---|---|
w | waiting time |
e | execution time |
s | total service time |
TAT | Turn-around time, w + s |
Decision Mode
| 방식 | 의미 |
|---|---|
| Non-preemptive | 프로세스가 종료되거나 스스로 대기 상태가 될 때까지 CPU를 빼앗지 않는다. |
| Preemptive | time slice, 우선순위, scheduler 판단에 따라 실행 중인 프로세스를 선점할 수 있다. |
FIFO(First In, First Out)
Ready queue에서 기다린 시간이 가장 긴 프로세스를 선택한다.
- Selection Function:
max[w] - Decision Mode: Non-preemptive
- 단순하다.
- Long process와 processor-bound process에 유리하다.
Convoy effect가 발생할 수 있다. 하나의 느린 프로세스 때문에 뒤의 프로세스들이 기다린다.
Shortest Process Next(SPN)
짧은 프로세스 먼저 수행한다.
- Selection Function:
min[s] - Decision Mode: Non-preemptive
- 평균 TAT가 개선된다.
- Long process에서 starvation이 발생할 수 있다.
- Service time을 미리 알기 어렵다.
Shortest Remaining Time(SRT)
Remaining time으로 선택을 한다.
- Selection Function:
min[s-e] - Decision Mode: Preemptive
- 평균 turnaround time과 response time이 좋다.
- starvation이 발생할 수 있다.
- preemption 오버헤드가 크다.
- 긴 작업에 불리하고 남은 실행 시간 예측이 어렵다.
Highest Response Ratio Next(HRRN)
오래 기다린 프로세스일수록 우선순위를 점점 높여주자.
- Response Ratio:
R = (w + s) / s - Selection Function:
max[(w+s)/s] - Decision Mode: Non-preemptive
- 오래 기다린 process의 우선순위가 점점 높아진다.
- service time을 예측하기 어렵다.
Round-Robin
일정 시간마다 돌아가면서 일을 하게 한다.
- Selection Function:
constant - Decision Mode: Preemptive
- 공정하다.
- starvation이 없다.
- response time이 좋다.
Time slice 기준
| Time slice | 효과 | 가까워지는 방식 |
|---|---|---|
| 짧은 time slice | response time이 좋아지지만 scheduling overhead가 증가한다. | SPN에 가까워진다. |
| 긴 time slice | response time이 나빠지지만 scheduling overhead가 감소한다. | FIFO에 가까워진다. |
Virtual Round Robin(VRR)
기존 round-robin은 long process에 조금 더 유리했다.
왜냐? 항상 time-slice를 소진하기 때문이다.
기존에 I/O가 끝난 프로세스도 ready queue 맨 뒤로 보내졌는데,
이를 보조 큐(auxiliary queue)에 넣고 먼저 처리시킨다.
그러면 스케줄러는 먼저 auxiliary queue를 먼저 본다.
Multi-Level Feedback Queue
이것도 RR를 개선하기 위해 나왔다.
Dynamic scheduler라고 한다.
Time-slice를 다 안쓰면? short process
Time-slice를 다 쓰면 demotion 한다.
Short process를 우대한다.
시간에 따라 큐를 나눈다.
시간에 따라 promotion할 수도 있다.
Scheduling Algorithm 정리
| 알고리즘 | Selection Function | Decision Mode | 장점 | 단점 |
|---|---|---|---|---|
| FIFO | max[w] | Non-preemptive | 단순하다. | Convoy effect가 발생할 수 있다. |
| SPN | min[s] | Non-preemptive | 평균 TAT가 좋다. | long process starvation 가능성이 있다. |
| SRT | min[s-e] | Preemptive | 평균 turnaround time과 response time이 좋다. | overhead가 크고 예측이 어렵다. |
| HRRN | max[(w+s)/s] | Non-preemptive | starvation을 완화한다. | service time 예측이 필요하다. |
| Round-Robin | constant | Preemptive | 공정하고 response time이 좋다. | time slice 설정에 민감하다. |
| VRR | auxiliary queue 우선 | Preemptive | I/O-bound process를 보완한다. | queue 관리가 추가된다. |
| MLFQ | queue priority | Preemptive | short process를 우대하고 동적으로 조절한다. | 구현과 튜닝이 복잡하다. |