스케줄링 알고리즘

스케줄링 성능 평가 기준

• 평균 대기시간: 각 프로세스가 생성된(준비 큐에 들어온) 시점부터 준비 큐에서 기다리는 시간의 합의 평균값

• 평균 반환시간: 각 프로세스가 생성된(준비 큐에 들어온) 시점부터 수행이 완료된 시점까지의 소요시간의 평균값

TIP

반환시간 = 대기시간 + 수행시간

스케줄링 알고리즘 목록

선점, 비선점의 차이

선점 기법: 실행 중인 프로세스를 중지시키고 CPU를 강제로 뺏어올 수 있는 방식 (문맥교환 O)
비선점 기법: 지금 실행중인 프로세스를 강제로 중지시킬 수 없는 방식 (문맥교환 X)

문맥교환이란?

프로세스를 바꿔주는 행위
(SRT 스케줄링에서 남은 시간이 더 적은 프로세스를 CPU에게 할당하기 위해 실행중인 프로세스와 교환하는 것을 뜻함)

	특징	장점	단점
FCFS 스케줄링 (First-Come First-Served)	비선점 스케줄링 알고리즘	가장 간단한 스케줄링 기법	- 중요한 프로세스가 있더라도 나중에 수행될 수 있음 - 프로세스들의 도착 순서에 따라 반환시간이 크게 변함
SJF 스케줄링 (Shortest Job First)	비선점 스케줄링 알고리즘 (대기중인 프로세스 중에서 실행시간이 가장 짧다고 예상된 것을 먼저 디스패치함)	일괄처리 환경에서 구현하기 쉬움	실행 예정 시간 길이를 사용자의 추정치에 의존하기 때문에 실제로 먼저 처리해주어야 할 작업을 알 수 없음
SRT 스케줄링 (Shortest Remaining Time)	선점 스케줄링 알고리즘 (매 시간마다 CPU에게 할당할 프로세스를 바꿔줄 수 있음) 실행이 끝날 때까지 남은 시간 추정치가 가장 짧은 프로세스를 먼저 디스패치	- SJF보다 평균 대기시간이나 평균 반환시간에서 효율적 - 대화형 운영체제에 유용	- 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드가 큼
RR 스케줄링 (Round Robin)	선점 스케줄링 알고리즘 - 준비 큐에 도착한 순서에 따라 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한함 - 시간 할당량 안에 완료되지 못한 프로세스는 준비 큐의 맨 뒤에 배치	- CPU를 독점하지 않고 공평하게 이용 - 대화형 운영체제에 유용	- 시간 할당량이 너무 크면 FCFS 스케줄링과 같아짐 - 시간 할당량이 너무 작으면 문맥 교환에 따른 오버헤드가 크게 증가함
HRN 스케줄링 (Highest Response Ratio Next)	비선점 스케줄링 알고리즘 - 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치 - 예상 실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커짐	SJF의 단점을 보완
다단계 피드백 큐 스케줄링	선점 스케줄링 알고리즘 - I/O or CPU 중심 프로세스 특성에 따라 서로 다른 시간 할당량 부여 - n개의 단계가 있고 각 단계마다 큐가 하나씩 존재 - 단계가 커질수록 시간 할당량도 커짐	- I/O 위주의 프로세스(대화형)는 높은 우선권 유지	- 연산 위주의 CPU 중심 프로세스는 낮은 우선권이라서 단계가 높아지는 대신 긴 시간 할당량을 가지게 됨
적응형 다단계 피드백 큐 스케줄링	선점 스케줄링 알고리즘 - 시간 할당량을 다 쓰기 전에 CPU를 반납하는 경우 하나 작은 단계의 큐로 이동 배치 - 연산 위주의 프로세스가 I/O 위주로 바뀐다면 점점 작은 단계로 배치 가능

응답비율 공식

다단계 피드백 큐 스케줄링 방법

1. 신규 프로세스는 단계 1의 큐에서 FIFO 순서에 따라 CPU 점유
2. 입출력 같은 이벤트가 발생하면 CPU를 양보하고 대기상태로 갔다가 다시 준비상태가 될 때에는 동일한 단계의 큐에 배치
3. 시간 할당량을 다 썼는데도 프로세스가 종료되지 않았다면 다음 단계로 이동
4. 마지막 단계 n에서는 RR 스케줄링 방식으로 동작
5. 단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 1부터 k-1까지 모든 큐가 비어있어야만 함