[운영체제] 5. CPU Scheduling

해당 내용은 공룡책(Operating System Concepts 10th Ed. : Abraham Silberschatz, Peter Baer Galvin, Greg Gagne)과 대학 강의를 기반으로 재구성하여 정리한 공부 내용입니다.

1. 기본 개념(Basic Concepts)

멀티 프로그래밍의 목적은 CPU 이용률을 최대화하기 위해 항상 실행 중인 프로세스를 갖는 것

한 프로세스가 대기해야 할 경우 운영체제는 그 프로세스로부터 CPU를 회수하여 다른 프로세스에 할당한다.

 

CPU-I/O 버스트 사이클(CPU-I/O Burst Cycle)

프로세스 실행은 CPU 실행과 I/O 대기의 사이클로 구성된다.

CPU 버스트로 시작되어 I/O 버스트와 두 상태가 교대로 발생하다가 실행 종료를 위한 시스템 요청으로 끝난다.

CPU 버스트의 분포는 CPU 스케줄링 알고리즘에 중요하다. (대기 시간과 반응 시간을 줄이는 효과적 스케줄링 정책)

CPU bound 프로그램들은 계산 중심적; 다수의 긴 CPU 버스트를 가짐

I/O bound 프로그램들은 입출력 연산 중심; 짧은 CPU 버스트를 많이 가짐

 

CPU 스케줄러(CPU Scheduler)

CPU가 유휴 상태가 되면 운영체제는 준비 큐에 있는 프로세스 중 하나를 실행해야 한다.

→ CPU 스케줄러가 수행; 실행 준비가 된 메모리 내 프로세스 중 하나를 선택하고 CPU를 할당한다.

* 선택은 스케줄러가, 할당은 디스패처가 진행

준비 큐는 반드시 선입선출(FIFO) 큐일 필요는 없다. 다양한 표현 가능!

 

선점 및 비선점 스케줄링(Preemptive and Nonpreemptive Scheduling)

CPU 스케줄링 결정 상황:

1. 한 프로세스가 실행 상태에서 대기 상태로 전환될 때(I/O 요청 등으로 wait() 호출 시)

2. 프로세스가 실행 상태에서 준비 완료 상태로 전환될 때(인터럽트 발생 시)

3. 프로세스가 대기 상태에서 준비 완료 상태로 전환될 때(I/O 종료 시)

4. 프로세스 종료 시

 

상황 1과 4의 경우: nonpreemptive(비선점) 또는 cooperative(협조적); 반드시 새로운 프로세스가 선택되어야 함

상황 2와 3의 경우: preemptive(선점) (모든 최신 운영체제들이 사용)

- 여러 프로세스가 공유된 데이터(메모리)에 접근하고 있는 경우(데이터 일관성 파괴. Sol. Atomic operation), 커널이 시스템 콜을 처리 중인 경우, 운영체제가 중요한 작업을 수행하고 있는 경우...

 

+) 구체적인 상황들

• 스레드가 시스템 콜 끝에 I/O를 요청하여 블락될 때: 스레드를 블락 상태로 만들고 스케줄링(CPU 활용률 향상 목적)
• 스레드가 자발적으로 CPU를 반환할 때: yield() 시스템 콜 등을 통해 자발적으로 반환되면 커널은 현재 스레드를 준비 리스트에 넣고, 새로운 스레드 선택(CPU의 자발적 양보) *yield(): 현재 실행 중인 스레드가 스스로 실행을 일시 중단하고 다른 스레드에게 실행 기회 제공
  스레드의 타임 슬라이스가 소진되어 타이머 인터럽트 발생 시(균등한 CPU 분배 목적)
• 더 높은 순위의 스레드가 요청한 입출력 작업이 완료되어 인터럽트 발생: 현재 스레드를 강제 중단(선점)시켜 준비 리스트에 넣고 높은 순위의 스레드를 깨워 스케줄링(우선순위를 지키기 위한 목적)

