CPU 스케줄링

본 자료 정리는 'Operating System Concepts'(Tenth Edition) - Abraham Silberschatz 원서에 출처합니다.
Copyright © 2020 John Wiley & Sons, Inc.

Chapter5: CPU Scheduling

• Basic concept
• Scheduling Criteria
• Scheduling Algorithms
• Thread Scheduling
• Multiple-Processor Scheduling
• Real-Time CPU Scheduling
• Algorithm Evaluation

Objectives (목표)

• 다양한 CPU 스케줄링 알고리즘을 설명
• 특정 시스템에 대한 CPU 스케줄링 알고리즘을 선택하기 위한 평가 기준을 논의
• 멀티프로세서 및 멀티코어 스케줄링과 관련된 문제 설명
• 다양한 실시간 스케쥴링 알고리즘 설명
• CPU 스케줄링 알고리즘을 평가하기 위해 모델링과 시뮬레이션 적용

Basic Concepts

CPU 스케줄링은 다중 프로그램 운영체제의 기본이다. 운영체제는 CPU를 프로세스 간에 교환함으로써, 컴퓨터를 보다 생산적으로 만든다.

• CPU-I/O *Burst Cycle

  • 프로세스 실행은 CPU 실행과 I/O 대기의 주기(cycle)로 구성된다.
  • CPU burst 다음에 I/O burst가 뒤따른다.

( *Burst: 간헐적으로 특정량의 데이터를 주고 받는 것을 의미)

Histogram of CPU-burst Times

• CPU burst 의 지속시간

  • 그래프는 많은 수의 짧은 CPU 버스트 & 적은 수의 긴 CPU 버스트를 나타낸다.
    -> 즉, 짧은 CPU burst를 갖는 process가 대부분이다.
    -> 가급적 짧게 이용할 수 있도록 해야 효율적이다. (대기시간이 줄어들기 때문)

CPU Scheduler

cpu 스케줄러는 ready queue에 있는 프로세스 중에서 선택하고 그 중 하나를 선택해 CPU를 할당한다.
-Queue may be ordered in various ways

CPU 스케줄링 결정은 프로세스가 다음과 같은 경우 발생할 수 있다.

1) 실행 상태에서 대기 상태로 전환 (running -> waiting)
2) 실행 상태에서 준비 상태로 전환 (running -> ready)
3) 대기 상태에서 준비 상태로 전환 (waiting -> ready)
4) 종료 상태 (terminates)

1,4번의 경우 스케줄링 면에서 선택의 여지가 없다. 실행을 위해 새로운 프로세스가 반드시 선택되어야 한다.

하지만 2,3번의 경우 선택의 여지가 있다.

만약 1,4번에서만 스케줄링이 발생할 경우, 비선점 또는 자발적 (nonpreemptive)이라고 한다.

다른 모든 경우는 선점 (preemptive)이라고 한다.

• 공유 데이터에 대한 엑세스 고려
• 커널 모드에서 선점 고려
• 중요한 OS 활동 중에 발생하는 인터럽트 고려

비선점 스케줄링 (nonpreemptive) 에서는 일단 CPU가 한 프로세스에 할당되면 프로세스가 종료하든지, 또는 대기 상태로 전환해 CPU를 방출할 때까지 점유한다. 최신 운영체제들은 선점 스케줄링 알고리즘을 사용한다.

Dispatcher

Dispatcher 모듈은 CPU 스케줄러가 선택한 프로세스에 CPU 제어를 제공한다.

이는 다음과 같은 작업을 포함한다.

• 한 프로세스에서 다른 프로세스로 context switch
• user mode로 전환
• 프로그램을 다시 시작하기 위해 사용자 프로그램의 적절한 위치로 이동

디스패치 지연 (dispatch latency) 은 디스패처가 하나의 프로세스를 정지하고 다른 프로세스의 수행을 시작하는 데까지 소요되는 시간을 의미한다.

Scheduling Criteria

서로 다른 CPU 스케줄링 알고리즘들은 다른 특성을 가진다. 이는 여러 기준에 따라 달라지는데, 사용되는 기준은 다음과 같다.

