03 - 4 CPU 스케줄링

CPU 스케줄링 : CPU를 어떤 프로세스에 할당할지를 결정하는 과정

(운영체제(OS)가 여러 프로세스를 효율적으로 실행하기 위함)

• CPU 스케줄 알고리즘 - 운영체제가 프로세스에 CPU를 배분하는 방법
• CPU 스케줄러 - 스케줄 알고리즘을 결정하고 수행하는 운영체제의 일부분

실행 문맥이 있다면 모두 스케줄링 대상

• 프로세스 뿐만 아니라 스레드도 CPU 스케줄링의 대상이다.
• 실행의 문맥을 가지고 있는 모든 것은 스케줄링 할 수 있기 때문

우선 순위

1. 운영체제는 프로세스별 우선순위를 판단하여 PCB(Process Control Block)에 명시
2. 우선 순위가 높은 프로세스에는 CPU의 자원을 더 빨리 , 많이 할당
3. 일부 프로세스의 우선순위를 직접 높힐 수도 있음
4. 운영체제마다 프로세스의 우선순위 확인 가능

---

운영체제는 어떤 프로세스에 높고 낮은 우선순위를 할당할까?

운영체제(OS)는 프로세스가 어떤 유형인지에 따라 우선순위를 다르게 부여한다.

CPU 스케줄링 우선순위

우선순위 기준 높은 우선순위 (✅) 낮은 우선순위 (❌)

프로세스 유형	운영체제 핵심 프로세스, I/O 중심 프로세스, 실시간 프로세스	배치 작업 (Batch Jobs), CPU 중심 프로세스
사용자 vs 시스템	운영체제의 핵심 프로세스, 관리자 실행 작업	일반 사용자가 실행한 애플리케이션, 백그라운드 프로세스
긴급성	마감 기한이 있는 실시간 작업 (예: 자동차 브레이크, 항공 관제), 인터랙티브 작업 (예: 키보드 입력, 마우스 클릭)	대기 시간이 길어도 되는 작업 (예: 파일 다운로드, 대량 데이터 처리), 소프트웨어 업데이트
자원 사용 패턴	빠르게 끝나는 짧은 작업 (Short Jobs), 적은 CPU 사용 작업 (I/O-bound)	오래 걸리는 작업 (Long Jobs), CPU 사용량이 높은 작업 (CPU-bound)
사용자 설정	Nice 값이 낮음 (예: nice -20), 시스템 관리자가 설정한 중요한 작업	Nice 값이 높음 (예: nice +19), 사용자가 낮은 우선순위로 설정한 작업

대부분의 프로세스들은 CPU와 입출력장치를 모두 사용해 실행과 대기 상태를 오가며 실행

용어

• CPU 활용률(Utilization) - CPU의 가동 시간 중 작업을 처리하는 시간의 비율을 의미
• CPU 버스트(Burst) - 프로세스가 cpu를 이용하는 작업
• 입출력 버스트 - 입출력 장치를 기다리는 작업

프로세스마다 입출력 장치를 이용하는 시간과 CPU를 이용하는 시간의 양에는 차이가 잇다.

밑은 그에 대한 용어다.

✅ 입출력 집중 프로세스 (I/O-Bound Process)

• CPU 연산보다는 **입출력 작업(디스크, 네트워크, 키보드 등)**을 많이 수행하는 프로세스
• CPU를 자주 쉬게 하므로 대기 시간이 길고, 빠른 응답이 필요
• 예: 파일 다운로드, 웹 브라우저, 데이터베이스 쿼리

✅ CPU 집중 프로세스 (CPU-Bound Process)

• 입출력보다는 연산 작업이 많아 CPU를 오래 사용하는 프로세스
• CPU를 최대한 활용하지만 다른 프로세스가 실행될 기회를 줄일 수 있음
• 예: 인공지능 연산, 대규모 데이터 분석, 비디오 렌더링

👉 운영체제는 I/O 집중 프로세스를 먼저 실행해서 CPU를 쉬지 않도록 최적화함!

  **`(추가)모든 프로세스가 동일한 시간의 빈도로 CPU를 사용하는 것은 합리적이지 않다.`**

 

+스케줄링에 사용되는 큐가 반드시 선입선출일 필요는 없다.

큐 종류(운영체제가 관리하는 줄)

• 준비 큐(Ready Queue) - CPU를 이용하고 싶은 프로세스의 PCB가 서는 줄
• 대기 큐(Wating Queue) - 대기 상태에 접어든 프로세스의 PCB가 서는 줄

