Scheduling

October 10, 2025 20 분 소요

이번 포스트는 OS의 중요 컴포넌트인 Scheduling에 대해 다룬다.

Scheduling

Scheduling Introduction

Workload Assumptions (가장 단순하고 이상적인 환경)

모든 프로세스가 동일한 실행 시간 (run time)을 가진다.

즉, CPU의 사용 시간이 모두 같다.

모든 프로세스가 동시에 도착 한다.

I/O 작업이 없다.

즉 CPU만 사용한다. (순수 CPU-bound workload)

각 프로세스의 실행 시간이 미리 알려져 있다. (예측 가능성)

Scheduling Metrics (스케줄링의 평가 기준) :

1. Turnaround Time (반환 시간)

하나의 프로세스가 시스템에 들어온 순간부터 완전히 끝날 때까지 걸린 전체 시간 \(T_{turnaround} = T_{completion} - T_{arrival}\)
프로세스가 시스템에 도착(arrival) 해서 완료(completion)될 때까지 얼마나 오래 걸렸는지를 의미
- 프로세스가 기다린 시간 + 실행된 시간이 포함된 것
- 사용자 입장에서 작업 요청으로부터 결과를 받기까지의 전체 지연 시간
- 반환시간이 작을수록 시스템의 성능이 좋다고 판단한다.

2. Fairness (공정성)

모든 프로세스가 CPU를 공평하게 사용할 수 있는 정도를 나타내는 지표
- 일부 프로세스가 너무 오래 기다리거나, 한 프로세스가 CPU를 독점하지 않도록 하는 것이 목적

두 가지의 평가기준은 서로 trade-off 관계

빠른 응답을 원하면 공정성을 포기하고, 모두에게 공평함을 원하면 효율이 떨어진다.

FIFO (First In, First Out)

FIFO

정의 : 먼저 들어온 프로세스를 먼저 실행하는 방식

즉, “도착 순서대로 실행” 하는 가장 단순한 스케줄링 알고리즘
큐(Queue) 자료구조처럼 동작

예시 분석 :

(조건)
A, B, C 세 개의 작업이 순서대로 도착
각 job의 실행 시간 = 10초

Job	Completion	Turnaround
A	10	10
B	20	20
C	30	30

따라서 Average Turnaround Time은 \(\frac{10 + 20 + 30}{3} = 20\ \text{seconds}\)

Convoy Effect (호위 효과)

CPU를 오래 사용하는 하나의 프로세스 때문에, 뒤에 짧은 프로세스들이 모두 기다리는 현상
- 즉, 긴 작업 하나로 인해 그 뒤에 있는 짧은 작업들이 호위하듯이 전부 지연되는 문제

예시 분석:

(조건)
A, B, C 세 개의 작업이 순서대로 도착
A는 실행 시간이 100초 / B,C는 10초 

Job	Completion	Turnaround (완료–도착)
A	100	100
B	110	110
C	120	120

따라서 Average Turnaround Time은 \(\frac{100 + 110 + 120}{3} = 110\ \text{seconds}\)

SJF (Shortest Job First)

정의 : 실행 시간이 가장 짧은 작업부터 먼저 수행하는 비선점형 (Non-preemptive) 스케줄링

CPU 작업의 길이(run time)를 미리 알고 있다면, 가장 빨리 끝낼 수 있는 것부터 처리하는 방식

예시 분석:

(조건)
모든 프로세스가 도착했다고 가정 (arrival time이 같다.)
A의 실행시간은 100초 / B,C는 10초

실행 순서 : B-> C -> A

Job	Completion	Turnaround
B	10	10
C	20	20
A	120	120

따라서 Average Turnaround Time은 \(\text{Average turnaround time} = \frac{10 + 20 + 120}{3} = 50\text{ sec}\)

성능 측면에서는 매우 효율적
FIFO랑 비교할 때 평균 반환 시간이 거의 절반 감소

SJF with Late Arrivals - 현실적 문제

위의 가정은 “모든 작업이 동시에 도착한다”는 비현실적 가정에 의존함.

예시 분석 (상황)

Job	Arrival Time	Run Time
A	0	100
B	10	10
C	10	10

A가 0초에 동작 - CPU는 A를 바로 실행함.
B,C는 10초에 도착했지만, SJF는 비선점형이기 때문에 이미 실행중인 A를 중간에 끊을수가 없다.
- 즉 B,C는 A의 작업이 끝날때까지 계속 기다려야 한다.

ob	Completion	Arrival	Turnaround
A	100	0	100
B	110	10	100
C	120	10	110

따라서 Average Turnaround Time은 \(\text{Average turnaround time} = \frac{100 + 100 + 110}{3} = 103.33\text{ sec}\)

STCF (Shortest Time-to-Completion First)

정의 : SJF(Shortest Job First) 방법에 ‘선점 (preemption)’ 개념을 추가한 것

실행 중이더라도 더 짧은 남은 작업이 들어오면 CPU를 즉시 빼앗김

스케줄링 규칙:

새 작업이 도착할 때마다, 현재 실행 중인 프로세스와 남은 작업들의 남은 실행 시간 (remaining time)을 비교한다.
가장 짧은 남은 실행 시간을 가진 프로세스가 CPU를 차지한다.

즉 실행 중이던 프로세스라도, 더 짧은 작업이 들어오면 CPU를 즉시 빼앗긴다. (preemption)

