[2일차] 정보처리산업기사 운영체제 – 선점형 스케줄링 정리 (SRTF, RR, Priority, MLFQ, MLQ)

---

1. SRTF (Shortest Remaining Time First)

개념

SRTF는 SJF(Shortest Job First) 의 선점형 버전이다.

매 시점마다 “남은 실행시간(Remaining Time)”이 가장 짧은 프로세스가 CPU를 차지한다.

문제 예시

프로세스	도착시간(A)	CPU 버스트(B)
P1	0	8
P2	1	4
P3	2	9
P4	3	5

---

실행 흐름 (스위칭 과정)

시간 구간	도착 / 실행 판단	현재 실행	전환 이유
t=0~1	P1만 존재	P1	초기 실행
t=1	P2(4) 도착 → 남은시간 7 vs 4 → P2로 교체	P2	짧은 남은 시간
t=1~5	P2 실행 완료	P2	완료
t=5	{P1(7), P3(9), P4(5)} → P4 선택	P4	남은시간 가장 짧음
t=5~10	P4 실행 완료	P4	완료
t=10	{P1(7), P3(9)} → P1 선택	P1	남은시간 짧음
t=10~17	P1 실행 완료	P1	완료
t=17~26	남은 P3 실행	P3	마지막 프로세스

---

간트 차트

---

계산 결과

프로세스	A	B	C	T=C−A	W=T−B
P1	0	8	17	17	9
P2	1	4	5	4	0
P3	2	9	26	24	15
P4	3	5	10	7	2

• 평균 반환시간 = (17+4+24+7) / 4 = 13.0
• 평균 대기시간 = (9+0+15+2) / 4 = 6.5

---

2. RR (Round Robin)

개념

모든 프로세스에 동일한 시간(Time Quantum) 을 순서대로 배분하는 방식이다.

시분할 시스템(Time-Sharing System)에서 자주 사용되며,

공평성(Fairness)과 빠른 응답성(Responsiveness)을 중시한다.

---

예시 데이터

프로세스	도착시간(A)	CPU 버스트(B)
P1	0	5
P2	1	4
P3	2	2
P4	3	1

타임 슬라이스(Time Quantum) = 2

---

실행 순서 (스위칭 흐름)

시간 구간	실행 프로세스	남은 시간 변화	설명
0~2	P1	5 → 3	첫 실행
2~4	P2	4 → 2	교체
4~6	P3	2 → 0	완료
6~8	P4	1 → 0	완료
8~10	P1	3 → 1	남은 작업
10~11	P1	1 → 0	완료
11~13	P2	2 → 0	완료

---

간트 차트

계산 공식

• 반환시간(T) = 완료시간(C) − 도착시간(A)
• 대기시간(W) = 반환시간(T) − CPU버스트(B)

---

계산 결과

프로세스	A	B	C	T	W
P1	0	5	11	11	6
P2	1	4	13	12	8
P3	2	2	6	4	2
P4	3	1	8	5	4

• 평균 반환시간 = (11+12+4+5)/4 = 8.0
• 평균 대기시간 = (6+8+2+4)/4 = 5.0

---

3. Priority Scheduling (우선순위 스케줄링)

개념

각 프로세스에 우선순위(Priority) 를 부여하여

가장 높은 우선순위(숫자가 낮을수록 높음)를 가진 프로세스가 먼저 CPU를 점유한다.

선점형과 비선점형 모두 가능하지만, 여기서는 선점형 기준으로 정리한다.

---

예시 데이터

프로세스	도착시간(A)	CPU 버스트(B)	우선순위(P)
P1	0	5	3
P2	1	3	1
P3	2	2	4
P4	3	1	2

---

실행 순서

시간 구간	실행 프로세스	이유
0~1	P1	첫 도착
1~4	P2	우선순위 1 (가장 높음)
4~5	P4	우선순위 2
5~7	P1	남은 실행 재개
7~9	P3	우선순위 4, 마지막 실행

---

간트 차트

특징 요약

• 장점: 중요 작업을 먼저 처리 가능
• 단점: 낮은 우선순위 프로세스가 무한 대기 → 기아(Starvation)
• 해결책: Aging(에이징) → 오래 대기할수록 우선순위를 높임

---

4. Multilevel Queue (MLQ)

개념

Multilevel Queue(다단계 큐 스케줄링) 은

프로세스들을 성격(우선순위, 목적, 사용자 유형 등)에 따라 여러 개의 큐로 나누어 관리하는 방식이다.

