Preemptive vs Non-preemptive
Preemptive : CPU가 실행중인 프로세스가 종료되거나 I/O가 발생하지 않아도 강제로 다른 프로세스가 점유 할 수 있는 것
Non-preemptive : 프로세스가 CPU를 할당받고 작업이 끝나면 CPU를 돌려줌
Scheduling Criteria
- CPU Utilization : CPU 활용도 (CPU가 얼마나 부지런하게 일하는가)
- Throughput : 단위시간당 처리한 프로세스 개수
- Waiting Time : 프로세스가 레디큐에서 기다리는 시간 (짧을 수록 좋음)
- Turnaround Time : 어떤 프로세스가 완료될 때까지 걸리는 시간 (짧을 수록 좋음)
- Response Time : 첫 응답이 올 때까지의 시간
CPU Scheduling
메인 메모리에서 실행중인 프로세스에게 CPU를 효율적으로 할당하는 것
FCFS (First-Come, First-Served)
먼저 온 프로세스를 CPU가 먼저 처리하는 방식
Convoy effect (호위 효과) : CPU 시간을 오래 사용하는 프로세스가 먼저 실행되는 동안 나머지 프로세스들이 그 만큼 기다려야하는 것 → CPU와 디바이스의 활용도가 나쁠 수 있음
Non-Preemptive 방식
SJF (Shortest-Job-First)
수행시간이 가장 짧은 프로세스가 가장 먼저 수행되는 방식
Non-Preemptive SJF
Preemptive SJF (SRTF)
SRTF는 Preemptive 방식으로, 각 프로세스들의 남은 실행 시간을 비교하여, 실행 시간이 더 짧은 새로운 프로세스가 들어올 경우 먼저 처리해주는 방식이다.
SRTF가 가장 이상적인 방법일 수 있다. 하지만 실제로는 컴퓨터에서 프로세스의 점유시간(burst time)을 알 수 없다. → 프로세스 점유시간을 예측하기 위해서는 많은 오버헤드가 생길 수 있다.
Priority Scheduling
우선순위가 높은 프로세스부터 처리하는 방식
Non-Preemptive와 Preemptive 모두 될 수 있음
문제점 : 기아상태(Starvation) → 우선순위가 낮은 프로세스들이 CPU를 무한히 대기하는 경우가 발생한다.
해결방식 : Aging → 우선순위가 낮은 프로세스들을 주기적으로 점진적으로 우선순위를 높여, 기아 상태를 해결함
현재 대부분의 OS는 Priority Scheduling을 사용함
RR (Round-Robin)
모든 프로세스가 같은 시간(Time Quantum, Time Slice)동안 돌아가며 처리되는 방식
시분할(Time-Sharing) 방식을 위해 설계
Time Quantum→ ∞ : FCFS와 같이 작동
Time Quantum→ 0 : Context Switching이 자주 일어나 overhead가 증가하여 비효율적임 (process sharing: 여러 프로세스가 거의 같이 도는것과 같이 보임)
Time Quantum : 실행의 최소 단위 시간
Preemptive 방식이다.
Multilevel Queue
여러 개의 큐를 갖고 모두 다른 스케줄링을 하며, 각 큐 간의 우선순위가 존재하는 방식
큐들 간의 프로세스 이동이 불가능하여, 스케줄링의 부담이 적다.
CPU time을 각 큐에 차등 배분하여 작동한다.
기아상태(Starvation)가 생길 수 있다는 단점이 있다.
Multilevel Feedback Queue
큐들 간의 프로세스 이동이 가능한 Multilevel Queue
할당 받은 시간 내에 프로세스 처리가 끝나지 못하면 하위 큐로 프로세스를 내린다.
기아상태(Starvation)가 우려되면 우선순위가 높은 큐로 이동한다.
| FCFS | SJF | Priority | RR | |
|---|---|---|---|---|
| Preemptive | X | O (SRTF) | O | O |
| Non-Preemptive | O | O | O | X |
스케줄링이 진행되는 시점
- 매 타임퀀텀 마다
- 새로운 프로세스가 등장할 때 마다
- 현재 실행중인 프로세스가 종료될 때마다
- 현재 실행중인 프로세스가 I/O 요청에 의해 Blocked 상태에 놓일 때 마다
