1. CPU Scheduling
2개 이상의 프로세스가 메모리에 적재되어 작업을 기다릴 때 CPU가 어떤 작업을 진행할지 순서를 결정하는 것을 CPU Scheduling이라 한다.
(메모리에 적재된 프로세스를 순차적으로 작업하는 방법이 가장 이상적이고 간단하지만, 작업 간의 효율적인 자원 할당 및 공유를 위해서는 적절한 순서를 정해주는 알고리즘이 필요하다.)
2. 선점형(Preemptive)/비선점형(Non-preemptive) 스케쥴링
선점형 스케쥴링(Preemptive Scheduling): 운영체제가 필요하다고 판단하면 강제로 실행 상태에 있는 프로세스의 작업을 중단하고 다른 프로세스의 작업을 진행하는 방식이다.
비선점형 스케쥴링(Non-preemptive Scheduling): 한 프로세스가 CPU를 할당받아 사용하면 프로세스의 대기 또는 종료될 때까지 다른 프로세스가 CPU를 할당받지 못하는 방식이다.
3. 스케쥴링 평가 기준(Scheduling criteria)
1. CPU 사용률(%)(CPU Utilization)
- 전체 시스템의 동작 시간 중 프로세스들이 CPU를 사용한 비율
- 높을수록 운영체제 성능이 좋음
2. 처리량(Throughput)
- 단위 시간당 작업을 마친 프로세스의 수
- 수치가 클수록 좋은 알고리즘
3. 반환시간(Turnaround time)
- 대기 시간을 포함하여 실행이 종료될 때까지의 시간
4. 대기시간(Waiting time)
- 프로세스가 생성된 후 실행되기 전까지 대기하는 시간
5. 응답시간(Response time)
- 첫 작업을 시작한 후 첫 번째 출력(응답)이 나오기까지의 시간
4. CPU Scheduling Algorithms
4-1. First-Come, First-Served(FCFS)
먼저 온 것을 먼저 서비스(선입선출 방식)하는 방법으로 큐에 도착한 순서대로 CPU를 할당 받는 알고리즘이다.
| 도착 순서 | 도착 시간 | 작업 시간 |
|---|---|---|
| P1 | 0 | 30 |
| P2 | 3 | 18 |
| P3 | 6 | 9 |
P1의 대기 시간 = 0
P2의 대기 시간 = 30 - 3 => 27
P3의 대기 시간 = 48 - 6 => 42
FCFS의 평균 대기시간 (대기시간 총합 / 프로세스의 수)
AVR = (0 + 27 + 42)/3 = 23
FCFS 단점
1. 작업 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 가만히 기다려야 한다.
2. 작업 중인 프로세스가 I/O 장치의 작업을 요청할 경우 I/O 작업이 종료될 때까지 프로세스는 대기 상태로 변하게 되면서 CPU를 사용하지 않게 되어 작업의 효율성이 떨어진다.
4-2. Shortest-Job-First(SJF)
작업 시간이 짧은 프로세스부터 우선적으로 CPU를 할당 받게 하는 알고리즘이다.
| 도착 순서 | 도착 시간 | 작업 시간 |
|---|---|---|
| P1 | 0 | 30 |
| P2 | 3 | 18 |
| P3 | 6 | 9 |
P1의 대기 시간 = 0
P2의 대기 시간 = 39 - 3 => 36
P3의 대기 시간 = 30 - 6 => 24
SJF의 평균 대기시간 (대기시간 총합 / 프로세스의 수)
AVR = (0 + 36 + 24)/3 = 20
SJF 단점
1. 운영체제가 프로세스의 종료 시간을 정확하게 예측하는 것이 사실상 불가능하다.
2. 작업 시간이 길다는 이유만으로 계속해서 순위가 뒤로 밀려나게 되면 아사(starvation) 현상이 발생할 수 있다.
4-3. Priority
- 우선순위가 높은 프로세스가 먼저 CPU를 할당 받는 방식의 알고리즘이다.
- Priority 방식 또한 아사(starvation)의 문제점이 존재한다.
4-4. Highest Response Ratio Next(HRN)
최고 응답률을 우선시하는 방법으로 아사 현상을 해결하기 위해 만들어진 비선형 알고리즘이다.
(대기 시간과 작업 시간을 고려하여 우선순위를 결정)
프로세스의 우선순위를 결정하여 CPU할당 순서를 결정한다.
우선순위 = (대기 시간 + CPU 사용 시간) / CPU 사용 시간
| 도착 순서 | 도착 시간 | 작업 시간 |
|---|---|---|
| P1 | 0 | 30 |
| P2 | 3 | 18 |
| P3 | 6 | 9 |
P2 우선순위 = (27 + 18) / 18 => 2.5
P3 우선순위 = (24 + 9) / 9 => 3.67
P1의 대기 시간 = 0
P2의 대기 시간 = 39 - 3 => 36
P3의 대기 시간 = 30 - 6 => 24
HRN의 평균 대기시간 (대기시간 총합 / 프로세스의 수)
AVR = (0 + 36 + 24)/3 = 20
HRN 단점
공평성이 위배되어 많이 사용하지 않는 알고리즘이다.
4-5. Round-Robin(RR)
한 프로세스가 일정 시간(Time Quantum) 동안 작업을 끝내지 못하면 큐의 맨 뒤로 이동하여 다시 자기 차례를 기다리는 방식의 알고리즘이다.
(선점형 알고리즘 중 가장 단순하고 대표적인 방식)
| 프로세스 | 작업시간 |
|---|---|
| P1 | 24 |
| P2 | 3 |
| P3 | 3 |
RR의 평균 대기시간 (대기시간 총합 / 프로세스의 수)
AVR = (0 + 6 + 4 + 7)/3 = 5.66
4-6. Multilevel Queue
- "다단계 큐"라고도 불리며, 우선순위에 따라 준비 Queue를 여러 개 사용하는 방식이다.
- 각각의 Queue에는 절대적 우선순위가 존재하며, 각 Queue에는 독립적인 scheduling이 정책되어 있다.
- 상단의 큐 작업이 모두 완료되면 하단의 큐 작업 진행 (아사 현상 유발)
4-7. Multilevel Feedback Queue
- 우선순위가 높은 프로세스가 가장 먼저 진입한다. 하지만 너무 많은 CPU Time이 사용되면 한 단계 낮은 Queue로 이동한다.
- 아사 상태가 우려되는 프로세스는 한 단계 높은 Queue로 이동시켜 아사 현상을 예방한다.
Reference
