CPU 스케줄링 알고리즘
CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에서 해야 하는 일을 스레드 단위로 CPU에 할당.
프로그램이 실행될 때는 CPU 스케줄링 알고리즘이 어떤 프로그램에 CPU 소유권을 줄 것인지 결정함.
이 알고리즘은 다음과 같은 설정을 목표로 하고 있음.
- CPU 이용률 증가
- 능률 증가
- 준비 큐(ready queue)에 있는 프로세스 최소화
- 응답 시간 감소
| CPU 스케줄링 알고리즘 | |||||
| 비선점형 | 선점형 | ||||
| FCFS | SJF | 우선순위 | 라운드로빈 | SRF | 다단계 큐 |
1. 비선점형 방식(Non-preemptive)
프로세스가 스스로 CPU 소유권을 포기하는 방식, 강제로 프로세스를 중지하지 않음.
따라서 컨텍스트 스위칭으로 인한 부하가 적음.
FCFS(First Come, First Served)
가장 먼저 온 것을 가장 먼저 처리하는 알고리즘.
길게 수행되는 프로세스 때문에 준비 큐에서 오래 기다리는 현상(convoy effect)이 발생하는 단점이 있음.
SJF(Shortest Job First)
실행 시간이 가장 짧은 프로세스를 가장 먼저 실행하는 알고리즘.
긴 시간을 가진 프로세스가 실행되지 않는 현상(starvation)이 일어나며 평균 대기 시간이 가장 짧음.
그러나 실제 실행 시간을 알 수 없기 때문에 과거의 실행했던 시간을 토대로 추측해서 사용.
우선순위
기존 SJF 스케줄링 긴 시간을 가진 프로세스가 실행되지 않는 현상을 오래된 작업일수록 '우선순위를 높이는 방법(align)을 사용해 보완한 알고리즘. FCFS를 활용하여 우선순위 알고리즘을 구현하기도 함.
2. 선점형 방식(Preemptive)
현대 운영체제가 쓰는 방식으로 지금 사용하고 있는 프로세스를 알고리즘에 의헤 중단시켜 버리고 강제로 다른 프로세스에 CPU 소우권을 할당하는 방식.
라운드 로빈(RR, Round Robin)
현대 컴퓨터가 쓰는 선점형 알고리즘 스케줄링 방법.
각 프로세스는 동일한 할당 시간을 주고 그 시간 안에 끝나지 않으면 다시 준비 큐의 뒤로 가는 알고리즘.
ex) q만큼의 할당 시간이 부여되었고 N개의 프로세스가 운영된다고 하면 (N-1) * q 시간이 지나면 자기 차례가 오게 됨.
할당 시간이 너무 크면 FCFS가 되고 짧으면 컨텍스트 스위칭이 잦아져서 오버헤드, 즉 비용이 커짐.
일반적으로 전체 작업 시간은 길어지지만 평균 응답 시간은 짧아진다는 특징이 있음.
로드밸런서에서 트래픽 분산 알고리즘으로도 쓰임.
SRF(Shortest Remaining Time First)
SJF는 중간에 실행 시간이 더 짧은 작업이 들어와도 기존 작업을 모두 수행하고 그 다름 짧은 작업을 이어나가는데, SRF는 중간에 더 짧은 작업이 들어오면 수행하던 프로세스를 중지하고 해당 프로세스를 수행하는 알고리즘.
다단계 큐
우선순에 따른 준비 큐를 여러 개 사용, 큐마다 라운드 로빈이나 FCFS등 다른 스케줄링 알고리즘을 적용한 것을 말함.
쿠 간의 프로세스 이동이 안되므로 스케줄링 부담이 적지만 유연성이 떨어지는 특징이 있음.
'면접을 위한 CS 전공지식 노트'를 기반으로 작성한 글입니다.