深入理解Linux内核－第七章 进程调度

深入理解Linux内核－第七章 进程调度

【摘要】本章首先分析了Linux调度的基本分时策略，然后介绍了RR、FIFO、OTHER等三种调度算法以及与之相关的基本时间片、静态优先级、动态优先级、平均睡眠时间、活动过期队列等；最后介绍了运行队列和进程描述符等数据结构和调度相关的函数。

【关键词】调度策略，分时，RR，FIFO，OTHER，时间片，静态动态优先级，活动过期队列，运行队列，PCB，schedule

 

第七章进程调度... 1

调度策略... 1

进程的抢占... 3

一个时间片必须持续多长？... 3

调度算法... 3

普通进程的调度... 4

实时进程的调度... 6

调度程序所使用的数据结构... 7

数据结构runqueue. 7

进程描述符... 9

调度程序所使用的函数... 10

scheduler_tick()函数... 11

recalc_task_prio()函数... 13

schedule()函数... 13

与调度相关的系统调用... 19

nice( ) 19

getpriority()和setpriority()系统调用... 19

 

第七章进程调度
Linux 与任何分时系统一样，通过一个进程到另一个进程的快速切换，达到表面上看来多个进程同时执行的神奇效果。本章讨论进程调度，主要关心什么时候进行进程切换及选择哪一个进程来运行。

本章由三部分组成。“调度策略”一节从理论上介绍Linux 进行进程调度所做的选择，“调度算法”一节讨论实现调度所采用的数据结构和相应的算法，最后，“与调度相关的系统调用”一节描述了影响进程调度的系统调用。

调度策略
传统Unix 操作系统的调度算法必须实现几个互相冲突的目标：进程响应时间尽可能快，后台作业的吞吐量尽可能高，尽可能避免进程的饥饿现象，低优先级和高优先级进程的需要尽可能调和等等。决定什么时候以怎样的方式选择一个新进程运行的这组规则就是所谓的调度策略（scheduling policy ），即何时如何选择被调度的进程。

Linux 的调度基于分时技术（time-sharing ）：多个进程以“时间多路复用”方式运行，因为CPU 的时间被分成“片”，给每个可运行进程分配一片。如果当前运行进程的时间片或时限（quantum ）到期时，该进程还没有运行完毕，进程切换就强制发生；若时间片未用完时进程运行完毕或者需要等待其他资源，则将主动进行进程切换。分时依赖于定时中断，不需要在程序中插入额外的代码来保证CPU 分时。

调度策略也是根据进程的优先级对它们进行分类。有时用复杂的算法求出进程当前的优先级，但最后的结果是相同的：每个进程都与一个值相关联，这个值表示把进程如何适当地分配给CPU 。

在Linux 中，进程的优先级是动态的，但对于实时进程，其优先级固定，保证其有固定的时间响应。调度程序跟踪进程正在做什么，并周期性地调整它们的优先级。在这种方式下，在较长的时间间隔内没有使用CPU 的进程，通过动态地增加它们的优先级来提升它们。相应地，对于已经在CPU 上运行了较长时间的进程，通过减少它们的优先级来处罚它们。普通进程的优先级是由动态优先权和静态优先权组合的，而动态优先权会随之运行时间的增加而减少，所以整体上其优先级会下降，以便让其他非实时进程运行。

常把进程分为以下三类：

l         交互式进程（Interactive process） 这些进程经常与用户进行交互，因此，要花很多时间等待键盘和鼠标操作。当接受了输入后，进程必须被很快唤醒，否则，用户将发现系统反应迟钝。典型的情况是，平均延迟必须低于50 到150ms 。这样的延迟变化也必须进行限制，否则，用户将发现系统是不稳定的。典型的交互式程序是命令shell 、文本编辑程序及图形应用程序。

l         批处理进程（Batch process） 这些进程不必与用户交互，因此，它们经常在后台运行。因为这样的进程不必被很快地响应，因此，它们常受到调度程序的慢待。

l         实时进程（Real-time process） 这些进程有很强的调度需要。这样的进程决不会被低优先级的进程阻塞，它们应该有一个短的响应时间，更重要的是，响应时间的变化应该很小。典型的实时程序有视频和音频应用程序、机器人控制程序及从物理传感器上收集数据的程序。

在Linux 中，调度算法可以明确地确认所有实时程序的身份，但没有办法区分交互式程序和批处理程序。Linux 2.6 调度程序实现了基于进程过去行为的启发式算法，以确定进程应该被当作交互式进程还是批处理进程。当然，与批处理进程相比，调度程序有偏爱交互进程的倾向。

