CPU 스케줄링 알고리즘

스케줄링 알고리즘

어떤 프로세스에 CPU 소유권을 제공할 것인지에 대한 알고리즘
CPU 이용률은 높게, 응답 시간은 짧게 하는 것이 목표.

종류

• 비선점형
  • FCFS
  • SJF
  • 우선순위
• 선점형
  • 라운드 로빈
  • SRF
  • 다단계 큐

비선점형 방식

프로세스가 스스로 CPU 소유권을 포기하는 방식.
강제로 프로세스를 종료하지 않음.

1. FCFS (First Come First Served)
   가장 먼저 온 것을 먼저 처리하는 방식.
   오래 걸리는 것이 먼저 들어오면 다른 작업이 큐에서 오래 대기할 수 있음.

2. SJF (Shortest Job First)
   실행 시간이 가장 짧은 프로세스 먼저 처리.
   평균 대기시간이 가장 짧지만 긴 시간이 걸리는 프로세스가 starvation을 겪을 수 있음.
   실제론 실행 시간 알 수 없기 때문에 과거 실행시간 토대로 추측.

3. 우선순위
   긴 시간이 걸리는 프로세스가 starvation 걸리는 점을 보완.
   오래된 작업일수록 우선순위를 높여 starvation을 보완함.

선점형 방식

사용 중인 프로세스를 알고리즘에 의해 중단시키고 다른 프로세스에 CPU 할당.

1. 라운드 로빈
   각 프로세스에 동일한 할당 시간을 주고 해당 시간안에 완료되지 않으면 다시 준비 큐로 들어감.
   할당 시간이 크면 FCFS, 짧으면 잦은 컨텍스트 스위칭 되므로 주의.

2. SRF
   SJF는 처리 중 더 짧은 작업이 들어와도 기존 작업 수행 후 짧은 작업 처리.
   SRF는 처리 중 더 짧은 작업이 들어오면 수행하던 프로세스 중지 후 짧은 작업 처리

3. 다단계 큐
   우선 순위에 따른 큐를 여러 개 준비해 큐마다 라운드 로빈, FCFS 등 다른 스케줄링 알고리즘 적용한 것.