• CPU 이용률 (CPU utilization) : CPU를 가능한 바쁘게 유지시키는 것

• 처리량 (throughput) : 시간당 실행을 완료하는 프로세스 개수

• 총 처리 시간 (turnaround time) : 특정 프로세스를 실행하는 데 걸리는 시간. ready queue에서 대기한 시간, CPU에서 실행하는 시간, I/O를 수행하는 시간의 합계.

• 대기 시간 (wating time) : ready queue에서 대기한 시간의 합계

• 응답 시간 (response time) : 요청이 제출된 후 첫 번째 응답이 시작될 때까지 소요된 시간(시분할 환경의 경우). 즉 응답이 시작되는 데까지 걸리는 시간

Scheduling Algorithm Optimization Criteria

• Max CPU utilization
• Max throughput
• Min turnaround time (처리 시간)
• Min waiting time
• Min response time

Scheduling Algorithms

• First-Come, First-Served(FCFS) Scheduling
• Shortest-Job-First (SJF) Scheduling
• Round-Robin (RR) Scheduling
• Priority Scheduling
• Multilevel Queue Scheduling
• Multilevel Feedback Queue Scheduling
  

First-Come, First-Served(FCFS) Scheduling

프로세스가 P1, P2, P3 순으로 도착했다고 가정해보자.
간트 차트로 나타내면 다음과 같다.

대기 시간: P1 = 0, P2 = 24, P3 = 27
평균 대기 시간: (0+24+27)/3 = 17

FCFS 방법의 가장 큰 단점은 convoy effect이다.
convoy effect란 긴 프로세스 뒤에 짧은 프로세스가 오는 것인데 이 경우 프로세스 대기 시간이 길어지므로 비효율적이다.

FCFS Scheduling

이번엔 프로세스가 P2, P3, P1 순으로 도착했다고 가정해보자.
간트 차트로 나타내면 다음과 같다.

대기 시간: P1 = 6, P2 = 0, P3 = 3
평균 대기 시간: (6+0+3)/3 = 3

전의 예시보다 훨씬 효율적이다.
FCFS는 비선점(Nonpreemptive) 알고리즘이다.

Shortest-Job-First (SJF) Scheduling

• CPU가 다음 CPU 버스트 시간이 가장 작은 프로세스에 할당된다.

• SJF는 최적의 스케쥴링 방법이다. 주어진 프로세스 집합에 대한 최소 평균 대기시간을 제공한다.

• 새로 도착한 프로세스의 다음 CPU 버스트는 현재 실행 중인 프로세스의 남은 시간보다 짧을 수 있다.

  • Nonpreemptive SJF: 현재 실행 중인 프로세스에서 CPU 버스트를 완료할 수 있다. (끝날 때까지 뺏기지 않는다.)

  • Preemptive SJF: 현재 실행 중인 프로세스를 선점한다. 이를 Shortest-Remaining-Time-First라고 부른다.

Example of SJF

• SJF scheduling chart

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

Example of Shortest-Remaining-Time-First

지금까지는 도착시간이 0인 비선점 SJF만 봤다면, 이제부터는 다양한 도착 시간과 선점(preemptive)의 개념을 분석에 추가한다.

Preemptive SJF 간트 차트

P1이 가장먼저 도착해서 CPU burst를 실행했지만 그 다음 도착한 P2의 CPU Burst가 짧으므로 선점당했다. 그 후로는 CPU burst time이 짧은 P4가 실행하고, P1의 남은 burst time이 7로 P3의 burst time보다 짧으므로 P1, P3 순으로 간트 차트가 그려진다.

대기 시간은 서비스 받기 시작한 시간 - 도착 시간으로 계산한다.

평균 대기 시간: [(10-1)+(1-1)+(17-2)+5-3)]/4= 26/4 = 6.5 msec

Example of Nonpreemptive SJF

같은 문제를 Nonpreemptive SJF로 풀면 다음과 같다.
평균 대기 시간: [(0-0)+(8-1)+(12-3)+(17-2)]/4= 31/4 = 7.5 msec