程序员可以通过表7-1 所列的系统调用改变调度优先级。

表7-1
 与调度相关的系统调用
 
系统调用                                     说明
nice( )                             改变一个普通进程的静态优先级 
getpriority( )                   获得一组普通进程的最大优先级
setpriority( )                 设置一组普通进程的静态优先级
sched_getscheduler( )             获得一个进程的调度策略
sched_setscheduler( )             设置一个进程的调度策略和实时优先级
sched_getparam( )                获得一个进程的实时优先级
sched_setparam( )               设置一个进程的实时优先级
sched_yield( )                   自愿放弃处理器而不阻塞
sched_get_ priority_min( )           获得一种策略的最小实时优先级
sched_get_ priority_max( )         获得一种策略的最大实时优先级
sched_rr_get_interval( )        获得时间片轮转策略的时间片值
 
 

进程的抢占
Linux 的进程是抢占式的。如果进程进入TASK_RUNNING 状态（状态何时改变何时检测？？），内核检查它的动态优先级是否大于当前正运行进程的优先级。如果是，current 的执行被中断，并调用调度程序选择另一个进程运行（通常是刚刚变为可运行的进程）。当然，进程在它的时间片到期时也可以被抢占。此时, 当前进程thread_info 结构中的TIF_NEED_RESCHED标志被设置，以便定时中断处理程序终止时调度程序被调用。

 

注意被抢占的进程并没有被挂起，因为它还处于TASK_RUNNING 状态，只不过不再使用CPU 。

此外，记住，Linux2.6 内核是抢占式的，这意味着进程无论是处于内核态还是用户态，都可能被抢占。

 

一个时间片必须持续多长？
时间片的长短对系统性能是很关键的：它既不能太长也不能太短。

如果平均时间片太短，由进程切换引起的系统额外开销就变得非常高。如果平均时间片太长，进程看起来就不再是并发执行。例如，让我们假定把时间片设置为5秒， 那么，每个可运行进程运行大约5秒，但是暂停的时间更长（典型的是5秒乘以可运行进程的个数）。时间片大小的选择总是一种折衷。Linux 采取单凭经验的方法，即选择尽可能长、同时能保持良好响应时间的一个时间片。

 

调度算法
早期Linux版本中的调度算法非常简单易懂：在每次进程切换时，内核扫描可运行进程的链表，计算进程的优先权，然后选择“最佳”进程来运行。这个算法的主要缺点是选择“最佳”进程所要消耗的时间与可运行的进程数量相关，因此，这个算法的开销太大，在运行数千个进程的高端系统中，要消耗太多的时间。

 

Linux2.6的调度算法就复杂多了。通过设计，该算法较好地解决了与可运行进程数量的比例关系，因为它在固定的时间内（与可运行的进程数量无关）选中要运行的进程。它也很好地处理了与处理器数量的比例关系，因为每个CPU都拥有自己的可运行进程队列。而且，新算法较好地解决了区分交互式进程和批处理进程的问题。调度程序总能成功地找到要执行的进程，事实上，总是至少有一个可运行进程：即swapper 空闲进程，它的PID等于0，而且它只有在CPU不能执行其他进程时才执行。

 

每个Linux进程总是按照下面的调度类型被调度：

SCHED_FIFO

先进先出的实时进程，此特性只有在具备相同优先级的实时进程间体现。当调度程序把CPU分配给进程的时候，它把该进程描述符保留在运行队列链表的当前位置。如果没有其他可运行的高优先权实时进程，进程就继续使用CPU， 想用多久就用多久，即使还有其他具有相同优先权的实时进程处于可运行状态。

SCHED_RR

时间片轮转的实时进程。当调度程序把CPU分配给进程的时候，把该进程的描述符放在运行队列链表的末尾。这种策略保证对所有具有相同优先权的SCHED_RR实时进程公平地分配CPU 时间。

SCHED_NORMAL

普通的分时进程。

 

普通进程的调度
每个普通进程都有它自己的静态优先权，调度程序使用静态优先权来估价系统中这个进程与其他普通进程之间调度的程度。内核用从100（最高优先权）到139（最低优先权）的数表示普通进程的静态优先权。注意，值越大静态优先权越低。新进程总是继承其父进程的静态优先权。不过，通过系统调用nice()和setpriority()，用户可以改变自己拥有的进程的静态优先权。

 

基本时间片

静态优先权本质上决定了进程的基本时间片，即进程用完了以前的时间片时，系统分配给进程的时间片长度。静态优先权和基本时间片的关系用下列公式确定：