+ 잠깐 PCB란? 이것들이 들어있음

• 운영체제가 각 프로세스의 정보를 저장하는 구조체
• 프로세스가 생성될 때 할당되며, 운영체제가 프로세스를 관리하는 핵심 데이터

항목 설명

PID (Process ID)	프로세스 식별 번호
프로세스 상태	실행 중, 대기 중, 종료 등
레지스터 정보	프로그램 카운터(PC), CPU 레지스터 값
메모리 정보	프로그램 코드, 데이터, 스택 위치
스케줄링 정보	우선순위, 스케줄링 큐 위치
입출력 정보	파일 핸들, 입출력 장치 정보
계정 정보	소유자, 권한 등

🔄 준비 큐 & 대기 큐 동작 원리( 입출력 I/O )

1️⃣ 프로세스가 생성되면 준비 큐로 들어감

2️⃣ CPU 스케줄러가 준비 큐에서 프로세스를 선택하여 CPU에 할당

3️⃣ 실행 중이던 프로세스가

• ✅ 실행을 마치면 종료
• ⏳ I/O 작업이 필요하면 대기 큐로 이동

4️⃣ 대기 큐에서 I/O가 끝나면 다시 준비 큐로 돌아옴 5️⃣ 이 과정이 계속 반복되면서 프로세스가 실행됨

큐에 삽입된 순서대로 실행하되,우선순위가 높은 프로세스부터 실행한다.

🔥 핵심 포인트

• 준비 큐 → CPU 실행 → 대기 큐 → 준비 큐 반복
• 준비 큐에서는 CPU 실행을 기다림, 대기 큐에서는 I/O 작업을 기다림
• 운영체제는 이 두 개의 큐를 관리하며 효율적으로 프로세스를 실행

---

선점형 스케줄링 (CPU 자원 강탈 도둑)

운영체제가 프로세스로부터 CPU 자원을 강제로 빼앗아 다른 프로세스에 할당할 수 있는 스케줄링

장점

• 응답 시간이 빠름 (긴급한 프로세스를 즉시 실행 가능)
• 높은 우선순위 프로세스가 빨리 실행됨
• 멀티태스킹 환경에서 유리

단점

• 문맥 전환(Context Switch) 비용 발생 → CPU 오버헤드 증가
• 낮은 우선순위 프로세스가 계속 밀릴 가능성 (Starvation 문제 발생)

언제 사용?

• 실시간 시스템 → 긴급한 작업을 먼저 실행해야 할 때 (예: 항공 관제 시스템, 의료 장비)
• 멀티태스킹 OS → 여러 프로세스를 공평하게 실행해야 할 때 (예: 일반적인 데스크톱 OS)
• 우선순위 스케줄링 → 높은 우선순위의 작업이 들어오면 즉시 실행해야 할 때

사용되는 스케줄링 알고리즘

✔ Round Robin (RR) → 일정 시간마다 프로세스를 교체 (타임 퀀텀)

✔ SRTF (Shortest Remaining Time First) → 남은 실행 시간이 짧은 작업을 먼저 실행

✔ 우선순위 스케줄링 (Priority Scheduling, Preemptive) → 높은 우선순위가 들어오면 강제 교체

---

비선형 스케줄링 (빈집털이 도둑)

어떤 프로세스가 CPU를 사용하고 있을 때

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

장점

• 문맥 전환이 적어 오버헤드가 낮음
• 한 프로세스가 CPU를 끝까지 사용하므로 예측 가능성 높음

단점

• 긴 작업이 CPU를 독점하면 짧은 작업이 오래 기다려야 함 (Convoy Effect)
• 실시간 응답이 중요한 환경에서는 비효율적

🔥 한 줄 정리

선점형은 빠르지만 오버헤드 있음, 비선점형은 안정적이지만 오래 걸릴 수 있음!

언제 사용?

• 배치 작업 (Batch Processing) → 프로세스를 중간에 끊지 않고 끝까지 실행해야 할 때 (예: 대량 데이터 처리, 백그라운드 작업)
• 일괄 처리 시스템 → CPU 오버헤드를 줄이고 단순한 작업을 처리할 때
• 임베디드 시스템 → 실행 도중 멈추면 안 되는 시스템 (예: 공장 자동화, 단순 제어 시스템)

사용되는 스케줄링 알고리즘

✔ FCFS (First Come First Served) → 먼저 도착한 작업부터 실행

