[운영체제] ch05. CPU Scheduling

📄 CPU-burst Time의 분포

전체 개요

CPU burst time은 프로세스가 CPU를 연속적으로 사용하는 시간을 의미함.
이 분포는 대부분의 프로세스가 짧은 burst time을 갖고, 일부만이 매우 긴 burst time을 갖는다는 특징이 있음.

---

그래프 해석

• x축: CPU 사용 시간 (burst duration, 단위: milliseconds)
• y축: 해당 시간의 사용 빈도 (frequency)

● I/O bound job

• 매우 짧은 CPU 사용 후 I/O 요청
• 짧은 burst time을 자주 반복 (그래프 왼쪽의 뾰족한 고봉)
• ✍️ 필기: “흔한 유형 (인터랙티브), 즉시 응답 요망”

● CPU bound job

• 연산량이 많아 한 번에 CPU를 오래 점유
• 긴 burst time (그래프 오른쪽의 낮고 긴 tail)
• ✍️ 필기: “신경망 학습 등 긴 처리 시간 필요”

---

✅ 암기 포인트

• 대부분의 프로세스는 burst time이 짧다 (I/O bound)
• 일부만이 burst time이 길다 (CPU bound)
• 그래프는 hyperexponential 분포를 따른다
• 스케줄러는 짧은 burst에 빠르게 반응하고, 긴 burst도 공정하게 배분해야 한다
• Interactive job에 빠른 response 제공이 핵심
• CPU와 I/O 자원을 효율적으로 분배해야 한다

---

✍️ 하단 필기 요약

• "여러 종류의 job이 섞여 있기 때문에 스케줄링이 반드시 필요함"
• "→ Interactive job은 응답속도 중요"
• "→ CPU bound는 자원 점유시간 길지만 효율 고려 필요"

---

이 슬라이드는 CPU 스케줄링 알고리즘의 동기부여 슬라이드야.
왜 SJF 같은 알고리즘이 burst time 예측 기반으로 움직이는지, 왜 preemption이 중요한지 이해하는 기반이 돼!
 
 
 
 

📄 CPU and I/O Bursts in Program Execution

전체 요약

프로세스는 CPU 작업(CPU burst)과 입출력 작업(I/O burst)을 번갈아 수행하며 실행된다.
이 흐름을 운영체제가 스케줄링을 통해 관리해야 함.

---

그림 구조 해설

• CPU burst: 계산, 메모리 연산, 변수 조작 등 → CPU가 처리
• I/O burst: 디스크, 파일 등 입출력 → I/O 장치가 처리

순서 예시

→ CPU burst

→ I/O burst (blocked)

→ CPU burst

→ I/O burst

→ CPU burst

→ I/O burst ...

 

• 각 I/O burst 동안에는 CPU는 다른 프로세스를 실행 가능
• ✍️ 필기: “process는 CPU burst ↔ I/O burst 왔다갔다 반복하며 실행된다”

---

상태 전이 흐름

1. running → blocked: I/O 요청 시
2. blocked → ready: I/O 완료 시 (인터럽트 발생)
3. ready → running: CPU 할당되면 다시 실행

• ✍️ 필기:
  • “running → blocked (I/O 요청 시)”
  • “blocked → ready → running (I/O 완료 후 스케줄러 할당 시)”

---

✅ 암기 포인트

• 모든 프로세스는 CPU burst와 I/O burst가 반복되는 구조로 실행된다
• CPU burst는 연산/제어, I/O burst는 장치 대기/전송
• I/O burst 동안 프로세스는 blocked 상태로 빠지고, CPU는 다른 프로세스를 실행
• 이 흐름을 운영체제가 효율적으로 스케줄링해야 시스템 자원을 낭비하지 않음
• I/O는 속도가 느리기 때문에 적절한 CPU-I/O 병행 실행이 중요

---

✍️ 필기 요약 정리

• “hard disk 접근 매우 느림”
• “I/O는 blocking operation → 바쁜 I/O 작업 중에는 CPU 못 씀”
• “blocked → ready 전이 후, 다시 running 진입”
• “전체 수행 시간 중 I/O가 많으면 효율 떨어짐 → 스케줄링 필요”

---

이 구조를 이해하면 스케줄링 알고리즘의 설계 이유,
예: Multilevel Feedback Queue가 왜 I/O bound에 유리한지까지 자연스럽게 이어질 수 있어!
 
 

📄 FCFS (First-Come First-Served)

전체 요약

FCFS는 먼저 도착한 프로세스부터 실행하는 스케줄링 방식으로, 도착 순서가 실행 순서를 결정한다.