같은 문제를 FCFS로 풀면 다음과 같다.
평균 대기 시간: [(0-0)+(8-1)+(12-2)+(21-3)]/4= 35/4 = 8.75 msec

직접 간트 차트를 그려보며 상황을 보면 이해가 쉬울 것이다.

Determining Length of Next CPU Burst 1

• 문제는 다음 CPU 요청의 길이를 아는 것이다.

• 길이를 추정하려면 과거의 CPU burst 사용기록을 기준으로 다음 CPU burst를 예측해야한다.

• 지수 평균화(exponential averaging)를 사용하여 이전 CPU 버스트의 길이를 사용하여 다음 CPU burst를 예측할 수 있다.

Prediction of the Length of the Next CPU Burst

Determining Length of Next CPU Burst 2

Round-Robin (RR) Scheduling

• 각 프로세스는 CPU 시간(시간 퀀텀 q)의 작은 단위(일반적으로 10-100밀리초)를 얻는다. 이 시간이 경과하면 프로세스가 미리 준비되어 ready queue의 끝에 추가된다.

• ready queue에 프로세스가 n개 있고 시간 퀀텀이 q이면 각 프로세스는 CPU 시간의 1/n을 최대 q 시간 단위로 한 번에 청크한다. (n-1)q 시간 단위를 초과하여 대기하는 프로세스는 없다.

• Timer는 다음 프로세스를 예약하기 위해 모든 퀀텀을 중단한다.

• 성능은 시간 퀀텀 q의 크기에 따라 달라진다.

  • q large => FCFS

  • q small => q는 context switch와 관련하여 커야 한다, 그렇지 않으면 오버헤드가 너무 높다.

Example of RR (Time Quantum = 4)

간트 차트는 다음과 같다.

평균 대기 시간: [(10-4)+4+7]/3 = 17/3 = 5.66 msec

• 일반적으로 SJF보다 평균 대기 시간과 소요 시간이 높지만 응답 시간이 더 빠르다.
• q는 context switch 시간에 비해 커야 한다.
• q는 일반적으로 10ms ~ 100ms, context switch < 10 microsec.

Time Quantum and Context Switch Time

• time quantum이 적을 수록 context switch가 증가한다.
  • 프로세스 실행을 늦춘다.

Turnaround Time Varies With The Time Quantum

Priority Scheduling

• 우선 순위 번호(정수)가 각 프로세스와 연결된다.

• CPU가 우선순위가 높은 프로세스에 할당된다.(가장 작은 정수 = 가장 높은 우선순위를 가짐)

  • Preemptive

  • Nonpreemptive

• SJF는 우선 순위 스케줄링이며, 여기서 우선 순위는 예측된 다음 CPU 버스트 시간의 역이다.

문제점

• Starvation(아사): 낮은 우선수위의 프로세스는 아예 실행되지 않을 수 있다. (무한대기)
  -> ready queue에서 대기만 하다가 서비스를 못받고 굶어죽음

해결책

• Aging(노화) : 오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시킨다.
• Round-robin과 우선순위 스케쥴링 결합 -> 가장 우선순위가 높은 프로세스를 실행하고 RR을 사용하여 동일한 우선순위로 프로세스를 실행한다.

Example of Priority Scheduling

간트 차트는 다음과 같다.

평균 대기 시간 : 8.2 msec

Example of Combining Priority & RR Scheduling

간트 차트는 다음과 같다.

Multilevel Queue Scheduling

• ready queue가 분할되어 우선순위마다 별도의 queue를 분리된 형태

• 우선순위 스케쥴링이 round-robin과 결합될 때 잘 작동된다.

• 일반적으로 우선순위는 각 프로세스에 통계적으로 할당된다.

• 프로세스는 실행시간 동안 동일한 queue에 남아있다.

Multilevel Queue Scheduling 2

• 프로세스 유형에 따라 ready queue를 분리한다.

각각의 queue에는 고유한 스케쥴링 알고리즘이 있다.

• foreground - RR
• background - FCFS

Thread Scheduling

