[CS] CPU 스케줄링

눈치없어·2025년 2월 19일

CPU 스케줄링: 운영체제의 배분 방법
CPU 스케줄링 알고리즘: CPU 스케줄링의 절차
CPU 스케줄러: CPU 스케줄링 알고리즘을 결정하고 수행하는 운영체제의 일부분

실행의 문맥이 있다면 모두 스케줄링의 대상
프로세스뿐만 아니라 스레드도 CPU 스케줄링의 대상

스케줄링 관련 사전 지식

우선순위(Priority)

운영체제는 모든 프로세스가 CPU 자원을 공정하고 합리적으로 사용할 수 있도록
각 프로세스에 우선순위를 부여하여 CPU를 할당함

📌 프로세스 우선순위

운영체제는 프로세스별 우선순위를 판단하여 PCB에 저장
우선순위가 높은 프로세스는 더 빨리, 더 많이 CPU를 할당받음
사용자가 직접 일부 프로세스의 우선순위를 높일 수도 있음

리눅스, 유닉스, macOS에서는 ps 명령어를 통해 확인 가능

	> 운영체제가 메모리에 적재된 다수의 프로세스를 관리하려면, 각 프로세스를 식별할 정보가 필요
	이 역할을 수행하는 것이 프로세스 제어 블록(PCB, Process Control Block)

📌 프로세스 우선순위 할당 기준

CPU 활용률(CPU Utilization): CPU가 작업을 수행하는 시간의 비율
운영체제는 CPU 활용률을 최적화하기 위해 프로세스의 우선순위를 설정함

우선순위 할당 원칙
- CPU 활용률이 높은 상태를 유지하는 것이 목표
- 입출력 작업이 많은 프로세스의 우선순위를 높게 설정

📌 CPU 버스트 / 입출력 버스트

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오가며 실행
- CPU 버스트(CPU Burst): 프로세스가 CPU를 이용하는 작업
- 입출력 버스트(I/O Burst): 입출력장치를 기다리는 작업

✔ 프로세스의 유형

1️⃣ 입출력 집중 프로세스(I/O Bound Process)

입출력 장치를 자주 사용
실행보다 입출력 대기 상태에 머무르는 시간이 많음
예시: 비디오 재생, 디스크 백업 작업

2️⃣ CPU 집중 프로세스(CPU Bound Process)

CPU 연산이 많아 CPU를 집중적으로 사용
실행 시간이 길고 입출력 대기 시간이 적음
예시: 복잡한 수학 연산, 그래픽 처리

✔ 입출력 집중 프로세스는 우선순위가 높음

CPU 집중 프로세스보다 입출력 집중 프로세스를 먼저 실행하는 것이 효율적
입출력 작업을 먼저 처리한 후 CPU 집중 프로세스를 실행하면 CPU 활용률이 증가

📌 CPU 우선순위 배분 전략

모든 프로세스가 CPU를 순차적으로 사용하면 비효율적
CPU 활용률을 최적화하려면 상황에 맞게 CPU를 배분해야 함

✔ 입출력 집중 프로세스가 먼저 실행되도록 스케줄링
✔ 입출력 집중 프로세스를 빠르게 실행하여 입출력 장치를 계속 가동
✔ 그 후 CPU 집중 프로세스를 실행하여 CPU를 최대한 활용

요약:
운영체제는 CPU 활용률을 최적화하기 위해 프로세스마다 우선순위를 설정하며, 입출력 집중 프로세스가 CPU 집중 프로세스보다 높은 우선순위를 갖음

스케줄링 큐(Scheduling Queue)

운영체제는 프로세스들이 자원을 이용하고 싶다면 "줄을 서서 기다릴 것"을 요구함

자원을 사용하려는 프로세스들이 대기하는 줄(Queue)
운영체제는 이 큐를 이용해 여러 프로세스를 효율적으로 관리
각 프로세스의 PCB가 큐에 삽입되어 순서를 기다림

큐는 자료구조 개념에서 선입선출(FIFO)이지만, 스케줄링 큐는 반드시 FIFO일 필요 없음

📌 스케줄링 큐의 종류

1️⃣ 준비 큐(Ready Queue)

CPU를 사용하고 싶은 프로세스들이 대기하는 큐
준비 상태인 프로세스의 PCB가 대기
CPU를 할당받을 차례를 기다리는 공간
운영체제는 준비 큐에서 우선순위가 높은 프로세스를 먼저 실행

2️⃣ 대기 큐(Waiting Queue)

대기 상태에 접어든 프로세스의 PCB가 서는 큐
대기 상태인 프로세스의 PCB가 저장됨
입출력 장치가 완료 때까지 기다림

📌 스케줄링 큐에서 프로세스의 이동 과정

운영체제는 프로세스를 스케줄링 큐를 통해 관리하며, 프로세스는 여러 큐를 거치며 실행됨
CPU 실행 → 타이머 인터럽트 발생 → 다시 준비 큐로 이동
입출력 요청 → 대기 큐로 이동 → 입출력 완료 후 다시 준비 큐로 이동