예시 분석: (위와 동일)

Job	Arrival Time	Run Time
A	0	100
B	10	10
C	10	10

A가 0초부터 실행 (A만 있기 때문에 A가 실행중)
Time = 10초 : B와 C가 도착
- A의 남은 시간은 90초 / B,C의 전체 시간 : 10초씩
- B, C 가 더 짧기 때문에 A를 중단하고 B를 실행
Time = 20초 : B 종료 이후 C 실행
C 종료 이후 다시 A로 복귀하여 남은 90초를 실행

Job	Completion	Arrival	Turnaround
A	120	0	120
B	20	10	10
C	30	10	20

따라서 Average Turnaround Time은 \(\text{Average turnaround time} = \frac{120 + 10 + 20}{3} = 50\ \text{sec}\)

선점 기능을 추가함으로써 평균 반환 시간이 절반 수준으로 감소

New Scheduling metric

3. Response Time (응답 시간)

프로세스가 도착(arrival) 한 시점부터 처음으로 CPU를 할당받을 때 (first Scheduled)까지 걸린 시간

\[T_{response} = T_{firstrun} - T_{arrival}\]

STCF의 한계

짧은 작업을 우선하기 때문에 평균 완료 시간은 매우 좋지만, 한 번 CPU를 잃으면 다시 실행되기까지 오래 기다릴 수도 있어서 Response Time이 좋지는 않다.
- 특히 긴 작업이 여러 번 선점당할 경우, 사용자는 시스템이 느리다라고 체감

RR Scheduling (Round Robin)

Round Robin

정의 : 모든 프로세스에 CPU를 공평하게 나누어주는 스케줄링 방식

각 프로세스는 고정된 시간 (time slice 또는 quantum) 동안만 실행되고, 시간이 끝나면 다음 프로세스로 순환(round-robin) 하며 교체
용어 정리
- Time Slice (Quantum) : 한 프로세스가 CPU를 독점할 수 있는 최대 시간
- Time Interrupt : OS가 CPU를 강제로 빼앗아 다음 프로세스로 넘기는 장치
- Fairness (공정성) : 모든 프로세스가 일정 주기로 CPU를 사용할 수 있게 보장

동작 원리:

프로세스들이 ‘run queue’에 순서대로 대기
CPU는 맨 앞의 프로세스에게 time slice만큼 CPU를 할당
시간이 끝나면 Timer Interrupt가 발생
CPU는 현재 프로세스를 뒤로 보내고, 다음 프로세스를 실행
이 과정을 모든 프로세스가 끝날 때까지 반복

장단점:

장 : 응답 시간이 매우 짧아서 사용자 체감이 빠르다 (모든 프로세스가 조금씩 실행되기 때문)
단 : context switch 오버헤드가 증가한다. 평균 반환시간은 비효율적이다.

예시 분석:

Job	Run Time	첫 실행	Response Time
A	5	0	0
B	5	5	5
C	5	10	10

이 표를 보고 응답 시간 (Response Time)을 기준으로 계산하면, SJF에서는 \(T_{avg\_response} = \frac{0 + 5 + 10}{3} = 5\text{ sec}\)

RR의 경우 : Time slice = 1초로 가정

Job	첫 실행	Response Time
A	0	0
B	1	1
C	2	2

따라서 응답 시간은 \(T_{avg\_response} = \frac{0 + 1 + 2}{3} = 1\text{ sec}\)

즉 Time Slice의 길이가 굉장히 중요하다.!!

Time Slice

프로세스가 CPU를 독점할 수 있는 최대 시간 단위
- Time Slice 가 짧을 수록 빠른 응답시간을 가지고 사용자 입장에서 즉각적인 반응을 하지만, context switch가 너무 자주 발생해 오버헤드가 증가한다.
  - 요약 : 효율성은 낮지만 반응성은 좋다.
  - 사용자 인터랙티브 프로그램 (UI, 키 입력 등)에 적합
- Time Slice가 길수록 스위칭 비용이 감소하여 효율이 좋지만, 응답 시간 약화로 사용자가 체감이 느리다.
  - 요약 : 효율은 좋지만 반응성이 나쁘다.

Trade-off 관계이다.

Incorporating I/O (입출력 작업 통합)

가정과 다르게 실제 시스템에서는 많은 프로그램이 I/O (디스크, 네트워크 등)를 자주 수행함.

예시 상황

A와 B는 두 프로세스가 각각 50ms의 CPU 시간이 필요함.
단, A는 10ms 마다 I/O 요청을 수행한다.
B는 I/O없이 CPU만 계속 사용한다.

가능 시나리오:

(Poor Use of Resources)

스케줄러가 A를 먼저 실행
- A는 10ms 동안 CPU 사용 이후 I/O 요청을 발생
- A는 Blocked 상태로 전환됨.
CPU는 놀게 된다. (Idle 상태)
- A가 I/O를 기다리는 동안 아무 프로세스도 실행되지 않는다.
이후 B가 실행됨.

잘못된 스케줄링

CPU가 A의 I/O 중에 놀고 있음. CPU Utilization이 낮다.

자원 활용 비효율적

(Overlap Allows Use of Resources)

