背景

  • 上下文切换
  • CPU调度

调度原则

  • CPU利用率
  • 吞吐量：在单位时间内完成的进程数量
  • 周转时间：一个进程从初始化到结束，包括所有等待时间所花费的时间
  • 等待时间：进程在就绪队列的总时间
  • 响应时间：从一个请求被提交到产生第一次响应所花费的总时间

  • 公平性

    调度算法

    先来先服务（FCFS）

  • 如果进程在执行中阻塞，队列中的下一个会得到CPU

  • 优点：
    • 简单

  • 缺点：

    • 平均等待时间波动较大
    • 可能处理花费时间长的排在处理花费时间短的前面
    • 可能导致I/O和CPU之间的重叠处理
      短进程优先（SPN）

  • 按照预测的完成时间来将任务入队

  • 可以是抢占也可以不可抢占的，根据最短最短剩余时间

  • 缺点

    • 连续的短任务流会使长任务饥饿
    • 短任务可用时的任何长任务的CPU时间都会增加平均等待时长
    • 需要预知未来
      最高响应比优先（HRRN）

  • 考虑了等待时间和执行时间

  • R = （w+s）/s， 选择R值最高的进程

    轮询（Round Robin）

  • 各个进程轮流占用CPU时间，公平，使每个进程都有机会去占用CPU

  • 设计时间切片

  • 缺点

    • 可能产生较多的上下文切换
    • 时间切片设置比较重要，不能太大或者太小
      多级反馈队列

  • 将就绪队列划分成独立的队列

  • 每个队列都有自己的调度策略
  • 根据反馈来调整优先级

  • 优点：

    • CPU密集型任务的优先级下降很快
    • I/O密集型任务停留在高优先级
      公平共享调度(FFS)

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

  • 在用户级别对资源进行公平调度

  • linux，CFS(Completey Fair scheduler)，完全公平调度算法

    实时调度

    实时操作系统

  • 定义

    • 正确性依赖于时间和功能两个方面的操作系统
  • 性能指标
    • 时间约束的及时性
    • 速度和平均性能相对不重要
  • 强实时系统
    • 时间约束很重要，需要保证在约束时间内完成，不然会产生错误

  • 弱实时系统

    • 要求重要的进程优先级更高，尽量完成

      多处理器调度

      多处理器的CPU调度更加复杂

  • 多个相同的单处理器组成一个多处理器

  • 考虑负载均衡

    对称多处理器（SMP）

  • 每个处理器运行自己的调度程序

  • 需要在调度程序中同步

    优先级反转

    优先级继承

  • 低优先级的进程继承了高优先级进程的优先级

    优先级天花板

  • 给所需的资源定优先级