linux内核调度算法（1）

winston

为什么要了解内核的调度策略呢？呵呵，因为它值得我们学习，不算是废话吧。内核调度程序很先进很强大，管理你的LINUX上跑的大量的乱七八糟的进程，同时还保持着对用户操作的高灵敏响应，如果可能，为什么不把这种思想放到自己的应用程序里呢？或者，有没有可能更好的实现自己的应用，使得操作系统能够以自己的意志来分配资源给自己的进程？

带着这两个问题来看看KERNEL。首先回顾上我们开发应用程序，基本上就两种类型，1、IO消耗型：比如hadoop上的trunk服务，很明显它的消耗主要在IO上，包括网络IO磁盘IO等等。2、CPU消耗型，比如mapreduce或者其他的需要对大量数据进行计算处理的组件，就象对高清视频压缩成适合手机观看分辨率的进程，他们的消耗主要在CPU上。当两类进程都在一台SERVER上运行时，操作系统会如何调度它们呢？现在的服务器都是SMP多核的，那么一个进程在多CPU时会来回切换吗？如果我有一个程序，既有IO消耗又有CPU消耗，怎么让多核更好的调度我的程序呢？


又多了几个问题。来看看内核调度程序吧，我们先从它的优先队列谈起吧。调度程序代码就在内核源码的kernel/sched.c的schedule函数中。
首先看下面的优先级队列，每一个runqueue都有。runqueue是什么？下面会详细说下，现在大家可以理解为，内核为每一颗CPU分配了一个runqueue，用于维护这颗CPU可以运行的进程。runqueue里，有几个成员是prio_array类型，这个东东就是优先队列，先看看它的定义：
struct prio_array {        unsigned int nr_active;    表示等待执行的进程总数        unsigned long bitmap[BITMAP_SIZE];    一个unsigned long在内核中只有32位哈，大家要跟64位OS上的C程序中的long区分开，那个是64位的。那么这个bitmap是干什么的呢？它是用位的方式，表示某个优先级上有没有待处理的队列，是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级，我只需要四位就能表示某个优先级上有没有进程要运行，例如优先级是2和3上有进程，那么就应该是0110.......非常省空间，效率也快，不是吗？        struct list_head queue[MAX_PRIO];     与上面的bitmap是对应的，它存储所有等待运行的进程。};

看看BITMAP_SIZE是怎么算出来的：#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
那么，LINUX默认配置（如果你用默认选项编译内核的话）MAX_PRIO是140，就是说一共内核对进程一共定义了140种优先级。等待某个CPU来处理的进程中，可能包含许多种优先级的进程，但，LINUX是个抢占式调度算法的操作系统，就是说，需要调度时一定是找到最高优先级的进程执行。上面的BITMAP_SIZE值根据MAX_PRIO算出来为5，那么bitmap实际是32*5=160位，这样就包含了MAX_PRIO的140位。优先级队列是怎么使用的？看2649行代码：idx = sched_find_first_bit(array->bitmap);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计：

2. static inline int sched_find_first_bit(unsigned long *b)
3. {
4.         if (unlikely(b[0]))
5.                 return __ffs(b[0]);
6.         if (unlikely(b[1]))
7.                 return __ffs(b[1]) + 32;
8.         if (unlikely(b[2]))
9.                 return __ffs(b[2]) + 64;
10.         if (b[3])
11.                 return __ffs(b[3]) + 96;
12.         return __ffs(b[4]) + 128;
13. }

复制代码

那么__ffs是干什么的？

2. static inline int __ffs(int x)
3. {
4.         int r = 0;
6.         if (!x)
7.                 return 0;
8.         if (!(x & 0xffff)) {
9.                 x >>= 16;
10.                 r += 16;
11.         }
12.         if (!(x & 0xff)) {
13.                 x >>= 8;
14.                 r += 8;
15.         }
16.         if (!(x & 0xf)) {
17.                 x >>= 4;
18.                 r += 4;
19.         }
20.         if (!(x & 3)) {
21.                 x >>= 2;
22.                 r += 2;
23.         }
24.         if (!(x & 1)) {
25.                 x >>= 1;
26.                 r += 1;
27.         }
28.         return r;
29. }

复制代码

sched_find_first_bit返回值就是最高优先级所在队列的序号，与queue是对应使用的哈，queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的，非常值得我们学习。