A가 10ms 동안 CPU 사용 이후 I/O 요청 -> Blocked
B를 즉시 실행하여 CPU 낭비 방지
A의 I/O가 끝나면 다시 Ready 상태로 전환되어 다음 번 CPU를 사용

올바른 스케줄링

병렬 자원 활용 (CPU + I/O 동시 사용)

CPU Utilization 이 최대화*

I/O 관련 스케줄링 메커니즘

1. I/O 시작 시

프로세스는 Blocked 상태로 전환된다. (I/O 완료까지 대기)
스케줄러는 다른 프로세스를 즉시 CPU에 배정해야 한다.

2. I/O 완료 시

하드웨어 인터럽트 발생
OS는 Blocked 상태의 프로세스를 Ready Queue로 이동시킨다.
다음 번 스케줄링에서 CPU를 다시 받을 수 있다.

Scheduling : The Multi-Level Feedback Queue

MLFQ (Multi-Level Feedback Queue)

아이디어 : 과거의 실행 패턴을 보면서 그 다음을 더 똑똑하게 스케줄링하자.

목표

Turnaround Time을 줄이기
- 실제로는 SJF처럼 짧은 작업을 먼저 돌려주고 싶다.
Response time도 좋게 유지하기
- 작업 길이를 미리 몰라도 짧아 보이는 것부터 빨리 한 번씩 돌려준다.

Basic Rules

1. 여러 개의 큐가 있고, 각 큐마다 우선순위가 다르다.

보통 Q0가 가장 높은 우선순위, 그 아래로 Q1, Q2...
(보통은 위로 갈수록 Time Slice가 짧고 자주 기회를 얻는다.)

2. 작업은 한 시점에 정확히 ‘한 개의 큐’에만 속한다.

각 작업은 현재 자신의 ‘우선순위 레벨’을 하나만 가진다.

3. 스케줄 선택 규칙

Rule 1 : 더 높은 큐에 작업이 있으면, 그 큐의 작업만 실행된다. (낮은 큐 작업은 대기)
- 우선순위가 다르면 높은 쪽이 무조건 먼저 실행
Rule 2 : 같은 큐 안에서는 Round Robin(RR)으로 공정하게 실행한다.
- 우선순위가 같으면 돌아가면서

Basic Rules (Cont.)

Queue 간의 이동 규칙 (승격 또는 강등)

MLFQ는 “관찰된 행동 (Observed Behavior)”로 판단한다.

OS는 각 job의 실제 실행 패턴을 관찰해서 CPU를 많이 쓴다 또는 짧게 쓰고 기다린다를 추론한다.
- 이에 따라 우선순위를 자동 조정

예시 분석:

Case 1 : I/O를 자주 하는 job (Interactive / I/O-bound)

이런 job은 CPU를 잠깐만 쓰고 곧 I/O 요청을 하며 CPU를 양보한다.
- 예 : 사용자 키 입력을 기다리는 GUI 앱, 터미널 등
이들은 반응성이 중요하기 때문에 우선순위를 유지 한다.
상위 큐에 계속 남아있는다.

Case 2 : CPU를 오래 붙잡는 job (CPU- bound)

이 job은 I/O 없이 계속 CPU를 점유하려고 한다.
- 과학 연산, 빌드, 머신러닝 학습 등
이런 job은 다른 job의 반응성을 방해하기 때문에 우선순위를 낮춘다.

Q8 : A, B			(Hight Priority)
Q7 :
Q6 : 
Q5 : 
Q4 : C
Q3 :
Q2 :
Q1 : D				(Low Priority)

A와 B가 같은 큐(Q8)에 있기 때문에 같은 우선순위로 Round Robin으로 번갈아서 수행한다.
그 아래에 있는 C, D는 A,B가 모두 실행이 끝나야 실행이 가능하다.

그렇다면 어떻게 우선순위에서의 변화가 일어날까?

How to Change Priority: 프로세스의 실제 CPU 사용 패턴에 따라 큐 위치를 바꿔주는 것

Rule 3 : Job이 처음 들어왔을 때 가장 위 큐에서 시작한다.
- 새로 들어온 작업은 무조건 highest Queue에 위치한다.
- 이유는 처음에 Job의 길이를 모르기 때문이다.
New Job = 잠재적 짧은 Job
Rule 4 : Time Slice를 다 써버린 경우에 우선순위는 내려간다.
- CPU를 오래 잡고 있으면 MLFQ는 이 프로세스를 CPU-Bound 하다고 판단한다.
- 따라서 한 단계 아래 큐로 이동한다.
Rule 4b : Time Slice가 끝나기 전에 CPU를 양보한 경우
- 대부분 I/O 요청 때문이다.
- 같은 큐에 그대로 유지한다.

예시 분석

Example 1 : A single Long-Running Job

설정

큐는 Q2, Q1, Q0 세 단계
각 time slice = 10ms
Job A 하나뿐이면, CPU-Bound 계속 CPU만 쓰는 작업

동작 순서

1️⃣ A는 시스템에 처음 들어옴 → Rule 3에 따라 최상위 큐(Q2)로 배정.

2️⃣ Q2에서 10ms 동안 실행함 → time slice 전부 소모 → Rule 4a 적용 → 한 단계 아래(Q1)로 이동.

3️⃣ Q1에서도 또 10ms 다 씀 → 다시 Rule 4a 적용 → Q0로 강등.

