CPU 스케줄링 FCFS·SJF·SRT·라운드 로빈 비교와 평균 대기시간 계산, HRN 우선순위까지 (정보처리기사)

CPU 하나를 여러 프로세스가 나눠 쓰는 순서를 정하는 일이 CPU 스케줄링이다. 정보처리기사 필기와 실기에서 모두 빠지지 않고 나오는데, 특히 도착 시간과 실행 시간을 주고 평균 대기시간을 구하는 계산 문제가 단골이다. 정의를 정확히 알고 간트 차트를 그리는 순서만 익히면 점수를 확실히 가져갈 수 있다.

스케줄링은 대기시간·반환시간·응답시간을 줄이는 선택이다

대기시간은 준비 큐에서 기다린 시간의 합이고, 반환시간은 도착부터 종료까지의 시간이다. 대기시간은 반환시간에서 실행 시간을 뺀 값과 같다. 응답시간은 처음 CPU를 받기까지 걸린 시간이다. 스케줄링은 비선점과 선점으로 나뉘는데, 비선점은 한 번 CPU를 받으면 끝날 때까지 쓰고, 선점은 더 급한 프로세스가 오면 CPU를 빼앗을 수 있다.

알고리즘마다 공정성과 효율의 균형이 다르다

알고리즘	방식	원리	장점	한계
FCFS	비선점	도착 순서대로 실행	단순하고 공정	긴 작업 뒤에 짧은 작업이 오래 기다리는 호위 효과
SJF	비선점	실행 시간이 가장 짧은 작업 우선	평균 대기시간이 짧음	긴 작업의 기아, 실행 시간 예측 필요
SRT	선점	남은 시간이 가장 짧은 작업 우선	평균 대기시간이 매우 짧음	문맥 교환이 잦고 기아 가능
HRN	비선점	(대기시간 + 서비스시간) / 서비스시간이 큰 작업 우선	SJF의 기아를 완화	계산이 필요
라운드 로빈	선점	시간 할당량(q)만큼 돌아가며 실행	응답성이 좋음	q가 너무 크면 FCFS, 너무 작으면 문맥 교환 과다
우선순위	선점·비선점	우선순위가 높은 작업 먼저	중요 작업 우선	기아, 에이징으로 보완

예시: P1(0,8), P2(1,4), P3(2,9), P4(3,5)의 평균 대기시간은 방식마다 다르다

괄호는 (도착 시간, 실행 시간)이다. FCFS는 P1(0~8), P2(8~12), P3(12~21), P4(21~26) 순이라 대기시간이 0, 7, 10, 18이고 평균은 8.75이다. 비선점 SJF는 P1이 끝나는 8 시점에 대기 중인 P2(4), P3(9), P4(5) 중 가장 짧은 P2, 그다음 P4, 마지막으로 P3를 실행해 대기시간이 0, 7, 15, 9, 평균 7.75이다. 선점형 SRT는 1 시점에 P2가 오면 남은 시간 7인 P1보다 짧은 P2로 넘어가는 식이라 평균이 6.5로 가장 짧다. 시간 할당량 4의 라운드 로빈은 새로 도착한 프로세스를 먼저 큐에 넣는다는 관례를 따르면 평균 11.75이다. 계산은 파이썬으로 검산했다.

HRN도 같은 상황에서 계산해 보자. P1이 끝나는 8 시점의 우선순위는 P2가 (7+4)/4 = 2.75, P3가 (6+9)/9 ≈ 1.67, P4가 (5+5)/5 = 2.0이므로 P2가 먼저 실행된다. 오래 기다릴수록 값이 커져 긴 작업도 결국 차례가 온다는 것이 핵심이다.

답안에는 선점 여부와 평균값 계산 과정을 함께 적는다

서술형은 평가 지표 정의 → 선점·비선점 구분 → 알고리즘 비교 → 기아와 에이징 순으로 쓴다. 계산 문제에서는 라운드 로빈의 큐 순서 관례가 문제마다 다를 수 있으니 문제에 주어진 조건을 따른다. 실제 운영체제는 다단계 피드백 큐처럼 여러 방식을 섞어 대화형 작업의 응답성과 처리량을 함께 맞춘다.

실전 팁으로, 계산 전에 도착 시간 순서로 표를 먼저 정리하고 간트 차트를 그린 뒤 종료 시각만 읽어 대기시간을 구한다. 선점형에서는 새 프로세스가 도착하는 시각마다 남은 시간을 다시 비교한다. 평균 반환시간을 묻는 경우에는 대기시간에 각자의 실행 시간을 더한 값을 쓰면 되므로, FCFS 예시에서 반환시간은 8, 11, 19, 23이고 평균은 15.25이다.

시험 직전 한 줄 요약

평균 대기시간은 SRT와 SJF가 짧고 라운드 로빈은 응답성이 좋으며, 대기시간은 종료 시각에서 도착 시각과 실행 시간을 뺀 값이다.

이 글은 학습용 정리이며 실제 시험 문항과 다를 수 있다. 출제 기준은 큐넷·KISA·한국데이터산업진흥원 등 공식 공지를 확인하라. 그림은 설명용 예시 데이터로 그린 개념도이며 실측 데이터가 아니다.