【操作系统】第八章：CPU调度

背景

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

  在一个状态向另一个状态转换的时候会触发一次调度。

• 内核运行调度程序的条件

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

• 不可抢占

  调度程序必须等待事件结束

  （效率并不是很高）

• 可以抢占

  调度程序在中断被响应后执行

  当前程序从运行切换到就绪，或者一个进程从等待切换到就绪

  当前运行的进程可以被换出

  （现代操作系统常用的策略，效率较高）

调度原则

调度策略

程序执行模型

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

比较调度算法的准则

• 更快的服务
  • 低延迟：喝水的时候想要打开水龙头就有水
  • 高带宽：给游泳池冲水时希望从水龙头里同时流出大量的水，并且不介意是否存在延迟
• 减少响应时间
• 减少平均响应时间的波动
• 增加吞吐量
  • 减少开销（操作系统开销，上下文切换）
  • 系统资源高效利用（CPU、I/O设备）
• 减少等待时间

吞吐量 vs 延迟

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

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

调度算法

FCFS（先来先服务）

SPN/SJF SRT（短进程优先）

HRRN（最高响应比优先）

缓解了长程序可能产生的饥饿状态

Round Robin（轮询）

Multilevel Feedback Queue（多级反馈队列）

Fair Share Scheduling（公平共享调度）

实时调度

实时系统

• 定义：正确性依赖于其时间和功能两方面的一种操作系统
• 性能指标：
  • 时间约束的及时性（deadline）
  • 速度和平均性能相对不重要
• 主要特性：时间约束的可预测性
• 分类：
  • 强实时系统：规定时间内必须完成
  • 若实时系统：尽量完成
• 

可调度性

单调速率（RM）

• 最佳静态优先级调度
• 通过周期安排优先级
• 周期越短优先级越高
• 执行周期最短的任务

截止日期最早优先（EDF）

• 最佳的动态优先级调度
• Deadline越早优先级越高
• 执行Deadline最早的任务

多处理器调度与优先级反转

多处理器调度

优先级反转

• 优先级翻转是当一个高优先级任务通过信号量机制访问共享资源时，该信号量已被一低优先级任务占有，因此造成高优先级任务被许多具有较低优先级任务阻塞，实时性难以得到保证。

• 解决方法：优先级继承、优先级天花板

  • 优先级继承：

    优先级继承是当任务A 申请共享资源S 时， 如果S正在被任务C 使用，通过比较任务C 与自身的优先级，如发现任务C 的优先级小于自身的优先级， 则将任务C的优先级提升到自身的优先级， 任务C 释放资源S 后，再恢复任务C 的原优先级。这种方法只在占有资源的低优先级任务阻塞了高优先级任务时才动态的改变任务的优先级，如果过程较复杂， 则需要进行判断。

  • 优先级天花板：

    优先级天花板是当任务申请某资源时， 把该任务的优先级提升到可访问这个资源的所有任务中的最高优先级， 这个优先级称为该资源的优先级天花板。这种方法简单易行， 不必进行复杂的判断， 不管任务是否阻塞了高优先级任务的运行， 只要任务访问共享资源都会提升任务的优先级。