4️⃣ 이후부터는 Q0에 머물러서 나머지 200ms 전부 수행.

의미

MLFQ가 이 프로세스는 이 CPU를 계속 긴 job 이라고 판단하여 자동으로 낮은 큐로 내린다.
- 따라서 우선순위 낮은 곳에서 몰아서 수행된다.
- 이런 구조로 나중에 짧은 job이 들어오면 빠르게 끼어들 수 있는 여유를 준다.

Example 2 : Along Came a Short Job

설정

Job A : 이미 오래 실행된 CPU-Bound (제일 낮은 우선순위 큐에서 돌고 있다.)
Job B : 새로 도착한 짧은 Job (20ms 짜리 interactive)
B는 T = 100ms 시점에 도착

동작 순서

1️⃣ B가 새로 도착했으므로 Rule 3에 따라 최상위 큐(Q2)로 들어감.

2️⃣ Q0에 있던 A보다 우선순위가 높기 때문에, B가 바로 A를 preempt(선점).

3️⃣ B는 짧은 작업이라 금방 끝나고 → 다시 A가 Q0에서 이어서 실행.

의미

Preemptive Scheduling이 자연스럽게 일어난다.
- SJF의 단점 (미리 job의 길이를 알아야 한다.)을 보완

Example 3 : What about I/O ?

설정

Job A : 여전히 long CPU-Bound
Job B : I/O-bound interactive job, CPU를 1ms만 쓰고 바로 I/O 요청
- 예시 ) 키 입력, 마우스 이벤트 등

동작 순서

1️⃣ B는 CPU를 잠깐만 쓰고 I/O 요청으로 CPU를 양보 → Rule 4b 적용 → 큐 레벨 유지 (Q2 유지).

2️⃣ A는 계속 CPU를 쓰므로 Q0에 머무름.

3️⃣ B가 I/O 완료되면 다시 ready로 돌아오고, 여전히 Q2에 있으므로 또 우선 실행.

→ 이 과정이 반복되면서 A와 B가 번갈아 실행됨.

의미

I/O job은 짧게 자주 CPU를 스기 때문에, 높은 우선순위를 계속 유지한다.
결과적으로 사용자 입력 같은 interactive 작업은 매우 빠른 반응성을 확보한다.

MLFQ는 I/O job을 항상 높은 우선순위에 두어 반응성을 보장한다.

interactive -> 빠른 응답 / batch -> 천천히 백그라운드 형태로 자원 분배

Problems In Basic MLFQ

기본 MLFQ의 한계

1. Starvation (기아 현상)

만약 Interactive 한 job이 너무 많다면?

-> 긴 job은 CPU를 거의 받지 못한다.

높은 큐(Q2, Q1)에 interactive한 job 이 계속 몰려있으면 낮은 큐의 CPU-bound job은 실행 기회가 거의 없다.
긴 job이 굶어 죽는 (starved) 현상이 발생한다.
- 시스템 자원이 공정하게 배분이 안됨.

2. Game the scheduler

똑똑한 프로그램이 MLFQ의 규칙 악용이 가능하다.

어떤 Job이 타임 슬라이스의 99%만 사용하고, 그 직후 I/O 요청을 날리면, 우선순위가 유지된다.
CPU-bound job 이지만, 의도적으로 조금 양보하는 척하면서 상위 큐에 머무르는 꼼수를 사용할 수 있음.

3. Behavior Change Over Time

프로그램의 성격이 실행 도중 바뀌기

처음에는 계산 위주 (CPU -bound)였다가 나중에 I/O 중심으로 변할 수 있다.
MLFQ는 과거 행동으로만 우선순위를 조정하기에, 변화에 즉각 대응하기 어렵다.

Priority Boost

해결책

Rule 5 : 일정 주기가 지나면 모든 job의 우선순위를 리셋한다.

starvation 해결
장기 job도 주기적으로 CPU 기회 휙득
I/O job은 여전히 빠른 반응성 유지
전체 시스템의 공정성을 회복

Better Accounting

기존의 Rule4를 수정한다.

CPU를 여러 번 나눠서 쓰더라도, 해당 큐에서 사용할 수 있는 총 시간이 다 끝나면 무조건 아래로 강등한다.

한 큐에서 누적 CPU 사용 시간이 기준이 된다.
- I/O로 쪼개도 총 시간이 넘으면 우선순위가 낮아진다.
- Game을 방지하기 (속임수 방지) + 공정성 향상

Low Priority, Longer Quanta

아이디어 : 모든 큐가 동일한 time slice를 가질 필요가 없다.

오히려 Queue의 레벨에 따라 다르게 설정하는 것이 효율적이다.

Queue Level	Time Slice (예시)	특징
Q2 (High)	10ms	반응성 중요 (interactive job)
Q1 (Mid)	20ms	중간 작업
Q0 (Low)	40~100ms	CPU-bound, 긴 job → context switching 비용 줄이기

Trade - Off

높은 큐 -> 반응성 중시

낮은 큐 -> 효율성 중시

아이디어 : Fair-share scheduler

CPU 시간을 비율(share)로 나누어 공정하게 배분한다. (가중치)
각 job이 미리 정해진 비율만큼의 CPU 자원을 보장받는다.

이 방식은 turnaround, response time을 최소화하려는 목적은 아니다.

Basic Concept - Ticket

Tickets : Lottery Scheduling

