[OS] Process / Thread Scheduling
현대 computer system은 multi processing 및 multi-threaded processes 들로 구성되기 때문에, 각각을 scheduling하는 방식에 따라 성능이 달라진다. 현재 ready-to-run process들은 Ready Queue에 담겨져 CPU로부터 수행되기를 기다린다. Scheduling algorithm은 많지만 대표적으로 5가지만 소개한다.
- FCFS (First Come First Served Scheduling) – Non-Preemptive
- SJF (Shortest Job First Scheduling) – Non-Preemptive
- SRTF (Shortest Remaining Time First) – Preemptive
- RR (Round Robin Scheduling) – Preemptive
- Priority Scheduling – Preemptive, Non-Preemptive
그리고 각 scheduling algorithm을 설명하기 위해 몇몇 용어들을 사전에 서술해보면 다음과 같다.
| Terminologies | Definition |
|---|---|
| Arrive time | Process가 수행되는 시간 |
| Burst time | Process가 수행해야 될 시간 |
| Completion time | Process가 종료되는 시간 |
| Turn-Around Time (TAT) | Process가 initiation되고 난 뒤 종료되는데 까지 걸리는 시간을 말한다. (Completion time - arrive time) |
| Waiting time | Process가 run time을 제외한 나머지 시간을 말한다. 이 시간이 크면 idle time이 많았다는 의미다. (TAT - burst time) |
| Response time | Process가 initiation 되고 최초로 CPU를 점유하는데 걸리는 시간을 나타낸다. |
1. First Come First Served (FCFS)
First Come First Served의 약자로, greedy하게 사용 요청이 오는 순서대로 처리하는 방식이다. FCFS는 non-preemptive 방식으로 중간에 scheduling에 의해 CPU로부터 yield되지 않는다. 아래는 FCFS를 사용했을 때 process scheduling의 예시다.
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 4 | 4 | 4 | 0 | 0 |
| P2 | 1 | 3 | 7 | 6 | 3 | 3 |
| P3 | 2 | 1 | 8 | 6 | 5 | 5 |
| P4 | 3 | 2 | 10 | 7 | 5 | 5 |
위 결과를 토대로 throughput을 구해보면 4/10이 된다.
2. Shortest Job First Scheduling (SJF)
Shortest Job First Scheduling는 평균 대기 시간을 최소화 하기 위해 CPU 점유 시간이 (burst time) 가장 짧은 process에 CPU를 먼저 할당하는 방식 평균 대기시간을 최소로 만드는 것을 최적으로 두고 있는 알고리즘이다. 요구 시간이 짧은 프로세스가 긴 process에게 항상 양보되어 기아 상태가 발생할 수 있으며, 대기 상태에 있는 process의 요구 시간에 대한 정확한 자료를 얻기 어렵다는 문제점이 있다. 단기 scheduling 보다 장기 scheduling에 유리하다. Non-preemptive 방식이다.
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 | 0 |
| P2 | 1 | 5 | 16 | 15 | 10 | 10 |
| P3 | 2 | 3 | 11 | 9 | 6 | 6 |
| P4 | 3 | 1 | 8 | 5 | 4 | 4 |
3. Shortest Remaining Time First (SRTF)
SJF와 비슷한데 SJF에서 preemptive 방식으로 된 것이다. 실시간으로 모든 process의 burst time을 확인 후에 가장 남은 시간이 작은 process를 우선으로 수행시키는 방식이다.
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 | 0 |
| P2 | 1 | 5 | 10 | 9 | 4 | 0 |
| P3 | 2 | 3 | 6 | 4 | 1 | 0 |
| P4 | 3 | 1 | 4 | 1 | 0 | 0 |
4. Round Robin Scheduling (RR)
시분할 시스템을 위해 설계된 preemptive scheduling의 하나로서, process들 사이에 priority를 두지 않고, 순서대로 시간 단위(Time quantum)로 CPU를 할당하는 방식의 CPU scheduling링 알고리즘이다. 보통 시간 단위는 10ms ~ 100ms 정도이다. 시간 단위동안 수행한 프로세스는 ready queue의 끝으로 밀려나게 된다. Context switching의 overhead가 큰 반면, response time이 짧아지는 장점이 있어서 real-time system에 유리하다.
아래 예시는 time quantum = 2인 경우다.
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 | 0 |
| P2 | 1 | 5 | 15 | 14 | 9 | 1 |
| P3 | 2 | 3 | 12 | 10 | 7 | 2 |
| P4 | 3 | 1 | 9 | 6 | 5 | 5 |
5. Priority Scheduling
Priority scheduling은 non-preemptive와 preemptive 방식 두 가지로 나뉜다. 각 process에 priority가 주어져서 그 priority에 따라서 실행 우선순위가 정해진다. 아래 예시에선 process number가 크면 클 수록 higher priority를 기준으로 설명한다.
5.1 Preemptive
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 16 | 16 | 9 | 0 |
| P2 | 1 | 5 | 10 | 9 | 4 | 0 |
| P3 | 2 | 3 | 6 | 4 | 1 | 0 |
| P4 | 3 | 1 | 4 | 1 | 0 | 0 |
5.2 Non-preemptive
| Process | Arrive Time | Burst Time | Completion Time | Turn-Around Time | Waiting Time | Response Time |
|---|---|---|---|---|---|---|
| P1 | 0 | 7 | 7 | 7 | 0 | 0 |
| P2 | 1 | 5 | 16 | 15 | 10 | 10 |
| P3 | 2 | 3 | 11 | 9 | 6 | 6 |
| P4 | 3 | 1 | 8 | 5 | 4 | 4 |