Base time quantum  =

(1) (140-static priority) ×20 if static < 120

(2) (140-static priority) ×5 if static priority≥120

因此静态优先权越高，基本时间片就越长。表7-2 说明了普通进程的静态优先权、基本时间片和对应的nice 值，与最高静态优先权、缺省静态优先权、最低优先权相对应的nice 值。

表7-2 普通进程优先权的典型值

说明
 静态优先权
 Nice 值
 基本时间片
 交互式的值
 睡眠时间的极限值
 
最高静态优先权
 100
 -20
 800ms
 -3
 299ms
 
高静态优先权
 110
 -10
 600ms
 -1
 499ms
 
缺省静态优先权
 120
 0
 100ms
 +2
 799ms
 
低静态优先权
 130
 +10
 50ms
 +4
 999ms
 
最低静态优先权
 139
 +19
 5ms
 +6
 1199ms
 

 

动态优先权和平均睡眠时间

普通进程除了静态优先权，还有动态优先权，其值的范围是100（最高优先权）到139（最低优先权）。动态优先权是调度程序在选择新进程来运行的时候使用的数。它与静态优先权的关系用下面的经验公式表示。

动态优先权=max(100,min (静态优先权-bonus +5,139))

Bonus 是范围从0到10的值，bonus的值小于5表示降低动态优先权以示惩罚，bonus的值大于5表示增加动态优先权以示额外奖赏。Bonus的值依赖于进程过去的情况，说得更准确一些是与进程的

平均睡眠时间相关。

表7-3平均睡眠时间、bonus值以及时间片粒度

平均睡眠时间
 Bonus
 粒度
 
大于或等于0小于100ms
 0
 5120
 
大于或等于100小于200ms
 1
 2560
 
大于或等于200 小于300ms
 2
 1280
 
大于或等于300 小于400ms
 3
 640
 
大于或等于400 小于500ms
 4
 320
 
 
大于或等于500 小于600ms
 5
 160
 
 
大于或等于600小于700ms
 6
 80
 
 
大于或等于700 小于800ms
 7
 40
 
 
大于或等于800小于900ms
 8
 20
 
 
大于或等于900 小于1000ms
 9
 10
 
 
1 秒
 10
 10
 
 
             

 

平均睡眠时间也被调度程序用来确定一个给定进程是交互进程还是批处理进程。高优先权进程比低优先权进程更容易成为交互进程。

 

活动和过期进程

即使具有较高静态优先权的普通进程获得了较大的CPU时间片，也不应该使静态优先权较低的进程无法运行。为了避免进程饥饿，当一个进程用完它的时间片时，它应该被还没有用完时间片的低优先权进程取代。为了实现这种机制，调度程序维持两个不相交的可运行进程的集合。

活动进程，这些进程还没有用完他们的时间片，因此允许他们运行。

过期进程，这些可运行进程已经用完了他们的时间片，并因此被禁止运行，直到所有活动进程都过期。

 

不过，总体的方案要稍微复杂一些，因为调度程序试图提升交互进程的性能。用完其时间片的活动批处理进程总是变成过期进程。用完其时间片的交互进程通常仍然是活动进程：调度程序重填它的时间片并把它留在活动进程集合中。但是，如果最老的过期进程已经等待了很长时间，或者过期进程比交互进程的静态优先权高，调度程序就把用完时间片的交互进程移到过期进程集合中。结果，活动进程集合最终会变为空，过期进程将有机会运行。

 

实时进程的调度
每个实时进程都与一个实时优先权相关，实时优先权是一个范围从1（最高优先权）到99（最低优先权）的值。调度程序总是让优先权高的进程运行，换句话说，实时进程运行的过程中，禁止低优先权进程的执行。与普通进程相反，实时进程总是被当成活动进程。用户可以通过系统调用sched_setparam()和sched_setscheduler ()改变进程的实时优先权。

 

如果几个可运行的实时进程具有相同的最高优先级，调度程序选择第一个出现在与本地CPU 的运行队列相应链表中的进程。这是区别并调度FIFO和RR进程的前提。

只有在下述事件发生时，实时进程才会被另外一个进程取代。

*进程被另外一个具有更高优先权的实时进程抢占。

*进程执行了阻塞操作并进入睡眠（处于TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE状态）

*进程停止（处于TASK_STOPPED或TASK_TRACED状态）或被杀死（ 处于EXIT_ZOMBIE或EXIT_DEAD状态）

