[OStudy] 4주차 - 스케줄링(2)

직전 포스팅에서는 가장 기초적인 스케줄링과, 그 스케줄링 구축에 대한 기초적인 정책에 대해 다루었습니다. 이번에는 실제 시스템과 유사한 방식으로 동작하는, MLFQ(Multi Level Feedback Queue)에 대해 알아볼 차례입니다. MLFQ 스케줄링 알고리즘은, 명칭 그대로, 여러 구간을 나누어 스케줄링을 진행하고, 그 구간을 나누는 기준의 경우, 프로세스의 실행 특성에 따라 동적으로 우선순위를 평가하여 조정하는 방식으로 진행됩니다. 또한, 이러한 방식의 동적 우선순위를 설정하는 스케줄링 뿐 아니라, 공정성을 가장 중요한 지표로 삼는 비례 배분 스케줄링 알고리즘 또한 존재합니다. 이번 포스팅에서는 이러한, 실전에서 응용하는, 상당한 복잡성의 스케줄링 알고리즘을 알아볼 겁니다.

 

멀티 레벨 피드백 큐(MLFQ)

 MLFQ의 경우, 짧은 작업을 우선적으로 처리해 반환 시간의 최적화 확보에 집중하는 것과, 상호작용 계열의 프로세스를 빠르게 처리하여 프로세스의 응답 시간을 단축시키기 위한 두가지 목적으로 고안되었습니다. 이는 곧 이전 포스팅에서 다뤘던 SJF와 STCF 또는, 응답 시간 쪽에선 RR 등의 알고리즘 등에서 보이는, 단일성 로직의 한계를 해소됨을 의미했습니다. 

하지만 위에서 언급한 대로라면, 몇가지 의문이 생기기도 합니다. 먼저, OS가 개별 프로세스에 대한 사전 정보가 전혀 없는 상황일텐데, 어떻게 실행 시간 등을 고려해서 우선순위를 조정할 수 있을까요? 프로세스가 실행되는 동안 판단할까요? 그렇다면, 해당 실시간 정보를 통해 더 나은 스케줄링 결정을 내리려면 어떤 방법을 고민해야 할까요? MLFQ에 대해 설명하며, 이러한 궁금증에 대한 해답을 탐색해보겠습니다.

먼저 MLFQ는 다음과 같은 기본 알고리즘이 기반됩니다. MLFQ로 구현된 케이스들은 대체로 다음과 유사한 원리를 가집니다. 우선, MLFQ의 경우 여러 큐로 구성되어 있으며, 해당 큐들은 각각 다른 우선순위 레벨(Priority Level)을 지닙니다. 그리고 실행 가능한 프로세스가 해당 큐들 중 하나에, 정책에 맞추어 배정됩니다. 그리고 스케줄링을 위해, MLFQ가 다음 실행할 프로세스를 선택하려 할 경우, 교체 가능한, 가장 높은 레벨의 큐에 존재하는 프로세스를 우선적으로 선택합니다. 한 구간의 큐가, 한 우선순위를 맡습니다. 즉, 특정 큐 안에 속한 프로세스들은 모두 동일한 우선순위를 가집니다. 또한, 동일 큐 이내에서는 RR 스케줄링을 통해 순서를 설정합니다. 또한 MLFQ를 통해 설정되는 우선순위는 고정된 값이 아닙니다. 프로세스의 실행 특성에 맞추어 동적으로 이 값을 설정합니다. 이는 단순히 프로세스의 역할만을 따지지 않습니다. 제어권의 양보 여부나, 타임 슬라이스 등을 통해, 우선 순위 조정이 가능합니다. 그럼 이 MLFQ를 자세히 살펴 볼까요?

먼저 MLFQ를 구축한다고 함은, 프로세스의 우선순위를 어떻게 조정할지를 먼저 결정해야 합니다. 동적인 순위 부여가되는 알고리즘이기 때문에, 해당 부분이 가장 중요하다고 볼 수 있습니다. 그리고 이러한 정책의 결정은, 시스템의 워크로드 특성을 반영해야합니다. MLFQ에 새로운 프로세스가 진입할 경우, 해당 프로세스에는 가장 높은 우선순위가 부여되어 최상된 큐로 위치됩니다. 그리고 실행 중인 프로세스에게 할당된 타임 슬라이스가 소진되어버리는 경우 해당 프로세스의 우선순위가 한 단계 낮아서, 한 칸 낮은 큐로 배정됩니다. 반대로, 자발적인 제어권 양도로 이루어진 경우(PintOS에서 구현했던, yield 명령어), 우선 순위는 유지됩니다. 이는 I/O를 지속 반복적으로 수행하는 프로세스는, 해당 작업 완료를 대기하며 반복적인 yield 호출로 높은 우선순위를 유지할 수 있게 해줌과 동시에, 단순히 CPU를 장시간 사용해야 하는 프로세스는 지속적으로 늦은 우선순위를 부여할 수 있게 해주는 효과를 보입니다. 이를 조금 더 나아가 말한다면, 상호작용을 위한 응답 시간을 최대한 단축시킴과 동시에, 반환 시간의 최적화를 극대화 시키는 모습을 보입니다. 

