운영체제 - 스케줄링 알고리즘

Schedule icons created by Freepik - Flaticon https://www.flaticon.com/free-icons/schedule

 

FCFS 스케줄링(First-Come First-Served)

 - 비선점 스케줄링 알고리즘

 - 준비 큐에 도착한 순서대로 디스패치

 - 장점 : 가장 간단한 알고리즘

 - 단점 : 처리시간이 짧은 프로세스가 긴 프로세스를 기다리거나, 중요한 프로세스가 나중에 수행될 수 있음(비효율적)

           프로세스가 도착하는 순서에 따라 평균 반환시간이 크게 변함(예측이 힘들다)

 

SJF 스케줄링(Shortest Job First) 

 - 비선점 스케줄링 알고리즘

 - 준비 큐에서 대기중인 프로세스 중 실행시간이 가장 짧다고 예상되는 작업을 먼저 디스패치

 - 장점 : 일괄처리 환경에서 구현하기 쉽다

 - 단점 : 실행 예상 시간을 사용자의 추정치에 의존하여 정확한 시간을 예상할 수 없음

 

SRT 스케줄링(Shortest Remaining Time)

 - 선점 스케줄링 알고리즘

 - 실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치

 - 장점 : SJF 스케줄링 기법보다 평균 대기시간이나 평균 반환시간에서 효율적

           대화형 운영체제에 유용함

 - 단점 : 각 프로세스의 실행시간 계산, 선점을 위해 문맥 교환 등 SJF 비해 오버헤드가 크다

 

RR 스케줄링(Round Robin)

 - 선점 스케줄링 알고리즘

 - 준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당랴에 따라 실행 -> 할당 시간안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤로 이동

 - 장점 : CPU를 독점하지 않고 공평하게 이용

           대화형 운영체제에 적절

 - 단점 : 시간 할당량을 적절하게 설정하지 않으면 FCFS 스케줄링과 같아지거나 오버헤드가 커질 수 있음

 

HRN 스케줄링(Highest Response Ratio Next)

 - 비선점 스케줄링 알고리즘

 - 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치(응답비율은 예상 실행시간이 짧을수록, 대기시간이 길수록 커짐)

 - 장점 : SJF 스케줄링의 단점을 보완

 

다단계 피드백 큐 스케줄링

 - 선점 스케줄링 알고리즘

 - I/O 중심 프로세스와 CPU 중심 프로세스의 특성에 따라 다르게 시간 할당

 - N개의 단계가 존재하여 커질수록 시간 할당량도 커짐

 - 장점 : I/O 위주의 프로세스(대화형)는 높은 우선권을 유지함

 - 연산 위주의 프로세스는 낮은 우선권이지만 긴 시간을 할당받음