*进程通过调用系统调用sched_yield()自动放弃CPU，但仍然处于TASK_RUNNING状态。

*进程是基于时间片轮转的实时进程（SCHED_RR），而且用完了它的时间片（这种情况何时再运行呢？？）。

 

系统调用nice()和setpriority()，当用于基于时间片轮转的实时进程时，不改变实时进程的优先权而会改变其基本时间片的长度。实际上，基于时间片轮转的实时进程的基本时间片的长度与实时进程的优先权无关，而依赖于进程的静态优先权。

 

调度程序所使用的数据结构
进程链表链接所有的进程描述符，而运行队列链表链接所有的可运行进程（也就是处于TASK_RUNNING状态的进程）的进程描述符，swapper 进程（idle进程）除外。

 

数据结构runqueue
数据结构runqueue是Linux2.6调度程序最重要的数据结构。系统中的每个CPU都有它自己的运行队列，所有的runqueue结构存放在runqueues per-CPU变量中。宏this_rq()产生本地CPU运行队列的地址，而宏cpu_rq(n)产生索引为n 的CPU的运行队列的地址。表7-4列出了runqueue数据结构所包括的字段，在下面的章节中我们将对其中的大部分进行讨论。最重要的字段是与可运行进程的链表相关的字段。系统中的每个可运行进程属于且只属于一个运行队列。只要可运行进程保持在同一个运行队列中，它就只可能在拥有该运行队列的CPU上执行。但是，正如我们将要看到的，可运行进程会从一个运行队列迁移到另一个运行队列（负载均衡）。

7-4  runqueue数据结构的部分字段

类型
 名称
 说明
 
spinlock_t
 Lock
 保护进程链表的自旋锁
 
Unsigned long
 nr_running
 运行队列链表中可运行进程的数量
 
Unsigned long
 cpu_load
 基于运行队列中进程的平均数量的CPU负载因子
 
Unsigned long
 nr_switches
 CPU 执行进程切换的次数
 
Unsigned long
 nr_uninterruptible
 先前在运行队列链表中而现在睡眠在TASK_UNINTERRUPTIBLE状态的进程的数量（对所有运行队列来说， 这些字段的总数才是有意义的）
 
Unsigned long
 expired_timestamp
 过期队列中最老的进程被插入队列的时间。
 
Unsigned long long
 timestamp_last_tick
 最近一次定时器中断的时间戳的值
 
task_t*
 curr
 当前正在运行进程的进程描述符指针（对本地CPU ，它与current相同）
 
task_t*
 idle
 当前CPU（this CPU） 上交换进程的进程描述符指针。
 
Struct mm_struct*
 prev_mm
 在进程切换期间用来存放被替换进程的内存描述符的地址
 
prio_array_t*
 active
 指向活动进程链表的指针
 
prio_array_t*
 Expired
 指向过期进程链表的指针
 
prio_array_t[2]
 arrays
 活动和过期进程的两个集合
 
int
 best_expired_prio
 过期进程中静态优先权最高的进程（权值最小）。
 
Struct list_head
 migration_queue
 从运行队列中被删除的进程的链表
 

 

运行队列的arrays 字段是一个包含两个prio_array_t结构的数组。每个数据结构都表示一个可运行进程的集合，并包括140个双向链表头、一个优先权位图和一个集合中所包含的进程数量的计数器。

图7-1 runqueue结构和可运行进程的两个集合

runqueue 结构的active字段指向数组中两个prio_array_t数据结构之一：对应于包含活动进程的可运行进程的集合。相反，expired字段指向数组中的另一个prio_array_t数据结构：对应于包含过期进程的可运行进程的集合。数组中两个数据结构的作用会发生周期性的变化：活动进程突然变成过期进程，而过期进程变为活动进程，调度程序简单地交换运行队列的active和expired字段的内容以完成这种变化

 

进程描述符
每个进程描述符都包括几个与调度相关的字段，他们被列在表7-5中

表7-5与调度程序相关的进程描述符字段

类型
 名称
 说明
 
unsignedlong
 thread_info->flags
 存放TIF_NEED_RESCHED标志如果必须调用调度程序， 则设置该标志
 
unsignedint
 thread_info->cpu
 可运行进程所在运行队列的CPU逻辑号
 
unsignedlong
 state
 进程的当前状态
 
int
 prio
 进程的动态优先权
 
int
 static_prio
 进程的静态优先权
 
Struct list_head
 run_list
 指向进程所属的运行队列中的下一个和前一个元素。
 
prio_array_t*
 array
 指向包含进程的运行队列的集合：prio_array_t
 
