CPU Scheduling

CPU 스케줄링

정의: 여러 프로세스가 CPU를 공유하는 환경에서, 효율적으로 CPU를 배분하여 시스템 성능을 최적화하고 처리 효율을 극대화하는 메커니즘.

목적: 시스템 성능 최적화 및 처리 효율 극대화. → CPU 이용률 최대화.

컴퓨터 시스템에서는 여러 프로세스가 동시에 실행되므로 CPU 자원을 효율적으로 관리하는 것이 중요하다.운영체제는 프로세스가 상황/중요도에 맞게 CPU를 이용할 수 있도록 프로세스 우선순위(priority) 를 부여한다.

스케줄링 큐

프로세스들이 서는 줄
스케줄링에서의 큐는 반드시 선입선출 방식일 필요는 없다.
같은 큐 내에서도 우선순위 별로 처리가 된다.
준비 큐 : CPU를 이용하고 싶어하는 프로세스들이 서는 줄
대기 큐 : 입출력장치들을 이용하고 싶어하는 프로세스들이 서는 줄

주요 용어

도착 시간: 프로세스가 준비 큐에 도착하는 시간.
완료 시간: 프로세스가 실행을 완료하는 시간.
버스트 시간(Burst Time): 프로세스가 CPU를 사용하는 시간.
대기 시간(Waiting Time): 프로세스가 CPU 할당을 기다린 시간.
턴어라운드 시간(Turnaround Time): 프로세스 제출부터 완료까지의 시간.

CPU 스케줄링 알고리즘

분류	설명	장점	단점
선점형	CPU를 강제로 뺏을 수 있는 방식. 프로세스가 중단될 수 있음.	자원 독점 방지, 모든 프로세스에 골고루 자원을 배분	문맥 교환에 오버헤드 발생, 비효율적인 자원 분배 가능
비선점형	CPU를 할당받은 프로세스가 종료될 때까지 다른 프로세스가 개입할 수 없음.	문맥 교환 오버헤드 적음	자원 독점 가능, 긴 프로세스가 시스템을 지배할 수 있음

비선점형(Non-preemptive)

FCFS (First-Come, First-Served)

선입 선처리 스케줄링
단순히 준비큐에 삽입된 순서대로 처리하는 비선점 스케줄링
먼저 CPU를 요청한 프로세스부터 CPU 할당
단점 : 프로세스들이 기다리는 시간이 매우 길어질 수 있다.(Convoy Effect, 호위 효과)

예제

다음과 같은 작업들이 있을 때:

P1 (실행 시간: 6ms)
P2 (실행 시간: 8ms)
P3 (실행 시간: 2ms)

프로세스	실행 시간(Burst Time)	대기 시간(Waiting Time)	완료 시간(Turnaround Time)
P1	6ms	0ms	6ms
P2	8ms	6ms	14ms
P3	2ms	14ms	16ms

도착 순서: P1 → P2 → P3

실행 순서: P1 → P2 → P3

평균 대기 시간 = (0 + 6 + 14) / 3 = 6.67ms 평균 완료 시간 = (6 + 14 + 16) / 3 = 12ms

FCFS에서는 P1 → P2 → P3 순서로 실행되므로, B와 C는 A가 끝날 때까지 대기해야 한다. 짧은 작업이 먼저 끝날 수 있지만, 긴 작업이 CPU를 점유하여 시스템 효율성이 떨어진다.

해결 방법으로 SJF, RR, Priority Scheduling과 같은 스케줄링 기법이 있다.

SJF (Shortest Job First)

CPU 사용 시간이 가장 짧은 프로세스부터 처리
장점
- 평균 대기 시간 최소화.
- 호위 효과 방지.
단점: 긴 작업은 무한정 대기할 가능성이 있다. (Starvation, 기아 상태)

예제

다음과 같은 작업들이 있을 때:

P1 (실행 시간: 6ms)
P2 (실행 시간: 8ms)
P3 (실행 시간: 2ms)

프로세스	실행 시간(Burst Time)	대기 시간(Waiting Time)	완료 시간(Turnaround Time)
P1	6ms	2ms	8ms
P2	8ms	8ms	16ms
P3	2ms	0ms	2ms

도착 순서: P1 → P2 → P3

실행 순서: P3 → P1 → P2

평균 대기 시간 = (0 + 2 + 8) / 3 = 3.33ms 평균 완료 시간 = (2 + 8 + 16) / 3 = 8.67ms

