[OS] CPU 프로세스 스케줄링(CPU Process Scheduling)

1. CPU 스케줄링

1-1. CPU 스케줄러

Ready 상태의 프로세스 중에서 CPU에 어떤 프로세스를 할당할 것인지 결정하는 프로그램

---

1-2. 프로세스 스케줄링

💡 프로세스 스케줄링(Process Scheduling)

 운영체제(OS)에서 프로세스가 CPU 및 기타 시스템 자원을 효율적으로 사용할 수 있도록 할당하는 작업을 말한다. 다중 프로세스 환경에서 CPU 사용을 최적화하고 시스템 성능을 극대화하는 데 핵심 역할을 한다.

---

1-3. 선점 VS 비선점 스케줄링

✅ 선점(Preemptive) 스케줄링

▶ 정의:
  - 현재 실행 중인 프로세스를 스케줄러가 강제로 중단하고, 다른 프로세스에 CPU를 할당하는 방식.
▶ 특징:
  - 우선순위가 높은 프로세스가 도착하면 현재 작업 중인 프로세스를 중단.
  - 실시간 시스템이나 응답 시간이 중요한 환경에서 사용.
▶ 예시 알고리즘:
  - Round Robin (RR)
  - Priority Scheduling (Preemptive)
  - Shortest Remaining Time First (SRTF)
▶ 장점:
  - 높은 응답 속도.
  - 우선순위가 높은 작업을 빠르게 처리 가능
▶ 단점:
  - 문맥 전환(Context Switching)이 빈번해져 오버헤드 발생.

✅ 비선점(Non-preemptive) 스케줄링

▶ 정의:
  - 현재 실행 중인 프로세스가 스스로 CPU를 반납(종료 또는 대기 상태로 전환)할 때까지 CPU를 유지하는 방식.
▶ 특징:
  - 현재 프로세스가 종료되기 전까지 다른 프로세스가 CPU를 사용할 수 없음.
  - 단순하고 구현이 쉬움.
▶ 예시 알고리즘:
  - First Come First Served (FCFS)
  - Shortest Job First (SJF, Non-preemptive)
  - Priority Scheduling (Non-preemptive)
▶ 장점:
  - 문맥 전환이 적어 오버헤드가 낮음.
  - 구현이 간단함.
▶ 단점:
  - 우선순위가 높은 프로세스가 오래 대기할 가능성.
  - 대화형 시스템에 적합하지 않음.

✅ 주요 차이점 비교

구분	선점 스케줄링	비선점 스케줄링
CPU 점유방식	강제로 중단하고 CPU를 다른 프로세스에 할당	프로세스가 스스로 CPU를 반납할 때까지 유지
문맥 전환	빈번히 발생하여 오버헤드가 큼	거의 발생하지 않아 오버헤드가 적음
응답 시간	우선순위 높은 프로세스를 빠르게 처리 가능	우선순위에 상관없이 대기 시간 증가 가능
복잡성	상대적으로 구현이 복잡함	구현이 단순함
사용 사례	실시간 시스템, 대화형 시스템	일괄처리 시스템, 단순 환경

---

1.4 스케줄링 결정 시점

상태	예시	방식
Running → Waiting	◾ I/O 요청 ◾ wait() 요청을 통한 자식 프로세스 종료	비선점
Running → Ready	◾Interrupt 발생	선점 or 비선점
Waiting → Ready	◾ I/O 완료	선점 or 비선점
Terminate	◾ 부모 프로세스 종료	비선점

---

1-5. Dispatcher 와 문맥 교환(Context Switch)

✅ 용어 뜻

▶ Dispatcher: CPU 스케줄러의 결정을 실행으로 옮기는 모듈.
▶ 문맥 교환(Context Switch): 프로세스 전환을 위해 상태를 저장/복원하는 작업.
▶ 관계: Dispatcher는 문맥 교환을 통해 프로세스 전환을 완료한다.
  - Dispatcher는 문맥 교환(Context Switch)을 구체적으로 실행하는 역할을 담당.
  - Context Switch는 Dispatcher 작업의 핵심으로, 프로세스를 교체하는 과정에서 반드시 수행됨.

✅ Dispatcher

▶ 정의:
  - 운영체제의 모듈로, CPU의 제어권을 CPU 스케줄러에 의해 선택된 프로세스에게 넘겨주는 모듈