마지막 상황의 경우:

대기 상태의 프로세스가 기다리는 I/O 작업 완료 시 인터럽트 시그널을 통해 CPU에 통지 → CPU는 커널 모드로 전환해 현재 프로세스 컨텍스트(레지스터, PC 상태 등)를 PCB/TCB에 커널 스택에 저장 후 중지 → CPU가 인터렙트 벡터 테이블을 참조하여 인터럽트 핸들러(ISR)의 시작 메모리 주소를 찾아 PC에 로드  → ISR은 해당 인터럽트를 처리하기 위한 서비스 루틴 실행 → ISR 내 또는 이후 단계에서 해당 프로세스/스레드 상태를 레디로 변경 및 레디 큐에 삽입 → OS 스케줄러가 레디 큐에서 대기 중인 우선 순위가 높은 프로세스/스레드 선택 → 실행 중인 프로세스의 상태를 ready로 전환 → 디스패처 호출 → 선택된 프로세스/스레드의 컨텍스트 복원 → 사용자 모드로 전환

디스패처(Dispatcher)

Dispatcher: CPU 코어의 제어를 CPU 스케줄러가 선택한 프로세스에 주는 모듈

수행:

1) 한 프로세스에서 다른 프로세스로 문맥을 교환하는 일

2) 사용자 모드로 전환하는 일

3) 프로그램을 재시작하기 위해 사용자 프로그램의 적절한 위치로 jump하는 일

 

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

가능한 한 빨리 수행되어야 함!

---

2. 스케줄링 기준(Scheduling Criteria)

• CPU 이용률(CPU utilization): 가능한 한 CPU를 최대한 바쁘게 유지해야 함
• 처리량(throughput): 단위 시간 당 완료된 프로세스 개수
• 총처리 시간(turnaround time): 프로세스가 시스템에 도착(생성)된 후 완료까지 걸린 시간. 프로세스의 제출 시간과 완료 시간의 간격. 준비 큐에서 대기한 시간부터 CPU 실행, I/O 시간을 모두 합한 시간. 사용자 입장
• 대기 시간(waiting time): 프로세스가 준비 큐에서 머무르는 시간의 합. OS와 사용자 입장
• 응답 시간(response time): 대화식 시스템에서 사용자에 대한 응답 시간. 요청 후 응답받을 때까지의 시간. 사용자 입장

---

3. 스케줄링 알고리즘(Scheduling Algorithms)

선입 선처리 스케줄링(First-Come, First-Served Scheduling, FCFS)

CPU를 먼저 요청하는 프로세스가 CPU를 먼저 할당받는다.

호위 효과(convoy effect): 모든 다른 프로세스들이 하나의 긴 프로세스가 CPU를 양도하기를 기다리는 것.

→ 하나의 CPU bound 프로세스와 많은 I/O bound 프로세스가 존재하는 경우: CPU 독점 문제

→ 자원 활용도 낮음

비선점형 스케줄링; CPU가 한 프로세스에 할당되면 그 프로세스가 종료하거나 I/O를 요청해 CPU를 방출할 때까지 CPU를 점유하기 때문에 특히 대화형 시스템에서 한 프로세스가 지나치게 오랫동안 CPU를 점유

하도록 하면 손해가 크다.

 

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

각 프로세스의 CPU 버스트 길이를 이용하여, CPU 버스트 길이가 작은 순으로 프로세스를 할당한다.

주어진 프로세스 집합에 대해 최소의 평균대기 시간을 가진다는 점에서 최적이다.

But 다음 CPU 버스트의 길이를 알기 어려움

→ Estimation(예측); 이전 버스트와 길이가 비슷할 것이다.

→ 이전의 CPU 버스트들의 길이를 지수 평균(exponential averaging)한 것으로 예측

α=0이면: 최근 히스토리가 아무 영향이 없음