unsignedlong
 sleep_avg
 进程的平均睡眠时间
 
unsignedlonglong
 timestamp
 进程最近插入运行队列的时间或涉及本进程的最近一次进程切换的时间。
 
int
 activated
 进程被唤醒时所使用的条件码
 
unsignedlong
 policy
 进程的调度类型(SCHED_NORMAL,SCHED_RR,或SCHED_FIFO)
 
unsignedint
 time_slice
 在进程的时间片中还剩余的时钟节拍数
 
unsignedint
 first_time_slice
 如果进程肯定不会用完其时间片，就把该标志设置为1 。
 
unsignedlong
 rt_priority
 进程的实时优先权
 
         

 

当新进程被创建的时候，用下述方法设置current进程（父进程）和p进程（子进程）的time_slice 字段。p->time_slice =(current->time_slice +1)>>1;current->time_slice >>=1;

换句话说，父进程剩余的节拍数被划分成两等份：一份给父进程，另一份给子进程。这样做是为了避免用户通过下述方法获得无限的CPU时间：父进程创建一个运行相同代码的子进程，并随后杀死自己，通过适当地调节创建的速度，子进程就可以总是在父进程过期之前获得新的时间片。更通俗地讲就是一个进程不能通过创建多个后代来霸占资源。

 

调度程序所使用的函数
调度程序依靠几个函数来完成调度工作，其中最重要的函数是：

scheduler_tick()维持当前最新的time_slice 计数器

try_to_wake_up()唤醒睡眠进程

recalc_task_prio()更新进程的动态优先权

schedule()选择要被执行的新进程

load_balance()维持多处理器系统中运行队列的平衡。

 

scheduler_tick()函数
每次时钟节拍到来时，scheduler_tick()是如何被调用以执行与调度相关的操作的。它执行的主要步骤如下：

把转换为纳秒的TSC的当前值存入本地运行队列的timestamp_last_tick 字段。这个时间戳是从函数sched_clock( )获得的。

检查当前进程是否是本地CPU的swapper进程，执行下面的子步骤：

a.如果本地运行队列除了swapper进程外，还包括另外一个可运行的进程，就设置当前进程的TIF_NEED_RESCHED字段，以强迫进行重新调度。

b.跳转到第7步（没必要更新swapper进程的时间片计数器）。

检查current->array是否指向本地运行队列的活动链表。如果不是，说明进程已经过期但还没有被替换：设置TIF_NEED_RESCHED标志以强制进行重新调度并跳转到第七步。

获得this_rq()->lock自旋锁。

递减当前进程的时间片计数器，并检查是否已经用完时间片。

释放this_rq()->lock自旋锁。

rebalance_tick( )函数，该函数应该保证不同CPU的运行队列包含数量基本相同的可运行进程。

 

更新实时进程的时间片

如果当前进程是先进先出（FIFO）的实时进程，函数scheduler_tick()什么都不做。实际上在这种情况下，current所表示的进程（当前进程）不可能被比它优先较低或与它优先权相等的进程所抢占，因此，维持当前进程的最新时间片计数器是没有意义的。

如果current表示基于时间片轮转的实时进程，scheduler_tick()就递减它的时间片计数器并检查时间片是否被用完：

if (current->policy == SCHED_RR && !--current->time_slice) {

current->time_slice = task_timeslice(current);

current->first_time_slice = 0;

set_tsk_need_resched(current);

list_del(¤t->run_list);

list_add_tail(¤t->run_list,

this_rq( )->active->queue+current->prio);

}

 

如果函数确定时间片确实用完了，就执行一系列操作以达到抢占当前进程的目的，如果必要的话，就尽快抢占。

 

scheduler_tick()的最后一步操作包括把进程描述符移到与当前进程优先权相应的运行队列活动链表的尾部。把current指向的进程放到链表的尾部可以保证在每个优先权与它相同的可运行实时进程获得CPU时间片以前，不会再次被选择来执行。这是基于时间片轮转的调度策略。进程描述符的移动通过两个步骤完成：先调用list_del()把进程从运行队列的活动链表中删除，然后调用list_add_tail()把进程重新插入到同一个活动链表的尾部。

 

更新普通进程的时间片

如果当前进程是普通进程，函数scheduler_tick()执行下列操作：

递减时间片计数器(current->time_slice).

检查时间片计数器，如果时间片用完，函数执行下列操作：

a.调用dequeue_task()从可运行进程的this_rq()->active集合中删除current指向的进程。