▶ 주요 기능:
  - 한 프로세스에서 다른 프로세스로 문맥 교환(Context Switch)을 수행하는 모듈
  - CPU를 준비 상태(Ready Queue)에 있는 프로세스로 전환.
  - 커널 모드(Kernel Mode)에서 사용자 모드(User Mode)로 전환.
 
💡 CPU Mode

유저 모드(User Mode)
- 응용 프로그램이 CPU를 사용할 때 수행되는 모드
- 어플리케이션 프로그램이 수행되는 모드

커널 모드(Kernel Mode)
- OS가 CPU를 사용할 때 수행되는 모드
- 프로그램이 수행되다가 인터럽트 걸려서 운영체제가 호출돼 수행되는 모드

 

✅ 문맥 교환 (Context Switch)

https://medium.com/@ian-white/%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EC%8A%A4%EC%BC%80%EC%A4%84%EB%A7%81-250a5f59b9ff

▶ 정의:
  - 한 프로세스에서 다른 프로세스로 CPU 실행을 전환하기 위해, 이전 프로세스의 상태(문맥)를 저장하고 새 프로세스의 상태를 적재하는 작업.
▶ 작동 과정:
  - 현재 실행 중인 프로세스의 상태를 PCB(Process Control Block)에 저장.
  - 새로 실행할 프로세스의 상태를 PCB에서 복원.
  - CPU의 제어권을 새 프로세스에 전달.
▶ 문맥에 포함되는 내용:
  - CPU 레지스터 값, 프로그램 카운터, 메모리 관리 정보, 프로세스 상태

---

1-6. 스케줄링 알고리즘의 선택 기준

어떤 알고리즘의 효율성 평가 기준은 다음과 같다.

---

1. CPU 사용률 : 전체 시스템의 동작 시간 중 CPU가 사용된 시간을 측정하는 방법이다. 100%이면 CPU를 효율적으로 사용했다는 것이므로 좋은 의미이다.
2.  처리량 : 단위 시간 당 작업량으로 클수록 좋다.
3. 대기 시간 : 작업을 요청한 프로세스가 시작하기 전까지 대기하는 시간이다. 짧을 수록 좋다.
4. 응답 시간 : 프로세스 시작 후 출력 또는 반응이 나올 때까지 걸리는 시간으로 짧을 수록 좋다.
5. 반환 시간 : 프로세스가 종료되어 자원을 모두 반환하는 데까지 걸리는 시간이다. 반환 시간은 대기 시간과 실행 시간을 더한 값이다.

지표	정의	목표
CPU 사용률	전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율	최대화
처리량	요청 후 응답이 오기 시작할 때까지의 시간	최대화
반환시간 ★	프로세스가 시작해서 끝날 때까지 걸리는 시간	최소화
대기시간 ★ ★	프로세스가 준비 큐에서 대기한 시간의 총합	최소화
응답시간 ★	요청 후 응답이 오기 시작할 때까지의 시간	최소화

---

https://velog.io/@chappi/

여기서 ⭐대기 시간⭐이 매우 중요하다. 보통 스케줄링 성능을 비교할 때 주로 평균 대기 시간을 본다. 평균 대기 시간은 모든 프로세스의 대기 시간을 합한 뒤 프로세스의 수로 나눈 값이다.

 
[위의 예시에서 평균 대기 시간]

(p1 대기시간 + p2 대기시간 + p3 대기시간) / 3

**p1은 대기 시간없이 바로 실행되므로 대기 시간이 0이다.

---

2. Scheduling Algorithms (스케줄링 알고리즘)

대기 시간(Waiting Time) = 마지막 작업 시작 시간 - 도착 시간
반환 시간(Turnaround Time) = 작업 종료 시간 - 도착 시간

 

2-1. FCFS(First Come First Served) 스케줄링

https://hyuntaekhong.github.io/blog/OperatingSystem03/

• 먼저 자원 사용을 요청한 프로세스에게 자원을 할당해주는 방식
• 가장 간단한 CPU 스케줄링 알고리즘
• 비선점 스케줄링 알고리즘

 

✅ 대기 시간(Waiting Time) 계산

도착 시간은 모두 0초라고 가정한다.
 

🔎 도착 순서 : P1 → P2 → P3

• 프로세스 별 대기시간(Wating Time)
• P1 = 0, P2 = 24, P3 = 27
• 총 대기시간(Total Wating Time)
• 0 + 24 + 27 = 51
• 평균 대기시간(Average Wating Time)
• 51 ÷ 3 = 17

 

