스케줄러
- 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드
종류
1. 장기 스케줄러(Long term scheduler)/잡 스케줄러(Job scheduler)
- 메모리는 한정되어 있는데 많은 프로세스들이 한꺼번에 메모리에 올라올 경우, 대용량 메모리에 임시로 저장된다.
- 이 pool에 저장되어 있는 프로세스 중 어떤 프로세스에 메모리를 할당하여 ready queue로 보낼지 결정하는 역할을 한다.
- 메모리와 디스크 사이의 스케줄링을 담당
- 프로세스에 메모리를 할당
- degree of Multiprogramming (메모리에 여러 프로그램이 올라가는 것) 제어
- 프로세스의 상태 (new -> ready(in memory))
메모리에 프로그램이 너무 많이 올라가거나 적게 올라가면 성능이 좋지 않은 것임
2. 중기 스케줄러(Medium-term scheduler)/스와퍼(Swapper)
- 여유 공간 마련을 위해 프로세스를 통쨰로 메모리에서 디스크로 쫓아냄
- 프로세스에게서 메모리를 deallocate
- degree of Multiprogramming 제어
- 현 시스템에서 메모리에 너무 많은 프로그램이 동시에 올라오는 것을 조절하는 스케줄러
- 프로세스의 상태 (ready -> suspended)
suspended : 외부적인 이유로 프로세스의 수행이 정지된 상태로 메모리에서 내려간 상태
- 프로세스 전부 swap out 된다.
- blocked 상태의 경우 스스로 ready state로 돌아갈 수 있지만 suspended 상태의 경우 스스로 ready state로 돌아갈 수 없다.
3. 단기 스케줄러(Short term scheduler)/CPU 스케줄러(CPU scheduler)
- CPU와 메모리 사이의 스케줄링을 담당
- Ready Queue에 존재하는 프로세스 중 어떤 프로세스를 running 시킬지 결정
- 프로세스에 CPU를 할당
프로세스의 상태 (ready -> running -> waiting -> ready)
스케줄링 알고리즘
1. FCFS(First Come First Served)
- 먼저 준비된 프로세스를 먼저 처리
- 간단하고 공정함 (우선순위, 실행시간 등의 다른 요소는 전혀 고려 X, 먼저 준비되면 먼저 실행)
- 실행시간이 긴 프로세스 먼저 실행 시 대기시간이 길어짐
- 콘보이 현상 발생(Convoy Effect)
- 비선점 스케줄링
콘보이 현상(Convoy Effect)
burst time이 긴 프로세스가 먼저 도착해 다른 프로세스의 실행 시간이 전부 늦처줘 효율을 떨어뜨리는 현상
2. SJF(Shortest Job First)
- Starvation 발생 가능
- burst time이 짧은 프로세스가 먼저 CPU를 할당
- 비선점 스케줄링
3. SRT(Shortest Remaining Time First)
- 남은 burst time이 더 짧은 프로세스에 CPU를 할당
- Starvation 발생 가능
- 선점형 스케줄링 방식
4. 우선순위 스케줄링(Priority Scheduling)
- 우선순위가 높은 프로세스에 CPU를 먼저 할당
- 기아 현상과 무기한 봉쇄가 발생할 수 있으며 에이징 기법을 통해 해결
- 선점 비선점 모두 가능
에이징 기법
먼저 도착한 프로세스가 나이를 계속 먹으며 우선순위가 올라가는 기법
5. 라운드 로빈(RR, Round Robin)
- 프로세스에 동일한 할당 시간만큼 순서대로 계속 CPU를 할당
- 응답시간이 빠르며, 모든 프로세스가 공정하게 CPU를 할당받을 수 있음을 보장
- 선점형 스케줄링 방식
6. 다단계 큐(Multilevel Queue)
- Background에서 돌아가는 프로세스와 Foreground의 프로세스에 다른 알고리즘을 적용하는 방식
- 큐 사이에 서로 다른 CPU 할당시간 적용
- Background에서는 FCFS, Foreground에서는 RR 알고리즘 적용
- 선점 스케줄링 방식
7. 다단계 피드백 큐 (Multilevel Feedback Queue)
- 프로세스가 큐 사이를 이동 가능
- 각 큐에 서로 다른 CPU 할당 시간을 적용함으로써, 프로세스가 해당 시간동안 작업을 다 처리하지 못했다면, 점점 긴 Time Quantum을 할당해주는 큐로 이동
- 우선 순위는 Time Quantum이 짧은 큐가 높음
- Starvation이 발생 가능하며 에이징을 통해 해결 가능
선점 스케줄링
한 프로세스가 CPU를 할당받아서 실행하고 있을 때 다른 프로세스가 CPU를 사용하고 있는 프로세스를 중지시키고 CPU를 차지할 수 있는 스케줄링 기법
- 우선순위가 높은 프로세스를 먼저 수행할 때 유리하고 빠른 응답 시간을 요구하는 대화식 시분할 시스템에 유용
- 많은 오버헤드 초래
- 기아(Starvation) 현상 발생 가능
비선점 스케줄링
이미 사용되는 CPU를 빼앗지 못하고 사용이 끝날 떄까지 기다리는 스케줄링 기법
- 할당받은 CPU는 끝날 때까지 사용
- 응답 시간을 예측 가능
- 일괄 처리 방식이 적합
- 모든 프로세스의 요구에 대해 공정
- 중요도가 높은 작업이 낮은 작업을 기다릴 수 있음
- 문맥교환(Context Switching)으로 인한 오버헤드가 적음
좋은 스케줄링 방식인지 판단하는 기준
- CPU utilization
- Throughput
- Turnaround Time
- Waiting Time
- Response Time
참고
