Scheduling

왜 필요한가?

싱글코어 환경에 CPU에서 여러개의 태스크를 병렬적으로 처리하는 것 처럼 보이려면 스케쥴링은 필수적이다. 싱글코어가 아니더라도, 멀티코어에서 실제 병렬적으로 처리되는 태스크는 코어 개수만큼에 불과하기 때문에 마찬가지로 스케쥴링이 요구된다.

그 뿐만 아니라, 태스크간에 우선순위도 분명 존재하기 때문에 이를 적절히 조절하여 사용성을 높이기 위해선 스케쥴링은 필수적이다. 간단하게 어떤 태스크가 수행중이라고 마우스 입력을 처리하는 태스크가 무시되선 안되는 상황을 생각해 볼 수 있다. 

-> 마우스 입력을 처리하는 것은 인터럽트이기 때문에 위 예시는 적절하지 않다. 다른 예시로, 웹 브라우저와 바이러스 스캐너, 워드 프로세서 3가지 프로그램이 동작하고 있다고 가정해보자. OS는 세가지 프로그램 중 웹브라우저의 우선순위를 가장 높게 책정하여 스케쥴링할 것이다. 만약 브라우저로 live stream 서비스를 시청하고 있거나, 비디오 콜등을 수행한다고 생각하면 이는 시간에 민감하기 때문에 다른 프로세스에 비해 우선적으로 처리될 필요가 있다. 그에 비해 바이러스 스캐너에 경우 백그라운드에서 돌아가며, 시간에 민감하진 않기 때문에 비교적 낮은 우선순위로 스케쥴링 될 것이다. 워드 프로세스는 브라우저 만큼 시간에 민감하진 않지만 바이러스 스캐너에 비해선 더 interactive 하게 동작할 것이며, 이에 따라 중간 정도에 우선순위를 부여받을 것이다.

이와 같이 OS 는 우선순위에 따라 프로세스를 수행하며 사용자 경험을 높일 수 있다.

한가지 더, 이는 자원 효율성에 측면에서도 중요하다. 한 태스크가 디스크에서 파일을 읽어오는 작업을 수행할 때 이를 기다릴 필요 없이 다른 태스크를 스케쥴링 하는 방식으로 활용될 수있다. 

OS에서는 여러가지 스케쥴링 기법을 사용한다.

가장 간단한 방법으로는 온 순서대로 처리하는 FIFO (First In, First Out)가 있다.

FIFO

치명적인 단점은 먼저 도달한 프로세스의 수행시간이 길 경우 뒤의 프로세스들은 속수무책으로 이를 기다려야 한다는 것이다. 

물론, 순서가 바뀌더라도 A~C 가 모두 처리되는데 걸리는 시간은 똑같을 것이다. 하지만 프로세스 요청 시점부터 종료시간까지의 평균인 turnaround time 이 짧아진다. 

turnaround time 이 짧아지면 뭐가 좋은걸까?

간단하게 예를 들어, A~C 모두 유저가 원하는 파일을 여는 작업이라고 가정해 보자. A가 먼저 스케쥴링 되는 위 상황에서는 유저는 해당 프로세스가 완료되기 전까지 아무것도 할 수 없이 기다려야 할 것이다. 그에 비해 B, C 가 먼저 스케쥴링 되는 상황에선 B, C 가 연 파일을 보다 빨리 확인할 수 있게 되고, 이를 읽는 동안 A가 완료될 수 있어 사용자 경험이 좋아질 것이다.

그렇다면, 어떤식으로 turnaround 를 짧게 만들 수 있을까? 이 때 생각해 볼 수 있는 것이 SJF (Shortest Job First) 기법이다.

SJF

요청시점에 쌓여있는 태스크 중, 가장 먼저 끝나는 태스크부터 수행한다. 이를 통해 turnaround 를 줄일 수 있다. 