프로세스의 흐름(정리)
1️⃣ 새로운 프로세스 생성 → 준비 큐로 이동
2️⃣ 준비 큐에서 우선순위에 따라 CPU 할당
3️⃣ CPU 실행 도중 타이머 인터럽트 발생 → 다시 준비 큐로 이동
4️⃣ 입출력 작업 요청 → 대기 큐로 이동
5️⃣ 입출력 작업 완료 → 다시 준비 큐로 이동
6️⃣ CPU에서 실행 완료 → 프로세스 종료

운영체제는 이 과정을 반복하며 여러 프로세스를 동시에 관리함

선점형 스케줄링 / 비선점형 스케줄링

📌 스케줄링이 발생하는 시점

운영체제에서 프로세스의 실행이 끝날 때만 스케줄링이 발생하는 것이 아니라, 실행 도중에도 특정 시점에서 스케줄링이 수행됨

대표적인 경우
- 입출력 작업 요청 시 (실행 → 대기 상태 전환)
- 타이머 인터럽트 발생 시 (실행 → 준비 상태 전환)

이때 스케줄링이 모든 경우에서 발생하면 → 선점형 스케줄링
입출력 요청 시에만 발생하면 → 비선점형 스케줄링

📌 선점형 스케줄링 (Preemptive Scheduling)

운영체제가 CPU를 강제로 빼앗아 다른 프로세스에게 할당하는 방식

운영체제가 실행 중인 프로세스를 중단할 수 있음
CPU를 사용 중인 프로세스라도 더 중요한 프로세스가 생기면 교체 가능
타이머 인터럽트 발생 시 강제적으로 다른 프로세스에게 CPU 할당

📌 비선점형 스케줄링 (Non-Preemptive Scheduling)

한 프로세스가 CPU를 차지하면, 끝날 때까지 다른 프로세스가 끼어들 수 없는 방식

CPU를 점유한 프로세스가 끝날 때까지 기다려야 함
운영체제가 CPU를 강제로 빼앗지 않음
프로세스가 자발적으로 종료되거나 입출력 요청 시에만 CPU가 다른 프로세스로 이동

요약:
선점형 스케줄링: 중요한 프로세스를 빠르게 실행, 하지만 문맥 교환 비용(오버헤드) 발생
비선점형 스케줄링: 문맥 교환 비용 적지만, CPU 독점 가능성 있음

CPU 스케줄링 알고리즘

대표적인 7가지 알고리즘

1️⃣ 선입 선처리 스케줄링

단순히 준비 큐에 삽입된 순서대로 CPU를 할당하는 방식(가장 단순함)
실행 시간이 긴 프로세스가 먼저 도착하면, 이후 프로세스들이 오래 기다려야 하는 문제 발생
```
이를 호위 효과(Convoy Effect) 라고 함
```

2️⃣ 최단 작업 우선 스케줄링

준비 큐에 삽입된 프로세스 중 CPU 실행 시간이 가장 짧은 프로세스를 먼저 실행하는 방식
일반적으로 비선점형 스케줄링 이지만, 선점형으로 구현될 수도 있음

3️⃣ 라운드 로빈 스케줄링

> 타임 슬라이스: 프로세스가 CPU를 사용하도록 정해진 시간

선입선처리 방식 + 타임 슬라이스 개념 추가
큐에 삽입된 순서대로 CPU를 이용하되, 정해진 타임 슬라이스만큼만 CPU를 사용하는 방식

시간이 지나면 문맥 교환이 발생하여 다음 프로세스로 넘어감

4️⃣ 최소 잔여 시간 우선 스케줄링

최단 작업 우선 스케줄링 + 라운드 로빈
남은 실행 시간이 가장 적은 프로세스를 우선 실행하는 방식

5️⃣ 우선순위 스케줄링

각 프로세스에 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행하는 방식
선점형 & 비선점형 방식 모두 가능

우선순위가 낮은 프로세스는 계속 실행이 지연될 가능성이 있음 → 아사 현상 발생 가능
이를 방지하기 위해 에이징(Aging) 기법 사용 (오래 기다린 프로세스의 우선순위를 점점 높임)

6️⃣ 다단계 큐 스케줄링

우선순위별로 여러 개의 준비 큐를 사용하는 방식

우선순위가 높은 큐의 프로세스를 먼저 실행
프로세스들이 큐 사이를 이동할 수 없음
우선순위가 낮은 프로세스는 계속 실행이 밀릴 가능성이 있음 (아사 현상 발생 가능)

7️⃣ 다단계 피드백 큐 스케줄링

다단계 큐 스케줄링 + 프로세스가 큐 사이를 이동 가능
처음에는 우선순위가 높은 큐에서 실행, 실행 시간이 길어지면 점점 낮은 큐로 이동
입출력 집중 프로세스는 우선순위가 높은 큐에서 빠르게 처리

