[스케쥴러] Efficient and Scalable Multiprocessor Fair Scheduling Using Distributed Weighted Round-Robin

초록

 어떤 운영체제이던 간에  Fairness (Fairness)을 만족시키는 것은 매우 중요한 요소이다. 하지만 현존하는 운영체제의 스케쥴링 알고리즘들은  Fairness을 만족시키지 못하거나 멀티프로세서에 확장성이 떨어진다. 이러한 문제들은 여러개의 코어를 갖는 프로세서가 생김에 따라 더 심각해진다. 이번 논문에서는 Distributed Weighted Round Robin (DWRR)이라는 새로운 알고리즘을 제시할 것이다. 이 알고리즘은 분산된(distributed) 큐를 갖고 있으면서 기존에 있는 스케쥴러에 약간의 오버헤드만을 가져다줌으로써 높은 효율성(efficiency)와 확장성(scalability)를 갖는다. 이러한 성질 외에 DWRR은 사용자가 설정한 가중치(weight)에 비례한 시간만큼 실행하면 그 오차는 상수의 오류 경계(constant error bound)를 만족한다. DWRR은 기존에 존재하는 스케줄러 정책(policy)와 융화되어서 동작하게 되고 이러한 성질은 여러 운영체제에 DWRR을 쉽게 적용할 수 있게해준다. 이러한 DWRR의 성질을 보이기 위해서 이번 연구에서는 DWRR은 linux-2.6.24, linux-2.6.32에 적용하였다. 이번 연구의 평가을 통해서 DWRR이 정확한  Fairness 을 만족함과 동시에 기존의 스케쥴러와 비슷한 성능(performance)을 가짐을 보였다. 

 Keywords 공정한 스케쥴링,  가중치 기반의 분산 순차 순환 대기산법(Distributed Weighted Round Robin) 


