第四章 进程调度

一、多任务

多任务操作系统就是能同时并发的交互执行多个进程的操作系统。

多任务操作系统使多个进程处于堵塞或者睡眠状态,实际不被投入执行,这些任务尽管位于内存,但是并不处于可运行状态。

多任务系统分类:

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

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.调度器类

  • 调度器类:

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

基础的调度器代码定义在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使用调度器实体结构来追踪进程运行记账:

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

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

(2)虚拟实时

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

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

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

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

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

相关的函数是update_curr(),它计算了当前进程的执行时间并存放入变量delta_exec中,然后又将运行时间传递给__update_curr();

__update_curr()根据当前可运行进程总数对进行时间进行加权计算,最终将权重值与当前运行进程的vruntime值相加。

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

2.进程选择

CFS调度算法的核心:

选择具有最小vruntime的任务。

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

(1) 挑选下一个任务

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

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

这个函数本身不会遍历树找到最左叶子节点,该值缓存在rb_leftmost字段中,函数返回值就是CFS选择的下一个运行进程。

如果返回NULL,表示树空,没有可运行进程,这时选择idle任务运行。

(2) 向树中加入进程

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

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

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

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

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

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

原理:

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

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

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

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

原理:

  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()。

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

4.睡眠和唤醒

睡眠时内核动作:

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

唤醒时内核动作:

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

两种休眠相关进程状态:

TASK_INTERRUPTIBLE

TASK_UNINTERRUPTIBLE

(1)等待队列

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

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

等待队列可以通过DECLARE_WAITQUEUE()静态创建

也可以由init_waitqueue_head()动态创建

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

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

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

  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()函数。

虚假唤醒:

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

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

六、抢占和上下文切换

上下文切换由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标志,因为访问进程描述符里的数值比访问一个全局变量要快。

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

1.用户抢占

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

用户抢占发生的情况:

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

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的实时优先级范围。

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

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

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()。

04-15 03:08