20135202闫佳歆--week 8 课本第4章学习笔记

第四章 进程调度

一、多任务

多任务操作系统就是能同时并发的交互执行多个进程的操作系统。
多任务操作系统使多个进程处于堵塞或者睡眠状态，实际不被投入执行，这些任务尽管位于内存，但是并不处于可运行状态。
多任务系统分类：

• 非抢占式多任务
• 抢占式多任务

1.抢占式多任务

Linux提供了抢占式的多任务模式，由调度程序来决定什么时候停止一个进程的运行。
几个相关概念：

• 抢占：强制的挂起动作
• 时间片：预先设置好的，进程被抢占之前能够运行的时间，实际上就是分配给每个可运行进程的处理器时间段
• 动态时间片计算的方式
• 可配置的计算策略

2.非抢占式多任务

除非进程自己主动停止运行，否则会一直执行。

• 让步：进程主动挂起自己的操作。
  缺点：调度程序无法躲每个进程该执行多长时间作出统一规定，所以进程独占的处理器时间可能会超过用户的预料

Unix从一开始就采用的是抢占式的多任务。

二、Linux的进程调度

1.O(1)调度器

对大服务器的工作负载很理想；
但是缺少交互进程。

2.RSDL与CFS

RSDL，反转楼梯最后期限调度算法，吸取了队列理论，公平调度。
又被称为CFS，完美公平调度算法。

三、策略

策略决定调度程序在合适让什么程序运行。

1.进程分类

• I/O消耗性进程
  进程的大部分时间用来提交I/O请求或者等待I/O请求，经常处于可运行状态但是运行时间很短，等待更多的请求时最后总会阻塞。
• 处理器耗费型进程
  把时间大多用在执行代码上，除非被抢占，否则通常都会不停运行。
  调度策略：尽量降低它们的调度频率，延长其运行时间。

调度策略通常要在两个矛盾的目标中间寻找平衡：

• 进程调度迅速（响应时间短）
• 最大系统利用率（高吞吐量）

Linux倾向于优先调度I/O消耗型进程

2.进程优先级

调度算法中最基本的一类就是基于优先级的调度——根据进程的价值和其对处理器时间的需求来对进程分级。
调度程序总是选择时间片未用尽而且优先级最高的进程运行。

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

1. nice
   范围[-20,19]，默认值为0；
   nice值越大，优先级越低；
   Linux系统中nice值代表时间片的比例；
   ps-el命令查看系统中进程列表，NI列为nice值。

2. 实时优先级
   值可以配置，默认变化范围是[0,99]；
   值越高优先级越高；
   任何实时进程的优先级都高于普通的进程。

——实时优先级和nice优先级处于互不相交的两个范畴。

ps-eo state,uid,pid,ppid,rtprio,time,comm.
查看系统中的进程列表以及对应的实时优先级（rtprio）
显示“-”表示不是实时进程

3.时间片

时间片表示进程在被抢占前所能持续运行的时间。

- I/O消耗型进程不需要很长的时间片
- 处理器消耗型进程希望时间片越长越好

Linux的CFS调度器没有直接分配时间片到进程，而是将处理器的使用比划分给进程——

1. 进程所获得的处理器时间和系统负载密切相关。

2. 这个比例受nice值影响，nice值作为权重来调整进程所使用的处理器时间使用比：

    高nice值—低优先权—低权重—损失小部分处理器使用比
    低nice值—高优先权—高权重抢得更多处理器使用比
   

Linux进程是抢占式的，是否抢占完全由进程的优先级和是否有时间片来决定。
CFS抢占器：抢占时机取决于新的可执行程序消耗了多少处理器使用比，如果消耗的使用比当前进程小：新程序立刻投入运行，抢占当前进程，否则推迟。

四.Linux调度算法

1.调度器类

Linux调度器是以模块方式提供，以便于允许不同类型的进程可以有针对性地选择调度算法。

• 调度器类：
  允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。

基础的调度器代码定义在kernel/sched.c文件中。
每个调度器有一个优先级，会按照优先级顺序遍历调度类，选择优先级最高的调度器类。

之前提过的完全公平调度CFS是一个针对普通进程【区别于实时进程】的调度类。

2.Unix系统中的进程调度

Unix使用的调度算法是分配绝对的时间片，这样就会引发固定的切换频率，不利于公平性。
而Linux采用的CFS完全摒弃了时间片，分配给进程一个处理器使用比重，保证恒定的公平性和变动的切换频率。

3.公平调度CFS

CFS是近乎完美的多任务。

1. 允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程
2. 在所有可运行进程总数基础上计算出一个进程应该运行多久
3. nice值作为进程获得的处理器运行比的权重
   即：绝对的nice值不再影响调度决策，它们的相对值才会影响处理器时间的分配比例——几何加权。
4. 目标延迟：无限小调度周期的近似值
5. 最小粒度：每个进程获得的时间片底线，默认为1ms。
6. 没有时间片概念但是仍需维持时间记账。

