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