[운영체제] CPU 스케줄링 알고리즘

2021. 7. 30. 15:50

1. CPU 스케줄링 알고리즘

: 스케줄링(scheduling)은 다중 프로그래밍을 가능하게 하는 운영 체제의 동작 기법이다. CPU가 유휴상태(어떠한 프로그램에 의해서도 사용되지 않는 상태)가 될 때마다 운영체제는 준비 완료 큐에 있는 프로세스 중 하나를 선택해 실행해야 한다. CPU 스케줄러는 CPU 스케줄링 알고리즘에 따라 프로세스에 CPU를 할당하고 작업을 완료한다.

2. 스케줄링 알고리즘의 평가 기준

CPU 사용률 (CPU Utilization)	전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율. 이상적인 수치는 100%이지만 주로 90%를 목표로 함.
처리량 (Throughput)	CPU가 단위 시간당 처리하는 프로세스의 개수. 클수록 좋은 알고리즘.
응답 시간 (Response Time)	대화식 시스템에서 요청 후 응답(첫번째 출력)이 오기 시작할 때까지의 시간.
대기 시간 (Waiting Time)	프로세스가 생성된 후 준비 큐 내에서 실행되기 전까지 대기하는 시간의 총합.
반환 시간 (Turnaround Time)	프로세스가 시작해서 끝날 때까지 걸리는 시간.
평균 대기시간 (Average Waiting Time)	[모든 프로세스의 대기시간 총 합] / [프로세스의 개수]

출처 https://herong.tistory.com/entry/08-CPU-스케줄링-알고리즘

3. 선점형 & 비선점형

: 스케줄링 알고리즘의 적용 시점에 따라 구분

선점형 스케줄링 (Preemptive Scheduling)

한 프로세스가 CPU를 차지하고 있을 때 우선순위가 높은 다른 프로세스가 현재 프로세스를 중지시키고 자신이 CPU점유 가능
모든 프로세스에게 CPU 사용 시간을 동일하게 부여 가능
높은 우선순위를 가진 프로세스가 먼저 수행되어야 할 때 유용
빠른 응답 시간을 요구하는 대화식 시분할 시스템이나 처리 시간이 제한되어 있는 실시간 시스템에 유용
높은 우선순위 프로세스들이 들어오는 경우 오버헤드를 초래
RR, SRTF, 다단계 큐, 다단계 피드백 큐, RM, EDF 스케줄링

비선점형 스케줄링 (Non-preemptive Scheduling)

프로세스에게 이미 할당된 CPU를 다른 프로세스가 강제로 점유 불가
모든 프로세스들에 대한 요구를 순서대로 공정하게 처리하며 응답시간의 예측 가능
선점 방식보다 스케줄러 호출 빈도가 낮고 문맥교환에 의한 오버헤드가 적음
짧은 작업을 수행하는 프로세스가 긴 작업의 종료를 기다리는 경우가 발생하여 처리율이 떨어질 수 있음
FCFS, SJF, HRRN 스케줄링

4. 스케줄링 알고리즘의 종류

FCFS (FIrst Come First Served)

가장 단순한 형태의 스케줄링 기법으로 FIFO(First In First Out)라고도 함
먼저 대기 큐에 들어온 작업에게 CPU를 할당하며 비선점 스케줄링 방식
일괄 처리 시스템에서는 효율적이나 사용자가 빠른 응답을 요구하는 대화식 시스템에서는 부적합
준비 큐가 하나로 모든 프로세스의 우선순위는 동일하여 작업 완료 시간 예측 용이
처리량이 긴 프로세스가 CPU를 차지하면 다른 프로세스들의 기다리는 호위 효과 (Convoy effect) 발생

SJF (Shortest Job First)

FCFS에서의 평균 대기 시간을 최소화 하기 위해 준비 큐에서 작업 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식
비선점 또는 선점형 모두 가능하며 선점형에 적용되는 SJF 스케줄링을 SRT (Shortest Remaining Time) 스케줄링이라 함
짧은 작업에 유리
긴 프로세스는 계속 뒤로 밀리는 기아 상태가 발생하며 공평성이 떨어짐
각 프로세스의 종료 시간 예측이 어려움

HRRN (Highest Response Ratio Next)

SJF에서의 기아 현상을 보완하기 위해 만들어진 비선점형 스케줄링 방식
우선순위 = (대기한 시간 + CPU 사용 시간) / CPU 사용 시간
CPU 사용 시간이 분모에 있으므로 짧은 작업의 우선 순위가 높아지며, 대기 시간이 분자에 있으므로 긴 작업도 대기 시간이 큰 경우에는 우선 순위가 높아짐

RR (Round Robin)

시분할 시스템을 위한 선점형 스케줄링 방식이며 선점형 중 가장 단순하고 대표적임
시간 할당량(time slice) 또는 time quantum 라는 시간의 단위를 정의하여 구현
준비 큐는 순환 큐로 설계하여 스케줄러가 준비 큐를 돌아가면서 한번에 한 프로세스에 정의된 time slice만큼 프로세스 제공
한 프로세스가 time slice동안 작업을 완료하지 못하면 실행을 강제로 다른 프로세스에게 선점시키고 그 프로세스는 준비 큐의 맨 뒤로 가서 자기 차례를 기다림
프로세스들의 모든 작업이 완료될 때까지 계속 순환하며 실행
time slice가 크면 FCFS와 같게 되고, 작으면 문맥 교환이 자주 일어나므로 적당한 크기(10ms ~ 100ms)로 하는 것이 중요
시스템이 사용자에게 적합한 응답시간을 제공해 주는 대화식 시분할 시스템에 적합

다단계 큐 (Multilevel Queue)

준비 큐를 여러 개의 큐로 분리하여 각각의 큐 사이에 우선순위를 부여하고 독자적인 스케줄링 알고리즘을 적용하는 방식
각 프로세스 형태에 따라 조건에 맞는 큐에 영구적으로 할당
고정형 우선순위 : 시스템 > 대화형 > 대화형 편집 > 일괄처리 > 학생 프로세스
높은 우선순위를 가진 프로세스의 큐들이 비어있지 않으면 다음 우선순위의 큐 실행 불가
응답이 빠름
다수의 준비 큐와 스케줄링 알고리즘으로 추가 오버헤드가 발생
우선순위가 낮은 큐의 프로세스는 무한정 대기하는 기아 상태 발생

다단계 피드백 큐 (Multilevel Feedback Queue)

프로세스들이 큐 사이를 이동 가능하여 새로운 프로세스는 그 특성에 따라 각각 준비 큐에 들어오게 되며, 그 실행 형태에 따라 다른 준비 큐로 이동
다양한 특성의 작업이 혼합된 경우 유용
에이징(Aging) 기법으로 대기 시간이 긴 프로세스를 높은 우선순위 큐로 이동시키거나, CPU 사용 시간이 긴 작업을 우선순위가 낮은 큐로 이동시켜 기아 상태를 막음