CPU 스케줄링 알고리즘과 성능 지표

CPU를 배분하는 운영체제의 판단

멀티프로그래밍 환경에서는 여러 프로세스가 동시에 실행 기회를 기다린다. CPU 스케줄링은 이들 프로세스가 한정된 CPU 자원을 공유하도록 조정하며, CPU 유휴 시간을 줄이고 자원을 공정하게 나누는 역할을 맡는다. 이 선택은 시스템의 처리량과 사용자 응답성에 직접 영향을 준다.

⤢✕

준비 큐에는 CPU 실행을 기다리는 프로세스가 들어간다. CPU 스케줄러는 이 큐에서 다음 실행 대상을 고르고, 디스패처는 선택된 프로세스에 CPU를 넘긴다. 이 과정에서 프로세스가 바뀌면 문맥 교환(Context Switch)을 통해 실행 상태를 저장하고 복원한다.

CPU를 회수하는 방식은 크게 비선점과 선점으로 나뉜다. 비선점 방식에서는 프로세스가 자발적으로 CPU를 반납할 때까지 실행된다. 구현이 단순하고 오버헤드가 낮은 반면, 응답성이 떨어질 수 있다. FCFS, SJF, HRN이 여기에 속한다.

선점 방식은 운영체제가 실행 중인 프로세스에서 CPU를 회수할 수 있다. 응답성에는 유리하지만 문맥 교환 오버헤드가 발생한다. Round Robin, SRTF, 다단계 큐가 대표적이다.

운영 목표를 드러내는 성능 지표

⤢✕

처리능력(Throughput)은 단위 시간당 완료된 프로세스 수다. 완료된 프로세스 수를 전체 시간으로 나눠 계산하며, 값이 높을수록 시스템 효율성이 높다.

반환시간(Turnaround Time)은 프로세스 제출부터 완료까지 걸린 전체 시간이다. 완료 시간에서 도착 시간을 빼며, 사용자 관점에서 중요한 지표가 된다.

대기시간(Waiting Time)은 프로세스가 준비 큐에서 기다린 총 시간이다. 반환시간에서 실행시간과 I/O 시간을 빼서 계산할 수 있어 CPU 스케줄링 효율성을 직접 보여준다.

응답시간(Response Time)은 요청을 제출한 시점부터 첫 응답을 받기까지의 시간이다. 첫 실행 시작 시간에서 도착 시간을 빼며, 대화형 시스템에서 특히 중요하다.

CPU를 자발적으로 반납하는 방식

FCFS: 도착 순서가 실행 순서가 될 때

⤢✕

FCFS(First-Come, First-Served)는 도착한 순서대로 프로세스를 처리한다. 구현이 단순하고 도착 순서를 지킨다는 점에서 공평하지만, 평균 대기시간이 길어질 수 있다. CPU 사용시간이 긴 프로세스가 먼저 들어오면 뒤따르는 짧은 프로세스가 오래 기다리는 호송효과(Convoy Effect)도 발생한다.

SJF: 짧은 CPU 버스트를 먼저 선택하는 경우

SJF(Shortest Job First)는 CPU 버스트 시간이 가장 짧은 프로세스를 우선 실행한다. 평균 대기시간을 최소화할 수 있어 배치 시스템에 적합하다. 다만 CPU 버스트 시간을 예측하기 어렵고, 긴 프로세스가 기아(Starvation) 상태에 놓일 가능성이 있다.

HRN: 기다린 시간까지 우선순위에 반영하기

HRN(Highest Response Ratio Next)은 SJF에서 발생할 수 있는 기아 문제를 완화한다. 우선순위는 다음 식으로 계산한다.

우선순위 = (대기시간 + 서비스시간) / 서비스시간

짧은 작업을 우선하면서도 대기시간이 길어진 작업의 우선순위를 높여 공평성과 효율성 사이의 균형을 맞춘다.

프로세스	서비스시간	대기시간	우선순위
P1	10	0	1.0
P2	3	5	2.67
P3	7	8	2.14

실행 순서: P2 → P3 → P1

실행 중인 작업을 중단할 수 있는 방식

Round Robin: 시간 할당량을 순환시키는 방식

⤢✕

Round Robin은 시간 할당량(Time Quantum)만큼 CPU를 사용한 뒤 다음 프로세스로 넘기는 순환 방식이다. 시간 할당량이 너무 크면 FCFS와 비슷해지고, 너무 작으면 문맥 교환 오버헤드가 늘어난다. 일반적인 시간 할당량은 10~100ms다.