α=1이면: 가장 최근의 CPU 버스트만 중요시

* 일반적으로 α=1/2로 설정: 최근과 과거가 같은 무게를 가짐

지수 평균은 가중치가 지수적으로 감소하는 이동 평균 방법; 최근 데이터에 더 큰 가중치를 부여해 현재 추세를 반영한다.

 

앞의 프로세스가 실행되는 동안 새로운 프로세스가 준비 큐에 도착하였는데, 새로운 프로세스가 현재 실행되고 있는 프로세스의 남은 시간보다도 더 짧은 CPU 버스트를 가질 수도 있음. (선택 문제)

• 선점형 SJF 스케줄링

= 최소 잔여 시간 우선(shortest remaining time first) 스케줄링

현재 실행하고 있는 프로세스를 선점하고 새로운 프로세스를 스케줄

장점: 대기 시간을 줄이고 시스템 응답 시간을 향상시킨다.

 

• 비선점형 SJF 스케줄링

현재 실행하고 있는 프로세스가 자신의 CPU 버스트를 끝내도록 허용

 

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

타임 슬라이스라고 하는 작은 단위의 시간을 정의

→ 각 프로세스는 작은 단위의 CPU 시간 (time quantum(slide), q)를 갖는다. (보통 10~100밀리초)

CPU 스케줄러가 준비 큐를 돌면서 한 번에 한 프로세스에 한 번의 시간 할당량 동안 CPU를 할당한다.

준비 큐에서 첫 번째 프로세스를 선택해 시간 할당량 이후에 인터럽트를 걸도록 타이머를 설정 후, 프로세스를 디스패치

→ 만약 CPU 버스트가 시간 할당량보다 길어 타이머가 끝나면 운영체제에 인터럽트를 발생하여 문맥 교환이 일어나고 실행하던 프로세스가 준비 큐의 끝에 넣어진다.

 

준비 큐에 n개의 프로세스가 있고, 시간 할당량이 q이면:

각 프로세스는 최대 q시간 단위로 CPU 시간의 1/n을 얻는다.

각 프로세스는 자신의 다음 시간 할당량이 할당될 때까지 (n-1) × q 시간 이상을 기다리진 않는다.

 

RR 알고리즘의 성능은 시간 할당량 q의 크기에 매우 많은 영향을 받는다.

q가 매우 크면 → FIFO와 같다.

q가 매우 작으면 → 매우 많은 문맥 교환 발생 → 오버헤드가 매우 높아질 수 있음

→ 시간 할당량 q가 문맥 교환 시간보다 크길 원함

→ 문맥 교환 시간은 일반적으로 10usec(마이크로초) 미만이다. 매우 작음!

 

총처리 시간(turnaround time)도 시간 할당량의 크기에 좌우된다.

대부분의 프로세스가 단일 시간 할당량 안에 다음 CPU 버스트를 끝낸다면 평균 총처리 시간이 개선된다.

But 너무 크면 FCFS 정책으로 퇴보하므로, CPU 버스트의 80%는 시간 할당량보다 짧아야 적당하다.

SJF는 최소 평균 대기 시간을 제공하지만, 긴 버스트 시간을 가진 프로세스는 매우 오랜 시간 대기할 수 있다(Starvation 현상 초래)

→ RR이 SJF보다 총처리 시간이 크다는 단점이 있으나, 프로세스에게 균등한 기회를 제공하여 더 나은 응답 시간을 갖는다.

 

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

SJF 알고리즘은 우선순위가 예상되는 다음 CPU 버스트 시간의 역인 우선순위 스케줄링의 일종이다.

우선 순위 수는 각 프로세스에 연관된 정수로ㅡ, CPU는 높은 우선순위의 프로세스를 할당하게 된다.

* 낮은 수가 높은 우선순위를 나타낸다고 가정

 

