운영체제는 CPU 자원을 효율적으로 관리하기 위해 프로세스에 CPU 사용 시간을 배분한다. 이 글에서는 CPU 스케줄링의 기본 개념과 다양한 스케줄링 알고리즘을 다룬다.

1️⃣ CPU 스케줄링의 개념

CPU 스케줄링(CPU Scheduling)은 운영체제가 프로세스에 CPU 사용 시간을 배분하는 방법을 말한다.

CPU 스케줄링의 구성 요소

• CPU 스케줄링 알고리즘: CPU 스케줄링의 절차를 정의한 알고리즘
• CPU 스케줄러(CPU Scheduler): 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 구성 요소

💡 스케줄링의 대상

프로세스뿐만 아니라 스레드도 CPU 스케줄링의 대상이다. 실행의 문맥을 가지고 있는 모든 것을 스케줄링할 수 있기 때문이다. 일반적으로 '프로세스를 스케줄링한다'는 표현은 실행의 문맥이 있는 모든 대상을 의미한다.

2️⃣ 우선순위 (Priority)

우선순위의 필요성

운영체제는 CPU 자원을 공정하고 합리적으로 프로세스에 할당해야 한다. 여기서 공정한 배분이란 단순히 돌아가면서 CPU를 할당하는 것이 아니라, 프로세스의 우선순위를 고려한 배분을 의미한다.

2-1 우선순위의 특징

• 프로세스별로 다른 우선순위를 가짐
• PCB에 명시됨
• 우선순위가 높은 프로세스는 CPU 자원을 더 빨리, 더 많이 할당받음
• 사용자가 일부 프로세스의 우선순위를 직접 조정할 수 있음

2-2 우선순위 확인 방법

유닉스/리눅스/맥OS에서 우선순위 확인

$ ps -l
F S UID  PID  PPID  C PRI NI ADDR SZ WCHAN  TTY      TIME CMD
0 S 1000 4412 4409  0  80  0    - 3210 do_wat pts/0 00:00:00 bash
0 R 1000 5149 4412  0  80  0    - 3495        pts/0 00:00:00 ps

PRI 열에서 프로세스의 우선순위를 확인할 수 있다.

Windows에서 우선순위 확인

Process Explorer의 'Priority' 항목을 통해 확인할 수 있다. 이 외에도 다음 정보를 확인할 수 있다:

• Threads: 스레드 수
• Context Switches: 문맥 교환 발생 횟수

CPU 활용률과 우선순위

운영체제는 CPU 활용률을 높게 유지할 수 있도록 우선순위를 할당한다.

CPU 활용률: 전체 CPU 가동 시간 중 작업을 처리하는 시간의 비율을 의미한다.

2-3 CPU 버스트와 입출력 버스트

대부분의 프로세스는 CPU와 입출력장치를 번갈아 사용하며 실행된다:

2-4 프로세스의 분류

프로세스는 CPU와 입출력장치 사용 비율에 따라 분류된다:

⚡ 입출력 집중 프로세스의 우선순위가 높은 이유

입출력 집중 프로세스를 먼저 실행하여 입출력장치를 작동시킨 후, CPU 집중 프로세스에 CPU를 할당하는 것이 CPU 활용률을 높이는 데 효율적이다:

1. 입출력 집중 프로세스 먼저 실행
2. 입출력 작업 시작 → 프로세스는 대기 상태로 전환
3. CPU 집중 프로세스가 CPU 사용
4. CPU 활용률 증가

3️⃣ 스케줄링 큐 (Scheduling Queue)

운영체제는 프로세스에게 자원을 이용하려면 큐에 줄을 서서 기다릴 것을 요구한다.

스케줄링 큐의 종류

스케줄링 큐는 프로세스들이 자원을 기다리는 줄을 구현한 자료구조다:

• CPU를 이용하고 싶은 프로세스의 PCB
• 메모리에 적재되고 싶은 프로세스의 PCB
• 특정 입출력장치를 이용하고 싶은 프로세스의 PCB

💡 스케줄링 큐의 특징

자료구조 관점에서 큐는 선입선출(FIFO) 구조를 따르지만, 스케줄링에 사용되는 큐가 반드시 선입선출일 필요는 없다. 우선순위를 고려하여 순서를 조정할 수 있다.

3-1 대표적인 스케줄링 큐

준비 큐 (Ready Queue)

CPU를 이용하고 싶은 프로세스의 PCB가 대기하는 큐다.

• 준비 상태인 프로세스의 PCB가 삽입됨
• 우선순위가 높은 프로세스부터 먼저 실행됨

대기 큐 (Waiting Queue)

대기 상태에 접어든 프로세스의 PCB가 대기하는 큐다.

• 주로 입출력 작업을 수행 중일 때 사용
• 입출력 완료 인터럽트를 기다림

프로세스의 큐 이동

프로세스는 상태에 따라 다양한 큐를 이동한다:

[준비 큐] → [실행] → [대기 큐] → [준비 큐]
            ↓
         [종료]

3-2 큐 이동의 조건