Ticket = 자원의 소유권
- 각 프로세스는 일정 개수의 티켓을 가진다.
- 전체 티켓 수 중 자신의 티켓 비율만큼 CPU 점유율을 가진다.

티켓 = CPU 실행 확률

프로세스가 가지는 CPU의 공정한 몫을 나타냄.

Lottery Scheduling

아이디어 : CPU를 누가 가질지 복권을 추첨하듯이 무작위로 정한다.

하지만 단순한 랜덤이 아니라, 티켓 개수에 비례한 확률 (random weighted by tickets)을 사용한다.

동작 과정 (예시)

각 프로세스에게 티켓을 할당
- A는 75장, B는 25장 할당
스케줄러는 매번 CPU를 줄 때마다 랜덤으로 1장의 티켓을 추첨 (0~99)
뽑힌 티켓을 가진 프로세스가 time slice동안 실행된다.

특징

짧은 구간에서는 3:1 의 완벽한 비율로 나오지는 않지만, 시간이 길어질수록 실제 점유 비율이 75:25 에 수렴한다.
장점
- 매우 구현이 단순하다.
- Fairness (공정성)을 보장하고, 비례적인 자원 분배가 가능하다.
- 동적 우선순위를 조정이 가능하다.
단점
- 확률 기반이기 때문에 단기적으로는 불안정성이 존재한다.
- 응답시간 최적화의 목적에서는 부적합하다.

Ticket Mechanisms

Ticket 확장 개념

Ticket Currency

정의 : 사용자 (user)마다 티켓 단위를 다르게 써도, 시스템이 자동으로 이를 글로벌 비율로 환산하여 공정성을 유지한다.

예시 분석)

전체 global 티켓 수 : 200장

프로세스 A : 100 tickets
프로세스 B : 100 tickets

User A 내부 구조

A에서 내부적으로 다른 통화 단위를 사용하여 A1, A2에 각각 500씩 배정
시스템이 알아서 비율을 1:1로 변환 하여 global 기준으로 반영
- A1 : 50 tickets / A2 : 50 tickets

서로 다른 사용자 간의 “티켓 단위 불일치” 해결

사용자별 독립적 비율과 설정을 허용

-> 공정성, 유연성을 동시에 확보

Ticket transfer

정의 : 한 프로세스가 자신이 가진 티켓 일부를 다른 프로세스에게 일시적으로 넘겨주는 기능

쉽게 말해 잠깐 빌려주는 것

프로세스 간 의존 관계가 있는 시스템 (예 : 클라이언트 - 서버)에서 유용

협업 프로세스 간 CPU 자원을 효율적으로 공유
I/O 중심 프로세스가 응답성이 향상

Ticket Inflation

정의 : 프로세스가 자기 자신이 가진 티켓의 수를 일시적으로 조정할 수 있는 기능

필요할 때는 raise, 필요가 없을 때는 lower 할 수 있다.
예시)
- 인코딩 중에는 CPU를 많이 써야 한다. -> 티켓을 일시적으로 증가
- 대기 상태(파일 저장 등)일 때 -> 티켓을 “감소”

Implementation

Linked List 구조

typedef struct node {
    int pid;        // 프로세스 ID
    int tickets;    // 티켓 개수
    struct node* next; // 다음 프로세스 포인터
} node_t;

node_t* head; // 리스트의 시작점

리스트는 티켓 수에 따라 정렬되어 있고, 헤드 포인터가 첫 번째 프로세스를 가리킨다.

복권 추첨 (랜덤 선택) 로직

int counter = 0;                        // 누적 티켓 합산용
int winner = getrandom(0, totalTickets); // 0~399 사이의 난수 생성
node_t* current = head;                 // 리스트 탐색 시작

while (current) {
    counter += current->tickets;       // 누적 합 계산
    if (counter > winner)              // 당첨 티켓이 포함된 프로세스 찾음
        break;                         // winner 찾음
    current = current->next;           // 다음 프로세스로 이동
}
// current가 당첨 프로세스 → 실행

예시) 랜덤으로 뽑힌 숫자가 339일 경우

A의 범위 : 0~99 (탈락)
B의 범위 : 100~149(탈락)
C의 범위 : 150~399(당첨)

프로세스 C가 실행이 된다.

U : 공정성 측정 지표

정의 : 두 프로세스의 완료 시점이 얼마나 차이나는가를 수치화한 것 \(U = \frac{T_{\text{first job finishes}}}{T_{\text{second job finishes}}}\) 두 개의 프로세스의 finish 비율로 계산

U = 1 : 완벽히 공정하다. (두 개의 작업이 거의 동시에 끝난다.)
U < 1 : 불공정하다.
- 한쪽이 먼저 끝나고, 나머지는 더 오래 기다린다.

즉 U의 값이 1에 가까울수록 스케줄러의 fairness(공정성)가 높다.

Job Length와의 비례 관계

Job Length 가 짧을 때는 Unfairness가 낮다. (0.5 ~ 0.7)
- 짧은 시간 동안에는 랜덤성의 영향이 커서 불공정
Job Length 가 길 때는 U 는 1에 수렴
- 장기적으로는 통계적으로 공정해짐

Stride Scheduling : Deterministic Approach

