Chinaunix首页 | 论坛 | 博客
  • 博客访问: 449067
  • 博文数量: 143
  • 博客积分: 6159
  • 博客等级: 准将
  • 技术积分: 1667
  • 用 户 组: 普通用户
  • 注册时间: 2010-08-25 23:08
文章分类

全部博文(143)

文章存档

2013年(1)

2012年(11)

2011年(55)

2010年(76)

分类:

2011-01-09 12:38:19


DRR在Linux中的实现

前面介绍了DRR算法,这里我们看看如何在Linux中实现DRR。从上面DRR介绍中,我们知道,对于DRR整个调度算法有一个active_queue,每个class都有一个deficit和weight。Linux中的DRR算法实现于net/sched/sch_drr.c,从中可以发现定义如下:

struct drr_sched {
     struct list_head active;
     struct tcf_proto *filter_list;
     struct Qdisc_class_hash clhash;
};
struct drr_class {
     struct Qdisc_class_common common;
     unsigned int refcnt;
     unsigned int filter_cnt;
 
     struct gnet_stats_basic_packed bstats;
     struct gnet_stats_queue qstats;
     struct gnet_stats_rate_est rate_est;
     struct list_head alist;
     struct Qdisc *qdisc;
 
     u32 quantum;
     u32 deficit;
};


在这里filter_list用于保存挂在这个Qdisc下面的filter,用于对子class进行进一步分类。每个class的weight用quantum表示,即每次class的deficit用完后一次添加的数目。

其enqueue函数如下(有删节):

static int drr_enqueue(struct sk_buff *skb, struct Qdisc *sch)
{
     struct drr_sched *q = qdisc_priv(sch);
     struct drr_class *cl;
 
     cl = drr_classify(skb, sch, &err); /* 首先进行利用q->filter_list进行分类 */
     len = qdisc_pkt_len(skb);
     err = qdisc_enqueue(skb, cl->qdisc); /* enqueue到子class的Qdisc中 */
     if (unlikely(err != NET_XMIT_SUCCESS)) {
          。。。
           return err;
     }
 
     if (cl->qdisc->q.qlen == 1) { /* class qdisc原来为空 */
           list_add_tail(&cl->alist, &q->active); /* 添加到active queue中 */
           cl->deficit = cl->quantum; /* 同时更新deficit到最大 = quantum */
     }
 
     /* 更新统计信息 */
     cl->bstats.packets++;
     cl->bstats.bytes += len;
     sch->bstats.packets++;
     sch->bstats.bytes += len;
 
     sch->q.qlen++;
     return err;
}


接下来看dequeue的实现 (有删节):

static struct sk_buff *drr_dequeue(struct Qdisc *sch)
{
     struct drr_sched *q = qdisc_priv(sch);
     struct drr_class *cl;
 
     while (1) { /* 在此循环中对active queue进行RR调度 */
           cl = list_first_entry(&q->active, struct drr_class, alist); /* 取出第一个class */
           skb = cl->qdisc->ops->peek(cl->qdisc);
           if (skb == NULL) /* 没有pkt,退出 */
                goto out;
 
           len = qdisc_pkt_len(skb);
           if (len <= cl->deficit) { /* 一个可调度的class */
                cl->deficit -= len; /* 更新class的deficit */
                skb = qdisc_dequeue_peeked(cl->qdisc);
                if (cl->qdisc->q.qlen == 0) /* 此class调度后为空,移出active queue */
                     list_del(&cl->alist);
                sch->q.qlen--;
                return skb; /* 返回这个pkt */
           }
 
           cl->deficit += cl->quantum; /* class不可调度,顺便更新其下一轮的deficit */
           list_move_tail(&cl->alist, &q->active); /* class移到active queue末尾,等待下一轮 */
     }
out:
     return NULL;
}


待续

阅读(1718) | 评论(0) | 转发(3) |
给主人留下些什么吧!~~