共有回帖数 0 个
-
SD调度器的源码1，可以从kernel.org自己在2.6.22之前找
2，可以在这里在线看
http://lxr.linux.no/#linux+v2.6.22.19/kernel/sched.c
linux调度器从2.4到2.6是个巨大的变革。
2.4内核的调度器我就不详细解说了，其实就是从链表中找最高优先级运行，然
后重新计算，这样的话，负载轻的完全没啥问题，但负载重的话因为是O(n)的查
找，后果会很严重。
2.6的内核从一开始是由现在的主线调度器CFS的作者Ingo Molnar着手重新设计。
最大的特色是这是一个由两个大小是MAX_PRIO(默认是140)的优先级数组组成。
每次调度的时候会从active数组抽取最高优先级的队列头的第一个进程来调度，
调度结束后进程的优先级会用进程的睡眠时间和运行来重新计算，然后放到expired
数组，也就是动态优先级。这样pick_next的时间复杂度就变成了1，并且改善了“一点”
的交互性。但害处也是有的，这样的优先级判断其实是不准确的，在程序下稍作手脚就会
影响系统的交互式进程的响应了。
SD调度器全名是Staircase-Deadline，这个调度器由Con Kolivas开发，
SD调度器的进程的优先级是静态的，最基础的优先级来源于task_struct结构体的
static_prio，也就是用户的nice值，sd调度器的运行队列结构体如下：
struct rq {
spinlock_t lock;
unsigned long nr_running;
unsigned long raw_weighted_load;
unsigned long long nr_switches;
unsigned long nr_uninterruptible;
unsigned long expired_timestamp;
unsigned long long most_recent_timestamp;
struct task_struct *curr, *idle;
unsigned long next_balance;
struct mm_struct *prev_mm;
struct prio_array *active, *expired, arrays[2];
int best_expired_prio;
atomic_t nr_iowait;
struct lock_class_key rq_lock_key;
};
大家把SMP和SCHEDSTATS先忽略了。首先调度器结构体成员lock就是runqueue的自旋锁，
是用来确保多CPU的安全。nr_running是指在该CPU的runqueue上的TASK_RUNNING进程的个数。
nr_switches是上下文切换的次数。nr_uninterruptible是TASK_UNINTERRUPTABLE睡眠进程的个数
curr是当前运行着的进程，active, expired, arrays就是运行队列了，不过可以把expired
给忽略了，因为SD调度器是多级反馈队列。
struct prio_array {
unsigned int nr_active;
DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_PRIO];
};
nr_active是多级反馈队列里的进程个数。
bitmap是代表对应优先级的队列头有没有进程。
然后queue你懂的，是队列头
SD调度器的策略就是这样：首先每个进程的初始优先级都是static_prio，也就是进程原本
应该在queue队列头数组的static_prio位置。当一个进程运行掉所有时间片，那么进程的
优先级就会降1。
假如一个进程运行完时间片，然后他的优先级是0，那么就会掉到1.
+-------------+
| -1 |
+-------------+
| 0 |-----+
+-------------+ |
| 1 | ---+
+-------------+
| 2 |
+-------------+
那么进程的优先级如果彻底降到最后然后又没办法反弹了，那么不是
等于被憋死在最低优先级了么？当然不是，SD调度器在碰到这种情况的时候，
进程的优先级会回到static_prio
好处就体验在这了。低优先级的进程比如那些计算什么什么算式啊，
那些的优先级就会不断的下降，然后又回到原来的优先级。而高优先级的
进程呢？就会保留着剩下的时间片，然后站在台阶上，很慢很慢的下降
其实这样呢，还有一个秘密，那就是如果进程在运行少于1毫秒后睡眠
或者yield，那么优先级就会一直保持。抢占的过程很简单，就
是进程优先级大于或等于当前运行进程的优先级这样的话，那么就抢占成功
被抢占的进程的时间片和优先级会保留，高优先级的进程就能获得很好的
响应，然后低优先级的进程因为有这种优先级下降然后反弹的策略，
所以不会因为长期有高优先级进程在队列而饿死，但又不会很容易霸占到
高优先级进程的执行权，互相的在平衡者，然后结果自然就是公平调度了。
写这个调度器分析的原因呢，是因为这个调度器实在是很适合在桌面的使用，而且十分的高效，也把多级反馈队列用到了极致。我的RIFS调度器里面的优先级下降跟SD调度器一样也是用了类似的反弹机制，不过我的反弹是直接回到原来的优先级的。而且如果进程运行时间少于time_slice() / 2的话，我的调度器会增加优先级的。不得不说，SD调度器真的很经典，很好而且响应力也真的很不错。
也希望Linux的调度器重视普通桌面用户的体验，官方也可以在源码内用make menuconfig，make xconfig的方法来让用户选择是普通桌面电脑还是服务器，不要一味的偏袒。我如果不是情非得已我是不会有写RIFS调度器这个考虑的
楼主 2015-11-05 13:38 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
