《Linux内核设计与实现》第四章学习笔记
——进程调度
姓名：王玮怡 学号：20135116
一、多任务
1、多任务操作系统的含义
多任务操作系统就是能同时并发地交互执行多个进程的操作系统。
- 无论在单处理器或者多处理器机器上，多任务操作系统都能使多个进程处于堵塞或者睡眠状态，也就是说，实际上不被投入执行，直到工作确实就绪。
- 相反，这些进程利用内核阻塞自己，直到某一事件（键盘输入、网络数据、过一段时间等）发生。
2、多任务操作系统的分类
- 非抢占式多任务
- 抢占式多任务
3、Linux的抢占式多任务模式
（1）抢占：强制的挂起动作
（2）时间片：分配给每个可运行进程的处理器时间段。有效管理时间片能使调度程序从系统全局的角度做出调度决定，这样做还可以避免个别进程独占系统资源。
（3）让步：进程主动挂起自己的操作
二、Linux的进程调度
1、O（1）调度程序
缺点：缺少交互进程
2、反转楼梯最后期限调度算法
优点：吸收了队列理论，引入公平调度的概念，“完全公平调度算法”
三、策略
1、I/O消耗型和处理器消耗型的进程
（1）I/O消耗型
- 指进程的大部分时间用来提交I/O请求或是等待I/O请求。因此，这样的进程经常处于可运行状态，但通常都是运行短短的一会儿。
- 举例：多数用户图形界面程序（GUI)、Unix系统、Linux
（2）处理器消耗型
- 处理器耗费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的1/0 需求。
- 举例：无限循环执行，如sshkeygen 或者MATLAB
（3）特殊情况
- X Window 服务器既是I/O消耗型，也是处理器消耗型
- 平衡点：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。
2、进程优先级
- 调度算法中最基本的一类就是基于优先级的调度，这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。
- 通常做法是是（其并未被Linux 系统完全采用）优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。
（1）使用nice值的优先级
- 范围是从－20 到＋19，默认值为0 ：越大的nice 值意味着更低的优先级
- Linux 系统中，nice值则代表时间片的比例
（2）实时优先级
- 其值是可配置的，默认情况下它的变化范围是从0到99（包括0和99）
- 越高的实时优先级数值意味着进程优先级越高
3、时间片
（1）时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。
（2）在Linux操作系统中
- Linux 的CFS 调度器并没有直接分配时间片到进程，它是将处理器的使用比划分给了进程。
- 在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比．如果消耗的使用比比当前进程小，则新进程立刻投入运行，抢占当前进程。否则，将推迟其运行。
四、Linux调度算法——完全公平调度（CFS）
1、相关概念
- 目标延迟：每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行，为了计算准确的时间片，CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标称作“目标延迟”，越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。
- 最小粒度：当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间片都将趋于0，造成了不可接受的切换消耗，CFS 为此引人每个进程获得的时间片底线，这个底线称为最小粒度。默认情况下这个值是lms。
2、决定因素
任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。
3、所属类型
针对普通进程的调度器类——允许多重不同的可动态添加的调度算法并存，调度属于自己范畴的进程
4、组成部分
- 时间记账
- 进程选择
- 调度器入口
- 睡眠和唤醒
五、Linux调度的实现
1、时间记账
一个进程的时间片被减少到0时，它就会被另一个尚未减到0的时间片可运行进程抢占。
- CFS使用调度器实体结构来追踪进程运行记账（定义在文件＜linux/sched.h＞的struct_sched _entity）
- CFS使用vruntime变量（虚拟实时）来记录一个程序到底运行了多长时间以及它还应该再运行多久，而且可以知道谁应该是下一个被运行的进程，以ns为单位
2、进程选择
红黑树是一种以树节点形式存储的数据，这些数据都会对应一个键值。Linux中，红黑树称为rb位时，它是一个自平衡二叉搜索树。
- 挑选下一个任务：CFS调度器选取所有进程中vruntime最小的那个进程为待运行的下一个进程（CFS调度算法的核心），对应的是树中最左侧的叶子节点，实现函数为__pick_next_entity()
- 向树中加入进程，发生在进程变为可运行状态（被唤醒）或通过fork()调用第一次创建进程时，由函数enqueue_entity()实现
- 从树中删除进程的动作发生在进程堵塞（变为不可运行态）或者终止时（结束运行），有辅助函数__dequeue_entity()完成
3、调度器入口
进程调度的主要入口点是函数schedule()，该函数中唯一重要的事就是调用pick_next_task()
4、睡眠和唤醒
（1）睡眠（被阻塞）——进程处于一个特殊的不可执行状态
- 常见原因：文件I/O
- 内核操作：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule()选择和执行一个其他进程。
- 等待队列：由等待某些事件发生的进程组成的简单链表，内核用wake_queue_ head _t 来代表等待队列。可通过DECL成立WAITQUEUE ()静态创建，也可以由init_waitqueue _head()动态创建
（2）唤醒——唤醒指定的等待队列上的所有进程
- 唤醒操作通过函数wake_up()进行，它调用函数try_to_wake_up()，该函数负责将进程设置为TASK_RUNNING状态，调用enqueue_task（）将此进程放入红黑树中
- 如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置need _resched 标志
- 注意虚假唤醒
六、抢占和上下文切换
1、抢占
（1）用户抢占
内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时会发生用户抢占
- 从系统调用返回用户空间时
- 从中断处理程序返回用户空间时
（2）内核抢占
每个进程的thread_info引人preempt_count计数器。该计数器韧始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占，具体发生在：
- 中断处理程序正在执行，且返回内核空间之前
- 内核代码再一次具有抢占性的时候
- 如果内核中的任务显式地调用schedule()
- 如果内核中的任务阻塞
2、上下文切换
- 一个可执行进程切换到另一个可执行进程
- 当一个新进程被选出来准备投入运行时，schedule()会调用context_switch()函数负责处理
七、实时调度策略
1、SCHED_FIFO
- 简单、先入先出
- 不使用时间片
- 如果SCHED_FIFO级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止
2、SCHED_RR
- 实时轮流调度算法：带有时间片的SCHED_FIFO
- 当SCHED_RR任务耗尽它的时间片时，同一优先级的其他实时进程被轮流调度
3、实时优先级范围默认为0-99
八、与调度有关的系统调用
1、与调度策略和优先级相关的系统调用
sched_setscheduler()和sched_getscheduler()分别用于设置和获取今后才能的调度策略和实时优先级。
2、与处理器绑定有关的系统调用
用户可以通过sched_setaffinity()设置不同的一个或几个位组合的位掩码，而调用sched_getaffinity()则返回房钱的cpus_allowed掩码。
3、放弃处理器时间
Linux通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。