linux内核调度算法（一）-快速找到最高优先级进程

linux内核调度算法（1）--快速找到最高优先级进程

为什么要了解内核的调度策略呢？呵呵，因为它值得我们学习，不算是废话吧。内核调度程序很先进很强大，管理你的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类型，这个东东就是优先队列，先看看它的定义：
asmlinkage void __sched schedule(void){long *switch_count;task_t *prev, *next;runqueue_t *rq;prio_array_t *array;struct list_head *queue;unsigned long long now;unsigned long run_time;int cpu, idx;/* * Test if we are atomic. Since do_exit() needs to call into * schedule() atomically, we ignore that path for now. * Otherwise, whine if we are scheduling when we should not be. */if (likely(!(current->exit_state & (EXIT_DEAD | EXIT_ZOMBIE)))) {先看看当前运行进程的状态if (unlikely(in_atomic())) {printk(KERN_ERR "scheduling while atomic: ""%s/0x%08x/%d\n",current->comm, preempt_count(), current->pid);dump_stack();}}profile_hit(SCHED_PROFILING, __builtin_return_address(0));need_resched:preempt_disable();prev = current;release_kernel_lock(prev);need_resched_nonpreemptible:rq = this_rq(); 这行找到这个CPU对应的runqueue，再次强调，每个CPU有一个自己的runqueue/* * The idle thread is not allowed to schedule! * Remove this check after it has been exercised a bit. */if (unlikely(current == rq->idle) && current->state != TASK_RUNNING) {printk(KERN_ERR "bad: scheduling from the idle thread!\n");dump_stack();}schedstat_inc(rq, sched_cnt);now = sched_clock();if (likely(now - prev->timestamp < NS_MAX_SLEEP_AVG))run_time = now - prev->timestamp;elserun_time = NS_MAX_SLEEP_AVG;/* * Tasks with interactive credits get charged less run_time * at high sleep_avg to delay them losing their interactive * status */if (HIGH_CREDIT(prev))run_time /= (CURRENT_BONUS(prev) ? : 1);spin_lock_irq(&rq->lock);if (unlikely(current->flags & PF_DEAD))current->state = EXIT_DEAD;/* * if entering off of a kernel preemption go straight * to picking the next task. */switch_count = &prev->nivcsw;if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {switch_count = &prev->nvcsw;if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&unlikely(signal_pending(prev))))prev->state = TASK_RUNNING;else {if (prev->state == TASK_UNINTERRUPTIBLE)rq->nr_uninterruptible++;deactivate_task(prev, rq);}}cpu = smp_processor_id();if (unlikely(!rq->nr_running)) {go_idle:idle_balance(cpu, rq);if (!rq->nr_running) {next = rq->idle;rq->expired_timestamp = 0;wake_sleeping_dependent(cpu, rq);/* * wake_sleeping_dependent() might have released * the runqueue, so break out if we got new * tasks meanwhile: */if (!rq->nr_running)goto switch_tasks;}} else {if (dependent_sleeper(cpu, rq)) {next = rq->idle;goto switch_tasks;}/* * dependent_sleeper() releases and reacquires the runqueue * lock, hence go into the idle loop if the rq went * empty meanwhile: */if (unlikely(!rq->nr_running))goto go_idle;}array = rq->active;if (unlikely(!array->nr_active)) { 上面说过的，需要重新计算时间片时，就用已经计算好的expired队列了/* * Switch the active and expired arrays. */schedstat_inc(rq, sched_switch);rq->active = rq->expired;rq->expired = array;array = rq->active;rq->expired_timestamp = 0;rq->best_expired_prio = MAX_PRIO;} elseschedstat_inc(rq, sched_noswitch);idx = sched_find_first_bit(array->bitmap); 找到优先级最高的队列queue = array->queue + idx;next = list_entry(queue->next, task_t, run_list);if (!rt_task(next) && next->activated > 0) {unsigned long long delta = now - next->timestamp;if (next->activated == 1)delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;array = next->array;dequeue_task(next, array);recalc_task_prio(next, next->timestamp + delta);enqueue_task(next, array);}next->activated = 0;switch_tasks:if (next == rq->idle)schedstat_inc(rq, sched_goidle);prefetch(next);clear_tsk_need_resched(prev);rcu_qsctr_inc(task_cpu(prev));prev->sleep_avg -= run_time;if ((long)prev->sleep_avg <= 0) {prev->sleep_avg = 0;if (!(HIGH_CREDIT(prev) || LOW_CREDIT(prev)))prev->interactive_credit--;}prev->timestamp = prev->last_ran = now;sched_info_switch(prev, next);if (likely(prev != next)) { 表面现在正在执行的进程，不是选出来的优先级最高的进程next->timestamp = now;rq->nr_switches++;rq->curr = next;++*switch_count;prepare_arch_switch(rq, next);prev = context_switch(rq, prev, next); 所以需要完成进程上下文切换，把之前的进程信息CACHE住barrier();finish_task_switch(prev);} elsespin_unlock_irq(&rq->lock);prev = current;if (unlikely(reacquire_kernel_lock(prev) < 0))goto need_resched_nonpreemptible;preempt_enable_no_resched();if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))goto need_resched;}
当然，在我们程序中，也可以通过执行以下系统调用来改变自己进程的优先级。nice系统调用可以改变某个进程的基本优先级，setpriority可以改变一组进程的优先级。

?