1. 서론

  운영체제와 네트워크, 실시간 시스템 등에서 가중치에 비례한 실행 시간을 갖게하는 스케쥴러는 오랜기간 연구되어왔다. 지금까지 일반적인 접근 방식은 각 태스크에 가중치를 주고, 스케쥴러가 그 가중치에 해당하는 시간만큼 수행될 수 있게 하는 것이다.[26] 완벽한  Fairness 를 얻기 위해서는 매우 작은 스케쥴링 단위시간을 필요로 한다. 하지만 이는 실제적으로 구현할 수 없기 때문에 실제로 사용되는 스케쥴러는 이 작은 스케쥴링 단위시간을 갖게 하고, 적은 에러 한계(error bound)를 갖는 것을 목표로 한다. 

 이러한 가중치에 비례한 시간을 할당하는 스케쥴러는 알기쉽고 직관적이긴 하지만 Mac OS, Solaris, Windows, 2.6.23이전 버젼의 리눅스 같은  일반적으로 사용되는 OS들에는 적용되지 않았었다. 이러한 OS에는 자원 굶주림(starvation)을 방지하기 위한  Fairness에 대한 정확하지 않는 개념이 적용되었고, 적당히 공평하다고 여겨졌다. 이러한 설계들에서는 스케쥴러는 우선순위가 높은 쓰레드를 먼저 수행시켰다. 각 쓰레드는 얼마만큼의 시간동안 수행될지를 의미하는 time slice를 할당받는다. 높은 우선순위를 가질 수록 더 많은 시간을 할당받는다. 우선순위에 비례해서 시간을 할당받지 않기 때문에 얼마만큼 더 많은 시간을 할당받는지에 대한 논의가 있었다.  Fairness 를 돕기 위해서 스케쥴러는 특정한 경우 task의 우선순위를 변경한다. 어떤 task가 오랜 시간 수행을 하지 않았을 경우가 이에 속하는데, 이러한 상황을 정의하는 것과 얼마나 우선순위를 바꿀 것인지에 대한 부분이 heuristic하다고 여겨졌다. 

   Fairness 에 대한 명확한 정의가 없기 때문에 생기는 스케쥴러의  unfairness 는 세 가지의 문제점을 야기할 수 있다. 첫 번째로 이는 CPU 과부하 시 starvation과 poor I/O performance의 원인이 될 수 있다.  예를 들어서, 우리가 32개의 CPU-intensive 쓰레드를 dual-core 환경에서 돌렸을 때 OS 자체에 starvation이 생겨서 응답이 느려지는 현상이 생겼다. 두 번째로 정확한  Fairness 의 부재는 실시간 어플리케이션을 잘 지원할 수 없다. 왜냐하면 우선순위에 비례해서 시간을 할당하는 것만이 멀티프로세서에서 주기적인 실시간 task들을 스케쥴하는 것이라고 알려졌기 때문이다[1, 29]. 세 번째로 이는 데이터 센터와 같은 서버 환경에 적합하지 않는다. 기존의 데이터 센터와 달리 여러개의 코어가 들어가는 프로세서는 하나의 server에서 여러 사용자에게 서비스를 제공한다. 이러한 환경에서 하나의 멀티프로세서로 이뤄진 시스템은 여러 사용자들에게 서비스를 제공하고 이 때 서비스의 질(Quality of Service) 척도를 만족해야 한다. 

 기존에 많은 비례적으로 공평한 스케쥴링 알고리즘들이 존재한다. 하지만 그 어떤 것이도 큰 크기의 멀티프로세서에서 실용적인 해답이 되지 못한다. 대부분의 알고리즘들은 global run queue들을 사용하기 때문에 비효율적이고 non-scalable하다. 이러한 전역 구조체에 접근하기 위해서는 data race를 막기 위해서 locking을 사용하는데 이는 CPU의 수가 늘어날 수록 극심한 serialization과 lock contention을 야기한다. 게다가 전역 구조체에 쓰기 위해서는 다른 CPU들에 공유된 캐시를 비우게되고, 이 때문에 많은 bus traffic으로 인한 성능 하락이 생긴다. CPU 마다 run queue를 갖고 있다면 이러한 문제를 해결할 수 있지만  Fairness 가 약하거나 latency-sensitive 한 응용프로그램에 적합하지 않다. 앞으로 멀티코어 구조가 늘어날 것이기 때문에 운영체제가 효율적이고 scalabe한 구조를 갖고 공평한 스케쥴링을 할 수 있어야한다. 

 이 논문에서는 다음의 성질을 갖는 Distributed Weighted Round-Robin(DWRR)이라는 새로운 스케쥴러를 제시하였다. 

 ο 정확한  Fairness . Generalized Processor Sharing(GPS) model [26]을 이용해서 DWRR은 정확한 비례적으로 정확한  Fairness 를 만족하면서 CPU와 쓰레드 수에 영향을 받지않는 constant error bound를 갖는다. 
 ο 효율적이고 scalable한 operation. DWRR은 per-CPU run queue를 사용하고, 쓰레드가 동적으로 오고, 가고, weight를 변화시켜도 기존의 운영체제 스케쥴러에 적은 overhead를 가한다. 
 ο 신축성있는 user control. DWRR은 우선순위에 기반해서 가중치를 설정하고 QoS를 control하기 위해서 쓰레드의 가중치를 바꿀 수 있는 추가적인 기능을 제공한다. 
 ο 높은 performance. DWRR은 기존에 있는 스케쥴러 정책과 같이 동작하기 때문에 latency나 throughput같은 그 시스템의 속성을 유지하기 때문에 높은 performance를 만족함과 동시에 정확한  Fairness 를 가능케한다. 

 이 논문의 나머지 부분은 다음과 같이 구성된다. Section 2 에서는  배경이론과 관련 연구에 대해서 논하였다. Section 3 은 DWRR 알고리즘에 대해서 설명하였다. Section 4 에서는 Linux에 적용을 설명하였고, Section 5 에서는 실험을 통해서 DWRR이 정확한  Fairness 와 낮은 overhead를 가짐을 보였다. Section 6 에서는 DWRR이  Fairness 에 대한 formal analysis를 하였고, constant error bound에 대한 증명을 하였다. Section 7 에서 마무리를 하였다. 


