04｜프로세스 스케줄링 기법과 계산

프로세스 스케줄링은 준비 상태에 있는 여러 프로세스 가운데 어떤 프로세스에 CPU를 먼저 할당할지 결정하는 작업입니다. 운영체제는 제한된 CPU 자원을 효율적으로 사용하면서 처리량, 응답성, 공정성과 시스템 안정성을 함께 고려해야 합니다.

이 장에서는 프로세스 스케줄링의 목적과 평가 기준을 살펴보고, 비선점 방식인 FCFS·SJF·HRN과 선점 방식인 RR·SRT를 정리합니다. 우선순위 스케줄링은 선점형과 비선점형을 함께 다루고, 다단계 큐와 다단계 피드백 큐는 각 큐의 정책과 프로세스 이동 방식에 따라 비교합니다. 또한 대기 시간과 반환 시간을 직접 계산하여 각 알고리즘의 특성을 살펴봅니다.

프로세스 스케줄링이란 무엇인가?

프로세스 스케줄링(Process Scheduling)은 실행 가능한 프로세스들 가운데 CPU를 사용할 프로세스를 선택하고 실행 순서를 결정하는 운영체제의 기능입니다. 다중 프로그래밍 환경에서는 여러 프로세스가 동시에 준비 상태에 있을 수 있지만, 하나의 CPU 코어는 한 시점에 하나의 실행 흐름만 처리할 수 있으므로 스케줄링이 필요합니다.

스케줄러는 준비 큐에 있는 프로세스의 도착 시간, 우선순위, 예상 실행 시간, 남은 실행 시간과 시간 할당량 등을 기준으로 다음 실행 대상을 선택합니다. 선택된 프로세스에 CPU 제어권을 넘기는 동작은 디스패치라고 합니다.

스케줄러와 디스패처의 차이

구분	스케줄러	디스패처
주요 역할	다음에 실행할 프로세스를 선택	선택된 프로세스에 실제로 CPU 제어권을 전달
핵심 질문	어떤 프로세스를 실행할 것인가?	어떻게 실행을 전환할 것인가?
주요 작업	우선순위·실행 시간·큐 정책 판단	문맥 교환·사용자 모드 전환·실행 위치 복원
관련 비용	선택 알고리즘 수행 비용	디스패치 지연과 문맥 교환 비용

프로세스 스케줄링의 목적

모든 상황에서 절대적으로 가장 우수한 스케줄링 알고리즘은 없습니다. 일괄 처리 시스템은 처리량과 반환 시간을 중요하게 보고, 대화형 시스템은 응답 시간을 중요하게 보며, 실시간 시스템은 정해진 시간 제한을 지키는 것을 우선합니다.

스케줄링 성능은 어떻게 평가할까?

평가 항목	의미	바람직한 방향
CPU 이용률	전체 시간 중 CPU가 실제 작업을 수행한 시간의 비율	높을수록 좋음
처리량 Throughput	단위 시간 동안 완료된 프로세스 또는 작업의 수	많을수록 좋음
대기 시간 Waiting Time	프로세스가 준비 큐에서 CPU 할당을 기다린 총시간	짧을수록 좋음
반환 시간 Turnaround Time	프로세스가 도착하거나 제출된 때부터 전체 실행이 완료될 때까지의 시간	짧을수록 좋음
응답 시간 Response Time	프로세스가 도착한 뒤 처음 CPU를 할당받거나 첫 반응을 보일 때까지의 시간	짧을수록 좋음
공정성	특정 프로세스가 부당하게 무한정 대기하지 않도록 하는 정도	높을수록 좋음
오버헤드	스케줄링 판단과 문맥 교환에 소비되는 부가 비용	작을수록 좋음

스케줄링 계산에 사용하는 기본 공식

반환 시간은 프로세스가 도착한 시점부터 실행을 모두 마칠 때까지 걸린 전체 시간입니다.

입출력 대기를 별도로 고려하지 않는 단순 스케줄링 문제에서 대기 시간은 반환 시간에서 실제 CPU 실행 시간을 빼서 구합니다.

응답 시간은 프로세스가 도착한 뒤 처음으로 CPU를 할당받기까지 걸린 시간입니다.

비선점 스케줄링과 선점 스케줄링