🔎 도착 순서 : P2 → P3 → P1

• 프로세스 별 대기시간(Wating Time)
• P1 = 6, P2 = 0, P3 = 3
• 총 대기시간(Total Wating Time)
• 6 + 0 + 3 = 9
• 평균 대기시간(Average Wating Time)
• 9 ÷ 3 = 3

 

✅ 반환 시간(Turnaround Time) 계산

🔎 도착 순서 : P1 → P2 → P3

• 프로세스 별 반환시간(Turnaround Time)
• P1 = 24, P2 = 27, P3 = 30
• 총 반환시간(Total Turnaround Time)
• 24 + 27 + 30 = 81
• 평균 반환시간(Average Wating Time)
• 81 ÷ 3 = 27

 

🔎 도착 순서 : P2 → P3 → P1

• 프로세스 별 반환시간(Turnaround Time)
• P1 = 30, P2 = 3, P3 = 6
• 총 반환시간(Total Turnaround Time)
• 30 + 3 + 6 = 39
• 평균 반환시간(Average Wating Time)
• 39 ÷ 3 = 13

🔥 장단점

FCFS 스케줄링의 단점

1. 프로세서를 장시간 독점하는 경우 다른 프로세스들이 오래 기다려야 함 (평균 응답시간이 길어질 수 있음)
2. 대화형 시스템에 부적합 (대화형 시스템 - 사용자와 시스템 간의 실시간 대화를 기반으로 하는 시스템. 카톡과 비슷함)
3. 우선순위가 높은 프로세스를 빨리 처리하지 못할수도 있음
 
💡 호송 효과(Convoy Effect)

소요시간이 긴 프로세스가 먼저 도달하여 시간을 잡아먹고 있는 현상

---

2-2. SJF(Shortest-Job-First) 스케줄링

Shortest-Job-First = Shortest-next-CPU-burst-first

• 최단 작업 우선 스케줄링이라고도 불리는 SJF 스케줄링은 FCFS 스케줄링의 단점인 호위 효과를 방지하는 알고리즘
• CPU 점유 시간이 가장 짧은 프로세스에 CPU를 먼저 할당하는 방식
• (단, 두 개 이상의 프로세스의 점유 시간이 같다면 FCFS 방식으로 처리) 
• 준비 큐에 있는 프로세스들 중에서 CPU 사용시간이 가장 짧은 프로세스부터 실행하는 방식 
• 비선점형 스케줄링 알고리즘

💡 기아 현상 (starvation)

언뜻 보기에는 소요시간이 짧은 프로세스부터 처리하니 효율적으로 보이지만 사용 시간이 긴 프로세스는 영원히 CPU의 할당을 못 받을 수도 있다는 문제점이 있다.

 

✅ 예시 조건

도착 시간은 모두 0초라고 가정한다.
각 프로세스 별 점유시간 ▼

💡 CPU burst time

프로세스가 실행(running) 상태에 진입한 후 대기(waiting) 또는 종료(terminated) 상태로 변하기까지의 시간을 의미한다. 비선점 시스템에서는 CPU가 프로세스의 CPU burst time동안 그 프로세스에게 독점적으로 할당된다.

 

✅ 대기 시간(Waiting Time) 계산

• 프로세스 별 대기시간(Wating Time)
• P1 = 3, P2 = 16, P3 = 9, P4 = 0
• 총 대기시간(Total Wating Time)
• 3 + 16 + 9 + 0 = 28
• 평균 대기시간(Average Wating Time)
• 28 ÷ 4 = 7

 

✅ 반환 시간(Turnaround Time) 계산

• 프로세스 별 반환시간(Turnaround Time)
• P1 = 9, P2 = 24, P3 = 16, P4 = 3
• 총 반환시간(Total Turnaround Time)
• 9 + 24 + 16 + 3 = 52
• 평균 반환시간(Average Wating Time)
• 52 ÷ 4 = 13

🔥 장단점

최소 평균 대기 시간을 위해 최적화 된 스케줄링 알고리즘이다.
소요시간이 짧은 프로세스를 긴 프로세스보다 먼저 이동
→ 긴 프로세스의 대기 시간 증가량 > 짧은 프로세스의 대기 시간 감소량 ∴ 평균 대기 시간 감소
 
