한양과기고 에듀테크 수업도구 대시보드

CPU는 하나, 실행할 프로그램은 여럿 — 누구부터?

컴퓨터에는 수십~수백 개의 프로세스가 "나 좀 실행시켜줘"라고 줄 서 있지만, CPU 코어는 몇 개뿐이다. 스케줄러는 이 대기열에서 다음에 어떤 프로세스에게 CPU를 줄지 매 순간 결정한다. 같은 작업들이라도 순서를 어떻게 정하느냐에 따라 평균 대기 시간이 크게 달라진다. 아래 시뮬레이터에서 프로세스 표를 바꿔가며 4가지 대표 알고리즘의 간트 차트를 직접 비교해 보자.

1 먼저 알아야 할 4가지 시간

스케줄링을 이야기할 때 항상 등장하는 값들이다. 시뮬레이터 결과 표에도 그대로 나온다.

도착 시간 arrival time

프로세스가 준비 큐(ready queue)에 들어와 실행을 기다리기 시작한 시각.

실행 시간 burst time

이 프로세스가 CPU를 실제로 써야 하는 총 시간. (중간에 끊겨도 합계는 동일)

대기 시간 waiting time

준비 큐에서 CPU를 못 받고 그냥 기다린 시간. = 반환 시간 − 실행 시간.

반환 시간 turnaround time

도착부터 완전히 끝날 때까지 걸린 전체 시간. = 완료 시각 − 도착 시간.

2 간트 차트 시뮬레이터

프로세스	도착 시간	실행 시간

타임 퀀텀

알고리즘을 고르고 실행을 눌러보세요.

같은 프로세스 목록이라도 FCFS → SJF로 바꿔보면 평균 대기 시간이 확 줄어드는 걸 볼 수 있다. 대신 SJF/SRTF는 긴 작업이 계속 뒤로 밀리는 기아(starvation) 위험이 있다.

3 선점형 vs 비선점형

스케줄링 방식은 크게 두 갈래로 나뉜다.

비선점형 non-preemptive

한번 CPU를 잡으면 스스로 끝내거나 I/O로 넘어갈 때까지 뺏기지 않는다. 구현이 단순하지만, 긴 작업이 앞에 있으면 뒤가 다 밀린다(호위 효과). FCFS·비선점 SJF가 여기 해당.

선점형 preemptive

더 급한 프로세스가 오면 실행 중인 것을 강제로 멈추고 준비 큐로 돌려보낸다. 반응성이 좋아 대화형 시스템에 적합하지만, 문맥 교환(context switch) 비용이 든다. SRTF·RR이 여기 해당.

4 4가지 알고리즘 한눈에 비교

알고리즘	고르는 기준	장점	단점
FCFS	준비 큐에 먼저 들어온 순서 (FIFO)	완전 공정, 기아 없음, 구현 최소	긴 작업 뒤 짧은 작업이 오래 대기(호위 효과), 평균 대기 시간 큼
SJF (비선점)	남은 프로세스 중 실행 시간이 가장 짧은 것	평균 대기 시간이 이론상 최소	실행 시간을 미리 알아야 함(예측 필요), 긴 작업 기아
SRTF (선점 SJF)	매 순간 남은 시간이 가장 짧은 것	SJF보다도 평균 대기 시간이 짧음	잦은 선점 → 문맥 교환 비용, 기아 더 심함
Round Robin	일정 시간(퀀텀)씩 돌아가며 공평하게	응답 시간이 짧고 균등, 기아 없음, 대화형에 적합	퀀텀이 크면 FCFS처럼, 작으면 문맥 교환만 늘어남

# 비선점 SJF의 핵심 — 매번 "가장 짧은 것"을 고른다 def sjf(procs): time, order = 0, [] ready = [] while procs or ready: # 지금까지 도착한 프로세스를 준비 큐로 이동 ready += [p for p in procs if p.arrival <= time] procs = [p for p in procs if p.arrival > time] if not ready: time += 1; continue ready.sort(key=lambda p: p.burst) # ← 짧은 작업 우선 p = ready.pop(0) order.append((p.pid, time, time + p.burst)) time += p.burst # 끝까지 실행(비선점) return order

5 자주 나오는 질문

💡 실제 리눅스·윈도우는 어떤 알고리즘을 쓰나?

순수한 한 가지가 아니라 여러 개를 섞은 다단계 큐를 쓴다. 리눅스는 오랫동안 CFS(Completely Fair Scheduler)를 썼고 최근엔 EEVDF로 바뀌었는데, 아이디어는 "각 프로세스가 받아야 할 CPU 몫을 계산해 가장 밀린 프로세스에게 준다"는 것이다. 대화형 프로세스(키보드·마우스 반응)에 우선순위를 높여주고, 오래 CPU를 독점한 프로세스는 낮춰 기아를 막는다. RR의 "공평함"과 SJF의 "짧은 것 우대"를 절충한 셈이다.

💡 타임 퀀텀은 어떻게 정하나?

보통 10~100밀리초. 너무 크면 RR이 사실상 FCFS가 되어 반응성이 나빠지고, 너무 작으면 실행 시간보다 문맥 교환(레지스터 저장·복원, 캐시 무효화)에 쓰는 시간이 더 커진다. 경험칙은 "대부분의 CPU 버스트가 한 퀀텀 안에 끝나도록" 잡는 것이다.

💡 SJF가 최적이라면서 왜 안 쓰나?

프로세스의 실행 시간을 미리 알 수 없기 때문이다. 그래서 실무에서는 과거 버스트 길이를 지수 이동 평균으로 예측해서 근사한다. 또 SJF는 짧은 작업이 계속 들어오면 긴 작업이 영원히 실행되지 못하는 기아가 생긴다. 이를 막으려면 오래 기다린 프로세스의 우선순위를 점점 올려주는 에이징(aging)을 함께 써야 한다.

💡 응답 시간과 반환 시간은 뭐가 다른가?

응답 시간은 도착 후 처음으로 CPU를 받기까지의 시간이고, 반환 시간은 도착부터 완전히 끝날 때까지의 시간이다. 편집기·게임처럼 즉각 반응이 중요한 프로그램은 응답 시간을, 배치 작업(대량 계산·렌더링)은 반환 시간과 처리량(throughput)을 중요하게 본다. RR은 응답 시간이 짧고, SJF는 평균 반환 시간이 짧다.