b.调用set_tsk_need_resched()设置TIF_NEED_RESCHED标志。

c.更新current指向的进程的动态优先权current->prio =effective_prio(current);

d.重填进程的时间片；

e.如果本地运行队列数据结构的expired_timestamp字段等于0（即：过期进程集合为空），就把当前时钟节拍的值赋给expired_timestamp

f.把当前进程插入活动进程集合或过期进程集合。

 

3．否则，如果时间片没有用完（ current->time_slice不等于0），检查当前进程的剩余时间片是否太长。基本上，具有高静态优先权的交互进程，其时间片被分成大小为TIMESLICE_GRANULARITY的几个片段，以使这些进程不会独占CPU.

 

try_to_wake_up()
函数try_to_wake_up()函数通过把进程状态设置为TASK_RUNNING，并插入本地CPU的运行队列来唤醒睡眠或停止的进程。例如：调用该函数唤醒等待队列中的进程或恢复执行等待信号的进程。该函数接受的参数：

* 被唤醒进程的描述符指针（p）

* 可以被唤醒的进程状态掩码（state）

* 一个标志(sync)，用来禁止被唤醒的进程抢占本地CPU上正在运行的进程。

 

recalc_task_prio()函数
函数recalc_task_prio()更新进程的平均睡眠时间和动态优先权。它接收进程描述符的指针和由函数sched_clock()计算出的当前时间戳。

 

schedule()函数
函数schedule()实现调度程序。它的任务是从运行队列的链表中找到一个进程，并随后将CPU分配给这个进程。schedule()可以由几个内核控制路径调用，可以采取直接调用或延迟调用的方式。

 

直接调用

如果current进程因不能获得必须的资源而要立刻被阻塞，就直接调用调度程序。在这种情况下，要阻塞进程的内核路径按下述步骤执行：

把current进程插入适当的等待队列。

把current进程的状态改为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。

调用schedule( )。

检查资源是否可用，如果不可用就转到第2步。

一但资源可用就从等待队列中删除当前进程current.

 

内核路径反复检查进程需要的资源是否可用，如果不可用，就调用schedule()把CPU分配给其它进程。稍后，当调度程序再次允许把CPU分配给这个进程时，要重新检查资源的可用性。这些步骤与wait_event()所执行的步骤很相似。

 

延迟调用

也可以把TIF_NEED_RESCHED标志设置为1，而以延迟方式调用调度程序。由于总是在恢复用户态进程的执行之前检查这个标志的值，所以schedule()将在不久之后的某个时间被明确地调用。

 

延迟调用调度程序的典型例子：

*当current进程用完了它的CPU时间片时，由scheduler_tick()函数完成schedule()的延迟调用。

*当一个被唤醒进程的优先权比当前进程的优先权高时，由try_to_wake_up()函数完成schedule()的延迟调用。

*当发出系统调用sched_setscheduler()时

 

进程切换之前schedule()所执行的操作

schedule()函数的任务之一是用另外一个进程来替换当前正在执行的进程。如果系统中没有优先权高于当前进程的可运行进程，最终next与current相等，不发生任何进程切换。schedule()函数在一开始，先禁用内核抢占并初始化一些局部变量：

need_resched:

preempt_disable( );

prev = current;

rq = this_rq( );

 

调用sched_clock()函数以读取TSC，并将它的值转换成纳秒，所获得的时间戳存放在局部变量now中。然后，schedule()计算prev所用的时间片长度：

now = sched_clock( );

run_time = now - prev->timestamp;

if (run_time > 1000000000)

run_time = 1000000000;

通常使用限制在1秒（要转换成纳秒）的时间。run_time的值用来限制进程对CPU的使用

 

在开始寻找可运行进程之前，schedule()必须关掉本地中断，并获得所要保护的运行队列的自旋锁：spin_lock_irq(&rq->lock);

 

接下来，schedule()检查prev的状态，如果不是可运行状态，而且它没有在内核态被抢占（见第四章“从中断和异常返回”一节），就应该从运行队列删除prev进程。不过，如果它是非阻塞挂起信号，而且状态为TASK_INTERRUPTIBLE，函数就把该进程的状态设置为TASK_RUNNING，并将它插入运行队列。这个操作与把处理器分配给prev是不同的，它只是给prev一次被选中执行的机会。

if (prev->state != TASK_RUNNING &&

!(preempt_count() & PREEMPT_ACTIVE)) {

if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev))

prev->state = TASK_RUNNING;

else {

if (prev->state == TASK_UNINTERRUPTIBLE)

rq->nr_uninterruptible++;

deactivate_task(prev, rq);

}

}

 

