- 알고리즘 선택 기준
CPU 사용률, 처리량, 대기 시간, 응답 시간 등을 보지만 계산하기 어렵기 때문에 주로 평균 대기 시간을 봄
- 비선점형 알고리즘
- FCFS (First Come First Served) 스케줄링
- 동작 방식
준비 큐에 도착한 순서대로 CPU 에 할당함
- 평가
처리 시간 긴 프로세스가 CPU 차지 시 다른 프로세스들이 기다려야 해서 효율성 떨어짐
프로세스 입출력 시 유휴시간 길어져 작업 효율 떨어짐
- SJF (Shortest Job First) 스케줄링
- 동작 방식
준비 큐에 있는 프로세스 중 실행 시간이 가장 짧은 작업부터 CPU 에 할당
- 평가
운영체제가 프로세스의 종료 시간 정확히 예측 어려움
공평하지 못 해 아사 문제 생길 수 있음
- 문제 해결책
프로세스가 자신의 작업 시간 운영체제에 알려줌
프로세스가 양보할 수 있는 상한선인 에이징을 정함
- HRN (Higest Response Ratio Next) 스케줄링
- 동작 방식
대기 시간과 CPU 사용 시간을 고려하여 우선 순위를 두고 스케줄링
우선순위 = 대기 시간 + CPU 사용 시간 / CPU 사용 시간
- 평가
아사 현상을 완화함
공평성이 위배됨
- 선점형 알고리즘
- 라운드 로빈 스케줄링
- 동작 방식
한 프로세스가 타임 슬라이스 동안 작업하다가 작업 완료 못 할 시 준비 큐의 맨 뒤로가서 차례 기다림
- 문맥 교환
문맥 교환에 대한 오버헤드 때문에 비효율적으로 될 수 있음
- 타임 슬라이스
타임 슬라이스가 적절히 배분되어야 문맥 교환 추가시간 고려
너무 클 경우 반응 속도 느려짐
너무 작을 경우 전반적인 성능 떨어짐
- SRT (Shortest Remaining Time) 우선 스케줄링
- 동작 방식
라운드 로빈 스케줄링에 SJF 스케줄링 혼합
- 평가
남은 시간 주기적 계산해야 하고 아사 현상 일어남
- 다단계 큐 스케줄링
우선 순위에 따라 준비 큐를 여러 개 사용하여 높은 우선 순위의 프로세스 우선 처리
고정형 우선순위 사용
우선 순위에 따라 타임 슬라이스 조절하여 작업 효율 높임
우선 순위가 높은 프로세스 때문에 우선 순위 낮은 프로세스 작업이 연기됨
- 다단계 피드백 큐 스케줄링
다단계 큐 스케줄링의 방식에 CPU 사용하고 난 프로세스의 우선순위를 낮추는 스케줄링
우선 순위가 낮은 프로세스에 불리한 다단계 큐 스케줄링 문제점 보완
커널 프로세스와 일반 프로세스의 큐에는 삽입되지 않음
마지막 큐는 FCFS 스케줄링으로 동작
일반적으로 운영체제가 사용하는 방식
- 우선 순위 알고리즘
프로세스의 중요도에 따라 우선 순위를 갖게 하는 알고리즘
고정 우선순위 알고리즘과 변동 우선순위 알고리즘으로 나뉨
- 특징
비 선점형과 선점형 모두 적용 가능
- 평가
아사 일으킬 수 있음
우선순위 매번 바꿔야 함으로 시스템 효율 떨어뜨림
프로세스의 중요도를 기준으로 결정됨