CPU 스케줄링 이해하기 (1): 기본 개념부터 FCFS, SJF, Priority, RR 알고리즘까지

운영체제(OS)의 핵심 기능 중 하나인 CPU 스케줄링에 대해 알아보는 시간을 갖겠습니다. 마치 식당 주방장이 여러 주문을 효율적으로 처리하듯, 운영체제는 한정된 CPU 자원을 여러 프로세스에게 효과적으로 배분해야 합니다. 이 글은 KOCW 반효경 교수님의 운영체제 강의를 바탕으로 CPU 스케줄링의 기본 개념과 대표적인 알고리즘들을 정리한 내용입니다.

1. 왜 CPU 스케줄링이 필요할까요? (CPU and I/O Bursts)

컴퓨터에서 실행되는 프로그램(프로세스)은 일반적으로 CPU 사용(CPU Burst)과 입출력(I/O) 대기(I/O Burst)를 반복하며 실행됩니다.

• CPU Burst: 프로세스가 CPU를 직접 사용하여 연산을 수행하는 구간
• I/O Burst: 프로세스가 입출력 장치(디스크, 네트워크 등)의 작업 완료를 기다리는 구간

프로그램의 종류에 따라 이 Burst의 패턴이 다릅니다.

• I/O-bound job: I/O Burst가 길고 CPU Burst가 짧은 작업 (예: 파일 복사, 사용자 입력 대기 등)
• CPU-bound job: CPU Burst가 길고 I/O Burst가 짧은 작업 (예: 복잡한 계산, 영상 인코딩 등)

실제 시스템에는 이 두 종류의 작업들이 섞여 실행됩니다. 만약 CPU 스케줄링이 없다면, CPU-bound job 하나가 CPU를 독점하여 다른 I/O-bound job들(특히 사용자와 상호작용하는 Interactive job)의 응답 시간(Response time)이 매우 길어질 수 있습니다. 또한, CPU는 계속 일하는데 I/O 장치는 노는 비효율적인 상황이 발생할 수도 있습니다.

 

따라서, CPU 스케줄링은 다음과 같은 목표를 가집니다.

1. 응답성 향상: 대화형 작업(Interactive Job)에 빠른 응답 제공
2. 자원 효율성 증대: CPU, I/O 장치 등 시스템 자원을 균형 있고 효율적으로 사용

[확인 질문]
프로그램 실행 과정에서 CPU 버스트와 I/O 버스트가 번갈아 나타나는 이유는 무엇이며, 이 때문에 CPU 스케줄링이 왜 필요할까요?

2. 누가 스케줄링을 담당할까요? (CPU Scheduler & Dispatcher)

CPU 스케줄링 과정에는 두 가지 주요 주체가 있습니다.

• CPU 스케줄러 (Scheduler): 실행 준비가 된 프로세스들(Ready Queue에 있는 프로세스들) 중에서 다음에 어떤 프로세스에게 CPU를 할당할지 결정하는 역할. 알고리즘에 따라 이 선택 기준이 달라집니다.
• 디스패처 (Dispatcher): 스케줄러가 선택한 프로세스에게 실제로 CPU 제어권을 넘겨주는 모듈. 이 과정에는 현재 실행 중이던 프로세스의 상태를 저장하고, 선택된 프로세스의 상태를 복원하는 문맥 교환(Context Switch) 작업이 포함됩니다.

간단히 말해, 스케줄러는 '누구를 실행할지' 결정하고, 디스패처는 그 결정에 따라 '실제로 실행시키는' 역할을 합니다.

 

[확인 질문]
CPU 스케줄러와 디스패처의 주요 역할은 각각 무엇인가요?

3. 무엇을 기준으로 스케줄링 성능을 평가할까요? (Scheduling Criteria)

좋은 CPU 스케줄링 알고리즘이란 무엇일까요? 어떤 기준으로 성능을 평가할 수 있을까요? 이는 시스템 관점과 사용자(프로세스) 관점에서 나눠볼 수 있습니다. (마치 중국집 주방장과 손님의 입장이 다른 것처럼요!)

 

[시스템 (CPU) 입장]

• CPU 이용률 (CPU utilization): 전체 시간 중 CPU가 실제로 작업을 처리하며 바쁘게 움직인 시간의 비율. 높을수록 좋습니다. (주방장이 쉬지 않고 요리하는 비율)
• 처리량 (Throughput): 단위 시간 동안 완료된 프로세스의 개수. 높을수록 좋습니다. (시간당 완성된 요리 개수)

 

[사용자 (프로세스) 입장]

