SJF 스케줄링(Shortest Job First Scheduling)
최소 작업 우선 스케줄링이란 각 작업의 프로세서 실행 시간을 이용하여 프로세서가 사용 가능할 때 실행 시간이 가장 짧은 작업에 할당하는 방법
- 최소 작업 우선 스케줄링은 FIFO 스케줄링
에서 실행 시간에 따른 할당 방식의 차이가 FIFO와 SJF의 차이점임 - 장점 : 항상 실행 시간이 짧은 작업을 신속하게 실므로 평균 대기 시간이 가장 짧음
- 단점 : 아사 현상, 해결 방법으로는 에이징이 있다. 나이 제한을 둠으로써 일정 횟수 이상 밀리면 더 이상 양보하지 않고 작업하는 것, 현대의 프로세스는 사용자와의 상호작용이 빈번하기 때문에 종료 시간을 예측할 수 없다. 따라서 SJF 스케줄링을 사용하기 힘듦, 프로세스가 자신의 작업 시간을 운영체제에 알려주어 해결할 수 있다. 하지만 이를 정확히 알기가 어렵다.
- 기본적으로 짧은 작업이 항상 실행되도록 설정하므로 불공정한 작업을 실행
- 반환 시간 = 실행 시간 + 대기 시간
- 대기 시간 = 반환 시간 - 실행 시간
SRT 스케줄링(Shortest Remaining Time)
- • SJF 방식을 선점 스케줄링 방식으로 변경한 기법임
- SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식, 최소 잔류 시간 우선 스케줄링이라고도 함, 준비 큐에 남아 있는 작업시간이 가장 작은 프로세스를 선택, 그리고 타임 슬라이스를 부여하여 작업 시간 제한을 둠.
- 장점 : SJF 스케줄링과 평균 대기 시간을 비교했을 때 SRT 스케줄링의 평균 대기 시간이 더 짧음
- 단점 : 현재 실행 중인 프로세스와 큐에 있는 프로세스의 남은 시간을 주기적으로 계산하고, 남은 시간이 더 적은 프로세스와 컨텍스트 스위칭을 해야 함. SJF 스케줄링에는 없던 작업이 추가된 것,운영 체제가 프로세서의 종료 시간을 예측하기 어렵고 아사 현상이 일어나기 때문에 잘 사용하지 않음
RR 스케줄링(Round-Robin)
프로세스가 CPU를 할당받고 작업하는 동안 할당받은 시간(타임 슬라이스)이 지나면 준비 큐의 맨 뒤로 보내는 방식. 선점형 알고리즘 방식 중 가장 단순하고 대표적인 방식으로 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행됨. FCFS 스케줄링에서 타임 슬라이스를 추가한 것. 우선 순위는 없음.
타임 슬라이스의 크기를 어떻게 설정하냐에 따라 시스템의 성능이 좌우됨
- 타임 슬라이스가 큰 경우
컨텍스트 스위칭 횟수가 적다. 하지만 너무 커질 경우 한 작업이 완료될 때까지 기다려야 하는 것처럼 보임. 만약 크기가 무한대라면 FCFS와 비슷. - 타임 슬라이스가 작은 경우 컨텍스트 스위칭 횟수가 많음. 이로 인해 실제 작업 시간보다 더 많아짐.
따라서 타임 슬라이스는 되도록 작게 설정하되 컨텍스트 스위칭에 걸리는 시간을 고려하여 적당한 크기로 하는 것이 중요함.
HRRN 스케줄링(Highest response ratio next)
HRRN은 Response Ratio를 계산하여 해당 값이 가장 높은 프로세스를 우선적으로 스케줄링하는 기법임.
- SPN을 변형한 기법 : SRTN보다 현실적임
- 비선점형 스케줄링
- Aging concepts : SPN의 기아 현상을 해결하기 위한 개념임
- 나이가 많은(대기 시간이 긴)프로세스를 배려한다는 의미
- 즉, 프로세스의 대기시간을 고려하여 스케줄링함
- Response ratio (응답률) : (대기 시간 + 실행 시간) / 실행 시간
- 분자의 대기 시간이 높으면 우선순위가 높아짐
- 즉, 실행 시간 대비 얼마나 기다렸는지를 고려함
SPN의 장점을 취하면서 기아 문제를 방지했지만, 여전히 실행 시간을 예측해야한다(Overhead)는 문제점이 있음
다단계 피드백 큐(MFQ) 스케줄링(MultiLevel Feedback Queue Scheduling)
다 단계 큐 + 동적인 프로세스 우선 순위 변화 적용
- 프로세스 생성 시 가장 높은 우선 순위 준비 큐에 등록되며 등록된 프로세스는 FCFS 순서로 CPU를 할당 받아 실행된다. 해당 큐의 CPU 시간 할당량(Time Quantum)이 끝나면 한 단계 아래의 준비 큐에 들어감
- 단계가 내려갈수록 시간 할당량(Time Quantum)이 증가함
- 큐 사이의 프로세스 이동 가능하며 CPU Burst는 낮은 우선순위의 큐, I/O Burst는 높은 우선순위의 큐에 배치함
- 가장 하위 큐는 FCFS 스케줄링
다단계 피드백 큐 스케줄링의 경우 큐의 수, 각 큐에 대한 알고리즘, 우선순위 격상 또는 격하 시기 결정, 처음 프로세스들이 진입해야 할 큐 등등 매우 복잡한 판단을 요구함
BSSM