OS 5. CPU 스케줄링

서론

 CPU스케줄링은 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다. 여기서 기본적인 스케줄링 개념과 여러 스케줄링 알고리즘을 소개한다. 일반적인 스케줄링 개념을 논의하는 경우 프로세스 스케줄링을 사용하고 스레드에 국한된 개념을 가리키는 경우에는 스레드 스케줄링이라는 용어를 사용한다. 그리고 코어가 CPU의 기본 계산 단위이며 프로세스가 CPU코어에서 실행되는 방식을 기억하자.

---

CPU 스케줄러 기본 개념

 다중 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 가지게 하는 데 있다. 다중 프로그래밍에 대한 기본 아이디어는 간단하다. 하나의 프로세스는 전형적으로 어떤 I/O 요청이 완료되기를 기다려야만 할 때까지 실행된다. 이렇게 되면, CPU가 노는 시간이 생기게 되며 모든 대기 시간은 낭비되고 어떤 유용한 작업도 수행하지 못한다. 다중 프로그래밍에서는 이러한 시간을 생산적으로 활용하려고 시도한다. 어느 한순간에 다수의 프로세스를 메모리 내에 유지한다. 어떤 프로세스가 대기해야 할 경우, 운영체제는 CPU를 그 프로세스로부터 회수해 다른 프로세스에 할당한다. 이러한 패턴은 계속된다.

CPU-I/O Burst Cycle

 CPU 스케줄링의 성공은 프로세스들의 다음과 같은 관찰된 성질에 의해 좌우된다. 프로세스 실행은 CPU 실행과 I/O 대기 사이클로 구성된다. 프로세스들은 이들 두 상태 사이를 교대로 왔다 갔다 한다. 프로세스 실행은 CPU 버스트(CPU burst)로 시작된다. 뒤이어 I/O 버스트(I/O burst)가 발생하고, 그 두를 이어 또 다른 CPU버스트가 발생하며, 이어 또 다른  I/O 버스트 등등으로 진행된다. 결국 마지막 CPU버스트는 또 다른 I/O 버스트가 뒤따르는 대신, 실행을 종료하기 위한 시스템 요청과 함께 끝난다.

Alternating sequence of CPU bursts and I/O bursts / Histogram of CPU burst times

CPU Scheduler

 CPU가 유휴 상태가 될 때마다, 운영체제는 준비 큐에 있는 프로세스 중에서 하나를 선택해 실행해야 한다. 선택 절차는 CPU 스케줄러에 의해 수행된다. 스케줄러는 실행 준비가 되어 있는 메모리 내의 프로세스 중에서 선택하여, 이들 중 하나에게 CPU를 할당한다.

준비 큐는 반드시 선입선출(FIFO) 방식의 큐가 아니어도 된다. 개념적으로 볼 때 준비 큐에 있는 모든 프로세스는 CPU에서 실행될 기회를 기다리며 대기하고 있다. 큐에 있는 레코드들은 일반적으로 프로세스들의 프로세스 제어 블록(PCB)들이다.

예시

 CPU 스케줄링 결정은 다음과 같은 경우에 발생할 수 있다.
(1) 프로세스가 실행 상태에서 대기 상태로 전환(예: I/O 요청),
(2) 프로세스가 실행 상태에서 준비 상태로 전환됨(예: 타임 슬라이스 만료),
(3) 프로세스가 대기에서 준비로 전환(예: I/O 완료)하거나
(4) 프로세스가 종료됩니다.

→ (1)과 (4)에 따른 스케줄링은 비선점적(non-preemptive)이다. (2)와 (3)의 스케줄링은 선점적(preemptive)이다.

디스패처(Dispatcher)

 디스패처(Dispatcher)는 CPU 스케줄러가 선택한 프로세스에 CPU 제어권을 부여해 주는 모듈이다. 디스패처는 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일, 사용자 모드로 전환하는 일, 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동하는 일을 맡는다. 디스패처는 모든 프로세스의 문맥 교환 시 호출되므로, 가능한 한 빨리 수행되어야 한다. 디스패처가 하나의 프로세스를 정지하고 다른 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 디스패치 지연(dispatch latency)이라고 한다.

---

스케줄링 기준(Scheduling Criteria)

• CPU 이용률(CPU utilization): CPU를 가능한 한 바쁘게 유지하기를 원한다. (0% ~ 100%)
• 처리량(Throughput): 시간 단위당 완료된 프로세스 개수.
• 총 처리 시간(Turnaround time): 프로세스를 실행하는 데 소요된 시간, 제출 시간에서 완료 시간까지의 시간.
• 대기 시간(Waiting time): 프로세스가 준비 큐에서 대기한 시간의 합.
• 응답 시간(Response time): 요청 제출부터 첫 번째 응답이 생성될 때까지의 시간.(응답을 출력하는 데 걸리는 시간이 아니라, 응답이 시작되는 데까지 걸리는 시간)