하지만, 위와 같이 요청이 동시에 오는 것이 아니라 A -> B -> C 순서대로 들어온다면 FIFO와 다를게 없다. 이를 해소하기 위해선 preemption 이 적용될 필요가 있다. A 태스크가 수행중이더라도 B가 들어왔을 때, 그 시점에 A와 B중 어떤 태스크가 먼저 끝냐나에 따라 A가 선점되고 B가 수행될 수 있는 것이다. 해당 기법을 STCF (Shortes Time-to-Completion First) 라고 한다.

STCF

다만, SJF 와 STCF 에는 모두 치명적인 한계가 존재한다. 한 태스크가 언제 끝날지를 미리 예측하는것은 매우 어렵다는 것이다. 사실상 이는 이론적인 모델이라고 봐야한다.

RR 

실제로 쓰이고 있는 스케쥴링 기법 중, 먼저 RR (Round Robin) 기법에 대하여 살펴보자. 이 기법에 강점은 Response Time 에 있는데, 쉽게 말해 프로세스가 요청 부터 처음 수행 시작하는 시간의 차이 평균이 작다는 것이다.

위 이미지를 보면 이를 쉽게 이해할 수 있다. Round Robin 은 모든 프로세스를 적절한 time slice 로 쪼개어 이를 번갈아가면서 스케쥴링 한다. 

respone time 이 작으면 뭐가 좋은걸까?

사용자가 브라우저 창을 여는 동작을 3번 수행한다고 했을 때, 만약 FIFO 방식이 사용된다면 1번 브라우저가 완벽히 켜질 때 까지 2~3번 브라우저는 아무런 동작 없이 대기하게 되며, 이 때 유저입장에서는 3번째 브라우저 요청에 대한 반응이 늦게 일어나는 것처럼 느껴진다. (실제로 비교적 늦게 일어난다)

Round Robin 기법을 적용하면, 비록 브라우저가 완벽히 켜지진 않더라도 빈 창을 띄우는 방식으로 3개의 브라우저를 요청과 동시에 띄울 수 있으며, 실제 처리되는 시간이 같다고 하더라도 유저는 시스템이 더 빠르게 동작한다고 느낄 수 있는 것이다.

적절한 time slice 가 어느정도일까? 

time slice 가 짧아질 수록 반응 속도가 더욱 좋아질 것이라고 생각되지만, 항상 그렇지는 않다. 프로세스가 새로 스케쥴링 될 때에는 context switching 이 발생하며, 이는 꽤 무거운 작업으로 time slice 가 너무 작아지면 오히려 context switching 의 비용으로 전반적인 퍼포먼스가 떨어지게 될 수 있다. 

이러한 trade-off 를 고려하여 적절한 수준에서 time slice 가 결정된다. 이는 물론 OS, 시스템 설계, 하드웨어 별로 상당히 다르게 설정될 것이다. 

그래도 궁금하니 내 노트북의 time slice 를 알아보자. macOS 기준으로 터미널에 sysctl kern.clockrate 명령어를 입력하면 다음과 같은 결과를 받아볼 수 있다. 

kern.clockrate: { hz = 100, tick = 10000, tickadj = 0, profhz = 100, stathz = 100 }

여기서 hz  값은 초당 타이머 인터럽트 횟수를 나타내며, 이에 따라 초당 100번의 인터럽트, 최대 10ms 에 해당한다.

다만, 이 결과가 반드시 내 노트북의 스케줄러가 10ms time slice 를 사용한다는 뜻은 아니며, 다양한 요인에 따라 더 짧거나 길게 결정될 수 있다. 간단하게 대략 어느정도구나 하고 넘어가는게 좋을 것 같아 보인다.

Incorporating I/O

앞서 스케쥴링이 왜 필요한지 설명할 때 자원 효율성을 언급하였다. 이를 이미지로 표현하면 다음과 같다.

STCF 에서 이상적으로  태스크가 종료되는 시간을 모두 예측할 수 있다고 하더라도, 위와 같이 I/O 관련 작업이 많은 경우엔 태스크는 이를 기다려야 하며 그에 따라 CPU는 놀게 된다. 물론, STCF 는 선점이 가능하지만 I/O 작업을 포함하더라도 여전히 A 태스크가 더 짧은 상황에는 위와 같은 문제가 발생할 것이다.

