作用：在可运行态进程之间分配有限的处理器时间资源的内核子系统。
概念： 同时并发地交互执行多个进程的操作系统
分类： ●抢占式多任务： 所有Unix的变体和许多现代操作系统一样，Linux提供了抢占式的多任务模式 抢占：由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行计划，这个强制的挂起动作叫作抢占。 进程在被抢占之前能够运行的时间是预先设置好的，这个事件叫做时间片。（Linux未采用）
●非抢占式多任务： 非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。 让步：进程主动挂起自己的操作称为让步。一个决不做出让步的悬挂进程就能使系统崩溃。
相当简陋，难以胜任
对于大服务器的工作负载很理想，但是在很多交互程序要运行的桌面系统则表现不佳，因为其缺少交互进程。
策略决定调度程序何时让什么进程运行
I/O消耗型进程通常运行一小会，然后阻塞在等待I/O请求，多数GUI都属于I/O密集型。
Linux为了保证交互式应用和桌面系统的性能，更倾向于优先调度I/O消耗型进程。
两种不同的优先级范围： ●nice值： 默认为0，越大的nice值意味着更低的优先级
●实时优先级： 越高的实时优先级数值意味着进程优先级越高。
概念：时间片是一个数值，表明进程在被抢占前所能持续运行的时间。
长短：过长会导致系统对交互响应迟钝，过短会增大进程切换带来的处理器耗时
作用：多数操作系统中，是否要将一个进程立刻投入运行（抢占当前进程），是完全由进程优先级和是否有时间片决定的。
理想的调度器： 假如文本编辑器和视频编码器进程同时运行，有两个目标： 1.文本编辑程序获得更多的处理器时间，因为它属于交互式应用，在需要时应该确保它得到处理器时间。 2.文本编辑器能在被唤醒时抢占视频解码程序
概念 CFS完全摒弃时间片而是分配给进程一个处理器使用比重。通过这种方式，CFS确保了进程调度中能有恒定的公平性。
做法 CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不采用时间片的做法。 最小粒度 当可运行任务数量趋于无限时，各自获得的处理器使用比趋于0，会造成不可接受的切换消耗。CFS为此引入了每个进程获得的时间片底线，默认为1ms。
完全公平？ CFS不是完美的公平，只是近乎完美的多任务。但是确实在多进程环境下降低了调度延迟带来的不公平性。
四个组成部分： 1.时间记账 2.进程选择 3.调度器入口 4.睡眠和唤醒
调度器实体结构 名为se的成员变量，嵌入在进程描述符struct task_struct内。进程描述符见第三章
虚拟运行时间 vruntime变量存放进程的虚拟运行时间（加权后的）。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。
进程选择 CFS会挑一个具有最小vruntime的进程来运行，这是CFS调度算法的核心。 CFS使用红黑树来组织可运行进程队列。
●挑选下一个任务：利用红黑树迅速找到vruntime值最小的进程 ●向树中加入进程：在进程变为可运行状态（被唤醒）或者是通过fork()调用第一次创建进程，CFS将进程加入rbtree。 ●从树中删除进程：删除动作发生在进程堵塞（不可运行态）或终止时（结束运行）
进程调度的主要入口点是函数schedule()，schedule()通常要和一个具体的调度类相关联。
该函数中唯一重要的事情是调用pick_next_task()。pick_next_task()会以优先级为序，从高到低依次检查每一个调度类，并从最高优先级的调度类中选择最高优先级的进程。
休眠： 进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列。
休眠的两种状态 ●TASK_INTERRUPTIBLE：接收到信号会被提前唤醒并响应该信号 ●TASK_UNINTERRUPTIBLE：忽略信号
等待队列： 休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。
过程：代码见书4.5.4 进程把自己放入等待队列中并设置成不可执行状态。当与等待队列相关的事件发生后，队列上的进程会被唤醒。还要注意避免产生竞争条件。
唤醒： 函数wake_up()唤醒指定的等待队列上的所有进程 虚假唤醒： 一种可能性是条件变量的等待被信号中断 另一种可能性是唤醒后被另一个进程抢先了。
上下文切换 从一个可执行进程切换到另一个可执行进程。
有两项基本工作： ●调用switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中 ●调用switch_to()，从上一个进程的处理器状态切换到新进程的处理器状态。包括保存、恢复栈信息和寄存器信息等。
内核调用schedule() 原因：不能只靠用户程序代码显示调用schedule()，可能会永远执行下去。
标志：need_resched表明是否需要重新执行一次调度。通过检查该标志来判断是否调用schedule()
发生情况 ●从系统调用返回用户空间时 ●从中断处理程序返回用户空间时
如何抢占 返回的时候查看need_resched标志，来判断是否调用schedule()
Linux的特点 支持内核抢占，其他大部分Unix变体和大部分操作系统不支持内核抢占，内核代码可以一直执行到完成。
调度的安全性 只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。 只要没有持有锁，内核就可以进行抢占。
发生情况 ●中断处理程序正在执行，且返回内核空间之前。 ●内核代码再一次具有可抢占性的时候 ●内核中的任务显式调用schedule() ●内核中的任务阻塞
静态优先级 两种实时算法都是静态优先级，不实时计算动态优先级。保证给定优先级别的实时进程总能抢占优先级比它低的进程。
两种策略具体见书 ●SCHED_FIFO：简单、先入先出，不基于时间片，可以一直执行下去，只有更高优先级的任务才能抢占 ●SCHED_RR：带有时间片的SCHED_FIFO
软实时工作方式 内核调度进程，尽力使进程在它的限定时间来前运行，但内核不保证总能满足这些进程的要求。但是Linux的实时调度算法的性能还是不错的
作用： sched_yield()系统调用，让进程显式地将处理器时间让给其他进程。
原理： 将进程从活动队列中移到过期队列中，确保在一段时间内它都不会再执行。