✔ SJF (Shortest Job First, Non-Preemptive) → 실행 시간이 가장 짧은 작업부터 처리

✔ 우선순위 스케줄링 (Priority Scheduling, Non-Preemptive) → 우선순위가 높은 순서대로 실행 (중간에 강제 교체 없음)

---

CPU 스케줄링 알고리즘

1️⃣ FCFS (First-Come, First-Served)

• 먼저 온 프로세스를 먼저 실행 (줄 서기 시스템)
• 구현이 쉽지만 Convoy Effect로 긴 작업이 있으면 대기 시간이 길어짐
• 예: P1(10ms) → P2(3ms) → P3(2ms) → 실행 순서: P1 → P2 → P3
• • 가상실행시간(vruntime) :
    Linux CFS(Completely Fair Scheduler)에서 각 프로세스가 실행한 시간을 추적하는 값으로, 낮을수록 CPU를 더 받을 우선순위가 높음

2️⃣ SJF (Shortest Job First)

• 실행 시간이 짧은 프로세스를 먼저 실행 (짧은 놈 우선)
• 평균 대기 시간이 짧지만 Starvation 문제 발생 가능
• 예: P2(2ms) → P4(3ms) → P1(6ms) → P3(8ms)

3️⃣ SRTF (Shortest Remaining Time First)

• SJF의 선점형 버전, 실행 중이더라도 더 짧은 작업이 오면 강제 교체됨
• 빠른 응답이 가능하지만 문맥 전환 오버헤드 증가
• 예: P1(10ms) 실행 중 → P2(5ms) 도착 → P1 중단 → P2 실행

4️⃣ RR (Round Robin)

• 각 프로세스가 타임 퀀텀만큼 실행 후 순차적으로 교체됨
• 공평하지만 타임 퀀텀 설정이 중요 (너무 크면 FCFS와 비슷)
• 예: P1(4ms) → P2(3ms) → P3(4ms) → P1(6ms) → P3(3ms)

5️⃣ Priority Scheduling

• 우선순위가 높은 프로세스를 먼저 실행 (높은 놈 먼저)
• Starvation 문제가 발생할 수 있어 Aging 기법이 필요함
• 예: P2(우선순위 1) → P3(2) → P1(3) → 실행 순서: P2 → P3 → P1

6️⃣ Multi-Level Queue

• 프로세스를 여러 개의 큐로 나누고, 각 큐마다 다른 스케줄링 적용
• 시스템/사용자/배치 작업 등 역할별로 분리하여 최적화
• 예: 시스템(FCFS), 사용자(RR), 배치(SJF) 등 다른 방식 적용

7️⃣ Multi-Level Feedback Queue

• Multi-Level Queue의 개선 버전으로 큐 간 이동 가능
• CPU를 많이 쓰면 낮은 우선순위 큐로 밀리고, 오래 대기하면 우선순위 상승
• 예: 처음엔 높은 우선순위 큐 → 오래 실행되면 낮은 큐로 이동

알고리즘 방식 장점 단점

FCFS(선입 선처리)	먼저 온 순서대로 실행	구현 쉬움, 공평함	Convoy Effect 발생
SJF(최단 작업 우선)	실행 시간이 짧은 놈 먼저	평균 대기시간 최소화	Starvation 문제
SRTF(최소잔여시간 우선)	남은 시간이 짧은 놈 먼저 (선점형)	빠른 응답 가능	문맥 전환 오버헤드
RR(라운드 로빈)	일정 시간씩 CPU 할당	공평하고 반응 속도 빠름	타임 퀀텀 설정 중요
Priority(우선 순위)	우선순위 높은 놈 먼저	중요한 작업 먼저 처리	Starvation 문제
**Multi-Level Queue
(다단계 큐)**	여러 개의 큐로 분리	다양한 작업에 적합	유연성이 부족할 수 있음
**Multi-Level Feedback Queue
(다단계 피드백 큐)**	다중 큐 + 동적 우선순위 조정	효율성과 공정성 ↑	구현이 복잡함

---

🔥 한 줄 요약

1️⃣ FCFS - 선착순 배식

2️⃣ SJF - 짧은 놈 먼저

3️⃣ SRTF - 짧은 놈 먼저 + 강탈 가능

4️⃣ RR - 한 입씩 공평하게

5️⃣ Priority - 높은 놈 먼저

6️⃣ Multi-Level Queue - 급 나누기

7️⃣ MLFQ - 급 나누기 + 적응형