---

예제 구성

ProcessBurst Time

P₁	24
P₂	3
P₃	3

• 모든 프로세스가 동시에 도착했다고 가정

---

실행 순서 및 Gantt Chart

• 도착 순서대로: P₁ → P₂ → P₃
• 실행 흐름 (시간 단위):

 

|-------P₁-------|--P₂--|--P₃--| 0 24 27 30

---

Waiting Time (대기 시간)

• P₁: 0 (도착하자마자 실행)
• P₂: 24 (P₁ 끝날 때까지 기다림)
• P₃: 27 (P₁ + P₂ 끝날 때까지 기다림)

→ 평균 대기 시간:
0+24+273=17\frac{0 + 24 + 27}{3} = \boxed{17}30+24+27=17

---

✅ 암기 포인트

• FCFS는 프로세스를 도착 순서대로 실행함
• 한 번 실행이 시작되면 중간에 중단되지 않음 (Non-preemptive)
• burst time이 긴 프로세스가 먼저 오면 → 전체 평균 대기 시간 증가 (convoy effect)
• 간단하지만 비효율적인 경우가 많다

---

✍️ 필기 요약

• “ready queue 순서: P₁ → P₂ → P₃”
• “P₂, P₃는 실행 못 하고 기다림” → CPU 낭비는 없지만, 대기 시간 큼
• “예정된 실행 시간”이라는 표현으로 burst time을 이해함

---

이 슬라이드는 FCFS의 단순성과 단점(긴 작업이 앞에 있으면 전체 지연)을 함께 보여주는 대표 예제야.
이후 SJF, RR, Priority 스케줄링과 비교할 때 기본이 되니 꼭 기억해둬야 해!
 
 
 

📄 Example of Non-Preemptive SJF 

이 슬라이드는 SJF (Shortest Job First) - Non-Preemptive 방식의 스케줄링 예제를 보여주고 있어.
**도착 시간(Arrival Time)**과 **실행 시간(Burst Time)**이 주어졌을 때,
Non-Preemptive SJF가 어떻게 프로세스를 실행하는지, **간트 차트(Gantt Chart)**와 평균 대기 시간까지 계산해놓은 아주 대표적인 예제야.
그림에 포함된 메모까지 반영해서 전체적으로 정리해줄게!

---

📄 Example of Non-Preemptive SJF (Shortest Job First)

---

프로세스 정보

ProcessArrival TimeBurst Time

P₁	0.0	7
P₂	2.0	4
P₃	4.0	1
P₄	5.0	4

---

스케줄링 규칙 (Non-Preemptive SJF)

Non-Preemptive SJF는 한 프로세스가 CPU를 점유하면 끝날 때까지 다른 프로세스로 바꾸지 않음.
단, 다음에 누구를 실행할지는 도착한 프로세스 중에서 burst time이 가장 짧은 것을 고름.

---

실행 순서 분석

1. 시간 0: P₁만 도착했으므로 → P₁ 실행 시작
2. 시간 7: P₁ 종료, 도착한 P₂, P₃, P₄ 중에서 burst time 가장 짧은 P₃ 선택
3. 시간 8: P₃ 종료 → 남은 P₂(4), P₄(4) 중 도착 빠른 P₂ 먼저
4. 시간 12: P₂ 종료 → P₄ 실행
5. 시간 16: P₄ 종료

➡️ Gantt Chart:

less

코드 복사

|---P₁---|P₃|----P₂----|----P₄----| 0 7 8 12 16

---

대기 시간(Waiting Time) 계산

• P₁: 0 (도착하자마자 실행)
• P₂: 8 - 2 = 6
• P₃: 7 - 4 = 3
• P₄: 12 - 5 = 7

→ 평균 대기 시간:
0+6+3+74=4\frac{0 + 6 + 3 + 7}{4} = \boxed{4}40+6+3+7=4

---

✅ 암기 포인트 요약

• SJF(Non-Preemptive)는 도착한 프로세스 중에서 burst time이 가장 짧은 것부터 선택
• 한 번 실행되면 종료까지 CPU 점유 (Preemption 없음)
• 대기 시간은 시작 시간 - 도착 시간
• 평균 대기 시간 계산은 모든 프로세스의 대기 시간의 평균

---

✍️ 그림 필기 내용 요약

• “0초에는 P₁만 도착 → 무조건 실행됨”
• “7초까지는 P₁이 점유하고 있어서 아무도 못 실행됨”
• “대기 시간 계산 순서 적혀 있음 (0, 6, 3, 7)”

