👍Scheduling
📢 MultiProgramming이란?
- 하나 또는 여러개의 프로세서에서 여러개의 프로세스를 실행하는 것을 말함.
- 예를 들어, Process A의 I/O Request를 하염없이 기다리는 대신 context switch를 통해 대기 시간 동안 Process B를 실행한다.
- 이를 위해서는 Processor 와 Memory 자원 관리가 필수적이다.
📢 Scheduling 성능 측정 요소
1. Turnaround time : 프로세스 A가 스케쥴링된 순간부터(T(arrival)) 프로세스 A가 실행종료되는 순간(T(completion)) 까지 걸리는 시간
2. Response time : 프로세스 A가 실행되는 순간부터(T(firstrun)) 프로세스 A가 실행종료되는 순간(T(completion)) 까지 걸리는 시간
3. Throughput: 특정 시간동안 실행완료 되는 프로세스의 수
4. Utilization: 특정 시간동안 자원이 얼마나 효율적으로 사용되고 있는가?
5. Fairness: 각각의 프로세스들이 스케쥴링되어 실행되는 빈도가 균일한가?
6. Predictability: response time과 turnaround time이 비교적 균일한가?
📢 Preemptive/Non-preemptive Scheduling(선점형/비선점형 스케쥴링)
1. Preemptive Scheduling(선점형 스케쥴링) - 대부분의 OS가 채택하는 방식
- 어떤 프로세스가 time-slice를 소모해 time-out되거나, I/O Request가 발생하는 등의 상황이 발생했을 때 다른 프로세스에게 CPU를 양보한다.
- 특정 상황이 발생했을 때 기존 프로세스를 쫓아내고 CPU를 선점할 수 있으므로 선점형 스케쥴링이라고 한다.
- Context-Switch가 발생할 때 커널 데이터도 그에 맞춰 바뀌어야 하므로, Kernel또한 preemptive해야 한다.
- Context-Switch overhead가 비교적 높다.
- Process synchronization?? - 나중에 다시 보기....
2. Non-preemptive Scheduling(비선점형 스케쥴링)
- 어떤 프로세스가 CPU를 자발적으로 양보하거나(yield) 종료하지 않는 이상 CPU를 계속 사용
- Context-switch overhead는 비교적 낮으나, response time이 비교적 길고, priority inversion이 많이 발생한다. - Priority Inversion 나중에 다시 보기
📜 참고
CPU burst: CPU 실행이 발생되는 사이클
I/O burst: I/O wait이 발생되는 사이클
👍Scheduling Schemes
📢 FCFS(First come, First served) Scheduling
-
먼저 Ready Queue에 도착한 프로세스가 먼저 실행된다!
-
Non-preemptive Scheduling(비선점형 스케쥴링)에 해당한다.
-
자원 효율성이 높고, interactive한 시스템보단 batch 시스템(먼저 받은 작업부터 처리하는 시스템)에 유리하다.
-
단점: Convoy Effect(실행시간이 긴 작업이 먼저 도착했을 경우 실행시간이 짧은 작업의 대기시간이 지나치게 늘어나는 현상) => 평균 Response time의 증가
📢 FCFS Scheduling의 예시
P1, P2, P3 순으로 Ready queue에 도착했을 때,
각 프로세스의 Turnaround time은
P1 = 24, P2 = 24+3 = 27, P3 = 24 + 3 + 3 = 30이며,
평균 Turnaround time은 (24+27+30)/3 = 27이 되게 된다.
P2, P3, P1 순으로 Ready queue에 도착했을 때,
각 프로세스의 Turnaround time은
P1 = 3+3+24 = 30, P2 = 3, P3 = 3 + 3 = 6이며,
평균 Turnaround time은 (30+3+6)/3 = 13이 되게 된다.
FCFS Scheduling은 작업시간이 긴 프로세스가 맨 처음 도착했을 때, 평균 turnaround time이 매우 높은 걸 보일 때 최악의 효율성을 보임을 알 수 있다.
📢 SJF(Shortest Job First) Scheduling
-
가장 실행시간이 짧은 (CPU burst 시간이 가장 짧은) 작업이 우선적으로 실행된다.
-
마찬가지로 Non-preemptive Scheduling(비선점형 스케쥴링)에 해당한다.
-
평균적인 Response time이 짧기 때문에 Ready queue에 저장해야 하는 프로세스의 개수도 비교적 작아 메모리 사용이 작다.
-
Starvation 현상 (비교적 실행시간이 긴 프로세스들은 실행시간이 짧은(우선순위가 높은) 프로세스에 밀려 하염없이 대기해야 하는 현상) -> aging (오래 기다린 프로세스들을 먼저 실행)을 통해 해결 가능
-
정확한 실행시간을 알 수 없기 때문에 기존의 실행시간 데이터 정보를 바탕으로 추측해야함.
기존에 실행됐던 실행정보를 바탕으로 실행시간을 estimate하며, 이 식에서 보면 가장 최근에 실행됐던 실행정보에 높은 가중치를 두는 것을 알 수 있다.
📢 STCF(Shortest Time-to-Completion) Scheduling
-
SJF의 변형이며, Preemptive Scheduling에 속한다. (남은 CPU burst 시간이 짧은 프로세스가 Ready queue에 도착하면 그 프로세스가 CPU를 선점)
-
높은 Context Switch overhead, Remaining time tracing overhead, Burst time estimation overhead 발생
📢 STCF Scheduling의 예시
T=1일때
- P1: 남은 CPU Burst Time: 7
- P2: Ready queue에 도착, CPU Burst Time: 4
=> P2가 Remaining CPU Burst time이 가장 작으므로, P2가 CPU를 선점
T=2일때
- P1: 남은 CPU Burst Time: 7
- P2: 남은 CPU Burst Time: 3
- P3: Ready queue에 도착, CPU Burst Time: 9
=> 여전히 P2가 Remaining CPU Burst time이 가장 작으므로, P2가 CPU를 유지함.
FCFS, SJF, STCF Scheduling은 공통적으로 Turnaround time (Ready queue에 들어왔을 때부터 execution completion까지 걸리는 시간)을 고려한다.
📢 RR(Round-Robin) Scheduling
- Preemptive Scheduling에 속한다. (특정 프로세스가 부여받은 time slice를 전부 소진하면 다른 프로세스가 CPU를 선점)
- 프로세스는 자신이 부여받은 time slice를 모두 소진하면 CPU를 release하고 ready 상태에 들어간다.
- context switch overhead가 높으며, interactive한 시스템에 어울린다.
📜 RR Scheduling은 Time slice가 매우 길면 FCFS(First Come, First Served) Scheduling과 유사하며, Time slice가 짧으면 CPU Sharing과 동일해진다.
📢 RR Scheduling의 예시 (Time Quantum = 4)
- P1 CPU burst = 24, P2 CPU burst = 3, P3 CPU burst 3이라고 가정할 때,
- CPU Burst time이 끝났거나, Time Slice를 전부 소모했을 때 프로세스는 CPU를 release한다.
- T= 14를 예로 들면, Time Slice를 소진하여 Timer interrupt가 발생하나, context switch overhead는 발생하지 않고 커널의 OS만 동작한 후 다시 P1을 실행한다.
- RR Scheduling은 Response time의 측면에서는 매우 효율적인 스케쥴링이나, Turnaround time (arrival-completion)의 측면에서는 매우 비효율적이다.
📢 Priority Scheduling
- 각 프로세스의 우선순위에 따라 우선순위가 높은 프로세스부터 먼저 CPU를 사용하는 스케쥴링 기법
- 우선순위가 같다면 FCFS(First come, First served)의 규칙을 따를 수 있다.
- Starvation 현상(우선순위가 낮은 프로세스는 CPU 자원을 계속 할당받지 못하는 문제) => Aging(Ready queue에 오랫동안 있는 프로세스에 CPU를 우선 할당)으로 해결