函数deactivate_task()从运行队列中删除该进程。现在，schedule()检查运行队列中剩余的可运行进程数。如果有可运行的进程，schedule()就调用dependent_sleeper()函数，在绝大多数情况下，该函数立即返回0。

if (rq->nr_running){

if (dependent_sleeper(smp_processor_id(),rq)){

next=rq->idle;

goto switch_tasks;

} }

如果运行队列中没有可运行的进程存在，函数就调用idle_balance()，从另外一个运行队列迁移一些可运行进程到本地运行队列中。

如果idle_balance()没有成功地把进程迁移到本地运行队列中，schedule()就调用wake_sleeping_dependen t()重新调度空闲CPU（ 即每个运行swapper进程的CPU）中的可运行进程。

我们假设schedule()函数已经肯定运行队列中有一些可运行的进程，现在它必须检查这些可运行进程中是否至少有一个进程是活动的，如果没有，函数就交换运行队列数据结构的active和expired字段的内容，因此，所有的过期进程变为活动进程，而空集合准备接纳将要过期的进程。

array = rq->active;

if (!array->nr_active) {

rq->active = rq->expired;

rq->expired = array;

array = rq->active;

rq->expired_timestamp = 0;

rq->best_expired_prio = 140;

}

现在可以在活动的prio_array_t数据结构中搜索一个可运行进程了。首先，schedule()搜索活动进程集合位掩码的第一个非0位。回忆一下， 当对应的优先权链表不为空时，就把位掩码的相应位置1。因此，第一个非0位的下标对应包含最佳运行进程的链表，随后，返回该链表的第一个进程描述符：

idx=sched_find_first_bit(array->bitmap);

next=list_entry(array->queue[idx].next,task_t,run_list);

函数sched_find_first_bit()是基于bsf l汇编语言指令的，它返回32位字中被设置为1的最低位的位下标。

局部变量next现在存放将取代prev的进程描述符。schedule()函数检查next->activated字段，该字段的编码值表示进程在被唤醒时的状态，如表7-6所示：

值
 说明
 
0
 进程处于TASK_RUNNING状态
 
1
 进程处于TASK_INTERRUPTIBLE或TASK_STOPPED状态， 而且正在被系统调用服务例程或内核线程唤醒。
 
2
 进程处于TASK_INTERRUPTIBLE或TASK_STOPPED状态， 而且正在被中断处理程序或可延迟函数唤醒。
 
-1
 进程处于TASK_UNINTERRUPTIBLE状态而且正在被唤醒。
 

 

如果next是一个普通进程而且它正在从TASK_INTERRUPTIBLE或TASK_STOPPED状态被唤醒，调度程序就把自从进程插入运行队列开始所经过的纳秒数加到进程的平均睡眠时间中。换而言之，进程的睡眠时间被增加了，以包含进程在运行队列中等待CPU所消耗的时间。

 

schedule()完成进程切换时所执行的操作

现在schedule()函数已经要让next进程投入运行。内核将立刻访问next进程的thread_info数据结构，它的地址存放在next进程描述符的接近顶部的位置。

switch_tasks:

prefetch(next);

prefetch宏提示CPU控制单元把next进程描述符的第一部分字段的内容装入硬件高速缓存，正是这一点改善了schedule()的性能。

 

prev->timestamp=prev->last_ran =now;

随后更新进程的时间戳。

prev和next很可能是同一个进程：在当前运行队列中没有优先权较高或相等的其他活动进程时，会发生这种情况。在这种情况下，函数不做进程切换：

if (prev==next){

spin_unlock_irq(&rq->lock);

goto finish_schedule;}

这里，prev和next是不同的进程，进程切换确实发生了：

next->timestamp = now;

rq->nr_switches++;

rq->curr = next;

prev = context_switch(rq, prev, next);

 

context_switch()函数建立next的地址空间。进程描述符的active_mm 字段指向进程所使用的内存描述符，而mm字段指向进程所拥有的内存描述符。对于一般的进程，这两个字段有相同的地址，但是，内核线程没有它自己的地址空间而且它的mm字段总是被设置为NULL。

context_switch()函数保证：如果next是一个内核线程，它使用prev所使用的地址空间：

if (!next->mm) {

next->active_mm = prev->active_mm;

atomic_inc(&prev->active_mm->mm_count);

enter_lazy_tlb(prev->active_mm, next);

}

 