2. 공평한 스케쥴링에 대한 배경이론

 Generalized Processor Sharing (GPS) 는 완벽한  Fairness 를 만족하는 가상의 스케쥴링 알고리즘이다. 모든 실용적인 스케쥴러는 GPS를 근사한 것이고 이것을 기준으로  Fairness  를  측정한다. 
 
 2.1 GPS 모델

 CPU가 P개 있고, 쓰레드가 N개 있다고 가정하자. 이 때 각 쓰레드 i가 가중치 '$w_i$'를 갖고 있을 때 다음의 두 성질을 만족하면 그 스케쥴러는 완벽히 공평하다. 

 (1) work-conserving. 돌아야할 쓰레드가 있을 때 CPU가 idle 상태로 빠지지 않는다. 
 (2) 쓰레드의 가중치에 정확히 비례해서 스케쥴러가 CPU time을 할당한다.
 이러한 스케쥴러는 일반적으로 Generalized Processor Sharing (GPS) 라고 불린다. '$S_i(t1, t2)$'가 시간 구간 '$[t1 t2]$'에서 쓰레드i가 할당받은 시간을 의미한다고 하자. 이때 GPS 스케쥴러는 다음과 같이 정의된다.[26] 

정의 1. GPS 스케쥴러는 다음의 성질을 만족한다. 
$$\frac{S_i(t_1, t_2)}{S_j(t_1, t_2)} \le \frac{w_i}{w_j}, j= 1,2, . . . , N$$ 
 가중치 '$w_i$'와'$w_j$'가 고정되어 있고 '$ [t_1, t_2] $' 인 구건에서 어떤 쓰레드 '$i$'에 대해서 만족을 한다. 

 
이 정의에서 부터, GPS는 다음 두 가지의 성질을 갖는다. 

성질 1. 만약 고정된 가중치를 갖는 쓰레드 i와 j가 '$[t_1,t_2]$'에서 연속적으로 runnable하다면, GPS는 다음의 성질을 만족한다. 
$$\frac{S_i(t_1,t_2)}{S_j(t_1,t_2)} = \frac{w_i}{w_j}$$ 

성질 2. 만약 runnable 쓰레드의 집합인 '$\phi$'가 있고, 그들의 가중치가 '$[t_1,t_2]$'에서 고정되어있다면 '$\phi$'에 속하는 어떤 쓰레드라도 GPS는 다음의 성질을 만족한다. 
$$ S_i(t_1,t_2)= \frac{w_i}{\sum_{j\in\phi} w_j}(t_2-t_1)P$$  
 이전에 했던 대부분의 연구는 uniprocessor 에 GPS 스케쥴링을 적용했었다. multiprocessor에 있어서는 특정한 가중치를 주는 것이 불가능하므로 GPS는 이론적으로 불가능하다.[9] 예를 들어서 두 개의 CPU를 갖는 시스템이 두 개의 쓰레드를 갖고 있고, '$w_1=1$'이고 '$w_2=10$'이라고 하자. 하나의 쓰레드는 하나의 CPU에서 돌 수 있으므로 work-conserving하면서 쓰레드2가 쓰레드1보다 10배 많은 시간을 할당 받는 것은 불가능하다. [9]에서는 다음과 같은 정의를 제안한다. 

정의 2. 어떤  '$ [t_1, t_2] $' 인 구간에서 다음의 상황에서 쓰레드 i의 가중치 '$w_i$'는 구현불가능하다. 
$$\frac{w_i}{\sum_{j\in\phi} w_j} > \frac{1}{P}$$
 여기서 '$phi$'는 runnable thread의 집합이고, P는 CPU의 개수이다. 

 구현 불가능한 가중치는 시스템의 허용을 초과하는 요구를 의미한다. [9] 에서 P개의 CPU로 이뤄진 시스템에서 P-1개보다 적은 쓰레드가 있을 경우 구현이 불가능함을 보였다. 이러한 정의를 추가하면 어떤 multiprocessor 시스템에서도 GPS가 정의될 수 있다.

 GPS는 이상적으로만 존재하는데 그 이유는 정의 1을 만족시키기 위해서는 무한히 작은 스케쥴링 quanta로 스케쥴링을 해야하기 때문이다. 그러므로 모든 실용적인 스케쥴러는 GPS를 근사적으로 모방하고 다음의 두 척도로 그 성능이 평가된다. 하나는  Fairness 이고, 다른 하나는 시간 복잡도(time complexity)이다. Lag 은  Fairness  를 평가하는 척도로 흔히 사용된다.[1] lag의 정의는 다음과 같다.