🔄 입출력 완료 처리 과정

1. 입출력 완료 인터럽트 발생
2. 운영체제가 대기 큐에서 완료된 PCB 탐색
3. 해당 PCB를 준비 상태로 변경
4. 대기 큐에서 제거
5. 준비 큐로 이동

4️⃣ 선점형과 비선점형 스케줄링

스케줄링은 기본적으로 프로세스의 실행이 끝나면 이루어진다. 하지만 프로세스가 종료되지 않았음에도 스케줄링이 수행되는 경우가 있다.

스케줄링이 발생하는 시점

프로세스 실행 도중 스케줄링이 이루어지는 대표적인 두 시점:

1. 실행 상태 → 대기 상태: 입출력 작업을 위해 대기 상태로 전환
2. 실행 상태 → 준비 상태: 타이머 인터럽트 발생

4-1 선점형 스케줄링

선점형 스케줄링은 현재 프로세스가 CPU를 사용하고 있더라도 운영체제가 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링 방식이다.

✅ 장점

• 더 급한 프로세스가 끼어들어 CPU를 사용할 수 있음
• 한 프로세스의 CPU 독점을 방지
• 여러 프로세스에 골고루 CPU 자원을 배분

⚠️ 단점

• 문맥 교환 과정에서 오버헤드 발생 가능

4-2 비선점형 스케줄링

비선점형 스케줄링은 프로세스가 종료되거나 스스로 대기 상태에 접어들기 전까지 다른 프로세스가 끼어들 수 없는 스케줄링 방식이다.

✅ 장점

• 문맥 교환 횟수가 적어 오버헤드 발생이 적음

⚠️ 단점

• CPU를 사용 중인 프로세스가 있으면 급한 프로세스도 무작정 기다려야 함

5️⃣ 전통적 CPU 스케줄링 알고리즘

전통적으로 많은 교재에서 소개되는 대표적인 CPU 스케줄링 알고리즘을 살펴본다.

FCFS (First Come First Served)

FCFS 스케줄링은 준비 큐에 삽입된 순서대로 프로세스를 실행하는 비선점형 스케줄링 방식이다.

5-1 FCFS의 특징

• 가장 단순한 스케줄링 알고리즘
• 먼저 CPU를 요청한 프로세스부터 CPU를 할당받음

⚠️ 호위 효과

먼저 삽입된 프로세스의 오랜 실행 시간으로 인해 나중에 삽입된 프로세스의 실행이 지연되는 문제를 말한다.

준비 큐: [프로세스 A(20ms)] → [프로세스 B(10ms)] → [프로세스 C(5ms)]

실행 순서: A(20ms) → B(10ms) → C(5ms)
대기 시간: A(0ms), B(20ms), C(30ms) ← 호위 효과 발생

SJF (Shortest Job First)

SJF 스케줄링은 CPU를 이용하는 시간의 길이가 가장 짧은 프로세스부터 실행하는 스케줄링 방식이다.

5-2 SJF의 특징

• 기본적으로 비선점형 스케줄링
• 평균 대기 시간을 최소화할 수 있음

💡 SJF의 선점형 버전

SJF는 선점형으로도 구현될 수 있다. 이를 최소 잔여 시간 우선(SRT) 스케줄링이라고 한다.

Round Robin

라운드 로빈 스케줄링은 FCFS에 타임 슬라이스 개념이 더해진 선점형 스케줄링 방식이다.

5-3 라운드 로빈의 구성 요소

🕐 타임 슬라이스 (Time Slice)

프로세스가 CPU를 사용하도록 정해진 시간을 의미한다.

• 프로세스는 정해진 타임 슬라이스만큼만 CPU를 이용
• 타임 슬라이스를 모두 사용하면 문맥 교환 발생
• 프로세스는 준비 큐의 맨 뒤에 재삽입

준비 큐: [P1(10ms)] → [P2(5ms)] → [P3(8ms)]
타임 슬라이스: 4ms

실행 순서:
P1(4ms) → P2(4ms) → P3(4ms) → P1(4ms) → P3(4ms) → P1(2ms) → P2(1ms)

SRT (Shortest Remaining Time)

SRT 스케줄링은 SJF와 라운드 로빈을 합친 선점형 스케줄링 방식이다.

5-4 SRT의 특징

• 정해진 타임 슬라이스만큼 CPU를 이용
• 남아 있는 작업 시간이 가장 적은 프로세스를 다음 실행 대상으로 선택

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

우선순위 스케줄링은 프로세스에 우선순위를 부여하고, 가장 높은 우선순위를 가진 프로세스부터 실행하는 방식이다.

5-5 우선순위 스케줄링의 문제점

🚨 아사 현상 (Starvation)

우선순위가 낮은 프로세스는 우선순위가 높은 프로세스로 인해 계속해서 실행이 연기될 수 있다.

💊 에이징 (Aging)

아사 현상을 방지하기 위한 기법으로, 오랫동안 대기한 프로세스의 우선순위를 점차 높이는 방식이다.