任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。

五、Linux调度的实现

——即CFS调度算法的实现。
四个组成部分：

• 时间记账
• 进程选择
• 调度器入口
• 睡眠和唤醒

1.时间记账

所有的调度器都必须对进程运行时间做记账。

（1）调度器实体结构

CFS使用调度器实体结构来追踪进程运行记账：

是进程描述符中的se变量。

（2）虚拟实时

CFS使用了vruntime变量来存放进程的虚拟运行时间，用来表示进程到底运行了多少时间，以及它还应该运行多久。

1. 这个虚拟运行时间是加权的，与定时器节拍无关。
2. 虚拟运行时间以ns为单位。

相关的函数是update_curr()，它计算了当前进程的执行时间并存放入变量delta_exec中，然后又将运行时间传递给__update_curr()；
__update_curr()根据当前可运行进程总数对进行时间进行加权计算，最终将权重值与当前运行进程的vruntime值相加。

undate_curr()是由系统定时器周期调用的。

2.进程选择

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

CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。

Linux中，红黑树被称为rbtree，是一个自平衡二叉搜索树，是一种以树节点形式存储的数据，这些数据会对应一个键值，可以通过这些键值来快速检索节点上的数据，而且检索速度与整个树的节点规模成指数比关系。

（1） 挑选下一个任务

节点键值是可运行进程的虚拟运行时间，进程选择算法是【运行rbtree树种最左边叶子节点所代表的那个进程】，函数是__pick_next_entity()

这个函数本身不会遍历树找到最左叶子节点，该值缓存在rb_leftmost字段中，函数返回值就是CFS选择的下一个运行进程。
如果返回NULL，表示树空，没有可运行进程，这时选择idle任务运行。

（2） 向树中加入进程

发生在进程被唤醒或者通过fork调用第一次创建进程时。

函数enqueue_entity()：更新运行时间和其他一些统计数据，然后调用__enqueue_entity()。

函数__enqueue_entity()：进行繁重的插入工作，把数据项真正插入到红黑树中：

原理：

1. 设置leftmost标志位，一旦为0则表示走过右边分支，放弃；
如果始终是1，新进程就是最左节点，可以更新缓存，设置rb_leftmost指向被插入的进程。
2. link为null时循环终止，退出。
3. 在父节点上调用rb_link_node()，使新插入的进程成为其子节点。
4. 函数rb_insert_color()更新树的自平衡相关特性。

（3） 从树中删除进程

删除动作发生在进程堵塞或终止时。

相关函数是dequeue_entity()和__dequeue_entity()：

原理：

1. rb_erase()函数删除进程
2. 更新rb_leftmost缓存
3. 如果删除的是最左节点，还要调用rb_next()按顺序遍历，找到新的最左节点。

3.调度器入口

进程调度的主要入口点函数是schedule()。

1. schedule()函数会调用pick_next_task()；
2. pick_next_task()会以优先级为序，从高到低依次检查每一个调度类，并且从最高优先级的调度类中选择最高优先级的进程。
3. pick_next_task()会返回指向下一个可运行进程的指针，没有时返回NULL
4. pick_next_task()函数实现会调用pick_next_entity()
5. pick_next_entity()会调用__pick_next_entity()。

4.睡眠和唤醒

睡眠时内核动作：
进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待序列，然后调用schedule()选择和执行一个其他进程

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

两种休眠相关进程状态：
TASK_INTERRUPTIBLE
TASK_UNINTERRUPTIBLE

(1)等待队列

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

休眠通过等待队列进行处理。

内核用wake_queue_head_t来表示等待队列。

等待队列可以通过DECLARE_WAITQUEUE()静态创建
也可以由init_waitqueue_head()动态创建

在内核中进行休眠的推荐操作：

进程通过执行以下几个步骤将自己加入到一个等待队列中：

1. 调用宏DEFINE_WAIT()创建一个等待队列的选项。
2. 调用add_wait_queue()把自己加入到队列中。
3. 调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。
4. 如果状态被设置成TASK_INTERRUPTIBLE，则信号唤醒进程。【伪唤醒，唤醒不是因为事件的发生。】
5. 当进程被唤醒的时候，会再次检查条件是否为真，真则退出循环，否则再次调用schedule()并且一直重复这步动作。
6. 当条件满足后，进程将自己设置为TASK_RUNNING并调用finish_wait()方法把自己移出等待序列。

函数inotify_read()：负责从通知文件描述符中读取信息。

（2）唤醒

唤醒操作通过函数wake_up()进行，会唤醒指定的等待队列上的所有进程。

1. wake_up()函数调用try_to_wake_up()
2. try_to_wake_up()函数负责将进程设置成TASK_RUNNING状态
3. 调用enqueue_task()将此进程放入红黑树中
4. 如果被唤醒的进程优先级比正在执行的进程优先级高，设置need_resched标志
5. 通常哪段代码促成等待条件达成，它就负责随后调用wake_up()函数。

