Cpu 스케줄링 1 (FIFO ~ I/O aware STCF)

서론

한개의 코어는 한번에 하나의 프로세스만 돌릴 수 있기때문에 언제 어떤 프로세스를 돌릴 지 정확히 파악해야합니다. 이 목적을 달성하기 위해서 필요한 것이 바로 CPU scheduling입니다.

이번 글에서는 가장 간단한 CPU scheduling부터 시작해서 I/O aware STCF이라는 스케줄링 기법까지 다루려고 합니다. 그 후 다음 글에서 최근에 쓰이는 더 복잡한 스케줄링 기법에 대해 다루겠습니다.

용어 정리

우선 글에 등장하는 몇 가지 용어들을 정리하고 넘어가겠습니다.

Non preemptive scheduling

Non preemptive scheduling은 현재 CPU에서 돌아가고 있는 프로세스를 쫓아내거나 밀어내고 다른 프로세스가 들어갈 수 없는 스케줄링 기법을 의미합니다. CPU에서 다른 프로세스가 돌아가기 위해서는 오로지 현재 돌아가고 있는 프로세스가 yield()라는 시스템 콜로 잠깐 멈추고 다른 프로세스에게 CPU를 양보하는 방법밖엥 업습니다.

그래서 만약 악성 프로세스가 무제한으로 CPU를 잡고 돌아가도 쫓아낼 방법이 없습니다. 그러므로 일반적인 환경보다는 Trusted, embedded system에서 사용 가능합니다. 통제된 환경이라 악성 프로세스가 자리잡을 일이 없는 환경이죠.

Preemptive scheduling

Preemptive scheduling은 앞서 말씀드린 non preemptive 방식이랑 반대겠죠. 일반적인 OS들이 사용하는 방식입니다. Timer interrupt를 통해서 일정 시간이 지나면 CPU에 있는 프로세스를 교체하고, 강제로 다른 프로세스를 돌립니다.

Workload

현재 CPU에서 돌아가는 Job의 특성입니다. arrival time, run time 등을 의미합니다.

Metric

스케줄러 평가의 지표로 생각하시면 됩니다. 앞으로 여러 스케줄링 기법을 다루면서 Metric으로 turnaround time, response time, fairness 등이 쓰일텐데 이것들을 기준으로 그 스케줄링 방식을 평가하는 것입니다.

Starvation

말 그대로 어떤 프로세스가 장기간 대기만 하다가 돌아가지못하고 굶어죽는 것을 의미합니다.

Workload Assumptions

본격적으로 스케줄러에 대해 공부하기 전 몇 가지 job에 대한 가정들을 하겠습니다.

이 가정들은 본 글의 진행 방식과 관련이 있는데, 아래의 5가지 가정을 통해 Job들이 처리하기 매우 쉬운 형태로 존재한다고 가정한 후, 그에 기반한 간단한 스케줄러를 제시할 것입니다.

그 후 현실에 맞게 가정들을 하나씩 제거하며 그에 맞는 더 나은 스케줄링 방식을 제시하는 식으로 글이 진행될 것 입니다.

1. Each job runs for the same amount of time
2. All jobs arrive at the same time
3. Once started, each job runs to completion
4. All jobs only use the CPU (no I/O)
5. The run time of each job is known

이렇게 5개의 가정을 세워놓으면 현실에 비해 CPU 스케줄링 시 고려할 것이 훨씬 적어집니다. 모든 job들이 한번에 도착하고, 똑같은 시간을 도니까요.

그리고 Metric으로 Turnaround time이라는 것을 적용하겠습니다. Turnaround time이란 요청이 도착한 시간부터 끝나기까지 얼마나 걸렸느냐를 의미합니다.

$$ T_{\text{turnaround}} = T_{\text{completion}} - T_{\text{arrival}} $$

FIFO

위의 다섯 가정들이 성립한다면 스케줄링 방식으로 단순하게 FIFO를 적용해도 아무 문제가 없을 것입니다. 모든 Job이 동일한 조건 하에서 동등하게 취급되니 starvation 문제도 없겠죠.

그러면 이제 현실에서도 FIFO를 적용할 수 있는지 생각해봅시다.

현실에 맞게 1번 가정부터 빼볼까요? 그러면 이제 Job들이 각기 다른 실행 시간을 가질 것이므로 어떤 것은 100, 어떤 것은 10 정도의 시간이 걸릴 것입니다.

그런데 100만큼 시간이 걸리는 job과 10만큼 시간이 걸리는 job이 있을 때 100짜리가 먼저 왔다고 먼저 실행시켜버리면 10짜리를 먼저 실행시키는 것에 비해 평균 Turnaround time이 굉장히 길어지겠죠?

이를 Convoy effect라고 합니다. 그러므로 FIFO는 현실적으로 적용하기에는 무리가 있어보이므로 다른 스케줄링 방법을 생각해봐야겠습니다.

1. Each job runs for the same amount of time
2. All jobs arrive at the same time
3. Once started, each job runs to completion
4. All jobs only use the CPU (no I/O)
5. The run time of each job is known

SJF (Shortest Job First)

1번 가정을 삭제하면 FIFO는 안된다는 것을 알았으니 2~5번 가정을 만족하는 스케줄링 방법이라도 생각해봐야겠습니다. 그리고 그것이 바로 SJF입니다.

2~5번 가정에 의해 Job들이 동시에 도착하고 각자 얼마나 걸리는지는 여전히 알고 있습니다.

