🤖 프로세스 스케줄링 알고리즘 | 🚀 정처기 실기 대비 문제 풀이 방법 포함

📝 프로세스 스케줄링 알고리즘 정리

🚦 프로세스 스케줄링, 왜 필요할까?

컴퓨터는 여러 프로세스를 동시에 처리해야 합니다. 이때, 어떤 프로세스에 CPU를 할당할지 결정하는 규칙이 바로 프로세스 스케줄링입니다. 스케줄링의 목표는 CPU를 효율적으로 사용하고, 모든 프로세스에 공평한 기회를 주며, 사용자의 대기 시간을 최소화하는 것입니다.

스케줄링 방식은 크게 비선점형(Non-preemptive) 과 선점형(Preemptive) 두 가지로 나뉩니다.

• 비선점형 스케줄링: 한 프로세스가 CPU를 할당받으면, 해당 프로세스가 종료되거나 입출력(I/O) 작업을 위해 스스로 CPU를 반납할 때까지 다른 프로세스가 CPU를 빼앗을 수 없습니다.
• 선점형 스케줄링: 운영체제가 필요하다고 판단하면, 현재 실행 중인 프로세스를 중단시키고 다른 프로세스에 CPU를 강제로 할당할 수 있습니다. 시분할 시스템에 적합합니다.

💡 아래 각 알고리즘 설명과 함께 제공되는 예제 문제를 통해 평균 대기 시간과 평균 반환 시간을 직접 계산해보세요!

---

🚫 비선점형 스케줄링 (Non-preemptive Scheduling)

한 번 할당되면 끝날 때까지 아무도 막을 수 없는 방식입니다.

1. FIFO (First-In, First-Out) 또는 FCFS (First-Come, First-Served)

가장 간단한 방식으로, 준비 큐(Ready Queue)에 도착한 순서대로 CPU를 할당합니다.

• 장점: 구현이 쉽고 공평합니다.
• 단점: 실행 시간이 긴 프로세스가 먼저 도착하면 뒤따르는 짧은 프로세스들이 하염없이 기다려야 하는 콘보이 효과(Convoy Effect) 가 발생할 수 있습니다.

2. SJF (Shortest Job First)

실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당합니다.

• 장점: 평균 대기 시간을 최소화하는 최적의 알고리즘입니다.
• 단점: 실행 시간이 긴 프로세스는 계속해서 새로운 짧은 프로세스에 밀려 무한정 기다릴 수 있는 기아 현상(Starvation) 이 발생할 수 있습니다. 또한, 각 프로세스의 실행 시간을 미리 정확히 예측하기 어렵습니다.

3. HRN (Highest Response-ratio Next)

SJF의 기아 현상을 보완하기 위해 만들어졌습니다. 대기 시간과 실행 시간을 모두 고려하여 우선순위를 동적으로 결정합니다.

• 우선순위 계산: (대기 시간 + 실행 시간) / 실행 시간
• 특징: 이 값이 가장 높은 프로세스에게 CPU를 할당합니다. 대기 시간이 길어질수록 우선순위가 높아지므로 기아 현상을 방지할 수 있습니다.

4. 기한부 (Deadline)

프로세스에 주어진 마감 시간(Deadline) 안에 작업을 완료해야 하는 실시간 시스템에서 사용됩니다. 마감 시간이 가장 임박한 프로세스에 높은 우선순위를 부여합니다.

5. 우선순위 (Priority)

각 프로세스에 부여된 정적 우선순위에 따라 CPU를 할당합니다. 우선순위가 가장 높은 프로세스가 먼저 실행됩니다. SJF처럼 기아 현상이 발생할 수 있습니다.

---

🔄 선점형 스케줄링 (Preemptive Scheduling)

실행 중인 프로세스를 언제든 중단시키고 다른 프로세스에 CPU를 넘겨줄 수 있는 유연한 방식입니다.

1. 라운드 로빈 (Round Robin, RR)

FIFO에 시간 할당량(Time Quantum 또는 Time Slice) 개념을 추가한 방식입니다. 모든 프로세스는 정해진 시간 할당량만큼만 CPU를 사용하고, 시간이 다 되면 준비 큐의 맨 뒤로 돌아갑니다.

