分类： LINUX
2008-11-18 21:06:31
2、调度算法基于优先级调度，Linux实现了一种基于动态优先级的调度方法。一开始，该方法先设置基本的优先级，然而它允许调度程序根据需要来加、减优 先级。如果一个进程在I/O等待上耗费的时间多于其运行时间，那么该进程明显属于I/O消耗型进程，它的优先级会被动态提高。相反，如果一个进程的全部时 间片一下就被耗尽，那么该进程属于处理器消耗型进程，它的优先级会被动态地降低。
3、Linux内核提供了两组独立的优先级范围。第一种是nice值，范围从-20到19，默认值为0。nice的值越大优先级越低。第二个范围是实时优先级，它的变化范围是从0到99。任何实时进程的优先级都高于普通的进程。
4、调度程序提供较长的默认时间片给I/O消耗型的进程，还能根据进程的优先级动态调整分配给它的时间片。进程并不是一定非要一次就用完它所有的时间片， 可以通过重复调度，分几次用完这些时间片。当一个进程的时间片耗尽时，就认为进程到期了。没有时间片的进程不会再投入运行，除非等到其他所有的进程都耗尽 了它们的时间片。到那时，所有进程的时间片会被重新计算。
5、由于Linux系统是抢占式的，当一个进程进入TASK_RUNNING状态，内核会检查它的优先级是否高于当前正在执行的进程，如果新的进程的优先 级高于当前正在执行的进程，调度程序会被唤醒，重新选择新的进程执行。此外，当一个进程的时间片变为0时，它会被抢占，调度程序被唤醒以选择一个新的进 程。
6、调度程序中最基本的数据结构是运行队列(runqueue)。可执行队列是给定处理器上的可执行进程的链表，每个处理器一个。
7、为避免死锁，要锁住多个运行队列的代码必须总是按照同样的顺序获取这些锁：按照可执行队列地址从低向高的顺序。
8、每个运行队列都有两个优先级数组，一个活跃的和一个过期的。优先级数组是一种能够提供O(1)级算法复杂度的数据结构。优先级数组使可运行处理器的每 一种优先级都包含一个相应的队列，而这些队列包含对应优先级上的可执行进程链表。优先级数组还拥有一个优先级位图，该位图含有5个数组项，总共160位。 每个优先级对应一位。一开始，所有的位都被置为0。当某个拥有一定优先级的进程状态变为TASK_RUNNING，位图中相应的位就会被置为1。这样，查 找系统中最高的优先级就变成了查找位图中被设置的第一个位。因为优先级个数是个定值，所以查找时间恒定，并不受系统到底有多少可执行进程的影响。
9、当一个进程的时间片耗尽时，它会被移至过期数组，但在此之前，时间片已经给它重新计算好了。当活动数组中没有剩余进程的时候，这两个数组就会被交换， 活动数组变成过期数组，过期数组替代活动数组。这种操作提供了时间复杂度为O(1)的时间片重新计算。如果一个进程的交互性非常强，那么当它时间片用完 后，它会被再放置到活动数组而不是过期数组中。
10、抢占分为用户抢占和内核抢占。用户抢占在以下情况下产生：
• 从系统调用返回用户空间。
• 从中断处理程序返回用户空间。
内核抢占会发生在：
• 当从中断处理程序返回内核空间的时候。
• 当内核代码再一次具有可抢占性的时候。
• 如果内核中的任务显式的调用schedule()。
• 如果内核中的任务阻塞。
