Linux 进程调度


308 第十章 进程调度 Linux 与任何分时系统一样,通过一个进程到另一个进程的快速切换,多个进程的 并发执行达到了不可思议的效果。进程切换本身已在第三章中讨论过 , 本章讨论进 程调度,主要关心什么时候进行进程切换及选择哪一个进程来运行。 本章由三部分组成。“调度策略”一节从理论上介绍 Linux 进行进程调度所做的选 择,“调度算法”一节讨论实现调度和相应的算法所采用的数据结构,最后, “与调 度相关的系统调用”一节描述了影响进程调度的系统调用。 调度策略 传统Unix操作系统的调度算法必须实现几个互相冲突的目标:进程响应时间尽可能 快,后台作业的吞吐量尽可能高,进程的饥饿现象尽可能避免,低优先级和高优先 级进程的需要尽可能调和等等。决定什么时候以怎样的方式选择一个新进程运行的 这组规则就是所谓的调度策略(scheduling policy)。 Linux 的调度是基于第五章已介绍的分时技术( time-sharing)。允许多个进程 “并 发”运行就意味着 CPU 的时间被粗略地分成“片” ,给每个可运行进程分配一片 (注 1)。当然,单处理器在任何给定的时刻只能运行一个进程。当一个并发执行的 注 1:运行CPU 时,调度算法不会选择调用已被停止和已被挂起的进程。 309进程调度 进程其时间片或时限( quantum)到期时还没有终止,进程切换就可以发生。分时 依赖于定时中断,因此,对进程是透明的。为保证 CPU 分时,不需要在程序中插入 额外的代码。 调度策略也是基于依照优先级排队的进程。有时用复杂的算法求出进程当前的优先 级,但最后的结果是相同的:每个进程都与一个值相关联,这个值表示把进程如何 适当地分配给 CPU。 在 Linux 中,进程的优先级是动态的。调度程序跟踪进程做了些什么,并周期性地 调整它们的优先级。在这种方式下,在较长的时间间隔内没有使用 CPU的进程,通 过动态地增加它们的优先级来提升它们。相应地,对于已经在 CPU上运行了较长时 间的进程,通过减少它们的优先级来处罚它们。 当谈及有关调度问题时,传统上把进程分类为“ I/O 范围( I/O-bound)”或“ CPU 范围( CPU-bound)”。前者频繁地使用I/O设备,并花费很多时间等待 I/O操作的完 成;而后者是需要大量 CPU 时间的数值计算应用程序。 另一种分类法把进程区分为三类: 交互式进程(Interactive process) 这些进程经常与用户进行交互,因此,要花很多时间等待击键和鼠标操作。当 输入被接受时,必须很快地唤醒进程,否则,用户将发现系统反应迟钝。典型 的情况是,平均延迟必须低于 50到 150ms。这样的延迟变化也必须进行限制, 否则,用户将发现系统是不稳定的。典型的交互式程序是命令 shell、文本编辑 程序及图形应用程序 。 批处理进程(Batch process) 这些进程不必与用户交互,因此,它们经常在后台运行。因为这样的进程不必 被很快地响应,因此,它们常受到调度程序的处罚。典型的批处理进程是程序 设计语言的编译程序、数据库搜索引擎及科学计算。 实时进程( Real-time process) 这些进程有很强的调度需要。这样的进程决不会被低优先级的进程阻塞,它们 应该有一个短的响应时间,更重要的是,这个响应时间应该有很小的变化。典 型的实时程序有视频和音频应用程序、机器人控制程序及从物理传感器上收集 数据的程序。 310 第十章 我们刚刚提到的两种分类法有点相互独立。例如,一个批处理进程可能既是 I/O 范 围(如数据库服务器)也是 CPU 范围(如图象着色程序)。在 Linux 中,调度算法 可以明确地确认所有实时程序的身份,但没有办法区分交互式程序和批处理程序。 为了为交互式应用程序提供好的响应时间, Linux(与所有的Unix内核类似)隐含 地支持 I/O 范围的进程胜过 CPU 范围的进程。 程序员可以通过表10-1所列的系统调用改变调度参数。更详细的内容将在“与调度 相关的系统调用”一节中给出。 表 10-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不支持很多过分要求的实时应用,因为Linux的内核是非抢占式的(参 见后面的“调度算法的性能”一节)。 进程的抢占 如第一章所述,Linux 的进程是抢占式的。如果进程进入 TASK_RUNNING 状态,内 核检查它的动态优先级是否大于当前正运行进程的优先级。如果是,current的执 行被中断,并调用调度程序选择另一个进程运行(通常是刚刚变为可运行的进程)。 311进程调度 当然,进程在它的时间片到期时也可以被抢占。如第五章中的“ CPU的分时”一节 中所提到的,此时设置当前进程的 need_resched域,以便定时中断处理程序终止 时调用调度程序。 例如,让我们考虑一种情况,在这种情况中,只有一个正文编辑程序和一个编译程 序正在被执行。正文编辑程序是一个交互式程序,因此, 它的优先级高于编译程序。 不过,因为编辑程序交替于暂停思考与数据输入之间,因此,它经常被挂起;此外, 两次击键之间的平均延迟相对较长。然而,只要用户一按键,中断就发生,内核唤 醒正文编辑进程。内核也确定编辑进程的动态优先级确实是高于current的优先级 (当前正运行的进程,即编译进程) ,因此,设置编辑进程的 need_resched 域,如 此来强迫内核处理完中断时激活调度程序。调度程序选择编辑进程并执行任务切换; 结果,编辑进程很快恢复执行, 并把用户敲的字符回显在屏幕上。当处理完字符时, 正文编辑进程自己挂起等待下一次击键,编译进程恢复执行。 注意被抢占的进程并没有被挂起,因为它还处于 TASK_RUNNING状态,只不过不再 使用 CPU。 一些实时操作系统具有抢占式内核的特点,这就意味着正如在用户态一样,任何一 条指令执行之后,在内核态运行的进程可能被中断。 Linux 内核不是抢占式的,这 意味着进程只有在用户态运行时才能被抢占。非抢占式内核的设计非常简单,因为 内核数据结构的大部分同步问题很容易被避免(参见第十一章中的“内核态进程的 非抢占性”一节) 。 一个时间片必须维持多长? 时间片的长短对系统性能是很关键的:它既不能太长也不能太短。 如果时间片太短,由任务切换引起的系统额外开销就变得非常高。例如,假定任务 切换需要 10ms,如果时间片也是 10ms,那么,CPU 至少把50%的时间花费在任务 切换上( 注 2)。 如果时间片太长,进程看起来就不再是并发执行。例如,让我们假定把时间片设置 注 2: 实际上,事情比这里所介绍的可能更糟糕。例如,在进程的时间片中还要计算进程切 换所需的时间,那么所有的 CPU 时间会花费在进程切换,就没有进程能够执行完。 312 第十章 为 5 秒,那么,每个可运行进程运行大约 5 秒,但是暂停的时间更长(典型的是 5 秒 乘以可运行进程的个数) 。 通常认为长的时间片降低交互式应用程序的响应时间,但这往往是错误的。正如本 章前面“进程的抢占”一节中所描述的那样,交互式进程有相对较高的优先级,因 此,不管时间片是多长,它们很快地抢占批处理进程。 在一些情况下,一个太长的时间片会降低系统的响应能力。例如,假定两个用户在 各自的shell提示符下输入两条命令,一条是 CPU范围的,而另一条是交互式应用。 两个shell都创建一个新进程,并把用户命令的执行委托给新进程。此外,又假定这 样的新进程最初有相同的优先级( Linux 预先并不知道执行进程是批处理的还是交 互式的) 。现在,如果调度程序选择 CPU 范围的进程执行,那么,另一个进程开始 执行前就可能要等待一个时间片。因此,如果这样的时间片较长,那么,看起来系 统可能对用户的请求反应迟钝。 时间片大小的选择总是一种折衷。Linux 采取单凭经验的方法,即选择尽可能长的 一个时间片,同时能保持良好的响应时间。 调度算法 Linux调度算法把 CPU 的时间划分为时期( epoch)。在一个单独的时期内,每个进 程有一个指定的时间片,时间片持续时间从这个时期的开始计算。一般情况下,不 同的进程有不同大小的时间片。时间片的值是在一个时期内,分配给进程的最大 CPU时间部分。当一个进程用完它的时间片时,这个进程被抢占,并用另一个可运 行进程代替它。当然,在同一时期内,一个进程可以几次被调度程序选中(只要它 的时间片还没用完) ,例如,如果进程挂起自己,等待 I/O,那么,它还剩余一些时 间片,并可以在同一时期内再度被选中。当所有的可运行进程都用完它们的时间片 时,一个时期才结束; 在这种情况下,调度程序的算法重新计算所有进程的时间片, 然后,一个新的时期开始。 每个进程有一个基本的时间片( base time quantum):如果进程在前一个时期内已 用完它的时间片,那么这个时间片值就是调度程序赋给进程的基本时间片。用户可 以通过nice()和setpriority()系统调用来改变进程的基本时间片(参见本章后 面“与调度相关的系统调用”一节) 。新进程总是继承父进程的基本时间片。 313进程调度 INIT_TASK 宏把进程 0(swapper)的基本时间片设置为 DEF_PRIORITY。宏的定义 如下: #define DEF_PRIORITY (20*HZ/100) 因为表示定时中断频率的HZ在 IBM PC中被设置为 100(参见第五章中的“可编程 间隔定时器”一节) ,因此,DEF_PRIORITY 的值是 20 个节拍,即大约 210ms。 用户很少改变他们进程的基本时间片,因此, DEF_PRIORITY 也表示系统中大多数 进程的基本时间片。 为了选择一个进程运行,Linux 调度程序必须考虑每个进程的优先级。实际上,有 两种优先级: 静态优先级(Static priority) 这种优先级由用户赋给实时进程,范围从 1 到 99,调度程序从不改变它。 动态优先级(Dynamic prority) 这种优先级只应用于普通进程。实质上它是基本时间片[由此也叫进程的基本 优先级( base priority)]与当前时期内的剩余时间片之和。 当然,实时进程的静态优先级总是高于普通进程的动态优先级,只有当 TASK_ RUNNING 状态没有实时进程时,调度程序才开始运行普通进程。 调度程序使用的数据结构 我们回忆一下第三章的“进程描述符”一节,进程链表把所有进程的描述符链接在 一起,而运行队列链表把所有可运行状态(即 TASK_RUNNING 状态)的进程描述符 链接在一起。在这两种情况下, init_task 进程描述符起链表头的作用。 每个进程描述符包含与调度有关的几个域: need_resched 由 ret_from_intr()检查的一个标志,决定是否调用 schedule()函数(参 见第四章中的“ ret_from_intr()函数”一节) 。 policy 调度的类型,允许的取值是: 314 第十章 SCHED_FIFO 先入先出的实时进程。当调度程序把 CPU分配给一个进程时,该进程的描 述符还留在运行队列链表的当前位置。如果没有其他更高优先级的实时进 程是可运行的,这个进程就可以随心所欲地使用 CPU,即使具有相同优先 级的其他实时进程是可运行的。 SCHED_RR 循环轮转的实时进程。当调度程序把 CPU分配给一个进程时,把这个进程 的描述符就放在运行队列的末尾。这种策略确保了把CPU时间公平地分配 给具有相同优先级的所有 SCHED_RR 实时进程。 SCHED_OTHER 普通的分时进程。 policy 域也对 SCHED_YIELD 二进制标志进行编码。当进程调用 sched_ yield()系统调用(不需要开始 I/O操作或睡眠就自愿放弃处理器的一种方式) 时,这个标志被设置。 调度程序就把这个进程描述符放在运行队列链表的末尾 (参见“与调度相关的系统调用”一节) 。 每当内核在执行一个较长而非紧急的任务,但又希望给其他进程一个运行的机 会时,内核也设置 SCHED_YIELD 标志,并调用 schedule()函数。 rt_priority 实时进程的静态优先级。普通进程不用这个域。 priority 进程的基本时间片(或基本优先级) 。 counter 进程的时间片用完之前剩余的 CPU 时间的节拍。当一个新的时期开始时,这 个域包含进程的时间片。回想一下, update_process_times()函数在每个 节拍把当前进程的 counter 域减 1。 当一个新的进程被创建时,do_fork()以下列方式设置 current(父)和 p(子) 进程的 counter 域。 current->counter >>= 1; p->counter = current->counter; 315进程调度 换句话说,父进程剩余的节拍数被分成两部分,一部分给父进程,另一部分给子进 程。这样做是为了防止用户使用下列方法无限制地使用CPU的时间:父进程创建了 运行相同代码的子进程,然后杀死自己。通过适当地调节创建速度,子进程就可以 在父进程的时间片用完之前总是获得一个新的时间片。这种编程技巧现在不起作用, 因为内核不奖赏fork。类似地,用户不能通过在shell下启动很多后台进程或在图形 化桌面上打开很多窗口而贪婪地不公平地共享处理器。更一般地说,一个进程不能 通过创建很多后代而占有资源。 注意,priority和counter域在不同种类的进程中起的作用不同。对于普通进程, 用它们既实现分时也计算进程的动态优先级。对于 SCHED_RR 实时进程,只用它们 实现分时。最后,对于 SCHED_FIFO 实时进程,根本就不用它们,因为调度算法认 为这种时间片是无限制的。 schedule()函数 schedule()实现调度程序。它的目的是在运行队列链表中找到一个进程,然后把 CPU 分配给它。几个内核例程以直接或松散的方式调用它。 直接调用(direct invocation) 因为current进程所需的资源无法得到满足而必须被立即阻塞时,就直接调用调度 程序。在这种情况下,要阻塞 current 的内核例程按如下方式进行: 1. 把 current 插入到合适的等待队列中 2. 把current当前的状态改变为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE 3. 调用 schedule() 4. 检查那个资源是否可用;如果不,转到第 2 步 5. 一旦那个资源成为可用的,把 current 从等待队列中删除 正如所看到的,内核例程反复地检查进程所需的资源是否可用,如果不可用,就通 过调用 schedule()把 CPU 让给某一其他进程。随后,当调度程序又把 CPU 返还 给这个进程时,又得检查资源的可用性。 你可能已注意到,这些步骤类似于在第三章的“等待队列”一节中所描述的 316 第十章 sleep_on()和interruptible_sleep_on()函数所实现的那些步骤。不过,我们 在这里讨论的这个函数,只要进程一被唤醒就立即从等待队列中删除它。 执行长的、重复的任务的很多设备驱动程序也直接调用调度程序。在每次反复循环 中,驱动程序都检查 need_resched 域的值,如果必要,调用 schedule()主动放 弃 CPU。 松散调用( lazy invocation) 也可以通过把current的need_resched域设置为1,以松散的方式调用调度程序。 因为对这个域值的检查总是在用户态的进程恢复执行之前进行(参见 第四章中的 “从中断和异常返回”一节) ,因此,在将来某一特定的时间, schedule()被明确 地调用。 调度程序的松散调用在下列情况下被执行: ● 当 current用完它的CPU时间片,这是通过 update_process_times()函数 进行的。 ● 当一个进程被唤醒,并且它的优先级高于 current 进程的优先级。这个任务由 reschedule_idle()函数执行,而它是由 wake_up_process()函数调用的 (参见第三章中的“标识一个进程”一节) : if (goodness(current, p) > goodness(current, current)) current->need_resched = 1; (在后面的“如何衡量一个可运行进程?”一节中将描述 goodness()函数) 。 ● 当发出一个 sched_setscheduler()或 sched_ yield()系统调用时(参见 本章后面“与调度相关的系统调用”一节) 。 schedule()所执行的操作 在实际调度一个进程之前,先运行其他内核控制路径在各种队列中剩余的函数,然 后 schedule()函数才开始运行。schedule()调用 run_task_queue()执行 tq_ scheduler任务队列上的函数。当一个函数必须延迟执行直到下一次schedule()调 用时,Linux 就把这个函数放到 tq_scheduler 任务队列中: run_task_queue(&tq_scheduler); 317进程调度 schedule()还执行所有活动的、未屏蔽的下半部分。这些下半部分通常执行由设 备驱动程序请求的任务(参见第四章中的“下半部分”一节) : if (bh_active & bh_mask) do_bottom_half(); 现在,到了实际的调度,由此可能发生一个进程切换。 current 的值被保存在 prev 局部变量中,并把 prev 的 need_resched 域置 0。 schedule()函数的关键操作是设置另一个局部变量next,以使 next代替 prev而 指向被选中的进程的描述符。 首先,进行一个检查以确定 prev 是不是用完时间片的循环轮转实时进程( policy 域被设置为 SCHED_RR)。如果是,schedule()给prev 分配一个新的时间片,并把 它放到运行队列链表的末尾: if (!prev->counter && prev->policy == SCHED_RR) { prev->counter = prev->priority; move_last_runqueue(prev); } 现在,schedule()检查 prev 的状态。如果 prev 有非阻塞的挂起信号且它的状态 为 TASK_INTERRUPTIBLE,就以如下方式唤醒这个进程。这种操作与把处理器分配 给 prev 不同,这仅仅是给 prev 一个被选择执行的机会。 if (prev->state == TASK_INTERRUPTIBLE && signal_pending(prev)) prev->state = TASK_RUNNING; 如果prev不是在TASK_RUNNING状态, prev进程本身就直接调用schedule(),因 为 prev 必须等待某一外部资源。因此,必须从运行队列链表中删除 prev: if (prev->state != TASK_RUNNING) del_from_runqueue(prev); 接下来,schedule()必须选择在下一个时间片内要执行的进程。于是,函数扫描 运行队列链表。这是从 init_task[进程 0(swapper)的描述符]的 next_run 域 所指向的进程开始的,目的是把最高优先级进程的描述符指针保存在 next中。为 了做到这点,把 next 初始化为要检查的第一个可运行进程,把 c 初始化为它的 “goodness”(参见后面“如何衡量一个可运行进程?”一节) 。 318 第十章 if (prev->state == TASK_RUNNING) { next = prev; if (prev->policy & SCHED_YIELD) { prev->policy &= ~SCHED_YIELD; c = 0; } else c = goodness(prev, prev); } else { c = -1000; next = &init_task; } 如果prev->policy的SCHED_YIELD标志被设置,prev就发出sched_yield()系 统调用自愿放弃 CPU。在这种情况下,这个函数把 0 赋给它的 goodness。 现在,schedule()在可运行进程队列上重复调用 goodness()函数以确定最佳候 选者: p = init_task.next_run; while (p != &init_task) { weight = goodness(prev, p); if (weight > c) { c = weight; next = p; } p = p->next_run; } 通过while循环在运行队列上选择第一个具有最大权值的进程。如果前一个进程是 可运行的,那么,对具有相同优先级的其他可运行进程而言,这个进程就是首选的。 注意,如果运行队列链表为空(除了 swapper,没有可运行进程存在) ,就不进入循 环,并且 next 指向 init_task。此外,如果运行队列链表中所有进程的优先级都 小于或等于 prev 的优先级,那么,不发生进程切换,原来的进程将继续执行。 在退出循环时还必须做进一步的检查,以确定 c 是否为 0。这只发生在运行队列中 的所有进程都用完了它们的时间片,即它们所有的 counter域为 0 时。当这种情况 发生时,一个新的时期开始,因此, schedule()给所有现有的进程(不仅仅指 TASK_RUNNING 进程)分配一个新的时间片,其大小为 priority 的值加 counter 值的一半: 319进程调度 if (!c) { for_each_task(p) p->counter = (p->counter >> 1) + p->priority; } 在这种方式下,挂起和停止的进程让它们的动态优先级周期性地增加。如前所述, 对挂起和停止进程 counter 值增加的基本原理是对 I/O 范围的进程给予优先选择。 然而,即使增加无数次后, counter 的值永远也不会变得大于priority 值的两倍 (注 3)。 现在到了 schedule()的结束部分。如果已选择了一个进程(除了 prev),进程切 换必须发生。不过,执行切换前, kstat 的context_swtch 域增加1 以更新由内核 维护的统计数据: if (prev != next) { kstat.context_swtch++; switch_to(prev,next); } return; 注意,从 schedule()退出的return语句并不是由 next进程立即执行,而是稍后 一点在调度程序又选择 prev 执行时由 prev 进程执行。 如何衡量一个可运行进程? 调度算法的核心是在运行队列链表的所有进程中确定最佳候选者。这就是 goodness()函数所做的事情。它接受 prev(前一个运行进程的描述符指针)和 p (要评估的进程描述符指针)作为输入参数。由 goodness()返回的c 整数值反映了 p 的“值得运行的程度( goodness)”,并有如下含义: c = -1000 永远不必选中 p。当运行队列链表只包含 init_task 时返回这个值。 注 3:假设priority 和 counter 的值都等于 P;那么几何级数 p ×(1+ + + +...)收敛 至 2 × p。 2 1 4 1 8 1 320 第十章 c = 0 p 用完了它的时间片。除非 p 是运行队列链表中的第一个进程,并且所有的可 运行进程也用完了它们的时间片,否则,不会选中 p 运行。 0 < c < 1000 p 是没有用完时间片的普通进程。c 较大时表示 goodness 的更高级。 c >= 1000 p 是实时进程。c 较大时表示 goodness 的更高级。 goodness()函数等价于: if (p->policy != SCHED_OTHER) return 1000 + p->rt_priority; if (p->counter == 0) return 0; if (p->mm == prev->mm) return p->counter + p->priority + 1; return p->counter + p->priority; 如果是实时进程,把它的 goodness置为至少1000。如果是用完时间片的普通进程, 把它的goodness置为0;否则,把它的 goodness置为p->counter + p->priority。 如果 p 与 prev共享地址空间(即它们进程描述符的 mm 域指向同一内存描述符) , 给 p 一个小小的奖励。这种奖励的基本原理是,如果 p 正好在 prev 之后运行,它 们将使用同一页表,也即同一内存,这样一些有价值的数据可以一直放在硬件的高 速缓存中。 Linux/SMP 调度程序 Linux 为了支持对称多处理器( SMP)体系结构,必须对 Linux 的调度程序稍做修 改。实际上,每个处理器运行它自己的 schedule()函数,但是,处理器必须交换 信息以提高系统性能。 当调度程序计算一个可运行进程的goodness时,还应该考虑这个进程是运行在以前 运行的CPU上还是运行在另一个CPU 上。一直运行在同一 CPU上的进程总是首选 的,因为 CPU的硬件高速缓存可能依然包含有用的数据。这条规则有助于减少高速 缓存的不命中数。 321进程调度 然而,让我们假定, CPU1正在运行一个进程时,第二个高优先级的曾在 CPU2上运 行的进程变为可运行的。现在内核面临一种有趣的两难选择:是应该在 CPU1上立 即执行高优先级的进程呢,还是应该延迟那个进程的执行直到 CPU2变为可用?在 前一种情况下,硬件高速缓存的内容被抛弃;在后一种情况下, CPU2正在运行idle 进程( swapper)时, SMP 的并行性并没有得到充分地挖掘。 为了达到较好的系统性能,Linux/SMP采取一种经验性的规则来解决这种两难情况。 采取的选择总是一种折衷,并且这种平衡主要依赖于集成到每个CPU中的硬件高速 缓存:高速缓存越大,保持一个进程在那个 CPU 上就越便利。 Linux/SMP 调度程序的数据结构 aligned_data表包含了每个进程的数据结构,这个表主要用来很快地获得当前进 程的描述符。表中每个元素的填充是通过调用 schedule()函数进行的,其结构如 下: struct schedule_data { struct task_struct * curr; unsigned long last_schedule; }; curr 域指向在相应 CPU 上正在运行进程的描述符,而 last_schedule 域指定什 么时候 schedule()选 curr 作为运行进程。 进程描述符中包含了几个与 SMP 相关的域。特别是, avg_slice 域保持对进程 平均时间片的跟踪,processor 域存放执行进程的最后一个 CPU 的逻辑标识符。 cacheflush_time变量包含对硬件高速缓存内容全部重写所花费的CPU最小周期 数的粗略估计。它由 smp_tune_scheduling()函数初始化为: 以KB为大小的高速缓存 5000 以kHz为单位的CPU频率 Intel Pentium 处理器有8MB 的硬件高速缓存,因此,它们的 cacheflush_time 被 初始化为几百个 CPU周期,即几微秒。最近 Intel处理器有了较大的硬件高速缓存, 因此,最小的高速缓存刷新时间范围从 50 到 100 微秒。 322 第十章 我们将在后面看到,如果cacheflush_time大于某一当前运行进程的平均时间片, 就不会执行进程的抢占,因为在这种情况下,把进程绑定到最后执行的处理器上是 很方便的。 schedule()函数 当 schedule()函数在 SMP 系统上执行时,它进行下列操作: 1. 照样执行 schedule()的初始化部分。 2. 在this_cpu局部变量中存放正在执行的处理器的逻辑标识符。这个值由prev 的 processor 域来读取。 3. 初始化sched_data局部变量,以便它指向this_cpu CPU的schedule_data 结构。 4. 重复调用 goodness()以选择将要执行的新进程。这个函数也检查进程的 processor 域,并对最后在 this_cpu CPU 上执行的进程给予一定的奖赏 (PROC_CHANGE_PENALTY,通常为 15)。 5. 如果必要,照样重新计算进程的动态优先级。 6. 把 sched_data->curr 置为 next。 7. 把 next->has_cpu 置为 1,next->processor 置为 this_cpu。 8. 在 t 局部变量中存放 current 时间标记寄存器的值。 9. 在 this_slice 局部变量中存放 prev 的最后时间片,这个值是 t 与 sched_ data->last_schedule 的差。 10. 把 sched_data->last_schedule 置为 t。 11. 把 prev的avg_slice域置为( prev->avg_slice+this_slice)/2,换句话 说,更新平均值。 12. 执行上下文切换。 13. 当内核返回到这儿时,以前的进程又被调度程序选中, prev 局部变量现在指 向刚刚被代替的进程。如果 prev还依然是可运行的,并且不是这个 CPU的空 任务,那么,对 prev 调用 reschedule_idle()函数。 323进程调度 14. 把 prev 的 has_cpu 域置为 0。 reschedule_idle()函数 当进程p变为可运行时, reschedule_idle()函数被调用[参见前面的 “schedule() 函数”一节] 。在 SMP 系统上,这个函数决定进程是否应该抢占某一 CPU上的当前 进程。它执行下列操作: 1. 如果 p 是实时进程,总会试图执行抢占,转到第 3 步。 2. 如果有一个 CPU 上的当前进程满足下列两个条件( 注 4),则立即返回(不试 图抢占) : — cacheflush_time大于当前进程的平均时间片。如果这个条件为真,则这 个进程没有使高速缓存变得太“脏” 。 — 为了存取某一临界内核数据结构,p 和当前进程都需要全局内核锁(参见 第十一章中的“全局内核锁和局部内核锁”一节) 。必须执行这种检查,因 为替换一个进程(保持着另一个进程所需的锁)并不是富有成效的。 3. 如果 p->processor CPU(p 最后运行的 CPU)为空,就选它。 4. 否则,对于在某个 CPU 上运行的每个任务 tsk 计算差: goodness(tsk, p) - goodness(tsk, tsk) 假定这个差为正,就选择这个差值最大的 CPU。 5. 如果已选择了CPU,设置相应正运行进程的need_resched域,并向那个处理 器发送一条“ reschedule”消息(参见第十一章中的“处理器间中断”一节) 。 调度算法的性能 Linux 的调度算法既是独立的,也是相对易理解的。因为这个原因,很多内核高手 热衷于试图对之做出改进。然而,调度程序是内核中相当神秘的一部分。当你可以 通过修改几个关键参数而极大地改善它的性能时,通常从理论上不能证明所得结果 是有效的。此外,当用户提出的混合请求(实时、交互式、 I/O 范围、后台等等)变 注 4: 这些条件看起来不可思议,但或许它们是能让 SMP 更好工作的经验性规则。 324 第十章 化较大时,你也不能确信得到的是正面结果还是负面结果。实际上,几乎对每个所 提议的调度策略,都可能产生人为的混合请求,而它们又导致了较差的系统性能。 让我们来略述一下Linux 调度程序的缺陷。正如将描述的那样,有些局限性对具有 很多用户的大型系统影响较大。在一次运行几十个进程的单个工作站上,Linux 调 度程序的效率是相当高的。因为 Linux 诞生于 Intel 80386,并继续在 PC 世界非常 流行,我们认为当前的 Linux 调度程序还相当合适。 这种算法不适合进程数量很大的情况 如果现有的进程数量很庞大,重新计算所有动态优先级就是低效的。 在老式传统的Unix内核中,每秒都计算动态优先级,因此,问题甚至更糟糕。Linux 试图更换一种方法以减少调度程序的额外开销。只有当所有的可运行进程都用完它 们的时间片时,才重新计算优先级。因此,当进程数量较大时,重算过程相当费时, 但计算次数大大减少。 这种简单的方式具有这样的缺点,即当可运行进程的数量很大时,I/O范围的进程很 少被执行,因此,交互式应用有较长的响应时间。 对高负载的系统来说,预定义的时间片太长 用户所感受的系统响应主要依赖于系统的负载,负载指的是可运行进程的平均数, 以及因此而等待 CPU 的时间(注 5)。 如前所述,系统的响应也依赖于可运行进程的平均时间片。在 Linux 中,对于有很 高期望的系统负载,预定义的时间片显得太长。 I/O 范围进程的执行策略不是最佳的 优先选择 I/O 范围进程是确保交互式程序具有短响应时间的好策略,但并不是理想 的策略。几乎没有用户交互的一些批处理程序甚至是 I/O 范围的。例如,考虑一下 数据库搜索引擎,必须从硬盘或网络应用(必须从慢速连接的远程主机搜集数据) 注 5: uptime程序每过1、5、15分钟返回系统负载。也可以通过读取/proc/loadavg 文件来 获得相同的信息。 325进程调度 有代表性地读很多数据。即使这些种类的进程不需要短的响应时间,但它们也是由 调度算法执行的。 另一方面,也是 CPU 范围的交互式程序可能让用户看起来反映迟钝,因为由于 I/O 阻塞操作而引起的动态优先级的增加并不能补偿由于CPU的使用而引起的动态优先 级的减少。 对实时应用的支持是微弱的 正如第一章中提到的,非抢占式内核并不是很适合实时应用,因为在内核态处理中 断或异常可能要花几毫秒。在这期间,变为可运行的实时进程不能被恢复执行。这 对于需要可预知的及要求低响应时间的实时应用是无法接受的( 注 6)。 Linux 的未来版本很可能致力于解决这个问题,或者通过实现 SRV4 的“固定抢占 点”来解决,或者通过使内核完全地可抢占而解决。 然而,内核抢占仅仅是实现有效的实时调度程序的几个必需的条件之一。还有几个 其他的问题必需考虑。例如,实时进程通常必需使用的资源也是普通进程所需的, 直到低优先级的进程释放了某一资源,实时进程才可能因此结束等待,这种现象叫 做优先级倒置( priority inversion)。此外,实时进程可能代表另一个低优先级的进 程(如内核线程) 请求一个内核同意的服务,这种现象叫做隐含调度( hidden scheduling)。一个有效的实时调度程序应该致力于解决这些问题。 与调度相关的系统调用 已经介绍的几个系统调用允许进程改变它们的优先级及调度策略。作为一般规则, 总是允许用户降低他们进程的优先级。然而,如果他们想修改属于其他某一用户进 程的优先级,或者如果他们想增加他们自己进程的优先级,那么,他们必须拥有超 级用户的特权。 注 6: Linux 内核已在几个方面进行了修改,因此,如果一些硬实时工作较短,内核就能处 理它们。硬件中断基本上被捕获,并由一种“超级内核”来监控内核的执行。但这种 改变并不能使 Linux 成为一个真正的实时系统。 注 7: 因为这个系统调用经常用来降低进程的优先级,因此用户在它们的进程中调用它对其 他进程“ nice”。 326 第十章 nice()系统调用 nice()(注 7)系统调用允许进程改变它们的基本优先级。包含在 increment 参数 中的整数值用来修改进程描述符的 priority 域。nice Unix 命令(允许用户运行 修改调度优先级的程序)就是基于这个系统调用的。 sys_nice()服务例程处理nice()系统调用。尽管 increment参数可以有任何值, 但是大于 40 的绝对值被截为 40。从传统上来说,负值相当于请求优先级增加,并 请求超级特权,而正值相当于请求优先级减少。 通过把increment的值拷贝到newprio局部变量,这个函数就开始了。在increment 为负的情况下,调用 capable()函数核实进程是否有 CAP_SYS_NICE 能力 (capability)。我们将在第十九章中与能力的表示一起来讨论这个函数。如果用户趋 于让需要的能力改变优先级,sys_nice()就改变newprio的符号并设置increase 局部标志: increase = 0 newprio = increment; if (increment < 0) { if (!capable(CAP_SYS_NICE)) return -EPERM; newprio = -increment; increase = 1; } 如果 newprio的值大于 40,把它截为40。在这点,newprio局部变量可以是 0~40 之间的任何值,包括 0 和 40。然后,根据调度算法所用的优先级数值范围改变这个 值。因为所允许的最高基本优先级是 2 × DEF_PRIORITY,新的值是: (newpri × 2× DEF_PRIORITY)/40+0.5 以适当的符号把这一结果拷贝到 increment: if (newprio > 40) newprio = 40; newprio = (newprio * DEF_PRIORITY + 10) / 20; increment = newprio; if (increase) increment = -increment; 327进程调度 因为 newprio 是一个整数变量,代码中的表达式与前面所列出的公式是相等的。 然后,从优先级中减去 increment来设置优先级最后的值。不过,进程最后的基本 优先级不能小于 1 或大于 2 × DEF_PRIORITY: if (current->priority - increment < 1) current->priority = 1; else if (current->priority > DEF_PRIORITY*2) current->priority = DEF_PRIORITY*2; else current->priority -= increment; return 0; 调整了优先级的进程如同其他进程一样随着时间的过去而改变,如果必要,获得额 外的优先级,或者退后以服从其他的进程。 getpriority()和 setpriority()系统调用 nice()系统调用只影响调用它的进程,而另外两个系统调用 getpriority()和 setpriority()则作用于给定组中所有进程的基本优先级。getpriority()返回20 加给定组中所有进程之中最高的基本优先级;setpriority()把给定组中所有进程 的基本优先级都设置为一个给定的值。 内核对这两个系统调用的实现是通过sys_getpriority()和sys_setpriority() 服务例程完成的。这两个服务例程本质上作用于一组相同的参数: which 指定进程组。它采用下列值之一: PRIO_PROCESS 根据进程的 ID 选择进程(进程描述符的 pid 域) PRIO_PGRP 根据组 ID 选择进程(进程描述符的 pgrp 域) PRIO_USER 根据用户 ID 选择进程(进程描述符的 uid 域) 328 第十章 Who 用来选择进程的 pid、pgrp 及uid域的值(依赖于用哪个值) 。如果 who是 0, 把它的值设置为当前进程相应域的值。 niceval 新的基本优先级值[仅仅由 sys_setpriority()需要] 。它的取值范围应该 在 -20(最高优先级)和 +20(最小优先级)之间。 正如以前提到的,只有有 CAP_SYS_NICE能力的进程才被允许增加它们自己的基本 优先级或修改其他进程的优先级。 正如我们在第八章已看到的,只有当出现了某一错误时,系统调用才返回一个负值。 因为这个原因,getpriority()不返回-20 到 +20之间正常的 nice值,而是 0~40 之间的一个非负值。 与实时进程相关的系统调用 现在我们介绍一组系统调用,它们允许进程改变调度规则,尤其是可以变为实时进 程。一个进程为了修改任何进程的进程描述符的 rt_priority和policy域(包括 自己的) ,它照样必须具有 CAP_SYS_NICE 能力。 sched_getscheduler()和 sched_setscheduler()系统调用 sched_ getscheduler()查询由pid 参数所标识的进程当前所用的调度策略。如 果 pid等于0,将检索调用进程的策略。如果成功,这个系统调用返回进程的策略: SCHED_FIFO、SCHED_RR 或SCHED_OTHER。相应的sys_sched_getscheduler()服 务例程调用 find_task_by_pid(),后一个函数确定给定 pid 所对应的进程描述 符,并返回 policy 域的值。 sched_setscheduler()系统调用既设置调度策略,也设置由参数 pid 所标识进程 的相关参数。如果 pid 等于 0,调用进程的调度程序参数将被设置。 相应的sys_sched_setscheduler()函数检查由policy参数指定的调度策略和由 param->sched_priority参数指定的新静态优先级是否有效。还检查进程是否有 CAP_SYS_NICE 能力,或它自己是否有超级用户特权。如果每件事都可以,执行下 列语句: 329进程调度 p->policy = policy; p->rt_priority = param->sched_priority; if (p->next_run) move_first_runqueue(p); current->need_resched = 1; sched_getparam()和 sched_setparam()系统调用 sched_getparam()系统调用为pid所标识的进程检索调度参数。如果pid是0,当 前进程的参数被检索。正如你所期望的,相应的sys_sched_getparam()服务例程 找到与 pid相关的进程描述符指针,把它的 rt_priority域存放在类型为 sched_ param的局部变量中,并调用 copy_to_user()把它拷贝到由param参数指定的地 址的进程地址空间。 sched_setparam()系统调用类似于sched_setscheduler(),它与后者的不同在 于不让调用者设置 policy 域的值( 注 8)。相应的 sys_sched_setparam()服务 例程几乎与 sys_sched_setscheduler()相同,但是,受影响进程的 policy从不 被改变。 sched_yield()系统调用 sched_yield()系统调用允许进程在不被挂起的情况下自愿放弃CPU,进程仍然处 于TASK_RUNNING状态,但调度程序把它放在运行队列链表的末尾。在这种方式下, 具有相同动态优先级的其他进程将有机会运行。这个调用主要由 SCHED_FIFO进程 使用。 相应的 sys_sched_yield()服务例程执行这些语句: if (current->policy == SCHED_OTHER) current->policy |= SCHED_YIELD; current->need_resched = 1; move_last_runqueue(current); 注意,只有进程是普通的 SCHED_OTHER 进程时,才在进程描述符的 policy域设置 SCHED_YIELD 域。结果, schedule()的下一次调用将把这个进程当作已用完时间 片的进程来处理[参见 schedule()如何处理 SCHED_YIELD 域]。 注 8: 这种不规则是由 POSIX 标准的一个指定要求所引起的。 330 第十章 sched_get_priority_min()和 sched_get_priority_max()系统调用 sched_get_priority_min()和 sched_get_priority_max()系统调用分别返 回最小和最大实时静态优先级的值,这个值由 policy 参数所标识的调度策略来使 用。 如果current是实时进程,sys_sched_get_priority_min()服务例程返回1,否 则返回 0。 如果 current 是实时进程,sys_sched_get_priority_max()服务例程返回 99 (最高优先级) ,否则返回 0。 sched_rr_get_interval()系统调用 sched_rr_get_interval()系统调用应该为指定的实时进程获得循环轮转的时间 片。 相应的sys_sched_rr_get_interval()服务例程并不像所期望的那样操作,因为 在 tp所指向的timespec 结构中,它总是返回一个 150ms的值。这个系统调用还没 有在 Linux 中有效地实现。 对 Linux 2.4 的展望 对内核线程和僵死进程, Linux 2.4关于TLB的刷新引入一种巧妙的最优化策略。因 此,由 schedule()函数,而不是由 switch_to 宏设置活动的全局页目录。 Linux 2.4 对 SMP 的调度算法已经进行了改进和简化。只要一个新的进程变为可运 行的,内核检查进程的首选 CPU(即最后运行的 CPU)是否为空,如果是,内核把 进程分配给那个 CPU;否则,内核把进程分配给另一个空闲的 CPU。如果所有的 CPU都忙,内核检查进程是否有足够的优先级抢占运行在首选CPU上的进程。如果 没有,只有在新的可运行进程是实时进程或与硬件 cache相比有较短的平均时间片 的情况下,内核才试图抢占某一其他的 CPU。(粗略地说,抢占发生在新的可运行 进程是交互式的且首选 CPU 不立即重新调度时。 )
还剩22页未读

继续阅读

下载pdf到电脑,查找使用更方便

pdf的实际排版效果,会与网站的显示效果略有不同!!

需要 6 金币 [ 分享pdf获得金币 ] 0 人已下载

下载pdf

pdf贡献者

cablist

贡献于2012-11-12

下载需要 6 金币 [金币充值 ]
亲,您也可以通过 分享原创pdf 来获得金币奖励!
下载pdf