공평성과 응답시간 보장에는 강점이 있지만, 평균 반환시간은 SJF보다 길 수 있다.

SRTF: 남은 실행시간이 가장 짧은 작업

SRTF(Shortest Remaining Time First)는 SJF를 선점 방식으로 확장한 알고리즘이다. 남은 실행시간이 가장 짧은 프로세스를 선택하므로 평균 대기시간을 최소화할 수 있다. 반면 선점이 잦으면 오버헤드가 커지고, 긴 프로세스는 기아 상태가 될 수 있다.

고정된 우선순위로 분리하는 다단계 큐

⤢✕

다단계 큐(Multilevel Queue)는 프로세스를 여러 큐로 나누고, 큐마다 독립적인 스케줄링 알고리즘을 적용한다. 큐 사이의 우선순위는 고정된다.

시스템 프로세스는 최우선 순위에 두고, 대화형 프로세스에는 높은 우선순위와 RR을 적용할 수 있다. 배치 프로세스는 낮은 우선순위에서 FCFS로 처리하는 구성이 가능하다.

실행 특성에 따라 이동하는 다단계 피드백 큐

⤢✕

다단계 피드백 큐(Multilevel Feedback Queue)에서는 프로세스가 큐 사이를 이동할 수 있다. 새 프로세스는 최상위 큐에서 시작하고, 할당량 안에 끝나지 않으면 하위 큐로 내려간다. I/O를 마친 뒤 복귀하면 상위 큐로 승격될 수 있다.

이 구조는 I/O 중심 프로세스에 우선권을 주고 CPU 중심 프로세스를 배치 큐로 이동시킨다. 워크로드 성격에 적응적으로 동작한다는 점이 특징이다.

오래 기다린 프로세스를 보호하는 에이징

우선순위가 낮은 프로세스는 계속 뒤로 밀리며 무한정 대기할 수 있다. 에이징(Aging)은 대기시간이 늘어날수록 우선순위를 점진적으로 높여 이 기아 문제를 완화하는 기법이다.

CPU 사용시간이 짧은 프로세스에는 높은 우선순위를 부여하고, 오래 기다린 프로세스의 우선순위를 높이며, 일정 시간마다 우선순위를 다시 계산하는 방식으로 구현할 수 있다.

초기 우선순위 = 기본값 - (CPU 버스트 시간 / 상수)
대기 중 우선순위 = 초기 우선순위 + (대기시간 / 상수)

프로세스	CPU시간	대기 0분	대기 10분	대기 20분
P1	10	50	60	70
P2	2	90	100	110
P3	5	70	80	90

FCFS에서 나타나는 호송효과

FCFS에서 CPU 사용시간이 긴 프로세스가 먼저 도착하면, 짧은 프로세스의 평균 대기시간이 크게 늘어난다. 이것이 호송효과이며 시스템 전체 성능을 떨어뜨릴 수 있다.

CPU 중심 프로세스가 먼저 도착한 시나리오에서는 다음과 같이 P2와 P3가 긴 대기시간을 갖는다.

프로세스	도착시간	버스트시간	대기시간
P1	0	24	0
P2	1	3	23
P3	2	3	25

평균 대기시간: (0 + 23 + 25) / 3 = 16ms

반대로 I/O 중심 프로세스가 먼저 도착한 경우는 다음과 같다.

프로세스	도착시간	버스트시간	대기시간
P2	0	3	0
P3	1	3	2
P1	2	24	4

평균 대기시간: (0 + 2 + 4) / 3 = 2ms

짧은 프로세스를 우선하는 SJF나 SRTF를 사용하거나, I/O 중심 프로세스에 높은 우선순위를 주는 다단계 큐를 적용해 영향을 줄일 수 있다. Round Robin도 시간 할당량을 통해 공평성을 보장하는 선택지다.

워크로드에 맞춰 알고리즘을 고르는 기준

배치 시스템은 처리량을 중시하고 응답시간의 중요도가 상대적으로 낮으므로 SJF 또는 HRN을 고려할 수 있다.

대화형 시스템은 빠른 응답시간이 필요하다. Round Robin이나 다단계 피드백 큐가 적합하다.

실시간 시스템은 우선순위 기반 선점 스케줄링을 사용하며, 데드라인 보장과 예측 가능성을 요구한다.

선택 과정에서는 워크로드가 CPU 중심인지 I/O 중심인지, 문맥 교환 비용이 어느 정도인지, 공평성과 효율성 사이에서 무엇을 우선할지, 실시간 요구사항을 충족할 수 있는지를 함께 검토해야 한다.