1. Introduction to Scheduler

가. Scheduler?

Thread Scheduler(이하 Scheduler)는 실행 중인 thread을 CPU에서 제거하고, 특정 알고리즘에 따라 다른 thread를 선택하는 역할을 한다. 기본적으로 여러 개의 실행 가능한 threads을 번갈아가며 실행시키는 기능을 하는 것이다.

일반적으로 thread는 다음과 같이 세 가지 상태를 가진다.

1) States

① 실행(running) 상태: 현재 CPU에 의해 실행 중인 상태

② 준비(ready) 상태: 실행할 준비가 되었지만 CPU를 할당받지 못한 상태

③ 차단(blocked) 상태: 사용자 입력 같은 이벤트를 기다리는 상태

어떤 한 순간에는 오직 하나의 thread만 실행 상태에 있을 수 있다. 나머지 threads은 준비 상태나 차단 상태에 있게 된다.

2) State Transition

① 준비 상태 → 실행 상태

• 현재 실행 중인 thread가 실행을 마쳤거나, 할당된 시간이 끝났거나, 혹은 준비 상태의 스레드가 더 높은 우선순위를 가질 경우 전환
• 어떤 경우가 적용될지는 사용 중인 스케줄링 알고리즘에 따라 달라짐

② 실행 상태 → 준비 상태

• 실행 중인 thread의 시간이 끝나거나, 준비 상태의 thread가 더 높은 우선순위를 가질 때 전환

③ 실행 상태 → 차단 상태

• 실행 중인 thread가 어떤 이벤트(예: 일정 시간 경과, I/O 장치 입력, 데이터 버스 사용 가능, 사용자 입력 등)를 기다려야 할 때 차단 상태로 이동

④ 차단 상태 → 준비 상태

• thread가 기다리던 이벤트가 발생했을 때, 그리고 현재 실행 중인 thread와 같은 우선순위거나 낮은 우선순위를 가질 때 준비 상태로 이동

⑤ 차단 상태 → 실행 상태

• 차단 상태에서 이벤트가 해결된 스레드가 현재 실행 중인 스레드보다 더 높은 우선순위를 가진다면, 바로 실행 상태로 전환될 수도 있음

즉, thread는 세 가지 상태를 오가며 동작하고, 매 순간 오직 하나의 thread만 실행 상태에 있게 된다.

2. Classification of Schedulers

Scheduling 알고리즘 여러 방식으로 분류할 수 있다. 그중 범용적인 분류 방법은 정적(static) vs 동적(dynamic), 선점형(pre-emptive) vs 비선점형(non pre-emptive) 이다.

분류 기준	종류	설명
우선순위 결정 시점	Static	thread의 우선순위가 시스템 실행 전에 미리 결정된다.
	Dynamic	시스템 실행 도중에 thread의 우선순위가 결정된다.
CPU 점유 방식	Pre-emptive	실행 중인 thread는 주기적 인터럽트나 더 높은 우선순위 스레드에 의해 중단될 수 있다.
	Non Pre-emptive	실행 중인 thread는 명시적으로 CPU를 양보하지 않는 한 실행을 끝마칠 때까지 CPU를 사용한다.

추가로, 다음과 같이 하나의 스케줄링 알고리즘이 두 가지 분류 체계에 동시에 속할 수 있다.

• 정적 선점형 스케줄러
• 정적 비선점형 스케줄러
• 동적 선점형 스케줄러
• 동적 비선점형 스케줄러

그러나 정적-동적 스케줄러나 선점형-비선점형 스케줄러 같은 조합은 성립하지 않는다.

※ Preemption(선점)?
Preemption이란 OS가 thread을 실행 상태에서 준비 상태로 옮기는 것을 말한다.

보통 thread가 실행 상태에서 차단 상태로 이동할 때는 OS가 아니라, thread 스스로 실행을 멈추는 것이다. 왜냐하면 thread가 실행을 멈추는 이유는, 당장 실행을 계속할 수 없어서 어떤 이벤트가 일어나기를 기다려야 하거나, 아니면 맡은 일을 모두 끝내 더 이상 실행할 필요가 없기 때문이다.

