第4章 进程调度

调度程序负责决定将哪个进程投入运行，何时运行以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统，是像Linux这样的多任务 *** 作系统的基础。

多任务 *** 作系统就是能同时并发地交互执行多个进程的 *** 作系统。可以分为两类：

进程可以分为I/O消耗型和处理器消耗型（进程可以同时展示这两种行为）。

调度策略通常要在两个矛盾的目标中寻找平衡：进程响应迅速和最大系统利用率。Linux为了保证交互式应用和桌面系统的性能，对进程的响应做了优化（缩短响应时间），更倾向于优先调度I/O消耗型进程。

Linux采用了两种不同的优先级范围：

实时优先级和nice值处于互不相交的两个范畴，任何实时进程的优先级都高于普通进程。

时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。

Linux自2.6内核系统开始引入新的进程调度算法，其中最著名的是“反转楼梯最后期限调度算法（rotating staircase deadline scheduler，RSDL）”，被称为“完成公平调度算法（CFS）”。

Linux的CFS调度器并没有直接分配时间片到进程，而是将处理器的使用比例划分给进程，也就是说，进程所获得的处理器时间和系统负载密切相关的。当一个进程进入可运行状态，他就被准许投入运行。Linux的CFS调度器，其抢占时机取决于新的可运行进程消耗了多少处理器使用比。如果消耗的使用比例比当前进程小，则新的进程立刻投入运行，抢占当前进程，否则推迟运行。

Linux调度器是以模块方式提供的，以允许不同类型的进程可以有针对性地选择调度算法。这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。每个调度器都有一个优先级，基础调度器会按照优先级顺序进程遍历调度类，拥有一个可执行进程的最高优先级的调度类胜出，去选择接下来要执行的程序。

CFS允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行的进程。nice值作为进程获得的处理器运行比的权重，nice值越低权重越高。每个进程都按照其权重在全部可行进程中所占比例的“时间片”来运行，任何进程所获的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标，称为目标延迟。

CFS调度算法的实现，主要关注：

所有的调度器都必须对进程运行时间做记账。CFS通过时间记账确保每个进程只在公平分配给它的处理器时间内运行。

CFS使用调度器实体结构来追踪进程运行记账，该结构为进程描述符（struct task_struct的成员变量）：

vruntime变量存放进程的虚拟运行时间，经过了所有可运行进程总数的标准化（被加权的）。以ns为单位，和定时器节拍不相关。CFS使用vruntime来记录一个程序到底运行了多长时间以及它还应该再运行多久。

update_curr()函数实现了记账功能。是由系统定时器周期性调用的，无论进程处于可运行态，还是不可运行态。因此，vruntime可以准确地测量给定进程的运行时间，而且知道谁是应该被下一个运行的进程。

CFS算法的核心：选择具有最小的vruntime任务。

CFS使用红黑树（rbtree）来组织可运行进程队列，其节点的键值为可运行进程的虚拟运行时间vruntime，有利于迅速找到最小vruntime的进程（可通过__pick_next_entity()函数来访问红黑树最左的叶子即可，当然最左的叶子可能被缓存在rb_left_most字段中，可直接读取）。

另外，可通过enqueue_entity/dequeue_entity函数从红黑树中增加/删除进程。这两个函数都会调用update_curr()函数来更新所处理任务的运行时统计数据。

进程调度的主要入口点是schedule()函数，是内核其他部分用于调用进程调度器的入口：选择哪个进程运行，何时将其投入运行。schedule()函数会通过pick_next_task()函数遍历调度类，找出优先级最高的调度类（struct sched_class），再通过调度类的pick_next_entity()函数（会调用__pick_next_entity()函数）来选择要执行的进程。

休眠（被阻塞）的进程处于不可运行的状态。内核对其 *** 作是：进程把自己标记称休眠状态，从可执行红黑树中删除，放入等待队列，然后调用schedule()选择和执行下一个进程。

唤醒：进程被设置为可执行状态，然后从等待队列中移到可执行红黑树中。

其中，等待队列是由等待某些事件发生的进程组成的简单链表。

上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由context_switch函数处理。

用户抢占：

Linux完整地支持内核抢占，只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。只要没有持有锁，内核就可以进行抢占。内核抢占主要发生在：

普通的、非实时的调度策略是SCHED_NORMAL。

Linux提供两种实时调度策略：

Linux为实时调度策略提供一种软实时工作方式。也就是内核调度进程，尽力使进程在它的限定时间内运行，但内核不保证总能满足这些进程的要求。

对应的，硬实时系统保证在一定条件下，可以满足任何调度的要求。

七、与调度相关的系统调用

其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。

执行低级调度功能的程序称做进程调度程序，由它实现 CPU在进程间的切换。进程调度的运行频率很高，在分时系统中往往几十毫秒就要运行一次。

进程调度是 *** 作系统中最基本的一种调度。在一般类型的 *** 作系统中都必须有进程调度，而且它的策略的优劣直接影响整个系统的计能。

处理机调度是 *** 作系统的主要功能之一，它的实现策略决定了 *** 作系统的类型，其调度算法的优劣直接影响整个系统的性能。处理机调度的任务是选出待分派的作业或进程，为之分配处理机。

扩展资料：

—个进程的上下文(context)包括进程的状态、有关变量和数据结构的值、机器寄存器的值和PCB以及有关程序、数据等。

一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。

当进行上下文切换时点统要首先检查是否允许做上下文切换(在有些情况下，上下文切换是不允许的，例如系统正在执行某个不允许中断的原语时)。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。

在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程、并装配该进程的上下文，使CPU的控制权掌握在被选中进程手中。

---