장점: 일괄처리 환경에서 구현하기 쉬움
단점1: 실제로는 먼저 처리할 프로세스의 CPU 시간을 예상할 수 없음
단점2: 새로 들어온 짧은 프로세스가 긴 프로세스를 기다리거나 중요한 프로세스가 나중에 수행될 수도 있음. 따라서 시분할 운영체제나 실시간 운영체제에는 부적합하다

---

2-3. Round Robin 스케줄링

• 시분할 선점 FCFS 스케줄링
• 주로 대화형 시스템에 사용된다.
• 쉽게 말해서 스케줄러가 준비 대기열을 돌아다니며 프로세스들 사이에 우선순위를 두지 않고 순서대로 시간단위로 CPU를 할당하는 방식이다.
• 프로세스가 도착한 순서대로 프로세스를 디스패치하지만 정해진 시간 할당량에 의해 실행을 제한한다.
• 시간 할당량을 매 프로세스에 주고 할당된 시간 안에 완료하지 못한 프로세스는 준비 큐의 맨 뒤에 배치되도록 하여 CPU 독접하지 않고 공평하게 이용이 가능하다.
• 준비 대기열(Ready Queue)는 원형 큐(Circular Queue)의 형태로 구현된다.

💡 시간 단위(Time Quantum, Time Slice)

프로세스에게 할당되는 최대 CPU 시간

 

✅ 동작 방식

프로세스가 시간 단위 미만의 CPU burst를 가지는 경우

프로세스가 자율적으로 반납
스케줄러가 Ready Queue의 다음 프로세스 진행

 
프로세스가 시간 단위를 초과한 CPU burst를 가지는 경우

타이머 종료 및 OS에 interrupt 발생
문맥 교환(context switch) 실행
프로세스가 준비 대기열의 맨 뒤에 위치

 

✅ 예시 조건

도착 시간은 모두 0초로 가정한다.
시간 단위(Time Quantum)는 4ms로 가정한다.

Burst Time ▼

 
 

✅ 대기 시간(Waiting Time) 계산

• 프로세스 별 대기시간(Wating Time)
• P1 = 10 - 4 = 6
• P2 = 4
• P3 = 7
• 총 대기시간(Total Wating Time)
• 6 + 4 + 7 = 17
• 평균 대기시간(Average Wating Time)
• 17 ÷ 3 = 5.66

✅ 반환 시간(Turnaround Time) 계산

• 프로세스 별 반환시간(Turnaround Time)
• P1 = 30
• P2 = 7
• P3 = 10
• 총 반환시간(Total Turnaround Time)
• 30 + 7 + 10 = 47
• 평균 반환시간(Average Wating Time)
• 47 ÷ 3 = 15.66

🔥 장단점

평균 대기 시간이 종종 긴 스케줄링 알고리즘이다.
RR는 선점 스케줄링이다.
→ 프로세스의 Burst Time이 시간 단위를 초과하는 경우, 해당 프로세스는 준비 대기열(Ready Queue)로 돌아가게 된다.
 
장점: CPU를 독점하지 않고 공평하게 이용하여 시분할 운영체제에 적합하다.
단점1: 시간 할당량이 너무 크면 FCFS 스케줄링과 동일
단점2: 시간 할당량이 너무 작으면 너무 많은 문맥 교환 발생으로 오버헤드가 커진다.

---

2-4. SRT(Shortest Remaining Time) 스케줄링

• SJF 알고리즘의 선점(preemptive) 알고리즘 버전으로, 준비 큐에서 기다리는 프로세스 중 남은 실행시간이 가장 짧다고 예상되는 것을 먼저 디스패치한다.
• 대화형 운영체제에 유용하다.
• SRT가 SJF보다 평균 대기시간이나 평균 반환시간에서 효율적이다.
• SRT는 실행되는 각 작업의 실행시간을 추적하여 각 프로세스가 서비스를 받은 시간이 기록되어야 하며 때로는 선점을 위한 문맥 교환되 해야 하므로 SJF보다 오버헤드가 더 크다.

✅ 예시 조건

✅ 계산 결과

대기 시간 : P1 =9 , P2 = 1, P3 = 0, p4=2
반환 시간 : P1 = 16, P2 = 5, P3 = 1 , P4 = 6
반응시간 : P1 = 0, P2 = 0 , P3 = 0 , p4 = 2
평균 대기 시간 : (9+1+0+2)/4 = 3
 

🔥 장단점