• 장점: 모든 프로세스가 공평하게 CPU 시간을 보장받아 대화형 시스템에 적합합니다.
• 단점: 시간 할당량이 너무 크면 FIFO와 같아지고, 너무 작으면 문맥 교환이 너무 잦아져 오버헤드가 커집니다. 적절한 시간 할당량을 설정하는 것이 중요합니다.

2. SRT (Shortest Remaining Time)

선점형 SJF 알고리즘입니다. 현재 실행 중인 프로세스의 남은 시간보다 더 짧은 실행 시간을 가진 새로운 프로세스가 도착하면, 즉시 CPU를 빼앗아 그 새로운 프로세스에 할당합니다.

• 장점: 평균 대기 시간을 더 줄일 수 있습니다.
• 단점: 잦은 문맥 교환(Context Switching)으로 인한 오버헤드가 발생할 수 있으며, 여전히 기아 현상이 발생할 수 있습니다.

---

📝 정처기 실기 대비 문제

문제 1 - SJF

문제 풀이

아래와 같이 표를 그리면 쉽게 풀 수 있습니다. 표에 도착 시간(O), 대기 시간(X), 실행 시간(V)을 표시하세요.

프로세스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
P1	O	V	V	V	V	V	V
P2		O	X	X	X	X	X	X	X	V	V	V
P3			O	X	X	X	X	X	X	X	X	X	V	V	V	V
P4				O	X	X	X	V	V

대기시간

• P1: 0
• P2: 7
• P3: 9
• P4: 2
• 평균 대기시간 : $\frac{0 + 7 + 9 + 2}{4} = 4.5$

반환시간

반환시간 = 대기시간 + 실행시간

• P1: 6
• P2: 10
• P3: 13
• P4: 5
• 평균 반환시간 : $\frac{6 + 10 + 13 + 5}{4} = 8.5$

---

문제 2 - SRT

문제 풀이

아래와 같이 표를 그리면 쉽게 풀 수 있습니다. 표에 도착 시간(O), 대기 시간(X), 실행 시간(V)을 표시하세요.

단, SRT는 남은 시간이 중요합니다. 새로운 프로세스가 도착했다면 그 다음 어떤 프로세스를 실행할지 결정할 때 남은 시간을 고려해야 합니다.

도착, 실행 시 남은 시간을 적어놓는 것이 문제를 푸는데 좋은 방법입니다. (예 : O6는 남은 시간이 6입니다.V5 는 남은 시간이 5입니다.)

프로세스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
P1	O6	V5	X	X	X	X	X	X	X	X	X	V4	V3	V2	V1	V0
P2		O3	V2	V1	V0
P3			O4	X	X	X	X	V3	V2	V1	V0
P4				O2	X	V1	V0

대기시간

• P1: 9
• P2: 0
• P3: 4
• P4: 1
• 평균 대기시간 : $\frac{9 + 0 + 4 + 1}{4} = 3.5$

반환시간

반환시간 = 대기시간 + 실행시간

• P1: 15
• P2: 3
• P3: 8
• P4: 3
• 평균 반환시간 : $\frac{15 + 3 + 8 + 3}{4} = 7.25$

---

문제 3 - RR

문제 풀이

아래와 같이 표를 그리면 쉽게 풀 수 있습니다. 표에 도착 시간(O), 대기 시간(X), 실행 시간(V)을 표시하세요.

프로세스	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
P1	O	V	V	X	X	X	X	X	X	V	V	X	X	X	V	V
P2		O	X	V	V	X	X	X	X	X	X	V
P3			O	X	X	V	V	X	X	X	X	X	V	V
P4				O	X	X	X	V	V

대기시간

• P1: 9
• P2: 7
• P3: 7
• P4: 3
• 평균 대기시간 : $\frac{9 + 7 + 7 + 3}{4} = 6.5$

반환시간

반환시간 = 대기시간 + 실행시간

• P1: 15
• P2: 10
• P3: 11
• P4: 5
• 평균 반환시간 : $\frac{15 + 10 + 11 + 5}{4} = 10.25$

---

➡️ 다음 읽으면 좋은 포스팅

• 💭 메모리 페이지 교체 알고리즘 | 🚀 정처기 실기 대비 문제 풀이 방법 포함
• 정처기 실기 2025년 2회 이론 문제 예상 | ⚡️ 벼락치기 팁 정리