선점형 스케줄링: 새로 도착한 프로세스의 우선순위가 현재 실행되는 프로세스의 우선순위보다 높으면 CPU 선점

비선점형 스케줄링: 준비완료 큐의 가장 앞 부분에 새로운 프로세스를 넣는다.

 

문제점: 기아 상태(Starvation) = 무한 봉쇄(indefinite blocking)

낮은 우선순위의 프로세스가 영원히 실행되지 못 하는 경우

 

솔루션: 노화(Aging)

시간 진행에 따라 프로세스의 우선 순위를 증가시킴

오랫동안 시스템에서 대기하는 프로세스들의 우선순위를 점진적으로 증가시켜 실행되도록 함

 

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

레디 큐를 여러 개의 개별 큐로 분할

ex. foreground(interactive, 대화형) 프로세스와 background(batch, 배치) 프로세스를 구분

 

각 큐는 자체 스케줄링 알고리즘을 가질 수 있다.

ex. foreground는 RR 알고리즘, background는 FCFS 알고리즘에 의해 스케줄

 

프로세스는 영구적으로 주어진 큐에만 있는다. (다른 큐로 옮겨가지 않는다.)

→ 스케줄링 오버헤드에 장점, but 융통성이 적음

 

스케줄링은 큐와 큐 사이에도 이루어져야 한다.

→ 일반적으로 고정 우선순위의 선점형 스케줄링(Fixed priority scheduling)으로 구현

ex. foreground의 모든 프로세스가 처리되어야 background 프로세스가 처리됨

→ 기아 현상 발생 가능성 높음

→ 타임 슬라이스 활용; 각 큐가 정해진 CPU 시간 할당량을 얻어 자기 큐의 프로세스들을 스케줄하게 함

→ foreground 큐가 CPU 시간의 80%를 받아 자신의 프로세스에 RR로 사용하고, background 큐는 CPU 시간의 20%를 받아 FCFS로 자신의 프로세스에 줄 수 있음

 

다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling, MLFQ)

프로세스가 큐 사이를 이동하는 것을 허용; 프로세스들을 CPU 버스트 성격에 따라 이동시킴

→ 노화(aging) 형태가 구현될 수 있다. → 기아 상태 예방

 

큐는 준비 상태의 프로세스를 저장함

큐마다 프로세스가 머무를 수 있는 큐 타임슬라이스 존재 → 낮은 레벨의 큐일 수록 더 긴 타임 슬라이스 가짐

 

알고리즘:

프로세스는 도착 시 최상위 레벨 큐에 삽입됨

가장 높은 레벨 큐에서부터 프로세스를 선택

높은 레벨에 있는 큐에 프로세스가 도착하면 이에 의해 선점됨

프로세스 CPU 버스트가 큐 타임 슬라이스를 초과하면 하위 레벨 큐로 이동시킴

프로세스가 자발적으로 중단한 경우(I/O 처리 등)에는 현재 소속한 큐 끝에 삽입

큐에 있는 시간이 오래 되면 기아를 막기 위해 상위 레벨 큐로 점차 이동

최하위 레벨 큐는 주로 FCFS나 긴 타임 슬라이스의 RR로 스케줄됨

 

다단계 피드백 큐 스케줄러를 정의하는 매개변수:

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

 

4개의 우선순위 레벨을 가진 예시:

---

4. 스레드 스케줄링(Thread Scheduling)

최신 운영체제에서의 스케줄 대상은 프로세스가 아니라 커널 수준의 스레드이다.

 

경쟁 범위(Contention Scope)

사용자 수준 스레드와 커널 수준 스레드를 구별

 

다대일 또는 다대다 모델을 구현하는 시스템에서 스레드 라이브러리는 유저 레벨 스레드를 가용한 LWP(Light Weight Process) 상에서 스케줄된다.

= process-contention scope(PCS, 프로세스 경쟁범위); 동일한 프로세스에 속한 스레드 사이에서 CPU를 경쟁하는 기법