사용자 스레드와 커널 스레드의 차이점은 스케쥴링 방식이다. 대부분의 현대 운영체제들은 프로세스가 아니라 커널 스레드가 OS에 의해 스케쥴링된다.

• Many-to-one 과 Many-to-Many 모델의 경우 스레드 라이브러리가 사용자 스레드를 LMP에 대해 스케쥴링한다. 이것을 Process-contention scope(PCS)라고 한다.

  • 동일한 프로세스에 속하는 스레드 간의 스케쥴링 경쟁

  • 일반적으로 프로그래머가 설정한 우선순위를 통해 수행됨

(이때, 스레드 라이브러리가 사용자 스레드를 LWP에 스케줄링한다는 것은 스레드가 실제 CPU에서 돌게한다는 것과는 다른 의미이다.)

• 사용 가능한 CPU에 의해 스케쥴된 커널 스레드는 System-contention scope(SCS)라고 부른다.
  • SCS 스케쥴링 사용시 시스템의 모든 스레드 간 CPU 점유 경쟁
  • one-to-one model을 사용하는 시스템은 오로지 SCS만 사용한다.

Multi-Processor Scheduling

지금까지는 코어 하나일 때만 다뤘다. 코어 여러 개이면(multiple CPUs) 부하 분담 load sharing을 통해 여러 스레드가 병렬적으로 돌 수 있게 되어 더 복잡해진다. (당장 단일 코어의 경우에서도 최적의 해라는 게 존재하지 않았기 때문)

보통 multiprocessor라는 말은 물리적인 프로세서가 여럿인 경우를 칭한다.

Multiprocessor은 다음 구조를 의미한다.

• Multicore CPUs

• Multithreaded cores

• NUMA systems

• Heterogeneous multiprocessing

-> 이 중 multicore cpu, multithreaded cores, NUMA systems는 다중 프로세서 내의 동종 프로세서 이다.

이 구조를 바탕으로 다중 프로세서 스케쥴링에 대해 다룰 것이다.

Approaches to Multiple-Processor Scheduling

Asymmetric multiprocessing : 단 하나의 프로세서가 모든 스케줄링 결정, I/O 처리 및 시스템 활동을 처리하는 것이다. 즉 마스터 서버가 처리하게 하는 것이다. 다른 프로세서는 사용자 코드만 실행한다.

-> 한 코어만 시스템 자료 구조에 접근하니까 자료 공유의 필요성도 줄어들어 단순해짐. 단점이라면 마스터 서버가 병목점이 되어 전체 성능이 낮아질 수도 있다.

Symmetric multiprocessing(SMP) :

각 프로세서는 자기 스스로 스케줄링한다. (대부분의 다중 프로세서 처리기법)
각 스케줄러가 준비 큐를 확인하고 실행할 스레드를 선택한다. 이후 스레드 스케줄링하려고 구조화할 때 다음의 두 가지 방법으로 구조화한다.

1) 모든 스레드가 동일한 ready queue를 사용한다.
2) 각 프로세서마다 개인 스레드 queue를 가진다. (most common)

사실상 모든 현대적인 운영체제(윈도우즈, 리눅스, macOS, 안드로이드, iOS 등)가 SMP를 지원하므로 앞으로 CPU 스케줄링 알고리즘은 전부 SMP 체제에서 발생하는 것들이다.

Multicore Processors

보통 SMP 체제는 여러 개의 물리적인 프로세서를 바탕으로 프로세스를 병렬 처리했었다. 하지만 요즘 현대적인 컴퓨터 하드웨어는 동일한 물리적 칩에 여러 프로세서 코어를 배치하여 Multicore processor 구조를 이용한다. (더 빠르고 더 적은 전력을 소모하기 때문)

하지만 다중 코어 프로세서 때문에 스케줄링이 조금 복잡해진다. 예를 들어 프로세서가 메모리에 접근을 할 때, 해당 메모리의 자료를 사용할 수 있을 때까지 대기하는 시간이 꽤 오래걸린다. 이를 메모리 지연 memory stall이 발생했다고 한다. (프로세서가 메모리보다 빨라서 발생) 이 뿐만아니라 캐시미싱(캐시 메모리에 없는 자료에 접근) 때문에 발생하기도 한다.

