1. FCFS (First-Come First-Served)
특징
- 먼저 큐에 온 순서대로 프로세스 처리
- 비선점형(Non-preemptive) 스케줄링
- 각각의 프로세스들이 언제 실행될 수 있을지 예측 가능
- 프로세스의 순서에 따라 평균 응답시간이 달라진다.
문제점
- Convoy effect (호위병 효과) : 앞에 무겁고 큰 프로세스가 있으면 뒤에 가벼운 프로세스가 있어도 빠르게 갈 수 없다.
| Process | Burst Time |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
1) P1 -> P2 -> P3
- waiting time : P1(0), P2(24), P3(27)
- Average waiting time : (0 + 24 + 27) / 3 = 17
2) P2 -> P3 -> P1
- waiting time : P1(6), P2(0), P3(3)
- Average waiting time : (6 + 0 + 3) / 3 = 3
2. SJF (Shortest-Job-First)
특징
- CPU burst time이 짧은 프로세스에게 먼저 할당
- 비선점형(Non-preemptive) 스케줄링
문제점
- starvation : CPU 사용이 짧은 프로세스를 선호하므로 사용 시간이 긴 프로세스는 계속 CPU를 할당 받을 수 없다.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0.0 | 7 |
| P2 | 2.0 | 4 |
| P3 | 4.0 | 1 |
| P4 | 5.0 | 4 |
3. SRT (Shortest-Remaining-Time-First)
특징
- 새로운 프로세스가 도착할 때마다 새로운 스케줄링이 이루어진다.
- SJF + preemptive 라고 생각하면 나중에 떠올리기 쉽다.
- 선점형(preemptive) 스케줄링
현재 수행중인 프로세스의 남은 burst time보다 더 짧은 CPU burst time을 가지는 프로세스가 도착하면 기본 프로세스의 CPU를 빼앗는다.
문제점
- starvation
- 새로운 프로세스가 도착할 때마다 스케줄링을 다시 하기 때문에 CPU burst time(CPU 사용시간)을 측정할 수 없다.
| Process | Arrival Time | Burst Time |
|---|---|---|
| P1 | 0.0 | 7 |
| P2 | 2.0 | 4 |
| P3 | 4.0 | 1 |
| P4 | 5.0 | 4 |
4. Priority Sheduling
특징
- 각 프로세스 마다 우선순위를 나타내는 순서를 주고, 순위가 높은 순서대로 CPU를 할당하겠다.
(일반적으로 정수이며, 숫자가 작을수록 우선순위가 높다.) - 선점형(preemptive) 방식
-> 더 높은 우선순위의 프로세스가 들어오면 실행 중인 프로세스를 멈추고 CPU를 선점한다. - 비선점형(non-preemptive) 방식
-> 더 높은 우선순위의 프로세스가 들어오면 Ready queue의 head에 넣는다.
문제점
- Starvation : 우선 순위가 낮은 프로세스가 있는데 우선 순위가 높은 프로세스가 자꾸 ready queue안에 들어온다.
해결책
- Aging : queue에서 기다리는 시간에 비례해서 순위를 높여준다.
5. RR (Round Robin)
특징
- 각각의 프로세스는 한번 CPU를 잡을 때 동일하게 사용할 수 있는 시간(time quantum)을 가지게 된다.
- 할당 시간이 지나면 프로세스는 선점당하고 ready queue의 제일 뒤에 가서 다시 줄을 선다.
RR이 가능한 이유는 프로세스의 context를 save할 수 있기 때문이다.
장점
- FCFS의 장점인 공정성을 그대로 사용하면서 시간 한도를 준다.
-> convoy 효과가 일어나지 않는다.
-> 무조건 내 차례가 온다는 게 보장
-> 그것을 이용해서 다른 곳에서 다른 일을 할 수 있다. - Response time이 빨라진다.
-> n개의 프로세스, 할당시간이 q(time quantum)인 경우, 어떤 프로세스도 (n-1)q 이상 기다리지 않는다.
주의할 점
- q(time quantum)의 길이에 따라
- q large
-> FCFS와 같아진다. - q small
-> 내 차례가 빨리온다 -> 진도가 나가는 모습을 사용자에게 보여줄 수 있다. -> 응답성이 좋아진다.
하지만 많은 context switch로 overhead가 증가한다.
- q large
| Process | Burst Time |
|---|---|
| P1 | 53 |
| P2 | 17 |
| P3 | 68 |
| P4 | 24 |
time quantum : 20
6. Multilevel Queue
특징
- Ready queue가 분리된 여러개의 큐들로 이루어져 있다.
- foreground : 사용자와 상호작용하는 앞단의 프로세스들
- background : 일괄처리형 batch 프로세스들
- 각각의 큐들은 서로 각자만의 스케줄링 알고리즘을 사용한다.
- foreground : RR
- background : FCFS
- 해당 큐에 들어간 프로세스는 다른 큐로 이동되거나 변경하는 것이 불가능하다.
7. Multilevel Feedback Queue
특징
- Ready queue가 분리된 여러개의 큐들로 이루어져 있다.
- 각각의 큐들은 서로 각자만의 스케줄링 알고리즘을 사용한다.
- 프로세스가 큐들 사이에서 이동이 가능하다.
Three queues
- Q0 : time quantum 8ms
- Q1 : time quantum 16ms
- Q2 : FCFS
참고자료
옹골찬 개발자가 되기 위한 험난한 일대기