🚀CPU 스케줄링 알고리즘

CPU 스케줄링이란?

• 준비큐에서 대기 프로세스를 선택하고 CPU를 할당하는 작업
• 디스패처에 의해 선택된 CPU가 프로세스에 할당된다.

선점 vs 비선점 기법

• 선점 : CPU를 프로세스로 부터 뺏을 수 있는 경우
• 비선점: 프로세스가 자발적으로 CPU 제어를 포기하는 경우
• 거의 모든 최신 운영체제가 선점적이다.

스케줄링 알고리즘의 평가기준

1. CPU 이용률
2. 처리량
3. 총 처리시간
4. 대기 시간
5. 응답 시간

스케줄링 알고리즘

1. 선입 선처리 스케줄링(FCFS)
   + 가장 간단한 스케줄링 알고리즘이다.
   - 매우 긴 프로세스를 기다리게 할 수 있다.
   
   
2. 최단 작업 우선 스케줄링(SJF)
   + 최적이며 평균 대기시간이 가장 짧다.
   - 다음 CPU 버스트의 길이를 예측하기 어려워 구현하는게 어렵다.
3. 라운드 로빈 스케줄링(RR)
   : CPU를 시간 할당량 동안 프로세스에 할당한다. 프로세스가 시간 할당량이 만료되기 전에 CPU를 포기하지 않으면 프로세스가 선점되고다른 프로세스가 시간 할당량 동안 실행되도록 스케줄 된다.
   
   
4. 우선순위 스케줄링
   : 각 프로세스에 우선순위를 배정하고 높은 순서대로 CPU 가 할당된다. 우선순위가 같은 프로세스는 FCFS순서 또는 RR 을 사용하여 스케줄 할 수 있다.
   
   
5. 다단계 큐 스케줄링
   : 프로세스를 우언순위에 따라 여러개의 큐로 분할하고 스케줄러는 우선순위가 가장 높은 큐에서 프로세스를 실행한다. 큐마다 다른 스케줄링 알고리즘이 사용될 수 있다.
   
   
6. 다단계 피드백 큐 스케줄링
   : 다단계 큐 스케줄링과 비슷하며 한가지 다른점은 다단계 피드백 큐 스케줄링은 큐 사이에 프로세스가 이주될 수 있다는 점이다.
   
   
7. 연성 실시간 스케줄링
   : 비실시간 작업보다 실시간 작업에 우선순위를 둔다. 경성 실시간 스케줄링은 실시간 작업에 대한 타이밍 보장을 제공한다.
   
   
8. Rate-monotonic 실시간 스케줄링
   : 선점과 함께 정적 우선순위 정책을 사용하여 주기적 작업을 스케줄 한다.
   
   
9. EDF(early-deadline-first) 스케줄링
   : 마감시한에 따라 우선순위를 지정한다. 마감시간이 빠를수록 우선순위가 높다.
   
   
10. 비례 공유 스케줄
    : 모든 응용 프로그램이 몫 T를 공유한다. 응용 프로그램에 N 몫 만큼의 시간이 배정되면 총 프로세서 시간의 N/T가 보장된다.

스케줄링 기법 실제 사용예

1. Linux : 완벽한 공정 스케줄러(CFS)
   : 각 작업에 일정 비율의 CPU 처리 시간을 할당한다. 비율은 각 작업과 관련된 가상 실행시간 값을 기준으로 한다.
2. Windows : 선점적인 32단계 우선순위 기법
3. Solaris : 전역 우선순위에 매핑된 6개의 고유한 스케줄링 클래스를 식별한다.
   : CPU를 많이 사용하는 스레드에는 일반적으로 낮은 우선순위(및 더 긴 시간 할당량)
   : I/O 중심 스레드에는 일반적으로 높은 우선순위(더 짧은 시간 할당량)가 할당된다.