메모리 지연의 경우 프로세서는 자료 사용할 수 있을 때까지 대기하는데 자기 시간의 50%를 사용하게 된다.

이 상황을 처리하기 위해 현대적인 하드웨어 설계는 두 개 이상의 하드웨어 스레드 (hardware thread)가 각 코어에 할당되는 다중 스레드 프로세싱 코어(Multithreaded processing cores)를 구현한다. 이 방식을 이용하면 한 하드웨어 스레드가 메모리 대기하느라 지연되면 코어는 다른 스레드로 교환할 수 있다.

Chip Multithreading(CMT)

운영체제 입장에서는 각 하드웨어 스레드가 각자 구조적 상태(명령어 포인터, 레지스터 집합 등)를 유지하므로 마치 소프트웨어 스레드를 돌릴 수 있는 논리 CPU로 보인다.
이 기술을 칩 멀티스레딩 (chip multithreading(CMT))이라 부른다.
아래 그림의 경우 프로세서가 4 개의 연산 코어를 갖고, 각 코어마다 2개의 하드웨어 스레드를 가진다. 운영체제 입장에서는 논리 CPU가 여덟 개인 것이다.

• multiple hardware threads to a single processing core

인텔 프로세서는 하이퍼 스레딩 hyper-threading(동시 멀티스레딩 simultaneous multithreading :SMT)이라는 용어로 여러 하드웨어 스레드를 한 프로세서 코어에 할당한다.

Two levels of scheduling

멀티스레드 멀티코어 프로세서에는 두 가지 다른 수준의 스케줄링이 필요하다.

물리적인 코어의 자원들(캐시, 파이프라인 등)이 반드시 하드웨어 스레드 간 공유가 되어야 한다. 그러므로 프로세싱 코어는 한 순간에 한 스레드만 실행이 가능하다. 따라서 아래 그림에서처럼 사실상 멀티스레드 다중 코어 프로세서는 두 가지 스케줄링 단계를 가진다.

(이 부분이 실질적으로 제일 중요해서 이 챕터에서 그동안주로 다루었던 것이다. 위의 스케줄링 방법 중 하나를 고르면 된다.)

1) 운영체제가 어떤 소프트웨어 스레드를 어떤 하드웨어 스레드(논리 CPU)에 돌릴지를 결정할 스케줄링 결정 [그림.level1]

2) 코어가 어떤 하드웨어 스레드를 실행시킬지를 결정하는 스케쥴링 [그림.level2]

-> 전략 1) 단순히 라운드 로빈 알고리듬으로 하드웨어 스레드를 프로세싱 코어에 스케줄링하기
-> 전략 2) 각 하드웨어 스레드에 동적 긴급도 할당(0~7)

Load Balancing

SMP 체계의 경우 효율성을 위해 모든 CPU를 로드된 상태로 유지해야 한다. 따라서 부하 분산 (load balancing) 을 통해 프로세스 간 작업을 고르게 분산해서 다중 프로세서의 이득을 최대한 땡겨야한다.

일반적으로 크게 두 가지 방법이 있다.

• Push migration: 주기적인 작업은, 현재 각 프로세서의 부하를 확인하고, 불균형하다 싶으면 불균형이 발견되면 과부하된 CPU에서 유휴 또는 사용량이 적은 CPU로 스레드를 푸시한다.

• Pull migration: 유휴 프로세서(놀고있는 프로세서)는 바쁜 프로세서에서 대기 중인 작업을 가져온다.

( 푸시, 풀 이동은 딱히 상호 배타적일 필요가 없고, 사실 부하 균형 체제에서 병렬적으로 구현하는 편이다.)

Processor Affinity

스레드가 프로세서에서 돌 때 스레드에서 자주 접한 자료가 프로세서의 캐시에 들어간다.(이를 "따뜻한 캐시"라고 부른다)