초기 우선순위: P1(10), P2(5), P3(3)
에이징 적용 후: P1(10), P2(5→7), P3(3→6)

다단계 큐 (Multilevel Queue)

다단계 큐 스케줄링은 우선순위별로 여러 개의 준비 큐를 사용하는 스케줄링 방식이다.

5-6 다단계 큐의 동작 방식

1. 우선순위가 가장 높은 큐의 프로세스를 먼저 처리
2. 해당 큐가 비어 있으면 다음 우선순위 큐의 프로세스 처리

[우선순위 0 큐] → CPU 할당
[우선순위 1 큐] → 우선순위 0이 비어 있을 때 CPU 할당
[우선순위 2 큐] → 우선순위 0, 1이 비어 있을 때 CPU 할당

⚠️ 문제점

프로세스들이 큐 사이를 이동할 수 없기 때문에 우선순위가 낮은 프로세스의 작업이 계속해서 연기될 수 있다 (아사 현상).

다단계 피드백 큐 (Multilevel Feedback Queue)

다단계 피드백 큐 스케줄링은 다단계 큐와 비슷하지만, 프로세스들이 큐 사이를 이동할 수 있다는 점에서 차이가 있다.

5-7 다단계 피드백 큐의 동작 방식

1. 새로운 프로세스는 우선순위가 가장 높은 큐에 삽입
2. 타임 슬라이스 동안 실행
3. 실행이 끝나지 않으면 다음 우선순위 큐로 이동
4. 오래 CPU를 사용해야 하는 프로세스의 우선순위가 점차 낮아짐

🎯 특징

• CPU 집중 프로세스의 우선순위는 자연스럽게 낮아짐
• 입출력 집중 프로세스는 높은 우선순위 큐에서 실행 완료
• 에이징 기법 적용 가능 (낮은 우선순위 큐에서 오래 기다린 프로세스를 높은 우선순위 큐로 이동)

[우선순위 0 큐] 타임 슬라이스: 2ms
       ↓ (완료되지 않으면)
[우선순위 1 큐] 타임 슬라이스: 4ms
       ↓ (완료되지 않으면)
[우선순위 2 큐] 타임 슬라이스: 8ms

6️⃣ 리눅스 CPU 스케줄링

실제 리눅스 운영체제에서는 상황에 따라 다양한 스케줄링 알고리즘이 사용된다.

스케줄링 정책 (Scheduling Policy)

스케줄링 정책은 새로운 프로세스를 언제 어떻게 선택하여 실행할지를 결정하기 위한 규칙의 집합이다.

6-1 리눅스의 스케줄링 정책

CFS (Completely Fair Scheduler)

CFS는 SCHED_NORMAL 정책 하에서 일반적인 프로세스에 적용되는 CPU 스케줄러다.

6-2 CFS의 특징

🎯 완전히 공평한 CPU 시간 배분

CFS는 이름처럼 프로세스에 대해 완전히 공평한 CPU 시간 배분을 지향한다.

6-3 가상 실행 시간 (vruntime)

vruntime(Virtual Runtime)은 프로세스의 가중치를 고려한 가상의 실행 시간이다.

vruntime 계산 공식

vruntime = 실제 실행 시간 × (평균 가중치 / 프로세스의 가중치)

vruntime의 특징

• 가중치가 높을수록 vruntime이 천천히 증가
• vruntime이 가장 작은 프로세스부터 스케줄링
• 프로세스의 가중치가 높을수록 먼저 스케줄링될 확률이 높음

💡 가중치 (Weight)

가중치는 프로세스의 우선순위와 연관된 값으로, 프로세스의 우선순위가 높아질수록 가중치도 높아진다.

6-4 타임 슬라이스 계산

CFS에서 프로세스의 타임 슬라이스는 가중치에 따라 결정된다:

타임 슬라이스 = (프로세스의 가중치 / 전체 가중치) × 전체 타임 슬라이스 합

📊 특징

• 프로세스의 가중치가 높아지면 타임 슬라이스도 크게 할당받음
• 우선순위가 높은 프로세스는 더 오래 CPU를 사용할 수 있음

6-5 vruntime과 가중치 확인

리눅스에서는 다음 명령어로 프로세스의 vruntime과 가중치를 확인할 수 있다:

$ cat /proc/<PID>/sched

예를 들어, PID가 34913인 프로세스의 정보를 확인:

$ cat /proc/34913/sched
se.vruntime              : 12345678.123456
se.sum_exec_runtime      : 1234.567890
se.load.weight           : 1024

7️⃣ 정리

스케줄링 기본 개념

• 우선순위: CPU 활용률을 높이기 위해 입출력 집중 프로세스의 우선순위가 높음
• 스케줄링 큐: 준비 큐와 대기 큐를 통해 프로세스 관리
• 선점형/비선점형: 문맥 교환 빈도와 응답 시간의 트레이드오프

전통적 스케줄링 알고리즘

리눅스 스케줄링

• RT 스케줄러: 실시간 프로세스 (FIFO, RR)
• CFS 스케줄러: 일반 프로세스 (vruntime 기반 공평한 배분)