물론, MLFQ 자체도, 완벽한 알고리즘이라 하기엔 어폐가 존재합니다. 먼저, 대화형 작업 계열의 프로세스가 시스템 내에 굉장히 많이 존재하는 케이스를 상정한다면, 이들이 CPU 시간 대부분을 차지합니다. 그렇다면 하위 레벨에서 대기하는 작업의 경우 CPU 할당을 받지 못하거나, 굉장히 늦게 이양받을 가능성이 생기며, 이는 건강한 시스템이 되진 못할 겁니다. 이러한 계열의 상태를 기아 상태(starvation)라고 하며, 단순 MLFQ는 해당 상태에 취약합니다. 또한 특정 프로세스가, 설계 단계에서부터, 해당 MLFQ 알고리즘으로부터 높은 우선순위를 부여받고, 지속적인 yield 반복으로 높은 우선순위를 유지할 수 있게끔 구축할 경우, 스케줄러를 악용해 지속적으로 CPU 제어권을 차지할 수 있습니다. 또한, 프로세스의 성격 변화를 MLFQ가 탐지하진 못합니다. 집약적 작업과 대화형 작업을 번갈아 수행하는 프로세스는 관측된 시점에 보인 해당 특성 계열로만 판단될 것입니다.

해당 기아 상태를 위 그림에서 반영하고 있습니다. 적혀 있듯, 우선순위 상향이라는 로직을 추가 적용하여 해당 문제를 해소할 수 있게되는데, 특정 시간의 경과마다, 시스템의 모든 프로세스를 최상위 레벨 큐로 이동시키는 로직을 통해 최저레벨로 이동하게되는 집약형 작업을 일정 시간마다 강제로 제어권을 이양 시키는 동작을 수행합니다. 해당 논리의 추가로, 기아 상태를 적어도, 특정 시간마다 해소시킬 수 있음을 보장받게되며, 특성의 변화가 일어나도, 최상위 레벨로 이동한 시점의 작업 특성에 맞추어 해당 작업에 맞는 레벨 큐로 이동할 수 있게 됩니다. 물론 해당 기법은, 이 특정 시간(S)를 얼마나 두냐에 따라 그 효율이 달라집니다. 하지만 이 S는 부두(voodoo) 상수로 불릴 만큼 악명이 높습니다. 높이게되면 기아 상태가 일정 시간 발생하고, 낮게 만들면 대화형 작업이 원활히 동작하지 못하게됩니다. 따라서 이 두 문제에서 균형을 맞추어 S를 산정해야합니다.

 

비례 배분 스케줄링(Proportional Share)

 기존 스케줄링 기법들의 목적이, 반환 시간이나 응답 시간의 단축 및 최적화였다면, 비례 배분 알고리즘은 CPU 제어 비중의 공정성에 초점을 맞춘 기법입니다. 즉, 각 프로세스의 작업에 있어서, CPU 제어 시간의 일정 비율을 보장하는 것을 목표로 합니다. 대표적인 비례 배분 스케줄리의 경우, 추첨 스케줄링(Lottery Scheduling) 기법이 있습니다. 그렇습니다. 우리는 OS에서조차, 가챠를 합니다. 이 가챠... 추첨 스케줄링은 다음 실행할 프로세스를 추첨 방식으로 랜덤 선택합니다. 다만 랜덤이라 하지 않는 이유는, 특정 기준(CPU 제어 시간이 비교적 더 필요한 프로세스인가 등)에 따라, 일부 프로세스는 당첨될 확률을 더 높게 설정하기 때문입니다. 비례 배분 스케줄링은, 각 프로세스에게 할당된 점유율의 공정성을 추구합니다. 설명한 논리 하에 동작하는 비례 배분 스케줄링은, 큰수의 법칙을 통해 사전 설정된 비율대로, 프로세스에게 CPU 제어권을 엄격히 배분합니다. 따라서 절대적인 시간이 아닌, 비율적인 측면에서 큰 공정성을 기대할 수 있습니다. 해당 기법을 통해서, 프로세스가 중요도를 확률로 조절할 수 있기 때문에, 중요도 변경에서 큰 유연함을 얻을 수 있고, 새 프로세스가 추가된다 하더라도, 당첨 확률을 조정하기만 하면 되니, 확장성 측면에서 굉장히 간단합니다. 또한 장기적으로 공정한 CPU 할당 시간이 보장되므로, 장기적인 공정성 측면에서도 큰 이점을 보입니다. 하지만 이러한 추첨 스케줄링도 단점은 존재하는데, 많은 수의 사건(교체)이 일어나기 전까진, 일부 불균형적인 제어권 부여가 발생할 수 있기 때문에, 단기적으로 불공정할 수 있음을 의미합니다. 또한, 이러한 추첨 방식은, 어떤 프로세스가 다음 실행 프로세스일지 바로 알 수 있는 것이 아니기 때문에, 추첨부터 프로세스 확인까지 모두 연산 비용이 발생하여 일부 오버헤드가 발생할 수 있습니다. 이러한 단점을 보완하여, 결정론적 공정 배분 성격의 보폭 스케줄링(stride scheduling)이 등장하기도 했습니다. 

보폭 스케줄링은 각 프로세스마다 고유 보폭(stride)값을 할당하고, 임의의 pass 변수를 설정해, 프로세스가 CPU를 사용할 때마다 해당 pass 값을 보폭만큼 증가시켜 CPU 사용량을 추적합니다. 그리고 이 pass와 보폭값을 이용해 스케줄링을 진행하는데, 가장 낮은 pass 값을 가진 프로세스를 선택해 CPU를 할당합니다. 대기 중인 프로세스들은 pass 값이 유지되거나 감소되며, 실행 순서가 조정됩니다. 이러한 방식을 통해 무작위성에 기반된 추첨 스케줄링의 초기 불공정성이나 오버헤드 문제를 다소 해결할 수 있습니다. 물론 구현의 난이도나, 유지해야하는 프로세스 정보 비용 등에서는 보폭 스케줄링이 비교적 밀리는 편이기 때문에, 새 작업 추가가 용이한 추첨 스케줄링이 무작위성으로 인한 단점이 존재하기는 하나, 비교적 선호되는 성향이 있습니다.