第四章 进程调度
前言：调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。最大限度地利用处理器时间的原则是,只要有可以执行的进程,那么就总会有进程正在执行。
4.1多任务
1.多任务操作系统就是能同时并发地交互执行多个进程的操作系统。
2.多任务系统可以划分为两类:非抢占式多任务和抢占式多任务。 Linux提供了抢占 式的多任务模式。
3.强制的挂起动作就叫做抢占。进程在被抢占之前能够运行 的时间是预先设置好的,而且有一个专门的名字,叫进程的时间片。时间片实际上就是分配给每个可运行进程的处理器时间段。Linux独一无二 的“公平”调度程度本身并没有采取时间片来达到公平调度。
4.在非抢占式多任务模式下，进程主动挂起自己的操作称为让步。 理想情况下,进程通常做出让步,以便让每个可运行进程享有足够的处理器时间。但这种机制有很多缺点:调度程序无诠对每个进程该执行多长时间做出统一规定,所以进程独占的处理器时间可能超出用户的预料:更糟的是, 一 个决不做出让步的悬挂进程就能使系统崩溃。Unix从一开始就采用的是抢占式的多任务。
4.2 Linux 的进程调度
1.Linux 2.5采用O(1)调度程序的新调度程序，静态时间片算法和针对每一处理器的运行队列,它们帮助我们摆脱了先前调度程序设计上的限制。该调度算提对于调度那些响应时间敏感的程序却有一些先天不足。O(1)调度程序虽然对于大服务器的工作负载很理想,但是在有很多交互程序要运行的桌面 系统上则表现不佳,因为其缺少交互进程。自 2.6内核系统中最为著名的是“反转楼梯最后期限调度算法，吸取了队列理论,将公平调度的概念引入了Linux调度程序，被称为“完全公平调度算法”,或者简称CFS.
4.3 策略
4.3.1 I/O消耗型和处理器消耗型的进程
1.调度器的策略往往决定系统的整体印象。而且负责优化使用处理器时间。
2.进程可以分为两个类型：I/O消耗型和处理器消耗型。前者是指进程的大部分时间用来提交I/O请求或者等待请求，这样的进程经常处于可运行状态，但是时间很短，因为要等待更多I/O请求时，最后会阻塞；后者是指进程把大部分时间用在执行代码上，除非被抢占，否则他们一直在不停的运行，因为没有太多的I/O需求；
3.调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速和最大系统系统利用率。
4.调度算法中一类是基于优先级的调度：调度程序总是选择时间片未用尽而且优先级最高的进程。用户和系统设置进程的优先级来影响系统的调度；Linux两种不同的优先级范围。第一种是nice值，范围从-20到+19,默认值为0；越大的nice值意味着更低的优先级;在Linux中，nice值代表时间片的；第二种是实时优先级，其值是可配置的，默认情况下它的变化范围是从0到99,与nice值不同，越高的实时优先级数值意味着进程优先级越高；
5.时间片是一个数值，它表明进程被抢占前能持续运行的时间；时间片过长会导致系统对交互的响应欠佳，让人觉得系统无法并发执行应用程序；时间片过短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。I/O消耗型号不需要长的时间片，而处理器消耗型的进程则希望越长越好。
4.3.2 进程优先级
1.基于优先级的调度：优先极高的进程先运行；相同优先级的进程按照轮转方式进行调度；优先级分为两类:
nice值（从-20——+19）：默认值为0；数值越大意味着优先级越低；可以通过 ps-el查看系统进程列表并找到NI标记列对应的优先级 实时优先级（从0——99）：越高的实时优先级级数意味着进程优先级越高
4.3.3 时间片
1.时间片表示进程在被抢占之前所能够持续运行的时间；调度策略必须确定一个默认的时间片；Linux的CFS调度器并没有直接划分时间片到进程，而是将处理器的使用比例划分给了进程。也就是说，其抢占时机取决于新的可执行程序消耗了多少处理器使用比，如果消耗的使用比比当前进程小，则新进程立即投入运行抢占当前进程。
4.4 Linux调度算法
4.4.1调度器类
1.Linux调度器是以模块方式提供的（也就是调度器类），目的是允许不同类型的进程可以有针对性地选择调度算法
2.调度器类允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程；
3.调度器代码会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序；
4.4.2 Unix中系统调度问题
1.将nice值映射到时间片的话，就必须将nice值对应到处理器的绝对时间；这样会导致进程切换无法最优进行；
2.如果使用相对nice值，所带来的效果将会极大取决于其nice的初始值；
3.如果执行nice值到时间片的映射，时间片极大受制于定时器。
4.4.3 公平调度
1.CFS基于一个简单的理念：进程调度的效果应当如同系统具备一个理想中的完美任务处理器。CFS的做法如下：
允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程； nice值作为进程获得的处理器运行比的权重（而不是完全由nice决定时间片）； 每个进程都按照其权重在全部的可运行进程中所占的比例对应的“时间片”来运行
2.越高的nice值进程获得越低的处理器使用权重，这是相对默认nice值进程而言的；相反，更反的nice值的进程获得更高的处理器使用权重。
3.CFS为此引入每个进程获得的时间片底线，这个底线称为最小粒度、默认情况下就是1ms。
4.任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的，nice值对时间片的作用不再是算数加权，而是几何加权，任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比；CFS称为公平调度是因为确保给每个进程公平的处理器使用比，CFS不是完美的公平。
4.5 Linux调度的实现
4.5.1 时间记账
所有的调度器都必须对进程的运行时间做记账；CFS使用调度器实体结构来追踪运行记账。
4.5.2虚拟实时
1.vrntime变量【也就是在上面所说的实体结构中】存放虚拟运行时间。虚拟时间以ns为单位，和节拍定时器无关；
2.update_curr()函数实现了记账功能；计算了当前进程的执行时间并将其存放在data_exec中；然后将运行时间传递给了_update_curr()，由后者再根据当前可运行进程总数对运行时间进行计算，最终确定上述的权重值与当前运行进程的vrntime。
4.5.3 进程选择
1.CFS算法核心：选择具有最小vrntime的任务
2.具体做法：利用红黑树rbtree（以节点形式存储数据的二叉树）
4.5.4 进程调度入口
1.进程调度的主要入口点是函数schedule()，定义在kernel/sched.c中；这正是内和其他部分用于调度进程调度器的入口
2.这一函数最重要的工作就是调用pick_next_state()，依次检查每一个调度类，并从最高优先级的调度类中，选择最高优先级进程
4.5.5 睡眠和唤醒
1.进程休眠一定是为了等待一些事件：进程把自己标记成休眠状态，从可执行红黑树中移除；放入等待队列——由等待某些时间发生的进程组成的链表，内核用wake_queue_head_t来代表等待队列。
2.唤醒操作由函数wake_up()进行：它会调用函数try_to _wake_up()将进程设置为TASK_RUNNING状态，调用enqueue_task()将进程放入红黑树中。
4.6 抢占和上下文切换
上下文切换由定义在kernel/sched.c中的context_switch()函数负责，每当一个新的进程被选出来准备运行的时候，schedule()就会调用该函数：调用switch_mm()，负责把虚拟内存从上一个进程映射切换到新的进程中； 调用switch_to()，负责从上一个进程的处理器状态切换到新进程的处理器状态
4.6.1 用户抢占
从系统调用返回用户空间 从中断处理程序返回用户空间
4.6.2 内核抢占
2.内核抢占发生在：
中断处理程序正在执行且返回内核空间之前； 内核代码再一次具有可抢占性的时候； 内核中的任务显式地调用schedule函数
4.7 实时调度策略
1.两种实时调度策略：sched_fifo和sched_RR
2.前者实现了一种简单、先入先出的调度算法：它不使用时间片；而后者尽量事先分配给它的时间后就不能再继续执行了。
4.8 与调度相关的系统调用
4.8.1 与调度策略和优先级相关的系统调用
1.sched_setscheduler()和sched__getscheduler()分别用于设置和获取进程的调度策略和实时优先级。其实最重要的工作在于读取或改写进程 tast_struct的 policy()和rt_priority的值。
2.sched_setparam()和 sched__getparam()分别用于设置和获取进程的实时优先级，封装在sched_param特殊结构体的rt_priority中。 sched_get_priority_max和sched_ get_priority_min()分别用于返回给定调度策略的最大和最小优先级。实时调度策略的最大优先级是MAX_USER_RT_PRIO减1,最小优先级等于1.
3.nice()函数会调用内核的set_user_ nice()函数, 这个函数会设置进程的 task_struct的 static_prio和 prio值。
4.8.2 与处理器绑定有关的系统调用
1.Linux调度程序提供强制的处理器绑定机制。这种强制的亲和性保存在进程task_ struct的cpus_allowed这个位掩码标志中 。该掩码标志的每一位对应一个系统可用的处理器。默认情况下,所有的位都被设置,进程可以在系统中所有可用的处理器上执行。用户可以通过 sched_setaffinity()设置不同的一个或几个位组合的位掩码,而调用scbed_getaffinity()则返回当前的cpus_allowed位掩码。
2.进程只运行在指定处理器上,对处理器的指定是由该进程描述符的 cpus_allowed域设置的。
4.8.3 放弃处理器时间
1.Linux通过 sched_yieldO系统调用,提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。它是通过将进程从活动队列中移到过期队列中实现的。