아이디어 : Lottery Scheduling 은 무작위 방식이기 때문에, 공정성은 장기적으로만 보장되는 단점이 존재한다. 무작위 대신에서 수학적 규칙으로 비례적으로 배분하는 Stride Scheduling이 등장했다.

Stride 공식 \(\text{Stride} = \frac{\text{Large number}}{\text{Number of tickets}}\)

Large Number는 임의의 큰 값
티켓이 많을수록 Stride가 작아진다. 자주 실행됨을 의미

Pass Value

각 프로세스마다 pass value (누적 실행 지표)를 유지한다.
- 처음에는 0
- 프로세스가 한 번 실행될 때마다 자기 stride만큼 패스 증가

동작 원리

각 프로세스의 pass 값을 비교
가장 작은 pass를 가진 프로세스를 실행
실행 후에 그 프로세스의 pass += stride
다시 큐에 넣고 반복

Pseudo-code

current = remove_min(queue);     // 최소 pass값 프로세스 선택
schedule(current);               // 실행
current->pass += current->stride; // pass 값 증가
insert(queue, current);          // 다시 큐에 삽입

핵심 포인트

Deterministic : 랜덤 없이 수학적으로 예측이 가능하다.

Fairness 즉각 보장 : Lottery 보다 단기적인 공정성이 우수하다.

단점
- 각 프로세스마다 pass 상태를 유지해야 한다.
  - per-process state가 필요하다.
- 새로운 Job이 pass = 0으로 들어오면 CPU 독점이 가능하다.

Multiprocessor Scehduling

배경 (개요)

멀티 코어의 등장 = 멀티프로세서 스케줄링의 필요
- 한 칩 안에 여러 개의 CPU 코어가 들어 있는 환경의 시작
- 코어 1개에 누구를 올릴까? -> 여러 코어엔 어떤 스레드를 어떻게 배치/이동할까? 를 결정해야하는 시대가 옴
CPU를 늘린다고 단일 프로그램이 자동으로 빨라지지는 않는다.
- 한 프로세스 안의 단일 스레드는 여전히 한 코어에서만 실행이 된다. 성능을 올리기 위해서는 프로그램을 병렬화 (멀티 스레딩)을 해야한다.
- OS 스케줄러는 “여러 스레드 / 여러 작업”을 여러 코어에 분산 배치

Cache

Single CPU with Cache

Cache (캐시) : 메인 메모리보다 작고 빠른 저장소. 자주 쓰이는 데이터 (인기 데이터)를 복사해 둔다.
- 시간 지역성 (Temporal locality) : 방금 쓴 데이터는 곧 또 쓸 확률이 높다.
- 공간 지역성 (Spatial locality) : 어떤 주소를 썼다면 그 주변도 곧 쓸 확률이 높다.
효과 : 캐시에 히트하게 되면 메모리의 접근보다는 훨씬 빠르다. (느린 메모리를 빠른 것처럼 보이게 함.)
왜 스케줄링과 연결이 되는지?
- 스레드가 같은 코어에서 계속 돌게 되면, 그 코어 캐시에 데이터가 남아 있어서 히트율이 높아진다.
- 반대로 코어를 자주 옮기면 캐시를 다시 데워야 해서 비용이 올라간다.

Cache의 기본 문제 설정

여러 코어가 각자 캐시를 가지고, 공유 메모리를 본다. 그러면 같은 주소의 값이 코어마다 다를 수 있다.

coherence (일관성) 문제

시나리오
1. 상태 0 : CPU0 / CPU1 이 같은 메모리(버스 공유)를 본다. 주소 1에 값 D가 메모리에 있다.
  - 아직 캐시에는 존재하지 않는 상태
2. CPU0이 주소 1을 읽음 : CPU0 캐시에 D가 채워진다.
  - 이것을 아직 CPU1은 모르는 상태
  여기까지는 문제 X
3. CPU0이 D를 D’으로 업데이트 (쓰기)
  - Write-through : 캐시에 쓰면서 바로 메모리에도 쓴다.
  - Write-back : 캐시에만 쓰고 나중에 메모리에 반영한다. (현대 CPU에 일반적)
  - 현재는 Write-back이라고 가정하고, 이후 스케줄러가 CPU1으로 스레드를 스위칭을 한다.
4. CPU1이 같은 주소를 다시 읽음. : CPU1 캐시에는 예전 D가 남아있거나 메모리에서 D를 다시 읽어서 채운다.
  - CPU0의 업데이트를 모른다.

=> 결과 : CPU1은 오래된 값 D를 읽어온다. 이는 일관성이 붕괴되는 현상이다.

캐시 일관성 해결 방법

Bus Snooping : 각 CPU의 캐시가 버스(Bus)를 감시(snoop)해서, 다른 CPU가 메모리의 데이터를 수정하면 그 사실을 즉시 감지하고 자신의 캐시에 저장된 복사본을 무효화 (invalidate) 하거나 업데이트 (update) 하는 방식
동작 과정

(1) 초기 상태

CPU0 이 메모리 주소 1의 데이터 D를 읽는다.
- CPU0 캐시에 D 가 저장된다.
이때 CPU1은 아직 아무것도 캐싱하지 않는다.
캐시 정책은 여기서 Write-through으로 표시된다.

(2) CPU1이 동일한 주소의 데이터를 요청