스케줄링 알고리즘의 목표(Scheduling algorithm’s goals)

• CPU 이용률과 처리량 극대화
• 총 처리 시간, 대기 시간, 응답 시간 최소화
  • 응답 시간의 평균보다 분산을 최소화하는 것이 더 중요할 수 있다.

---

스케줄링 알고리즘(Scheduling algorithms)

선입 선처리(First-Come First-Served, FCFS)

 가장 간단한 CPU 스케줄링 알고리즘이다. CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.  이 알고리즘의 구현은 선입선출 큐로 쉽게 관리할 수 있다. 즉, 선입 선처리를 위한 코드는 작성하기 쉽고 이해하기 쉽다. 그러나 단점으로 선입 선처리 정책하에서 평균대기 시간은 종종 대단히 길 수 있다.

예

 Gantt차트는 참여한 각 프로세스의 시작 시각과 종료 시각을 포함하여 특정 스케줄 기법을 도시하는 막대형 차트이다. 아래와 같이 프로세스가 있고 해당 burst 시간을 갖는다고 하자.

The process set

 프로세스들이 P1, P2, P3 순으로 도착하고 선입 선처리 순으로 서비스받는 다면 다음 Gantt 차트에 보인 결과를 얻는다.

대기 시간: P1 = 0, P2 = 24, P3 = 27.

평균 대기 시간: (0 + 24 + 27)/3 = 17.

FCFS는 비선점형이다.

The Gantt Chart for the schedule

 프로세스들이 P2, P3, P1 순으로 도착하고 선입 선처리 순으로 서비스받는 다면 다음 Gantt 차트에 보인 결과를 얻는다.

대기 시간: P1 = 6, P2 = 0, and P3 = 3.

평균 대기 시간: (6 + 0 + 3)/3 = 3.

The Gantt Chart for the schedule

최단 작업 우선 스케줄링(Shortest-Job-First, SJF)

 CPU가 이용가능해지면, 가장 작은 CPU 버스트를 가진 프로세스에 할당한다. 만약 두 프로세스가 동일한 CPU 버스트 길이를 가진다면 선입 선처리 스케줄링을 적용한다. 이 스케줄링은 프로세스의 전체 길이가 아니라 다음 CPU 버스트의 길이에 의해 스케줄링이 되므로 최단 다음 CPU 버스트(shortest-next-CPU-brust)라고도 불린다. SJF은 평균 대기 시간 측면에서 최적이라는 장점이 있다.
 SJF는 비선점형(Non-preemptive)과 선점형(Preemptive) 두 가지 버전이 있다. 비선점형(Non-preemptive)은 CPU가 프로세스에 주어지면 선점될 수 없다. 선점형(Preemptive)은 현재 실행 중인 프로세스의 남은 시간보다 짧은 CPU 버스트 길이로 새 프로세스가 도착하면 선점한다. SJF의 선점형은 SRTF(Shortest-Remaining-Time-First)이라고도 한다.

예

아래와 같이 프로세스가 있고 해당 도착시간과 burst 시간을 갖는다고 하자.

Non-Preemptive SJF

Non-Preemptive SJF에서는  

대기 시간: P1 = 0, P2 = 6, P3 = 3, P4 = 7.

평균 대기 시간: (0 + 6 + 3 + 7)/4 = 4.

Preemptive SJF (Shortest-Remaining-Time-First, SRTF)에서는 

대기 시간:  P1 = 9, P2 = 1, P3 = 0, P4 = 2.

평균 대기 시간: (9 + 1 + 0 +2)/4 = 3.

CPU 버스트 길이 예측

 SJF 알고리즘이 최적이긴 하지만, 다음 CPU 버스트의 길이를 알 방법이 없기 때문에 CPU 스케줄링 수준에서는 구현할 수 없다. 한 가지 접근 방식은 SJF 스케줄링과 근사한 방법을 사용하는 것이다. 다음 CPU 버스트의 길이를 알 수는 없으나, 그 값을 예측 기대한다. 그러므로 다음 CPU 버스트가 이전의 버스트와 길이가 비슷하다고 기대한다. 그러므로 다음 CPU 버스트 길이의 근삿값을 계산해, 가장 짧은 예상 CPU 버스트를 가진 프로세스를 선택한다.

 다음 CPU 버스트는 일반적으로 측정된 이전의 CPU버스트들의 길이를 지수 평균한 것으로 예측한다. 지수 평균(exponential averaging)을 다음과 같이 정의할 수 있다.