好，优先级队列搞明白了，现在来看看runqueue，每个runqueue包含三个优先级队列。
struct runqueue {        spinlock_t lock;   这是个自旋锁，nginx里解决惊群现象时也是用这个。与普通锁的区别就是，使用普通锁时，你去试图拿一把锁，结果发现已经被别人拿走了，你就在那睡觉，等别人锁用完了叫你起来。所以如果有一个人拿住锁了，一百个人都在门前睡觉等。当之前的人用完锁回来后，会叫醒所有100个等锁的人，然后这些人开始互相抢，抢到的人拿锁进去，其他的人继续等。自旋锁不同，当他去拿锁发现锁被别人拿走了，他在那不睡觉的等，稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗？

1.         /*
2.          * nr_running and cpu_load should be in the same cacheline because
3.          * remote CPUs use both these fields when doing load calculation.
4.          */
5.         unsigned long nr_running;
6. #ifdef CONFIG_SMP
7.         unsigned long cpu_load;
8. #endif
9.         unsigned long long nr_switches;
12.         /*
13.          * This is part of a global counter where only the total sum
14.          * over all CPUs matters. A task can increase this counter on
15.          * one CPU and if it got migrated afterwards it may decrease
16.          * it on another CPU. Always updated under the runqueue lock:
17.          */
18.         unsigned long nr_uninterruptible;
21.         unsigned long expired_timestamp;
22.         unsigned long long timestamp_last_tick;
23.         task_t *curr, *idle;
24.         struct mm_struct *prev_mm;
25.         prio_array_t *active, *expired, arrays[2];上面说了半天的优先级队列在这里，但是在runqueue里，为什么不只一个呢？这个在下面讲。
26.         int best_expired_prio;
27.         atomic_t nr_iowait;
28.         ... ...
29. };

复制代码

LINUX是一个时间多路复用的系统，就是说，通过把CPU执行时间分成许多片，再分配给进程们使用，造成即使单CPU系统，也貌似允许多个任务在同时执行。那么，时间片大小假设为100ms，过短过长，过长了有些不灵敏，过短了，连切换进程时可能都要消耗几毫秒的时间。分给100个进程执行，在所有进程都用完自己的时间片后，需要重新给所有的进程重新分配时间片，怎么分配呢？for循环遍历所有的run状态进程，重设时间片？这个性能无法容忍！太慢了，跟当前系统进程数相关。那么2.6内核怎么做的呢？它用了上面提到的两个优先级队列active和expired，顾名思义，active是还有时间片的进程队列，而expired是时间片耗尽必须重新分配时间片的进程队列。


这么设计的好处就是不用再循环一遍所有进程重设时间片了，看看调度函数是怎么玩的：

1. array = rq->active;
2.         if (unlikely(!array->nr_active)) {
3.                 /*
4.                  * Switch the active and expired arrays.
5.                  */
6.                 schedstat_inc(rq, sched_switch);
7.                 rq->active = rq->expired;
8.                 rq->expired = array;
9.                 array = rq->active;
10.                 rq->expired_timestamp = 0;
11.                 rq->best_expired_prio = MAX_PRIO;
12.         } else
13.                 schedstat_inc(rq, sched_noswitch);

复制代码

当所有运行进程的时间片都用完时，就把active和expired队列互换指针，没有遍历哦，而时间片耗尽的进程在出acitve队列入expired队列时，已经单独的重新分配好新时间片了。


再看一下schedule(void)调度函数，当某个进程休眠或者被抢占时，系统就开始调试schedule(void)决定接下来运行哪个进程。上面说过的东东都在这个函数里有体现哈。