비교 항목	비선점 스케줄링	선점 스케줄링
CPU 회수	프로세스가 종료되거나 대기 상태로 전환될 때까지 강제로 회수하지 않음	시간 할당량 만료나 높은 우선순위 작업 도착 시 강제로 회수 가능
문맥 교환	상대적으로 적음	상대적으로 자주 발생
오버헤드	작은 편	큰 편
응답성	긴 작업 때문에 짧은 작업이 오래 기다릴 수 있음	대화형·긴급 작업에 빠르게 대응 가능
구현	상대적으로 단순	타이머와 인터럽트 등의 지원 필요
대표 기법	FCFS, 비선점 SJF, HRN, 비선점 우선순위	RR, SRT, 선점 우선순위, 다단계 피드백 큐

FCFS 스케줄링

FCFS(First Come, First Served)는 준비 큐에 먼저 도착한 프로세스부터 CPU를 할당하는 비선점 스케줄링 방식입니다. FIFO(First In, First Out) 큐를 사용하므로 구현이 간단하고 도착 순서라는 명확한 기준을 적용합니다.

호위 효과란 무엇인가?

호위 효과(Convoy Effect)는 실행 시간이 긴 프로세스가 CPU를 먼저 차지하여, 뒤에 도착한 여러 짧은 프로세스가 긴 프로세스를 따라 줄지어 기다리는 현상입니다. 이로 인해 평균 대기 시간과 응답 시간이 증가하고 입출력장치와 CPU의 이용이 불균형해질 수 있습니다.

FCFS 계산 사례

다음 세 프로세스가 도착 시간 순서대로 준비 큐에 들어왔다고 가정합니다.

프로세스	도착 시간	실행 시간
P1	0	13
P2	3	35
P3	8	10

프로세스	완료 시간	대기 시간	반환 시간
P1	13	0	13
P2	48	10	45
P3	58	40	50

SJF 스케줄링

SJF(Shortest Job First)는 준비 큐의 프로세스 가운데 예상 실행 시간이 가장 짧은 프로세스를 먼저 선택하는 방식입니다. 일반적으로 SJF라고 하면 비선점 방식을 의미하며, 일단 실행을 시작하면 프로세스가 종료되거나 대기할 때까지 CPU를 계속 사용합니다.

모든 프로세스의 실행 시간을 정확히 알 수 있다면 SJF는 주어진 작업 집합의 평균 대기 시간을 최소화하는 데 유리합니다. 그러나 실제로는 미래의 CPU 실행 시간을 정확히 알기 어려워 과거 실행 기록 등을 바탕으로 추정해야 합니다.

SJF 계산 사례

네 프로세스가 모두 시간 0에 준비 큐에 도착했다고 가정합니다.

프로세스	실행 시간	실행 순서	대기 시간	반환 시간
P2	3	1	0	3
P1	6	2	3	9
P4	7	3	9	16
P3	8	4	16	24

HRN 스케줄링

HRN(Highest Response Ratio Next) 또는 HRRN은 실행 시간만 고려하는 SJF의 기아상태 문제를 완화하기 위해 대기 시간과 실행 시간을 함께 사용하는 비선점 스케줄링 방식입니다.

프로세스가 오래 기다릴수록 응답률이 높아지고, 실행 시간이 짧을수록 응답률이 높아집니다. CPU가 비는 시점마다 준비 큐에 있는 프로세스의 응답률을 계산하고 가장 높은 프로세스를 선택합니다.

HRN 응답률 비교 사례

프로세스	대기 시간	실행 시간	응답률
P1	5	20	$\frac{5+20}{20}=1.25$
P2	40	20	$\frac{40+20}{20}=3.00$
P3	15	45	$\frac{15+45}{45}\approx 1.33$
P4	20	20	$\frac{20+20}{20}=2.00$

우선순위 스케줄링

우선순위 스케줄링(Priority Scheduling)은 각 프로세스에 부여된 우선순위를 비교하여 가장 우선순위가 높은 프로세스에 CPU를 할당하는 방식입니다. 비선점형과 선점형 모두로 구현할 수 있습니다.

우선순위 숫자의 의미는 시스템에 따라 다릅니다. 어떤 시스템은 숫자가 작을수록 높은 우선순위를 나타내고, 다른 시스템은 숫자가 클수록 높은 우선순위를 나타냅니다. 문제에서 우선순위 값이 주어지면 반드시 기준을 먼저 확인해야 합니다.

기아상태와 에이징

높은 우선순위의 프로세스가 계속 도착하면 낮은 우선순위 프로세스는 CPU를 할당받지 못하고 무한정 기다릴 수 있습니다. 이를 기아상태 또는 무한 대기라고 합니다.

에이징(Aging)은 준비 큐에서 오래 기다린 프로세스의 우선순위를 시간에 따라 점차 높여 결국 CPU를 할당받도록 하는 방법입니다.

라운드 로빈 스케줄링