선점형(Preemptive)

RR (Round Robin)

일정 시간(Time Quantum) 동안 프로세스를 실행한 후 대기열의 끝으로 이동한다.
선입 선처리 스케줄링 + 시간 퀸텀(Time Quantum)
- 시간 퀸텀 : 각 프로세스가 CPU를 사용할 수 있는 정해진 시간
장점: 응답 시간이 일정.
단점: 프로세스 실행 시간(Time Quantum) 설정이 성능에 영향을 준다.
- 프로세스 실행 시간이 극단적으로 커지면 FCFS과 같이 호위 효과가 발생할 수 있다.
- 프로세스 실행 시간이 지나치게 작으면 문맥교환에 발생하는 오버헤드가 발생한다.

예제

Time Quantum = 5ms

| 프로세스 | 실행 시간(Burst Time) | 대기 시간(Waiting Time) | 완료 시간(Turnaround Time) | | — | — | — | — | | P1 | 20ms | 15ms | 35ms | | P2 | 3ms | 5ms | 8ms | | P3 | 7ms | 18ms | 25ms | | P4 | 5ms | 13ms | 18ms |

0ms: P1 실행
5ms: P2 실행, P1 대기 (남은 시간 15ms)
8ms: P2 완료, P3 실행
13ms: P4 실행, P3 대기(남은 시간 2ms)
18ms: P4 완료, P1 실행
23ms: P3 실행 P1 대기 (남은 시간 10ms)
25ms: P3 완료, P1 실행
35ms: P1 완료

결과

평균 대기 시간 = (15+5+18+13)/4=12.75ms

평균 완료 시간 = (35+8+25+18)/4=21.5ms

SRTF (Shortest Remaining Time First)

남은 실행 시간이 가장 짧은 프로세스를 우선 실행한다.
정해진 시간만큼 CPU를 이용하고, 다음으로 CPU를 사용할 프로세스는 남은 작업 시간이 가장 적은 프로세스로 선택한다.
최단 작업 우선 스케줄링 + 라운드 로빈 스케줄링
장점: 짧은 작업 우선 처리로 평균 대기 시간 감소.
단점: 긴 작업은 계속 대기할 가능성 있음.

예제

Time Quantum = 5ms

| 프로세스 | 실행 시간(Burst Time) | 대기 시간(Waiting Time) | 완료 시간(Turnaround Time) | | — | — | — | — | | P1 | 20ms | 15ms | 35ms | | P2 | 3ms | 0ms | 3ms | | P3 | 7ms | 7ms | 20ms | | P4 | 5ms | 3ms | 8ms |

0ms: P2 실행
3ms: P2 완료, P4 실행
8ms: P4 완료, P3 실행
13ms: P3 대기(남은 시간 2ms), P1 실행
18ms: P1 대기, P3 실행
20ms: P3 완료, P1 실행
35ms: P1 완료

결과

평균 대기 시간 = (15+0+7+3)/4=6.25ms

평균 완료 시간 = (35+3+20+8)/4=16.5ms

Priority Scheduling

프로세스들에 우선순위를 부여하고, 우선순위 높은 프로세스부터 실행한다.
동일한 우선순위를 가진 프로세스가 여러 개 있을 경우, 일반적으로 FCFS (First Come First Serve) 방식으로 실행된다.
장점: 중요 작업 우선 처리 가능.
단점: 낮은 우선순위 작업의 기아 현상(Starvation).

Aging 기법(시간이 지남에 따라 우선순위 증가).

오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식으로 대기 중인 프로세스의 우선순위를 점진적으로 증가시킨다. 우선순위가 낮아도 언젠가는 우선순위가 높아진다.

장점

기아 현상을 방지.
우선순위가 낮은 프로세스도 결국 CPU를 사용할 수 있도록 보장.

단점

오버헤드: 우선순위를 조정하는 데 추가적인 계산이 필요
우선순위 상승으로 인해 예기치 않은 실행 순서가 발생할 수 있음.

다단계 큐 스케줄링 (Multilevel queue)

우선순위 스케줄링의 발전된 형태로 우선순위별로 준비 큐를 여러 개 사용한다.
우선 순위가 가장 높은 큐에 있는 프로세스를 먼저 처리한다.
장점
- 프로세스 유형별로 우선순위를 구분하기 쉽다.
- 상황에 맞는 스케줄링 알고리즘을 적용할 수 있다.
단점: 우선순위 간 이동이 불가능 하기 때문에 우선순위가 낮은 프로세스는 계속해서 대기하는 기아 현상이 발생할 수 있다.

