비선점 스케줄링
- Non-preemptive Scheduling
- 프로세스가 할당 받은 자원을 스스로 반납할 때까지 사용
- 장점: 프로세스의 종료 시간에 대해 비교적 정확한 예측 가능
- 단점: 일시적으로 우선순위가 지켜지지 않을 수 있음, 평균 응답 시간이 길어질 수 있음
선점 스케줄링
- Preemptive Scheduling
- 대화형의 시분할 시스템 & 실시간 시스템 등에 적합
- 문맥 교환을 위한 오버헤드 증가
우선순위
- 프로세스의 중요도를 숫자로 표현
- 정적 우선 순위
- 프로세스 생성 당시에 부여되고 실행 중 불변
- 구현 단순, 적은 오버헤드
- 시스템 환경의 변화에 적절한 대응 곤란
- 동적 우선 순위
- 프로세스 생성 당시에 초기 우선순위 부여
- 시스템과 프로세스의 상태 변화에 따라 우선 순위 변경
- 구현 복잡, 우선순위의 수시 계산으로 오버헤드 큼
- 환경 변화에 유연한 대응 가능해야 함
FIFO 스케줄링
- First-In-First-Out
- 비선점 스케줄링
- 준비 상태에 먼저 도착한 프로세스에게 먼저 프로세서 할당
- 자원의 효율성 높음
- 일괄 처리 시스템 등에 적합
- 대화형 시스템에 부적합
- 프로세서를 장시간 독점하는 경우 다른 프로세스들이 오래 기다려야 함
- 평균 응답 시간이 길어질 수 있음
RR 스케줄링
- Round-Robin
- 선점 스케줄링
- 준비 상태에 먼저 도착한 프로세스에게 먼저 프로세서 할당
- 각 프로세스들에게 시간 할당량(time quantum) 지정
- time 할당량을 소모한 프로세스는 프로세서를 반납하고 준비상태로 전이
- 한 프로세스에 대한 프로세서 독점 방지
- 프로세서 선점에 따른 문맥 교환 오버헤드 증가
- 대화형 시스템, 시분할 시스템에 적합
- time quantum의 결정이 시스템 성능에 영향을 줌
SJF 스케줄링
- Shortest Job First
- 총 실행 시간이 가장 짧은 프로세스부터 스케줄링 하는 기법
- 비선점 스케줄링
- 장점
- 평균 대기 시간 최소화
- 시스템 내의 대기 프로세스 수를 최소화
- 많은 프로세스들에게 빠른 응답 시간 제공
- 준비 큐의 크기 감소, 저장 공간 오버헤드 줄임
- 단점
- 무기한 연기 현상 발생 가능
- 실행 시간이 긴 프로세스들의 무한 대기 가능
- 에이징 기법으로 해결 가능
- 프로세스 생성 시 총 실행 시간에 대한 정확한 계산 불가능
- 각 프로세스의 실행 시간에 대한 추정 필요
SRTN 스케줄링
- Shortest-Remaining-Time-Next
- SJF 스케줄링의 변형
- 서비스 시간이 가장 적게 남은 프로세스에게 먼저 프로세서 할당
- 선점 스케줄링
- 프로세스 실행 중 남은 실행 시간이 더 적은 프로세스가 준비 상태에 들어올 경우 선점됨
- 단점
- 프로세스 생성 시 총 실행 시간 추정 작업 필요
- 잔여 실행 시간에 대한 계속적인 계산 오버헤드 증가
- 실행 시간이 긴 프로세스들의 평균 응답 시간 길어짐
- 잦은 선점으로 문맥 교환 오버헤드 증대
- 위의 단점들로 인해 구현 및 사용이 비현실적, 단점 해결 및 보완이 가능하다면 효율적으로 사용 가능
HRRN 스케줄링
- High-Response-Ratio-Next
- 실행 시간이 길고 짧은 프로세스들간의 불평등 심화 방지 기법
- 응답률이 가장 높은 프로세스에게 우선권을 주는 방식
- 응답률: 서비스 시간에 대한 대기 시간 비율 = (대기시간 + 서비스시간) ÷ 서비스시간
- 특정 프로세스의 장시간 대기 방지
- 준비상태에서 기다리는 시간이 길어질수록 우선 순위 향상됨
- 단점: 프로세스의 총 실행 시간 추정 오버헤드 발생
MFQ 스케줄링
- Multi-level Feedback Queue
- 프로세스들에 대한 사전 정보가 전혀 없는 경우
- 준비 상태의 큐를 여러 개 두어 스케줄링
- MFQ 스케줄링 기법의 기본 목적
- 짧은 실행 시간을 요구하는 프로세스 선호
- 입출력 위주의 프로세스 선호
- 신속한 프로세스의 성격 분석으로 적응성 있게 스케줄링
- Feedback
- 현재까지 프로세서를 사용한 시간을 근거로 스케줄링 함
- 다단계 피드백 큐: 준비 큐를 여러 개 두어 준비 상태로 들어오는 프로세스들이 디스패치 될 당시와 같이 다른 큐로 진입할 수 있게 함
- 문제점
- 시스템 부하 증가
- 우선 순위가 낮아진 프로세스의 무기한 연기 현상 발생 가능
MFQ 스케줄링 기법의 변형
- 각 준비 큐마다 시간 할당량을 다르게 배정
- 디스패치된 프로세스는 해당 큐에 할당된 시간 할당량을 배정 받음
- 프로세스의 특성에 맞는 형태로 시스템 운영 가능
- 입출력 위주 프로세스들을 상위 단계의 큐로 이동, 우선 순위 높임
- 프로세스가 블럭될 때 상위의 큐로 진입하게 함
- 시스템 전체의 평균 응답 시간 줄임
- 입출력 작업 분산시킴
- 대기 시간이 지정된 시간을 초과한 프로세스들을 상위 큐로 이동
- 에이징 기법
- 특정 프로세스가 오랜 시간 준비 큐에서 대기하는 것 방지