• 총 소요 시간 (Turnaround time): 프로세스가 시스템에 제출된 시점부터 완료될 때까지 걸린 총 시간 (대기 시간 + 실행 시간 + I/O 시간). 짧을수록 좋습니다. (손님이 식당에 들어와서 식사를 마치고 나갈 때까지 걸린 시간)
• 대기 시간 (Waiting time): 프로세스가 CPU를 사용하기 위해 준비 큐(Ready Queue)에서 순수하게 기다린 시간의 합. 짧을수록 좋습니다. (손님이 코스 음식을 기다린 시간. 하나 먹고 기다리고 하나 먹고 기다리고)
  • 선점형 스케줄링에서는 CPU를 중간에 빼앗길 수 있으므로 대기 시간이 더 길어질 수 있습니다.
• 응답 시간 (Response time): 프로세스가 작업을 요청한 시점부터 첫 번째 응답(결과 출력이 아닌, 실행 시작)이 나올 때까지 걸린 시간. 특히 대화형 시스템(Time-sharing environment)에서 중요하며, 짧을수록 좋습니다. (손님이 주문하고 첫 번째 음식이 나올 때까지 걸린 시간)

어떤 기준을 가장 중요하게 생각하는지에 따라 선택하는 스케줄링 알고리즘이 달라질 수 있습니다.

 

[확인 질문]
CPU 스케줄링의 성능을 평가하는 다양한 척도(기준)들이 있습니다. 시스템(CPU) 관점과 사용자(프로그램) 관점에서 중요하게 생각하는 척도는 각각 무엇이며, 왜 그런 차이가 발생할까요?

4. 기본적인 스케줄링 알고리즘들

이제 몇 가지 대표적인 CPU 스케줄링 알고리즘을 살펴보겠습니다.

4.1 FCFS (First-Come First-Served)

이름 그대로, 먼저 온 순서대로 CPU를 할당하는 가장 간단한 방식입니다.

• 특징: 비선점형(Non-preemptive) - 일단 CPU를 할당받으면 해당 CPU Burst가 끝날 때까지 계속 사용합니다.
• 장점: 구현이 매우 간단합니다.
• 단점:
  • Convoy Effect (호위 효과): CPU Burst Time이 매우 긴 프로세스가 먼저 도착하면, 뒤따르는 짧은 프로세스들이 하염없이 기다려야 하는 문제가 발생합니다. 이는 평균 대기 시간을 급격히 증가시킵니다.
  • 도착 순서에 따른 성능 편차: 어떤 순서로 프로세스가 도착하는지에 따라 평균 대기 시간이 크게 달라집니다.

예시:
프로세스 P1(Burst=24), P2(Burst=3), P3(Burst=3)가 거의 동시에 도착했을 때 (P1->P2->P3 순)

• Waiting Time: P1=0, P2=24, P3=27
• Average Waiting Time: (0 + 24 + 27) / 3 = 17

만약 P2->P3->P1 순으로 도착했다면?

• Waiting Time: P2=0, P3=3, P1=6
• Average Waiting Time: (0 + 3 + 6) / 3 = 3
  -> 도착 순서에 따라 성능 차이가 매우 큽니다!

[확인 질문]
FCFS 스케줄링 방식의 가장 큰 장점과 단점은 무엇이며, 특히 'Convoy Effect'는 어떤 상황에서 발생하나요?

4.2 SJF (Shortest-Job-First)

FCFS의 Convoy Effect 문제를 보면서 'CPU를 짧게 쓸 프로세스를 먼저 처리하면 좋지 않을까?'라는 아이디어에서 출발한 방식입니다.

• 핵심 아이디어: 다음번 예상 CPU Burst Time이 가장 짧은 프로세스에게 CPU를 먼저 할당합니다.
• 두 가지 방식:
  • 비선점형 (Non-preemptive): 일단 CPU를 잡으면 이번 CPU Burst가 끝날 때까지 계속 사용합니다. 새로운 더 짧은 작업이 도착해도 CPU를 빼앗기지 않습니다.
  • 선점형 (Preemptive): 현재 실행 중인 프로세스의 남은 CPU Burst Time보다 더 짧은 CPU Burst Time을 가진 새로운 프로세스가 도착하면, 현재 프로세스는 CPU를 빼앗기고 Ready Queue로 돌아갑니다. 이를 SRTF (Shortest-Remaining-Time-First) 라고도 부릅니다.
• 장점: 평균 대기 시간(Average Waiting Time)을 최소화하는 최적(Optimal) 알고리즘입니다. (특히 선점형 방식)
• 단점:
  • 기아 현상 (Starvation): CPU Burst Time이 긴 프로세스는 계속해서 더 짧은 프로세스들에게 밀려 영원히 CPU를 할당받지 못할 수 있습니다.
  • CPU Burst Time 예측의 어려움: 다음번 CPU Burst Time을 미리 정확히 알 수 없습니다. 프로그램 실행은 입력 데이터, 분기 조건 등에 따라 달라지기 때문입니다.
    • 해결 시도: 과거의 CPU Burst Time 기록을 이용해 다음번 시간을 추정(Estimate)하는 방법을 사용합니다. 대표적으로 Exponential Averaging 기법이 있습니다. (과거의 실제 값과 예측 값에 가중치를 두어 계산하며, 최근 값에 더 높은 가중치를 부여하는 방식)