다단계 피드백 큐 스케줄링 (Multilevel feedback queue)

다단계 큐 스케줄링의 단점을 보완한 알고리즘으로 큐 간 이동을 허용한다.
CPU 스케줄링 방식의 가장 일반적인 형태
동작 원리
1. 높은 우선순위 큐에서 프로세스를 먼저 처리.
2. 일정 시간 동안 실행 후 시간 초과하면 하위 큐로 이동.
3. 하위 큐에서 대기 시간이 길어지면 다시 상위 큐로 이동

https://imbf.github.io/computer-science(cs)/2020/10/18/CPU-Scheduling.html

https://www.geeksforgeeks.org/cpu-scheduling-in-operating-systems/

https://www.robotstory.co.kr/raspberry/?vid=148

https://www.youtube.com/watch?v=CdrozYcVccE

https://www.youtube.com/watch?v=w1z6WCyMdhQ

추가

CFS (Completely Fair Scheduler )

모든 프로세스가 CPU 자원을 공평하게 사용할 수 있도록 보장하는 스케줄러
가상 런타임(Virtual Runtime)
- 각 프로세스가 CPU를 사용한 시간을 기록한 값
- CPU를 가장 적게 사용한 프로세스가 가장 먼저 실행된다.
- CPU 사용 시간이 많을수록 가상 런타임 값이 더 빨리 증가한다.
레드-블랙 트리(Red-Black Tree)
- 레드-블랙 트리라는 자료구조를 사용해 프로세스를 관리하며, 프로세스가 CPU를 사용한 시간에 따라 정렬한다.

특징

공정성 보장
- CPU 사용량이 적은 프로세스가 더 자주 실행된다.
- 우선순위가 높은 프로세스는 가상 런타임 증가 속도가 느려져 더 많은 CPU 시간을 할당받는다.
레드-블랙 트리 사용
- 모든 실행 가능한 프로세스를 가상 런타임을 기준으로 정렬하여 관리한다.
- 가장 가상 런타임이 작은 프로세스가 트리의 왼쪽 끝에 위치하고 먼저 실행된다.

CFS의 동작 방식

프로세스 삽입
- 새 프로세스가 실행 준비 상태(Ready)에 들어오면, 레드-블랙 트리에 삽입된다.
최소 가상 런타임 선택
- 레드-블랙 트리에서 가장 가상 런타임 값이 작은 프로세스를 선택하여 실행한다.
실행 및 가상 런타임 업데이트
- 프로세스가 실행되면 해당 프로세스의 가상 런타임 값이 증가한다.
- 실행이 끝난 후, 프로세스는 다시 레드-블랙 트리에 삽입된다.

장점

공정성: 모든 프로세스가 CPU를 공평하게 사용할 수 있다.
효율성: 레드-블랙 트리를 사용해 스케줄링 작업을 효율적으로 수행한다. O(log N)
우선순위 조정 가능: Nice 값을 통해 우선순위를 조정하여 특정 프로세스에 더 많은 CPU 시간을 할당할 수 있다.
- Nice 값: 프로세스의 우선순위(priority)를 조정하는 값
다양한 환경 지원

리눅스에서 CFS를 사용하는 이유

공정성, 성능, 확장성, 다양한 워크로드 처리 등을 모두 만족시키기 위함.

기존 스케줄러의 문제점

과거 리눅스는 우선순위 기반의 타임 슬라이스 방식을 사용했는데, 특정 프로세스가 불공정하게 자원을 독점하는 문제가 있었다.
- 👉 Nice 값으로 우선순위 조정
GUI 프로그램(인터랙티브 프로그램)이나 I/O 중심의 프로세스는 응답 시간이 매우 중요하지만, 기존 스케줄러는 CPU 중심 프로세스에 우선순위를 주어 지연(latency)이 발생했다.
특정 환경에 최적화된 스케줄러는 다른 환경에서는 비효율적일 수 있다.
- 예를 들어, I/O 중심 프로세스와 CPU 중심 프로세스가 섞인 경우 효율적으로 처리하지 못한다.
프로세스 수가 많아지면 성능이 급격히 저하되거나 관리 오버헤드가 증가 했다.
- 👉 레드-블랙 트리(Red-Black Tree) 구조로 성능 보장