[운영체제] CPU Scheduling

CPU Scheduling

ready queue에 있는, 실행이 준비된 프로세스들 중에서 무엇을 먼저 실행할 것인지를 결정하는 것이 CPU Scheduling 입니다.

Basic Concepts

CPU utilization을 최대화하기 위해서는 Multi-Programming이 필수적입니다. 그리고 Process execution은 CPU burst 와 I/O burst 로 구성되어 있습니다.

• CPU burst : CPU 실행 시간입니다.
• I/O burst : I/O 실행 시간입니다.

위 그림은 대부분의 프로세스 사이클을 나타낸 사진입니다. CPU burst 뒤에는 I/O burst가 따라옵니다. 따라서 CPU burst를 잘 분배하는 것이 중요한 포인트입니다! 그런데, 대부분의 프로세스들은 CPU-burst가 짧습니다. 따라서 CPU Scheduler 가 등장하게 되었습니다.

CPU Scheduler

ready queue에 있는 프로세스 중 하나를 선택하여 CPU 코어에 할당해줍니다. 여기서는 싱글 프로세서라고 가정하여 설명하였습니다. 스케줄러가 선택하는 방식에는 여러가지가 있습니다. 선입선출, 우선순위 등등 많습니다.

CPU Scheduling 은 다음과 같은 상황에서 발생합니다.

• running > waiting state
• running > ready state
• waiting > ready state
• terminates

즉, running으로 가는 경우를 제외한 모든 상태 변경 시에 발생합니다.

참고)

• running -> wait 혹은 terminated는 프로세스가 자체적으로 할당된 CPU를 해제하는 과정입니다.
• running -> ready 혹은 wait -> ready 의 경우에는 강제적으로 할당된 CPU를 해제하는, 강제적으로 발생된 스케줄링입니다.

Preemptive & Non-Preemptive

running -> wait 혹은 terminated 의 경우를 Non-Preemptive (비선점형) 스케줄링 이라고 합니다. 나머지의 경우를 Preemptive 라고 합니다.

Non-Preemptive 스케줄링 하에서는, CPU에 프로세스가 할당되면 해당 프로세스는 terminated되거나 waiting state로 스스로 전환되기 전까지 CPU 제어권을 계속 가지고 있습니다. 따라서 현대의 운영체제 대부분(윈도우, 맥, 리눅스, 유닉스 등등)은 Preemptive (선점형) 스케줄링을 채택하여 사용하고 있습니다.

Preemptive Scheduling and Race Conditions

Preemptive Scheduling 은 커널의 의지로 상태가 강제적으로 바뀝니다. (커널에 있어도 강제로 주도권이 해제됩니다) 이로 인해 여러 프로세스 간 데이터가 공유될 때 Race Condition 을 발생시킵니다.

Dispatcher

CPU 스케줄러에 의해 선택된 프로세스에게 CPU 주도권을 주는 모듈입니다. 이는

• context-switching
• user-mode-switching
• 해당 프로그램을 다시 시작하기 위해 알맞은 위치로 명령어를 점프하는 과정

을 전부 포함한 과정입니다.

Dispatch-latency는 하나의 프로세스를 종료하고 다른 프로세스를 수행하기 까지의 시간을 모두 포함한 개념이기 때문에 context-switching 보다 더 광범위한 지연 시간입니다.

Scheduling Criteria

스케줄링 평가 기준입니다! 대부분의 스케줄러는 CPU utilization (CPU 이용률) 을 100%에 가깝게 하기 위해 노력합니다.

$utilization = \frac {execution - waiting} {execution} * 100$

이렇게 나타내며, execution = 시스템 기동시간 / waiting = CPU 유휴시간 입니다.

• Throughput : 단위 시간당 수행을 완료한 프로세스의 수 입니다.
• Turnaround time : ready + running 시간입니다. 즉, 실행을 완료할 때 까지의 시간입니다. ready queue에서 기다린 시간, CPU 실행 시간, I/O 실행 시간을 모두 포함하는 총 처리 시간 이라고 볼 수 있습니다.
• Waiting time : ready queue에서 대기한 시간입니다.
• Response time : 첫 응답이 오기까지 소요되는 총 시간입니다.

스케줄링 알고리즘은

• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time

을 추구해야 합니다. 그런데 여기서, CPU utilization 과 throughput 중에 무엇을 올리는지에 따라 turnaround time, waiting time, response time 이 달라집니다.