이에 비해 RR 방식에선 A가 Disk 관련 작업을 기다려야 한다면 그 즉시 다른 프로세스를 스케쥴링하여 CPU 를 효율적으로 사용할 수 있다.

해당 동작에 대하여 조금 더 자세히 살펴보자. A는 명령어를 수행 중에 Disk I/O 를 요청하게 되는데, 아직 데이터가 준비되지 않은 경우엔 sleep 되며 다른 프로세스가 스케쥴링 된다. 이 때 sleep 된 프로세스는 더 이상 스케쥴링 되지 않는다. 파일 I/O 가 완료되면 디바이스에 의하여 인터럽트가 발생하며, 이 인터럽트 핸들링 과정에서 프로세스 A는 ready 상태로 변경된다. ready 상태의 프로세스는 스케쥴링 대상이기 때문에, 특정 시점에 OS에 의하여 A프로세스가 다시 수행되게 된다.

MLFQ

Multi-Level Feedback Queue 의 약자로, RR과 함께 실제 스케쥴링 구현에 자주 활용되는 기법이다. 이는 우선순위별로 여러개의 큐를 관리하며, 각 큐에서는 RR 방식으로 프로세스를 스케쥴링 한다. 

MLFQ의 장점은 무엇일까? turnaround time 을 줄이고, response time은 빠르게 한다. 그게 어떻게 가능한지는 MLFQ 의 자세한 동작을 살펴보며 알아보자.

먼저, MLFQ 에서는 작업을 크게 2가지 유형으로 관리한다. 한가지는 Interactive job 으로, 이는 여러번의 I/O 요청을 사용하며 CPU 를 time slice 를 다 쓰지 않고도 반복적으로 자주 포기하고, 짧게 동작한다. MLFQ 에선 이를 높은 우선순위의 태스크로 유지한다.

다른 한가지는 CPU-intensive job 으로, 이는 주로 time slice 를 꽉 채워 사용하며, 전체 수행시간이 길고, response time 이 크게 중요하지 않다. MLFQ 에선 이를 낮은 우선순위에 태스크로 유지한다. 

SJF와 STCF 에 대한 한계에서 설명하였듯이, OS가 처음부터 어떤 task 가 Interactive job 인지 CPU-intensive job 인지 알 수 없는거 아닌가?

그렇다. 그렇기 때문에 우선순위를 관리한다고 표현한 것이다. MLFQ 방식에선 실제 태스크를 수행하면서 이를 판단한다.

즉, 새로운 태스크가 생성된다면 우선 이를 가장 높은 우선순위에 큐에 추가한다. 그 후, 해당 태스크가 스케쥴링되었을 때  time slice 전에 CPU 를 포기한다면 우선순위를 유지하고, time slice 를 끝까지 사용한다면 우선순위를 한단계 낮추는 방식으로 동작한다. 

위 방식을 사용하면 자연스럽게 Interactive job 은 높은 우선순위의 큐에 유지되고, CPU-intensive job 의 경우 낮은 우선순위의 큐에서 스케쥴링 될 것이다. 

이 동작방식을 이애하고 나면, 앞서 turnaround time 을 줄일 수 있다는 것은 쉽게 이해할 수 있다. 오래 걸리는 태스크는 자연스럽게 가장 낮은 우선순위로 이동할 것이고, 더 빨리 끝나는 태스크들이 먼저 스케쥴링 되어 STCP 만큼 이상적이진 않더라도, turnaround time 을 많이 줄일 수 있을 것이다. 

response time은 어떨까? 새롭게 추가된 태스크는 우선 가장 높은 우선순위 큐에 추가되기 때문에 당연히 빨라질 것이다.

