(OS) CPU 스케줄러와 디스패처, 그리고 스케줄링 알고리즘 총정리

 CPU 스케줄러와 디스패처, 그리고 스케줄링 알고리즘 총정리

---

 CPU 스케줄러란?

• 역할: CPU를 어떤 프로세스가 사용할지 선택
• 동작: Ready 상태에 있는 프로세스들 중 하나를 선택하여 CPU에 할당
• 대상: Ready Queue에 있는 프로세스들

예: 
Ready Queue: P1, P2, P3  
스케줄러가 P2를 선택 → 실행 준비 완료

사진 출처- 유튜브 쉬운코드

 

 

---

디스패처(Dispatcher)란?

• 역할: 스케줄러가 선택한 프로세스를 실제 CPU에 할당하고 실행
• 세부 기능:
  • 컨텍스트 스위칭 수행
  • 사용자 모드로 전환 (커널 → 유저 모드)
  • 프로그램 카운터와 레지스터 설정

예: 
P2를 스케줄러가 선택함 → 디스패처가 CPU에 할당 → P2 실행 시작

 

 

사진 출처 - 유튜브 쉬운코드

 

---

선점(Preemptive) vs 비선점(Non-Preemptive)

 

 비선점 (Non-Preemptive Scheduling)

정의

• 프로세스가 자발적으로 CPU를 반납할 때만 스케줄러가 개입
• OS는 강제로 개입 X → 프로세스가 종료되거나 대기 상태로 들어갈 때까지 기다림

---

 프로세스 상태 전이 흐름

Running ──▶ Waiting      (I/O 요청 발생 → Blocked 상태)
       └──▶ Terminated   (작업 완료)
       └──▶ Ready        (자발적 yield → 매우 드문 경우)

 실제 상황 예시 (OS 내부에서)

• 프로세스 P1이 CPU 사용 중
• 사용자 입력 기다리는 순간 → 시스템 콜 발생 → Waiting 상태로 이동
• 그제서야 OS가 Ready Queue에서 다음 프로세스 선택

 특징 요약

항목	설명
개입 시점	프로세스가 자발적 상태 변경할 때
응답성	느림 (긴 작업은 끝까지 CPU 점유)
컨텍스트 스위칭	적음
데이터 안정성	높음 (중간에 끊기지 않음)
예시	전통적인 Windows 3.x, 오래된 임베디드 OS

---

 선점 (Preemptive Scheduling)

정의

• 실행 중인 프로세스를 OS가 강제로 중단하고
  → 더 높은 우선순위의 프로세스에게 CPU 양도
• 주로 타이머 인터럽트나 새로운 프로세스 도착 시 개입

---

 프로세스 상태 전이 흐름

Running ──▶ Ready  (타이머 인터럽트 or 높은 우선순위 Ready 프로세스 등장)
       └──▶ Waiting  (I/O 요청)
       └──▶ Terminated

 실제 상황 예시 (OS 내부에서)

• P1 실행 중 (우선순위 5)
• P2(우선순위 2)가 Ready Queue에 새로 도착
  → 스케줄러가 인터럽트 → 디스패처가 P1 상태 저장 후 P2로 전환

[타이머 인터럽트 발생]
→ 커널 모드 진입
→ Ready Queue 우선순위 비교
→ P2 우선순위 ↑ → P1 중단
→ P2로 컨텍스트 스위칭

---

 타이머 인터럽트 흐름 도식

[CPU 시간 소진됨] (time slice) or 더 높은 우선순위 프로세스가 Ready Queue에 도착
   ↓
[인터럽트 발생]
   ↓
[스케줄러 실행 → Ready Queue 우선순위 비교]
   ↓
[더 높은 우선순위 발견 → 디스패처가 컨텍스트 스위칭]

---

특징 요약

 

항목	설명
개입 시점	타이머 인터럽트, 우선순위 높은 프로세스 도착
응답성	빠름 (긴급한 프로세스 즉시 실행 가능)
컨텍스트 스위칭	잦음 → CPU 오버헤드 증가
데이터 일관성	깨질 수 있음 → 락, 뮤텍스 필요
예시	현대 리눅스, Windows NT 이후, Android 등

 

 

⚠️ 최종 비교

구분	비선점 (Non-Preemptive)	선점 (Preemptive)
CPU 회수 방식	자발적 반환	강제 회수
예시 상황	I/O 요청 or 종료 시	높은 우선순위 등장
응답성	느림	빠름
데이터 안정성	높음	낮음 (락 필요)
대표 키워드	신사적, 협력적	공격적, 강제적

 

 

 스케줄링 알고리즘 종류 및 예시

---

1️⃣ FCFS (First Come First Serve, 선입선출)

• 설명: 먼저 도착한 프로세스부터 처리
• 비선점형

예시:

도착 순서: P1(도착 0, 버스트 4), P2(도착 1, 버스트 3), P3(도착 2, 버스트 2)

실행 순서: P1 → P2 → P3

---

2️⃣ SJF (Shortest Job First)

• 설명: CPU 버스트(실행 시간)가 가장 짧은 프로세스를 먼저 실행
• 비선점형

예시:

P1(버스트 7), P2(버스트 3), P3(버스트 1)

실행 순서: P3 → P2 → P1

---

3️⃣ SRTF (Shortest Remaining Time First)

• 설명: SJF의 선점형 버전. 실행 중 더 짧은 프로세스가 들어오면 CPU 뺏김
• 선점형

예시:

P1(도착 0, 버스트 8),  
P2(도착 1, 버스트 4),  
P3(도착 2, 버스트 2)

실행 흐름:
0~1s: P1  
1~2s: P2  
2~4s: P3  
4~8s: P2  
8~16s: P1

---

4️⃣ Priority Scheduling

• 설명: 우선순위(priority)가 높은 프로세스를 먼저 실행
• 선점형/비선점형 모두 가능

예시 (숫자 작을수록 우선순위 높음):

P1(priority 3), P2(priority 1), P3(priority 2)

실행 순서: P2 → P3 → P1

---

5️⃣ Round Robin (RR)

• 설명: Time Slice를 기준으로 순차적 실행
• 선점형

예시 (Time Slice: 4):

P1(버스트 10), P2(버스트 5), P3(버스트 7)

실행 순서:
0~4: P1  
4~8: P2  
8~12: P3  
12~16: P1  
16~20: P3  
20~22: P1

---

6️⃣ Multilevel Queue (다단계 큐)

• 설명: 프로세스를 그룹으로 분류하고, 각 그룹마다 큐를 따로 관리
  • 예: 시스템 프로세스, 사용자 프로세스 등
• 정책: 각 큐마다 다른 스케줄링 적용 가능

예시:

 

시스템 큐 → RR  
사용자 큐 → FCFS

전체 흐름:
→ 시스템 큐 먼저 실행 (우선순위 높음)
→ 사용자 큐는 시스템 큐가 한가할 때만 실행

---

 마무리 요약

 

항목	설명
CPU 스케줄러	어떤 프로세스를 실행할지 선택
디스패처	선택된 프로세스를 CPU에 실제 할당
선점 방식	강제로 실행 중단 가능, 응답성 빠름
비선점 방식	자발적 종료 or 대기로 CPU 반환, 안정적
알고리즘 예	FCFS, SJF, SRTF, Priority, RR, Multilevel 등