[CS] 프로세스 스케줄링(Process Scheduling) 기법

운영체제(OS)는 CPU를 여러 프로세스가 공유해서 효율적으로 사용할 수 있도록 관리합니다.
이때 어떤 프로세스에 CPU를 언제, 얼마나 할당할지 결정하는 것을
👉 “프로세스 스케줄링(Process Scheduling)” 이라고 합니다.

---

🧩 1. 스케줄링이란?

CPU 자원을 여러 프로세스에게 효율적으로 배분하는 과정

CPU는 한 번에 하나의 프로세스만 실행할 수 있기 때문에,
운영체제는 준비(Ready) 상태의 프로세스 중 하나를 선택해 CPU를 할당해야 합니다.

스케줄링의 목적

• CPU 이용률 최대화: CPU가 유휴 상태 없이 항상 실행되도록
• 처리량 증가: 단위 시간당 완료되는 프로세스 수 최대화
• 응답 시간 최소화: 요청부터 응답까지의 시간 단축
• 대기 시간 최소화: Ready Queue에서 대기하는 시간 감소
• 반환 시간 최소화: 프로세스 제출부터 완료까지의 총 시간 단축
• 공정성: 모든 프로세스가 공평하게 CPU를 할당받도록

---

🧠 2. 프로세스 상태 전이 (기본 흐름)

 

           [제출(Submit)]
              |
              ↓     Spooling
           [접수] ----------→[디스크]
          [(Hold)]←----------[(disk)]
              |
              | Job 스케줄러
              ↓              입·출력 종료 (Wake Up)
           [준비(Ready)] ←------------------- [대기(Wait, Block)]
              | ↑                               ↑
              | | 선점, 시간 초과                | 
    Dispatch  | |                               |
              ↓ |                               |
           [실행(Run)] -----------------------→ ┙
              |                입·출력 발생
              | 
              ↓ 
          [종료(Terminated, Exit)]

• Ready: CPU 할당 대기
• Running: CPU에서 실행 중
• Waiting (Blocked): I/O 대기 상태
• Terminated: 실행 종료

 

 

상태 전이 설명

1. New → Ready: 프로세스 생성 완료, 메모리 적재 (admitted)
2. Ready → Running: 스케줄러가 CPU 할당 (dispatch)
3. Running → Ready: 할당 시간 만료 또는 우선순위 높은 프로세스 등장 (interrupt/preemption)
4. Running → Waiting: I/O 요청이나 이벤트 대기 (I/O or event wait)
5. Waiting → Ready: I/O 완료 또는 이벤트 발생 (I/O or event completion)
6. Running → Terminated: 프로세스 실행 완료 (exit)

---

🧭 3. 스케줄링의 종류

구분	설명	예시
비선점형 (Non-preemptive)	한 프로세스가 CPU를 점유하면, 스스로 CPU를 반납할 때까지 다른 프로세스가 기다림	FCFS, SJF, HRN
선점형 (Preemptive)	운영체제가 강제로 CPU를 회수하고 다른 프로세스에 할당 가능	RR, SRTF, MLQ, MLFQ

---

⏱️ 4. 주요 스케줄링 알고리즘 정리

* 비선점형

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

도착 순서대로 처리

구분	설명
방식	Ready 큐에 먼저 도착한 순서대로 CPU 할당
장점	구현 간단, 공정성 높음
단점	평균 대기시간 ↑, Convoy Effect 발생 (짧은 작업이 긴 작업 뒤에 묶임)

📘 예시

프로세스  도착시간  실행시간
P1         0        24
P2         1         3
P3         2         3

실행순서: P1 → P2 → P3
평균 대기시간: (0 + 23 + 25) / 3 = 16ms

2️⃣ SJF (Shortest Job First)

실행 시간이 가장 짧은 작업 우선

구분	설명
방식	CPU Burst(실행 시간)가 짧은 프로세스 우선
장점	평균 대기시간 최소화
단점	실행 시간 예측 어려움, Starvation(기아) 가능

📘 예시

프로세스  도착시간  실행시간
P1         0         6
P2         2         8
P3         4         7
P4         6         3

실행순서: P1 → P4 → P3 → P2
평균 대기시간: (0 + 7 + 6 + 10) / 4 = 5.75ms

 

3️⃣HRN (Highest Response Ratio Next)