근데 스레드가 부하 분산 등의 이유로 다른 프로세서로 가면 새로운 프로세서에 의해 캐시 메모리 내용이 다른 내용으로 채워지게 된다.

이렇게 기존 캐시 무효화하고 새 캐시로 채우는 과정이 비싼 연산이기 때문에 SMP 지원하는 대부분의 운영체제들은 스레드를 프로세서 간 이동시키는 걸 좀 피하고자 한다.

따라서 최대한 따뜻한 캐시를 유지하려는 것. 이것을 프로세서 친화도 processor affinity라고 한다.

운영체제가 최대한 프로세스를 같은 프로세서에서 돌게 정책을 짰더라도, 그걸 보장하지 않으면 약친화도 soft affinity를 갖는다. 여기선 프로세스를 단일 프로세서에 유지하려고 시도하지만 load balanbing 중에 프로세스가 다른 프로세서로 이동될 수 있다.

반대의 경우는 강친화도 hard affinity로, 프로세스가 자기가 돌 프로세서들을 지정하는 것이다.

대부분의 체제들은 둘 다 갖고 있음. 시스템의 주메모리 구조도 프로세서 친화도에 영향을 준다. (e.g, NUMA)

아래 그림은 각자 CPU와 지역 메모리를 갖는 물리적인 프로세서 칩 두 개에서의 비균등 메모리 접근(NUMA)이다. NUMA 체제에서 CPU 간 상호연결해서 서로 같은 메모리 공간을 사용하더라도 당연히 남의 메모리보다는 자기 메모리 접근이 더 빠르다. 만약 운영체제의 CPU 스케줄러와 메모리 배정 알고리듬이 NUMA를 인식하고 있다면 특정 CPU에 스케줄링된 스레드는 해당 CPU와 제일 가까운 메모리에 할당이 될 것이다.

load balanbing은 프로세서 친화도가 주는 이득과 반대로 작동하기도 한다. 스레드를 다른 프로세서로 넘겨버리기 때문에.. NUMA 체제에서도 마찬가지로 프로세서 간 이동하면 페널티가 있다. 애초에 load balanbing이랑 메모리 접근 시간 줄이는 거랑 자연스레 경쟁 관계가 된다. 그래서 요즘 다중 코어 NUMA 체제에서 스케줄링하는 알고리즘은 상당히 복잡하다. 이후 리눅스 CFS 스케줄링 알고리즘으로 이 두 가지 토끼를 어떻게 잡는지 균형 잡는 법을 볼 것이다.

Heterogeneous Multiprocessing

지금까지는 프로세서가 전부 동일한 기능을 갖는다고 가정했다.

모바일도 이젠 다중 코어 구조지만 코어끼리 명령어 집합은 같은데 클럭 속도나 전력 관리가 서로 다를 수도 있다. 이런 체제가 바로 불균등 다중 프로세싱 heterogeous multiprocessing(HMP)이다.

(비대칭 다중 프로세싱이랑 다른 것이다. HMP의 경우 전력 관리 때문에 하는 것)

e.g. ARM processor in mobile - big.LITTLE

ARM 프로세서 중 HMP 지원하는 애들을 big.LITTLE이라고 한다.

• 고성능인 big cores : 짧은 기간 동안 더 많은 에너지를 소비 (e.g. user-interactive한 부분 실행)

• 에너지 효율적인 little cores : 더 적은 에너지를 사용하여 더 오랜 기간 동안 사용 (e.g. background 처리 실행)

• 절전 모드에서 에너지 집약적인 빅 코어를 비활성화할 수 있다.

윈도우즈 10에서 HMP 스케줄링 지원해서 전력 관리 요구에 적합한 스케줄링 정책 선택했다.

Real-Time CPU Scheduling

Real-time scheduling에는 Soft real-time systems와 Hard real-time systems가 있다. 보통 임베디드시스템(로봇청소기 드론..)에 사용된다.

• soft real-time system : 중요한 실시간 프로세스가 언제 스케쥴되는지에 대한 보장 없음
  (따라서 우선 순위가 있는 스케쥴링 -> soft real-time system이 되도록 함)