실제로 스레드가 CPU상에서 실행되려면 운영체제가 LWP의 커널 스레드를 물리적인 CPU 코어로 스케줄해야 한다.

프로그래머가 지정한 우선순위에 따라 행해진다.

 

CPU상에 어느 커널 스레드를 스케줄할지 결정하기 위해 커널은 system-contention scope(SCS, 시스템-경쟁 범위); 시스템 상의 모든 스레드 사이에서 CPU를 경쟁하는 기법을 사용한다.

Windows나 Linux 같은 일대일 모델을 사용하는 시스템은 SCS만을 이용해 스케줄함

 

Pthread 스케줄링(Pthread Scheduling)

API는 스레드 생성 동안 PCS나 SCS를 지정할 수 있다.

PTHREAD_SCOPE_PROCESS: PCS 스케줄링을 사용하여 스레드를 스케줄

PTHREAD_SCOPE_SYSTEM: SCS 스케줄링을 사용하여 스레드를 스케줄

---

5. 다중 처리기 스케줄링(Multiple-Processor Scheduling)

CPU 스케줄링은 여러 개의 CPU를 사용할 수 있을 때 더욱 복잡해진다.

기능이 동질한 프로세서들이 있는 시스템의 경우, 동질하지 않은 프로세서들이 있는 시스템의 경우

 

다중 처리기 스케줄링에 대한 접근 방법(Approaches to Multi-Processor Scheduling)

Asymmetric multiprocessing(비대칭 다중 처리): 오직 하나의 코어만 시스템 자료구조에 접근하여 자료 공유의 필요성을 배제하여 간단함

마스터 서버(master server)라고 칭하는 하나의 프로세서가 모든 스케줄링 결정과 I/O 처리, 다른 시스템의 활동을 취급하게 하고, 다른 프로세서들은 사용자 코드 수행만 하게 함

→ 단점: 마스터 서버가 전체 시스템 성능을 저하할 수 있는 병목 현상

 

Symmetric multiprocessing(SMP): 각 프로세서가 스스로를 스케줄링; 각 프로세서의 스케줄러가 레디 큐를 검사하고 실행할 스레드를 선택. 표준 접근 방식!

 

스케줄 대상이 되는 스레드를 관리하기 위한 전략:

• 1. 모든 스레드가 공통(공유) 레디 큐에 존재할 수 있다. (Shared Ready Queue)

장점: 스레드의 관리 중앙화(Centralized management of threads)

단점:

Race Conditions(경쟁 조건); 다중 프로세서가 동일한 스레드를 스케줄하지 않도록, 큐에서 스레드가 없어지지 않도록 보장해야 함

→ Locking(락킹): 경쟁 조건으로부터 공통 준비 큐를 보호하기 위한 기법 사용

→ But 큐에 대한 모든 액세스에 락 소유권이 필요하여 락킹 경쟁 증가 → 공유 큐 액세스가 성능의 병목이 될 수 있음

 

• 2. 각 프로세서는 자신만의 스레드 큐를 가질 수 있다. (Private Per-Processor Run Queues)

장점:

경합(contention) 감소: 각 프로세서가 자신만의 실행 큐에서 스레드를 스케줄하여 공유 실행 큐와 관련한 성능 문제X, 락을 최소화

성능 향상: 간섭 감소, 프로세스별 큐가 있어 캐시 메모리를 효율적으로 사용(캐시 일관성 문제와 캐시 미스 감소, 캐시에 데이터 보관해 전체 시스템 성능 향상)

단점:

큐마다 부하의 양이 다를 수 있음 (But 균형 알고리즘을 사용해 해결)

 

→ 2번 방식이 더 선호됨!

 

처리기 선호도(Processor Affinity)

프로세스가 현재 실행 중인 프로세서에 대한 선호도를 보이는 것