• tn을 n번째 CPU 버스트의 길이라 한다.
• τn+1은 다음 CPU 버스트에 대한 예측값이라고 하자.
• 매개변수 α는 우리의 예측에서 최근의 값과 이전  값의 상대적 무게를 제어한다.(적응의 속도) 0 <=α<=1(일반적으로 α를 1/2로 설정)

α = 0이라면 τn+1 = τn이며, 최근 history에 아무 영향이 없다.(현재 조건들이 일시적인 것으로 간주) α = 1이라면 τn+1 = tn이며, 단지 가장 최근의 CPU 버스트만 중요시된다. (history는 오래되고 관계가 없는 것으로 간주)

Prediction of the length of the next CPU burst time

우선순위 스케줄링(Priority scheduling)

 SJF 알고리즘은 일반적인 우선순위 스케줄링 알고리즘의 특별한 경우이다. 우선순위가 각 프로세스들에 연관되어 있으며, CPU는 가장 높은 우선순위(SJF의 기준)를 가진 프로세스에 할당된다. 우선순위가 같은 프로세스들은 선입 선치리(FCFS) 순서로 스케줄 된다. SJF 알고리즘은 우선순위(p)가 예상되는 다음 CPU 버스트의 역인 단순한 우선순위 알고리즘이다. CPU 버스트가 클수록 우선순위가 낮으며, 그 역도 성립이 된다.

 우선순위 스케줄링은 우선순위 번호(정수)는 각 프로세스와 연결되며 우선순위가 가장 높은 프로세스에 CPU가 할당된다. 즉, 가장 작은 정수가 즉, 가장 높은 우선순위를 의미한다. 우선순위 스케줄링에는 기아(Starvation) 혹은 무한 봉쇄(Indefinite blocking)이라 불리는 주요 문제가 있다. 이 문제의 요점은 우선순위가 낮은 프로세스는 절대 실행되지 않을 수 있다는 것이다. 해결 방안으로 노화(Aging)가 있다. 노화는 시간이 지날수록 프로세스의 우선순위를 점진적으로 높여 문제를 해결한다.

라운드 로빈 스케줄링(Round Robin, RR)

 라운드 로빈(RR)은 일정한 시간 할당량(time quantum)을 가진 각 프로세스들을 번갈아 가며 실행하는 스케줄링 알고리즘이다. 라운드 로빈은 선입 선처리 스케줄링과 유사하지만 시스템이 프로세스들 사이를 옮겨 다닐 수 있도록 선점(Preemptive)이 추가된다. 시간 할당량(time quantum), 또는 타임슬라이스(time slice)라고 하는 작은 단위의 시간(보통 10-100밀리 초)을 정의한다. 준비 큐는 원형 큐(circular queue)로 동작한다. CPU스케줄러는 준비 큐를 돌면서 한 번에 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다. 준비 큐 n개의 프로세스가 있고 시간 할당량이 q이면 , 각 프로세스는 최대 q 시간 단위의 덩어리로 CPU시간의  1/n을 얻는다. 각 프로세스는 자신의 다음 시간 할당량이 할당될 때까지 ( n - 1) * q 시간 이상을 대기하지 않는다. 즉, 각 프로세스에 공평한 실행 시간을 보장하고, 짧은 응답 시간을 가지는 특징이 있다. RR 알고리즘의 성능은 시간 할당량의 크기에 매우 많은 영향을 받는다. q가 클 경우 RR 알고리즘은 FCFS과 다를 바 없다. 이와 반대로 q가 작을 경우 문맥 교환을 야기한다.

Time quantum and context switch time

예

아래와 같이 프로세스가 있고 해당 burst 시간을 갖는다고 하자.

시간 할당량(time quantum)이 2인 경우

The Gantt Chart for the schedule

응답 시간: P1 = 0, P2 = 2, P3 = 4, P4 = 6
평균 응답 시간: (0 + 2 + 4 + 6)/4 = 3.
일반적으로 SJF보다 평균 처리 시간이 높지만, 평균 응답 시간이 낮다.

Turnaround time varies with the time quantum.

다단계 큐 스케줄링(Multilevel Queue Scheduling)