CPU1이 주소 1의 최신 데이터 (D’)을 읽으려고 한다.
버스를 통해 ‘이 주소를 누가 가지고 있는지’를 감시하고, CPU0이 D'으로 갱신했다는 신호를 스누핑
- CPU1은 버스에서 D’ 을 받아와서 자신의 캐시에 반영한다.

(3) 최종 상태

두 CPU의 캐시와 메모리 모두 일관성을 유지한다.
만약 CPU1이 D를 이미 캐시하고 있었다면, 이 단계에서 자기 캐시의 D를 무효화한다.

동기화 (Synchronization)

캐시 일관성이 해결되도, 여러 CPU가 공유 데이터를 동시에 수정하면 여전히 논리적 불일치가 생길 수 있다. 그래서 OS나 사용자 코드에서는 동기화가 필수다.

동기화

typedef struct __Node_t {
    int value;
    struct __Node_t *next;
} Node_t;

int List_Pop() {
    Node_t *tmp = head;      // head 포인터 복사
    int value = head->value; // 값 읽음
    head = head->next;       // head를 다음 노드로 이동
    free(tmp);               // 원래 head 해제
    return value;            // 값 반환
}

위 함수의 문제점

단일 스레드에서는 문제가 없다.
멀티코어 환경에서는 동시에 두 CPU가 head를 pop()하면 문제가 생긴다.
예시) Race condition
1. CPU0, CPU1 이 둘 다 같은 head 주소를 읽음.
2. CPU0이 head를 다음 노드로 바꾼다.
3. CPU1도 여전히 옛 head를 보고 free()를 호출한다.
  - 이중 free 발생
4. 심하면 segmentation fault나 리스트 손상 위험이 존재.

해결 방법

pthread_mutex_t m;

typedef struct __Node_t {
    int value;
    struct __Node_t *next;
} Node_t;

int List_Pop() {
    lock(&m);                //  한 번에 하나만 접근
    Node_t *tmp = head;
    int value = head->value;
    head = head->next;
    free(tmp);
    unlock(&m);              //  다른 CPU 접근 허용
    return value;
}

한 스레드가 락을 휙득하면 해결 완료
다른 스레드는 락이 풀릴 때까지 기다리기 때문에, 동시에 같은 자료구조를 조작할 수 없다.

Cache Affinity

개념 : 가능하다면 동일한 CPU 위에서 프로세스를 계속 실행해라

프로세스를 자주 다른 CPU로 옮기지 말라는 뜻
이유
- 프로세스는 실행 도중에 캐시에 데이터를 남긴다.
  - 예시 : 로컬 변수, 스택, 최근 접근한 페이지의 메모리 블록 등
  - 이 데이터는 CPU 캐시에 남아 있다.
- 다음번에 같은 프로세스가 다시 실행될때
  - 그 프로세스가 같은 CPU에서 돌아가면 이미 필요한 데이터가 이미 캐시에 있을 확률이 높다.
  - 캐시 히트 (Cache Hit)가 증가
- 반대로, 다른 CPU로 옮겨버리게 된다면 그 캐시에 남아있는 데이터는 쓸모가 없어진다.
  - 캐시 미스 (Cache Miss) 증가로 성능이 저하된다.

SQMS (Single Queue Multiprocessor Scheduling)

개념 : 모든 CPU가 하나의 전역 큐 (Global Queue)를 공유하는 방식

각 CPU는 이 큐에서 다음에 실행할 작업을 꺼내간다.
CPU0~3 이 모두 하나의 ready queue를 공유한다.
장점 : 구현이 간단하고, 모든 작업이 공평하게 스케줄된다.
단점
- 락 (Locking)이 필요 : 여러 CPU가 동시에 하나의 큐에 접근하므로, 큐를 보호하기 위해 락 (mutex)를 사용해야 한다.
  - 락 경합으로 확장성이 떨어진다.
- Cache Affinity 손실 : CPU0에서 실행되던 프로세스가 다음 번에 CPU2에서 잡힐 수도 있다.
  - 캐시가 다시 채워져야 하기 때문에 비효율적이다.

프로세스들이 코어 사이를 이리저리 옮겨 다니기 때문에 캐시 친화성 (Cache Affinity)가 완전히 붕괴

아래는 해결 방법

예시 )

Queue : A -> B -> C -> D -> E의 순서로 진행될 때

CPU	실행 순서 (반복)
CPU0	A, E, A, A, A…
CPU1	B, B, E, B, B…
CPU2	C, C, C, E, C…
CPU3	D, D, D, D, E…

작업 A~D는 자기 코어에 고정되어 실행 (캐시 친화성 유지)
단, 작업 E만 분산을 위해 코어 사이를 옮겨 다닌다.
오직 부하 분산 (Load balancing)을 위한 작업만 이동

단점 : 구현이 복잡하다. 부하가 치우치면 결국 캐시 친화성을 포기해야 한다.

MQMS (Multi-queue Multiprocessor Scheduling)

개념 : 각 CPU가 자신만의 스케줄링 큐(queue)를 가진다.

CPU0 은 Q0, CPU1은 Q1 이런 식으로 각자 독립된 큐를 갖고 있다.

특징

