CPU调度_20200309_202000315

对CUP调度原理的简单介绍与了解，调度算法的介绍

CPU调度

• 5.0.1：目标
  • 介绍CPU调度
    • 为多道程序操作系统做基础
  • 多CPU之间的调度算法
  • 讨论为特定系统选择CPU调度算法
• 5.1：概述
  • 概念
    • 多道程序
      • 使得CPU可以在任何时候都有进程可以运行，以使CPU使用率达到最大
    • 当所需要执行的进程需要等待IO完成的时候，其他进程将CPU使用权拿走，进而提高了CPU的执行时间
  • CPU-I/O区间周期
    • 进程周期
      • CPU执行周期
      • I/O等待周期
    • CPU区间
      • 短CPU区间
      • 长CPU区间
    • 程式的分类
      • I/O约束程序
        • 具有很多短CPU区间
      • CPU约束程序
        • 可能有少量的长CPU区间
  • CPU调度程序
    • 当CPU空闲时，调度程序就会从就绪队列中选择一个进程让CPU运行
    • 就绪队列
      • 先进先出（FIFO）
      • 优先队列
      • 树或简单的无序链表
  • 抢占调度
    • 调度决策发生情况
      • 1、从运行状态到等待状态
        • I/O请求
        • 调用wait，等待子进程终止
      • 2、从运行态到就绪态
        • 中断
      • 3、等待态到就绪态
        • I/O完成
      • 4、进程终止
    • 对于上诉1、4只有调度，2、3可以进行选择
    • 1、4：非抢占、协作
    • 2、3：抢占
      • 共享数据的处理
      • 共享设备的处理
      • 对中断现场的保护
  • 分派程式
    • 定义
      • 将CPU的控制权交给由短期调度程序选择的进程
    • 所含功能
      • 切换上下文
      • 切换到用户模式
      • 跳转到用户程序的合适位置，以重新启动程序
• 5.2：调度准则
  • CPU使用率
  • 吞吐量
    • 单元时间内所完成进程的数量
    • 关注长短进程
  • 周转时间
    • 从进程提交到进程完成的时间
    • 包含时间
      • 等待进入内存
      • 在就绪队列中等待
      • CPU上执行时间
      • I/O等待
  • 等待时间
    • 不影响进程执行和执行I/O的时间
    • 只影响在就绪队列中等待所花费的总时间
  • 相应时间
    • 从提交请求到产生第一响应的时间
    • 是开始响应所需要的时间，不是输出相应所需要的时间
• 5.3：调度算法
  • CPU调度的定义
    • 从就绪队列中选择进程并为之分配CPU的问题
  • 先到先服务调度
    • first come first served FCFS
    • 先请求CPU的进程先分配CPU
    • 非抢占的
  • 最短作业优先调度
    • shortest job first SJF
    • 每一个进程与其下一个CPU区间段相关联，最先执行最短CPU区间的进程
    • 如何定义下一个CPU区间段
      • 批处理，就是一个批处理的CPU区间段
      • 短处理，近似的一个区间段来进行计算评估
    • 类型
      • 抢占
        • 最短剩余时间优先调度
          • shortest remaining time first scheduling
          • 目前阶段，最短的时间就是最先执行
      • 非抢占
  • 优先级调度
    • priority scheduling algorithm
    • 每一个进程都有一个优先级与其关联，优先级最高的先执行，如果一样，采用FCFS原则
    • 会遇到低优先级的进程无限等待的过程
      • 无穷阻塞
      • 饥饿
    • 防止如上现象的技术手段
      • 老化
        • 随着时间的推移，会将进程的优先级逐步提高
  • 轮转法调度
    • round-robin RR
    • 将CPU执行时间切成时间片，CPU循环执行就绪队列中的进程
    • 时间片
      • CPU一次执行同一个进程的时间
  • 多级队列调度
    • multilevel queue scheduling algorithm
    • 将就绪队列分成多个独立队列
      • 队列之间有优先级，并且可被抢占
      • 队列的调度方法可以不一样
  • 多级反馈队列调度
    • multilevel feedback queue scheduling algorithm
    • 将进程进行分类组成多个队列，并且队列之间允许进程交换；
    • 允许进程从一个队列换到另外一个队列
• 5.7：算法评估
  • 首先定义相对重要的参数，对系统有一个相对重要的影响
    • CPU使用率
    • 最大吞吐量
  • 评估的方法
    • 确定模型
      • 分析评估法
        • 使用给定算法和系统负荷，产生一个公式或者数字，以评估负荷算法的性能
      • 确定模型法
        • 采用特定预先确定的负荷，计算在该给定负荷下每种算法的性能
    • 排队模型
    • 模拟
    • 实现
• 5.6：操作系统实例
  • Solaris
  • Windows
  • Linux
    • 传统的UNIX调度算法
      • 不提供对SMP系统的支持
      • 当系统任务数量增加时，不能按比例调整
    • OS维护两个队列
      • 活动队列
        • 时间片未耗尽
      • 到期队列
        • 时间片耗尽
      • 当活动队列为空队列的时候，两个队列互换，继续执行
      • OS中每一个task都会均匀的分配到时间片
• 5.5：线程调度
  • 用户进程和内核进程是如何进行关联的
  • 主要讨论用户线程和内核线程调度问题
  • 竞争范围
    • 进程竞争范围
      • process contention scope PCS
      • 线程库将用户线程分配到哪个LWP上运行
      • LWP：虚拟处理器
    • 系统竞争范围
      • system contention scope SCS
      • OS决定LWP在哪个物理CPU上运行的问题
  • Pthread调度
    • 有效的区别设置PCS及SCS
• 5.4：多处理器调度
  • 多处理器调度的方法
    • 非对称多处理器
      • 一个主处理器处理所有的调度决策、I/O处理以及其他系统活动
    • 对称多处理
      • symmetric multiprocessing SMP
      • 每一个处理器自我调度
  • 处理器亲和性
    • 同一个进程需要或者尽量在同一个处理器上计算完成
    • 进程从一个处理器迁徙到另外一个处理器，连带着缓存及相关数据连带需要迁徙，这样子造成速率下降，资源浪费
  • 负载平衡
    • 保证多处理器之间，工作负载均匀分配
    • 分配方法
      • push migration
      • 定期检查所有CPU的负载情况，以达到负载均匀
      • pull migration
      • 当CPU空闲的时候，从负载高的CPU中索取任务
      • 会降低处理器亲和力
    • 因为迁徙进程会消耗一定的资源，因此很少会迁徙，就应该在分配的时候考虑到此问题
  • 对称多线程
    • 一个物理处理器提供多个逻辑处理器
      • SMT
      • 超线程
    • 提供的每个逻辑处理器都有独立的架构状态，并且负责处理自己的中断处理
    • 对SMT系统，线程的分配原则是仍旧对物理CPU进行分配，在考虑逻辑CPU