현재 포스트는 이후에 습득한 지식으로 인해 내용이 추가, 수정, 삭제될 수 있음
0. 🔖 목차
- 📜 스케줄링 기본 개념
1-1. 개념
1-2. 용어 - 🥇 먼저 온 사람이 임자, 선점 스케줄링
2-1. Priority Scheduling
2-2. Round Robin
2-3. Multilevel-Queue - 🩺 응급환자 먼저, 비선점 스케줄링
3-1. FCFS(First-Come, First-Served)
3-2. SJF(Shortest Job First)
3-3. HRN(Highest Response Ratio Next)
1. 📜 스케줄링 기본 개념
1-1. 개념
컴퓨터 시스템의 자원을 효율적으로 사용하기 위해 프로세스 실행 순서를 결정하는 과정
1-2. 용어
-
프로세스(Process): 프로그램을 실행하는 주체
-
쓰레드(Thread): 프로세스 내에서 실행되는 가장 작은 실행 단위
-
스케줄러(Scheduler): 프로세스가 CPU를 사용할 순서를 결정하는 시스템 컴포넌트
-
디스패처(Dispatcher): 스케줄러의 결정에 따라 프로세스에 CPU를 할당하는 역할
-
컨텍스트 스위칭(Context Switching): CPU가 한 쓰레드에서 다른 쓰레드로 실행 제어권을 넘기는 과정
-
CPU 사용률(Utilization): 전체 시간 중 CPU가 일한 시간의 비율
-
처리량(Throughput): 단위 시간당 처리할 수 있는 작업의 수
-
총 처리 시간(Turnaround Time): 작업이 완료되기까지 걸린 총 시간
-
대기 시간(Waiting Time): 프로세스가 CPU를 할당받기 위해 대기하는 시간
-
응답 시간(Response Time): 대화형 시스템에서 사용자 요청에 대해 첫 번째 응답이 나타나기까지의 시간
-
오버헤드(Overhead): 컨텍스트 스위칭하거나 스케줄링 결정을 내리는 데 소요되는 시간(자원)
-
기아 현상(Starvation): 한 프로세스가 다른 프로세스에 비해 긴 시간 동안 자원을 할당받지 못하는 상황
-
공평성(Fairness): 모든 프로세스가 공평하게 CPU 자원을 할당받는 정도
-
호위 효과(convoy effect): 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들이 기다리며 처리량이 떨어지는 효과
-
I/O Burst: 프로세스가 입력/출력 작업을 수행하는 기간
-
CPU Burst: 프로세스가 CPU를 사용하여 연산 작업을 수행하는 기간
2. 🩺 응급환자 먼저, 선점 스케줄링
현재 CPU를 할당받아 실행중인 프로세스가 있을 때 다른 프로세스가 현재 프로세스를 중단시키고 실행될 수 있는 스케줄링 방법.
장점
- 응답 시간이 짧음
- CPU 사용률이 높음
- 프로세스의 우선순위에 따라 배정하기 때문에 중요한 작업을 빠르게 처리 가능
단점
- 오버헤드 증가
- 기아 현상 발생
에이징
실행되지 못하는 프로세스의 우선순위를 시간이 지남에 따라 높게 조정하여 기아 현상 해결 가능
어디에 쓰이나
실시간 시스템이나 중요한 작업을 우선적으로 처리해야 하는 환경에서 유용하게 사용.
위의 내용은 이후 소개할 모든 선점 스케줄링에 공통으로 해당하는 특징임.
특정 선점 알고리즘이 다른 알고리즘에게 없는 특징이 있으면 "특징"에서 기술
2-1. Priority Scheduling
각 프로세스에 우선순위를 할당하는 스케줄링 알고리즘.
할당된 우선순위를 기반으로 CPU의 사용 순서가 결정됨.
2-2. Round Robin
시분할 시스템에서 널리 사용되는 선점형 스케줄링 알고리즘.
각 프로세스에 동일한 크기의 시간 할당량(타임 퀀텀)을 부여하고, 할당된 시간 동안 프로세스를 실행한 후 다음 프로세스로 전환.
할당된 시간을 다 쓴 프로세스는 준비큐의 맨 뒤로 밀려나면서 모든 프로세스가 공평한 CPU 시간을 할당받게 됨.
특징
- 공평성이 높음
- 타임 퀀텀이
- 짧으면: 오버헤드가 높음
- 길면: FCFS와 유사한 비선점 스케줄링으로 변해 응답 시간이 길어짐
2-3. Multilevel-Queue
프로세스를 여러 개의 큐로 분류하여 각각 다른 스케줄링 알고리즘을 적용할 수 있게 하는 선점형 스케줄링 알고리즘
메모리 크기, 우선순위, 유형 등 프로세스의 특성에 따라 하나의 큐에 영구적으로 할당됨.
3. 🥇 먼저 온 사람이 임자, 비선점 스케줄링
CPU가 프로세스에 할당되면 CPU 사용을 완전히 마칠 때까지, 즉 프로세스가 종료되거나 입출력 작업 등을 기다리는 상태가 될 때까지 다른 프로세스가 CPU를 빼앗을 수 없는 스케줄링 방법
장점
- 오버헤드가 낮음
- 프로세스 하나의 완료 시간을 예측하기 용이함
- 공평성이 높음
단점
- 응답 시간이 느림
- 처리율이 낮음(convoy effect)
어디에 쓰이나
응답 시간을 정확히 예측해야하고 오버헤드를 최소화해야 하는 환경. 일괄처리 시스템에 적합
위의 내용은 이후 소개할 모든 비선점 스케줄링에 공통으로 해당하는 특징임.
특정 비선점 알고리즘이 다른 알고리즘에게 없는 특징이 있으면 "특징"에서 기술
3-1. FCFS(First-Come, First-Served)
준비 큐에 도착한 순서대로 프로세스에 CPU를 할당하는 비선점 스케줄링 알고리즘.
한 프로세스가 CPU를 할당받으면, 해당 프로세스가 종료되거나 입출력 작업을 위해 대기 상태가 될 때까지 CPU를 점유.
3-2. SJF(Shortest Job First)
프로세스가 준비 큐에 도착하면 CPU 버스트 시간을 기준으로 정렬하고, 가장 짧은 CPU 버스트 시간을 가진 프로세스부터 CPU에 할당하는 선점, 비선점 스케줄링 알고리즘
선점으로 구현하는 경우에는 SRTF(Shortest Remaining Time First)이라고 부른다.
SRTF는 현재 실행되고 있는 프로세스의 잔여시간을 기반으로 프로세스를 선점할지 안할지를 결정한다.
즉, CPU Burst가 5인 프로세스가 2만큼 작업을 하여 3만큼의 잔여시간이 남았을 때 2의 프로세스가 온다면 자리를 뺏긴다.
특징
- 평균 대기 시간과 평균 응답 시간을 최소화하는 최적의 스케줄링 방식
- 프로세스의 CPU 버스트 시간을 미리 알아야 함, 추정값을 사용하거나 과거의 실행 패턴을 기반으로 예측
- 기아 현상이 일어날 수 있음
3-3. HRN(Highest Response Ratio Next)
각 프로세스에 대해 응답률(Response Ratio)을 계산하고, 가장 높은 응답률을 가진 프로세스에 CPU를 할당하는 비선점형 스케줄링 알고리즘
응답률 은 아래와 같이 계산됨
여기서 와 는 각각 대기 시간, CPU Burst이다.
특징
- SJF에서 일어나는 기아 현상을 에이징을 통해 해결함
- 수식에서 알 수 있듯, 똑같은 대기시간을 가졌을 때 작업 시간이 제일 짧은 프로세스의 응답률이 가장 높음