정의 3.  어떤  '$ [t_1, t_2] $' 인 구간에서 쓰레드 i의 lag은 다음과 같다. 
$$lag_i(t) = S_{i,GPS}(t_1,t)-S_{i,A}(t_1,t)$$ 
 positive lag값은 쓰레드가 GPS에 비해서 시간을 적게 받았다는 것을 의미하고, negative lag 값은 해당 쓰레드가 GPS에 비해서 시간을 많이 받았다는 것을 의미한다. 모든  Fairness  를 추구하는 스케줄러는 이 positive lag과 negative lag을 bound하려고 노력한다. 즉 이 값이 작으면 작을수록 스케쥴러의  Fairness 에 대한 성능이 뛰어난 것이다. 만약 이 bound가 작은 상수로 bound된다면 그 알고리즘은 강한  Fairness  를 가질 것이다. 하지만 만약 이 lag이 O(N)으로 bound된다면 나쁜  Fairness  를 갖는 것이다. 여기서 N은 쓰레드의 수를 의미한다. 

 2.2  이전의 연구 
 
  공평한 스케쥴링은 운영체제, 네트워크 그리고 실시간 시스템에서 사용된다. 한 분야에서 만들어진 알고리즘이 다른 분야에도 적용디 되기 때문에 우리는 공평한 스케쥴링을 크게 세 개의 category로 나눴다. 

 2.2.1 Virtual-time 기반 알고리즘

  이 category에 속하는 알고리즘들은 각 task나 네트워크 packet에 virtual time을 정의한다. 정밀한 알고리즘을 통해서 이 방법으로는 constant lag bound를 가지며 가장 공평한 스케쥴링이 가능하다. 이 알고리즘의 단점은 각 task를 정렬하는데 시간이 걸리는 것이고 이것은 '$O(logN)$'을 필요로 하거나 어떤 경우에는 '$O(NlogN)$' 시간이 걸린다. 이때 N은 task나 네트워크 flow의 수이다. 이 알고리즘의 강한  Fairness 는 집중된 run queue에 의존하기 때문에 생기는데 이는 효율성과 scalability를 저해시킨다. 

 [네트워크 부분 생략]
 [실시간 시스템 생략]

 일반적인 운영체제에서는, Surplus Fair Scheduling(SFS)[9], Borrowed-Virtual-Time(BVT)[11], Smart-time Fair Queuing(SFQ)[14], Completely Fair Scheduler(CFS) 는 모두 비슷한 알고리즘을 사용을 하고 constant lag bound와 O(N) negative bound를 가진다.  

 2.2.2 Round-robin 알고리즘

  Round-robin 알고리즘은 가중치에 비례한 packet의 수를 전송하는 Weighted Round-Robin(WRR)으로 확장된다. Round-robin 알고리즘은 시간 복잡도가 O(1)이기 때문에 매우 효율적이다. 하지만 이들은 일반적으로 O(N) lag bound를 갖는다. 그럼에도 불구하고 만약 task나 flow의 가중치가 상수로 bound되고, 실전에서 합리적인 가정이 지켜진다면 constant lag bound를 가질 수 있다. 그러므로 이 RR 알고리즘은 효율적이고 scalable한 공평한 스케쥴링에 적합하다고 할 수 있다. 

 불행이도 현재 존재하는 대부분의 RR 알고리즘들은 멀티프로세서에 non-scalable하다. 왜냐하면 Group Ratio Round Robin(GRRR) [6], Smoothed Round-Robin(SRR) [17], Virtual-Time Round-Robin(VTRR) [25], Deflict Round-Robin(DRR) [28]과 같이 이것들은 하나의 queue나 weight matrices를 사용하기 때문이다. 우리가 아는 한 Grouped Distributed Queues(GDQ) [7]이 constant positive, negative lag bound를 갖고, distributed queue를 같는 유일한 일반적인 운영체제의 스케쥴링 알고리즘이다. 하지만 이를 적용하기 위해서는 dynamic properties나 load balancing과 같은 기존 스케쥴러의 정책을 많이 고쳐야 하기에 실용성이 크지 않다. 만약 GDQ를 적용핟마녀 성능의 하락이 생길 수 있다. 이와 반대로 DWRR은 기존 스케쥴러의 정책을 대부분 따르기 때문에 높은 performance를 낼 수 있다. 

 2.2.3 그 외 알고리즘
  [생략]

