CPU 스케줄링 알고리즘 (비선점형)

스케줄링 효율성 기준

• CPU 사용률: CPU가 가능한 한 쉬지 않고 사용되는가?
• 처리량 (Throughput): 단위 시간당 완료된 프로세스 수가 많은가?
• 대기 시간 최소화: 프로세스가 준비 큐에서 기다리는 시간이 짧은가?

비선점형 스케줄링 특징

• 프로세스가 CPU를 스스로 포기할 때까지 실행 → 강제 중단 없음
• 컨텍스트 스위칭 오버헤드가 적음

1. FCFS (First Come First Serve, 선입 선처리)

• 방식: 준비 큐에 먼저 도착한 순서대로 실행
• 장점: 구현이 단순, 공정한 처리
• 단점: 실행 시간이 긴 프로세스 때문에 뒤에 온 프로세스가 오래 기다리는 Convoy Effect 발생

2. SJF (Shortest Job First, 최단 작업 우선)

• 방식: 실행 시간이 가장 짧은 프로세스를 먼저 실행
• 장점: 평균 대기 시간을 최소화 → 이론적으로 가장 효율적
• 단점:
  • 실행 시간이 긴 프로세스가 계속 밀려 실행되지 못하는 Starvation(기아 현상) 발생 가능
  • 실제로는 프로세스의 실행 시간을 미리 알 수 없어, 과거 실행 시간 기록을 기반으로 예측

3. 우선순위 (Priority Scheduling)

• 방식: 프로세스마다 우선순위를 부여하고, 우선순위가 높은 프로세스부터 실행
• 우선순위 기준: 실행 시간, 메모리 요구량, 열린 파일 수, CPU 사용량 등
• 장점: 중요한 작업(예: 실시간 프로세스) 우선 처리 가능
• 단점: 낮은 우선순위의 프로세스가 무한정 실행되지 못하는 기아 현상 발생 가능
• 해결책: 에이징(Aging) 기법 → 오래 기다린 프로세스의 우선순위를 점차 높여 실행 기회 보장

 

알고리즘	방식	장점	단점
FCFS	도착 순서대로 실행	단순, 공정	긴 작업이 있으면 뒤에 프로세스가 오래 대기 (Convoy Effect)
SJF	실행 시간 짧은 순	평균 대기시간 최소화	실행 시간 긴 프로세스 기아 현상, 실행 시간 예측 어려움
우선순위	우선순위 높은 순	중요 작업 우선 처리	낮은 우선순위 프로세스 기아 현상 (→ 에이징으로 보완)