---

이 슬라이드는 SJF 개념을 시각적으로 정리할 수 있는 대표 예제니까 시험 전에 꼭 다시 한 번 보길 추천해!
 

 
이 슬라이드는 Preemptive SJF (Shortest Job First), 즉 SRTF (Shortest Remaining Time First) 알고리즘을 보여주는 예제야.
프로세스가 실행 중이어도, 더 짧은 작업이 도착하면 선점(preemption)된다는 특징이 핵심이고,
이 알고리즘은 평균 대기 시간을 최소화하는 이론상 최적 알고리즘이야.
이번에도 슬라이드의 표, Gantt 차트, 필기까지 전부 반영해서 정리해줄게!

---

📄 Example of Preemptive SJF (SRTF)

---

프로세스 정보

ProcessArrival TimeBurst Time

P₁	0.0	7
P₂	2.0	4
P₃	4.0	1
P₄	5.0	4

---

실행 흐름 분석 (Preemption 있음)

1. 0~2: P₁ 시작 (남은 시간 5)
2. 2~4: P₂ 도착 → P₂(4) vs P₁(5) → P₂ 실행
3. 4~5: P₃ 도착 → P₃(1) vs P₂(2) → P₃ 실행 (P₂ 선점됨)
4. 5~7: P₃ 종료 → P₂(2) 복귀
5. 7~11: P₄ 도착 → P₂ 종료 후 P₄ 실행
6. 11~16: 마지막으로 P₁ 재개 → 종료

---

Gantt Chart

less

코드 복사

|--P₁--|--P₂--|P₃|--P₂--|----P₄----|-----P₁-----| 0 2 4 5 7 11 16

---

Waiting Time 계산

ProcessStart - ArrivalTotal Wait

P₁	(재개 시점 11 - 도착 0 - 실제 실행 2초) = 9
P₂	(재개까지 대기: 5~7) = 1
P₃	바로 실행 → 0
P₄	7 - 5 = 2

평균 대기 시간=9+1+0+24=3\text{평균 대기 시간} = \frac{9 + 1 + 0 + 2}{4} = \boxed{3}평균 대기 시간=49+1+0+2=3

---

✅ 암기 포인트

• SRTF (Preemptive SJF)는 남은 시간 기준으로 가장 짧은 작업을 우선 실행
• 기존에 실행 중인 프로세스보다 더 짧은 job이 도착하면 선점된다
• 평균 대기 시간을 최소화할 수 있는 알고리즘 (Optimal)
• 단점: 예측 어려움, Starvation 발생 가능 (긴 job이 계속 밀림)

---

✍️ 필기 요약

• "P₃가 도착했을 때 P₂보다 burst가 더 짧아서 선점됨 (1 vs 2)"
• "P₄ 도착했지만 P₂가 더 짧아서 먼저 실행"
• "Non-preemptive보다 평균 대기 시간이 감소함 → Optimal"

---

이 슬라이드는 스케줄링 알고리즘 중 이론적으로 가장 좋은 성능을 보이지만,
실제로는 burst time 예측이 어려워서 그대로 구현되긴 힘들어.
 
 
 
 

📄 Example: RR (Round Robin) with Time Quantum = 20

 

 
이 슬라이드는 RR (Round Robin) 스케줄링 알고리즘의 예제를 보여줘.
Time Quantum이 20일 때, 각 프로세스가 어떻게 CPU를 나눠서 사용하는지 시각적으로 설명하고 있고,
짧은 작업 응답 시간(response time)은 좋아지지만, 평균 완료 시간은 길어질 수 있다는 점이 핵심이야.
 

프로세스 정보

ProcessBurst Time

P₁	53
P₂	17
P₃	68
P₄	24

• Time Quantum = 20
• 선입선출(FCFS) 방식으로 큐에서 돌아가며 실행

---

Gantt Chart 분석

less

코드 복사

| P₁ | P₂ | P₃ | P₄ | P₁ | P₃ | P₄ | P₁ | P₃ | P₃ | 0 20 37 57 77 97 117 121 134 154 162

각 프로세스 실행 분할:

• P₁: 20 + 20 + 13 = 53 (총 3번)
• P₂: 17 (1번에 끝)
• P₃: 20 + 20 + 20 + 8 = 68 (총 4번)
• P₄: 20 + 4 = 24 (총 2번)

---

✅ 핵심 개념 요약

