0 引言

Linux调度算法中最基本的一类就是基于优先级的调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的思想。

优先级高的进程先运行，低的后运行，相同优先级的进程按照轮转方式进行调度（Round Robin方法，一个接一个，重复进行）。在包括Linux在内的某些系统中，

优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。

Linux根据以上思想实现了一种基于动态优先级的调度方法。一开始，该方法先设置基本的优先级，然而它允许调度程序根据需求来加、减优先级。举个例子，如果一个进程在

I/O等待上的耗费的时间多于其运行时间，那么该进程明显属于I/O消耗型的进程。它的优先级会被动态的提高。作为一个反例，如果一个进程的全部时间就被耗尽，那么该进程属于处理器消耗型进程---那么它的优先级会被动态地降低。

1 问题的产生

对于经常在交换机，路由器等L2/L3工作的产品，其上不可避免的要用到关于带宽和其他一些资源的调度算法。越是涉及到越底层的东西要求算法越精确，越合理。

常见的调度算法如FCFS、时间片轮换、优先级调度、最短作业优先（有关文章可以参见http://blog.csdn.net/stanmouse/article/details/6067904）。

因为本项目设计到芯片级的调度，采用了DWRR算法，故有机会一览DWRR的神秘之处。

2 DWRR介绍

DWRR来源于RR（Round Ronbin），之后又有WRR（Weighted RR），最后又有DWRR（Deficit Weighted Round Robin）（参见wiki介绍http://wiki.hill.com/wiki/index.php?title=Deficit_weighted_round_robin_queuing和http://en.wikipedia.org/wiki/Deficit_round_robin）。

RR调度算法将所有物理服务器看作一个有向逻辑环，依次轮流调度逻辑环中的各个物理服务器。当各个物理服务器的计算能力不一样对。
RR算法将造成负载不平衡，因为性能较高的服务器分配不到较多的任务。

WRR调度算法允许为每个物理服务器S，指定一个整数权值 (缺省值为1)，以标记服务器的性能(性能较高的服务器具有较高的权值)与动态调度算法相比，WRR算法的调度开销比较小，因此可支持更多的物理服务器；它的缺点是当任务的大小频繁变化时，有可能将大多数长任务调度到同一个物理服务器上，从而导致负载不平衡。

3 DWRR Pseduo Code

Degueue()
    While(TRUE) DO
         IF (ActiveList is NotEmpty) THEN
           i = the index at the head of the ActiveList
           DeficitCounter[i] = DeficitCounter[i] +Quantum[i]
           WHILE (DeficitCounter[i] >0 AND NOT Eemty(Queue[i])) DO
              PaceketSize = Size(Head(Queue[i]))
              IF (PacketSize <= DeficitCounter[i]) THEN
                      Transmit packet at head of Queue[i]
                      DeficitCounter[i] = DeficitCounter[i] -PacketSize
              ELSE
                         Break 
              ENDIF
          ENDWHILE
          IF (Empty(Queue[i])) THEN
                DeficitCounter[i] = 0
                RemoveFromActiveList(i)
          ELSE
                InsertActiveList(i)
          ENDIF
        ENDIF
     ENDWHILE
END DQUEUE

4 DWRR EXAMPLE

在本例中，假设DWRR算法对一个输出端口enabled，并且同时支持三队列。队列一分配50%的带宽，队列二和队列三分别占有25%。

开始时，Credit（或者伪代码中的DeficitCounter）为0.假设round robin起始点在队列一上。在DWRR开始作用在队列一是，Quantum[1]=1000被加到DeficitCounter[1]上，如下图。

在这里，不再详细解释每次循环的意思，每次循环一次列出，很简单，聪明的你，应该能看懂，有问题咱们在讨论。

第一次：

第二次：

第三次：

第四次：

第五次：

第六次：

最后一次：

 

4 DWRR算法的优点和不足

（待补充）