스케줄링 알고리즘
운영체제는 실행할 준비가 된 프로세스들이 적절히 CPU를 배정받아 효율적으로 작업을 처리할 수 있도록 관리해야 하고
이를 처리할 수 있도록 관리해야 하고, 이를 위해서 다양한 스케줄링 알고리즘을 활용한다.
01. 스케줄링 성능 평가 기준
1) 평균 대기시간
- 각 프로세스가 수행이 완료될 때까지 준비 큐에서 기다리는 시간의 합의 평균값
2) 평균 반환시간
- 각 프로세스가 생성된 시점부터 수해이 완료된 시점까지 소요시간의 결과값
02. 다양한 스케줄링 알고리즘
01) FCFS 스케줄링
(1) SJF(Shrtest Job First) 스케줄링
- 비선점 스케줄링 알고리즘
- 준비 큐에서 기다리는 프로세스 중 실행기간이 가장 짧다고 예상된 것을 먼저 디스패치 ❖ 장점 : 일괄처리 환경에서 구현하기 쉬움 ❖ 단점 : 실행 예정 시간 길이를 사용자의 추정치에 의존하기 떄문에 실제로는 먼저 처리할 작업의 CPU 시간을 예상할 수 없음
(2) SRT 스케줄링
- 선점 스케줄링 알고리즘
- 실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치
❖ 장점
- SJF 보다 평균 대기시간이나 평균 반환시간에서 효율적
- 대화형 운영체제에 유용
❖ 단점
- 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등
- SJF보다 오버헤드가 큼
(3) RR 스케줄링
- 선점 스케줄링 알고리즘
- 준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한
- 시간 할당량 안에 완료되지 못한 프롤세스는 준비 큐의 맨 뒤에 배치
❖ 장점
- CPU를 독점하지 않고 공평하게 이용
- 대화형 운영체제에 유용
❖ 단점
- 시간 할당량이 너무 크면 FcFS 스케줄링과 같아짐
- 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함
(4) HRN 스케줄링
- 비선점 스케줄링 알고리즘
- 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치
- 예상 실행시간이 짧을수록 , 대기시간이 갈수록 응답비율이 커짐
❖ 장점
- SJF의 단점을 보완
(5) 다단계 피드백 큐 스케줄링
- 선점 스케줄링 알고리즘
- I/O 중심 프로세스와 CPU 중심 프로세스의 특성에 따라 서로 다른 시간 할당량 부여
- n개의 단계 ( 단게 1 ~ 단계 n)
- 각 단계마다 하나씩의 큐 존재
- 단계가 커질수록 시간 할당량도 커짐