더 나아가 반응 시간을 그저 처음 태스크가 시작하는 시간이 아닌, 유저가 빠르게 받아보길 원하는 동작을 수행하는 시간이라고 생각해 보자.

스케쥴링의 우선순위 예시로 브라우저로 라이브 스트리밍을 시청하는 경우를 들면, 해당 프로세스는 지속적으로 소켓을 읽는 I/O 작업을 포함하기 때문에 Interactive jobs 으로 관리되어 높은 우선순위를 유지할 것이다. 이에 따라 유저는 그 외에 우선순위가 낮은 프로세스에 의하여 스트리밍이 느려지는 상황을 겪지 않을 수 있다.

Problems 

이러한 MLFQ 에는 몇가지 문제점이 존재한다.

Starvation

먼저, Starvation 현상이 발생할 수 있다. 즉, 우선순위가 높은 태스크들이 많을 경우에 우선순위가 낮은 태스크들은 아예 스케쥴링을 받지 못하는 기아 현상이 발생한다. 이를 방지하기 위해서 Priority Boost 를 적용한다.

이는 일정 주기마다 모든 태스크를 높은 우선순위의 큐로 끌어 올려주는 방식이다. 이를 통해 B, C 작업이 더 많은 스케쥴링을 받는 것이 유지되면서도, A 작업도 한번씩 해당 주기마다 스케쥴링을 받을 수 있게된다.

Game the scheduler

앞서 time slice 를 100% 사용하지 않고 CPU를 놓아주는 경우 우선순위가 유지된다고 설명하였다. 이를 개발자가 프로그램을 매 주기에 time slice 의 99% 만 사용하고 CPU를 놓아주는 방식으로 작성하여 악용할 수 있다. 

이를 방지하기 위해 MLFQ 구현에서 추가적인 rule 들을 정의한다. 태스크의 요청이 진짜 I/O 요청인지를 판단하는 방식, CPU 를 포기하는 패턴을 감지하는 방식을 사용하여 gaming 을 판단해 우선순위를 낮추기도 하며, CPU를 계속 놓아주었더라도 주어진 레벨에에서의 시간 이상을 사용했다면 우선순위를 낮추는 방식을 사용한다.

Program may change its behavior

마지막으로 다룰 문제점은, 태스크가 처음에는 CPU-intensive 로 동작하다가 후반부에 interactive 작업을 진행할 경우 MLFQ 에선 이를 제대로 처리하지 못한다는 것이다. 하지만, 이 또한 앞서 설명한 Priority Boost 기법에 의하여 어느정도 해소될 수 있다.

Tuning MLFQ

우선순위를 구분하는 것으로 그치지 않고, 높은 우선순위의 작업에는 time slice 를 적게 배정하고, 낮은 우선순위의 작업에는 time slice 를 많이 배정하는 방식으로 시스템의 반응성과 처리량을 높일 수 있다.

I/O bound task 가 높은 우선순위를 갖는 것이 자원 효율측면에서 좋다는 점은 위에서 설명한 바 있다. time slice 를 작게 배정하면, I/O bound task 가 아닌 task 들은 더욱 많이 걸러져 낮은 우선순위로 내려갈 것이고, 이에 따라 I/O bound task 는 반응성이 높아짐과 동시에, 시스템 전체적으로는 자원을 더욱 효율적으로 사용하게 될 것이다. (그렇다고 너무 줄이면 I/O 요청도 전에 time slice 가 끝나버릴 수도 있으니 적정한 수준이 필요하다)

그에 비해 CPU-bound task 들은 낮은 우선순위의 큐에 배정되는데, 이는 기본적으로 CPU 를 더 오래 사용하며 많은 작업을 수행해야 하기 때문에, 자주 스케쥴링 될 경우에 context switching 으로 인한 비효율이 발생할 수 있다. 따라서, 낮은 우선순위 큐에 작업들의 경우 time slice 를 늘려주는 것이 효율적일 수 있다. (그렇다고 너무 늘리면 반응성이 떨어지기 때문에 적정한 수준이 필요하다)