CPU 스케줄링(CPU Scheduling)
Summary
CPU 스케줄링에 대해 알아본다.1
CPU 스케줄링
여러 프로세스가 CPU를 교환하여 생산적으로 동작할 수 있도록 스케줄링하는 과정이다. 시스템을 효율적으로, 빠르고, 공정하게 만드는 것을 목표로 한다.
운영체제는 CPU가 일하지 않을 때마다 ready 큐에 있는 프로세스들 중 하나를 선택하여 실행해야 한다. 이 결정하는 과정(selection process)을 CPU 스케줄러가 책임진다. CPU 스케줄러는 어떤 프로세스를 CPU에 할당할지 결정한다. Dispatcher는 선택된 프로세스에 CPU 제어를 주는 모듈이다.2
CPU 스케줄러
CPU와 메모리 사이의 스케줄링을 담당하는 단기 스케줄러(short-term scheduler)이다. 메모리에 올라가 있는 ready 한 프로세스들 중 어떤 프로세스를 실행해서 CPU에 할당할지 결정한다.
Dispatcher
CPU 스케줄러가 선택한 프로세스에 CPU 제어를 주는 모듈이다. 하는 일은 다음과 같다:
- context switch
- 유저 모드로 전환
- 유저 프로그램의 알맞은 장소로 이동(jump)해서 마지막으로 떠나기 전에 있던 장소로 프로그램을 재시작한다.
디스패처는 매번 프로세스 전환(switch)이 일어날 때 사용됨으로 빨라야 한다. 한 프로세스를 멈추고 다른 프로세스를 시작하는 시간을 Dispatch Latency 라고 한다.
CPU 스케줄링 목적과 종류
CPU 스케줄링은 다음과 같은 상황에 발생할 수 있다:
- 프로세스가 running 상태에서 waiting 상태로 전환할 때
- I/O 요청, wait요청을 통해 자식 프로세스를 종료할 때
- 프로세스가 running 상태에서 ready 상태로 전환할 때
- 인터럽트가 발생할 때
- 프로세스가 waiting 상태에서 ready 상태로 전환할 때
- I/O가 끝났을 때
- 프로세스가 종료할 때(terminate)
- 부모 프로세스가 종료할 때
1과 4같은 경우는 스케줄링 옵션이 없다. ready 큐에 존재하는 새로운 프로세스가 선택돼서 실행되어야 한다. 반면에, 2와 3은 옵션이 있다.
1과 4같은 경우에 일어나는 스케줄링을 비선점(non-preemptive) 스케줄링이라고 한다. 이 외의 케이스는 선점(preemptive) 스케줄링이라고 한다.
CPU 스케줄링 알고리즘의 목적
일반시스템
- No Starvation
- 각 프로세스들이 오랜시간동안 CPU를 할당받지 못하는 상황을 피한다.
- Fairness
- 각 프로세스에 공평하게 CPU를 할당한다.
- Balance
- 시스템 모든 부분을 바쁘게 활용한다.
일괄처리(Batch) 시스템
요청시 즉각적으로 처리하는 것이 아니라, 일정기간 또는 일정량을 모았다가 한꺼번에 처리하는 방식
- Throughput
- 시간당 최대의 작업량을 낸다
- Turnaround time
- 프로세스 생성부터 소멸까지의 시간을 최소화 한다.
- CPU utilization
- CPU가 쉬는 시간이 없도록 한다.
대화형(Interactive) 시스템
온라인과 같이 일에 대한 요청에 즉각적으로 처리하여 응답 받을 수 있는 시스템
- Response time
- 요청에 대한 응답시간을 줄인다.
Time Sharing 시스템
각 프로세스에 CPU에 대한 일정시간을 할당하여 주어진 시간동안 프로그램을 수행할 수 있게하는 시스템
- Meeting deadlines
- 데이터의 손실을 피하고, 끝내야하는 시간 안에 도달한다.
- Predicatbility
- 멀티미디어 시스템에서의 품질이 저하되는 부분을 방지한다.
스케줄링 criteria
스케줄링의 효율을 분석하는 기준들이다.
- CPU Utilization(이용률, %)
- CPU가 수행되는 비율
- Throughput(처리율, jobs/sec)
- 단위시간당 처리하는 작업의 수, 처리량
- Turnaround time(반환시간)
- 프로세스의 처음 시작 시간부터 모든 작업을 끝내고 종료하는데 걸린 시간
- CPU, waiting, I/O 등 모든 시간을 포함. 반환시간은 짧을 수록 좋다.
- Waiting time(대기시간)
- CPU를 점유하기 위해서 ready queue에서 기다린 시간
- 다른 큐에서 대기한 시간은 제외한다.
- Response time(응답시간)
- 일반적으로 대화형 시스템에서 입력에 대한 반응 시간을 말한다.
비선점 스케줄링(Non-Preemptive Scheduling)
- 한 프로세스가 한 번 CPU를 점유하면, I/O(프로세스 상태가 실행에서 대기로 변경)가 발생하거나 프로세스가 종료될 때까지 다른 프로세스가 CPU를 점유하지 못한다.3
- Time-slice가 없다.4
- CPU를 사용 중인 프로세스가 자율적으로 반납한다.
- 프로세스가 자율적으로 CPU를 반납하는 시점에서 사용한다.
- 스케줄링 알고리즘
- FCFS, SJF, Priority Scheduling
선점 스케줄링(Preemptive Scheduling)
- 낮은 우선순위를 가진 프로세스보다 높은 우선순위를 가진 프로세스가 CPU를 선점한다.
- 프로세스가 CPU를 점유하고 있는 동안 I/O나 인터럽트가 발생한 것도 아니고, 작업을 끝내지도 않았는데도, 다른 프로세스가 CPU를 강제로 점유 할 수 있다. 3
- 운영체제가 알고리즘에 따라 적당한 프로세스에 CPU를 할당하고, 필요할 때 회수한다.
- I/O-bound 프로세스는 CPU-bound 프로세스보다 높은 우선순위에 있어야 한다.
- Time slice의 양은 CPU 버스트 시간(burst time, execution time)보다 조금만 더 많아야 한다.
- Time slice가 더 적을 경우, 불필요한 context switch 가 많이 일어난다.
- 반대로, time slice가 더 클 경우에는, I/O가 일어날 때에 CPU를 반납하거나, 다른 프로세스는 CPU에 굶주리는 현상이 일어날 수 있다.
-
Real time 프로세스는 다른 프로세스에 비해 매우 높은 우선순위를 갖는다.
- 스케줄링 알고리즘
- SRT, RR, Priority Scheduling
CPU 스케줄링 알고리즘
FCFS(First Come First Served)
- 먼저 CPU를 요청하는 프로세스를 먼저 처리한다.4
-
예) P1, P2, P3 순으로 프로세스가 CPU를 요청하면, P1,P2,P3 순으로 실행된다.
Process Burst Time Waiting Time Turnaround Time P1 15 0 15 P2 5 15 20 P3 3 20 23 P1
15 P2
5 P3
3 - Average waiting time: $\frac{(0 + 15 + 20)}{3} \approx 11.67$
- 만약 P3, P2, P1 순으로 요청하면, P3, P2, P1 순으로 실행된다.
P3 P2 P1
- Average waiting time: $\frac{(0 + 3 + 8)}{3} \approx 3.67$
SJF(Shortest Job First)
- 버스트 시간(burst time)이 짧은 프로세스부터 CPU를 할당한다.
- 평균 waiting time을 최소하 하기 위해 사용된다.
-
버스트 시간이 긴 프로세스는 오랜 시간 기다려야되서, No Starvation 룰을 위반한다.
Process Burst Time Waiting Time Turnaround Time P1 6 3 9 P2 3 0 3 P3 8 16 24 P4 7 9 16 P2
3 P1
6 P4
7 P3
8
SRT(Shortest Remaining Time)
- 최단 잔여시간을 우선시 한다.
- 진행 중인 프로세스가 있어도, 최단 잔여시간인 프로세스를 위해 sleep 시키고 짧은 프로세스를 먼저 할당한다.
| Process | Arrival T | Burst T | Exit T | Waiting T | Turnaround T |
|---|---|---|---|---|---|
| P1 | 0 | 8 | 17 | 9 | 17 |
| P2 | 1 | 4 | 5 | 0 | 4 |
| P3 | 2 | 9 | 26 | 15 | 24 |
| P4 | 3 | 5 | 10 | 2 | 7 |
1 P2
4 P4
5 P1
7 P3
9
- P1이 0에 도착해서 실행된다.
- t=1 에 P2가 도착하고, P2와 P1의 잔여시간을 비교한다.
- $P2_t = 4 < 7 = P1_t$ 이기 때문에 더 적은 잔여 시간을 가진 P2가 실행된다.
- P1, P3, P4 의 잔여시간을 비교한다. 각각, 7, 9, 5이기때문에 제일 적은 잔여시간을 가진 P4가 실행된다.
- P1이 P4 보다 작은 잔여시간을 가지기 때문에 (7 < 9) P1이 실행된다.
- P4가 실행된다.
RR(Round Robin)
- Time Sharing System을 위해 설계되었다.
- 모든 프로세스가 같은 우선순위를 가지며, time slice 기반으로 스케줄링한다.
- Time slice burst 가 일어나면 해당 프로세스는 스케줄링 큐의 끝으로 이동한다.
- 알고리즘의 성능은 Time slice 크기와 같아진다.
- Time slice 가 크면 FCFS와 다를게 없다.
-
Time slice 가 작다면 불필요한 context switch가 많이 일어난다.
-
Time slice = 3 ms 인 경우,
Process Burst Time Waiting Time Turnaround Time P1 13 10 23 P2 3 3 6 P3 7 12 19 P1
3 P2
3 P3
3 P1
3 P3
3 P1
3 P3
1 P1
3 P1
1
Priority Scheduling(우선 순위 스케줄링)
- 우선 순위가 높은 프로세스에 CPU를 우선 할당한다.
- 우선 순위는 시간 제한, 메모리 요구량, 프로세스의 중요성, 자원사용 비용 등에 따라 달라진다.
- 우선 순위가 같을 경우, FCFS와 같다.
- 선점, 비선점 둘다 사용한다.
- 선점형 방식
- 더 높은 우선순위의 프로세스가 도착하면 실행중인 프로세스를 멈추고 CPU 를 선점한다.
- 비선점 방식
- 더 높은 우선순위의 프로세스가 도착하면 Ready Queue 의 Head 에 넣는다
Leave a comment