그러므로 FIFO의 문제점을 해결하기 위해 가장 실행시간이 짧게 걸리는 job을 먼저 실행하면 되겠습니다. 그러면 최적의 turnaround time을 보장할 수 있을 것입니다.

그러면 SJF는 현실에 적용 가능할까요? 2번 가정도 빼보죠. 그러면 job들이 각자 다른 시간에 도착할 것입니다. 예를 들어 처음 0초에 1000짜리 job이 도착하고 10초 뒤에 5짜리 job이 도착했다고 생각해봅시다.

SJF는 처음에 1000짜리 job이 도착한 job들 중 가장 실행시간이 짧은 job이므로 1000짜리 job을 실행할 것입니다. 그러면 5짜리 job은 굉장히 많이 기다려야하고 starvation문제가 발생할 수 있겠죠.

그러므로 SJF도 2번 가정을 빼니 현실에 적용하기에는 무리가 있어 보입니다.

1. Each job runs for the same amount of time
2. All jobs arrive at the same time
3. Once started, each job runs to completion
4. All jobs only use the CPU (no I/O)
5. The run time of each job is known

STCF (Shortest Time to Completion First)

지금까지는 non-preemptive 방식의 스케줄링이었으나 SJF의 문제를 해결하려면 기존에 있던 job을 쫓아내야하기때문에 preemptive 방식으로 바꾸어야할 것 같습니다.

1000짜리 job을 돌리다가도 5짜리 job이 오면 1000짜리 job을 중지하고 5를 끝내고 다시 1000짜리를 돌려야 Turnaround time을 최소화할 수 있겠죠.

그래서 SJF의 preemptive 버전인 STCF를 적용하기로 하였습니다. 이를 적용하니 자연스럽게 3번 가정도 깨지게 되는군요.

1. Each job runs for the same amount of time
2. All jobs arrive at the same time
3. Once started, each job runs to completion
4. All jobs only use the CPU (no I/O)
5. The run time of each job is known

RR (Round Robin)

한편, STCF와 다른 접근법도 있는데요. 바로 RR(Round Robin)이라는 방식입니다. RR이란 모든 job들이 일정한 시간만큼 돌아가면서 cpu를 사용하는 것입니다. 이 시간은 보통 10~100ms로 설정되는데 너무 길면 즉각적인 반응이 일어나지않고 너무 짧으면 컨텍스트 스위칭 부하가 커지니까 그렇습니다.

RR은 기존과 달리 response time이라는 것을 Metric으로 사용합니다. 도착한 때부터 시작할때까지 얼마나 걸리냐는 것이죠. 그래서 Turnaround time기준으로는 sjf보다 느리지만 response time 기준으로는 sjf보다 빠르게 됩니다.

$$ T_{\text{response}} = T_{\text{first run}} - T_{\text{arrival}} $$

(Static) Prioiry Scheduling

다른 방법으론 각 job에 priority를 부여해주는 Priority Scheduling 기법이 있습니다. 그래서 priority 순서대로 글을 job들을 돌리는데 같은 priority끼리는 RR을 적용하거나 더 높은 priority를 가진 job이 나타나면 기존 job을 쫓아내고 작동하기도 합니다.

그렇지만 높은 priority job이 계속해서 유입된다면 낮은 priority job은 절대 돌아가지 않을 수도 있죠.

I/O aware STCF

제한 사항을 가지고있던 non-preemptive 방법인 SJF을 여러가지로 개선하여 starvation을 막으려는 시도들이 있었습니다. 그런데 4번의 가정을 제거한 상황에서도 STCF같은 스케줄 방법이 효과적일까요?

1. Each job runs for the same amount of time
2. All jobs arrive at the same time
3. Once started, each job runs to completion
4. All jobs only use the CPU (no I/O)
5. The run time of each job is known

현실에서 job이 돌아갈때 항상 CPU가 필요한 것은 아닙니다. I/O작업을 할 때에는 굳이 CPU가 필요없곘죠. 그런데 그 I/O 시간동안 CPU를 운용하지 않는다면 비효율적일 것입니다.

그렇다면 I/O 시간에 다른 대기 중인 작업들을 돌려서 더 효율적으로 CPU를 운용해야겠습니다. 아직 5번의 가정을 통해 각 job에 걸리는 시간은 알고 있으니 다음 그림과 같이 운용할 수 있을 것입니다.

스케줄러가 점점 더 괜찮아지고 있지만 여전히 현실과는 다른 상황 속에서만 적용되는 스케줄러입니다. 현실에서는 job의 run time을 미리 알 수 없죠. 그렇기때문에 5번의 가정을 제거하면 I/O aware STCF도 쓸 수가 없겠습니다.

그러므로 더 일반적인 CPU scheduler를 생각해보아야겠네요.

마무리

지금까지 처음에 제시한 가정들을 제거해가면서 현실에 더 적합한 스케줄러를 계속해서 제시하는 한편, 스케줄러는 어떤 특성을 가져야하는지도 알게되었습니다.

스케줄러는 job들의 특성을 고려해야하고, preemptive해야합니다. 그리고 I/O가 발생하더라도 CPU가 놀지 않도록 해야하죠.

현재 I/O aware STCF까지 왔지만 5번의 가정때문에 현실에 적용하기에는 무리가 있는 것 같습니다. 그렇기에 더 제너럴한 CPU 스케줄러를 고려해보아야할 것 같고, 그건 다음 글을 통해서 알아보도록 하겠습니다.

감사합니다.