스케줄링_CPU Scheduling

Schedulers

스케줄러는 크게 3가지로 구분할 수 있습니다.

 

Long-term scheduler(Job scheduler)

메모리가 부족할 때, 디스크에 있는 프로그램 중 어떤 것을 메모리에 적재하고 ready queue에 넣을 것인지 선택하는 것을 의미합니다.

 

Medium-term scheduler(Swapper)

메모리가 부족할 때, 메모리에 있는 프로세스 중 어떤 것을 디스크로 내릴지 선택하는 것을 의미합니다.

 

Short-term scheduler(CPU scheduler)

Ready queue에서 대기하고 있는 프로세스 중 다음으로 CPU를 점유하여 실행될 프로세스를 선택하는 것을 의미합니다.

 

Long-term과 Mid-term은 메모리와 디스크 사이의 swap in, swap out을 다루는데,

사실 이러한 Scheduler는 운영체제의 후반에서 배우는 Page replacement로 대체되어 실제로 사용되지는 않습니다.

 

이번 포스팅과 다음 포스팅에서는 CPU를 점유할 다음 프로세스를 선택하는 Short-term scheduler에 대해 다룹니다.

 

 

 

프로세스 특성에 따른 Scheduler 선택

 

하나의 프로세스는 CPU burst와 I/O burst 상태를 번갈아 가며 수행합니다.  

 

• CPU burst: CPU 연산을 수행하는 running 상태
• I/O burst: waiting queue에서 I/O를 waiting 하는 상태

 

이때, CPU burst의 비율이 높은 프로세스를 CPU-bound process, I/O burst의 비율이 높은 프로세스를 I/O-bound process라고 합니다.  딥러닝, 시뮬레이션 프로그램과 같이 오랫동안의 연산이 중요한 프로세스는 주로 CPU-bound process로 분류되고, 사용자와의 상호작용이 중요한 대부분의 프로그램은 I/O-bound process 가 됩니다.

 

 

 

 

이 둘을 구분하는 이유는, 

프로세스의 유형에 따라 사용하는 CPU scheduling algorithm이 다르기 때문입니다. 일반적으로는 CPU-bound process보다 I/O-bound process를 먼저 스케줄링하고, 두 프로세스 간 다른 스케줄링 알고리즘을 사용합니다.

 

 

 

Dispatcher

한 프로세스가 동작을 하던 중 interrupt를 받거나 종료되면,

Scheduler는 다음으로 CPU를 점유할 프로세스를 선택합니다. 

 

Dispatcher는 선택된 프로세스를 동작시키기 위해 필요한 여러가지 작업들을 수행합니다.

CPU를 점유하고 있던 기존 프로세스의 실행 상태를 PCB에 저장하고, 새로 스케줄링된 프로세스의 실행 상태를 PCB로부터 불러옵니다. OS는 user mode로 전환된 후 스케줄링된 프로세스의 재시작 위치로 이동하여 해당 프로세스를 실행합니다. 

 

이 때, Dispatcher가 기존의 프로세스를 멈추고 새로운 프로세스를 시작할 때까지 걸리는 시간을 Dispatch latency라고 부릅니다.

 

 

 

Preemptive scheduling vs Non-preemptive scheduling

 

Preemptive scheduling(선점형 스케줄링)

한 프로세스가 CPU에서 동작하고 있는 와중, ready queue에 우선순위가 높은 프로세스가 들어오면 현재 프로세스를 강제로 멈추고 우선순위가 높은 프로세스를 스케줄링하는 방식입니다.

현존하는 대부분의 운영체제들은 Preemptive scheduling을 채택하고 있습니다.

 

 

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

Ready queue에 우선순위가 높은 프로세스가 들어온다 하더라도 현재 프로세스를 계속 수행시키는 방식입니다.

스케줄링은 프로세스가 I/O 요청을 받거나 종료될 때만 발생하며, 이외의 상황에는 강제로 CPU 사용권을 빼앗을 수 없습니다.

 

 

 

Scheduling criteria(Trade off)

Scheduling과 관련된 기준 지표들은 다음과 같습니다. 

 

높을 수록 좋은 기준

 

• CPU utlization(CPU 사용률)
• Throughput(단위 시간당 처리량)
• 해당 기준들은 Context switching의 주기가 길어질수록 향상됩니다.

 

낮을수록 좋은 기준

 

• Turnaround time(특정 프로세스가 실행되는 시간, 메모리에 적재되어 terminate 될 때까지의 시간)
• Waiting time(프로세스가 ready queue에서 기다리는 시간)
• Response time(사용자에게 보이는 반응 시간)
• 해당 기준들은 Context switching의 주기가 짧아질수록 향상됩니다.

 

 

 

Scheduling Goals & Non-Goals

 

Goals

스케줄링 할 때 프로세스의 일부가 소외되는 상황을 방지하고 모든 프로세스의 Fairness와 Balance를 보장해야 합니다. 이외에도 시스템의 목적에 따라 각각 다른 스케줄링 목표를 적용하고 있습니다.

 

• All system: Fairness, Balance
• Batch system: Throughput, Turnaround time, CPU utilization
• Interactive system: Response time, Waiting time, Proportionality
• Real-time system: Meeting deadlines, Predictability 

 

Non-Goals: Starvation

starvation이란, 프로세스 일부가 다른 프로세스들의 우선순위에 밀려 필요한 자원들을 사용하지 못하고 실행되지 않는 경우를 말합니다. 해당 문제를 해결하기 위한 방법으로 Aging이 있습니다. 오랫동안 실행되지 못한 프로세스의 우선순위를 높여 starvation이 발생하지 않도록 예방합니다.