soft affinity(약한 선호도): 운영체제가 동일한 프로세서에서 프로세스를 실행시키려고 노력하는 정책을 가지고는 있지만 보장하지 않는 경우

hard affinity(강한 선호도): 시스템 콜을 통해 프로세스가 자신이 실행될 프로세서 집합을 명시할 수 있음 ex. Linux

 

NUMA(Non-Uniform Memory Access): 각 CPU 노드가 자체 메모리를 가지고 있어 로컬 메모리에 빠른 접근이 가능하나 다른 CPU 메모리 접근은 느림(비대칭)

→ 프로세스 선호도가 중요

 

부하 균등화(Load Balancing)

SMP 시스템에서 멀티 프로세서를 최대한 활용하려면 부하를모든 프로세서에 균등하게 배분하는 것이 매우 중요

부하 균등화(Load balancing): SMP 시스템의 모든 프로세서 사이에 부하가 고르게 배분되도록 시도

 

두 가지 일반적인 접근법:

1) Push migration: 특정 태스크가 주기적으로 각 프로세서의 부하를 검사, 불균형 상태면 과부하인 프로세서에서 쉬고 있거나 덜 바쁜 프로세서로 스레드를 이동(push)시킴

 

2) Pull migration: 쉬고 있는 프로세서가 바쁜 프로세서를 기다리고 있는 프로세스를 pull할 때 발생

 

→ 두 방식이 상호 배타적일 필요는 없고, 실제로 종종 병렬적으로 구현됨

 

OS에서 스케줄링과 로드 밸런싱의 목적:

스케줄링: 레디 큐의 프로세스에 우선 순위를 정해서 CPU에 할당

로드 밸런싱: 스템의 모든 프로세서 또는 노드가 균등한 작업 부하를 가지도록 자원 분산

차이:

1) Scope; 스케줄링은 단일 시스템 내 프로세스/스레드 우선 순위 선택에 초점, 로드 밸런싱은 다수의 시스템 또는 프로세서 사이의 작업 부하를 조정

2) 동적,정적; 각 프로세스의 우선 순위는 보통 정적, 로드 밸런싱은 시스템의 실시간 상태를 반영해 동적으로 조정

 

다중 코어 프로세서(Multicore Processors)

현대 컴퓨터 하드웨어는 동일한 물리적 칩 안에 여러 개의 처리 코어를 장착하여 멀티 프로세서를 구성

→ 각 CPU가 각 물리 칩을 가지는 시스템보다 더 빠르고 적은 전력을 소모한다.

 

메모리 스톨 문제(Memory Stall Explanation):

프로세서가 메모리에 접근할 때 데이터가 가용해지기를 기다리면서 많은 시간을 허비하는 상황

주로 최신 프로세서가 메모리보다 훨씬 빠른 속도로 작동하여 속도 차이로 발생

프로세서가 메모리를 기다리느라 최대 50%의 시간을 허비하고 있는 상태

 

Solution: 다중 스레드 처리 코어(Multithreaded Multicore System) 구현

하나의 코어에 2개 이상의 하드웨어 스레드가 할당

→ 메모리를 기다리는 동안 하나의 하드웨어 스레드가 중단되면 코어가 다른 스레드로 전환 가능

 

 

Chip Multithreading(CMT): 각 코어가 다중 하드웨어 스레드를 가지고 있는 것

OS의 관점에서 각 하드웨어 스레드는 논리적 CPU로 보인다.

(n개의 코어가 있고, 각 코어에 m개의 하드웨어 스레드가 있으면 운영체제에 n*m개의 논리적 CPU 제공)

하이퍼 스레딩(Hyper-Threading, 동시 다중 스레딩;simultaneous multithreading, SMT): Inter 프로세서가 단일 하드웨어 코어에 여러 하드웨어 스레드를 할당하는 것을 설명하기 위해 사용한 용어

각 코어에 두 개의 독립적인 스레드를 할당하여 동시에 처리할 수 있게 함 → 하드웨어 수준에서 멀티스레딩 구현

