[CS] CPU 스케줄링 기법

CPU 스케줄링 알고리즘은 여러 프로세스가 CPU를 공유할 때 어떤 프로세스에게 CPU를 우선 배정할지를 결정하는 방식이다. 각 방식은 시스템 목표(응답 시간, 대기 시간, 공정성 등)에 따라 장단점이 존재한다.

---

1. FCFS (First Come First Served)

FCFS는 많이 들어본 FIFO와 비슷한 개념이다.

개념:

• 도착 순서대로 프로세스에게 CPU를 할당
• 큐에 먼저 들어온 순서대로 실행한다 (FIFO 방식)

특징:

• 구현이 가장 간단하다
• 비선점형 방식 (Non-preemptive)

단점:

• Convoy Effect(호송 효과) 발생 가능 → CPU를 오래 점유하는 프로세스가 먼저 오면, 뒤따르는 짧은 프로세스가 오래 기다려야 함

---

2. SJF (Shortest Job First)

개념:

• 실행 시간이 가장 짧은 프로세스부터 실행

특징:

• 비선점형 또는 선점형 둘 다 가능
• 평균 대기 시간을 최소화할 수 있음 (이론적으로 최적)

단점:

• 다음 프로세스의 실행 시간을 정확히 알아야 함 (현실에서는 어려움)
• 기아 현상(Starvation) 가능 → 긴 작업은 계속 밀릴 수 있음

---

3. SRTF (Shortest Remaining Time First)

SJF의 선점형(Preemptive) 버전이다.

개념:

• 새 프로세스가 도착했을 때, 남은 실행 시간이 더 짧으면 현재 작업을 중단하고 교체

특징:

• 응답 시간 짧음
• 실시간 시스템에 적합할 수 있음

단점:

• 문맥 교환이 빈번하게 발생
• 역시 정확한 실행 시간 예측 필요
• 기아 현상 존재

---

4. Round Robin (RR)

개념: 

• 각 프로세스에 동일한 시간 할당량(타임 퀀텀) 을 주고, 순환적으로 실행

특징:

• 선점형 스케줄링
• 공정성 보장: 모든 프로세스가 CPU를 골고루 사용

단점:

• 타임 퀀텀 설정이 너무 크면 FCFS와 유사, 너무 작으면 문맥 전환 오버헤드

---

5. Multilevel Queue Scheduling

개념:

• 프로세스를 우선순위 또는 특성에 따라 여러 개의 큐로 분류
  예:
  • 시스템 프로세스
  • 대화형 프로세스
  • 배치 작업 등

특징:

• 각 큐는 자체의 스케줄링 알고리즘 사용 가능 (예: RR, FCFS)
• 큐 간에도 우선순위 또는 비율 기반으로 CPU 분배

단점:

• 고정된 큐에 프로세스가 할당되면 이동 불가 (기아 현상 가능)
• 복잡한 관리 필요

보완책: Multilevel Feedback Queue
→ 프로세스가 실행 상태에 따라 큐를 오갈 수 있음 (좀 더 유연하고 공정한 방식)