CPU 스케줄링

 

 

CPU 스케줄링

  CPU 스케줄링이란,  어떤 프로세스에게 자원을 얼마나 할당하는지에 대한 정책을 만드는 것을 말한다. 스케줄링 대상은 Ready Queue에 있는 프로세스들이다. 

 

CPU 스케줄링 목표 

1. 공정성 : 모든 프로세스가 CPU를 공정하게 사용할 수 있도록 한다.
2. 효율성 : 시스템 자원의 사용률을 최대화하여 CPU가 항상 유용한 작업을 수행하도록 한다.
3. 응답 시간 : 사용자 상호작용 응용 프로그램에 대해 신속한 응답을 제공한다.
4. 처리량 : 주어진 시간 동안 최대한 많은 작업을 완료하도록 한다.
5. 대기 시간 최소화 : 프로세스가 CPU를 사용할 수 있도록 대기하는 시간을 최소화 한다. 

 

CPU 스케줄링 종류 

 - 선점형 스케줄링( preemptive scheduling )

- 프로세스가 실행 상태에서 준비 상태로 전환되거나 대기 상태에서 준비 상태로 전환될 때 사용된다.

• 모든 프로세스에게 CPU 사용 시간을 동일하게 부여할 수 있다.
• 빠른 응답시간을 요하는 대화식 시분할 시스템에 적합하다.
• 긴급한 프로세서를 제어할 수 있다.

 라운드로빈 스케줄링(Round Robin)
  여러 프로세스들에 우선 순위를 메기지 않고, 순서대로 순환하여 균일하게 시간단위로 CPU를 할당하는 방식의 스케줄링 알고리즘이다.
 문맥 전환의 오버헤드가 크다는 단점이 있으나 응답시간이 짧아지는 장점 덕분에 실시간 시스템에서 유리하다.

 

우선순위 큐 스케줄링(Priority Queue) 
  우선순위 큐 스케줄링은 각각의 프로세스들이 우선 순위를 가지고 가장 높은 우선 순위를 가진 프로세스에게 CPU 권한을 할당하는 방식이다. 우선순위가 같은 프로세스가 있다면 선입 선처리 스케줄링 한다. 우선순위 큐 스케줄링은 선점형과 비선점형이 될 수 있다. 선점형은 새로 도착한 프로세스의 우선 순위가 현재 실행 중인 프로세스의 우선순위보다 높다면 CPU를 선점하게 되며 비선점형에 경우, 준비 완료 큐 머리 부분에 새로운 프로세스를 할당 시켜놓는다. 

 

다단계 큐 스케줄링 (Multi-level Queue Scheduling)
  커널 내의 준비 큐를 여러 개의 큐로 분리하여 각 큐 마다 우선순위를 부여하는 스케줄링 알고리즘이다. 

 

다단계 피드백 큐 스케줄링( Multi-level Feedback Queue, MLFQ)
 여러 개의 우선 순위 큐를 사용하면서 프로세스가 큐 사이를 이동할 수 있는 스케줄링 방식을 말한다. 우선순위 기반이기 때문에 중요한 큐는 빠르게 처리할 수 있으며 모든 작업이 상위 큐에서 시작하므로 각 작업이 공평하게 처리될 기회를 가질 수 있다. 반면에, 구현이 복잡하고 과다하게 문맥을 전환하는 스케줄링이기 때문에 오버헤드가 발생할 수 있다. 

 

---

 - 비선점형 스케줄링( Nonpreemptive Scheduling )

- 프로세스가 종료되거나 프로세스가 실행 상태에서 대기 상태로 전환될 때 사용된다. 

• 선점형 스케줄링보다 스케줄러 호출 빈도가 낮고 문맥 교환에 의한 오버 헤드가 적다. 
• 일괄 처리 시스템에 적합하다.
• CPU 사용 시간이 긴 하나의 프로세스가 CPU 사용 시간이 짧은 여러 프로세스를 오랫동안 대기시 시킬 수 있어서 처리율이 떨어질 수 있다는 단점이 있다. (Convoy Effect)

  FCFS( First-Come-First-Served) 
운영체제와 네트워크가 큐에 추가되는 추가되는 순서대로 작업, 프로세스 및 요청을 효율적이고 자동적으로 수행하도록 돕는 비선점 기반 스케줄링 알고리즘이다. 

 

최단 작업 우선 SJF(Shortest Job First)
  실행시간이 가장 짧은 프로세스를 선택하여 다음 실행을 수행하는 스케줄링 알고리즘이다. 비선점형이며 평균 대기시간을 최소화할 수 있다. 

 

 

데드라인 스케줄러(Deadline Scheduler) 
  작업 요청에 대한 서비스 시간을 보장하는 알고리즘이다. 데드라인 스케줄러는 데드라인 큐와 각 작업에 대한 이익을 수치화하여 이를 정렬한 정렬된 큐를 가지고 있는데, 데드라인 큐는 데드라인 에 따라정렬된다. 데드라인 큐에서 첫 번째 것을 골라서 나머지 작업들에 대해 데드라인이 겹치지 않는지 검사하며 겹치면 넘어가고 겹치지 않으면 선택하여 수행한다.