• RR은 고정된 시간(Time Quantum)마다 CPU를 교대로 할당
• 짧은 작업이 먼저 끝나지 않더라도 자주 CPU를 받으므로 응답 시간(response time)은 좋음
• 작업의 길이와 관계없이 공정하게 실행되지만,
  평균 turnaround time은 SJF보다 길어질 수 있음
• short job과 long job이 섞여 있을 때 특히 효과적

---

✍️ 슬라이드 필기 요약

• "응답 시간이 짧아짐 → time sharing 환경에 적합"
• "short job, long job 섞여 있을 때 효과적"
• "단, 동등 job 아니면 오히려 비효율 가능"
• "CPU first 받는 시간이 빨라짐 = 빠른 반응"

---

RR 알고리즘의 특성 요약

장점단점

✅ 응답 시간(response time) 좋음	❌ 평균 완료 시간 증가 가능
✅ starvation 없음	❌ Context Switching 비용 있음
✅ 공정한 할당 (Fairness)	❌ 너무 작은 Quantum은 오버헤드

---

이 예제는 시분할 시스템에서 왜 RR이 쓰이는지를 명확히 보여줘.
특히 사용자 인터페이스 기반 시스템에서는 SJF보다 훨씬 자연스럽고 반응성이 좋아!
 
 
 

📄 Turnaround Time Varies With Time Quantum

전체 맥락

RR (Round Robin) 스케줄링에서 time quantum의 크기는
시스템 반응성과 **평균 turnaround time(작업 종료까지 걸린 전체 시간)**에 큰 영향을 줌.

---

그래프 구조 해석

• x축: Time Quantum (1~7)
• y축: Average Turnaround Time (9.0 ~ 12.5)

관찰 포인트:

• Time Quantum이 너무 작으면: context switching이 자주 발생해 오버헤드 증가 → turnaround time 증가
• Time Quantum이 적당하면: short job 빠르게 종료 + long job도 분산 실행 → turnaround time 최소화
• Time Quantum이 너무 크면: FCFS처럼 작동하게 되며 short job 지연 → turnaround time 증가

✍️ 필기:

• "time quantum 변화에 따라 turnaround time이 어떻게 변하는지 통찰력 주는 그래프"
• "할당 시간 커질수록 FCFS처럼 동작하게 됨"

---

오른쪽 프로세스 정보

ProcessBurst Time

P₁	6
P₂	3
P₃	1
P₄	7

→ short job(P₃), medium(P₁, P₂), long job(P₄)이 섞여 있음
→ time quantum 크기에 따라 큰 차이 발생 가능

---

✅ 암기 포인트

• time quantum이 너무 작으면 → context switch 비용 ↑ → 비효율
• 너무 크면 → short job이 늦게 끝남 (FCFS와 유사)
• 적절한 값 설정 필요 → short job은 빠르게, long job은 공정하게

---

전략적 요약

Time Quantum시스템 반응성Turnaround Time특징

작을수록	높음	증가 가능	context switch 과다, short job 빠름
적절할 때	높음 + 효율적	최소화	가장 이상적 성능
클수록	낮음	증가 가능	FCFS처럼 동작, short job 지연

---

✍️ 핵심 정리 멘트

“RR의 핵심은 time quantum이다.
너무 작으면 시스템 과부하, 너무 크면 FCFS화.
적절한 중간값을 찾는 것이 성능 최적화의 핵심이다.”

---

이 슬라이드는 운영체제 설계에서 타임 슬라이스 조절이 얼마나 중요한가를 보여주는 핵심 통계 그래프야.
실험문제, 서술형 둘 다 출제 가능성이 높으니 꼭 기억해!
 

📄 Multilevel Feedback Queue (MLFQ)

📄 Multilevel Feedback Queue (MLFQ)

---

🔧 핵심 개념

MLFQ는 프로세스의 실행 시간과 행동 패턴에 따라 우선순위를 동적으로 조절하는 스케줄링 기법이다.
짧은 작업은 빠르게, 긴 작업은 점차 낮은 우선순위로 밀리게 하여 공정성과 반응성을 동시에 잡는다.

---

🔢 큐 구조

1. Queue 1 (quantum = 8)
   • 초기 진입
   • 8초 이내 종료되면 여기서 완전히 끝
   • 시간 초과 시 → Queue 2로 이동
2. Queue 2 (quantum = 16)
   • Queue 1에서 밀려온 프로세스
   • 16초 안에 종료되면 여기서 완료
   • 또 시간 초과 시 → FCFS 큐로 이동
3. Queue 3 (FCFS)
   • Time quantum 없이 순서대로 끝날 때까지 실행

---

🔄 동작 예시 (슬라이드 필기 순서 기준)

