[OS5] CPU Scheduling

이제 여러 프로세스를 동시에 실행할 때 CPU 에서 어떤 프로세스를 우선적으로 실행할 지에 대해서 정하는 스케쥴링에 대해서 알아보자.

CPU

CPU burst & I/O burst

프로세스는 크게 두 가지로 나뉠 수 있다. 프로세싱 중에 CPU 의 사용, 연산이 많은 CPU-bound process와 I/O 의 사용이 많아 사용자와 상호작용이 많은 I/O-bound process 가 있다.

기본적으로 I/O-bound process 는 I/O 처리를 기다리는 시간이 길다. 따라서 CPU 입장에서는 기다리는 시간에 다른 프로세스를 처리하는 것이 더 효율적이라고 할 수 있다.

Dispatcher

여러 프로세스 중 하나를 골라 CPU 에 실제 올리는 작업을 Dispatch 라 한다. 실행 중인 프로세스를 바꾸는 작업이기 때문에 Context Switch 라 하기도 한다.

Preemptive

• Preemptive
  • 스케쥴러가 하던 일에 인터럽트를 걸고 다른 일을 하도록 강제할 수 있다
• Non-Preemptive
  • 어떤 일을 수행하는 중에는 다른 일을 하도록 강제할 수 없고 해당 일이 끝날 때까지 기다려야한다

Scheduling Criteria

스케쥴링 시 고민해야할 기준이다.

• CPU utilization : CPU의 효율이다. 당연히 100%가 되도록 노력해야하며 할 일이 존재하는 동안에는 CPU가 쉬어서는 안된다.
• Throughput : 단위 시간 당 처리 양이다. 최대화해야한다.
• Turnaround time : 실행부터 끝나는 시간이다. 최소화해야한다.
• Waiting time : 프로세스가 Ready 상태에서 기다리는 시간이다. 최소화해야한다.
• Response time : 사용자가 작업을 요청하고 눈으로 확인하는 데까지 걸리는 시간이다. progress bar 같은 개념이다. 최소화해야한다.

Scheduling

스케쥴링의 목표는 모든 프로세스가 fair 하게 실행되는 것이며 시스템의 모든 장치들을 효율적으로 사용하는 것이다.

동시에 한 프로세스가 ready 상태에서 계속해서 기다리는 Starvation 을 주의해야한다.

FCFS, First Come First Served

• 먼저 도착한 프로세스가 먼저 실행된다
• 모든 프로세스는 순서대로 실행되기 때문에 Starvation 이 없다
• 어느 프로세스 던 가장 공평하게 실행된다
• 프로세스가 중간에 멈추지 않기 때문에 non-preemptive 이다
• 문제는 프로세스의 도착 순서에 따라 Waiting time 이 길어진다. (Convoy effect)

SJF, Shortest job First

• average waiting time 최소화하기 위한 방법이다
• job 의 길이가 가장 짧은 프로세스부터 실행한다
• non-preemptive

SRTF, Shortest Remaining Time First

• SJF 의 preemptive 한 버전이다.
• 프로세스가 도착할 때마다 남은 job의 길이가 가장 짧은 프로세스를 찾아 먼저 실행한다
• 실행되고 있는 프로세스보다 더 짧은 길이의 job 을 가진 프로세스가 도착하면 실행 중인 프로세스를 중단시킨다
• 짧은 프로세스만 계속해서 도착한다면 길이가 긴 프로세스는 Starvation 에 걸릴 수 있다

Priority

• 프로세스의 우선순위에 따라 처리하는 방법이다
  • SJF 도 짧은 길이가 우선순위를 결정한다고 볼 수 있다
• SRTF 와 마찬가지로 우선순위가 높은 프로세스만 들어오면 우선순우가 낮은 프로세스는 Starvation 에 걸릴 수 있다
  • 해결 방법으로 Aging이 있다. 어느 프로세스가 실행 순서가 밀릴 수록 우선순위를 높이는 방법이다

RR, Round Robin

• 타임 퀀텀을 주고 돌아가면서 프로세스를 스케쥴링하는 방법
• Waiting time 을 줄일 수 있다.
• 지금 현존하는 운영체제가 사용하는 방법이 Priority + Round Robin 이다
  • 모든 프로세스는 우선순위를 가지고 같은 우선순위 큐에서는 RR로 진행한다
• 타임 퀀텀이 줄어들 수록 공평하지만 프로세스간 Context Switching 이 빈번해져 오버헤드가 커진다

Multi-Level Queue

• Queue 를 여러 개 두고 각 Queue 마다 다른 알고리즘을 가져가는 것
• 각 프로세스의 성질에 따라 즉각적 상호작용이 필요하면 RR로 Waiting time을 줄이고 Batch 이면 즉각적인 확인이 필요없으므로 FCFS 로 설정하는 방법
• 하지만 어떤 프로세스가 어떤 큐에 들어갈 것인지 파악하고 우선순위를 정하기 어렵다

Multi-Level Feedback Queue

• 가장 먼저 프로세스에게 8이라는 타임 퀀텀을 준다
• 8 수행 후 프로세스의 job 이 남아있으면 다음에는 16이라는 타임퀀텀을 준다
• 16 수행 후 프로세스의 job 이 남아있으면 FCFS 로 처리한다
• Interative 한 프로세스는 높은 우선순위를 가질 수 있다

Real-Time Scheduling

Static

• 우선순위가 프로세스별로 고정되어 바뀌지 않는다
• Rate-Monotonic algorithm : Rate = 실행 주기. 기본적으로 자주 실행되면 우선순위가 높고 가끔 실행되면 우선순위가 낮다.

Dynamic

• 우선순위가 바뀐다
• EDF (Earliest Deadline First) : 데드라인이 가장 가까운 프로세스가 높은 우선순위를 가진다.
  • 계속해서 데드라인을 확인해야하므로 스케쥴링 오버헤드가 너무 커서 실제로는 사용하지 않는다.