[OS] 6 - CPU Scheduling (1)

1. Concept

CPU 스케줄링은 CPU의 효율을 최대화하기 위해 사용되는 개념이다.

CPU를 끊임없이 사용해야 CPU의 효율이 오르기에 메모리에 여러개의 프로세스를 동시에 올려 필요할 때 마다 CPU에 할당을 하게 된다. 이때 어떤 프로세스 결정하는 것이 CPU 스케줄링이다.

 

2. CPU Scheduler

CPU scheduler는 CPU 스케줄링 중 어떤 프로세스를 골라서 CPU에 할당을 할 것인지를 정하는 요소이다.

스케줄러는 다음와 같은 상황에서 동작을 한다.

1. 프로세스가 Running 상태에서 Waiting 상태로 바뀔 떄 (ex. I/O 요청)
2. 프로세스가 Running 상태에서 Ready 상태로 바뀔 떄 (ex. 인터럽트)
3. 프로세스가 Waiting 상태에서 Ready 상태로 바뀔 떄 (ex. I/O 완료)
4. 프로세스 종료 시

1, 4 번은 NonPreemptive 방식 (자발적 반납)으로 동작하고 2, 3번은 Preemptive 방식(비자발적 방식)으로 동작한다.

3. Nonpreemptive vs Preemptive

위에서 말한 것 처럼 이 둘의 차이는 프로세스의 CPU 반납이 자발적이냐 강제적이냐의 차이이다.

 

Nonpreemptive 스케줄링은 프로세스가 할당 받은 CPU를 자발적으로 반납하기 전까지 계속 사용한다.

Preemptive 스케줄링은 프로세스가 CPU를 사용하고 있더라도 다른 프로세스가 CPU를 뺏어서 할당할 수 있는 스케줄링 방식이다.

4. Dispatcher

디스패처 모듈은 CPU 스케줄러에 의해 선택된 프로세스에 대한 CPU 제어를 제공한다.

제어의 종류는 다음과 같다.

1. Context Switching
2. User mode Switching
3. 유저 프로그램 내에서 프로그램 재시작을 위한 적절한 주소로의 변경 

* Dispatch latency - 디스패처가 한 프로세스를 중지하고 다른 프로세스를 시작하는 데 걸리는 시간

5. 스케줄링 기준

다양한 기준을 통해 어떤 프로세스를 할당할 것인가를 조정한다.

다양한 기준이 있는데 기준의 우선 순위에 따라 다양한 스케줄링 방식이 있다.

 

종류는 다음과 같다.

• CPU utilization (CPU 효율)
  • 얼마나 바쁘게 CPU를 유지할 수 있는 지
• Throughput
  • Time Limit (CPU를 사용하는데 정해진 시간) 내에 얼마나 많은 작업을 끝낼 수 있는 지
• TurnAround Time
  • 프로세스의 시작부터 끝날 때 까지의 소요 시간
• Waiting Time
  • 프로세스가 Waiting Queue에 존재하는 시간 (대기 시간)
• Response Time
  • 요청이 제출된 시점부터 첫 응답이 나올 때까지 걸리는 시간

 

최적화된 스케줄링을 위해서는

1. CPU utilization 과 Throughput 을 높여야 하고, TurnAroundTime, Waiting Time, Response Time을 줄여야한다.
2. 각 수치의 평균을 이루는 것 보단 최대값, 최소값을 최적화하는 것이 좋다.
3. 반응 시간(Response Time)의 분산을 최소화하는 것이 좋다 (interactive system 일때)

 

이러한 기준등을 이용한 다양한 알고리즘들이 있다.

• FCFS (First-Come, First-Served) scheduling
• SJF (Short-Job-First) scheduling
• Priority scheduling
• RR (Round-Robin) scheduling
• MultiLevel Queue scheduling
• MultiLevel Feedback Queue scheduling

다음 글에서 해당 알고리즘들에 대해 살펴보고자 한다.