스케줄링
- 여러 프로세스가 번갈아 사용하는 자원을 어떤 시점에 어떤 프로세스에 할당할지 결정
- 스케줄링 방법에 따라 시스템의 성능에 영향을 미침
목적
- 자원 할당의 공정성 보장
- 단위 시간당 처리량 최대화 (CPU 활용을 최대화)
- 예측 가능성 보장
- 오버헤드 최소화 (Context Switching 비용 최소화)
스케줄링 수행 단계
1단계 : 작업 선택 (장기 스케줄링)
- 실제로 시스템 자원을 사용할 작업 결정하는 작업 스케줄링. 승인 스케줄링이라고도 함
- 작업 스케줄링에 따라 작업 프로세스들로 나눠 생성. 수행 빈도가 적다.
2단계 : 작업 승인과 프로세서 결정 스케줄링 (사용 권한 부여, 중기 스케줄링)
- 시스템의 오버헤드에 따라 연기할 프로세스를 잠정적으로 결정
- 1단계 작업 스케줄링과 3단계 프로세서 할당 스케줄링의 완충 역할
- 메모리 사용성도 높이고 작업 효율성도 향상시키는 스와핑 기능의 일부로 이해 가능
3단계 : 프로세서 할당 스케줄링 (준비 상태의 프로세스에 자원 할당, 디스패칭)
- 수행 빈도가 매우 많아 단기 스케줄링에 해당
장기 스케줄러와 단기 스케줄러의 가장 큰 차이는 실행 빈도이다.
단기 스케줄러는 실행할 프로세스를 수시로 선택하므로 매우 빨라야 한다.
장기 스케줄러는 시스템에 새로운 작업이 분단위로 들어오므로 단기 스케줄러에 비해 상대적으로 드물게 수행된다.
장기 스케줄러는 다중 프로그래밍의 정도(degree of multiprogramming)를 결정한다.
선점 스케줄링
→ 다른 프로세스가 사용 중인 프로세서를 선점(뺏을 수 있음)할 수 있는 스케줄링
- 프로세스 하나가 장시간 동안 프로세서를 독점하는 것을 방지한다.
- 우선순위가 높은 프로세스들의 긴급 처리가 가능
- 실시간 시스템에서 인터럽트를 받아들이지 않으면 결과는 예측 불가
- 대화식 시분할 시스템이나 실시간 시스템에서 빠른 응답 시간 유지를 위해 필수
- 오버헤드가 커질 수 있다.
비선점 스케줄링
→ 다른 프로세스가 사용 중인 프로세서를 뺏을 수 없음
- 모든 프로세서가 공정하게 관리된다.
- 응답 시간 예측이 용이하다.
스케줄링 알고리즘 참조 기준
- 프로세서 사용률
- 처리율
- 반환시간
- 대기시간
- 반응시간
선입선처리 (FCFS, First Come Fist Served)
비선점 방법으로 프로세서 스케줄링 알고리즘 중 가장 단순하다.
말 그대로 먼저 들어온 프로세스를 먼저 처리하는 알고리즘이다.
일괄 처리 시스템에서는 매우 효율적이지만, 빠른 응답을 요청하는 대화식 시스템에는 적합하지 않다.
최소 작업 우선 스케줄링 (SJF, Shortest Job First)
실행 시간이 가장 짧은 프로세스를 먼저 처리하는 알고리즘이다.
평균 대기시간이 가장 짧음
우선순위 스케줄링 (Priority Scheduling)
우선순위가 높은 순으로 스케줄링하는 알고리즘
만약 동일하다면 선입선처리로 처리한다.
문제점 : 우선순위가 낮은 프로세스는 무한정 연기되는 기아가 발생할 수 있음
해결 방법 : 에이징
- 오래 대기하는 프로세스들의 우선순위를 점진적으로 증가시키는 방법
라운드 로빈(round-robin) 스케줄링
- 시분할 시스템을 위해 설계됨
- 프로세서를 사용할 시간을 정의한다.
- 준비 큐를 순환 큐로 설계하여 스케줄러가 준비 큐를 돌아가면서 한 번에 한 프로세스에 정의된 규정 시간량만큼 프로세서 제공
→ 규정 시간량이 작을수록 문맥 교환 횟수는 많아지므로 문맥 교환에 소요하는 시간보다 규정 시간량을 충분히 크게 해야 한다.
HRN(Highest Response-ratio Next) 스케줄링
- 최소 작업 우선 스케줄링의 약점인 긴 작업과 짧은 작업 간의 지나친 불평등을 보완
- 비선점 스케줄링이며 우선순위 스케줄링의 또 다른 예
→ 우선순위를 계속 계산해야 하므로 메모리와 프로세서를 낭비해 오버헤드가 높을 수 있다.
라운드 로빈 스케줄링이 가장 많이 사용된다.
Reference
- 운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미
백엔드 개발자