가라멜의 달달한 세상 탐방

스케줄링 알고리즘

1. 스케줄링 성능 평가 기준

- 평균 대기시간 : 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균 값

- 평균 반환시간 : 각 프로세스가 생성된 시점부터 수행이 완료된 시점까지의 소요시간의 평균 값 

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 위주의 프로세스는 높은 우선권 유지, 연산 위주의 CPU 중심 프로세스는 낮은 우선권이지만 긴 시간 할당량

- 단점 : 시간 할당량을 다 쓰기 전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 이동 배치

         : 연산 위주의 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능