장점: SJF보다 평균대기시간이나 평균반환시간에서 효율적임
단점1: 실제로는 프로세스의 CPU 시간을 예상할 수 없음
단점2: 각 프로세스의 실행시간 추적, 선점을 위한 문맥교환의 비용때문에 SJF보다 오버헤드가 큼

---

2-5. HRN(Highest Response Ratio Next) 스케줄링

• 준비 큐에서 기다리는 프로세스 중 응답비율이 가장 큰 것을 먼저 디스패치하여 실행하는 비선점 스케줄링 알고리즘
• 예상실행시간이 짧을수록, 대기시간이 길수록 응답비율이 커짐.
• SJF 스케줄링의 단점을 보완한 것으로 SJF에서는 예상 실행시간이 긴 프로세스가 먼저 들어왔더라도 이후에 실행시간이 짧은 프로세스가 계속해서 들어오면 우선순위에서 계속 밀리는 현상이 발생했다.
• 그러나 HRH 스케줄링은 실행시간이 긴 프로세스라 하더라도 대기시간이 길어지면 응답비율도 커져서 자기보다 실행시간이 짧은 프로세스가 들어오더라도 우선순위에서 밀리지 않을 수 있다

✅ 계산식

 

✅ 예시 조건 & 계산결과

프로세스 번호	P1	P2	P3
실행시간	20	4	6
대기시간	10	20	10
우선순위 계산	(10 + 20) / 20 = 1.5	(20 + 4) / 4 = 6	(10 + 6) / 6 = 2.6
우선순위	P2 → P3 → P1

 

🔥 장단점

장점: SJF 스케줄링의 단점을 보완하는데, 예상실행시간이 긴 프로세스도 오래 대기하면 응답비율이 커져 나중에 들어오는 짧은 프로세스보다 먼저 디스패치 가능하다.
단점1: 모든 프로세스의 실행 시간을 알아야 하므로, 실제로는 프로세스의 CPU 시간을 예상할 수 없는 상황에서는 성능이 저하될 수 있다.
단점2: 오버헤드가 크지 않지만, 대기 시간을 계산하는 과정이 추가된다.

---

2-6. 다단계 피드백 큐(Multilevel Feadback Queue) 스케줄링

• 선점 스케줄링 방식
• 입출력 중심인 프로세스와 CPU 중심인 프로세스의 특성에 따라 서로 다른 시간 할당량을 부여
• n개의 단계가 있는 경우, 각 단계마다 하나씩의 큐가 존재하며, 단계 k는 단계 k+1에 피드백을 주며, 단계가 커질수록 시간 할당량은 커지는 형태로 구성

https://hyuntaekhong.github.io/blog/OperatingSystem03/

1) 처음 프로세스 도착하면 단계 1 큐에 들어간다.

2) 해당 큐의 시간 할당량 만큼 도착한 순서대로 프로세스 처리(FCFS)

3) 시간 할당량을 다 썼지만 프로세스가 종료되지 못했다면 다음 단계의 큐로 이동 배치

4) 3)의 과정을 반복하며 마지막 n단계 시간 할당량만큼 실행 후 종료되지 못한 경우 RR 스케줄링 방식으로 동작

단계 k의 큐에 있는 프로세스가 CPU를 할당 받으려면 단계 1부터 단계 k-1까지 모든 큐가 비어있어야 한다.

---

⭐그림 한장으로 요약⭐

아래 이미지는 정리가 잘 되어 있는 블로그에서 일괄 퍼왔습니다. 
https://velog.io/@inhalin/knou-os-03
 

---

참고자료 & 포스팅 작성에 도움을 주신 블로그 (꾸벅)

1. https://www.inflearn.com/course/운영체제-공룡책-전공강의/
2. 「Operating System Concepts」 by Siberschatz et. al.
3. 블로그

프로세스 스케줄링

[운영체제 03] 스케줄링 알고리즘

프로세스란? (PCB, Context Switching)

OS #4. CPU 스케줄링 (CPU Scheduling)

3강 스케줄링 알고리즘

스케줄링 알고리즘(FCFS, RR, SJF, SRT, Priority, MLQ, MFQ)

OS는 할껀데 핵심만 합니다. 6편 스케줄링3, 선점형 스케줄링 알고리즘(Round Robin, SRT, 우선 순위 방

[운영체제] CPU 스케줄링

CPU 스케줄링과 알고리즘