• hard real-time system : 기한까지 작업을 서비스해야 함
  (e.g. 자율주행자동차의 충돌감지)

Minimizing Latency

실시간 체제가 이벤트 기반임을 우선 알아야 한다. 이벤트란 냉장고 온도감지 및 조절, 충돌 감지와 같은 것을 말한다.

보통 이벤트 발생할 때까지 대기하다가 이벤트가 발생하면 최대한 빠르게 대응해야하는데, 이때 이벤트 발생 시간부터 서비스된 시간까지를 이벤트 지연 속도 event latency라 부른다.

이벤트 별로 지연속도 요소가 다르다.

실시간 체제의 성능에 영향을 주는 두 가지 지연 속도:

• 인터럽트 지연 속도
• 디스패치 지연 속도

인터럽트 지연 속도란 인터럽트가 CPU에 도착하는 시점부터 이에 대응하는 서비스가 시작할 때까지를 의미한다. 인터럽트가 발생하면 운영체제는 일단 실행 중이던 명령어 끝내고 나서 무슨 인터럽트인지 확인한다. 현재 프로세스의 상태를 저장하고 특정 인터럽트 서비스 루틴(ISR)에 따라 서비스를 한다. 이때 걸린 총 시간이 인터럽트 지연 속도이다.

지연 속도 줄이는 게 좋음. 특히 hard real-time system이면 이걸 단순히 줄이는 게 아니라, 체제의 소요까지 맞춰줘야한다.

인터럽트 지연 속도에 기여하는 요소 중 하나가 커널 자료 구조가 갱신 중에 얼마나 인터럽트가 비활성화되느냐이다. 실시간 운영체제에서는 인터럽트를 정말 짧은 시간만 비활성화해야한다.

Dispatch Latency

한 프로세스를 멈추고 다른 걸 실행하기 위한 디스패처를 스케줄링하는데 걸리는 시간이 디스패치 지연 속도 (dispatch latency) 이다.

CPU에 즉시 접근해야하는 작업의 경우 이 지연 속도도 줄여야한다. 가장 효과적인 방법은 선점적인 커널을 제공하는 것이다. hard real-time system의 경우 보통 몇 ms 수준이다.

디스패치 지연 속도의 충돌 단계 conflict phase는 두 성분으로 구성된다.

• 커널에서 도는 임의의 프로세스 선점
• 우선순위가 높은 프로세스가 필요한 자원을 우선순위가 낮은 프로세스에서 뺏기

(충돌 단계 이후엔 디스패치 단계가 우선순위가 높은 프로세스를 CPU에 스케줄링한다.)

Priority-based Scheduling

실시간 운영체제에서 제일 중요한 기능은 실시간 프로세스가 CPU가 필요할 때 즉시 대응하는 것이다. 그러므로 실시간 운영체제는 반드시 선점적 우선순위 기반 알고리즘이어야 한다.

선점적 우선순위 기반 알고리즘은 soft real-time system만 보장한다. 따라서 hard real-time system을 위해 마감 기한을 맞춰야 하므로 추가적인 스케쥴링 기능이 필요하다. 따라서 앞으로는 hard real-time system에 대한 내용만을 다룬다.

각 스케줄러 다루기 전에 스케줄링할 프로세스의 특징을 봐야한다.

우선 프로세스는 p시간마다 한 번씩 interrupt가 발생한다. t는 interrupt를 처리하는 시간이고 d (deadline)안에 꼭 처리해줘야 한다.

이 관계는 0 ≤ t ≤ d ≤ p이다. 주기적 작업의 주기율 rate은 1/p이다.
이를 바탕으로 스케줄러가 프로세스의 마감 기한이나 주기율 소요를 바탕으로 우선순위 배정한다.

Rate Montonic Scheduling

비율 단조 (rate-monotonic) 스케줄링 알고리즘이란 정적 우선순위 정책을 통해 주기적 작업을 선점적으로 스케줄링하는 것이다. 주기적 작업은 시스템에 들어온 순간 자기 주기의 역수를 우선순위로 가진다.