오래 기다린 프로세스는 다시 높은 우선순위 큐로 이동할 수 있음 (에이징 적용 가능)
CPU 집중 프로세스는 낮은 우선순위 큐로 이동하여 자원을 효율적으로 사용

📌 스케줄링 알고리즘 비교

스케줄링 방식	선점형 여부	장점	단점
선입선처리 스케줄링	비선점형	구현이 간단	호위 효과 발생
최단 작업 우선 스케줄링	비선점형	평균 대기 시간이 짧음	아사 현상 발생 가능
라운드 로빈 스케줄링	선점형	공평한 CPU 할당	문맥 교환 비용(오버헤드) 발생
최소 잔여 시간 우선 스케줄링	선점형	평균 대기 시간 최소화	기아 현상 발생 가능
우선순위 스케줄링	둘 다 가능	우선순위 높은 작업을 빠르게 실행	기아 현상 발생 가능 (에이징 필요)
다단계 큐 스케줄링	둘 다 가능	프로세스 특성에 맞는 실행 가능	기아 현상 발생 가능
다단계 피드백 큐 스케줄링	선점형	CPU 활용 최적화 + 기아 현상 해결	구현이 복잡함

요약

선입선처리 스케줄링 → 먼저 온 순서대로 실행, 하지만 긴 프로세스가 있으면 대기 시간 증가

최단 작업 우선 스케줄링 → 짧은 작업을 먼저 실행, 하지만 긴 프로세스가 계속 밀릴 가능성

라운드 로빈 스케줄링 → 정해진 시간(TS) 동안만 실행 후 교체, 문맥 교환 많음

최소 잔여 시간 우선 스케줄링 → 실행 시간이 가장 짧은 프로세스 먼저 실행, 하지만 기아 현상 발생 가능

우선순위 스케줄링 → 우선순위 높은 프로세스 먼저 실행, 하지만 기아 현상 발생 가능

다단계 큐 → 여러 개의 큐에서 우선순위에 따라 실행, 하지만 기아 현상 발생 가능

다단계 피드백 큐 → 큐를 이동하며 CPU 사용 최적화, 기아 현상 해결 가능

기아 현상과 아사 현상은 거의 같은 의미로 쓰이지만, 기아 현상은 CPU 스케줄링 문제에서, 아사 현상은 좀 더 광범위한 자원 할당 문제에서 발생하는 개념

리눅스 CPU 스케줄링

리눅스 스케줄링 정책

스케줄링 정책	적용 상황
SCHED_FIFO	실시간성 프로세스에 적용되는 정책 (매우 높은 우선순위를 할당함)
SCHED_RR	실시간성 프로세스에 적용되는 정책 (매우 높은 우선순위를 할당함)
SCHED_NORMAL	일반적인 프로세스에 적용되는 정책
SCHED_BATCH	일반적인 프로세스만큼 자주 선점하지 않는 배치 작업에 적용되는 정책
SCHED_IDLE	우선순위가 매우 낮은 프로세스에 적용되는 정책(매우 낮은 우선순위를 할당함)

SCHED_FIFO: 위 선입선출에서 설명
SCHED_RR: 위 라운드로빈에서 설명
SCHED_NORMAL
- 일반적인 프로세스에 사용되는 정책 (디폴트)
- CFS를 기반으로 동작
- CFS는 완전히 공평한 CPU 시간 배분을 목표로 하는 스케줄러

vruntime (가상 실행 시간)

프로세스가 실행된 시간이 아닌, 프로세스의 가중치를 고려한 가상의 실행 시간

우선순위가 높을수록 vruntime이 천천히 증가 → 더 오래 실행될 수 있음
가중치가 높은 프로세스(우선순위가 높은 프로세스)는 CPU를 더 오래 사용 가능

계산공식

CFS의 타임슬라이스 계산

가중치가 높은 프로세스는 더 많은 타임슬라이스를 받음
가중치가 낮은 프로세스는 적은 타임슬라이스를 받음
우선순위가 높은 프로세스는 더 자주 실행되고, 우선순위가 낮은 프로세스는 실행 빈도가 줄어듦

계산공식

리눅스에서 프로세스의 vruntime & 가중치 확인

/proc/<PID>/sched 명령어를 사용하면 특정 프로세스의 스케줄링 정보를 확인할 수 있음

$ cat /proc/34193/sched
bash(34193, #threads: 1)
--------------------------------------
se.exec_start : 1895846397.856628
se.vruntime : 4599515.302565
se.sum_exec_runtime : 73.672331
:
se.load.weight : 1048576
se.runnable_weight : 1048576
se.avg.load_sum : 599
:
policy : 0
prio : 120

참고: 북스터디 - 이것이 취업을 위한 컴퓨터 과학이다 (Chapter 3-4)

눈치없어

dock 사이즈 다르잖아

이전 포스트

[CS] 동기화와 교착 상태

다음 포스트