CPU 스케줄링 1

OS가 CPU를 스케줄링하는 과정에 대해 배운 내용을 정리해보았다.

CPU를 스케줄링 하는 것은 OS가 하는 가장 중요한 일 중 하나이다. 이를 통해 여러 프로세스가 동시에 실행되는 것 처럼 보여줄 수 있고, 프로세스 실행 우선순위에 따라서 먼저 실행되어야 하는 프로세스를 먼저 실행할 수 있다. 이 스케줄링은 자주 해야 하는 작업이므로 빨라야 한다.

우선, 스케줄링은 크게 Non-preemptive 스케줄링과 Preemptive 스케줄링으로 나눌 수 있다.

1. Non-preemptive 스케줄링
   • Non-preemptive 스케줄링은 CPU에서 돌아가고 있는 프로세스를 쫓아낼 수 없는 스케줄링 방식이다. 따라서 각 프로세스가 CPU를 점유하다가 yield()를 통해 CPU를 양보해야 한다. 하지만 CPU를 독점하는 악성 프로세스를 만들게 되면 CPU가 그 일만 하게 된다. 따라서 서로 믿을 수 있는 환경에서만 사용할 수 있다.
   • 이 때는 스케줄러가 간단해진다는 장점이 있다. Timer interrupt도 필요 없기 때문에 관련 하드웨어도 있을 필요가 없다.
2. Preemptive 스케줄링
   • Preemptive 스케줄링은 돌아가는 프로세스를 쫓아낼 수 있는 방식이다. 스케줄러가 프로세스를 바꾸는 context switch를 강제할 수 있다. 따라서 한 프로세스에 의해 CPU를 독점당할 걱정은 없다.
   • 하지만 중요한 일을 하는 프로세스도 쫓겨날 수 있다는 단점이 있다.

용어 정리

각각의 스케줄러에 대해 알아보기 전에 사용하게될 용어를 정리하고 넘어가자.

Workload

CPU가 해야할 job과 그에 대한 정보이다. 예를 들면 CPU에 도착하는 arrival time, CPU에서 돌아가야 하는 시간인 run time 등이 있다.

Scheduler

어떤 job을 실행할 지에 대한 로직이다.

Metric

스케줄링의 퀄리티를 평가하기 위한 지표이다. turnaround time, response time, fairness 등이 있다.

Turnaround time

어떤 job이 CPU에 도착하고 나서 실행이 완료될 때 까지의 시간을 나타낸다.

Starvation

어떤 job이 우선순위에서 계속 밀려 실행되지 못하는 것을 말한다. 이를 지양해야 한다.

\( T_{turnaround} = T_{completion} - T_{arrival} \)

Response time

어떤 job이 CPU에 도착하고 나서 처음으로 실행될 때 까지의 시간이다.

\( T_{response} = T_{firstrun} - T_{arrival} \)

기본적인 스케줄링

스케줄러에 대해 알아보기 전에, 5개의 가정을 하고 시작한다. 그리고 가정을 하나씩 지워가면서 그에 맞는 스케줄링에 대해서 생각해 볼 것이다.

그 가정은 다음과 같다.

1. 모든 job을 수행하는데 드는 시간은 모두 같다.
2. 모든 job은 한 번에 같이 주어진다.
3. 한 번 시작하면, 그 job이 끝날 때 까지 실행한다.
4. job은 I/O 없이 CPU만 사용한다.
5. 모든 job이 얼마나 실행되어야 할 지를 알고 시작한다.

먼저 Turnaround time을 metric으로 하여 각 스케줄링을 비교해보자.

1. FIFO (First In, First Out)

선착순. 스케줄링 할 때 항상 나오는 개념 중 하나는 선착순과 랜덤이다. 먼저 오는 일을 먼저 하는 것으로, Non-preemptive 스케줄링의 예 중 하나이다. 순서대로 모두 실행하는 스케줄링이므로 starvation이 발생하지 않는다. 하지만 엄청 긴 job뒤에 짧은 job들이 많이 들어오게 된다면, 짧은 job들도 긴 job에 의해 늦게 실행되므로 \( T_{turnaround} \)가 커지게 된다. (Convoy effect)

2. SJF (Shortest Job First)

실제로는 모든 job은 수행하는데 걸리는 시간이 다르다. 따라서 1번 가정을 지워보자. SJF 스케줄링은 그 job들 사이에서 가장 짧은 job을 우선 실행하는 스케줄링 방식이다. 따라서 이 방식도 Non-preemptive 스케줄링이다. 각 job이 동시에 주어지고, job의 소요시간을 아는 Non-preemptive 스케줄링에서 이 방식은 optimal임을 증명할 수 있다.

하지만 job이 동시에 오는 것이 아니면 optimal이 아니고, 수행하는데 시간이 오래걸리는 job은 실행되지 않는 starvation이 발생할 수 있다.

3. STCF (Shortest Time-to-Completion First)

이번에는 2. job이 동시에 주어진다는 가정과, 3. job을 한번 시작하면 끝까지 실행해야 한다는 가정을 지우고 생각하자. SJF를 preemptive한 버전으로 구현할 수 있다. 어느 순간 실행하고 있는 job보다 일찍 끝나는 job이 들어왔을 때, 그 job을 실행한다. 이렇게 실행하면 preemption을 통해 Turnaround time을 줄일 수 있다.

4. RR (Round Robin)

Run queue를 순환 FIFO queue로 만들고, 각 job은 한 time slice(scheduling quantum)동안 실행된다. time slice는 한 프로세스를 잠깐 실행할 시간을 나타낸다. 우리는 timer interrupt의 주기를 한 tick이라고 하는데, context switch는 timer interrupt에 맞추어 일어나므로 time slice는 tick의 배수가 된다. 이 time slice가 너무 짧으면 context switch를 하는데 생기는 overhead가 너무 커지고, 너무 길면 반응성이 낮아진다. 모든 job을 돌아가면서 실행하므로 preemptive한 스케줄링이고, starvation도 생기지 않는다. 또한 RR은 새로운 metric인 response time도 줄일 수 있다.

$$ T_{response} = T_{firstrun} - T_{arrival} $$

5. Incorporation I/O

이번에는 4번 가정인 I/O없이 CPU만 사용하는 job만 주어진다는 가정을 지워낸다. CPU에 주어지는 job들은 I/O를 동반하는 경우가 많다. 따라서 이 느린 작업을 하는 동안 CPU를 사용할 수 있어야 한다. 따라서 어떤 job이 I/O를 하려고 할 때, 그 시간 동안 다른 job을 실행하는 방식을 활용할 수 있다.

General CPU Scheduler

이렇게 5개의 스케줄러에 대해서 알아보았다. 스케줄러를 구현할 때 우리가 고려해야할 요소는 다음과 같다.

• Turnaround time 최적화
• interactive jobs에 대해 response time 최소화

또한, 실제로는 처음 5개의 가정들 중 모든 job의 실행시간을 미리 알고있다는 5번 가정도 지운 상태의 스케줄러를 구현해야 한다. 그렇다면 스케줄러를 어떻게 구현해야 할까? 오늘날 컴퓨터는 Priority Scheduling이라는 스케줄링을 사용한다. 이는 다음 글인 CPU 스케줄링 2에서 살펴보자.