대기시간 + 실행시간의 비율을 고려하는 비선점형 기법

구분	설명
계산식	응답률 = (대기시간 + 서비스시간) / 서비스시간
특징	SJF의 단점(기아)을 개선
장점	오래 기다린 프로세스의 우선순위 점점 상승
단점	실행시간을 미리 알아야함

📘 예시

현재 시각: 10ms
프로세스  도착시간  실행시간  대기시간  Response Ratio
P1         0         3         10       (10+3)/3 = 4.33
P2         2         6          8       (8+6)/6  = 2.33
P3         4         4          6       (6+4)/4  = 2.50
P4         6         5          4       (4+5)/5  = 1.80
P5         8         2          2       (2+2)/2  = 2.00

실행순서: P1(RR=4.33) → P3(RR=2.50) → P5(RR=2.00) → P2(RR=2.33) → P4

시각 0 : P1 도착
시각 2 : P2 도착
시각 4 : P3 도착
시각 6 : P4 도착
시각 8 : P5 도착
시각 10: P1 실행 시작 (완료: 13)
시각 13: P3 실행 시작 (완료: 17)
시각 17: P5 실행 시작 (완료: 19)
시각 19: P2 실행 시작 (완료: 25)
시각 25: P4 실행 시작 (완료: 30)

---

* 선점형

1️⃣ SRTF (Shortest Remaining Time First)

SJF의 선점형 버전

구분	설명
방식	남은 실행 시간이 가장 짧은 프로세스 우선
장점	CPU 활용 효율 ↑
단점	Context Switching 과다, 기아 현상 가능

📘 예시

P1(10ms) 실행 중 P2(3ms) 도착 → P2로 선점 전환

---

2️⃣ RR (Round Robin)

타임퀀텀(Time Quantum) 단위로 CPU 순환 할당

구분설명

방식	각 프로세스에 일정 시간(q) 동안 CPU 할당 후 다음 프로세스로 전환
장점	응답성 우수, 시분할 시스템에 적합
단점	q 값이 너무 작으면 Context Switching 과다, 너무 크면 FCFS처럼 됨

📘 예시

타임퀀텀 q = 4ms
Ready Queue: P1(6ms), P2(4ms), P3(7ms)
실행 순서: P1(4) → P2(4) → P3(4) → P1(2) → P3(3)

---

3️⃣Multi-Level Queue (MLQ)

프로세스 성격별로 여러 큐로 나눠서 관리

구분설명

구조	Ready Queue를 여러 개로 분할 (예: 시스템, 대화형, 배치 작업)
특징	각 큐마다 다른 스케줄링 알고리즘 사용
단점	큐 간 이동 불가 → 유연성 낮음

---

4️⃣ Multi-Level Feedback Queue (MLFQ)

프로세스의 행동에 따라 큐 이동이 가능한 동적 방식

구분설명

특징	처음엔 높은 우선순위 큐에서 시작, 오래 실행될수록 낮은 우선순위 큐로 이동
장점	짧은 작업은 빠르게 처리, 긴 작업도 언젠가 실행됨
단점	구현 복잡도 ↑

📘 예시

 

Q1 (우선순위 높음, RR 4ms)
Q2 (중간, RR 8ms)
Q3 (낮음, FCFS)
→ CPU 점유 시간 늘어날수록 아래 큐로 이동

 

---

⚙️ 5. 각 알고리즘 비교 요약표

알고리즘	선점	기준	장점	단점
FCFS	X	도착 순서	단순, 공정	긴 작업 대기시간
HRN	X	응답률	공정성 ↑	계산 복잡
SJF	X	실행시간	평균 대기 ↓	기아 현상
SRTF	O	남은 실행시간	효율적	잦은 문맥 전환
Priority	O/X	우선순위	중요 작업 우선	기아 가능
RR	O	타임퀀텀	응답성 ↑	q 조절 필요
MLQ	O	큐 분류	단순 구조 분리	큐 이동 불가
MLFQ	O	동적 우선순위	실시간 + 공정성	구현 복잡

---

✍️ 마무리

스케줄링 알고리즘은
운영체제가 CPU를 얼마나 효율적으로 분배하느냐의 핵심 로직입니다.

💡 정리하자면

• 비선점형: FCFS, SJF, HRN
• 선점형: SRTF, RR, MLQ, MLFQ