라운드 로빈(RR, Round Robin)은 준비 큐의 프로세스에 일정한 시간 할당량을 차례로 배정하는 선점 스케줄링 방식입니다. 프로세스가 시간 할당량 안에 작업을 끝내지 못하면 CPU를 반납하고 준비 큐의 뒤로 이동합니다.

각 프로세스가 순환하면서 반복적으로 CPU를 사용할 수 있으므로 시분할 시스템과 대화형 환경에 적합합니다. 같은 우선순위의 실행 단위에 공정한 실행 기회를 제공할 수 있습니다.

시간 할당량	장점	문제점
매우 큼	문맥 교환 횟수가 줄어듦	FCFS와 비슷해져 응답성이 낮아질 수 있음
적절함	응답성과 문맥 교환 비용의 균형	작업 특성에 맞는 값 선택 필요
매우 작음	각 프로세스가 빠르게 첫 실행 기회를 얻음	문맥 교환이 지나치게 자주 발생해 오버헤드 증가

SRT 스케줄링

SRT(Shortest Remaining Time)는 현재 준비된 프로세스 가운데 남은 실행 시간이 가장 짧은 프로세스를 선택하는 선점 스케줄링 방식입니다. SJF의 선점형 확장으로 볼 수 있어 SRTF(Shortest Remaining Time First)라고도 합니다.

실행 중인 프로세스보다 남은 실행 시간이 짧은 새 프로세스가 도착하면 현재 프로세스의 CPU를 선점하여 새 프로세스를 실행할 수 있습니다.

다단계 큐 스케줄링

다단계 큐(Multilevel Queue) 스케줄링은 프로세스를 성격이나 우선순위에 따라 여러 준비 큐로 분류하고, 각 큐마다 서로 다른 스케줄링 정책을 적용하는 방식입니다.

예를 들어 대화형 프로세스에는 RR을, 일괄 처리 프로세스에는 FCFS를 적용할 수 있습니다. 큐 사이에는 고정 우선순위나 각 큐에 CPU 시간을 배분하는 별도의 정책을 사용할 수 있습니다.

다단계 피드백 큐 스케줄링

다단계 피드백 큐(Multilevel Feedback Queue)는 여러 단계의 준비 큐를 사용하면서 프로세스의 CPU 사용 특성과 대기 시간에 따라 프로세스를 다른 큐로 이동시킬 수 있는 방식입니다.

상위 큐는 높은 우선순위와 짧은 시간 할당량을 사용하고, 하위 큐로 갈수록 우선순위가 낮아지고 시간 할당량이 길어지는 형태가 일반적입니다. 시간 할당량 안에 작업을 끝내지 못한 CPU 중심 프로세스는 하위 큐로 이동하고, 오래 기다린 프로세스는 에이징이나 우선순위 상향을 통해 상위 큐로 이동할 수 있습니다.

비교 항목	다단계 큐	다단계 피드백 큐
큐 구성	프로세스 종류별 여러 준비 큐	우선순위와 실행 특성별 여러 준비 큐
큐 사이 이동	일반적으로 제한됨	실행 결과와 대기 시간에 따라 가능
정책 변화	처음 분류된 정책을 계속 적용	프로세스 행동에 따라 정책이 달라짐
적응성	상대적으로 낮음	상대적으로 높음
기아상태 대응	별도 정책 필요	상위 큐 이동과 에이징으로 완화 가능

주요 스케줄링 기법 비교

기법	선점 여부	선택 기준	주요 장점	주요 문제
FCFS	비선점	도착 순서	구현이 단순함	호위 효과
SJF	비선점	실행 시간이 가장 짧음	평균 대기 시간 감소	긴 작업 기아상태·시간 추정
HRN	비선점	응답률이 가장 높음	SJF의 기아상태 완화	응답률 재계산 필요
우선순위	둘 다 가능	가장 높은 우선순위	중요 작업 우선 처리	낮은 우선순위 기아상태
RR	선점	순환 순서와 시간 할당량	공정성과 응답성	시간 할당량에 따른 오버헤드
SRT	선점	남은 실행 시간이 가장 짧음	짧은 작업에 빠른 대응	긴 작업 기아상태·잦은 선점
다단계 큐	정책에 따라 다름	프로세스 종류와 큐 우선순위	작업 유형별 정책 적용	큐 사이 이동 제한
다단계 피드백 큐	주로 선점	실행 특성과 큐 단계	적응성과 대화형 응답성	설계와 튜닝이 복잡함

시험에서 자주 혼동되는 개념

이번 장 핵심 요약

