当前位置 博文首页 > 司夏的博客：操作系统 - 处理机调度

最大化 缩小

    司夏的博客：操作系统 - 处理机调度

    作者：[db:作者] 时间：2021-08-06 21:55

    CPU资源的时分复用

    进程切换：CPU资源的当前占用者切换

    • 保存当前进程在PCB中的执行上下文(CPU状态)
    • 恢复下一个进程的执行上下文

    处理机调度

    • 从就绪队列中挑选下一个占用CPU运行的进程
    • 从多个可用CPU中挑选就绪进程可使用的CPU资源

    调度程序：挑选就绪进程的内核函数

    • 调度策略，依据什么原则挑选进程/线程？
    • 调度时机，什么时候进行调度？

    调度时机：在进程/线程的生命周期中的什么时候进行调度？

    内核运行调度程序的条件

    • 进程从运行状态切换到等待状态
    • 进程被终结了

    非抢占系统

    • 当前进程主动放弃CPU时

    可抢占系统

    • 中断请求被服务例程响应完成时
    • 当前进程被抢占，进程时间片用完，进程从等待切换到就绪

    在这里插入图片描述

    调度策略

    调度策略：确定如何从就绪队列中选择下一个执行进程

    调度策略要解决的问题

    • 挑选就绪队列中的哪一个进程？
    • 通过什么样的准则来选择？

    调度算法：在调度程序中实现的调度策略

    比较调度算法的准则：哪一个策略/算法较好?

    处理机资源的使用模式

    进程在CPU计算和I/O操作间交替

    • 每次调度决定在下一个CPU计算时将哪个工作交给CPU
    • 在时间片机制下，进程可能在结束当前CPU计算前被迫放弃CPU

    在这里插入图片描述

    比较调度算法的准则

    CPU使用率：CPU处于忙状态的时间百分比

    吞吐量：单位时间内完成的进程数量

    周转时间：进程从初始化到结束(包括等待)的总时间

    等待时间：进程在就绪队列中的总时间

    响应时间：从提交请求到产生响应所花费的总时间

    吞吐量与延迟

    调度算法的要求

    • 希望“更快”的服务

    什么是更快？

    传输文件时的高带宽，调度算法的高吞吐量。玩游戏时的低延迟，调度算法的低响应延迟。这两个因素是独立的。与水管的类比。
    低延迟：喝水的时候想要一打开水龙头水就流出来。
    高带宽：给游泳池充水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟。

    处理机调度策略的响应时间目标

    减少响应时间。及时处理用户的输入请求，尽快将输出反馈给用户

    减少平均响应时间的波动。在交互系统中，可预测性比高差异低平均更重要

    低延迟调度改善了用户的交互体验。如果移动鼠标时，屏幕中的光标没动，用户可能会重启电脑

    响应时间是操作系统的计算延迟。

    处理机调度策略的吞吐量目标

    增加吞吐量

    • 减少开销（操作系统开销，上下文切换）
    • 系统资源的高效利用（CPU，I/O设备）

    减少等待时间。减少每个进程的等待时间

    操作系统需要保证吞吐量不受用户交互的影响。操作系统必须不时进行调度，即使存在许多交互任务

    吞吐量是操作系统的计算带宽

    处理机调度的公平性目标

    公平的定义：

    • 保证每个进程占用相同的CPU时间
    • 保证每个进程的等待时间相同

    公平通常会增加平均响应时间

    调度算法

    1、先来先服务算法(First Come First Served, FCFS)

    依据进程进入就绪状态的先后顺序排列

    进程进入等待或结束状态时，就绪队列中的下一个进程占用CPU

    FCFS算法的周转时间，示例：3个进程，计算时间分别为12,3,3
    在这里插入图片描述
    先来先服务算法的特征

    优点：简单

    缺点：

    • 平均等待时间波动较大，短进程可能排在长进程后面。
    • I/O资源和CPU资源的利用率较低，CPU密集型进程会导致I/O设备闲置时，I/O密集型进程也等待。

    2、短进程优先算法（SPN: Shortest Process Next）

    选择就绪队列中执行时间最短进程占用CPU进入运行状态，就绪队列按预期的执行时间来排序

    短进程优先算法的特征：缺点

    可能导致饥饿，连续的短进程流会使长进程无法获得CPU资源

    需要预知未来：
    如何预估下一个CPU计算的持续时间？
    简单的解决办法：询问用户，用户不知道怎么办？

    3、最高响应比优先算法（HRRN: Highest Response Ratio Next）

    选择就绪队列中响应比R值最高的进程

    Ｒ＝（ｗ+s)/s   
        w: 等待时间(waiting time)
         s: 执行时间(service time)

    在短进程优先算法的基础上改进
    不可抢占
    关注进程的等待时间
    防止无限期推迟

    4、时间片轮转算法（RR: Round Robin）

    时间片：分配处理机资源的基本时间单元

    算法思路：

    • 时间片结束时，按FCFS算法切换到下一个就绪进程
    • 每隔(n – 1)个时间片进程执行一个时间片q

    时间片为20的RR算法示例
    在这里插入图片描述

    时间片轮转算法中的时间片长度

    RR算法开销（额外的上下文切换）

    时间片太大（等待时间过长，极限情况退化成FCFS）

    时间片太小（反应迅速，但产生大量上下文切换，大量上下文切换开销影响到系统吞吐量）

    时间片长度选择目标

    • 选择一个合适的时间片长度
    • 经验规则：维持上下文切换开销处于1%以内

    5、多级反馈队列算法（MFQ: Multilevel Feedback Queues）

    就绪队列被划分成多个独立的子队列，如：前台（交互）、后台（批处理）

    每个队列拥有自己的调度策略，如：前台-RR、后台-FCFS

    队列间的调度

    • 固定优先级
      先处理前台，然后处理后台
      可能导致饥饿
    • 时间片轮转
      每个队列都得到一个确定的能够调度其进程的CPU总时间
      如：80%CPU时间用于前台，20%CPU时间用于后台

    进程可在不同队列间移动的多级队列算法

    • 时间片大小随优先级级别增加而增加
    • 如进程在当前的时间片没有完成，则降到下ー个优先级

    MLFQ算法的特征

    • CPU密集型进程的优先级下降很快
    • I/O集型进程停留在高优先级

    在这里插入图片描述

    6、公平共享调度算法（FSS: Fair Share Scheduling）

    FSS控制用户对系统资源的访问

    • 一些用户组比其他用户组更重要
    • 保证不重要的组无法垄断资源
    • 未使用的资源按比例分配
    • 没有达到资源使用率目标的组获得更高的优先级

    传统调度算法总结

    先来先服务算法

    • 不公平，平均等待时间较差

    短进程优先算法

    • 不公平，平均周转时间最小
    • 需要精确预测计算时间
    • 可能导致饥饿

    最高响应比优先算法

    • 基于SPN调度
    • 不可抢占

    时间片轮转算法

    • 公平，但是平均等待时间较差

    多级反馈队列

    • 多种算法的集成

    公平共享调度

    • 公平是第一要素

    实时操作系统

    实时操作系统的定义：正确性依赖于其时间和功能两方面的操作系统

    实时操作系统的性能指标

    • 时间约束的及时性（deadlines）
    • 速度和平均性能相对不重要

    实时操作系统的特性：时间约束的可预测性

    实时操作系统分类

    强实时操作系统：要求在指定的时间内必须完成重要的任务

    弱实时操作系统：重要进程有高优先级，要求尽量但非必须完成

    实时任务

    任务（工作单元）：一次计算，一次文件读取，一次信息传递等等

    任务属性：完成任务所需要的资源，定时参数

    在这里插入图片描述

    周期实时任务

    周期实时任务：一系列相似的任务

    • 任务有规律地重复
    • 周期p = 任务请求时间间隔 (0 <p)
    • 执行时间e = 最大执行时间(0 < e < p)
    • 使用率U = e/p

    软时限和硬时限

    硬时限（Hard deadline）

    • 错过任务时限会导致灾难性或非常严重的后果
    • 必须验证，在最坏情况下能够满足时限

    软时限(Soft deadline)

    • 通常能满足任务时限，如有时不能满足，则降低要求
    • 尽力保证满足任务时限

    可调度性

    可调度表示一个实时操作系统能够满足任务时限要求

    • 需要确定实时任务的执行顺序
    • 静态优先级调度
    • 动态优先级调度

    实时调度

    速率单调调度算法(RM, Rate Monotonic)

    • 通过周期安排优先级
    • 周期越短优先级越高
    • 执行周期最短的任务

    最早截止时间优先算法 (EDF, Earliest Deadline First)

    • 截止时间越早优先级越高
    • 执行截止时间最早的任务

    多处理器调度

    多处理机调度的特征

    • 多个处理机组成一个多处理机系统
    • 处理机间可负载共享

    对称多处理器(SMP, Symmetric multiprocessing)调度

    • 每个处理器运行自己的调度程序
    • 调度程序对共享资源的访问需要进行同步

    在这里插入图片描述

    对称多处理器的进程分配

    静态进程分配

    • 进程从开始到结束都被分配到一个固定的处理机上执行
    • 每个处理机有自己的就绪队列
    • 调度开销小
    • 各处理机可能忙闲不均

    动态进程分配

    • 进程在执行中可分配到任意空闲处理机执行
    • 所有处理机共享一个公共的就绪队列
    • 调度开销大
    • 各处理机的负载是均衡的

    优先级反置(Priority Inversion)

    操作系统中出现高优先级进程长时间等待低优先级进程所占用资源的现象。

    基于优先级的可抢占调度算法存在优先级反置
    在这里插入图片描述

    优先级继承（Priority Inheritance）

    占用资源的低优先级进程继承申请资源的高优先级进程的优先级
    只在占有资源的低优先级进程被阻塞时,才提高占有资源进程的优先级
    在这里插入图片描述

    优先级天花板协议（priority ceiling protocol）

    占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同

    • 不管是否发生等待,都提升占用资源进程的优先级
    • 优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞
    cs
    上一篇：司夏的博客：操作系统 - 同步互斥
    下一篇：没有了