2. asmlinkage void __sched schedule(void)
3. {
4.         long *switch_count;
5.         task_t *prev, *next;
6.         runqueue_t *rq;
7.         prio_array_t *array;
8.         struct list_head *queue;
9.         unsigned long long now;
10.         unsigned long run_time;
11.         int cpu, idx;
14.         /*
15.          * Test if we are atomic.  Since do_exit() needs to call into
16.          * schedule() atomically, we ignore that path for now.
17.          * Otherwise, whine if we are scheduling when we should not be.
18.          */
19.         if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看当前运行进程的状态
20.                 if (unlikely(in_atomic())) {
21.                         printk(KERN_ERR "scheduling while atomic: "
22.                                 "%s/0x%08x/%d\n",
23.                                 current->comm, preempt_count(), current->pid);
24.                         dump_stack();
25.                 }
26.         }
27.         profile_hit(SCHED_PROFILING, __builtin_return_address(0));
30. need_resched:
31.         preempt_disable();
32.         prev = current;
33.         release_kernel_lock(prev);
34. need_resched_nonpreemptible:
35.         rq = this_rq();      这行找到这个CPU对应的runqueue，再次强调，每个CPU有一个自己的runqueue
38.         /*
39.          * The idle thread is not allowed to schedule!
40.          * Remove this check after it has been exercised a bit.
41.          */
42.         if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {
43.                 printk(KERN_ERR "bad: scheduling from the idle thread!\n");
44.                 dump_stack();
45.         }
48.         schedstat_inc(rq, sched_cnt);
49.         now = sched_clock();
50.         if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))
51.                 run_time = now - prev->timestamp;
52.         else
53.                 run_time = NS_MAX_SLEEP_AVG;
56.         /*
57.          * Tasks with interactive credits get charged less run_time
58.          * at high sleep_avg to delay them losing their interactive
59.          * status
60.          */
61.         if (HIGH_CREDIT(prev))
62.                 run_time /= (CURRENT_BONUS(prev) ? : 1);
65.         spin_lock_irq(&rq->lock);
68.         if (unlikely(current->flags & PF_DEAD))
69.                 current->state = EXIT_DEAD;
70.         /*
71.          * if entering off of a kernel preemption go straight
72.          * to picking the next task.
73.          */
74.         switch_count = &prev->nivcsw;
75.         if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
76.                 switch_count = &prev->nvcsw;
77.                 if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
78.                                 unlikely(signal_pending(prev))))
79.                         prev->state = TASK_RUNNING;
80.                 else {
81.                         if (prev->state == TASK_UNINTERRUPTIBLE)
82.                                 rq->nr_uninterruptible++;
83.                         deactivate_task(prev, rq);
84.                 }
85.         }
88.         cpu = smp_processor_id();
89.         if (unlikely(!rq->nr_running)) {
90. go_idle:
91.                 idle_balance(cpu, rq);
92.                 if (!rq->nr_running) {
93.                         next = rq->idle;
94.                         rq->expired_timestamp = 0;
95.                         wake_sleeping_dependent(cpu, rq);
96.                         /*
97.                          * wake_sleeping_dependent() might have released
98.                          * the runqueue, so break out if we got new
99.                          * tasks meanwhile:
100.                          */
101.                         if (!rq->nr_running)
102.                                 goto switch_tasks;
103.                 }
104.         } else {
105.                 if (dependent_sleeper(cpu, rq)) {
106.                         next = rq->idle;
107.                         goto switch_tasks;
108.                 }
109.                 /*
110.                  * dependent_sleeper() releases and reacquires the runqueue
111.                  * lock, hence go into the idle loop if the rq went
112.                  * empty meanwhile:
113.                  */
114.                 if (unlikely(!rq->nr_running))
115.                         goto go_idle;
116.         }
119.         array = rq->active;
120.         if (unlikely(!array->nr_active)) {       上面说过的，需要重新计算时间片时，就用已经计算好的expired队列了
121.                 /*
122.                  * Switch the active and expired arrays.
123.                  */
124.                 schedstat_inc(rq, sched_switch);
125.                 rq->active = rq->expired;
126.                 rq->expired = array;
127.                 array = rq->active;
128.                 rq->expired_timestamp = 0;
129.                 rq->best_expired_prio = MAX_PRIO;
130.         } else
131.                 schedstat_inc(rq, sched_noswitch);
134.         idx = sched_find_first_bit(array->bitmap);         找到优先级最高的队列
135.         queue = array->queue + idx;
136.         next = list_entry(queue->next, task_t, run_list);
139.         if (!rt_task(next) && next->activated > 0) {
140.                 unsigned long long delta = now - next->timestamp;
143.                 if (next->activated == 1)
144.                         delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;
147.                 array = next->array;
148.                 dequeue_task(next, array);
149.                 recalc_task_prio(next, next->timestamp + delta);
150.                 enqueue_task(next, array);
151.         }
152.         next->activated = 0;
153. switch_tasks:
154.         if (next == rq->idle)
155.                 schedstat_inc(rq, sched_goidle);
156.         prefetch(next);
157.         clear_tsk_need_resched(prev);
158.         rcu_qsctr_inc(task_cpu(prev));
161.         prev->sleep_avg -= run_time;
162.         if ((long)prev->sleep_avg <= 0) {
163.                 prev->sleep_avg = 0;
164.                 if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))
165.                         prev->interactive_credit--;
166.         }
167.         prev->timestamp = prev->last_ran = now;
170.         sched_info_switch(prev, next);
171.         if (likely(prev != next)) {              表面现在正在执行的进程，不是选出来的优先级最高的进程
172.                 next->timestamp = now;
173.                 rq->nr_switches++;
174.                 rq->curr = next;
175.                 ++*switch_count;
178.                 prepare_arch_switch(rq, next);
179.                 prev = context_switch(rq, prev, next);              所以需要完成进程上下文切换，把之前的进程信息CACHE住
180.                 barrier();
183.                 finish_task_switch(prev);
184.         } else
185.                 spin_unlock_irq(&rq->lock);
188.         prev = current;
189.         if (unlikely(reacquire_kernel_lock(prev) < 0))
190.                 goto need_resched_nonpreemptible;
191.         preempt_enable_no_resched();
192.         if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
193.                 goto need_resched;
194. }

复制代码

当然，在我们程序中，也可以通过执行以下系统调用来改变自己进程的优先级。nice系统调用可以改变某个进程的基本优先级，setpriority可以改变一组进程的优先级。






作者：russell_tao 发表于2011-12-22 11:17:48 原文链接