CPU调度

背景

• 上下文切换

切换CPU的当前任务，从一个进程/线程到另一个

保存当前进程/线程在PCB/TCP中的执行上下文

读取下一个进程/线程的上下文

• CPU调度

从就绪队列中挑选一个进程/线程作为CPU将要运行的下一个进程/线程

调度程序：挑选进程/线程的内核函数（通过一些调度策略）

什么时候进行调度？

• 在进程/线程声明周期的什么时候进行调度？

一个程序从运行态转换成等待状态

一个进程被终结了

• 不可抢占

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

• 可以抢占

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

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

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

调度原则

• 执行模型：程序在CPU突发I/O中交替

每个调度决定都是关于在下一个CPU突发时将那个工作交给CPU

在时间分片机制下，线程可能结束当前CPU突发性被迫放弃CPU

评价指标：

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

调度原则：

• 减少相应时间：及时处理用户输出并且尽快将输出提供给用户
• 减少平均响应时间的波动：在交互系统中，可预测性比高差异低平均更重要
• 增加吞吐量：减少开销(操作系统上的开销，上下文切换)；系统资源的高效利用(CPU，I/O设备)
• 减少等待时间：减少每个进程的等待时间

遵守调度原则：

• 低延时调度增加了交互式表现
• 操作系统需要保证吞吐量不受影响
• 吞吐量是操作系统的计算带宽
• 响应时间是操作系统的计算延时

调度算法

• FCFS 先来先服务

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

• SPN(SJF) SRT 短进程优先（短作业优先） 短剩余时间优先

不公平，但是平均等待时间最小

需要精确预测计算时间

可能导致饥饿

• HRRN 最高响应优先

基于SPN调度改进

不可抢占

• RoundRobin 轮循

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

• Multilevel Feedback Queues 多级反馈队列

和SNP类似

• Fair Share Scheduling 公平共享调度

公平是第一要素

实时调度

正确性依赖于其时间和功能两方面的一种操作系统

性能指标：

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

主要特性：

• 时间约束的可预测性

分为2类：

• 强实时系统：需要在保证的时间内完成重要的任务，必须完成
• 弱实时系统：要求重要的进程的优先级更高，尽量完成，并非必须

如何衡量系统完成实时性要求？

• 任务：一次计算，一次文件读取，一次信息传递

周期任务：

任务有规律的重复

周期 P

执行时间 e

使用率 U = e/p

• 属性：取得进展所需的资源。定时参数

调度算法：

• RM速率单调调度

最佳静态优先级调度

通过周期安排优先级

周期越短优先级越高

执行周期最短的任务

• EDF最早期限调度

最佳动态优先级调度

DeadLine越早优先级越高

执行DeadLine最早的任务

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

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

• 多个相同的但处理器组成一个多处理器
• 优点：负载共享

对称多处理器（SNP）

• 每个处理器运行自己的调度程序
• 需要在调度程序中同步

优先级反转

• 可以发生在任何基于优先级的可抢占的调度机制中
• 当系统内的环境强制使用高优先级任务等待低优先级任务时发生

优先级反转的持续时间取决于其他不想管任务的不可预测的行为

• 优先级天花板：资源的优先级和所有可以锁定该资源的任务中优先级最高的那个任务的优先级相同
• 除非优先级高于系统中所有被锁定的资源的优先级上限，否则任务尝试执行临界区的时候会被阻塞
• 持有最高优先级上限信号量锁的任务，会继承被该锁所阻塞的任务的优先级