Multiple Queues : 각 CPU마다 독립적인 ready queue를 가진다.
Scheduling discipline : 각 큐는 고유한 스케줄링 정책을 따를 수 있다.
Job placement : 새 작업이 시스템에 들어오면 딱 한 큐에만 배치된다.
Synchronization 문제 : 각 CPU가 자기 큐만 접근하므로, 락이 필요 없다.
- 경합 최소화
장점 : 락 오버헤드가 감소되기에 확장성이 향상된다.
- 여러 코어가 동시에 스케줄링 작업이 가능함. : Scalability (확장성)
- 캐시 친화성 향상 Cahce Affinity

예시 상황)

두 개의 CPU, 두 개의 큐가 있다고 하자.
각 큐는 라운드 로빈 (Round Robin) 방식으로 작업을 돌린다.

Q0 → A → C
Q1 → B → D

실행 결과

CPU	수행 순서
CPU0 (Q0 담당)	A, A, C, C, A, A, C, C …
CPU1 (Q1 담당)	B, B, D, D, B, B, D, D …

=> 각 CPU는 자기 큐에 있는 작업만 번갈아가면서 수행한다.

CPU0은 A,C만, CPU1은 B와 D만 돌린다.

MQMS의 한계점

Load Imbalance

위의 예시에서 Q0에서 Job C가 끝난 후의 상황

Q0: A        (C가 끝남)
Q1: B → D

Q0 에서는 A가 하나밖에 없어서 CPU0은 계속 A만 돌린다.
Q1은 여전히 두 작업 (B, D)을 번갈아 수행한다.
- A는 B,D 보다 2배 많은 CPU시간을 차지한다.

Load Imbalance (부하 불균형) : CPU0이 과도하게 한 작업만 수행 중

만약 위상황에서 A가 B, D 보다 먼저 끝나게 된다고 가정할때의 상황

Q0: (비어 있음)
Q1: B → D

Q0에서는 아무 작업이 없어 놀고 있는 상태 (idle)

즉, CPU 자원이 균등하게 활용되지 않는다.

해결 방법 : Migration (이동)

OS가 job(프로세스)을 다른 큐로 옮겨서 부하를 재분배한다.
결과적으로 CPU 부하를 균등하게 가능
하지만 간단하지만은 않음.
- 아까처럼 C의 작업만 끝나서 CPU0에는 A만 있고, CPU1에는 B,D가 남아있을 때,
- B를 CPU0, 1을 계속 옮기면서 반복하게 되면 스위칭발생
  
  => 오히려 캐시 무효화가 발생하여 성능이 저하 됨.

Work Stealing

개념 : Idle 한 CPU가 다른 CPU의 큐에서 일을 훔쳐오는 방식

모든 큐를 주기적으로 맞추는 것이 아닌, 놀고 있는 CPU가 직접 자발적으로 일거리를 가져가는 구조
구현 방법
1. Source Queue 선택 : 작업이 거의 없는 (비어가는) 큐를 선택
2. Target Queue 탐색 : 주기적으로 다른 큐를 살짝 들여다 본다.
3. Stealing : 만약 target queue가 source queue보다 훨씬 많으면, source가 그 중 일부를 job을 훔쳐온다.
단점 : High Overhead, Scaling Difficulty

Twitter Facebook LinkedIn

Scheduling

Scheduling

Scheduling Introduction

FIFO (First In, First Out)

SJF (Shortest Job First)

STCF (Shortest Time-to-Completion First)

RR Scheduling (Round Robin)

Incorporating I/O (입출력 작업 통합)

Scheduling : The Multi-Level Feedback Queue

MLFQ (Multi-Level Feedback Queue)

Example 1 : A single Long-Running Job

Example 2 : Along Came a Short Job

Example 3 : What about I/O ?

Problems In Basic MLFQ

Priority Boost

Lottery Scheduling

Ticket Mechanisms

Implementation

U : 공정성 측정 지표

Stride Scheduling : Deterministic Approach

Multiprocessor Scehduling

Cache

Cache Affinity

SQMS (Single Queue Multiprocessor Scheduling)

MQMS (Multi-queue Multiprocessor Scheduling)

Load Imbalance

Work Stealing

공유하기

참고

컴퓨터 통신 04. 인터네트워킹 (Internetworking)

컴퓨터 통신 03. 패킷 스위칭 (Packet Switching)

Concurrency, Locks

Translation Buffer, Advanced Page Table

Scheduling

Scheduling Introduction

FIFO (First In, First Out)

SJF (Shortest Job First)

STCF (Shortest Time-to-Completion First)

RR Scheduling (Round Robin)

Incorporating I/O (입출력 작업 통합)

Scheduling : The Multi-Level Feedback Queue

MLFQ (Multi-Level Feedback Queue)

Example 1 : A single Long-Running Job

Example 2 : Along Came a Short Job

Example 3 : What about I/O ?

Problems In Basic MLFQ

Priority Boost

Scheduling : Proportional Share

Lottery Scheduling

Ticket Mechanisms

Implementation

U : 공정성 측정 지표

Stride Scheduling : Deterministic Approach

Multiprocessor Scehduling

Cache

Cache Affinity

SQMS (Single Queue Multiprocessor Scheduling)

MQMS (Multi-queue Multiprocessor Scheduling)

Load Imbalance

Work Stealing

공유하기

참고

컴퓨터 통신 04. 인터네트워킹 (Internetworking)

컴퓨터 통신 03. 패킷 스위칭 (Packet Switching)

Concurrency, Locks

Translation Buffer, Advanced Page Table