다단계 큐(Multilevel Queue)

  우선순위와 라운드 로빈 스케줄링을 사용할 때 모든 프로세스가 단일 큐에 배치되고 스케줄러는 우선순위가 가장 높은 프로세스를 선택하여 실행하였다. 이번에는 프로세스 유형에 따라 프로세스를 여러 개의 개별 큐로 분할하기 위해 다단계 큐(Multilevel Queue) 스케줄링 알고리즘을 알아보자. 일반적으로 포그라운드 큐(대화형)와 백그라운 큐(배치)로 구분한다. 각 큐에는 자체 스케줄링 알고리즘이 있다. 예를 들어, 백그라운드 큐는 FCFS 알고리즘에 의해 스케줄 되는 반면, 포그라운드 큐는 RR알고리즘에 의해 스케줄 된다.

 큐와 큐 사이에 스케줄링도 반드시 있어야 하며, 일반적으로 고정 우선순위의 선점형 스케줄링으로 구현된다. 예를 들어, 실시간 큐는 대화형 큐보다 절대적으로 높은 우선순위를 갖는다. 각 큐는 낮은 우선순위의 큐보다 절대적인 우선순위를 가진다.(실시간 > 시스템 > 대화형 > 배치) 예를 들어, 실시간 프로세스, 시스템 프로세스, 대화형 프로세스를 위한 큐들이 모두 비어 있지 않으면 배치 큐에 있는 프로세스는 실행될 수 없다. 반대로, 배치 프로세스가 실행되고 있는 데, 대화형 프로세스가 준비 큐에 들어오면 배치 프로세스는 선점될 것이다. 하지만 이 방법은 기아(starvation)가 일어날 가능성이 있다.

 다른 방법으로 시간을 나누어 사용하는 것(Time slice)이다. 각 큐는 일정량의 CPU 시간을 얻어 자신 큐에 있는 다양한 프로세스들을 스케줄 할 수 있다. 예를 들어, 포그라운드-백그라운드 큐의 예에서, 포그라운드 큐는 자신의 프로세스들 사이에서 라운드 로딘 스케줄링을 위해 80%가 주어지고, 백그라운드 큐는 CPU 시간의 20%를 받아 자신의 프로세스들에 선입 선처리 방식으로 줄 수 있다.

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

 다단계 피드백 큐(Multilevel Feedback Queues) 스케줄링 알고리즘에서는 프로세스가 큐들 사이를 이동하는 것을 허용한다. 프로세스들을 CPU 버스트 성격에 따라서 구분한다. 어떤 프로세스가 CPU 시간을 너무 많이 사용하면, 낮은 우선순위의 큐로 이동된다. 일반적으로 다단계 피드백 큐 스케줄러는 다음의 매개변수에 의해 정의된다.

• 큐의 개수
• 각 큐를 위한 스케줄링 알고리즘
• 한 프로세스를 높은 우선순위 큐로 올려주는 시기를 결정하는 방법
• 한 프로세스를 낮은 우선순위 큐로 강등시키는 시기를 결하는 방법
• 프로세스에 서비스가 필요할 때 프로세스가 들어갈 큐를 결정하는 방법

A process can move between the various queues

---

스레드 스케줄링

다중 처리 스케줄링(Multi-Processor Scheduling)

 다중 프로세서 스케줄링은 두 가지 유형의 스케줄링으로 나눌 수 있다. 비대칭 다중 처리(Asymmetric multiprocessing)는  오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하기 때문에 간단하다. 이 접근 방식의 단점은 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목이 된다는 것이다. 대칭 다중 처리(Symmetric multiprocessing, SMP)는 각 프로세서는 스스로 스케줄링으로 현재 가장 일반적인 방법이다. 각 프로세스의 스케줄러가 준비 큐를 검사하고 실행할 스레드를 선택하여 스케줄링이 진행된다.
 다중 프로세서 스케줄링에는 스케줄링 알고리즘의 효율성과 성능에 중요한 이슈가 있다.

• 처리기 선호도(Processor affinity): 각 프로세스가 실행되는 처리기를 미리 지정하는 기술로 프로세스가 실행되는 동안 처리기를 변경하는 오버헤드를 줄이고 캐시 메모리 효율성을 높이는 데 도움이 된다.
• 부하 균등화(Load balancing): 여러 개의 프로세스에서 실행되는 프로세스 간의 작업 부하를 균등하게 분산하는 기술이다. 이를 통해 프로세스들이 골고루 실행되고 모든 처리기가 균등하게 작업을 수행하도록 할 수 있다.(Push migration, Pull migration)

NUMA and CPU Scheduling

NUMA(None Uniform Memory Access)

 SMP 시스템인 경우 효율성을 위해 모든 CPU를 로드된 상태로 유지해야 함