• 주기가 길면 우선순위가 낮다.

• 주기가 짧으면 우선순위가 높다.

이 정책을 하는 이유는 CPU를 자주 쓰는 애한테 우선순위 계속 주기 위함이다.

Rate Montonic Scheduling 알고리즘을 적용하지 않고 그냥 실행하는 예를 보면 다음과 같다.

Example 1:

• p1=50, t1=20 / p2=100, t2=35

• deadline: 다음 기간이 시작될 때까지 CPU 버스트 완료

• CPU 활용도: t/p = 20/50 + 35/100 = 0.4 + 0.35 = 0.75
  (총 75%로 마감기한을 지킬 수 있음)

• P2가 P1보다 높은 우선순위를 할당받았다고 가정
  

p1의 deadline을 놓치게 된다. 즉 우선 순위가 낮은 애는 처리하지 못할 수 있다.

하지만 만약 Rate Montonic 스케쥴링을 적용하면 P1의 우선순위가 더 높아질 것이다.

Example 2:

• p1=50, t1=20 / p2=100, t2=35

• Use the rate-montomic scheduling

• P1이 P2보다 높은 우선순위를 가진다.

rate-montomic 스케쥴링은 프로세스가 이 알고리즘에 의해 스케줄링이 안된다면, 정적 우선순위를 갖는 다른 모든 알고리즘에서도 스케줄링이 안된다는 점에서 최적이다. 이 예시는 다음과 같다.

Example 3:

• p1=50, t1=25 / p2=80, t2=35

• CPU 활용도: t/p = 25/50 + 35/80 = 0/94

• rate-montomic scheduling에 의해 P1이 P2보다 높은 우선순위를 가진다.

이 경우 P2가 deadline을 놓치게된다.

rate-montomic 스케쥴링은 정적 우선순위를 사용하여 최적이다. 하지만 한 가지 한계점이 있다.

• CPU 효율이 유계이고, 언제나 CPU 자원을 100%로 최대화하기 힘들다. N 프로세스에 대한 CPU 효율 최악의 경우:

Earliest Deadline First Sheduling (EDF)

최단 마감 우선 earliest-deadline-first(EDF) 스케줄링은 마감 기한에 따라 우선순위가 동적으로 지정된다.

마감 기한이 빠른 순으로 우선순위 부여한다.

• 마감기간이 빠른경우, 높은 우선순위

• 마감기간이 느린 경우, 낮은 우선순위

(실행하는 과정에서 계속 우선순위가 바뀌므로 CPU 효율성이 좋다.)

프로세스가 실행 가능할 때 반드시 시스템에 자기 마감 기한 소요를 알려서 우선순위 갱신해야한다. (rate-montomic scheduling처럼 정적 우선순위가 아님)

Example:

• p1=50, t1=25 / p2=80, t2=35

deadline이 짧은 P1이 우선순위가 높다.

rate-montomic scheduling과 달리 프로세스가 굳이 주기적이지 않아도 되고, 버스트 당 상수 CPU 시간을 필요로 하지도 않는다. 실행 가능할 때 마감 기한만 스케줄러한테 알려주면 된다. 이론적으론 최적이고, CPU 효율도 100%라는 점에서 매력적이다.

하지만 프로세스 간 문맥 교환이랑 인터럽트 처리 때문에 현실적으로 100%의 CPU 효율은 불가능한다.

Proportional Share Scheduling

비례적 proportional share 스케줄러는 모든 어플리케이션에 T만큼의 지분을 할당한다. 어플리케이션은 N 개의 시간 지분을 받을 수 있어 모든 어플리케이션이 총 프로세서 시간의 N/T를 가진다. (e.g. 총 T = 100의 지분이 있으면, A, B, C에 각각 지분을 50, 15, 20으로 준다.)

Example:

• Total T = 100 지분

• A: 50지분, B: 15지분, C: 20지분

• 만약 새로운 프로세스 D가 30 지분을 요청하면, 거절한다.
  (85+30 = 115, but total T=100)

수정할 부분이 있으면 댓글 달아주세요