1️⃣ 개념
CPU를 사용하려고 하는 프로세스들 사이의 우선순위를 관리하는 작업
선점형 스케줄링과 비선점형 스케줄링으로 유형을 나눌 수 있음
목적
- 프로세스 처리율 증가
- 모든 프로세스에게 CPU를 공정하게 할당하여, 프로세스 처리율이 증가함
- CPU 이용률 최대화
- 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율 최대화
- 응답시간/대기시간/반환시간 최소화
- 응답시간: 요청 후 응답이 올 때까지의 시간
- 대기시간: 프로세스가 준비 큐에서 대기한 시간의 총합
- 반환시간: 프로세스가 입력되어 수행하고 결과를 산출하기까지 걸리는 시간
2️⃣ 프로세스 스케줄러
어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제 커널의 코드를 의미함
스케줄러는 역할과 목적에 따라서 3가지로 분류할 수 있음
단기 스케줄러
CPU 스케줄러라고도 하며, 미리 정한 스케줄링 알고리즘에 따라 실행할 프로세스를 선택함
즉, 준비 큐에 존재하는 프로세스 중 어떤 프로세스를 실행할지 결정하고, 선택된 프로세스에게 CPU를 할당함
중기 스케줄러
Swapper라고도 하며, 너무 많은 프로세스에게 메모리를 할당해 시스템의 성능이 저하되는 경우를 대비하기 위해 메모리에 적재된 프로세스 수를 관리함
우선순위가 가장 낮은 프로세스나 일정 시간 동안 활성화되지 않았던 프로세스들을 디스크로 내림
장기 스케줄러
작업 스케줄러라고도 부르며, 디스크에 저장되어 있는 프로그램 중 어떤 프로그램에 메모리를 할당하여 준비 큐로 보낼지 결정하는 역할을 함
즉, 하드 디스크에 있는 프로그램을 메모리에 로드하는 역할을 담당함
But, 현대 운영체제에서는 장기 스케줄러를 두지 않는 경우가 많음
프로세스가 시작되면 장기 스케줄러 없이 바로 그 프로세스에 메모리를 할당해 준비 큐에 넣어주게 됨
3️⃣ 선점형 스케줄링
하나의 프로세스가 CPU를 차지하고 있을 때, 우선순위가 높은 다른 프로세스가 현재 프로세스를 중단시키고 CPU를 점유하는 스케줄링 방식 (= 중간에 다른 프로세스가 빼앗는다)
- 장점: 비교적 빠른 응답, 대화식 시분할 시스템에 적합
- 단점: 우선순위가 높은 프로세스가 많이 들어오면 많은 오버헤드 발생
- 실시간 응답 환경, Deadline 응답환경 등에서 활용됨
라운드로빈 (RR, Round Robin)
FCFS를 선점형으로 변형한 기법
같은 크기의 시간할당량을 주고, 할당된 시간 내에 완료가 안되면 다시 준비 큐 리스트의 가장 뒤로 보내지며, CPU는 다음 프로세스로 넘어감
시간 할당량이 너무 커지면 FCFS와 비슷해지고, 너무 작아지면 오버헤드가 커짐
SRT (Shortest Remaining Time First)
가장 짧은 시간이 소요되는 프로세스를 먼저 수행하고, 남은 처리시간이 더 짧은 프로세스가 준비 큐에 생기면 언제라도 그 프로세스가 선점됨
SJF 기법을 선점형으로 구성한 방식으로, 각 프로세스의 실행시간 추적, 선점을 위한 문맥 교환 등 SJF보다 오버헤드가 크다는 단점
다단계 큐 (MLQ, Multi Level Queue)
각 프로세스마다 우선순위를 설정하고, 우선순위마다 준비 큐를 생성함
항상 가장 높은 우선순위 큐에 있는 프로세스에 CPU를 할당함
즉, 만약 우선순위가 낮은 큐에서 작업이 실행 중이더라도 상위 단계의 큐에 프로세스가 도착하면 CPU를 빼앗음
큐들 간 프로세스 이동이 불가능하기 때문에 유연성이 떨어지며, 우선순위가 낮은 프로세스가 오랫동안 CPU 할당을 기다리는 기아 현상이 발생할 수 있다는 단점
다단계 피드백 큐 (MFQ, Multi Level Feedback Queue)
프로세스 생성 시 가장 높은 우선순위 준비 큐에 등록되며, 해당 큐의 CPU 시간 할당량이 끝나면 한 단계 아래의 준비 큐에 들어감
기본적으로 가장 우선순위가 낮은 큐를 제외하고는 RR 스케줄링 방법을 사용함
단계가 내려갈수록 시간 할당량이 증가함
큐 사이 프로세스 이동이 가능하며, 맨 아래 큐에서 너무 오래 대기한 프로세스는 다시 상위 큐로 이동함 (에이징 기법을 통한 기아 상태 예방)
4️⃣ 비선점형 스케줄링
한 프로세스가 CPU를 할당 받으면, 해당 프로세스가 작업을 종료하고 CPU를 반환할 때까지
다른 프로세스는 CPU 점유가 불가능한 방식 (뺏기 불가능)
- 장점: 응답시간 예상 용이, 모든 프로세스의 요구를 공정하게 처리
- 단점: CPU 사용시간이 짧은 프로세스들이 사용 시간이 긴 프로세스로 인해 오래 기다리는 경우 발생
- 처리시간의 편차가 적은 특정 프로세스 환경에 활용
우선순위 (Priority)
프로세스 별로 우선순위가 주어지고, 이 우선순위에 따라 CPU를 할당함
동일 우선순위는 FCFS로 처리
주요 긴급 프로세스를 우선적으로 처리하고, 설정이나 자원 상황 등에 따라 우선순위를 선정함
기한부 (Deadline)
설명 추가 예정
FCFS (First Come First Served; FIFO)
준비 큐에 도착한 순서에 따라 CPU를 할당함
SJF (Shortest Job First)
준비 큐에 있는 작업 중 가장 짧은 작업부터 수행함
FIFO보다 평균 대기시간이 감소함
But, CPU 요구시간이 긴 작업과 짧은 작업 간 불평등이 심하여 기아현상이 발생할 수 있음
HRN (Highest Response Ratio Next)
우선순위 계산 공식을 이용해, 서비스(실행)시간이 짧은 프로세스나 대기시간이 긴 프로세스에게 우선순위를 주어 CPU를 할당하는 기법
- 우선순위 = (대기시간+서비스시간) / 서비스 시간
- 우선순위를 계산하여 그 수치가 높은 순으로 우선순위를 부여
- SJF의 약점인 기아 현상을 보완한 기법으로, 긴 작업과 짧은 작업 간 등의 불평등을 완화함
참고자료
https://dev.classmethod.jp/articles/load-balancing-types-and-algorithm/
https://www.samsungsds.com/kr/techreport/job-scheduling.html
https://velog.io/@jinh2352/Linux-8-실시간-태스크-스케줄링-FIFO-RR-DEADLINE
https://ko.wikipedia.org/wiki/최단마감우선_스케줄링
https://damagucci-juice.tistory.com/120
https://haun25ne.tistory.com/55
https://cocoon1787.tistory.com/124
https://taegyunwoo.github.io/os/OS_MultiLayerQueue_MultiProcessor_RealtimeSystem