3. Distributed Weighted Round Robin

 DWRR은 FreeBSD 5.2, Linux 2.6, Solaris 10, Windows Server 2003과 같은 per-CPU run queue를 사용하는 기존에 존재하는 스케쥴러 위에서 동작한다. DWRR은 이름에서도 알 수 있듯이 WRR의 Distributed한 버젼이다. WRR이 문제는 global queue를 필요로 하다는 것이었다. DWRR에서는  Fairness  를 얻기 위해서는 thread가 매번 같은 순서로 동작될 필요는 없고 어떤 순서로 동작을 하던 그들의 한 round에서 총 수행 시간만 그들의 weight에 비례해서 받으면 되다는 것을 알았다. 

 DWRR은 각 CPU에 대해서 초기값이 0인 round number를 가진다. 각 쓰레드의 round slice를 '$w\cdot B$'라고 정의하자. 여기서 w는 각 쓰레드의 가중치를 의미하고, B는 system-wide 상수인 round slice이다. DWRR에서 round는 시스템의 모든 쓰레드가 자신의 round slice만큼 수행을 하는데 걸리는 최소한의 시간이다. 각 쓰레드의 round slice는 각 round에서 자신에게 할당받은 싱행 시간을 의미한다. 예를 들어서 하나의 쓰레드의 가중치가 2이고, B가 30ms라면 그 쓰레드는 한 round에서 60ms만큼 수행될 수 있다. B의 값은 구현상의 선택이다. 이 B가 작으면 작을 수록  Fairness  를 좋아지지만 performance는 떨어진다. 

 만약 하나의 쓰레드가 round slice만큼 수행을 했다면 우리는 그 쓰레드가 해당 round를 마쳤다고 표현을 할 것이다. 그러므로 DWRR은 그 쓰레드를 CPU run queue에서 제고할 것이다. 만약 CPU의 모든 쓰레드가 수행되었다면 DWRR는 다른 CPU에 있는 수행되지 않은 쓰레드를 탐색하고 가져올 것이다. 만약 아무것도 탐색되지 않았다면 CPU는 자신의 round number를 올리고, 자신이 가지고 있는 쓰레드들이 다음번 round에서 돌 수 있도록 full round slice를 준다. 

 3.2 알고리즘 

  이 section에서는 DWRR을 구체적으로 설명하곘다. 각 CPU에 DWRR은 local fairness를 얻기 위해서 round slicing을 하고, global fairness를 얻기 위해서 CPU간에 round balancing을 한다. 

 3.2.1 Round Slicing
  

 기존에 각 cpu에 있던 run queue를 round-active라 했을 때 DWRR은 하나의 round-expired queue를 추가한다. 여기서 queue는 어떤 구조체로도 정의될 수 있다. 예를 들어 많은 운영체제에서는 이것을 list의 array로 구현을 한다. 하지만 Linux의 CFS에선 이를 red-black tree를 이용해서 구현한다. 이 구조체가 무엇이든 간에 DWRR은 이것을 round-active와 round-expired 모두에 적용한다. 그림 1은 이들 data 구조를 보여준다. 
 

 개별 CPU에서 round-active와 round-expired는 초기에 비어있고 round number는 0이다. 스케쥴러는 각 runnable 쓰레드를 round-active에 넣는다. round-active에 있는 모든 쓰레드들에게 CPU의 round값은 그 쓰레드들이 돌은 round를 의미한다. DWRR는 쓰레드를 dispatch하는 순서는 신경쓰지 않는다. 예를 들어 기존의 스케쥴러가 해당 쓰레드를 우선순위를 기반으로 선택한다면 DWRR도 그 정책을 따라간다. 이 특성은 DWRR로 하여근 latency-sensitive한 어플리케이션에게 기존의 스케쥴러와 비슷한 response time을 가능하게 한다. 

 어떤 기존의 스케쥴러라도, 하나의 쓰레드는 일정시간 수행되고, 다른 쓰레드가 수행되고 (quantum expiration) 또 다시 수행된다. DWRR은 각 쓰레드의 각 round에서 cumulative run time을 모니터한다. 이 값이 쓰레드의 round slice를 넘었다면 DWRR은 그 쓰레드를 preempt하고, 이를 round-active에서 round-expired로 넘긴다. 이 모든 동작은 O(1) 시간에 일어나고 이는 CPU에 쓰레드가 몇 개이던 상관없이 일정함을 뜻한다. 그러므로 언제든 DWRR은 다음과 같은 변하지 않는 성질을 유지한다. 어떤 CPU가 R에 있을 때 round-expired에 있는 쓰레드는 R을 마치고 R+1을 기다리고 있는 것이다. 이제 CPU가 R에서 R+1로 넘어갈 때에 대해서 논의해보자. 

 3.2.2 Round Balancing

 CPU들 간에  Fairness  를 보장하기 위해서 DWRR은 모든 CPU의 round값이 최대 1 차이가 나도록 한다. Section 6 에서는 이렇게 할 경우 왜 강한  Fairness 가 보장되는지를 증명하였다. 직관적으로 이 성질은  Fairness  를 보장하는데 왜냐하면 각 쓰레드들이 주어진 시간 간격 동안 모두 같은 round만큼 수행됨을 의미하기 때문이다. (그들이 갖고 있는 round slice를 같은 수 만큼 돌았다.) 이 성질을 강화하기 위해서 CPU가 해당 round를 마쳤을 때 (round-active가 비었을 때) 해당 CPU는 다른 CPU의 쓰레드를 가져오기 위해서round balancing을 수행한다. 

 round balancing을 돕기 위해서 DWRR은 CPU들의 round값 중에서 가장 높은 값을 의미하는 highest값을 항상 가지고 있다. Section 3.2.4 에서 이 전역 변수를 이용해서 scalability에 대해서 설명할 것이다. round(p)가 p CPU의 round number라고 하자. p의 round-active가 비었다면, DWRR은 다음과 같이 round-balancing 을 한다. 
 

 p의 round-active가 비었다면, round-balancing을 수행한다. 

 step 1: 만약 round(p)가 highest이거나 p의 round-expired가 비었다면 