하지만 실행 상태에서 준비 상태로 이동할 때는 OS의 스케줄러가 개입하는 것이다. OS 스케줄러가 이렇게 하는 이유는 모든 thread에 공정성(fairness)을 보장하거나, 사용 중인 선점형 알고리즘에 따라 특정 데드라인(deadline)을 맞추기 위해서이다.

3. Scheduler Criteria

스케줄러는 여러 가지 기준에 따라 성능을 평가할 수 있다. 대표적인 기준은 다음과 같다.

평가 기준	설명
처리율 (Throughput)	단위 시간당 완료되는 작업(태스크)의 수
턴어라운드 타임 (Turnaround Time)	각 작업이나 스레드가 시작부터 완료까지 걸리는 총 시간
응답 시간 (Response Time)	요청이 들어온 시점부터 첫 응답이 반환될 때까지 걸리는 시간
CPU 이용률 (CPU Utilization)	사용 가능한 CPU 사이클 중 실제로 사용된 사이클의 비율(%)
대기 시간 (Wait Time)	각 작업이 준비(Ready) 상태 큐에서 대기하는 시간

※ CPU Utilization?
보통 대문자 U로 표기한다. 앞서 언급했듯이, 이는 사용 가능한 CPU 사이클 중 실제로 사용된 사이클의 비율을 의미한다.

예를 들어, CPU를 80 MHz에서 실행한다고 가정하겠다. 이는 1초에 8천만(80 million) 사이클이 존재한다는 뜻이다. 그리고 만약 OS가 이 중 4천5백만(45 million) 사이클을 사용한다면, CPU 이용률은

가 된다. 즉, 실제로 사용된 CPU 자원의 비율이 56.25%라는 뜻이다.

다른 관점에서 보면, 1초마다 3천5백만 사이클(43.75%)이 낭비되고 있다는 의미이기도 하다. 이는 바람직하지 않으며, OS를 설계할 때는 CPU 자원이 최대한 활용되도록 좋은 스케줄링 알고리즘을 만들어야 한다.

RTOS에서 CPU Utilization을 계산하는 방법은 간단하다. 각 작업이 실행되는 최대 실행 시간을 그 작업의 주기(period)로 나눈 값을 모두 더하면, 그것이 해당 OS의 CPU 이용률이 된다.

4. Scheduling Algorithm

가. Optimization Goal

Scheduling 알고리즘에서 목표하는 바는 다음과 같다.

• 단위 시간당 완료되는 작업의 수(처리율, throughput) 최대화

• 각 작업이 완료되는 데 걸리는 시간(턴어라운드 타임, turnaround time) 최소화

• 응답 시간(response time) 최소화

• CPU 이용률 최대화

• 스케줄링 오버헤드(scheduling overhead) 최소화

여기서 스케줄링 오버헤드란, 스케줄링 결정을 내리고 한 작업에서 다른 작업으로 전환하는 데 소요되는 시간을 의미한다.

나. First Come First Served(FCFS) Scheduler

1) Introduction

FCFS 스케줄러는 먼저 도착한 작업이 먼저 실행되는 방식으로 동작한다. 비선점형(non-preemptive) 스케줄러이므로, 한 thread가 실행을 시작하면 실행이 끝날 때까지 CPU를 빼앗을 수 없다.

• 장점: 단순한 구현
• 단점: 실행 시간이 짧은 thread가 긴 thread 뒤에 오면 대기 시간이 길어짐(Convoy Effect)

2) Example: Four threads(A, B, C, D)

thread	도착 시간 (ms)	실행 시간 (ms)	시작 시간 (ms)	종료 시간 (ms)	대기 시간 (ms)	턴어라운드 타임 (ms)
A	0	5	0	5	0	5
B	1	3	5	8	4	7
C	2	8	8	16	6	14
D	3	6	16	22	13	19

계산 결과는 다음과 같다.

• 평균 대기 시간

  $(0 + 4 + 6 + 13) ÷ 4 = 5.75ms$

• 평균 턴어라운드 타임

  $(5 + 7 + 14 + 19) ÷ 4 = 11.25ms$

• 처리율 (Throughput)

  $(총 스레드 수) ÷ (총 실행 시간) = 4 ÷ 22 = 0.18 threads/ms$

나. Round Robin(RR) Scheduler

1) Introduction