예를 들어,

• 시스템 프로세스(운영체제 수준)
• 대화형(Interactive) 프로세스
• 배치(Batch) 프로세스

이렇게 나누고, 각 큐마다 다른 스케줄링 정책을 적용할 수 있다.

큐 간에는 우선순위가 고정되어 있으며, 상위 큐가 항상 CPU를 선점한다.

---

예시 데이터

큐 이름	프로세스 유형	적용 알고리즘	우선순위
Q1	시스템 프로세스	RR (Quantum=4)	1 (가장 높음)
Q2	대화형 프로세스	SJF	2
Q3	배치 프로세스	FCFS	3 (가장 낮음)

---

동작 흐름 (스위칭 예시)

1. CPU는 항상 가장 높은 우선순위 큐(Q1) 를 먼저 확인한다.
2. Q1에 실행할 프로세스가 없을 때만 Q2로 넘어간다.
3. Q2에서도 없으면 Q3를 실행한다.
4. 즉, 상위 큐가 비워져야 하위 큐가 실행 가능하다.

---

간트 차트

• Q1: Round Robin(타임 슬라이스 4)
• Q2: SJF 방식
• Q3: FCFS 방식

---

장점

• 프로세스 특성에 따라 스케줄링 분리 가능
• CPU 활용도 향상
• 관리 정책이 명확

---

단점

• 큐 간 우선순위 고정 → 하위 큐가 실행되지 못할 가능성
• 큐 간 이동이 불가능 (프로세스가 한 큐에 고정)
• 균형 조절이 어려움

---

기억 포인트

MLQ는

정적(Static) 우선순위 기반 큐 분리 구조

각 큐는 서로 다른 알고리즘을 가질 수 있고,

큐 간 우선순위 고정

---

5. MLFQ (Multilevel Feedback Queue)

개념

다단계 피드백 큐(Multilevel Feedback Queue) 는

실제 운영체제에서 가장 널리 쓰이는 현실형 스케줄링이다.

프로세스의 실행 이력에 따라 우선순위를 동적으로 조정한다.

---

구조 예시

큐 번호	정책	타임 슬라이스
Q1	RR	4
Q2	RR	8
Q3	FCFS	–

---

동작 예시

1. 새 프로세스는 Q1(우선순위 가장 높음)에서 시작
2. 주어진 타임슬라이스 내에 끝나면 종료
3. 시간을 초과하면 Q2로 이동
4. 다시 초과하면 Q3로 이동 → CPU를 오래 사용하는 프로세스일수록 낮은 우선순위 큐로 내려감

---

간트 차트

특징

• 장점: 다양한 작업 유형에 적응, 현실 시스템에 가장 근접
• 단점: 설정이 복잡하고, 파라미터 조정이 어렵다

---

요약 비교표

알고리즘	선점	기준	장점	단점
SRTF	O	남은 실행시간	평균 대기시간 최소	잦은 교체, 기아 발생
RR	O	타임 슬라이스	공평성, 빠른 응답성	타임 슬라이스 조정 필요
Priority	O / X	우선순위	중요 작업 우선	기아 문제 발생 (Aging)
MLQ	O	큐 간 우선순위	유형별 정책 적용	하위 큐 실행 불균형
MLFQ	O	동적 우선순위	현실 시스템 유사	구조 복잡, 튜닝 어려움

---

6. 결론

선점형 스케줄링은 운영체제의 CPU 자원을 효율적으로 분배하고, 시스템 응답속도를 향상시키는 핵심 알고리즘이다.

각 기법은 적용 목적과 계산 방식이 다르기 때문에, 시험에서는 구분 중심으로 학습하는 것이 중요하다.

• SRTF 와 RR 은 실제 계산 문제가 자주 출제되므로, 간트 차트 작성과 평균 대기시간 계산 과정을 반드시 연습해야 한다.
• Priority Scheduling 과 MLFQ 는 개념 중심 문제로, 우선순위 변화, 기아(Starvation), Aging(에이징) 원리의 이해가 핵심이다.

요약하면,

• 타임 슬라이스 계산 (RR)
• SJF와 SRTF의 차이 비교
• Aging을 통한 우선순위 조정 원리

이 세 가지가 실기 시험에서 가장 자주 등장한다.

따라서 계산 훈련과 개념 구분을 함께 익히는 것이 효과적이다.

---