(i) DWRR은 round가 highest이거나 highest-1인 다른 CPU들의 현재 실행 중이 아닌 쓰레드들을 살펴본다. 이들 쓰레드들은 highest에 있는 CPU에 있는 round-active나 highest-1에 있는 CPU의 round-expired에 있다. 
(ii) 만약 step i에서 조건을 만족하는 쓰레드를 찾았다면 DWRR은 이 중에서 X개를 p의 round-active로 옮긴다. X의 값은 performance와 상관이 있는 값이다. 여기서 주의할 점은 X개를 옮긴 후에 이들을 모두 수행하면 다시 round-balancing을 수행하게된다. 
(iii) 만약 step i에서 쓰레드를 못찾았다면 p는 다음 round로 진행한다. 즉 DWRR은 step 2로 이동한다. 

 step 2: 만약 p의 round active가 여전히 비었다면 
(i) DWRR은 p의 round-active와 round-expired를 서로 바꾼다. 
(ii) 만약 새롭게 바뀐 round-active가 비어 있다면 해당 run queue는 task가 없기 때문에 DWRR은 p를 idle상태로 놓고, round(p)를 0으로 한다. 그렇지 않다면 round(p)를 1올린다. 그리고 만약 새로운 round(p)가 highest보다 크다면 highest를 update한다. 

 그림 2는 이 알고리즘은 flowchart에 요약한다. 대부분의 운영체제는 run queue가 비었을 때 비슷한 행동을 하기 때문에 이러한 동작들은 기존에 있는 스케쥴러에 약간의 오버헤드만 부담한다. 예를 들어 리눅스 2.6, Solaris 10, Windows Server 2003은 모두 idle CPU로 load balancing을 하기 위해 다른 CPU의 쓰레드를 찾는다. DWRR은 이 동작을 쓰레드가 migrate할 수 있는 CPU의 set을 한정시키도록 간단히 변경을 한다. 이 알고리즘의 성능을 보이기 위해서 리눅스에 적용을 하였다. 

 p가  현재 round-active가 비니 CPU라고 하자. 이때 DWRR은 round가 highest나 highest-1인 CPU를 검색하고, highest-1인 CPU를 '$p_a$'라고 하면 DWRR은 '$p_a$'의  round-expired에 있는 [X/2]의 쓰레드를 p로 옮긴다. 이 때 X는 '$p_a$'의 round-expired에 있는 쓰레드의 수이다. DWRR은 또한 round가 highest이거나 highest-1인 CPU 중에서 load가 가장 많은 것을 찾는다. load는 round-active에 있는 쓰레드의 수를 의미한다. 이렇게 찾은 '$p_b$'의 round-expired에서 Y개의 쓰레드를 p의 round-active로 옮긴다. 여기서 Y는 평균 CPU 로드이다(전체 시스템의 쓰레드 수를 전체 CPU 수로 나눈 것).

 3.2.3 Dynamic Events and Infeasible Weights
 [생략] - 새로운 쓰레드가 생기면 DWRR은 가장 load가 적은 CPU에 넣는다. infeasible weight에 대한 조정이 필요없다. 

 3.2.4 Performance Considerations
 [생략] - 일시적인 imbalance는 중요하지 않다. (locking mechanism은 좋지 않다.)

 3.3. Example
 

 그림3은 DWRR의 간단한 동작을 보여준다. 두 개의 CPU와 세 개의 쓰레드가 있고, 모든 쓰레드의 가중치는 1, round slice도 1이라고 하자. time 0 에 A와 B는 CPU 0에 있고, C는 CPU 1에 있다. time 1 에는 A,B는 모두 0.5만큼 수행했고, C는 1만큼 수행해서 round-expired로 옮겨졌다. round-balancing이 일어나서 CPU 0 에 있는 B를 CPU 1 으로 옮긴다. time 1.5 가 되었을 때 A와 B 모두 0.5를 채워서 자신의 round slice를 모두 수행하고 round-expired로 옮긴다. 모든 쓰레드가 수행을 다 했으므로 round-active와 round-expired를 바꾸고 round를 0에서 1로 옮긴다.  

 
 4. Implementation

 리눅스의 O(1) 스케쥴러의 경우  Fairness 가 좋지 못하다. CFS는 local fairness는 뛰어나나 global fairness가 좋지 못하다. O(1) 스케쥴러는 heuristics로 쓰레드 우선순위를 조정하는데 이것이 효율적이 못할때가 많다. CFS와 DWRR을 합치면 정확한  Fairness 와 performance를 가질 수 있을 것이다. 

 5. Experimental Result
 
 