RR Scheduler은 선점형(pre-emptive), 정적(static) 스케줄링 알고리즘으로, time sharing 방식을 사용한다. 각 thread가 일정한 시간(quantum)만큼만 CPU를 사용한 뒤, ready queue의 뒤로 돌아가며 차례를 기다리는 구조이다.

① 장점

• 모든 thread가 CPU 시간을 공평하게 배분받는다.
• 응답 시간이 일정 수준 보장되어 대화형(Interactive) 시스템에서 효과적이다.

② 단점

• Quantum 크기 설정이 성능에 큰 영향을 준다.
• Quantum이 너무 크면 FCFS와 유사
• Quantum이 너무 작으면 컨텍스트 스위칭 오버헤드가 커짐

2) Example: Five Threads(Quantum = 10ms)

스레드	도착 시간 (ms)	실행 시간 (Burst Time, ms)	남은 실행 시간 변화
A	0	17	17 → 7 → 완료
B	40	17	17 → 7 → 완료
C	15	10	10 → 완료
D	90	10	10 → 완료
E	120	30	30 → 20 → 10 → 완료

3) time quantum 선택 시 고려사항

RR Scheduling에서 time quantum의 크기는 성능과 효율성에 큰 영향을 준다. Quantum을 잘못 설정하면 FCFS처럼 동작하거나, 컨텍스트 스위칭 비용이 과도하게 발생할 수 있다.

퀀텀 크기	특징
매우 큼	FCFS와 유사하게 동작 → 선점 효과 사라짐
적당함	이상적인 라운드 로빈 → 각 스레드가 공정하게 CPU 사용
매우 작음	시분할 효과 극대화 → 각 스레드가 마치 독점하는 듯 실행되지만 컨텍스트 스위칭 비용 급증

4) Context Switching 비용

• Quantum 크기가 작아질수록 컨텍스트 스위칭 횟수 증가
• 컨텍스트 스위칭에는 고정된 비용(시간)이 발생 → CPU 사이클 낭비
• Rule of Thumb: Quantum 크기는 반드시 컨텍스트 스위칭 시간보다 훨씬 커야 한다.

※ Example: Burst Time = 10ms (스레드 1개)

퀀텀 (ms)	실행 과정	컨텍스트 스위칭 횟수
12	스레드가 10ms에 완료 → 전환 없음	0회
6	6ms 실행 → 1회 선점 → 4ms 실행 후 완료	1회
1	1ms마다 선점 → 총 9회 선점 발생	9회

만약 컨텍스트 스위칭 1 회에 2 ms가 소요된다면, 퀀텀이 1일 때 9 × 2 = 18 ms 낭비인 것이다.

다. Weighted Round Robin Scheduler

Weighted RR은 기본적으로 RR Scheduler와 동일하다. 따라서 선점형(preemptive)이며, 시분할(time sharing)을 사용하고, time quantum이 소진되면 OS가 thread를 선점한다.

하지만 Weight RR Scheduling에서는 여기에 더해 thread 별로 weight를 부여한다. Weight가 큰 thread는 더 많은 time quantum을 할당받게 된다.

1) How to Implement

① 가중치 파라미터 부여 방식
각 thread에 weight 파라미터를 부여한다. Scheduler는 thread을 실행시킬 때, 그 thread의 weight에 비례하여 time quantum의 배수를 할당한다.

예를 들어, time quantum을 10 ms로 하고, 5 개의 thread A, B, C, D, E가 있다고 하겠다.

A: weight = 1
B: weight = 1
C: weight = 3
D: weight = 1
E: weight = 1

위 경우 C는 타 thread보다 더 중요한 thread이므로, 항상 3 × 10 ms = 30 ms를 할당받는다. 반면 나머지 thread는 각각 10 ms씩 실행된다.

② Circular Linked List에서 중복 삽입 방식
thread의 실행 순서를 저장하는 Thread Control Block(TCB)을 만들고, 중요한 thread를 리스트에 여러 번 삽입하는 것이다.

예를 들어, time quantum이 10 ms이고, C thread를 두 배로 실행하고 싶다면 TCB를 다음과 같이 구성할 수 있다.

A → B → C → D → E → C → (다시 A로 순환)

이렇게 하면 thread C가 리스트 내에서 두 번 등장하므로, 실제 실행 순서에서도 항상 다른 thread보다 두 배 자주 실행된다.

<참고 자료>
https://www.udemy.com/course/arduino-freertos/