예시 (표는 원본 노트 참조):
Average Waiting Time 비교:

• Non-preemptive SJF: 4
• Preemptive SJF (SRTF): 3 (이것이 최적 값)

[확인 질문]
SJF 스케줄링은 평균 대기 시간을 최소화하는 최적의 알고리즘으로 알려져 있습니다. 하지만 실제 시스템에서 SJF를 완벽하게 구현하기 어려운 두 가지 주요 문제점은 무엇인가요?

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

각 프로세스마다 우선순위(Priority)를 부여하고, 가장 높은 우선순위를 가진 프로세스에게 CPU를 할당하는 방식입니다. (일반적으로 정수값이 작을수록 높은 우선순위)

• 방식: 선점형(Preemptive)과 비선점형(Non-preemptive) 모두 가능합니다.
  • 선점형: 더 높은 우선순위의 프로세스가 도착하면 현재 프로세스는 CPU를 빼앗깁니다.
  • 비선점형: 일단 CPU를 잡으면 해당 Burst가 끝날 때까지 사용합니다.
• SJF와의 관계: SJF는 우선순위 스케줄링의 특별한 경우로 볼 수 있습니다. (우선순위 = 다음번 예상 CPU Burst Time)
• 문제점:
  • 기아 현상 (Starvation): 낮은 우선순위를 가진 프로세스는 높은 우선순위 프로세스들에게 계속 밀려 실행되지 못할 수 있습니다. (SJF의 문제점과 동일)
• 해결책:
  • 노화 (Aging): 오랫동안 대기한 프로세스의 우선순위를 점진적으로 높여주는 방식입니다. 언젠가는 높은 우선순위를 갖게 되어 실행될 기회를 얻습니다.

[확인 질문]
우선순위 스케줄링에서 발생할 수 있는 '기아(Starvation)' 문제를 해결하기 위한 '노화(Aging)' 기법은 어떻게 동작하나요?

4.4 라운드 로빈 (Round Robin, RR)

시분할 시스템(Time-sharing systems)을 위해 고안된 스케줄링 방식으로, 응답 시간을 줄이는 데 효과적입니다.

• 핵심 아이디어: 각 프로세스는 동일한 크기의 할당 시간(Time Quantum 또는 Time Slice)만큼만 CPU를 사용합니다. (보통 10-100ms)
• 동작 방식:
  1. 프로세스가 CPU를 할당받아 실행됩니다.
  2. 할당된 시간(Time Quantum)이 만료되기 전에 프로세스가 완료되거나 I/O 요청을 하면 스스로 CPU를 놓습니다.
  3. 만약 할당된 시간이 만료되면, 해당 프로세스는 선점(Preempted) 당하고 Ready Queue의 맨 뒤로 가서 다음 차례를 기다립니다.
• 특징:
  • 공정성: n개의 프로세스가 Ready Queue에 있고 할당 시간이 q이면, 각 프로세스는 최대 (n-1) * q 시간 안에 최소 q 시간만큼의 CPU를 얻을 수 있습니다. (굶어 죽는 프로세스가 없음)
  • 성능:
    • Time Quantum(q)이 크면: FCFS와 유사하게 동작합니다.
    • Time Quantum(q)이 작으면: 프로세스 간의 문맥 교환(Context Switch)이 너무 잦아져 오버헤드가 커집니다.
    • SJF와의 비교: 평균 총 소요 시간(Average Turnaround Time)은 SJF보다 길 수 있지만, 평균 응답 시간(Average Response Time)은 훨씬 짧습니다. (짧은 작업을 오래 기다리지 않게 함)
• 고려사항: 만약 CPU Burst Time이 모두 100으로 동일한 여러 작업이 있고 Time Quantum을 1로 설정하면, 각 작업이 완료되기까지 번갈아 가며 실행되므로 총 소요 시간(Turnaround Time)은 매우 길어질 수 있습니다.

[확인 질문]
Round Robin 스케줄링에서 '타임 퀀텀(Time Quantum)'의 크기는 시스템 성능에 어떤 영향을 미치나요? 타임 퀀텀이 매우 크거나 매우 작을 때 각각 어떤 현상이 발생할 수 있을까요?

---

여기까지 CPU 스케줄링의 기본적인 필요성, 관련 용어, 성능 척도, 그리고 대표적인 알고리즘(FCFS, SJF, Priority, RR)에 대해 알아보았습니다. 각 알고리즘은 장단점을 가지며, 시스템의 목표(처리량 극대화, 응답 시간 최소화 등)에 따라 적합한 알고리즘을 선택하는 것이 중요합니다. 다음 포스팅에서는 더 발전된 스케줄링 기법들에 대해 다룰 예정입니다.