虚假唤醒：
有时候进程被唤醒并不是因为它所等待的条件达成了，所以才需要用一个循环处理来保证它等待的条件真正达成。

六、抢占和上下文切换

上下文切换由context_switch()函数负责。
每当一个新进程被选出准备投入运行时，schedule()会调用context_switch()。
context_switch()完成了两项基本工作：

• 调用switch_mm()，该函数负责把虚拟内存从上一个进程映射到新进程中
• 调用switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。
  这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。

need_resched标志：
内核用这个标志来表明是否需要重新执行一次调度。

1. 当某个进程应该被抢占时，scheduler_tick()会设置这个标志。
2. 当一个优先级高的进程进入可执行状态时，try_to_wake_up()会设置这个标志。
3. 内核检查这个标志确认其被设置，调用schedule()来切换到一个新的进程。
4. 该标志对于内核来说是一个信息，表示youqitajinc应当被运行了，要尽快调用调度程序。
5. 再返回用户空间以及从中断返回时，内核也会检查标志。
6. 每个进程都包含一个need_resched标志，因为访问进程描述符里的数值比访问一个全局变量要快。

1.用户抢占

内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时会发生用户抢占。

用户抢占发生的情况：

• 从系统调用返回用户空间时
• 从中断处理程序返回用户空间时

entry.S：包含内核入口部分和退出部分的相关代码。

2.内核抢占

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

判断调度——锁。
锁是非抢占区域的标志。

实现：
为每个进程的thread_info中加入preempt_count计数器，初值为0，使用锁+1，释放锁-1，数值为0时，可以执行抢占。

1. 从中断返回内核空间时，先检查need_resched标志，如果被设置表示需要被调度，然后检查preempt_count计数器，如果为0，表示可以被抢占，这时调用调度程序。
   否则，内核直接从中断返回当前执行进程。
2. 当前进程持有的锁全部被释放，这时preempt_count归0，释放锁的代码会检查need_resched是否被设置，如果是就调用调度程序。
3. 如果内核中的进程被阻塞了，或者显式地调用了schedule()，内核抢占也会显式地发生。

※内核抢占会发生在:

• 中断处理程序正在执行，且返回用户空间之前
• 内核代码再一次具有可抢占性的时候
• 内核中的任务显式地调用schedule()
• 内核中的任务阻塞（同样导致调用schedule()）

七、实时调度策略

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

1.两种实时调度策略：

• SCHED_FIFO
  简单的先入先出算法，不使用时间片
  • 可运行的SCHED_FIFO比任何SCHED_NORMAL进程更先得到调度
  • 只有更高优先级的FIFO或者RR才能抢占它
  • 同等优先级的FIFO轮流执行，只有它愿意让出时才会退出
• SCHED_RR
  SCHED_RR是带有时间片的FIFO。
  • 这是一种实施轮流调度算法。
  • 当RR耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度
  • 时间片只用来重新调度同一优先级进程。

总而言之，高优先级总是立即抢占低优先级，而低优先级决不能抢占高优先级。

这两种实时算法实现的都是静态优先级：
内核部位实施进程计算动态优先级，这能保证给定优先级别的实时进程总是能抢占优先级比它低的进程。

软实时：内核调度进程，尽力使进程在它的限定时间到来前进行，但内核不保证总能满足这些进程的要求。
硬实时：系统保证在一定条件下，可以满足任何调度的要求。

2.优先级范围

• 实时：
  0~[MAX_RT_PRIO-1]
  默认MAX_RT_PRIO=100，所以默认实时优先级范围为[0,99]

• SCHED_NORMAL:
  [MAX_RT_PRIO]~[MAX_RT_PRIO+40]
  默认情况下，nice值从-20到+19对应的是从100到139的实时优先级范围。

八、与调度相关的系统应用

1.与调度策略和优先级相关的系统调用

nice()  将给定进程的静态优先级增加一个给定的量，只有超级用户才能在调用它时使用负值来提高进程的优先级
getpriority()/setpriority() 设置优先级
sched_getscheduler()/sched_setscheduler() 设置和获取进程的调度策略和实时优先级
sched_getparam()/sched_setparam()   设置和获取进程的实时优先级
sched_get_priority_min()/sched_get_priority_max()   返回给定调度策略的最大和最小优先级

2.与处理器绑定有关的系统调用

Linux调度程序提供强制的处理器绑定机制
task_struct中的cpus_allowed位掩码中

sched_setaffinity() 设置不同的一个或者几个位组合的位掩码
sched_getaffinity() 返回当前的cpus_allowed位掩码

3.放弃处理器时间

sched_yield()   让进程显式地将处理器时间让给其他等待执行进程

普通进程移到过期队列中，实时进程移到优先级队列最后。

内核先调用yield，确定给定进程确实处于可执行状态，然后调用sched_yield()。
用户空间可以直接调用sched_yield()。