一直到Linux 2.2 版，内核线程都有自己的地址空间，因此不管什么时候当调度程序选择一个新进程（即使是一个内核线程）运行时，都必须改变页表；因为内核线程都运行在内核态，它仅使用线性地址空间的第4个GB ，其映射对系统的所有进程都是相同的。因为如果next 是内核线程，就根本不触及页表。

相反，如果next 是一个普通进程，schedule( ) 函数用next 的地址空间替换prev 的地址空间：

if (next->mm)

switch_mm(prev->active_mm, next->mm, next);

 

如果prev 是内核线程或正在退出的进程，context_switch()函数就把指向prev 内存描述符的指针保存到运行队列的prev_mm 字段中，然后重新设置prev->active_mm：

if (!prev->mm) {

rq->prev_mm = prev->active_mm;

prev->active_mm = NULL;

}

 

现在，context_switch()终于可以调用switch_to()执行prev和next之间的进程切换了：switch_to(prev,next,prev);

return prev;

 

进程切换后schedule()所执行的操作

schedule( ) 函数中在switch_to 宏之后紧接着的指令并不由next 进程立即执行，而是稍后当调度程序选择prev 又执行时由prev 执行。

 

进程切换后的第一部分指令是：

barrier();

finish_task_switch(prev);

在schedule()中，紧接着context_switch()函数调用之后，宏barrier()产生一个代码优化屏障。然后，执行finish_task_switch()函数：

 

mm = this_rq( )->prev_mm;

this_rq( )->prev_mm = NULL;

prev_task_flags = prev->flags;

spin_unlock_irq(&this_rq( )->lock);

if (mm)

mmdrop(mm);

if (prev_task_flags & PF_DEAD)

put_task_struct(prev);

 

如果prev是一个内核线程，运行队列的prev_mm 字段存放借给prev的内存描述符的地址。

finish_task_switch()函数还要释放运行队列的自旋锁并打开本地中断。然后，检查prev是否是一个正在从系统中被删除的僵死任务， 如果是，就调用put_task_struct()以释放进程描述符引用计数器，并撤消所有其余对该进程的引用。

schedule()函数的最后一部分指令是：

finish_schedule:

prev = current;

if (prev->lock_depth >= 0)

_ _reacquire_kernel_lock( );

preempt_enable_no_resched();

if (test_bit(TIF_NEED_RESCHED, ¤t_thread_info( )->flags)

goto need_resched;

return;

 

如你所见，schedule()在需要的时候重新获得大内核锁、重新启用内核抢占、并检查是否一些其他的进程已经设置了当前进程的TIF_NEED_RESCHED标志，如果是，整个schedule()函数重新开始执行，否则，函数结束。

 

schedule()函数从本地CPU的运行队列挑选新进程运行。因此，一个指定的CPU只能执行它相应的运行队列中的可运行进程。另外，一个可运行进程总是存放在某一个运行队列中：任何一个可运行进程都不可能同时出现在两个或多个运行队列中。因此，一个保持可运行状态的进程通常被限制在一个固定的CPU上。这种设计通常对系统性能是有益的，因为，运行队列中的可运行进程所拥有的数据可能填满每个CPU的硬件高速缓存。但是，在有些情况下，把可运行进程限制在一个指定的CPU上可能引起严重的性能损失。如系统中一个CPU将会超负荷，而其他一些CPU几乎处于空闲状态。因此，内核周期性地检查运行队列的工作量是否平衡，并在需要的时候，把一些进程从一个运行队列迁移到另一个运行队列。

 

与调度相关的系统调用
总统来说，系统调用允许进程改变它们的优先级及调度策略。作为一般原则，总是允许用户降低他们进程的优先级。然而，如果他们想修改属于其他某一用户进程的优先级，或者如果他们想增加他们自己进程的优先级，那么，他们必须拥有超级用户的特权。

 

nice( )
系统调用nice( )允许进程改变它们的基本优先级。包含在increment 参数中的整数值用来修改进程描述符的nice 字段。从传统上来说，负值相当于请求优先级增加，并请求超级特权，而正值相当于请求优先级减少。

 

获得本地运行队列锁，更新current进程的静态优先权，调用resched_task()函数以允许其他进程抢占current进程，并释放运行队列锁。

 

getpriority()和setpriority()系统调用
nice( ) 系统调用只影响调用它的进程，而另外两个系统调用getpriority( ) 和setpriority( ) 则作用于给定组中所有进程的基本优先级。getpriority( ) 返回20 减去给定组中所有进程之中最低nice 字段的值；setpriority( ) 把给定组中所有进程的基本优先级都设置为一个给定的值。