CPU 스케줄링

CPU 스케쥴링

여러 프로세스들 중에서 어떤 것을 먼저 처리할지 순서를 정하는 것

Ready Queue에 준비된 프로세스들 중 어떤 것을 CPU에게 할당할지 정해준다.

필요한 이유

CPU는 한 번에 하나의 프로세스만을 처리할 수 있다.

그렇기에 최대한 효율적으로 프로세스를 스케쥴링 할 필요가 있다.

궁극적인 목적은 CPU 이용률을 극대화 함으로서 동일 시간 내에 많은 업무를 처리할 수 있도록 하는 것이다.

선점/비선점 스케쥴링

선점 스케줄링

• 특정 프로세스가 CPU를 점유하고 있을 때 해당 프로세스의 작업이 완료될 때까지 다른 프로세스가 CPU를 점유할 수 없음
• 최신 운영체제 대부분은 선점 스케줄링 방식을 사용

비선점 스케줄링

• 특정 프로세스가 CPU를 점유하고 있더라도 알고리즘 기준에 따라 우선순위가 높다면 CPU를 점유 할 수 있음

스케쥴링 알고리즘

비선점 스케쥴링

• FCFS(First Come First Service)
  • Ready Queue에 도착한 순서대로 CPU에 할당하는 방식
  • 작업 완료 시간 예측 용이
• SJF(Shortest Job First)
  • CPU 처리 시간이 짧은 순서대로 CPU에 할당하는 방식
  • 평균 대기 시간이 가장 짧은 방식
  • CPU 처리 시간이 길다면 새로운 프로세스들에 의해 무한정 대기해야 하는 상황 발생
• HRN (Highest Response Ratio Next)
  • SJF에서 발생하는 무한정한 대기 상태 (aka.기아상태) 를 해결하기 위해 고안된 방식
  • 처리 시간 + 대기 시간까지 고려하여 결정

선점 스케쥴링

• SRT (Shortest Remaining Time)
  • 비선점 스케쥴링의 SJF 방식을 선점 스케줄링 방식으로 변경한 기법
• 라운드 로빈 (Round-Robin)
  • FCFS 방식에서 선점 스케줄링 방식과 Time Quantum 개념을 추가한 방식
  • 프로세스마다 CPU를 연속적으로 사용할 수 있는 시간에 제한을 둠
  • 시간 제한을 꽉 채운다면 해당 프로세스를 Ready Queue의 맨뒤로 보냄
• 다단계 큐(Multi-Level Queue)
  • 프로세스를 특정 기준에 따라 여러 그룹으로 나눠 그룹별 Queue로 관리하는 방식

알고리즘 평가 기준

• 프로세서 이용률
  • 시간당 CPU를 사용한 시간의 비율
• 처리율
  • 시간당 처리한 작업의 비율
• 반환시간 또는 소요시간
  • CPU burst time
• 대기시간
  • 대기열에 들어와 CPU를 할당 받기까지 기다린 시간
• 반응시간
  • 대기열에서 처음으로 CPU를 얻을 때까지 걸린 시간