CPU 스케줄링

taeyul_de·2025년 2월 25일

CS 스터디

CPU 스케줄링이란?

CPU 스케줄링은 운영체제가 CPU를 여러 프로세스에 어떻게 할당할지 결정하는 과정이다.

• 다수의 프로세스가 동시에 실행될 때, CPU는 한 번에 하나의 프로세스만 실행할 수 있기 때문에 효율적 할당이 중요.

• 스케줄링 알고리즘을 통해 응답 시간, 처리량, 공정성 등을 최적화한다.

CPU 스케줄링의 목적

✅ CPU 사용률 최대화: CPU가 가능한 한 놀지 않도록 유지

✅ 처리량(Throughput) 증가: 단위 시간당 완료된 작업 수 증가

✅ 대기 시간 최소화: 프로세스가 대기 큐에서 기다리는 시간 감소

✅ 응답 시간 개선: 사용자 요청에 대한 빠른 응답 제공

✅ 공정성 보장: 모든 프로세스에 공평한 CPU 할당

스케줄링이 필요한 이유

• 멀티태스킹: 여러 프로그램을 동시에 실행할 때, CPU는 프로세스 간 빠르게 전환해야 함

• 리소스 최적화: CPU 자원을 효율적으로 사용하여 시스템 성능 향상

• 사용자 경험 개선: 빠른 프로그램 반응으로 사용자 만족도 증가

CPU 스케줄링의 기본 개념

프로세스 상태 (Process States)

Ready: CPU 할당을 기다림
Running: CPU를 할당받아 실행 중
Waiting: I/O 작업 등으로 대기 중
Terminated: 실행 완료

스케줄러(Scheduler) 는 Ready 상태의 프로세스 중 하나를 선택해 CPU 할당

CPU 스케줄링 알고리즘 종류

1️⃣ FCFS (First-Come, First-Served)

• 가장 먼저 도착한 프로세스부터 처리
• 비선점형(Non-Preemptive) 방식

✅ 장점: 구현이 쉽고 공정함
⚠️ 단점: 평균 대기 시간이 길어질 수 있음 (Convoy Effect 발생)

📝 예시:

프로세스 도착 순서: P1(도착0, 실행4), P2(도착1, 실행3), P3(도착2, 실행2)
스케줄링 순서: P1 → P2 → P3

2️⃣ SJF (Shortest Job First)

• 실행 시간이 가장 짧은 프로세스부터 처리
• 비선점형/선점형(Preemptive) 둘 다 가능

✅ 장점: 평균 대기 시간 최소화
⚠️ 단점: 긴 작업이 계속 대기할 수 있음 (Starvation 문제)

3️⃣ Round Robin (RR)

• 각 프로세스에 동일한 시간 할당량(Quantum) 부여
• 선점형 방식 → 시간 초과 시 다음 프로세스로 전환

✅ 장점: 공정성 보장, 반응 시간 개선
⚠️ 단점: Quantum 설정이 너무 짧으면 과도한 컨텍스트 스위치 발생

📝 비유:

놀이공원에서 회전목마에 한 번씩 돌아가며 타는 것과 유사

4️⃣ Priority Scheduling

• 우선순위가 높은 프로세스부터 실행
• 선점형/비선점형 모두 가능

✅ 장점: 중요한 작업 우선 처리 가능
⚠️ 단점: 낮은 우선순위 프로세스가 무한 대기 (Starvation)

💡 해결책: 우선순위에 노화(Aging) 기법 적용 (시간 경과 시 우선순위 상승)

5️⃣ Multilevel Queue Scheduling

• 프로세스를 여러 큐로 분류 (예: 시스템 프로세스, 사용자 프로세스)
• 각 큐마다 다른 스케줄링 알고리즘 적용

✅ 장점: 프로세스 특성에 맞는 스케줄링 가능
⚠️ 단점: 큐 간 이동이 제한적일 수 있음

📊 스케줄링 성능 지표

지표	설명
CPU 사용률	CPU가 사용 중인 시간 비율
처리량(Throughput)	단위 시간당 완료된 프로세스 수
대기 시간(Waiting Time)	프로세스가 Ready 상태에서 대기한 총 시간
응답 시간(Response Time)	요청 → 첫 응답까지 걸린 시간
턴어라운드 시간(Turnaround Time)	작업 시작 → 완료까지 걸린 시간

💻 Round Robin 간단 코드 예시 (JavaScript)

function roundRobin(processes, quantum) {
  let time = 0;
  const queue = [...processes];

  while (queue.length) {
    const process = queue.shift();
    if (process.burstTime <= quantum) {
      time += process.burstTime;
      console.log(`${process.name} 완료 at time ${time}`);
    } else {
      time += quantum;
      process.burstTime -= quantum;
      queue.push(process); // 남은 작업 재삽입
    }
  }
}

const processes = [
  { name: 'P1', burstTime: 5 },
  { name: 'P2', burstTime: 3 },
  { name: 'P3', burstTime: 1 },
];

roundRobin(processes, 2);

✅ 코드 설명:

• 각 프로세스에 시간 할당량(Quantum)을 주고 실행

• 시간이 남으면 다시 큐에 추가하여 공정성 유지

🧭 스케줄링 알고리즘 비교

알고리즘	선점 여부	특징	장점	단점
FCFS	비선점형	도착 순서대로 실행	구현 쉬움, 공정함	긴 평균 대기 시간
SJF	둘 다 가능	짧은 작업 우선 처리	평균 대기 시간 최소화	긴 작업 지연 (Starvation)
Round Robin	선점형	일정 시간 할당, 순환 실행	공정성, 응답 시간 개선	과도한 컨텍스트 스위치 가능
Priority	둘 다 가능	높은 우선순위 먼저 실행	중요한 작업 우선 처리	낮은 우선순위 작업 무시 위험
Multilevel	상황에 따라	프로세스 분류 및 다중 큐 사용	특성별 최적화 가능	구현 복잡