"Scheduling: Proportional Share"
이 장에서는 비례(공정) 분배 스케줄러( Proportional share 스케줄링 )를 살펴보겠습니다. 이 스케줄러는 반응 시간이나 반환 시간을 최적화하는 대신, 각 작업이 일정 비율의 CPU 시간을 보장받도록 합니다. 해당 스케줄링을 구현하기 위한 초기 방법은 Lottery Scheduling입니다. 말 그대로 로또 복권처럼 이번엔 어떤 프로세스가 실행될지 추첨하는 방식입니다. 그렇다면 이런 스케줄러를 어떻게 설계할지, 이를 위한 핵심 메커니즘과 효과를 알아봅시다.
로터리 스케줄링의 기반이 되는 매우 기본적인 개념은 티켓입니다. 이는 프로세스(또는 사용자)가 받아야 할 자원의 지분을 뜻합니다.예를 들어보겠습니다 (그림2). 프로세스 A와 B가 있고, A는 75개의 티켓을, B는 25개의 티켓을 가지고 있다고 가정합니다. 이 의미는 A가 CPU의 75%를, B가 나머지 25%를 받는 것을 원한다는 것이라 할 수 있습니다. 로터리 스케줄링은 매 타임 슬라이스마다 무작위로 티켓을 선택해가며 확률적으로(결정론적X) 이를 달성합니다. 당첨 티켓은 0~99사이 무작위 숫자이며, A가 0부터 74까지, B가 75부터 99까지의 티켓을 가지고 있다고 가정할 때, 당첨 티켓은 A 또는 B가 실행될지를 결정합니다. 그런 다음 스케줄러는 그 당첨 프로세스의 상태를 로드하고 실행합니다.
앞서 말했듯, 로터리 스케줄링은 결정을 내려야 할 때, 무작위 추첨 방식을 사용합니다. 이 무작위 추첨 방식은 세 가지 이점이 있습니다. 첫째, 무작위는 극단적인 경우나 최악의 경우가 없습니다. 둘째, 대안을 추적 및 상태 저장이 없으므로 가볍습니다 . 무작위로 하면 프로세스 당 가장 최소한의 상태(예: 각자 가진 티켓의 수)만 필요합니다. 마지막으로, 무작위는 빠릅니다.
로터리 스케줄링은 또한 티켓을 조작하는 여러 메커니즘을 제공합니다.첫번째는 Ticket Currency 입니다. 어떤 프로세스에게 지역 통화를 부여하면 이를 CPU에서는 글로벌 통화로 바꾸어 스케줄링에 사용합니다.
예를 들어, 사용자 A와 B가 각각 100개의 티켓을 받았다고 가정합니다. 사용자 A는 두 개의 작업(A1과 A2)을 실행 중이며, 각각 500티켓을 A의 통화로 줍니다. 사용자 B는 하나의 작업만 실행 중이며, 그것에 10티켓을 줍니다.
사용자 A의 각 작업은 전체 티켓의 50%인 50티켓을 전역 통화로 받게 됩니다. 즉, A1과 A2의 할당을 A의 통화에서 각각 500에서 전역 통화에서 각각 50으로 변환합니다.
마찬가지로 사용자 B는 10티켓을 자신의 하나의 작업에 할당했습니다. 사용자 B의 전체 티켓은 100티켓이므로, 이는 10티켓 작업이 사용자 B의 전체 티켓 100%를 사용함을 의미합니다. 따라서 B의 10 티켓은 100 티켓으로 변환합니다.
이렇게 각 프로세스 작업들을 전역 티켓 통화로 바꾼 후, 전역 티켓 통화로 로터리가 열려 어떤 작업이 실행될지 결정됩니다.
또 다른 유용한 메커니즘은 Ticket transfer 입니다. 프로세스는 일시적으로 자신의 티켓을 다른 프로세스에게 넘길 수 있습니다.예를들어 서버/클라이언트에서, 클라이언트 프로세스가 서버에게 클라이언트 대신하여 일을 시킵니다. 이때 빠른 작업을 위해 클라이언트는 티켓을 서버에게 전달할 수 있으며, 이를 통해 서버가 클라이언트의 요청을 처리하는 동안 성능을 극대화할 수 있습니다. 작업이 완료되면 서버는 티켓을 다시 클라이언트에게 전송하고 모든 것이 이전 상태로 돌아갑니다.
마지막으로, Ticket inflation 입니다. 프로세스는 일시적으로 소유한 티켓의 수를 늘리거나 줄일 수 있습니다. 이것은 경쟁상황엔 적용되지 않으며, 프로세스 그룹이 서로 신뢰하는 환경에서 적용됩니다. 어떤 프로세스라가 더 많은 CPU 시간이 필요하다면, 시스템에서 티켓값을 높입니다.
코드는 프로세스 리스트를 순회하며, 각 티켓 값을 카운터에 더합니다. 값이 당첨자를 초과할 때까지 계속됩니다. 먼저, A로 인해 카운터가 100으로 증가합니다; 100은 300보다 적기 때문에, 루프는 계속됩니다. 그 다음 B의 티켓으로 카운터가 150으로 업데이트되지만, 여전히 300보다 적기 때문에 다음을 순회합니다. 마지막으로, 카운터가 400으로 업데이트됩니다. 이때 이 값은 300보다 크기때문에 루프를 탈출하고 당첨자는 C가 됩니다. 이때 리스트를 티켓 수가 가장 많은 순으로 정렬하면 이 과정이 좀더 효율화 됩니다.
이제 lottery 스케줄링을 fairness라는 관점으로 다시 살펴보겠습니다.
이 관점에선 각 작업이 대략 같은 시간에 완료되기를 원하지만, 로터리 스케줄링 무작위성으로 인해 때때로 한 작업이 다른 작업보다 먼저 완료될 수 있습니다. 이 차이를 정량화하기 위해, 간단한 공정성 지표 F를 정의합니다. F는 단순히 첫 번째 작업이 완료되는 시간을 두 번째 작업이 완료되는 시간으로 나눈 것입니다.
A, B 프로세스가 있고 A 프로세스가 끝나는 시간을 C1, B 프로세스가 끝나는 시간을 C2라고 하겠습니다. 그리고 먼저 끝나는 작업을 A라고 하겠습니다. 여기서 Fairness를 구하면 C1/C2의 값이 됩니다. 이 값은 0.5일 때 가장 형평성이 안 좋다고 할 수 있고 1일 때 가장 좋다고 할 수 있습니다.
A 프로세스 도착시간 0초, 수행 시간 : 10초, 완료 시간 10초 => C1 = 10초
B 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 20초 => C2 = 20초
fairness = C1 / C2 = 10 / 20 = 0.5
위와 같은 상황이 최악의 상황입니다. A 프로세스가 모두 끝난 뒤에야 B 프로세스가 동작하기 때문이죠. 그럼 가장 좋은 경우를 살펴보겠습니다.
A 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 19.9999초 => C1 = 19.9999초
B 프로세스 도착시간 0초, 수행시간 : 10초, 완료시간 20초 => C2 = 20초
fairness = C1 / C2 = 19.9999 / 20 = 1
위처럼 A 프로세스와 B 프로세스가 lottery 스케줄러로 잘 스케줄링되어 번갈아가며 수행되어 완료되는 시간이 동일하게 되면 그때 fairness가 1이 나옵니다!
그림 9.2는 두 작업의 길이(R)가 1에서 1000까지 변화될 때 F를 나타냅니다. 그래프에서 볼 수 있듯이, 작업 길이가 매우 길지 않은 경우, F는 꽤 낮을 수 있습니다. 작업이 상당한 수의 시간 슬라이스 동안 실행될 때만 원하는 공정한 결과에 접근합니다.
그렇다면 작업에 티켓을 어떻게 할당할까요? 한 가지 접근법은 사용자가 가장 잘 안다고 가정하는 것입니다. 이 경우 각 사용자에게 일정 수의 티켓을 주고, 사용자는 원하는 대로 자신이 실행하는 작업에 티켓을 할당할 수 있습니다. 하지만 "티켓 할당 문제"는 여전히 해결되지 않은 상태로 남습니다.
또한 티켓을 어떻게 할당할지 정했다고 해도, 복권 방식이라 누가 수행될지는 랜덤이죠. 이렇게 어떤 결과를 가져올지 확실하지 않은 것을 Not deterministic이라고 합니다. 이를 deterministic 하게 만드는 것이 바로 다음 섹션에서 나타나는 Stride 스케줄링입니다.
앞서 보았듯 무작위성은 간단한 스케줄러를 제공하지만, 짧은 시간대에서는 정확한 비율값을 전달하지 못할 수 있습니다. 이런 이유로 결정론적( deterministic )인 공정 분배 스케줄러인 스트라이드 스케줄링이 등장했습니다.
여기서 각 프로세스는 stride 를 가지고 있으며, 이는 할당된 티켓 수에 반비례합니다. 위의 예시에서 A, B, C 작업은 각각 100, 50, 250 티켓을 가지고 있으며, 각 프로세스에 할당된 티켓 수로 어떤 큰 수를 나눔으로써 각각의 스트라이드를 계산합니다.
예를 들어, 각 티켓 값에 10,000을 나누면 A, B, C의 스트라이드 값이 각각 100, 200, 40이 됩니다. 이 값을 각 프로세스의 stride 라고 하며, 프로세스가 실행될 때마다 그것의 스트라이드만큼 카운터(그것의 패스 값이라고 함)를 증가시켜 그것의 전역 진행 상황을 추적합니다.
즉, 주어진 시간에, 지금까지중 가장 낮은 패스 값을 가진 프로세스를 실행합니다. 프로세스를 실행할 때, 그것의 pass 카운터를 그것의 스트라이드만큼 증가시킵니다.
그림 9.3은 시간에 따른 스케줄러의 동작을 추적합니다. 위 예( 그림 9.3 ) 에서, 우리는 스트라이드 값이 각각 100, 200, 40인 세 개의 프로세스(A, B, C)로 시작하며, 모두 처음에는 패스 값이 0입니다. 따라서 처음에는 패스 값이 동일하므로 어떤 프로세스라도 실행될 수 있습니다. 여기서는 A를 선택한다고 가정하면, A가 실행되고 시간 슬라이스가 끝난 후에는 그것의 패스 값을 100으로 업데이트합니다. 그런 다음 B를 실행하고, 그것의 패스 값을 200으로 설정합니다.
마지막으로 C를 실행하고, 그것의 패스 값을 40으로 증가시킵니다. 이 시점에서, 알고리즘은 가장 낮은 패스 값을 가진 C를 선택하고, 그것의 패스를 80으로 업데이트합니다. C는 여전히 가장 낮은 패스 값을 가지고 있으므로 다시 실행되어 패스 값을 120으로 올립니다. 그런 다음 A가 실행되어 패스 값을 200으로 업데이트합니다. 그런 다음 C가 두 번 더 실행되어 패스 값을 160, 그리고 200으로 업데이트합니다. 이 시점에서 모든 패스 값이 다시 동일해지고, 프로세스는 무한히 반복됩니다.
그림에서 볼 수 있듯이, C는 5회, A는 2회, B는 1회 실행되었으며, 이는 각각 250, 100, 50의 티켓 값을 완벽하게 비례하여 반영합니다. 로터리 스케줄링은 시간에 따라 확률적으로 비율을 달성하는 반면, 스트라이드 스케줄링은 각 스케줄링 주기의 끝에 정확한 비율을 달성합니다.
스트라이드 스케줄링이 이토록 정밀한데 왜 로터리 스케줄링을 사용할까요? 로터리 스케줄링은 스트라이드 스케줄링과 달리, 전역 상태가 없습니다. 만약 스트라이드 스케줄링 예시 중간에 새로운 작업이 들어오고 패스 값을 0으로 설정해야 한다면, 그 작업은 CPU를 독점하게 될 것입니다.
반면 로터리 스케줄링에서는 프로세스당 전역 상태가 없으며, 단순히 새 프로세스를 추가하고, 우리가 가진 티켓의 총 수를 추적하는 단일 전역 변수를 업데이트하고 거기서부터 시작합니다. 이런 방식으로 로터리는 새로운 프로세스를 통합하기가 훨씬 쉽습니다.
지금까지 proportional share 스케줄링의 방법을 살펴봤지만, 현재 Linux에서는 다른 방식으로 fairness를 만족시킵니다. 바로 CFS(Completely Fair Scheduler)라는 이름의 스케줄링입니다.
최근 연구에서 스케줄러의 효율성은 컴퓨터의 성능에서 엄청나게 중요하다는 것이 밝혀졌습니다. CFS는 스케줄링 결정을 내리는 데 매우 적은 시간을 소비하려는 목표를 가지고 있습니다.
대부분의 스케줄러가 고정된 time slice를 기반으로 하는 반면, CFS(완전 공정 스케줄러)는 가상 실행 시간(vruntime)기술로 CPU를 모든 경쟁 프로세스 사이에서 공평 균등하게 나눕니다.
각 프로세스가 실행됨에 따라 vruntime이 쌓입니다. 각 프로세스의 vruntime은 물리적(실제) 시간에 비례하여 동일한 비율로 증가합니다. CFS는가장 낮은 vruntime을 가진 프로세스를 다음 실행으로 선택합니다.
그렇다면 time slice없이 vruntime을 사용한다고 했는데,스케줄러는 현재 실행 중인 프로세스를 언제 멈추고 다음 프로세스를 실행할지 어떻게 알까요? 만약 CFS가 실행 중인 프로세스들을 자주 바꾸면 fairness는 증가할 수 있지만 너무 잦은 context switch 때문에 성능은 저하될 것입니다. 그렇다고 너무 적게 바꾸면 fairness가 나빠집니다. CFS는 다양한 매개 변수로 이를 해결합니다.
첫 번째는 sched latency 입니다. CFS는 이 값을 사용하여 한 프로세스가 실행되어야 하는 시간을 결정합니다.일반적인 스케줄 지연 값은 48ms입니다. CFS는 전환 전, 이 값을 CPU에서 실행 중인 프로세스 수(n)로 나누어 프로세스의 시간 조각을 결정합니다.
예를 들어, n = 4 프로세스가 실행 중이라면, CFS는 스케줄 지연 값을 n으로 나누어 프로세스당 12ms의 시간 조각을 계산합니다.
그림 9.4는 네 개의 작업(A, B, C, D)이 각각 이 방식으로 두 번의 시간 조각 동안 실행되는 예를 보여줍니다. 처음에는 A, B, C, D 프로세스가 실행 중이지만 어느 순간부터 A, B 작업만 수행합니다. 이렇게 CPU에서 수행되는 작업 수가 줄어들면 CFS는 time slice를 늘립니다.두 개(C, D)는 완료되었으니 남은 두 개가 각각 24ms 동안 라운드 로빈 방식으로 실행됩니다.
그러나 "너무 많은" 프로세스가 실행되고 있다면 이는 너무 작은 시간 조각으로 이어져 너무 많은 컨텍스트 스위칭을 초래할 겁니다.
이 문제를 해결하기 위해 CFS는 또 다른 매개변수인 min granularity 을 추가합니다. CFS는 결코 시간 조각을 이보다 작게 설정하지 않습니다. 즉, 이 매개변수는 아무리 프로세스가 많아도 min granularity보다 time slice가 작아지지 않도록 합니다.
이때 min granularity는 보통 6ms로 설정됩니다. 이를 사용하는 예를 보자면 10개의 프로세스가 있고 time slice를 구한다면 아까의 방식대로라면 48ms / 10 = 4.8ms라는 time slice를 가져야 합니다. 하지만 이젠 min granularity가 있기 때문에 6ms가 되는 것이죠. 이렇게 되면 fairness는 나빠질 수 있지만 효율성 부분에서는 좋아집니다.
또한 CFS는 주기적인 타이머 인터럽트를 사용합니다. 이 인터럽트는 자주 발생합니다(예: 매 1 ms마다). 따라서 CFS는 vruntime을 정확히 추적하므로, 장기적으로 보면 결국 CPU의 이상적인 공유를 근사하게 됩니다.
CFS는 또한 프로세스 우선순위에 대한 제어를 가능케 합니다. 이는 티켓이 아닌, nice level 이라는 고전적인 UNIX 메커니즘을 통해 이루어집니다. nice 매개변수는 프로세스에 대해 -20에서 +19까지 설정할 수 있으며, 기본값은 0입니다. 너무 친절하면, 안타깝게도 스케줄링에서 주목을 받지 못합니다. 긍정적인 nice 값은 낮은 우선순위를, 부정적인 값은 높은 우선순위를 의미합니다.
주어진 우선순위 별 가중치를 사용해서 수식에 따라 프로세스의 time slice를 구합니다.예를들어 A, B 프로세스가 있고 A에는 nice 값을 -5로 B는 0으로 설정합니다.이 설정 값으로 가중치 값을 찾고 위의 식에 대입하여 time slice를 구해보면 A 프로세스는 43, B는 약 14가 나오게 됩니다.
또한 CFS에서 virtual runtime을 계산하는 방법에도 가중치를 사용할 수 있습니다. 위 식(9.2) 을 사용하여 아까 A, B의 virtual runtime 비율을 구해보면 1:3이 됩니다. 즉 A의 시간이 마치 3배 느리게 가는 거처럼 만드는 것입니다.
위에서 언급했듯이, CFS의 주요 초점 중 하나는 효율성입니다. 스케줄러가 다음에 실행할 작업을 가능한 한 빠르게 찾아야 합니다. 리스트와 같은 단순한 데이터 구조는 확장성이 떨어집니다. 따라서 CFS는 이 문제를 레드-블랙 트리를 사용하여 해결합니다.
CFS는 이 구조에 모든 프로세스를 유지하진 않고, 실행 중이거나 실행 가능한 즉 Run, Ready 상태의 프로세스만 이 구조에 저장합니다. 프로세스가 잠들 경우(예를 들어, I/O 완료를 기다리거나 네트워크 패킷이 도착하기를 기다림)엔 트리에서 제거되고 다른 곳에서 추적됩니다.
예를 들어 10개의 작업이 있고, 그들이 가진 vruntime 값이 1, 5, 9, 10, 14, 18, 17, 21, 22, 24라고 가정해 봅시다. 이 작업들을 리스트에 넣는다면, 실행할 작업을찾기 위해 O(n) 연산이 걸립니다. 반면 같은 값을 레드-블랙 트리에 유지하면 (그림 9.5 ) 프로세스들은 vruntime에 따라 트리에 배열되며, 작업시간은 O(log n)입니다.
가장 낮은 vruntime을 가진 작업을 다음에 실행하기로 결정하면,예상되는 문제가 있습니다. A와 B 두 프로세스를 상상해 보세요, 이 중 하나(A)는 지속적으로 실행되고, 다른 하나(B)는 오랜 시간 동안 수면 상태에 있었습니다(예를 들어, 10초). B가 깨어났을 때, 그것의 vruntime은 A보다 10초 뒤처질 것이고, B는 다음 10초 동안 CPU를 독점하며 따라잡게 되고, 이는 A를 굶주립니다.
CFS는 깨어날 때 작업의 vruntime을 변경함으로써 이 문제를 처리합니다. 구체적으로, CFS는 그 작업의 vruntime을 실행 중인 작업 중 최소 vruntime으로 재설정합니다. (트리에는 실행 중인 작업만 포함됩니다).
최소 vruntime 값으로 설정함으로써, 깨어난 작업은 다른 실행 중인 작업들과 비슷한 시작점에서 경쟁을 시작하게 됩니다. 이는 장기적으로 작업 간의 공정한 CPU 시간 분배를 유지하도록 돕습니다.이런 식으로 CFS는 기아상태를 피하지만, 짧은 시간 동안 자주 수면 상태에 들어가는 작업들은 공정한 CPU 시간을 받지 못한다는 단점도 있습니다.
여기서는 비례 분배 스케줄링의 개념을 알아보고 로터리 스케줄링, 스트라이드 스케줄링, 그리고 리눅스의 완전 공정 스케줄러(CFS)에 대해 간략하게 논의했습니다. 로터리는 비율을 달성하기 위해 무작위 방법을 사용하며, 스트라이드는 결정론적으로 이를 진행합니다. 이 장에서 논의된 현재 활발히 쓰이고있는 스케줄러인 CFS는 다이내믹한 시간 조각으로, 부하시 규모를 확장하고 잘 수행하도록 구축되었으며, 오늘날 가장 널리 사용되는 공정 분배 스케줄러입니다.
학습 자료 출처
https://pages.cs.wisc.edu/~remzi/OSTEP
https://icksw.tistory.com/125
'운영체제' 카테고리의 다른 글
| [Operating System] Virtualization-Mechanism: Limited Direct Execution (0) | 2023.12.21 |
|---|---|
| [Operating System] Virtualization-Processes (0) | 2023.12.19 |
