# 프로세스 스케줄링
---
## 1. 선점(Preemptive) 스케줄링
> 선점 스케줄링이란 우선순위가 높은 프로세스가 현재 프로세스를 중지시키고 자신이 CPU를 점유하는 스케줄링 기법
- 실행 중인 프로세스를 중단하고,더 우선순위가 높은 다른 프로세스에게 CPU를 양보
- 비교적 응답이 빠르다는 장점이 있으나, 처리 시간을 예측하기 힘들고 높은 우선순위 프로세스들이 계속 들어오는 경우 오버헤드가 발생하게 된다.
- 선점 스케줄링의 예로는 RR, SRT, 다단계 큐, 다단계 피드백 큐가 있음.
📌 선점 스케줄링 알고리즘
🔹 Round Robin : 시간 할당량(Time Quantum) 지나면 다음 프로세스로 교체
🔹 SRTF (Shortest Remaining Time First) : 남은 시간이 더 짧은 새 작업이 오면 현재 작업 중단
🔹 선점형 우선순위(Priority Scheduling) : 더 높은 우선순위의 프로세스가 도착하면 중단됨
---
## 2. 비선점(Non-preemptive) 스케줄링[](https://dainwiki.com/uploads/images/gallery/2025-07/7g3mF2UwxXr0d5Ae-image.png)
> 프로세스가 자원을 할당받았을 경우 자원을 스스로 반납할 때 까지 계속 그 자원을 사용하도록 허용하는 기법
한 번 실행된 프로세스는 끝날 때까지 CPU를 점유한다. 그래서 새로 도착한 프로세스는 대기해야 한다.
중요한 작업이 길면, 뒤에 있는 짧은 작업이 오래 기다릴 수 있기 때문에 기아현상 발생 가능
📌 비선점 스케줄링 알고리즘
🔸 FCFS (First Come First Serve) : 먼저 도착한 순서대로 실행
🔸 SJF (Shortest Job First) : 실행시간이 짧은 것부터 실행
🔸 비선점 우선순위 스케줄링 : 우선순위 높은 순으로 실행, 중간 교체 없음
🔸 HRN (Highest Response Ratio Next) : 반응 비율 기반, 대기시간 고려
---
## ****문제풀이****
비선점은 들어온 순서대로 처리하니까 쉬움
선점형은 실행 도중에도 더 짧은 프로세스가 도착하면 현재 작업을 중단하고 짧은 걸 먼저 실행하므로실행 순서가 바뀜
### 1.FCFS
- 난이도 ⭐
- 도착한 순서대로 처리하면 됨
[](https://dainwiki.com/uploads/images/gallery/2025-07/Ia0bH9Tfu9rAMhST-image.png)
- 최소 평균 반환시간 t 는 실행시간이 짧은 것부터 실행 (P2 → P1 → P3)
- t = ( 0 + 3 + 12 ) / 3 = 15 / 3 = 5
- 최대 평균 반환시간 T 는 실행시간이 긴 것부터 나열 (P3 → P1 → P2)
- T = (0 + 12 + 21) / 3 = 33 / 3 = 11
- T - t = 11 - 5 = 6
### 2.SFJ
- 난이도 ⭐
- 실행시간 짧은 것부터 실행하면 됨
- 평균대기시간 / 평균반환시간 / 평균실행시간 중 무엇을 구해야 하는지 확인
[](https://dainwiki.com/uploads/images/gallery/2025-07/AjTEx19j6gc8xsV4-image.png)
| ****프로세스****
| ****실행시간****
| ****대기시간****
| ****반환시간****
|
| P-2
| 3
| 0
| 3
|
| P-1
| 6
| 3
| 9
|
| P-4
| 7
| 9
| 16
|
| P-3
| 8
| 16
| 24
|
|
|
| ****28 / 4 = 7****
| ****52 / 4 = 13****
|
[](https://dainwiki.com/uploads/images/gallery/2025-07/tX7iulvX2FH99Iu4-image.png)
| Task
| 도착시간
| 실행시간
| 대기시간
| 반환시간
|
| Task1
| 0
| 6
| 0
| 6
|
| Task2
| 1
| 3
| 6
| ****9****
|
| Task3
| 2
| 2
| 9
| 2
|
| 합계
|
|
| 15
| 17
|
- Task2의 반환시간 = 2의 대기시간(Waiting Time) + 2의 실행시간(Burst Time) = 6 + 3 = 9
⭐ 도착시간이 0일 때 T1만 도착했기 때문에 T1가 실행시간이 길더라도 먼저 실행된다. (왜? 해당 시간에 도착한 작업이 T1뿐)
### 3.HRN
- 난이도 ⭐
- 비선점 스케줄링 알고리즘 중 하나로, 대기시간이 길어질수록 우선순위가 높아지는 방식
- ****우선순위 = 1 + 대기시간/서비스 시간****
- → 숫자가 클수록 우선순위가 높다!
✅ HRN 우선순위 계산식
- 대기시간 (Waiting Time) = 현재 시점 − 도착시간 − 아직 실행 안 된 경우
- 서비스시간 (Service Time) = 실행시간, 즉 Burst Time
- 짧은 작업(SJF)에게 유리하면서도,오래 기다린 작업도 점점 우선순위가 높아져 기아 현상(starvation) 방지 가능!
[](https://dainwiki.com/uploads/images/gallery/2025-07/TSOuAuZkKqNjWJln-image.png)
- A = 1 + (8 / 2) = 1 + 4 = 5
- B = 1 + (10 / 6) = 2.6666
- C = 1 + (15 / 7) = 3.14
- D = 1 + (20 / 8) = 3.5
- 우선 순위 큰 순서대로 ****A > D > C > B****
### 4.SRT
- 난이도 ⭐⭐
- SRT(Shortest Remaining Time First)는 선점형 프로세스 스케줄링 알고리즘 방식
- 현재 실행 중인 프로세스보다 남은 실행시간이 더 짧은 새로운 프로세스가 도착하면 CPU를 양보하기
- 그래프 그리면서 풀기
- ****반환시간 = 종료시간 - 도착시간****
[](https://dainwiki.com/uploads/images/gallery/2025-07/0KsEjJCITVF4L3H0-image.png)
[](https://dainwiki.com/uploads/images/gallery/2025-07/fFnZwMmvl2H14MUX-image.png)
### 5.RR(Round Robin)
- 난이도 ⭐⭐⭐
- 타임 퀀텀 (Time Quantum) 이 주어짐
- 선입선출 (FIFO) 방식으로 할당시간(타임 퀀텀)만큼 실행 후 대기 큐로 이동
- 새로운 작업이 도착하면 도착 순서대로 대기 큐에 추가
- ****할당 시간****이 중요
- ****대기큐 + 남은 시간 + 그래프**** 세 가지를 그리면서 풀어야 함
- ****무조건 짧은게 우선이 아니라 큐에 들어간 순서대로 다시 실행되므로 만약 프로세스가 3개면 3개가 번갈아 가면서 실행됨****
- 유형 : ****CPU 사용 순서 / 평균 대기시간 / 평균 반환시간**** 문제!
- ⭐ 대기 시간 (Waiting Time, WT) = 완료 시간 (FT) - 도착 시간 (AT) - 실행 시간 (BT)
- ⭐ 반환 시간 (Turnaround Time, TAT) = 완료 시간 (FT) - 도착 시간 (AT)
#### ****CPU 사용 순서 문제****
[](https://dainwiki.com/uploads/images/gallery/2025-07/1MuHvRRf3H7YXFm4-image.png)
[](https://dainwiki.com/uploads/images/gallery/2025-07/FmycT0APR4nlWzAY-image.png)
****라운드 로빈 방식에서 주의할 점****
****⭐ 남은 실행 시간만 보고 풀면 틀린다.****
****⭐ 대기큐를 그려야 한다.****
라운드 로빈 (RR) 스케줄링을 풀 때 대기 큐의 순서를 반드시 고려해야 한다. 단순히 "남은 실행 시간"만 보고 짧은 작업을 먼저 실행하는 것이 아니라, 큐에 들어간 순서대로 작업이 실행된다.
타임 퀀텀(시간 할당)이 끝나면 무조건 대기 큐로 이동! → 대기 큐에 있는 순서대로 실행! → 남은 실행 시간이 짧아도 먼저 실행되지 않음 → 그래서 모든 작업이 번갈아가면서 실행됨
라운드 로빈에서는 남은 시간이 적은 작업이 있더라도 먼저 들어온 순서대로 실행된다. 즉, ABC 세 개의 작업이 남아 있다면, ABC 순서대로 계속 번갈아가면서 실행된다. 이걸 놓치면 잘못된 순서로 풀게 되어 답이 틀릴 수 있다.
[](https://dainwiki.com/uploads/images/gallery/2025-07/zlMs7UlWAQTO2aWj-image.png)
이렇게 풀면 절대 틀리지 않는다.
#### ****평균 대기시간 문제****
> 대기 시간 (Waiting Time, WT) = 완료 시간 (FT) - 도착 시간 (AT) - 실행 시간 (BT)
####
#### ****평균 반환시간 문제****
> 반환 시간 (Turnaround Time, TAT) = 완료 시간 (FT) - 도착 시간 (AT)
\- 이런 문제는 도착시간이 모두 0이라고 생각하고 푼다 (문제에 따로 명시되지 않았기 때문)
---
참고 자료
1. 흥달쌤의 정보처리기사 계산식 특강
2. [https://buly.kr/8eljGok](https://buly.kr/8eljGok)