한 코어가 한 스레드의 메모리 요청을 처리하는 동안 다른 스레드가 연산 작업을 계속할 수 있게 해준다.

---

6. 실시간 CPU 스케줄링(Real-Time CPU Scheduling)

실시간 운영체제에서 PCU를 스케줄링할 때에는 특정 시간 내에 작업을 완료해야; 시간이 중요한 개념!

 

Soft real-time systems: 중요한 실시간 프로세스가 스케줄되는 시점에 관해 아무런 보장을 하지 않음

Hard real-time systems: 태스크가 반드시 데드라인까지 서비스를 받아야 함(엄격)

 

지연시간 최소화(Minimizing Latency)

실시간 시스템의 이벤트 기반 특성: 시스템이 일반적으로 특정 이벤트 발생을 기다렸다가, 이벤트가 발생하면 시스템이 가능한 빨리 응답하고 그에 맞는 정해진 동작을 수행한다.

 

이벤트 지연 시간(Event Latency): 이벤트가 발생해서 그에 맞는 서비스가 수행될 때까지의 시간

= 이벤트 E가 처음 발생한 시점(t_0)부터, 실시간 시스템이 그 이벤트 E에 대해 의미 있는 반응 또는 서비스를 시작하는 시점(t_1)까지의 시간

이벤트 지연 시간은 단순히 하나의 지연 요소가 아니라 여러 지연 요소들이 합쳐진 결과이다.

 

인터럽트 지연시간(Interrupt Latency): CPU에 인터럽트가 발생한 시점부터 해당 인터럽트 처리 루틴(ISR)이 시작하기까지의 시간

인터럽트 서비스 루틴 실행 시간: 이벤트 발생을 알리고 필요한 초기 작업을 수행하는 ISR 코드 자체의 실행 시간

태스크 준비 및 스케줄링 지연 시간: ISR이 이벤트를 처리할 메인 태스크를 레디 상태로 만들고, 스케줄러가 이 태스크를 인지하는 시간

디스패치 지연 시간(Dispatch Latency): 스케줄링 디스패처가 하나의 프로세스를 블록시키고 다른 프로세스를 시작하는 데까지 걸리는 시간

= 준비 상태가 된 메인 태스크가 실제로 CPU를 할당받아 실행을 시작하기까지 걸리는 시간

- 문맥 교환 시간

- 충돌 해결 시간

태스크 실행 시간: 태스크가 실행을 시작해서 실제로 반응이라고 할 수 있는 동작을 하는 데 걸리는 시간

 

디스패치 지연시간의 충돌 단계:

1. 커널에서 동작하는 프로세스에 대한 선점

- 커널 모드 작업 중에는 운영체제의 핵심 데이터를 변경하거나 중요한 자원을 락하고 사용하는 경우가 많은데, 이런 작업 중 함부로 실행을 중단시키면 시스템 전체에 문제 발생 가능

2. 높은 우선순위의 프로세스가 필요한 자원을 낮은 우선순위 프로세스 자원이 방출

- 낮은 우선순위 프로세스가 작업을 수행하기 위해 특정 자원을 필요로 할 때

 

우선순위 기반 스케줄링(Priority-Based Scheduling)

실시간 운영체제의 스케줄러는 선점을 이용한 우선순위 기반 스케줄링을 지원해야만 한다.

→ soft real-time systems에 대해서도 마감 시간 내에 실시간 태스크가 수행되는 것을 보장해야 함

 

스케줄될 프로세스들의 특성 정의:

1. 프로세스들은 주기적이다(periodic); 프로세스들은 일정한 간격으로 CPU가 필요하다.

각 주기 프로세스들이 CPU 사용권을 얻었을 때마다 고정된 수행 시간 t, CPU로부터 반드시 서비스를 받아야 하는 마감시간 d와 주기 p가 정해져 있다. (0 ≤ t ≤ d ≤ p)