• ①~⑤: 처음엔 모두 Queue 1에 들어감
  • 각각 8초씩 실행됨
  • 예: ⑤번은 6초 만에 끝나서 Queue 1에서 종료됨 (✅)
• 남은 프로세스(④,③,②,①)는 시간이 부족해 → Queue 2로 이동
  • 각자 16초 배정됨
• Queue 2에서도 못 끝난 프로세스(예: ③)는 → Queue 3 (FCFS)로 이동

---

✍️ 슬라이드 필기 요약

• “24초 작업이 있었는데… Queue 1에서 8초, Queue 2에서 16초 → 총 24초 후 종료”
• “남은 양이 많으면 FCFS로 내려간다”
• “선점형 큐 → 짧은 job에 유리”
• “두 번째 큐는 preemptive 아님” (context switch 없음)
• “짧은 job은 Queue 1에서 바로 끝냄 → 반응성 좋음”

---

✅ 암기 포인트

• 다단계 큐로 우선순위 구성
• 높은 우선순위 큐는 짧은 quantum (선점형)
  → 반응성↑
• 긴 job은 점차 낮은 우선순위로 밀려 FCFS로
• 짧은 job은 높은 우선순위에서 빠르게 끝남
• 실제 운영체제에서 가장 유연하고 현실적인 방식

---

요약 표

QueueQuantum선점 여부용도

Q1	8	O	짧은 작업 빠르게 처리, 기본 진입
Q2	16	X	중간 작업 처리
Q3	없음	X (FCFS)	긴 작업 처리, CPU bound용

---

이 슬라이드는 실제 OS에서 사용하는 동적 스케줄링 방식의 핵심 모델
 
 
 

📄 Multiple-Processor Scheduling

🧠 핵심 개념

여러 개의 **CPU 또는 코어(Core)**가 있는 시스템에서,
각 작업(Job, 프로세스)를 어떤 방식으로 어떤 CPU에 배분할지를 결정하는 스케줄링 기법

---

🏗️ 시스템 유형 구분

1. Homogeneous Processor

• 동일한 CPU 구조
• 하나의 **공통 큐(shared ready queue)**를 사용
• 어떤 CPU든 어떤 job이나 실행 가능

→ Load Sharing 가능

---

🔄 스케줄링 방식 구분

✅ Asymmetric Multiprocessing (AMP)

• 한 CPU만 스케줄링을 담당 (master)
• 나머지 CPU는 단순히 작업만 실행
• 장점: 설계 간단
• 단점: 스케줄링 병목 가능

→ ✍ 필기: “한놈이 스케줄 다 담당함 → 병목될 수 있음”

---

✅ Symmetric Multiprocessing (SMP)

• 모든 CPU가 스케줄링 기능 가짐
• 각각 스스로 작업을 큐에서 가져옴
• 장점: 병렬성 극대화
• 단점: 경쟁 조건, 동기화 오버헤드

→ ✍ 필기: “모두 알아서 큐에서 꺼냄 → lock 경합, 성능 저하 가능”

---

📈 Load Sharing 전략

여러 CPU가 ready queue를 공유하면서,
각자가 균형 있게 작업을 분담하는 구조

• 작업이 몰리는 현상을 완화
• SMP와 함께 사용되는 대표 전략

---

🧠 필기 포함 요약

• “Core = 처리 단위”
• “Multicore는 하나의 CPU 안에 여러 코어”
• “Multiprocessor는 물리적으로 CPU가 여러 개”
• 아래 도식에서 MultiCPU vs MultiCore를 구분해 그림

---

✅ 암기 포인트

• AMP: 한 CPU가 전체 스케줄 관리 (병목 가능)
• SMP: 모든 CPU가 독립적으로 작업 가져감 (성능 좋지만 경쟁 발생 가능)
• Load Sharing: queue 공유 기반의 작업 분산
• Homogeneous vs Heterogeneous도 구분 필요 (이 슬라이드엔 언급 X)

---

구조 요약표

구분스케줄링 담당구조장점단점

AMP (비대칭)	1개 CPU	중앙집중식	설계 간단	병목, 유연성 낮음
SMP (대칭)	모든 CPU	분산식	병렬성/확장성 좋음	동기화 오버헤드 존재
Load Sharing	공유 큐 기반	균등 분산	유휴 CPU 활용, 부하 균형	구현 복잡도 존재

---

이 슬라이드는 다중 프로세서 환경에서 스케줄링 정책의 구조와 장단점을 비교하는 핵심 슬라이드야.
SMP와 AMP는 시험에서 자주 비교