기본 개념
단일 CPU 코어 시스템에서는 한 순간에 오직 하나의 프로세스만 실행될 수 있음.
나머지 프로세스들은 CPU 코어가 가용 상태가 되어 다시 스케줄될 수 있을 때까지 기다려야 함.
다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 것.
하나의 프로세스는 보통 어떤 입출력 요청이 완료되기를 기다려야 할 때까지 실행됨.
단순한 컴퓨터 시스템에서는 프로세스가 입출력을 기다리는 동안 CPU가 유휴 상태가 됨.
이 대기 시간 동안 CPU는 유용한 작업을 수행하지 못함.
다중 프로그래밍에서는 여러 프로세스를 메모리 안에 유지하여 이러한 대기 시간을 생산적으로 활용함.
어떤 프로세스가 대기해야 할 경우 운영체제는 그 프로세스로부터 CPU를 회수하고 다른 프로세스에 할당함.
이 패턴은 계속 반복됨.
하나의 프로세스가 대기해야 할 때마다 다른 프로세스가 CPU 사용을 양도받을 수 있음.
다중 코어 시스템에서는 이러한 개념이 시스템의 모든 처리 코어를 바쁘게 유지하는 방식으로 확장됨.
CPU 스케줄링은 운영체제의 기본적인 기능.
거의 모든 컴퓨터 자원은 사용되기 전에 스케줄됨.
CPU는 가장 중요한 컴퓨터 자원 중 하나.
따라서 CPU 스케줄링은 운영체제 설계의 핵심이 되는 부분.
CPU-I/O 버스트 사이클
CPU 스케줄링의 성공은 프로세스 실행 특성에 대한 관찰에서 출발함.
프로세스 실행은 CPU 실행과 입출력 대기의 사이클로 구성됨.
프로세스는 CPU 버스트와 입출력 버스트 사이를 반복적으로 이동함.
CPU 버스트는 프로세스가 CPU 코어에서 명령어를 실행하는 구간.
입출력 버스트는 프로세스가 입출력 작업의 완료를 기다리는 구간.
프로세스 실행은 보통 CPU 버스트로 시작됨.
그 뒤 입출력 버스트가 발생하고, 다시 CPU 버스트가 발생하며, 다시 입출력 버스트가 이어지는 식으로 진행됨.
마지막 CPU 버스트는 또 다른 입출력 버스트가 아니라 실행 종료를 위한 시스템 요청과 함께 끝남.
CPU 버스트의 지속 시간은 프로세스마다 다르고 컴퓨터마다 차이가 있음.
그러나 일반적으로 짧은 CPU 버스트가 많이 존재하고, 긴 CPU 버스트는 적게 존재하는 경향.
이러한 분포는 지수형 또는 초지수형 분포와 비슷한 형태로 나타남.
입출력 중심 프로그램은 보통 짧은 CPU 버스트를 많이 가짐.
CPU 중심 프로그램은 긴 CPU 버스트를 많이 가질 수 있음.
입출력 중심 프로세스는 CPU를 오래 사용하지 않고 빠르게 입출력을 요청하는 경향이 있음.
CPU 중심 프로세스는 계산을 오래 수행하므로 CPU를 긴 시간 동안 필요로 하는 경향이 있음.
이러한 CPU 버스트 분포는 CPU 스케줄링 알고리즘을 구현할 때 매우 중요한 기준이 됨.
스케줄러는 입출력 중심 프로세스와 CPU 중심 프로세스의 특성을 고려하여 CPU를 효율적으로 배분해야 함.
CPU 스케줄러
CPU가 유휴 상태가 될 때마다 운영체제는 준비 큐에 있는 프로세스 중 하나를 선택해야 함.
이 선택 절차는 CPU 스케줄러에 의해 수행됨.
CPU 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중 하나를 선택하여 CPU를 할당함.
준비 큐는 반드시 선입선출 방식의 큐일 필요는 없음.
준비 큐는 선입선출 큐, 우선순위 큐, 트리, 단순 연결 리스트 등으로 구현될 수 있음.
개념적으로 준비 큐에 있는 모든 프로세스는 CPU에서 실행될 기회를 기다리는 상태.
준비 큐에 있는 레코드들은 일반적으로 각 프로세스의 프로세스 제어 블록을 가리키는 구조.
CPU 스케줄러는 준비 큐 안의 프로세스들 중 다음에 CPU를 받을 대상을 결정함.
CPU 스케줄러는 매우 자주 실행될 수 있음.
따라서 스케줄링 결정은 가능한 한 빠르게 이루어져야 함.
스케줄러의 결정 시간이 길면 운영체제 오버헤드가 커질 수 있음.
선점 및 비선점 스케줄링
CPU 스케줄링 결정은 네 가지 상황에서 발생할 수 있음.
첫 번째는 프로세스가 실행 상태에서 대기 상태로 전환될 때.
예를 들어 입출력 요청을 하거나 자식 프로세스 종료를 기다리기 위해 wait 시스템 콜을 호출하는 경우.
두 번째는 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때.
예를 들어 인터럽트가 발생하거나 시간 할당량이 만료되는 경우.
세 번째는 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때.
예를 들어 입출력이 완료되어 다시 실행 준비 상태가 되는 경우.
네 번째는 프로세스가 종료될 때.
첫 번째와 네 번째 상황에서는 스케줄링 측면에서 선택의 여지가 없음.
실행 중인 프로세스가 CPU를 더 이상 사용할 수 없으므로
준비 큐에 프로세스가 있다면 새로운 프로세스를 반드시 선택해야 함.
두 번째와 세 번째 상황에서는 선택의 여지가 있음.
현재 실행 중인 프로세스를 계속 실행할 수도 있고, 다른 프로세스에 CPU를 할당할 수도 있음.
스케줄링이 첫 번째와 네 번째 상황에서만 발생하면 비선점 스케줄링 또는 협조적 스케줄링이라고 함.
비선점 스케줄링에서는 CPU가 한 프로세스에 할당되면 그 프로세스가 종료하거나 대기 상태로 전환하여 CPU를 방출할 때까지 CPU를 점유함.
그 외의 상황에서도 스케줄링이 발생하면 선점 스케줄링이라고 함.
선점 스케줄링에서는 운영체제가 실행 중인 프로세스로부터 CPU를 빼앗아 다른 프로세스에 할당할 수 있음.
Windows, macOS, Linux, UNIX를 포함한 대부분의 최신 운영체제는 선점 스케줄링 알고리즘을 사용함.
선점 스케줄링은 대화형 시스템에서 응답성을 높일 수 있음.
그러나 데이터가 여러 프로세스에 의해 공유될 때 경쟁 조건을 초래할 수 있음.
한 프로세스가 공유 자료를 갱신하는 동안 선점되고,
다른 프로세스가 그 자료를 읽거나 수정하면 데이터 일관성이 깨질 수 있음.
이 문제는 동기화와 관련된 중요한 주제.
선점은 운영체제 커널 설계에도 영향을 줌.
프로세스가 시스템 콜을 처리하는 동안 커널 내부 자료구조를 수정할 수 있음.
입출력 큐 같은 중요한 커널 자료구조를 변경하는 도중 선점이 발생하면 커널 자료구조가 불일치 상태가 될 수 있음.
비선점형 커널은 시스템 콜이 완료되거나 프로세스가 입출력 완료를 기다리며 봉쇄될 때까지 문맥 교환을 하지 않음.
이 방식은 커널 자료구조가 불일치한 상태에서 선점되지 않으므로 커널 설계를 단순하게 만듦.
그러나 비선점형 커널은 정해진 시간 안에 태스크가 실행되어야 하는 실시간 컴퓨팅을 지원하기에는 적합하지 않음.
선점형 커널은 커널 모드에서 실행 중인 프로세스도 선점될 수 있는 구조.
이 경우 공유 커널 데이터 구조에 접근할 때 경쟁 조건을 방지하기 위해 mutex 락 같은 동기화 기법이 필요함.
대부분의 최신 운영체제는 커널 모드에서도 완전히 선점될 수 있는 구조를 사용함.
인터럽트는 어느 시점에서든 발생할 수 있음.
운영체제는 인터럽트를 항상 무시할 수 없음.
입출력 손실이나 출력 충돌을 막기 위해 인터럽트를 받아들여야 함.
따라서 인터럽트에 영향을 받는 코드 부분은 동시에 접근되지 않도록 보호되어야 함.
일부 코드 구간에서는 진입 시 인터럽트를 불능화하고, 출구에서 다시 가능화하는 방식이 사용될 수 있음.
다만 인터럽트 불능화는 자주 발생해서는 안 됨.
인터럽트 불능화는 매우 짧은 명령어 구간에만 사용되어야 함.
디스패처
디스패처는 CPU 스케줄러가 선택한 프로세스에 CPU 코어의 제어를 넘겨주는 모듈.
디스패처는 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일을 수행함.
또한 사용자 모드로 전환하는 일도 담당함.
선택된 프로세스가 다시 시작될 수 있도록 사용자 프로그램의 적절한 위치로 이동하는 일도 포함함.
디스패처는 모든 프로세스 문맥 교환 시 호출됨.
따라서 가능한 한 빠르게 수행되어야 함.
디스패처가 하나의 프로세스를 정지시키고 다른 프로세스의 수행을 시작하는 데 걸리는 시간을 디스패치 지연이라고 함.
디스패치 지연이 길면 문맥 교환 오버헤드가 커짐.
그 결과 실제 유용한 작업에 쓰이는 CPU 시간이 줄어듦.
Linux에서는 vmstat 명령을 사용하여 시스템 차원의 문맥 교환 횟수를 확인할 수 있음.
vmstat 명령은 일정 시간 간격으로 문맥 교환 횟수와 CPU 사용 상태 같은 정보를 보여줌.
첫 번째 줄은 시스템 부팅 이후의 평균값을 보여줄 수 있음.
이후 줄은 지정된 간격 동안 발생한 문맥 교환 횟수를 보여줄 수 있음.
특정 프로세스의 문맥 교환 횟수는 /proc 파일 시스템을 통해 확인할 수 있음.
특정 PID의 status 파일에는 voluntary context switches와 nonvoluntary context switches가 표시될 수 있음.
자발적 문맥 교환은 프로세스가 입출력 같은 자원을 기다리기 위해 CPU를 스스로 포기할 때 발생함.
비자발적 문맥 교환은 타임 슬라이스 만료나 더 높은 우선순위 프로세스에 의해 CPU를 빼앗길 때 발생함.
스케줄링 기준
서로 다른 CPU 스케줄링 알고리즘은 서로 다른 특성을 가짐.
어떤 알고리즘은 특정 종류의 프로세스를 다른 종류보다 더 선호할 수 있음.
특정 상황에서 어떤 알고리즘을 선택하려면 여러 알고리즘의 특성을 비교해야 함.
CPU 스케줄링 알고리즘을 비교하기 위한 기준에는 CPU 이용률, 처리량, 총처리 시간, 대기 시간, 응답 시간이 있음.
CPU 이용률은 CPU를 가능한 한 바쁘게 유지하는 정도.
개념적으로 CPU 이용률은 0%에서 100%까지 가능함.
실제 시스템에서는 부하가 적은 시스템의 경우 40% 정도, 부하가 큰 시스템의 경우 90% 정도까지 나타날 수 있음.
Linux, macOS, UNIX 시스템에서는 top 명령을 사용하여 CPU 이용률을 확인할 수 있음.
처리량은 단위 시간당 완료된 프로세스의 수.
CPU가 프로세스를 수행하느라 바쁘다면 작업이 진행되고 있는 것.
이 작업량을 측정하는 한 방법이 처리량.
긴 프로세스의 경우 처리량은 몇 초 동안 하나의 프로세스가 될 수 있음.
짧은 트랜잭션의 경우 처리량은 초당 수십 개의 프로세스가 될 수도 있음.
총처리 시간은 특정 프로세스의 제출 시각부터 완료 시각까지의 전체 시간.
총처리 시간에는 준비 큐에서 대기한 시간, CPU에서 실행한 시간, 입출력 시간이 포함됨.
사용자 입장에서는 자신이 제출한 작업이 완료되기까지 걸린 시간이 중요한 기준이 될 수 있음.
대기 시간은 프로세스가 준비 큐에서 대기하면서 보낸 시간의 총합.
CPU 스케줄링 알고리즘은 프로세스가 실제로 CPU에서 실행하는 시간이나 입출력하는 시간 자체를 직접 바꾸지는 않음.
스케줄링 알고리즘은 준비 큐에서 기다리는 시간에 주로 영향을 줌.
응답 시간은 하나의 요구를 제출한 뒤 첫 번째 응답이 나오기까지 걸리는 시간.
대화형 시스템에서는 총처리 시간보다 응답 시간이 더 중요한 기준이 될 수 있음.
응답 시간은 응답이 시작되기까지 걸리는 시간이지, 그 응답을 모두 출력하는 데 걸리는 시간은 아님.
일반적으로 CPU 이용률과 처리량은 최대화하는 것이 바람직함.
총처리 시간, 대기 시간, 응답 시간은 최소화하는 것이 바람직함.
많은 경우 평균값을 최적화하려고 하지만, 항상 평균만 중요한 것은 아님.
어떤 경우에는 최대 응답 시간을 줄이는 것이 더 중요할 수 있음.
대화형 시스템에서는 응답 시간의 평균뿐 아니라 응답 시간의 변동을 줄이는 것도 중요함.
사용자에게 예측 가능한 응답성을 제공하려면 분산이 작은 스케줄링이 더 적절할 수 있음.
스케줄링 알고리즘
CPU 스케줄링 알고리즘은 준비 큐에서 어떤 프로세스에 CPU를 할당할 것인지 결정하는 방법.
대표적인 알고리즘에는
선입 선처리, 최단 작업 우선, 라운드 로빈, 우선순위, 다단계 큐, 다단계 피드백 큐 스케줄링이 있음.
각 알고리즘은 대기 시간, 총처리 시간, 응답 시간, 공정성, 구현 복잡도 면에서 서로 다른 특징을 가짐.
여기서 설명하는 알고리즘들은 하나의 처리 코어만 존재한다고 가정하고 설명됨.
다중 처리기 스케줄링은 뒤에서 별도로 설명되는 내용.
선입 선처리 스케줄링
선입 선처리 스케줄링은 FCFS 스케줄링이라고 함.
FCFS는 First-Come, First-Served의 약어.
가장 먼저 준비 큐에 도착한 프로세스가 가장 먼저 CPU를 할당받는 방식.
준비 큐는 보통 FIFO 큐로 관리됨.
새로운 프로세스가 준비 큐에 들어오면 큐의 끝에 삽입됨.
CPU가 가용 상태가 되면 큐의 앞에 있는 프로세스가 제거되어 CPU를 할당받음.
FCFS 알고리즘은 이해하기 쉽고 구현도 단순함.
그러나 평균 대기 시간이 길어질 수 있음.
CPU 버스트가 긴 프로세스가 먼저 도착하면 뒤에 있는 짧은 프로세스들이 오래 기다릴 수 있음.
프로세스의 CPU 버스트 시간이 크게 다르면 FCFS에서 평균 대기 시간도 크게 변할 수 있음.
짧은 프로세스들이 긴 프로세스 하나가 CPU를 양도하기를 기다리는 현상을 호위 효과라고 함.
호위 효과는 CPU 장치와 입출력 장치의 이용률을 떨어뜨릴 수 있음.
CPU 중심 프로세스가 CPU를 오래 점유하는 동안 입출력 중심 프로세스들은 준비 큐에서 기다림.
그 사이 입출력 장치는 유휴 상태가 될 수 있음.
CPU 중심 프로세스가 입출력 장치로 이동하면
입출력 중심 프로세스들이 짧은 CPU 버스트를 빠르게 끝내고 다시 입출력 큐로 이동함.
이후 CPU는 유휴 상태가 되고, 다시 CPU 중심 프로세스가 CPU를 오래 점유하는 상황이 반복될 수 있음.
FCFS 스케줄링은 비선점형 알고리즘.
한 프로세스에 CPU가 할당되면 그 프로세스가 종료되거나 입출력 요청으로 CPU를 방출할 때까지 계속 실행됨.
이 방식은 대화형 시스템에서 문제가 될 수 있음.
대화형 시스템에서는 각 프로세스가 규칙적인 간격으로 CPU를 얻는 것이 중요하기 때문.
한 프로세스가 지나치게 오랫동안 CPU를 점유하게 허용하면 사용자 응답성이 떨어질 수 있음.
최단 작업 우선 스케줄링
최단 작업 우선 스케줄링은 SJF 스케줄링이라고 함.
SJF는 Shortest-Job-First의 약어.
이 알고리즘은 각 프로세스에 다음 CPU 버스트 길이를 연결함.
CPU가 사용 가능해지면 가장 짧은 다음 CPU 버스트를 가진 프로세스에 CPU를 할당함.
두 프로세스의 다음 CPU 버스트 길이가 같다면 FCFS 방식을 적용할 수 있음.
정확히 말하면 전체 작업 길이가 아니라
다음 CPU 버스트 길이를 기준으로 하므로 최단 다음 CPU 버스트 알고리즘이라고 부르는 것이 더 정확함.
그러나 일반적으로 이 방식은 SJF라고 부름.
SJF 스케줄링은 주어진 프로세스 집합에 대해 평균 대기 시간을 최소화하는 최적 알고리즘.
짧은 프로세스를 긴 프로세스 앞에 배치하면 짧은 프로세스의 대기 시간이 크게 줄어듦.
긴 프로세스의 대기 시간은 늘어나지만, 줄어드는 대기 시간의 효과가 더 크기 때문에 평균 대기 시간이 감소함.
SJF의 문제는 다음 CPU 버스트 길이를 정확히 알 수 없다는 점.
운영체제는 미래의 CPU 버스트 길이를 직접 알 수 없음.
따라서 다음 CPU 버스트 길이를 예측하는 방식이 필요함.
일반적으로 다음 CPU 버스트는 이전 CPU 버스트 길이들의 지수 평균으로 예측할 수 있음.
예측 공식은 최근 CPU 버스트와 과거 예측값에 가중치를 주어 다음 값을 계산하는 방식.
최근 CPU 버스트의 실제 길이를 t라고 하고, 다음 CPU 버스트에 대한 예측값을 j라고 둘 수 있음.
새로운 예측값은 최근 실제 CPU 버스트와 이전 예측값을 가중 평균하여 계산함.
가중치 a는 0과 1 사이의 값.
a가 0이면 최근 기록은 예측에 영향을 주지 않음.
a가 1이면 가장 최근 CPU 버스트만 예측에 반영됨.
a가 1/2이면 최근 기록과 과거 기록이 같은 비중을 가짐.
SJF는 비선점형 또는 선점형으로 구현될 수 있음.
비선점형 SJF에서는 한 프로세스가 CPU를 얻으면 자신의 CPU 버스트를 끝낼 때까지 계속 실행됨.
선점형 SJF에서는 새로운 프로세스가 도착했을 때
그 프로세스의 CPU 버스트가 현재 실행 중인 프로세스의 남은 시간보다 짧으면 현재 프로세스를 선점함.
선점형 SJF는 최단 잔여 시간 우선 스케줄링이라고도 함.
선점형 SJF는 평균 대기 시간을 더 줄일 수 있음.
그러나 문맥 교환이 더 자주 발생할 수 있음.
또한 짧은 작업이 계속 들어오면 긴 작업이 오래 기다릴 수 있음.
라운드 로빈 스케줄링
라운드 로빈 스케줄링은 RR 스케줄링이라고 함.
RR은 Round-Robin의 약어.
라운드 로빈은 FCFS와 비슷하지만 프로세스 사이를 옮겨 다닐 수 있도록 선점 기능이 추가된 구조.
시간 할당량 또는 타임 슬라이스라고 부르는 작은 시간 단위를 정의함.
시간 할당량은 일반적으로 10밀리초에서 100밀리초 사이.
준비 큐는 원형 큐처럼 동작함.
CPU 스케줄러는 준비 큐를 돌면서 한 번에 한 프로세스에 하나의 시간 할당량 동안 CPU를 할당함.
새로운 프로세스는 준비 큐의 꼬리에 추가됨.
CPU 스케줄러는 준비 큐의 첫 번째 프로세스를 선택함.
그 뒤 한 번의 시간 할당량 이후 인터럽트를 발생시키도록 타이머를 설정한 뒤 프로세스를 디스패치함.
프로세스의 CPU 버스트가 시간 할당량보다 짧으면 프로세스는 시간 할당량이 끝나기 전에 CPU를 자발적으로 방출함.
이 경우 스케줄러는 준비 큐의 다음 프로세스로 진행함.
현재 실행 중인 프로세스의 CPU 버스트가 시간 할당량보다 길면 타이머가 만료되어 인터럽트가 발생함.
문맥 교환이 일어나고 실행 중이던 프로세스는 준비 큐의 꼬리에 다시 삽입됨.
그 뒤 스케줄러는 준비 큐의 다음 프로세스를 선택함.
RR 알고리즘에서는 유일하게 실행 가능한 프로세스가 아닌 이상 한 프로세스가 연속으로 두 번 이상의 시간 할당량을 받을 수 없음.
CPU 버스트가 시간 할당량을 초과하면 프로세스는 선점되고 준비 큐로 되돌아감.
따라서 RR 알고리즘은 선점형 스케줄링 알고리즘.
준비 큐에 n개의 프로세스가 있고 시간 할당량이 q라면, 각 프로세스는 CPU 시간의 1/n을 최대 q 시간 단위씩 나누어 받음.
각 프로세스는 다음 시간 할당량을 받을 때까지 최대 (n-1)q 시간 이상 기다리지 않음.
RR 알고리즘의 성능은 시간 할당량의 크기에 크게 영향을 받음.
시간 할당량이 매우 크면 RR은 FCFS와 비슷하게 동작함.
시간 할당량이 매우 작으면 많은 문맥 교환이 발생함.
문맥 교환이 많아지면 오버헤드가 증가하고 실제 프로세스 실행 시간이 줄어듦.
따라서 시간 할당량은 문맥 교환 시간보다 충분히 커야 함.
문맥 교환 시간이 시간 할당량의 큰 비율을 차지하면 CPU 시간의 상당 부분이 문맥 교환에 사용됨.
대부분의 현대 운영체제는 10밀리초에서 100밀리초 범위의 시간 할당량을 사용함.
문맥 교환 시간은 보통 마이크로초 단위이므로 시간 할당량에 비해 작은 부분을 차지함.
총처리 시간도 시간 할당량의 크기에 영향을 받음.
시간 할당량을 늘린다고 해서 평균 총처리 시간이 항상 개선되는 것은 아님.
일반적으로 대부분의 프로세스가 하나의 시간 할당량 안에 다음 CPU 버스트를 끝낼 수 있으면
평균 총처리 시간이 좋아질 수 있음.
RR은 모든 프로세스가 주기적으로 CPU를 받을 수 있으므로 대화형 시스템에 적합함.
그러나 평균 총처리 시간은 SJF보다 나쁠 수 있음.
우선순위 스케줄링
우선순위 스케줄링은 각 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스에 CPU를 할당하는 방식.
SJF도 다음 CPU 버스트가 짧을수록 높은 우선순위를 갖는 특수한 우선순위 스케줄링으로 볼 수 있음.
우선순위는 숫자로 표현될 수 있음.
어떤 시스템에서는 작은 숫자가 높은 우선순위를 의미함.
어떤 시스템에서는 큰 숫자가 높은 우선순위를 의미할 수 있음.
우선순위는 내부적으로 정의될 수도 있고 외부적으로 정의될 수도 있음.
내부 우선순위는 시간 제한, 메모리 요구량, 열린 파일 수, 평균 입출력 버스트와 평균 CPU 버스트의 비율 같은
측정 가능한 값으로 계산될 수 있음.
외부 우선순위는
프로세스의 중요성, 컴퓨터 사용 비용, 작업을 후원하는 부서, 정책적 요인 같은 운영체제 외부 기준에 의해 결정될 수 있음.
우선순위 스케줄링은 선점형 또는 비선점형으로 구현될 수 있음.
선점형 우선순위 스케줄링에서는 새로 도착한 프로세스의 우선순위가 현재 실행 중인 프로세스보다 높으면 CPU를 선점함.
비선점형 우선순위 스케줄링에서는 새로 도착한 프로세스를 준비 큐의 적절한 위치에 넣고
현재 프로세스가 CPU를 내놓을 때까지 기다림.
우선순위 스케줄링의 주요 문제는 무한 봉쇄 또는 기아 상태.
기아 상태는 실행 준비가 되어 있지만 CPU를 받지 못하고 계속 기다리는 상태.
높은 우선순위 프로세스들이 계속 들어오면 낮은 우선순위 프로세스는 무기한으로 연기될 수 있음.
기아 상태를 해결하는 대표적인 방법은 노화.
노화는 오랫동안 대기하는 프로세스의 우선순위를 점진적으로 높이는 방식.
시간이 지날수록 낮은 우선순위 프로세스의 우선순위가 올라가면 결국 CPU를 할당받을 수 있음.
우선순위 스케줄링은 라운드 로빈과 결합될 수 있음.
이 방식에서는 가장 높은 우선순위 큐의 프로세스가 먼저 실행됨.
우선순위가 같은 프로세스들 사이에서는 라운드 로빈 방식으로 CPU를 나누어 사용함.
다단계 큐 스케줄링
다단계 큐 스케줄링은 준비 큐를 여러 개의 개별 큐로 나누어 관리하는 방식.
우선순위마다 별도의 큐를 두면 우선순위가 가장 높은 프로세스를 찾기 쉬움.
스케줄러는 가장 높은 우선순위를 가진 비어 있지 않은 큐에서 프로세스를 선택함.
우선순위가 같은 큐 안에 여러 프로세스가 있으면 라운드 로빈 방식으로 실행할 수 있음.
다단계 큐 스케줄링은 프로세스 유형에 따라 여러 개의 큐를 둘 수도 있음.
예를 들어 전경 프로세스와 배경 프로세스를 별도의 큐로 나눌 수 있음.
전경 프로세스는 사용자와 직접 상호작용하는 대화형 프로세스.
배경 프로세스는 일괄 처리 성격을 가진 프로세스.
전경 프로세스와 배경 프로세스는 응답 시간 요구 사항이 다를 수 있음.
따라서 서로 다른 스케줄링 알고리즘을 사용할 수 있음.
전경 큐는 응답성을 위해 라운드 로빈 스케줄링을 사용할 수 있음.
배경 큐는 선입 선처리 스케줄링을 사용할 수 있음.
큐들 사이에도 스케줄링이 필요함.
일반적으로 큐 사이의 스케줄링은 고정 우선순위 선점 스케줄링으로 구현될 수 있음.
예를 들어 실시간 큐는 대화형 큐보다 절대적으로 높은 우선순위를 가질 수 있음.
대화형 큐는 배치 큐보다 높은 우선순위를 가질 수 있음.
실시간 프로세스, 시스템 프로세스, 대화형 프로세스, 배치 프로세스 같은 여러 큐를 둘 수 있음.
각 큐는 낮은 우선순위 큐보다 절대적인 우선순위를 가질 수 있음.
높은 우선순위 큐가 비어 있지 않으면 낮은 우선순위 큐의 프로세스는 실행될 수 없음.
배치 프로세스가 실행 중이더라도 대화형 프로세스가 준비 큐에 들어오면 배치 프로세스는 선점될 수 있음.
다른 방식으로는 큐들 사이에 CPU 시간을 나누어 주는 방법이 있음.
예를 들어 전경 큐에는 CPU 시간의 80%, 배경 큐에는 CPU 시간의 20%를 할당할 수 있음.
각 큐는 자신에게 주어진 CPU 시간 안에서 자체 스케줄링 알고리즘을 사용할 수 있음.
다단계 피드백 큐 스케줄링
다단계 큐 스케줄링에서는 프로세스가 시스템 진입 시 하나의 큐에 영구적으로 할당되는 경우가 많음.
이 방식은 스케줄링 오버헤드가 적지만 융통성이 부족함.
다단계 피드백 큐 스케줄링에서는 프로세스가 큐 사이를 이동할 수 있음.
이 알고리즘의 기본 아이디어는 프로세스들을 CPU 버스트 성격에 따라 구분하는 것.
어떤 프로세스가 CPU 시간을 너무 많이 사용하면 낮은 우선순위 큐로 이동됨.
입출력 중심 프로세스와 대화형 프로세스는 보통 짧은 CPU 버스트를 가지므로 높은 우선순위 큐에 머물 수 있음.
낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동할 수 있음.
이러한 방식은 노화의 한 형태로, 기아 상태를 방지함.
예를 들어 세 개의 큐를 가진 다단계 피드백 큐 스케줄러를 생각할 수 있음.
스케줄러는 먼저 큐 0의 모든 프로세스를 실행함.
큐 0이 비어 있을 때만 큐 1의 프로세스를 실행함.
큐 0과 큐 1이 모두 비어 있을 때만 큐 2의 프로세스를 실행함.
큐 1에 프로세스가 도착하면 큐 2에서 실행 중인 프로세스를 선점할 수 있음.
큐 0에 프로세스가 도착하면 큐 1에서 실행 중인 프로세스도 선점될 수 있음.
새로 들어오는 프로세스는 큐 0에 삽입될 수 있음.
큐 0의 프로세스는 짧은 시간 할당량을 받음.
그 시간 안에 끝나지 않으면 큐 1의 꼬리로 이동됨.
큐 1의 프로세스는 큐 0보다 긴 시간 할당량을 받을 수 있음.
큐 1에서도 완료되지 않으면 큐 2로 이동됨.
큐 2의 프로세스는 낮은 우선순위로 FCFS 방식에 의해 실행될 수 있음.
이 구조는 짧은 CPU 버스트를 가진 프로세스에 높은 우선순위를 부여함.
CPU 버스트가 짧은 프로세스는 빠르게 CPU를 할당받고 CPU 버스트를 끝낸 뒤 입출력 버스트로 이동함.
긴 프로세스는 자동으로 낮은 우선순위 큐로 내려감.
그 결과 긴 프로세스는 높은 우선순위 큐가 사용하지 않는 CPU 시간을 활용하게 됨.
다단계 피드백 큐 스케줄러는 여러 매개변수에 의해 정의됨.
필요한 큐의 개수를 정해야 함.
각 큐를 위한 스케줄링 알고리즘을 정해야 함.
프로세스를 높은 우선순위 큐로 올려 주는 시기를 결정해야 함.
프로세스를 낮은 우선순위 큐로 강등시키는 시기도 결정해야 함.
새 프로세스가 서비스를 필요로 할 때 어느 큐에 들어갈지도 결정해야 함.
다단계 피드백 큐는 가장 일반적인 CPU 스케줄링 알고리즘.
특정 시스템의 요구에 맞게 구성할 수 있다는 장점이 있음.
그러나 좋은 스케줄러로 동작하게 하려면 모든 매개변수의 값을 적절하게 정해야 함.
따라서 다단계 피드백 큐는 가장 복잡한 알고리즘이기도 함.
스레드 스케줄링
대부분의 최신 운영체제에서 스케줄되는 대상은 프로세스가 아니라 커널 수준 스레드.
사용자 수준 스레드는 스레드 라이브러리에 의해 관리됨.
커널은 사용자 수준 스레드의 존재를 직접 알지 못할 수 있음.
사용자 수준 스레드가 CPU에서 실행되려면 궁극적으로 커널 수준 스레드에 사상되어야 함.
다대다 모델에서는 사용자 수준 스레드가 LWP를 통해 간접적으로 커널 수준 스레드와 연결될 수 있음.
스레드 스케줄링에서는 사용자 수준에서 어떤 스레드를 실행할지 결정하는 문제와
커널 수준에서 어떤 커널 스레드를 CPU에 배정할지 결정하는 문제가 구분됨.
경쟁 범위
경쟁 범위는 스레드가 CPU를 얻기 위해 누구와 경쟁하는지를 나타내는 개념.
다대일 모델과 다대다 모델을 구현하는 시스템에서는
스레드 라이브러리가 사용자 수준 스레드를 사용 가능한 LWP에 스케줄함.
이때 같은 프로세스 안의 스레드들 사이에서 CPU 경쟁이 일어남.
이 방식을 프로세스 경쟁 범위라고 함.
프로세스 경쟁 범위는 PCS라고 하며, Process-Contention Scope의 약어.
PCS에서는 같은 프로세스에 속한 스레드들끼리 경쟁함.
커널 수준에서 실제 CPU에 어떤 커널 스레드를 배정할지는 커널이 결정함.
이때 시스템 전체의 스레드들이 CPU를 얻기 위해 경쟁함.
이 방식을 시스템 경쟁 범위라고 함.
시스템 경쟁 범위는 SCS라고 하며, System-Contention Scope의 약어.
SCS에서는 시스템 전체의 커널 스레드들이 CPU를 얻기 위해 경쟁함.
PCS는 일반적으로 우선순위에 따라 수행됨.
스레드 라이브러리는 같은 프로세스 안의 사용자 스레드 중 더 높은 우선순위의 스레드를 LWP에 배정할 수 있음.
하지만 PCS 방식에서는 같은 프로세스 안에서만 경쟁이 이루어짐.
다대다 모델에서는 사용자 스레드 라이브러리 수준에서 PCS가 발생하고, 커널 수준에서 SCS가 발생할 수 있음.
일대일 모델을 사용하는 시스템에서는 각 사용자 스레드가 하나의 커널 스레드에 대응됨.
따라서 Linux와 Windows 같은 일대일 모델 시스템에서는 보통 SCS만 사용됨.
Pthread 스케줄링
POSIX Pthreads는 스레드 생성뿐 아니라 스레드 스케줄링 속성을 지정할 수 있는 기능도 제공함.
Pthreads에서는 경쟁 범위를 PTHREAD_SCOPE_PROCESS 또는
PTHREAD_SCOPE_SYSTEM으로 설정할 수 있음.
PTHREAD_SCOPE_PROCESS는 프로세스 경쟁 범위를 의미함.
PTHREAD_SCOPE_SYSTEM은 시스템 경쟁 범위를 의미함.
pthread_attr_setscope 함수는 스레드 속성 객체에 경쟁 범위를 설정하는 데 사용됨.
pthread_attr_getscope 함수는 속성 객체에 설정된 경쟁 범위를 확인하는 데 사용됨.
스레드를 만들기 전에 pthread_attr_init 함수로 속성 객체를 초기화할 수 있음.
이후 경쟁 범위를 설정하고 pthread_create 함수에 속성 객체를 전달하면 해당 속성을 가진 스레드를 만들 수 있음.
운영체제가 지정한 경쟁 범위를 지원하지 않으면 속성 설정이나 스레드 생성이 실패할 수 있음.
Linux와 macOS처럼 일대일 모델을 사용하는 시스템은 일반적으로 PTHREAD_SCOPE_SYSTEM을 사용함.
일부 시스템에서는 PTHREAD_SCOPE_PROCESS를 지원하지 않을 수 있음.
Pthreads API는 스케줄링 범위의 설정을 허용하지만, 실제 지원 여부는 운영체제 구현에 의존함.
다중 처리기 스케줄링
다중 처리기 스케줄링은 여러 개의 CPU 또는 여러 개의 코어가 존재하는 시스템에서의 CPU 스케줄링 문제.
단일 처리기 시스템에서는 준비 큐에서 하나의 프로세스를 골라 하나의 CPU에 할당하면 됨.
다중 처리기 시스템에서는 어떤 프로세스를 실행할지뿐 아니라 어느 처리기에서 실행할지도 결정해야 함.
다중 처리기 시스템은 단일 처리기 시스템보다 스케줄링 문제가 더 복잡함.
여러 처리기가 동시에 준비 큐에 접근할 수 있기 때문에 동기화 문제가 발생할 수 있음.
각 처리기의 부하를 균등하게 유지해야 하는 문제도 있음.
이전에 실행하던 처리기에서 다시 실행되도록 할 것인지,
부하를 맞추기 위해 다른 처리기로 이동시킬 것인지도 고려해야 함.
다중 코어, 하드웨어 스레드, NUMA, 이기종 다중 처리 구조는 다중 처리기 스케줄링을 더 복잡하게 만드는 요소.
여기서 다중 처리기라는 용어는
다중 코어 시스템, 다중 CPU 시스템, 하드웨어 스레드를 포함한 일반적인 의미로 사용됨.
다중 처리기 스케줄링에 대한 접근 방법
다중 처리기 스케줄링의 한 접근 방법은 비대칭 다중 처리.
비대칭 다중 처리에서는 하나의 처리기가 모든 스케줄링 결정, 입출력 처리, 시스템 활동을 담당함.
다른 처리기들은 사용자 코드만 실행함.
이 방식은 하나의 처리기만 시스템 자료구조에 접근하므로 자료 공유 문제가 단순해짐.
그러나 주 처리기가 병목이 될 수 있음.
대부분의 현대 운영체제는 대칭 다중 처리를 사용함.
대칭 다중 처리는 SMP라고 함.
SMP에서는 각 처리기가 자체적으로 스케줄링을 수행함.
모든 처리기는 공통 준비 큐에서 실행할 스레드를 선택할 수도 있음.
또는 각 처리기가 자신만의 준비 큐를 가질 수도 있음.
공통 준비 큐 방식은 모든 스레드가 하나의 큐에 들어가고, 각 처리기가 그 큐에서 실행할 스레드를 가져가는 구조.
이 방식은 부하 분산이 비교적 단순할 수 있음.
그러나 여러 처리기가 동시에 공통 큐에 접근하므로 동기화 오버헤드가 발생할 수 있음.
공통 준비 큐는 경쟁 조건을 막기 위해 락으로 보호되어야 함.
락 경쟁이 심해지면 준비 큐 접근 자체가 병목이 될 수 있음.
개별 준비 큐 방식은 각 처리기가 자신만의 준비 큐를 가지는 구조.
이 방식은 준비 큐 접근 경쟁을 줄일 수 있음.
그러나 어떤 처리기는 작업이 많고 어떤 처리기는 유휴 상태가 되는 부하 불균형이 발생할 수 있음.
개별 준비 큐 방식에서는 부하 균등화 기법이 중요함.
다중 코어 프로세서
다중 코어 프로세서는 하나의 물리 칩 안에 여러 처리 코어를 포함하는 구조.
각 코어는 운영체제에 독립적인 처리기처럼 보일 수 있음.
최근의 시스템은 하나의 코어가 둘 이상의 하드웨어 스레드를 지원하기도 함.
메모리 접근 지연은 처리기 성능에 큰 영향을 줄 수 있음.
한 스레드가 메모리에서 데이터를 기다리는 동안 처리 코어는 유휴 상태가 될 수 있음.
메모리 정지는 CPU가 데이터를 기다리면서 실행을 진행하지 못하는 상황.
칩 다중 스레딩은 이러한 메모리 대기 시간을 숨기기 위한 방법.
한 하드웨어 스레드가 메모리 접근으로 대기하면 같은 코어에 있는 다른 하드웨어 스레드를 실행할 수 있음.
이 방식은 하나의 코어 안에서 여러 하드웨어 스레드를 교대로 실행하여 코어 활용도를 높이는 구조.
운영체제 입장에서는 각 하드웨어 스레드가 논리 CPU처럼 보일 수 있음.
따라서 운영체제는 실제 물리 코어 수보다 더 많은 논리 CPU를 대상으로 스케줄링하게 됨.
다중 스레드 다중 코어 시스템에서는 운영체제가 어떤 스레드를 어떤 논리 CPU에 배치할지 결정해야 함.
같은 물리 코어에 속한 하드웨어 스레드들은 일부 자원을 공유함.
따라서 두 하드웨어 스레드가 같은 코어에서 실행되는 것은 완전히 독립적인 두 코어에서 실행되는 것과 같지 않음.
스케줄러는 물리 코어와 하드웨어 스레드의 관계를 고려해야 함.
가능하면 먼저 서로 다른 물리 코어에 작업을 배치하고,
필요할 때 같은 코어의 하드웨어 스레드를 활용하는 방식이 사용될 수 있음.
메모리 정지 시간이 많은 작업에서는 하드웨어 스레드가 성능 향상에 도움이 될 수 있음.
그러나 CPU 실행 자원을 많이 사용하는 작업들이 같은 코어의 하드웨어 스레드에 몰리면 성능 향상이 제한될 수 있음.
부하 균등화
부하 균등화는 여러 처리기 사이에 작업량이 고르게 분산되도록 하는 작업.
각 처리기가 별도의 준비 큐를 가지는 시스템에서는 한 처리기는 바쁘고 다른 처리기는 유휴 상태가 될 수 있음.
이 경우 전체 시스템 성능을 높이기 위해 작업을 이동시켜야 함.
부하 균등화는 대칭 다중 처리 시스템에서 중요한 문제.
공통 준비 큐 방식에서는 모든 처리기가 같은 큐에서 작업을 가져가므로 부하 균등화가 자연스럽게 이루어질 수 있음.
그러나 개별 준비 큐 방식에서는 별도의 부하 균등화 기법이 필요함.
부하 균등화에는 push migration과 pull migration이 있음.
push migration은 특정 작업이 주기적으로 각 처리기의 부하를 검사하는 방식.
부하가 높은 처리기에서 부하가 낮은 처리기로 프로세스를 이동시키는 구조.
pull migration은 유휴 상태의 처리기가 바쁜 처리기의 준비 큐에서 대기 중인 프로세스를 가져오는 방식.
두 방식은 서로 배타적인 것이 아니며 함께 사용될 수 있음.
예를 들어 Linux 스케줄러는 부하를 주기적으로 검사하면서 동시에 유휴 처리기가 작업을 가져오는 방식을 사용할 수 있음.
부하 균등화는 처리기 이용률을 높이는 데 도움이 됨.
그러나 프로세스를 다른 처리기로 이동시키면 캐시 친화성이 떨어질 수 있음.
따라서 부하 균등화는 처리기 선호도와 함께 고려되어야 함.
처리기 선호도
처리기 선호도는 프로세스가 이전에 실행되던 처리기에서 다시 실행되려는 성향.
프로세스가 특정 처리기에서 실행되면 해당 처리기의 캐시에 그 프로세스의 데이터가 남을 수 있음.
같은 처리기에서 다시 실행되면 캐시에 남은 데이터를 재사용할 수 있음.
이 경우 메모리 접근 시간을 줄이고 성능을 높일 수 있음.
반대로 프로세스가 다른 처리기로 이동하면 기존 캐시 내용을 사용할 수 없음.
새로운 처리기 캐시에 데이터를 다시 적재해야 하므로 비용이 발생함.
이러한 비용 때문에 운영체제는 가능한 한 같은 프로세스를 같은 처리기에서 계속 실행하려고 할 수 있음.
이를 처리기 선호도 또는 처리기 친화성이라고 함.
약한 선호도는 운영체제가 되도록 같은 처리기에서 프로세스를 실행하려고 하지만 반드시 보장하지 않는 방식.
강한 선호도는 프로세스가 실행될 수 있는 처리기 집합을 명시적으로 지정하는 방식.
강한 선호도를 사용하면 특정 프로세스나 스레드가 지정된 처리기에서만 실행되도록 제한할 수 있음.
처리기 선호도는 캐시 효율을 높일 수 있음.
그러나 선호도를 지나치게 강하게 유지하면 부하 균등화가 어려워질 수 있음.
어떤 처리기는 매우 바쁜데 특정 프로세스가 그 처리기에 고정되어 있다면 다른 처리기의 유휴 시간을 활용하기 어려움.
따라서 다중 처리기 스케줄링에서는 처리기 선호도와 부하 균등화 사이의 균형이 필요함.
NUMA 시스템에서는 처리기 선호도가 메모리 접근 시간과도 연결됨.
NUMA는 Non-Uniform Memory Access의 약어.
NUMA 시스템에서는 특정 CPU가 특정 메모리 영역에 더 빠르게 접근할 수 있음.
따라서 스레드를 어떤 CPU에 배치하는지가 메모리 접근 비용에도 영향을 줄 수 있음.
이기종 다중 처리
지금까지 설명한 예에서는 모든 처리 코어가 기능 면에서 동일하다고 가정함.
이 경우 어느 스레드든 모든 처리 코어에서 실행될 수 있음.
유일한 차이점은 NUMA 시스템에서의 메모리 접근 시간, 부하 균등화 정책, 처리기 선호도 정책에 따라 달라질 수 있음.
그러나 일부 시스템은 동일한 명령어 집합을 실행하더라도
속도와 전력 관리 측면에서 서로 다른 코어를 사용하도록 설계됨.
이러한 구조를 이기종 다중 처리라고 함.
이기종 다중 처리는 HMP라고 하며, Heterogeneous Multiprocessing의 약어.
HMP 시스템에서는 시스템 태스크와 사용자 태스크가 모든 코어에서 실행될 수 있음.
비대칭 다중 처리 형태와는 다름.
비대칭 다중 처리는 특정 처리기가 시스템 활동을 전담하고 다른 처리기가 사용자 작업만 실행하는 구조.
반면 HMP는 모든 코어에서 태스크 실행이 가능하되, 코어의 성능과 전력 특성이 서로 다른 구조.
HMP의 목적은 작업의 특정 요구에 따라 적절한 코어에 작업을 할당하여 전력 소비를 더 잘 관리하는 것.
모바일 시스템에서는 다중 코어 아키텍처가 널리 채택되어 있음.
일부 모바일 시스템은 동일한 명령어 집합을 실행하지만 전력 소비를 여러 수준으로 조정할 수 있는 코어를 포함함.
클록 속도와 전력 관리 측면에서 차이가 나는 코어를 사용하는 방식.
ARM 프로세서에서 이러한 유형의 아키텍처는 big.LITTLE이라고 불림.
big.LITTLE 구조는 고성능 big 코어와 에너지 효율적인 LITTLE 코어를 결합함.
big 코어는 더 많은 에너지를 소비하지만 높은 처리 능력을 제공함.
따라서 big 코어는 짧은 시간 동안 높은 성능이 필요한 작업에 적합함.
LITTLE 코어는 더 적은 에너지를 사용하므로 더 오랫동안 사용할 수 있음.
따라서 LITTLE 코어는 백그라운드 작업이나 높은 성능이 필요하지 않은 작업에 적합함.
HMP 방식에는 여러 장점이 있음.
CPU 스케줄러는 느린 코어를 빠른 코어와 결합하여 작업의 특성에 맞게 배치할 수 있음.
고성능을 요구하지 않지만 오랫동안 실행되어야 하는 백그라운드 작업은 LITTLE 코어에 할당할 수 있음.
이렇게 하면 배터리 충전을 보존하는 데 도움이 됨.
더 많은 처리 능력이 필요하지만 짧은 기간 동안 실행될 수 있는 대화형 응용 프로그램은 big 코어에 할당할 수 있음.
모바일 장치가 절전 모드일 경우 에너지 집약적인 big 코어를 비활성화할 수 있음.
이때 시스템은 에너지 효율적인 LITTLE 코어에 의존할 수 있음.
Windows 10은 스레드가 전원 관리 요구를 가장 잘 지원하는 스케줄링 정책을 선택할 수 있도록 하여
HMP 스케줄링을 지원함.
HMP 스케줄링에서는 단순히 모든 코어를 동일하게 보고 작업을 분배하는 것이 아님.
성능 요구와 전력 요구를 함께 고려하는 방식.
따라서 이기종 다중 처리 환경에서는
작업의 성격, 사용자 상호작용 여부, 에너지 상태, 배터리 상태, 코어 성능 차이를 함께 고려하는 스케줄링이 중요함.
실시간 CPU 스케줄링
실시간 시스템은 작업이 정해진 시간 제약 안에 완료되어야 하는 시스템.
실시간 CPU 스케줄링은 결과의 정확성뿐 아니라 결과가 나오는 시간도 중요한 환경에서 사용됨.
실시간 시스템은 연성 실시간 시스템과 경성 실시간 시스템으로 나뉨.
연성 실시간 시스템은 중요한 실시간 프로세스가 일반 프로세스보다 높은 우선순위를 받도록 보장하는 시스템.
그러나 연성 실시간 시스템은 실시간 프로세스가 반드시 정해진 시간 안에 완료된다는
절대적 보장은 제공하지 않을 수 있음.
경성 실시간 시스템은 작업이 반드시 마감시간 안에 완료되어야 하는 시스템.
경성 실시간 시스템에서 마감시간을 놓치면 시스템 실패로 이어질 수 있음.
실시간 CPU 스케줄링에서는 지연 시간을 최소화하는 것이 중요함.
또한 실시간 작업의 우선순위를 적절히 관리하고 마감시간을 고려해야 함.
지연 시간 최소화
실시간 시스템에서는 이벤트가 발생한 뒤 그 이벤트가 처리되기까지의 시간이 매우 중요함.
이벤트 지연 시간은 이벤트가 발생한 시점부터 해당 이벤트가 서비스되기 시작할 때까지 걸리는 시간.
실시간 시스템은 이벤트 지연 시간을 가능한 한 줄여야 함.
지연 시간에는 인터럽트 지연 시간과 디스패치 지연 시간이 있음.
인터럽트 지연 시간은 CPU에 인터럽트가 도착한 시점부터 인터럽트 서비스 루틴이 시작될 때까지의 시간.
인터럽트가 발생하면 운영체제는 현재 실행 중인 명령을 완료해야 함.
그 뒤 현재 프로세스의 상태를 저장하고, 인터럽트 서비스 루틴의 시작 위치로 이동해야 함.
이 과정에서 걸리는 시간이 인터럽트 지연 시간.
실시간 태스크에서는 인터럽트가 너무 오래 지연되면 마감시간을 놓칠 수 있음.
디스패치 지연 시간은 스케줄러가 현재 프로세스를 멈추고 다른 프로세스를 실행하기까지 걸리는 시간.
높은 우선순위 실시간 프로세스가 준비되었을 때 현재 실행 중인 낮은 우선순위 프로세스를 빠르게 선점해야 함.
디스패치 지연 시간에는 현재 실행 중인 프로세스를 선점하는 데 걸리는 시간이 포함됨.
또한 높은 우선순위 프로세스를 실행 가능하게 만드는 시간이 포함됨.
선점형 커널은 디스패치 지연 시간을 줄이는 데 중요함.
커널 자료구조를 갱신하는 동안에는 선점이 제한될 수 있음.
따라서 실시간 시스템에서는 커널의 임계 구역을 짧게 유지하는 것이 중요함.
디스패치 지연을 줄이려면 선점 지점이 많고, 커널 내부 봉쇄 시간이 짧아야 함.
우선순위 기반 스케줄링
실시간 운영체제에서 가장 중요한 기능은 실시간 프로세스가 필요할 때 즉시 CPU를 받을 수 있도록 하는 것.
이를 위해 실시간 스케줄링은 보통 우선순위 기반 선점 스케줄링을 사용함.
실시간 프로세스는 일반 프로세스보다 높은 우선순위를 가져야 함.
높은 우선순위 실시간 프로세스가 준비 상태가 되면 낮은 우선순위 프로세스를 선점할 수 있어야 함.
연성 실시간 시스템에서는 우선순위 기반 선점 스케줄링만으로도 어느 정도 요구를 만족할 수 있음.
그러나 경성 실시간 시스템에서는 마감시간 보장이 필요하므로 단순한 우선순위만으로는 충분하지 않음.
실시간 프로세스는 보통 주기적 프로세스로 표현될 수 있음.
주기적 프로세스는 일정한 주기마다 CPU를 요구하는 작업.
각 주기적 프로세스는 처리 시간, 마감시간, 주기를 가짐.
처리 시간은 한 번 실행될 때 필요한 CPU 시간.
마감시간은 작업이 완료되어야 하는 시점.
주기는 작업이 반복되는 간격.
실시간 스케줄링 알고리즘은 이러한 시간 매개변수를 고려하여 작업을 스케줄함.
실시간 프로세스의 마감시간은 다음 주기가 시작되기 전까지일 수도 있음.
또는 그보다 더 짧을 수도 있음.
스케줄러는 새 실시간 프로세스를 받아들일 수 있는지 판단해야 할 수도 있음.
마감시간을 만족시킬 수 없는 작업까지 받아들이면 전체 실시간 보장이 깨질 수 있음.
Rate-Monotonic 스케줄링
Rate-Monotonic 스케줄링은 주기적 작업을 위한 정적 우선순위 스케줄링 알고리즘.
각 프로세스의 우선순위는 주기에 따라 결정됨.
주기가 짧은 프로세스일수록 높은 우선순위를 가짐.
주기가 긴 프로세스일수록 낮은 우선순위를 가짐.
Rate-Monotonic 방식에서 우선순위는 고정됨.
실행 중에 우선순위가 변하지 않음.
높은 우선순위 프로세스가 준비되면 낮은 우선순위 프로세스를 선점할 수 있음.
이 알고리즘은 각 주기마다 하나의 작업이 발생하고, 마감시간이 주기와 같다는 가정에서 사용됨.
예를 들어 짧은 주기를 가진 프로세스는 더 자주 실행되어야 하므로 높은 우선순위를 받음.
긴 주기를 가진 프로세스는 상대적으로 덜 자주 실행되어도 되므로 낮은 우선순위를 받음.
Rate-Monotonic 스케줄링은 단순하고 분석하기 쉬움.
그러나 모든 실시간 작업 집합을 스케줄할 수 있는 것은 아님.
CPU 이용률이 일정 한계를 넘으면 모든 마감시간을 만족시키지 못할 수 있음.
처리 시간과 주기의 조합에 따라 스케줄 가능 여부가 결정됨.
어떤 작업 집합은 이론적으로 스케줄 가능하더라도 Rate-Monotonic 방식으로는 마감시간을 만족하지 못할 수 있음.
Rate-Monotonic 스케줄링은 정적 우선순위 방식이므로 구현이 비교적 단순함.
하지만 동적으로 변하는 마감시간이나 비주기적 작업에는 유연성이 낮을 수 있음.
Earliest-Deadline-First 스케줄링
Earliest-Deadline-First 스케줄링은 EDF 스케줄링이라고 함.
EDF는 마감시간이 가장 빠른 프로세스에 가장 높은 우선순위를 부여하는 방식.
마감시간이 가까울수록 우선순위가 높음.
마감시간이 늦을수록 우선순위가 낮음.
EDF는 동적 우선순위 스케줄링 알고리즘.
프로세스의 우선순위는 실행 중에도 마감시간에 따라 변할 수 있음.
새로운 프로세스가 준비 상태가 되었을 때
그 프로세스의 마감시간이 현재 실행 중인 프로세스보다 빠르면 현재 프로세스를 선점할 수 있음.
EDF는 주기적 프로세스뿐 아니라 다양한 마감시간 기반 작업에 적용될 수 있음.
이론적으로 EDF는 단일 처리기에서 CPU 이용률이 100%에 가까운 경우에도 스케줄 가능한 작업 집합을 처리할 수 있음.
그러나 실제 시스템에서는 문맥 교환, 인터럽트 처리, 커널 오버헤드 등을 고려해야 함.
EDF는 우선순위가 동적으로 변하기 때문에 구현과 분석이 복잡할 수 있음.
마감시간이 계속 바뀌는 환경에서는 스케줄러가 매번 가장 가까운 마감시간을 가진 작업을 찾아야 함.
EDF는 Rate-Monotonic보다 더 많은 작업 집합을 스케줄할 수 있는 경우가 있음.
하지만 동적 우선순위 갱신에 따른 비용이 존재함.
일정 비율의 몫 스케줄링
일정 비율의 몫 스케줄링은 각 응용이 전체 처리기 시간 중 일정한 몫을 받도록 보장하는 방식.
전체 CPU 시간을 일정한 수의 몫으로 나누고, 각 프로세스에 일부 몫을 할당하는 구조로 생각할 수 있음.
프로세스가 가진 몫이 많을수록 CPU를 더 많이 받을 수 있음.
예를 들어 전체 몫이 100개이고 어떤 프로세스가 20개를 받으면 전체 CPU 시간의 20%를 받을 수 있음.
이 방식은 각 프로세스가 약속된 비율만큼 CPU 시간을 받도록 하는 것이 목적.
할당된 몫의 합이 전체 몫보다 크면 약속된 CPU 비율을 보장할 수 없음.
따라서 시스템은 각 프로세스에 할당된 몫의 총합을 관리해야 함.
일정 비율의 몫 스케줄링은 공정한 CPU 배분이 필요한 환경에서 사용할 수 있음.
실시간 요구를 가진 응용이 일정한 처리기 몫을 필요로 할 때도 활용 가능.
이 방식은 절대적인 마감시간보다 CPU 시간 비율 보장이 중요한 경우에 적합함.
POSIX 실시간 스케줄링
POSIX는 실시간 스레드를 위한 스케줄링 정책을 정의함.
대표적인 POSIX 실시간 스케줄링 정책은 SCHED_FIFO와 SCHED_RR.
SCHED_FIFO는 선입선출 방식의 실시간 스케줄링 정책.
같은 우선순위 안에서는 먼저 준비된 스레드가 먼저 실행됨.
SCHED_FIFO 스레드는 더 높은 우선순위 스레드가 준비되지 않는 한 계속 실행될 수 있음.
높은 우선순위 스레드가 준비되면 낮은 우선순위 스레드는 선점됨.
SCHED_RR은 라운드 로빈 방식의 실시간 스케줄링 정책.
같은 우선순위를 가진 스레드들이 시간 할당량을 기준으로 CPU를 나누어 사용함.
SCHED_RR은 SCHED_FIFO와 비슷하지만 같은 우선순위 스레드 사이에서 시간 할당량을 적용한다는 차이가 있음.
POSIX 실시간 스케줄링에서는 스레드의 우선순위 범위를 확인할 수 있음.
sched_get_priority_min 함수는 특정 정책에서 가능한 최소 우선순위를 반환함.
sched_get_priority_max 함수는 특정 정책에서 가능한 최대 우선순위를 반환함.
응용 프로그램은 스케줄링 정책과 우선순위를 지정하여 실시간 스레드를 만들 수 있음.
pthread_attr_setschedpolicy 함수는 스레드의 스케줄링 정책을 설정하는 데 사용될 수 있음.
pthread_attr_setschedparam 함수는 스레드의 스케줄링 매개변수를 설정하는 데 사용될 수 있음.
다만 실제 지원 여부와 우선순위 범위는 운영체제 구현에 따라 달라질 수 있음.
운영체제 사례
운영체제는 각자의 목적과 구조에 맞게 CPU 스케줄러를 구현함.
여기서는 Linux, Windows, Solaris의 스케줄링 방식을 살펴봄.
세 운영체제 모두 우선순위와 선점 개념을 사용함.
그러나 우선순위 범위, 스케줄링 클래스, 시간 할당량 관리 방식은 서로 다름.
Linux 스케줄링
Linux는 버전과 시기에 따라 여러 스케줄러를 사용해 왔음.
초기의 Linux 스케줄러는 전통적인 UNIX 스케줄링 방식을 따름.
2.5 커널에서는 O(1) 스케줄러가 도입됨.
O(1) 스케줄러는 실행 가능한 프로세스 수와 관계없이 일정한 시간 안에 스케줄링 결정을 내리는 것을 목표로 함.
그러나 대화형 작업에 대한 응답성과 공정성 측면에서 한계가 있었음.
2.6.23 커널부터 Linux는 완전 공평 스케줄러를 사용함.
완전 공평 스케줄러는 CFS라고 하며, Completely Fair Scheduler의 약어.
CFS의 목표는 각 작업이 공정하게 CPU 시간을 받도록 하는 것.
CFS는 고정된 시간 할당량 대신 가상 실행 시간이라는 값을 사용함.
가상 실행 시간은 작업이 CPU를 얼마나 사용했는지를 추적하는 값.
CPU를 많이 사용한 작업은 가상 실행 시간이 증가함.
우선순위가 높은 작업은 가상 실행 시간이 더 천천히 증가하도록 처리될 수 있음.
우선순위가 낮은 작업은 같은 실제 실행 시간에 대해 가상 실행 시간이 더 빠르게 증가할 수 있음.
CFS는 가상 실행 시간이 가장 작은 작업을 선택하여 실행함.
이 방식은 지금까지 CPU를 가장 적게 받은 작업에 실행 기회를 주려는 구조.
Linux는 실행 가능한 작업을 효율적으로 찾기 위해 균형 이진 트리 구조를 사용할 수 있음.
실행 가능한 작업들은 가상 실행 시간을 기준으로 정렬됨.
스케줄러는 트리에서 가장 왼쪽에 있는 작업을 선택할 수 있음.
가장 왼쪽의 작업은 가상 실행 시간이 가장 작은 작업.
Linux는 nice 값을 사용하여 일반 작업의 우선순위를 조정함.
nice 값이 낮을수록 높은 우선순위를 의미함.
nice 값이 높을수록 낮은 우선순위를 의미함.
CFS는 nice 값을 바탕으로 각 작업이 받을 CPU 비율을 조정할 수 있음.
Linux는 일반 작업뿐 아니라 실시간 작업도 지원함.
실시간 작업은 일반 작업보다 높은 우선순위를 가질 수 있음.
Linux의 실시간 스케줄링 정책에는 FIFO와 RR 방식이 포함됨.
실시간 작업은 CFS로 관리되는 일반 작업보다 먼저 스케줄될 수 있음.
Windows 스케줄링
Windows는 우선순위 기반의 선점 스케줄링을 사용함.
Windows 스케줄러는 가장 높은 우선순위를 가진 준비 스레드를 실행하도록 선택함.
선택된 스레드는 더 높은 우선순위 스레드가 준비되거나,
시간 할당량이 끝나거나, 대기 상태로 이동하거나, 종료될 때까지 실행됨.
Windows에서 스케줄링 단위는 스레드.
프로세스는 하나 이상의 스레드를 가지며, 실제 CPU에 배정되는 것은 스레드.
Windows는 32단계 우선순위 체계를 사용함.
우선순위는 일반적으로 0부터 31까지의 범위로 표현됨.
우선순위 0은 시스템에서 사용되는 특별한 우선순위.
1부터 15까지는 가변 우선순위 영역.
16부터 31까지는 실시간 우선순위 영역.
실시간 우선순위 스레드는 일반 가변 우선순위 스레드보다 높은 우선순위를 가짐.
스레드의 기본 우선순위는 프로세스의 우선순위 클래스와 스레드 자체의 상대 우선순위에 의해 결정됨.
Windows는 여러 프로세스 우선순위 클래스를 제공함.
예를 들어 idle, below normal, normal, above normal, high, realtime 같은 우선순위 클래스가 사용될 수 있음.
스레드는 프로세스 우선순위 클래스 안에서 상대 우선순위를 가질 수 있음.
Windows는 대화형 응답성을 높이기 위해 일부 스레드의 우선순위를 동적으로 조정함.
입출력이 완료되어 깨어난 스레드는 일시적으로 우선순위가 높아질 수 있음.
사용자 인터페이스와 관련된 스레드도 응답성을 위해 우선순위 향상을 받을 수 있음.
키보드나 마우스 입력과 관련된 전경 프로세스는 더 나은 응답성을 얻을 수 있음.
CPU를 오래 사용하는 스레드는 동적 우선순위 향상 효과가 줄어들 수 있음.
Windows는 전경 응용 프로그램에 더 긴 시간 할당량을 줄 수도 있음.
이를 통해 사용자가 직접 상호작용하는 응용의 응답성을 높일 수 있음.
멀티프로세서 환경에서는 스레드 친화성과 부하 분산도 고려함.
Windows 스케줄러는 스레드가 이전에 실행된 처리기에서 다시 실행되도록 하여 캐시 활용을 높이려 할 수 있음.
동시에 시스템 전체 부하가 한쪽으로 몰리지 않도록 스레드를 다른 처리기로 이동시킬 수도 있음.
Solaris 스케줄링
Solaris는 우선순위 기반 스케줄링을 사용함.
Solaris에는 여러 스케줄링 클래스가 존재함.
대표적인 스케줄링 클래스에는
시분할 클래스, 대화형 클래스, 실시간 클래스, 시스템 클래스, 공평 공유 클래스, 고정 우선순위 클래스가 있음.
시분할 클래스는 일반 사용자 프로세스를 위한 클래스.
대화형 클래스는 사용자와 상호작용하는 작업의 응답성을 높이기 위한 클래스.
실시간 클래스는 시간 제약이 있는 작업을 위한 클래스.
시스템 클래스는 커널 스레드 같은 시스템 작업을 위한 클래스.
공평 공유 클래스는 CPU 시간을 프로젝트나 사용자 그룹 사이에 공평하게 나누기 위한 클래스.
고정 우선순위 클래스는 우선순위를 고정적으로 설정하여 실행하는 클래스.
Solaris는 전역 우선순위를 사용하여 스레드를 선택함.
각 스케줄링 클래스는 자신의 우선순위 범위를 가짐.
스케줄러는 가장 높은 전역 우선순위를 가진 실행 가능한 스레드를 선택함.
같은 우선순위 안에서는 각 클래스의 정책에 따라 스케줄링됨.
Solaris의 시분할 클래스에서는 우선순위와 시간 할당량을 표 형태로 관리할 수 있음.
CPU를 많이 사용한 스레드는 우선순위가 낮아질 수 있음.
오래 기다린 스레드는 우선순위가 높아질 수 있음.
이를 통해 대화형 작업의 응답성과 CPU 중심 작업의 공정성을 조정함.
실시간 클래스는 일반 클래스보다 높은 우선순위를 가질 수 있음.
실시간 스레드는 시스템의 응답 시간을 보장하기 위해 높은 우선순위에서 실행됨.
그러나 실시간 스레드를 잘못 사용하면 일반 시스템 작업이 실행되지 못할 위험이 있음.
따라서 실시간 우선순위는 신중하게 사용해야 함.
알고리즘의 평가
CPU 스케줄링 알고리즘은 어떤 기준으로 좋은지 평가해야 함.
평가 기준에는 CPU 이용률, 처리량, 총처리 시간, 대기 시간, 응답 시간 등이 있음.
어떤 기준을 중요하게 볼 것인지는 시스템의 목적에 따라 달라짐.
대화형 시스템에서는 응답 시간이 중요함.
일괄 처리 시스템에서는 처리량과 총처리 시간이 중요할 수 있음.
실시간 시스템에서는 마감시간 준수와 지연 시간 최소화가 중요함.
스케줄링 알고리즘을 평가하는 방법에는 결정론적 모델링, 큐잉 모델, 시뮬레이션, 실제 구현이 있음.
결정론적 모델링
결정론적 모델링은 미리 정해진 특정 작업 부하를 사용하여 알고리즘의 성능을 계산하는 방식.
분석할 프로세스 집합과 각 프로세스의 CPU 버스트 시간이 주어져 있을 때
알고리즘별 대기 시간과 평균 대기 시간을 계산할 수 있음.
이 방식은 사전에 정의된 부하에 대해 각 알고리즘이 어떻게 동작하는지 명확히 보여줌.
예를 들어 다섯 개의 프로세스 P1, P2, P3, P4, P5가 존재한다고 가정할 수 있음.
각 프로세스의 CPU 버스트 시간은
P1이 10밀리초,
P2가 29밀리초,
P3가 3밀리초,
P4가 7밀리초,
P5가 12밀리초라고 둘 수 있음.
이 프로세스들이 모두 시간 0에 도착했다고 가정함.
선입 선처리 스케줄링을 적용하면 프로세스들은 P1, P2, P3, P4, P5 순서로 실행됨.
이때 P1의 대기 시간은 0밀리초.
P2의 대기 시간은 10밀리초.
P3의 대기 시간은 39밀리초.
P4의 대기 시간은 42밀리초.
P5의 대기 시간은 49밀리초.
따라서 평균 대기 시간은 (0 + 10 + 39 + 42 + 49) / 5 = 28밀리초.
비선점 SJF 스케줄링을 적용하면 CPU 버스트가 짧은 순서로 실행됨.
실행 순서는 P3, P4, P1, P5, P2가 됨.
이때 P1의 대기 시간은 10밀리초.
P2의 대기 시간은 32밀리초.
P3의 대기 시간은 0밀리초.
P4의 대기 시간은 3밀리초.
P5의 대기 시간은 20밀리초.
따라서 평균 대기 시간은 (10 + 32 + 0 + 3 + 20) / 5 = 13밀리초.
라운드 로빈 스케줄링을 시간 할당량 10밀리초로 적용할 수도 있음.
실행 순서는 P1, P2, P3, P4, P5, P2, P5, P2와 같은 형태로 진행됨.
P1은 처음 10밀리초 동안 실행되어 완료됨.
P2는 처음 10밀리초를 실행한 뒤 남은 시간이 있어 다시 준비 큐로 들어감.
P3는 3밀리초만 실행하면 완료됨.
P4는 7밀리초만 실행하면 완료됨.
P5는 처음 10밀리초를 실행한 뒤 남은 2밀리초를 나중에 실행함.
P2는 여러 번 시간 할당량을 받아 마지막에 완료됨.
이 경우 P1의 대기 시간은 0밀리초.
P2의 대기 시간은 32밀리초.
P3의 대기 시간은 20밀리초.
P4의 대기 시간은 23밀리초.
P5의 대기 시간은 40밀리초.
따라서 평균 대기 시간은 (0 + 32 + 20 + 23 + 40) / 5 = 23밀리초.
이 예에서는 SJF가 평균 대기 시간을 가장 작게 만듦.
그러나 결정론적 모델링의 결과는 특정 프로세스 집합에만 적용됨.
다른 프로세스 집합에 대해서는 알고리즘의 상대적 성능이 달라질 수 있음.
결정론적 모델링은 간단하고 빠르며 알고리즘의 동작을 정확히 보여줄 수 있음.
그러나 일반적인 성능 평가 방법으로는 제한적임.
정확한 입력이 주어진 경우에만 유용한 방식.
큐잉 모델
많은 시스템에서 실행되는 프로세스들은 날마다 변화함.
따라서 결정론적 모델링을 사용할 수 있는 고정된 프로세스 집합이나 고정된 시간이 존재하지 않는 경우가 많음.
그러나 결정할 수 있는 것은 CPU와 입출력 버스트의 분포.
이러한 분포는 측정할 수 있고, 근사적으로 추정할 수 있음.
일반적으로 CPU 버스트의 분포는 지수형 분포로 표현되는 경우가 많음.
프로세스들이 시스템에 도착하는 시간의 분포도 기술할 수 있음.
도착 시간과 서비스 시간의 분포를 알면 CPU 이용률, 평균 처리량, 평균 대기 시간 등을 계산할 수 있음.
이러한 연구 분야를 큐잉 네트워크 분석이라고 함.
컴퓨터 시스템은 서버들의 네트워크로 기술될 수 있음.
각 서버는 대기 프로세스들의 큐를 가짐.
CPU는 하나의 서버이고, 각 입출력 장치도 하나의 서버로 볼 수 있음.
각 서버에는 대기 큐가 존재함.
프로세스는 CPU 큐에서 서비스를 받은 뒤 입출력 큐로 이동할 수 있음.
입출력 서비스가 끝나면 다시 CPU 큐로 돌아올 수 있음.
이러한 흐름을 네트워크 형태로 모델링하는 것이 큐잉 네트워크 분석.
큐잉 모델에서 중요한 값으로 평균 큐 길이, 평균 대기 시간, 평균 도착률이 있음.
n은 평균 큐 길이를 의미함.
W는 큐에서의 평균 대기 시간을 의미함.
y는 새로운 프로세스들이 큐에 도착하는 평균 도착률을 의미함.
만약 y가 초당 평균 도착 프로세스 수라면, W는 각 프로세스가 큐에서 보내는 평균 시간.
안정 상태에서는 큐를 떠나는 프로세스의 수와 큐에 도착하는 프로세스의 수가 같아야 함.
이때 다음 식이 성립함.
n = y × W
이 식을 Little의 공식이라고 함.
Little의 공식은 어떤 스케줄링 알고리즘이나 도착 분포에서도 성립하기 때문에 유용함.
예를 들어 평균 도착률과 평균 대기 시간을 알고 있다면 평균 큐 길이를 계산할 수 있음.
반대로 평균 큐 길이와 평균 도착률을 알고 있다면 평균 대기 시간을 계산할 수 있음.
큐잉 모델은 수학적으로 시스템을 분석할 수 있다는 장점이 있음.
그러나 실제 시스템에서 도착 분포와 서비스 시간 분포를 정확히 알기 어렵다는 한계가 있음.
또한 복잡한 스케줄링 알고리즘을 수학적으로 정확히 표현하기 어려운 경우가 많음.
프로세스 간의 상호작용, 캐시 효과, 입출력 장치의 실제 동작, 운영체제 오버헤드도 모델에 모두 반영하기 어려움.
따라서 큐잉 모델은 이론적 분석에는 유용하지만 실제 시스템 전체를 완전히 반영하기에는 한계가 있음.
시뮬레이션
시뮬레이션은 컴퓨터 프로그램으로 스케줄링 알고리즘의 동작을 모의 실험하는 방식.
결정론적 모델링보다 다양한 작업 부하를 다룰 수 있음.
큐잉 모델보다 실제 시스템의 세부 동작을 더 많이 반영할 수 있음.
시뮬레이터는 시스템 시간을 나타내는 변수와 자료구조를 사용하여 동작함.
시뮬레이터는 프로세스 도착, CPU 버스트, 입출력 요청, 입출력 완료 같은 사건을 생성함.
각 사건이 발생할 때 시뮬레이터는 스케줄링 알고리즘에 따라 준비 큐와 CPU 상태를 변경함.
그 결과 평균 대기 시간, 총처리 시간, 응답 시간, CPU 이용률 등을 측정할 수 있음.
시뮬레이션에 필요한 입력 데이터는 여러 방식으로 생성 가능.
한 가지 방식은 난수 발생기를 사용하는 것.
난수 발생기는 특정 확률 분포에 따라 프로세스, CPU 버스트 시간, 입출력 시간을 생성할 수 있음.
확률 분포는 균등 분포, 지수 분포 등으로 설정될 수 있음.
그러나 난수 기반 시뮬레이션은 실제 시스템과 다른 작업 부하를 만들 수 있음.
더 정확한 방식은 실제 시스템에서 측정한 자료를 사용하는 것.
실제 시스템에서 프로세스의 도착 시간, CPU 버스트, 입출력 요청 같은 사건을 기록할 수 있음.
이 기록을 추적 테이프라고 함.
추적 테이프는 실제 시스템에서 발생한 사건들의 순서를 저장한 자료.
시뮬레이터는 추적 테이프를 입력으로 사용하여 여러 스케줄링 알고리즘을 비교할 수 있음.
같은 추적 테이프를 여러 알고리즘에 적용하면 공정한 비교가 가능함.
시뮬레이션은 실제 운영체제를 수정하지 않고도 알고리즘을 비교할 수 있다는 장점이 있음.
그러나 시뮬레이터를 작성하는 데 시간과 비용이 필요함.
시뮬레이션 결과는 입력 데이터와 모델의 정확성에 크게 의존함.
시뮬레이터가 실제 시스템의 모든 오버헤드와 하드웨어 특성을 반영하지 못할 수도 있음.
따라서 시뮬레이션은 실제 구현보다 안전하지만, 여전히 근사적인 평가 방법.
구현
가장 정확한 평가 방법은 실제 운영체제에 스케줄링 알고리즘을 구현하고 실행해 보는 것.
실제 시스템에서 알고리즘을 실행하면 실제 작업 부하와 실제 하드웨어 환경에서 성능을 확인할 수 있음.
그러나 구현은 비용이 많이 들고 위험할 수 있음.
운영체제 스케줄러를 수정하면 시스템 안정성에 영향을 줄 수 있음.
새 스케줄러가 예상과 다르게 동작하면 사용자는 성능 저하나 응답성 저하를 경험할 수 있음.
실제 환경에서는 작업 부하가 계속 변하기 때문에 평가 결과를 일반화하기 어려울 수 있음.
특정 스케줄러가 특정 작업 부하에서는 잘 동작하지만 다른 작업 부하에서는 좋지 않을 수 있음.
사용자들은 스케줄러가 바뀌면 자신의 작업 방식을 바꿀 수도 있음.
이 때문에 알고리즘 변경 후 측정 결과가 원래 예상과 달라질 수 있음.
실제 구현은 가장 현실적인 평가 방법이지만 가장 어렵고 비용이 큰 방법.
일부 시스템은 관리자가 스케줄링 정책이나 매개변수를 조정할 수 있는 기능을 제공함.
사용자는 프로세스 우선순위를 바꾸거나 특정 스케줄링 클래스를 선택할 수 있음.
그러나 일반 사용자가 스케줄링 알고리즘을 직접 조정하는 것은 복잡하고 위험할 수 있음.
따라서 운영체제는 일반적인 작업 부하에서 좋은 성능을 내도록 기본 스케줄러를 제공함.
실제 구현 전에는 결정론적 모델링, 큐잉 모델, 시뮬레이션을 통해 후보 알고리즘을 미리 평가할 수 있음.
그 뒤 제한된 환경에서 실제 구현을 실험하는 방식이 사용될 수 있음.