주기 태스크의 실행 빈도(Rate)는 1/p

 

Rate-Monotonic 스케줄링(Rate-Monotonic Scheduling)

각 작업의 주기가 짧을 수록, 즉 더 자주 수행되어야 할 수록 더 높은 우선순위를 부여 = 주기에 따른 우선순위 부여

주기가 짧은 태스크는 높은 우선순위 / 주기가 긴 태스크는 낮은 우선순위 배정

최적의 기법!

 

가정사항:

주기 프로세스들의 처리 시간은 각각 CPU 버스트와 같다.

각 프로세스의 마감 시간은 그 프로세스의 다음 주기가 시작하기 전에 CPU 사용을 완료해야 함을 의미한다.

각 프로세스의 CPU 이용률 = 수행시간 / 주기 = t/p

→ 마감 시간을 충족시키는지를 알 수 있다.

 

CPU 이용률은 한계가 있기 때문에 CPU 자원을 최대화해서 사용하는 것은 불가능하다.

고정 우선순위 스케줄링 시스템에서 모든 태스크가 데드라인 이내에 완료될 수 있는지 확인하기 위한 필요 조건:

N개의 프로세스를 스케줄 하는 데 있어 최악의 경우 CPU 이용률은

이다.

N=1: CPU 이용률은 100%

N=2: CPU 이용률은 최대 83%

→ 이 이하여야 마감 시간을 만족시키는 것을 보장할 수 있다.

N이 증가함에 따라 CPU 이용률은 69%까지 떨어진다.

 

Earliest Deadline First 스케줄링(Earliest Deadline First Scheduling)

마감시간에 따라 우선순위를 동적으로 부여

마감시간이 빠를 수록 우선순위가 높아지고, 늦을 수록 낮아진다.

 

정책:

프로세스가 실행 가능하게 되면 자신의  마감시간을 시스템에 알려 우선순위가 새로 실행 가능하게 된 프로세스의 마감시간에 맞춰 재조정된다.

 

이론적으로 최적인 기법!

 

일정 비율의 몫 스케줄링(Proportionate Share Scheduling)

모든 응용 프로그램에 고정된 수 T개의 시간 몫(Shares)을 할당하여 동작

한 개의 응용 프로그램이 N개의 시간 몫을 할당받으면 그 응용 프로그램은 모든 프로세스 시간 중 N/T 시간을 할당받는 것

 

ex. T=100인 시간 몫(Shares)이 있고, 3개의 프로세스에 할당하는 경우:

A 프로세스에 50 몫 할당 = 모든 프로세서 시간의 50%를 할당받는 것

B 프로세스에 15 몫 할당 = 모든 프로세서 시간의 15%를 할당받는 것

C 프로세스에 29 몫 할당 = 모든 프로세서 시간의 20%를 할당받는 것

 

응용 프로그램이 시간 몫을 할당받는 것을 보장하는 승인 제어 정책(admission control)과 함께 동작해야만 함

→ 사용 가능한 충분한 몫이 존재할 때, 그 범위 내 몫을 요구하는 클라이언트에게만 실행을 허락해줌

 

POSIX 실시간 스케줄링(POSIX Real-Time Scheduling)

POSIX.1b standard 제공; 실시간 컴퓨팅용 확장

실시간 스레드를 위하여 제공하는 두 개의 스케줄링 클래스:

SCHED_FIFO: FIFO 큐를 사용하여 FCFS 정책에 따라 스레드를 스케줄

SCHED_RR: 라운드 로빈 정책 사용, 같은 우선순위의 스레드에 시간 할당량을 제공

 

스케줄링 정책에 관한 정보를 set하고 get하는 두 개의 함수 제공:

pthread attr getsched policy(pthread attr t *attr, int *policy)

pthread attr setsched policy(pthread attr t *attr, int policy)