1. 프로세스 스케줄링은 준비 상태의 프로세스 중 CPU를 할당할 대상을 결정합니다.
2. CPU 이용률과 처리량은 높을수록, 대기·반환·응답 시간은 짧을수록 좋습니다.
3. 대기 시간은 준비 큐에서 기다린 시간이고 반환 시간은 도착부터 완료까지의 시간입니다.
4. FCFS는 도착 순서대로 실행하며 긴 작업 때문에 호위 효과가 발생할 수 있습니다.
5. SJF는 실행 시간이 가장 짧은 프로세스를 먼저 실행하며 평균 대기 시간 감소에 유리합니다.
6. HRN은 대기 시간과 실행 시간을 함께 반영한 응답률이 가장 높은 프로세스를 우선합니다.
7. 우선순위 스케줄링의 기아상태는 에이징으로 완화할 수 있습니다.
8. RR은 일정한 시간 할당량을 순환하여 배정하는 선점 방식입니다.
9. RR의 시간 할당량이 매우 크면 FCFS와 비슷해지고, 너무 작으면 문맥 교환이 증가합니다.
10. SRT는 남은 실행 시간이 가장 짧은 프로세스를 선택하는 SJF의 선점형 방식입니다.
11. 다단계 큐는 작업 유형별로 큐를 분리하고, 다단계 피드백 큐는 프로세스의 큐 이동을 허용합니다.
12. 실제 스케줄링 문제에서는 도착 시간, 실행 시간, 우선순위 기준과 선점 여부를 먼저 확인해야 합니다.

복습 문제

프로세스 스케줄링의 가장 기본적인 역할은?

준비 상태의 프로세스 가운데 다음에 CPU를 할당할 프로세스와 실행 순서를 결정하는 것입니다.

스케줄러와 디스패처는 어떻게 다를까?

스케줄러는 다음 실행 대상을 선택하고, 디스패처는 선택된 프로세스의 문맥을 복원하여 실제로 CPU 제어권을 넘깁니다.

대기 시간과 반환 시간의 차이는?

대기 시간은 프로세스가 준비 큐에서 CPU를 기다린 총시간이고, 반환 시간은 프로세스가 도착한 시점부터 전체 실행이 끝날 때까지의 시간입니다.

FCFS에서 발생할 수 있는 호위 효과란?

실행 시간이 긴 프로세스가 앞에서 CPU를 오래 사용하여 뒤의 여러 짧은 프로세스가 함께 오래 기다리는 현상입니다.

SJF가 평균 대기 시간 감소에 유리하면서도 실제 적용이 어려운 이유는?

각 프로세스의 미래 실행 시간을 정확히 알아야 하지만 실제 시스템에서는 이를 정확히 알기 어려워 추정해야 하기 때문입니다.

HRN의 응답률 공식과 선택 기준은?

응답률은 대기 시간과 실행 시간을 분수 형태로 계산하며, 그 값이 가장 높은 프로세스를 선택합니다.

우선순위 스케줄링에서 기아상태를 완화하는 방법은?

오래 기다린 프로세스의 우선순위를 점차 높이는 에이징을 적용합니다.

라운드 로빈의 시간 할당량이 매우 커지면 어떤 방식과 비슷해질까?

각 프로세스가 사실상 종료될 때까지 실행될 가능성이 커지므로 FCFS와 비슷해집니다.

라운드 로빈의 시간 할당량이 지나치게 작으면 어떤 문제가 생길까?

문맥 교환이 지나치게 자주 발생하여 스케줄링 오버헤드가 커집니다.

SJF와 SRT의 핵심 차이는?

SJF는 실행 시간이 가장 짧은 프로세스를 선택한 뒤 계속 실행하는 비선점 방식이고, SRT는 더 짧은 남은 실행 시간을 가진 프로세스가 도착하면 CPU를 선점할 수 있습니다.

다단계 큐와 다단계 피드백 큐의 핵심 차이는?

다단계 큐에서는 프로세스의 큐 사이 이동이 일반적으로 제한되지만, 다단계 피드백 큐에서는 프로세스의 실행 특성과 대기 시간에 따라 다른 큐로 이동할 수 있습니다.

SJF 문제에서 실행 시간이 P1=6, P2=3, P3=8, P4=7이고 모두 동시에 도착했다면 첫 번째 프로세스는?

실행 시간이 3으로 가장 짧은 P2입니다.

HRN에서 P1의 대기 시간이 5, 실행 시간이 20이라면 응답률은?

대기 시간 5와 실행 시간 20을 응답률 공식에 대입하면 $\frac{5+20}{20}=1.25$입니다.