• 부하 균등화: 워크로드를 고르게 분산시키려는 시도
• Push 이주(Push migration): 주기적인 작업은 각 프로세서의 부하를 확인하고 발견되면 과부하된 CPU에서 다른 CPU로 작업을 푸시한다.
• Pull 이주(Pull migration): 유휴 프로세서는 바쁜 프로세서에서 대기 중인 작업을 가져온다.

Linux Scheduling

 타임 슬라이스(timeslice)로 시분할한다. 타임 슬라이스가 있는 프로세스만 실행할 수 있다. 타이머 인터럽트(timer interrupt)가 발생하면 타임슬라이스를 뺀다. 타임 슬라이스 = 0이면 다른 프로세스가 선택된다. 모든 프로세스의 타임슬라이스가 0인 경우 재계산을 수행한다. 선 순위가 가장 높은 프로세스가 항상 먼저 실행하는 실시간 우선순위(Real-time with priority) 방법을 사용하고 있다.(Linux는 타임 슬라이스로 우선 순위가 가장 높은 프로세스를 예약한다.)

Process with higher priority is given longer time slice.

알고리즘 평가(Algorithm Evaluation)

 평가 방법의 한 중요한 부류로 분석적 평가(Analytic Evaluation)가 있다. 분석적 평가에서는 주어진 작업 부하에 대한 알고리즘의 서능을 평가하는 공식이나 값을 생성하기 위해 주어진 알고리즘과 시스템 작업 부하를 이용한다.

결정론적 모델링(Deterministic modeling)

 결정론적 모델링(Deterministic modeling)은 사전에 정의된 특정한 작업 부하를 받아들여 그 작업 부하에 대한 각 알고리즘의 성능을 정의한다. 이 방법은 간단하고 빠르며 알고리즘을 설명하고 예제를 제공하는 데 유용하다.

E.g. 일련의 프로세스가 주어졌을 때 Gantt 차트가 포함된 SJF.

큐일 모델(Queueing models)

 큐잉 모델(Queueing)은 큐를 사용하여 시스템의 성능을 분석하는 수학적 모델링 기법이다. 이 모델은 다양한 형태의 대기역 시스템에서 발생하는 프로세스의 도착 패턴과 서비스 시간등을 고려하여 시스템의 특성을 분석한다. 프로세스들이 시스템에 도착하는 시간의 분포(도착 시간 분표)와 서비스 비용을 주어지며 이들을 이용하여 평균 처리량, 이용률, 대기 시간 등을 계산하는 것이 가능하다. 하지만 일부 평가에서 제한적으로 사용된다.

모의실험(Simulation)

 스케줄링 알고리즘을 더욱 정확하게 평가하기 위해서 모의실험(simulation)을 사용할 수 있다. 모의실험을 하는 것은 컴퓨터 시스템의 모델을 프로그래밍하는 것을 포함한다. 소프트웨어 자료구조가 시스템의 주요 구성요소(clock)를 표현한다. 모의실험을 구동하는 가장 보편적인 방법은 난수 발생기(Random number generator)로서, 이것은 확률 분포에 따라서 프로세스 수, CPU 버스트 시간, 도착, 출발 등을 생성하기 위해 프로그램된다. 모의실험은 컴퓨터를 오랜 시간 동안 사용하기 때문에 매우 큰 비용이 소요될 수 있다. 모의실험을 상세하게 할수록 더 정확한 결과를 얻을 수 있으나 컴퓨터 사용 시간을 더 필요로 하게 된다. 더구나 추적 파일은 대량의 저장 공간을 요구할 수 있다.

구현(Implementation)

 알고리즘을 평가하는 완전히 정확한 방법이지만 매우 어렵다. (algorithm coding, operating system modification)

---

핵심

• CPU 스케줄러는 실행할 준비가 된 프로세스 중에서 프로세스를 선택한다.
• 스케줄링 알고리즘의 목표는 CPU 사용률, 처리량을 최대화하고 처리 시간, 대기 시간, 응답 시간을 최소화하는 것이다.
• SJF(Shortest Job First)는 CPU 버스트 시간이 가장 짧은 프로세스에 CPU를 할당한다.
• 라운드 로빈 알고리즘(RR)에서 각 프로세스는 시간 양자라는 작은 CPU 시간 단위를 얻는다.
• Multilevel Feedback Queues 알고리즘에서 프로세스는 다양한 대기열 사이를 이동할 수 있다.

---

주섬주섬

 유휴란 컴퓨터 시스템이 사용 가능한 상태이나 실제적인 작업이 없는 시간을 의미한다.

참고

OS 1.기본개념