운영체제(OS)의 CPU 스케줄링 알고리즘들의 특징 비교

1. 용어 정의 (표의 행 설명)

• 선택 함수 (Selection Function): 준비 큐(Ready Queue)에 있는 프로세스 중 누구를 다음에 실행할 것인가를 결정하는 수식입니다.
  • w (waiting time): 기다린 시간
  • s (service time): 실행에 필요한 총 시간
  • e (execution time): 현재까지 실행한 시간
• 결정 모드 (Decision Mode):
  • 비선점 (Non-preemptive): 한 프로세스가 CPU를 잡으면 끝날 때까지 뺏지 않습니다.
  • 선점 (Preemptive): 우선순위가 높은 다른 프로세스가 오거나 시간이 다 되면 CPU를 강제로 뺏습니다.
• 처리량 (Throughput): 단위 시간당 작업을 얼마나 많이 끝내는가 (높을수록 좋음).

---

2. 알고리즘별 상세 설명

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

• 방식: 먼저 온 놈이 먼저 처리됩니다. (선착순)
• 선택 함수: \max[w] (기다린 시간 w가 가장 긴 프로세스 선택)
• 특징:
  • 비선점: 한 번 잡으면 끝날 때까지 안 놓아줍니다.
  • 단순하지만, 긴 작업이 앞에 있으면 뒤에 짧은 작업들이 오래 기다리는 **호위 효과(Convoy Effect)**가 발생할 수 있습니다.

(2) 라운드-로빈 (Round-Robin)

• 방식: 돌아가면서 조금씩 공평하게 실행합니다.
• 선택 함수: 상수 (특정 기준 없이 순서대로 돕니다)
• 특징:
  • 선점 모드: 정해진 시간 할당량(Time Slice)이 끝나면 강제로 다음 타자에게 넘깁니다.
  • 주의점: 시간 할당량을 너무 작게 잡으면 프로세스를 바꾸는 비용(Context Switching)이 커져서 실제 처리량이 아주 낮아질 수 있습니다.

(3) SPN (Shortest Process Next) (=SJF)

• 방식: 실행 시간이 가장 짧은 프로세스를 먼저 시킵니다.
• 선택 함수: \min[s] (총 실행 시간 s가 가장 작은 것 선택)
• 특징:
  • 비선점: 실행 도중 뺏기지 않습니다.
  • 짧은 것부터 빨리 해치우므로 단위 시간당 완료되는 프로세스 수(처리량)가 높음입니다.
  • 단점: 긴 프로세스는 영원히 실행되지 못할 수도 있음(기아 현상).

(4) SRT (Shortest Remaining Time)

• 방식: SPN의 선점형(Preemptive) 버전입니다. 남은 시간이 가장 짧은 것을 먼저 합니다.
• 선택 함수: \min[s - e] (총 시간 s - 이미 한 시간 e = 남은 시간이 최소인 것)
• 특징:
  • 선점 모드: 새로운 프로세스가 도착했을 때, 걔가 나보다 더 금방 끝날 것 같으면 비켜줍니다.
  • SPN처럼 처리량이 높음입니다.

(5) HRRN (Highest Response Ratio Next)

• 방식: SPN의 단점(긴 작업 소외)을 보완하기 위해 **'오래 기다린 시간'**도 점수에 쳐줍니다.
• 선택 함수: \frac{w + s}{s} (응답률 Response Ratio)
  • 이 식은 1 + \frac{w}{s} 와 같습니다. 즉, 실행 시간(s)이 짧을수록 유리하지만, 대기 시간(w)이 길어져도 우선순위가 높아집니다(에이징 기법).
• 특징:
  • 비선점: 중간에 뺏지 않습니다.
  • 처리량도 높음을 유지하면서 기아 현상을 방지합니다.

(6) 피드백 (Feedback)

• 방식: 여러 단계의 큐를 두어 우선순위를 조절합니다. (보통 오래 걸리는 작업은 아래 단계 큐로 강등됨)
• 특징:
  • 선점 모드: 시간 할당량이 끝나면 뺏깁니다.
  • 이전의 정보 없이도 스케줄링이 가능하여 범용 OS에서 많이 쓰입니다.