只要不发生这种情况，进程就会被重新设置在活动数组里，否则，进程会被放入过期数组里。 有关休眠我就不用多讲了。内核对休眠的处理都相同：进程把自己标记成休眠状态，然后将自己从可执行队列移出，放入等待队列，然后调用schedule()选择和执行一个其他进程，唤醒的过程刚好相反。要明白一点就是：即使休眠也有两种进程状态，TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE.前者如果接收到一个信号会被提前唤醒并响应该信号，后者会忽略信号。这两种进程位于同一等待队列(wake_queue_head_t)上，等待某些事情，不能够运行。有关等待队列的知识，跳过(我已经在Linux驱动开发理论帖里讲过，自己去看吧)现在，在内核中进行休眠的推荐操作相比较以前而言复杂了很多，但更安全：
1.调用DECLARE_WAITQUEUE() 创建一个等待队列的项。 2.调用add_wait_queue()把自己加入到等带对列中。 3.将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE. 4.检查条件是否为真，如果是的话，就没必要休眠了。不为真，就调用schedule(). 5.当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环，如果不是，它再次调用schedule()并一直重复这步操作。 6.当条件满足后，进程将自己设置为TASK_RUNNING并调用remove_wait_queue把自己移出等待队列。 如果在进程开始休眠之前条件就已经达成了，那么循环会退出，进程不会存在错误的进入休眠的倾向。有休眠就有唤醒，唤醒是通过wake_up()进行。她唤醒指定的等待队列上的所有进程。它调用try_to_wake_up,该函数负责将进程设置为TASK_RUNNING状态，调用active_task()将此进程放入可执行队列，如果被唤醒进程的优先级比当前正在执行的进程的优先级高，还要设置need_resched标志。编程的技巧，通常哪段代码促使等待条件达成，它就要负责随后调用wake_up函数。说明：存在虚假的唤醒，有时候进程被唤醒并不是因为它所等待的条件达成了，所以才需要用一个循环处理来保证它等待的条件真正到达。 开始新的问题，现在市场上，你说单核CPU，你都没脸见人，现在是啥时代，多核的时代，瞧，我这都酷睿i7了(四核)，我用的服务器实验平台是8核心的。和我有啥关系，和我今天讲的有啥关系。关系大了去了。前边提到过，linux的调度程序为对称多处理器系统的每个处理器准备了单独的可执行队列和锁，出于效率的考虑，整个调度系统从每个处理器来看都是独立的。那么这样的情况咋办呢？一个处理器上有5个进程，另外一个处理器的队列上只有一个进程，这时很明显出现了系统负载不均衡的情况。这时咋办呢？由负载均衡程序来解决(kernel/sched.c的load_balance来实现)。它有两种调用方法，在schedule执行的时候，只要当前的可执行对列为空，它就会被调用。此外，它也会被定时器调用，系统空闲时每隔1ms调用一次或者在其他情况下每隔200ms调用一次。单系统中，它不会被调用，甚至不会被编译进内核，因为那里边只有一个可执行队列，根本没有平衡负载的必要。load_balances调用时需要锁住当前处理器的可执行队列并且屏蔽中断，以避免可执行队列被并发的访问，所完成的操作步骤如下所示：
1.load_balance()调用find_busiest_queue(),找到最繁忙的可执行队列(进程数目最多)并返回该队列。如果没有哪个可执行队列中进程的数 目比当前队列中的数目多25%或25%以上。它就返回NULL,同时load_balance也返回。 2.load_balance从最繁忙的运行队列中选择一个优先级数组以便抽取进程。最好是过期数组，如果过期数组为空，那就只能选活动数组。 3.load_balance寻找到含有进程并且优先级最高的链表，因为把优先级高的进程分散开来才是最重要的。 4.分析找到的所有这些优先级相同的进程，这样一个不是正在执行，也不会因为处理器相关性而不可移动，并且不在高速缓存中的进程。如 果有，就调用pull_task将其从最繁忙的队列中抽取到当前队列 5.只要可执行队列之间仍然不平衡，就重复上面两个步骤，这最终会消除不平衡。然后解除对当前运行队列进行的锁定，从load_balance返 回。 我们后面会提到的上下文切换，就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c的context_switch函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule就会调用该函数。它主要完成如下两个工作： 1.调用定义在include/asm/mmu_context.h中的switch_mm().该函数负责把虚拟内存从上一个进程映射切换到新进程中。 2.调用定义在include/asm/system.h的switch_to(),该函数负责从上一个进程的处理器状态切换到新进程的处理器状态，这包括保存，恢复 栈信息和寄存器信息。 内核也必须知道什么时候调用schedule(),单靠用户代码显示调用schedule(),他们可能就会永远地执行下去，相反，内核提供了一个need_resched标志来表明是否需要重新执行一次调度。当某个进程耗尽它的时间片时，scheduler_tick()就会设置这个标志，当一个优先级高的进程进入可执行状态的时候，try_to_wake_up()也会设置这个标志。下表给出了用于访问和操作need_resched的函数。 函数 set_tsk_need_resched(task) clear_tsk_need_resched(task) need_resched() 说明 设置指定进程中的need_resched标志 清除指定进程中的nedd_resched标志 检查need_resched标志的值，如果被设置就返回真，否则返回假 再返回用户空间以及从中断返回的时候，内核也会检查need_resched标志，如果已被设置，内核会在继续执行之前调用该调度程序。最后，每个进程都包含一个need_resched标志，这是因为访问进程描述符内的数值要比访问一个全局变量要快(因为current宏速度很快并且描述符通常都在高速缓存中)。在2.6内核中，他被移到了thread_info结构体里，这是和以前不同的。
抢占，还是抢占！我们总是逃不了抢占的话题。内核放回到用户空间的时候，如果need_resched标志被设置，就会导致schedule()被调用。简儿言之，用户抢占在以下情况下发生：从系统调用返回到用户空间和从中断处理程序返回用户空间。
在linux2.6内核中，内核引入了抢占内力。为了支持内核抢占所做的第一个变动就是为每个进程的thread_info引入preempt_count计数器，该计数器初始为0，每当使用锁的时候，该值减1。当为0的时候，内核就可执行抢占。从中断返回内核空间的时候，内核会检查need_resched和preempt_count的值，如果need_resched被设置，并且preempt_count为0的时候，这说明有一个更重要的任务需要执行并且安全地抢占，此时，调度程序就会被调度。如果，preempt_count不为0，说明当前任务持有锁，这时抢占是不安全的。这时，就会想通常那样直接从中断返回当前执行进程。如果当前进程持有的锁都被释放了，那么preempt_count就会重新为0。此时，释放锁的代码会检查need_sheduled是否被设置，如
果是的话，就会调用调度程序，有些内核需要允许或禁止内核抢占，这个后面具体问题具体分析。如果内核中的进程阻塞了，或它显示地调用了schedule(),内核抢占也会显示地发生，这种形式的内核抢占从来都是支持的，因为根本无需额外的逻辑来保证内核可以安全地被抢占，如果代码显示的调用了schedule(),那么它清楚自己是可以安全地被强化的。
我们前边讲的是普通的，非实时的调度策略(SCHED_OTHER),Linux也支持两种实时调度策略(SCHED_FIFO和SCHED_RR).SCHED_FIFO从名字中我们也知道，就不说了。它不使用时间片。该级的进程会比任何SCHED_OTHER级的进程都先得到调度。一旦一个SCHED_FIFO级进程处理可执行状态，就会一直执行，直到它自己被阻塞或是显示地释放处理器为止。由于不基于时间片，所以它会一直执行下去。多个SCHED_FIFO级进程存在时，他们会轮流执行。而且只要有SCHED_FIFO级的进程存在，普通级进程级只能等待它结束后才有机会执行。SCHED_RR是一种带有时间片的SCHED_FIFO。以上两种实时调度算法实现都是静态优先级的。内核不为实时进程计算动态优先级。这样就能保证给定优先级级别的实时进程总能抢占优先级比它低的进程。
linux的实时调度算法分为软实时和硬实时。软实时的含义是，内核调度进程尽可能使进程在它的限定时间到来前执行，但内核不会拍着胸脯说：我一定能保证。对应地，硬实时会这样哥们义气哦。linux下的实时调度不做任何保证，只保证只要实时进程可执行，就尽量去执行它。现在开来，效果还是不错的。
实时优先级范围从0~MAX_RT_PRIO-1.默认情况下，MAX_RT_PRIO为100.SCHED_OTHER级进程的nice值共享了这个取值空间。它的取值范围是从MAX_RT_PRIO到MAX_RT_PRIO+40.也就是说，nice值从-20到+19对应的是从100到140的实时优先级范围。
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类型，这个东东就是优先队列，先看看它的定义：
[cpp] view plaincopy
1. struct prio_array {
2. unsigned int nr_active; 表示等待执行的进程总数
3. unsigned long bitmap[BITMAP_SIZE]; 一个unsigned long在内核中只有32位
哈，大家要跟64位OS上的C程序中的long区分开，那个是64位的。那么这个bitmap是干什么的呢？它是用位的方式，表示某个优先级上有没有待处理的队列，是实现快速找到最高待处理优先进程的关键。如果我定义了四种优先级，我只需要四位就能表示某个优先级上有没有进程要运行，例如优先级是2和3上有进程，那么就应该是0110.......非常省空间，效率也快，不是吗？
4. struct list_head queue[MAX_PRIO]; 与上面的bitmap是对应的，它存储所有等
待运行的进程。 5. };
看看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);这个方法就用来快速的找到优先级最高的队列。看看它的实现可以方便我们理解这个优先级位的设计：
[cpp] view plaincopy
1. static inline int sched_find_first_bit(unsigned long *b) 2. {
3. if (unlikely(b[0])) 4. return __ffs(b[0]); 5. if (unlikely(b[1]))
6. return __ffs(b[1]) + 32; 7. if (unlikely(b[2]))
8. return __ffs(b[2]) + 64; 9. if (b[3])
10. return __ffs(b[3]) + 96; 11. return __ffs(b[4]) + 128; 12. }
那么__ffs是干什么的？
[cpp] view plaincopy
1. static inline int __ffs(int x) 2. {
3. int r = 0; 4.
5. if (!x) 6. return 0; 7. if (!(x & 0xffff)) { 8. x >>= 16; 9. r += 16; 10. }
11. if (!(x & 0xff)) { 12. x >>= 8; 13. r += 8; 14. }
15. if (!(x & 0xf)) { 16. x >>= 4; 17. r += 4; 18. }
19. if (!(x & 3)) { 20. x >>= 2; 21. r += 2; 22. }
23. if (!(x & 1)) { 24. x >>= 1; 25. r += 1; 26. }
27. return r; 28. }
sched_find_first_bit返回值就是最高优先级所在队列的序号，与queue是对应使用的哈，queue = array->queue + idx;这样就取到了要处理的进程队列。这个设计在查找优先级时是非常快的，非常值得我们学习。
好，优先级队列搞明白了，现在来看看runqueue，每个runqueue包含三个优先级队列。
[cpp] view plaincopy
1. struct runqueue {
2. spinlock_t lock; 这是个自旋锁，nginx里解决惊群现象时也是用这个。与普通锁的
区别就是，使用普通锁时，你去试图拿一把锁，结果发现已经被别人拿走了，你就在那睡觉，等别人锁用完了叫你起来。所以如果有一个人拿住锁了，一百个人都在门前睡觉等。当之前的人用完锁回来后，会叫醒所有100个等锁的人，然后这些人开始互相抢，抢到的人拿锁进去，其他的人继续等。自旋锁不同，当他去拿锁发现锁被别人拿走了，他在那不睡觉的等，稍打个盹就看看自己主动看看锁有没有还回来。大家比较出优劣了吗？