Reference 

[1] S. K. Baruah, N. K. Cohen, C. G. Plaxton, and D. A. Varvel. Proportionate progress: A notion of fairness in resource allocation. Algorithmica, 15(6):600–625, June 1996.
[6] B. Caprita, W. C. Chan, J. Nieh, C. Stein, and H. Zheng. Group ratio round-robin: O(1) proportional share scheduling for uniprocessor and multiprocessor systems. In Proceedings of the 2005 USENIX Annual Technical Conference, pages 337–352, Apr. 2005.
[7] B. Caprita, J. Nieh, and C. Stein. Grouped distributed queues: Distributed queue, proportional share multiprocessor scheduling. In Proceedings of the 25th ACMSymposium on Principles of Distributed Computing, pages 72–81, July 2006.
[9] A. Chandra, M. Adler, P. Goyal, and P. Shenoy. Surplus fair scheduling: A proportional-share CPU scheduling algorithm for symmetric multiprocessors. In Proceedings of the 4th Symposium on Operating Systems Design and Implementation, pages 45–58, Oct. 2000. 
[11] K. J. Duda and D. R. Cheriton. Borrowed-virtual-time (BVT) scheduling: Supporting latency-sensitive threads in a general purpose scheduler. In Proceedings of the 17th ACM Symposium on Operating System Principles, pages 261–276, Dec. 1999.
[14] P. Goyal, X. Guo, and H. M. Vin. A hierarchical CPU scheduler for multimedia operating systems. In Proceedings of the Second Symposium on Operating Systems Design and Implementation, pages 107–121, Oct. 1996.
[17] C. Guo. SRR: An O(1) time complexity packet scheduler for flows in multi-service packet networks. IEEE/ACM Transactions on Networking, 12(6):1144–1155, Dec. 2004.
[25] J. Nieh, C. Vaill, and H. Zhong. Virtual-time round-robin: An O(1) proportional share scheduler. In Proceedings of the 2001 USENIX Annual Technical Conference, pages 245–259, June 2001.
[26] A. K. Parekh and R. G. Gallager. A generalized processor sharing approach to flow control in integrated services networks: The single-node case. IEEE/ACM Transactions on Networking, 1(3):344–357, June 1993.
[28] M. Shreedhar and G. Varghese. Efficient fair queueing using deficit round robin. IEEE/ACM Transactions on Networking, 4(3):375–385, June 1996.
[29] A. Srinivasan. Efficient and Flexible Fair Scheduling of Realtime Tasks on Multiprocessors. PhD thesis, University of North Carolina at Chapel Hill, 2003.