操作系统（五）

处理机调度

CPU 资源的时分复用

进程切换：CPU 资源的当前占用者切换
- 保存当前进程在 PCB 中的执行上下文(CPU状态)
- 恢复下一个进程的执行上下文
处理及调度
- 从就绪队列中挑选下一个占用 CPU 运行的进程
- 从多个可用 CPU 中挑选就绪进程可使用的 CPU 资源
调度程序：挑选就绪进程的内核函数
- 调度策略：依据什么原则挑选进程/线程？
- 调度时机：什么时候进行调度？

调度时机

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

内核运行调度程序的条件
- 进程从运行状态切换到等待状态
- 进程被终结了
非抢占系统
- 当前进程主动放弃 CPU 时
可抢占系统
- 中断请求被服务例程响应完成时
- 当前进程被抢占
  - 进程时间片用完
  - 进程从等待切换到就绪

调度策略

调度策略：确定如何从就绪队列中选择下一个执行进程
调度策略要解决的问题
- 挑选就绪队列中的哪一个进程？
- 通过什么样的准则来选择？
调度算法：在调度程序中实现的调度策略
比较调度算法的准则：哪一个策略/算法较好？

处理机资源的使用模式

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

比较调度算法的准则

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

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

减少响应时间
- 及时处理用户的输入请求，尽快将输出反馈给用户
减少平均响应时间的波动
- 在交互系统中，可预测性比高差异的平均更重要
低延迟调度改善了用户的交互体验
- 如果移动鼠标时，屏幕中的光标没动，用户可能会重启电脑
响应时间是操作系统的计算延迟

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

增加吞吐量
- 减少开销(操作系统开销，上下文切换)
- 系统资源的高效利用( CPU，I/O 设备 )
减少等待时间
- 减少每个进程的等待时间
操作系统需要保证吞吐量不受用户交互的影响
- 操作系统必须不时进行调度，即使存在许多交互任务
吞吐量是操作系统的计算带宽

处理机调度的公平性目标

公平的定义
- 保证每个进程占用相同的 CPU 时间
- 保证每个进程的等到时间相同
公平通常会增加平均响应时间

调度算法

先来先服务算法
- FCFS：First Come，First Served
短进程优先算法
- SPN：Shortest Process Next
- SJF：Shortest Job First (短作业优先算法)
- SRT：Shortest Remaining Time(短剩余时间优先算法)
最高响应比优先算法
- HRRN：Highest Response Ratio Next
时间片轮转算法
- RR：Round Robin
多级反馈队列算法
- MFQ：Multilevel Feedback Queues
公平共享调度算法
- FSS：Fair Share Scheduling

先来先服务算法( First Come First Served，FCFS

依据进程进入就绪状态的先后顺序排列
- 进程进入等待或结束状态时，就绪队列中的下一个进程占用 CPU
FCFS 算法的周转时间
- 示例：3个进程，计算时间分别为12，3，3
FCFS 算法的特征
- 优点：简单
- 缺点
  - 平均等待时间波动较大
    - 短进程可能排在长进程后面
  - I/O 资源和 CPU 资源的利用率较低
    - CPU 密集型进程会导致 I/O 设备闲置时 I/O 密集型进程也等待

短进程优先算法( SPN )

选择就绪队列中执行时间最短进程占用 CPU 进入运行状态
- 就绪队列按预期的执行时间来排序
短剩余时间优先算法( SRT )
- SPN 算法的可抢占改进
短进程优先算法具有最优平均周转时间
- SPN 算法中一组进程的平均周转时间
- - 修改顺序后平均等待时间更大
SPN 的特征
- 优点：具有最优平均周转时间
- 缺点
  - 可能导致饥饿：连续的短进程流会使长进程无法获得 CPU 资源
  - 需要预知未来
    - 如何预估下一个 CPU 计算的持续时间？
    - 简单的解决办法：询问用户
      - 用户欺骗就杀死相应进程
      - 用户不知道怎么办？
    - SPN 的执行时间预估
      - 用历史的执行时间来预估未来的执行时间

最高响应比优先算法( HRRN )

选择就绪队列中响应比 R 值最高的进程
- R = (w+s)/s
- w：等待时间(waiting time)
- s：执行时间(service time
特征
- 在短进程优先算法的基础上改进
- 不可抢占
- 关注进程的等待时间
- 防止无限期推迟

时间片轮转算法(RR，Round-Robin)

时间片：分配处理机资源的基本时间单元
算法思路
- 时间片结束后，按 FCFS 算法切换到下一个就绪进程
- 每隔 ( n - 1 ) 个时间片进程执行一个时间片 q
时间片为20的 RR 算法示例
- 4个进程的执行时间如下：
  - P1：53；P2：8；P3：68；P4：24；
- 甘特图
- 等待时间
  - P1 = ( 68 - 20 ) + ( 112 - 88 ) = 72
  - P2 = ( 20 - 0 ) = 20
  - P3 = ( 28 - 0 ) + ( 88 - 48 ) + ( 125 - 108 ) = 85
  - P4 = ( 48 - 0 ) + ( 108 - 68 ) = 88
- 平均等待时间 = ( 72 + 20 + 85 + 88 ) / 4 = 66.25
RR 算法的时间片长度
- RR 算法开销：额外的上下文切换
- 时间片太大
  - 等待时间过长
  - 极限情况退化成 FCFS
- 时间片太小
  - 反应迅速，但产生大量上下文切换
  - 大量上下文切换开销影响到系统吞吐量
- 时间片长度选择目标
  - 选择一个合适的时间片长度
  - 经验规则：维持上下文切换开销处于 1% 以内
比较 FCFS 和 RR
- 示例：4个进程的执行时间如下：
  - P1：53；P2：8；P3：68；P4：24；
  - 假设上下文切换时间为0，FCFS 和 RR 各自的平均等待时间是多少？
  - 这里两个极端中的 BestFCFS 即短进程优先算法，WorstFCFS 即长进程优先算法。表中可以看出，FCFS 抖动较大，而 RR 相对稳定

多级队列调度算法( MQ )

就绪队列被划分成多个独立的子序列
- 如：前台(交互)、后台(批处理)
每个队列拥有自己的调度策略
- 如：前台-RR，后台-FCFS
队列间的调度
- 固定优先级
  - 先处理前台，然后处理后台
  - 可能导致饥饿
- 时间片轮转
  - 每个队列都得到一个确定的能够调度其进程的 CPU 总时间
  - 如：80% CPU 时间用于前台，20% CPU 时间用于后台

多级反馈队列算法( MLFQ )

进程可在不同队列间移动的多级队列算法
- 时间片大小随优先级级别增加而增加
- 如进程在当前的时间片没有完成，则降到下一个优先级
MLFQ 算法的特征
- CPU 密集型进程的优先级下降很快
- I/O 密集型进程停留在高优先级

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 )
  - 占用资源进程的优先级和所有可能申请该资源的进程的最高优先级相同
    - 不管是否发生等待，都提升占用资源进程的优先级
    - 优先级高于系统中所有被锁定的资源的优先级上限，任务执行临界区时就不会被阻塞

同步互斥

并发进程的正确性

独立进程
- 不和其他进程共享资源或状态
- 确定性：输入状态决定结果
- 可重现：能够重现起始条件
- 调度顺序不重要
并发进程
- 在多个进程间有资源共享
- 不确定性
- 不可重现
并发进程的正确性
- 执行过程是不确定性和不可重现的
- 程序错误可能是间歇性发生的

进程并发执行的好处

进程需要与计算机中的其他进程和设备进行协作
好处1：共享资源
- 多个用户使用同一台计算机
- 银行账号存款余额在多台 ATM 机操作
- 机器人上的嵌入式系统协调手臂和手的动作
好处2：加速
- I/O 操作和 CPU 计算机可以重叠(并行)
- 程序可划分成多个模块放在多个处理器上并行执行
好处3：模块化
- 将大程序分解成小程序
  - 以编译为例，gcc 会调用 cpp，cc1，cc2，as，Id
- 使系统易于复用和扩展

并发创建新进程时的标识分配

程序可以调用函数 fork() 来创建一个新的进程
- 操作系统需要分配一个新的并且唯一的进程 ID
- 在内核中，这个系统调用会运行
  1
  new_pid = next_pid++
- 翻译成机器指令
  1
  2
  3
  4
  LOAD next_pid Reg1
  STORE Reg1 new_pid
  INC Reg1
  STORE Reg1 next_pid
两个进程并发执行时的预期结果(假定 next_pid = 100)
- 一个进程得到的 ID 应该是100
- 另一个进程的 ID 应该是101
- next_pid 应该增加到102

原子操作( Atomic Operation )

原子操作是指一次不存在任何中断或者失败的操作
- 要么操作成功完成
- 或者操作没有执行
- 不会出现部分执行的状态
操作系统需要利用同步机制在并发执行的同时，保证一些操作是原子操作

进程的交互关系：相互感知程度

相互感知的程度	交互关系	进程间的影响
相互不感知(完全不了解其他进程的存在)	独立	一个进程的操作对其他进程的结果无影响
间接感知(双方都与第三方交互，如共享资源)	通过共享进行协作	一个进程的结果依赖于共享资源的状态
直接感知(双方直接交互，如通信)	通过通信进行协作	一个进程的结果依赖于从其他进程获得的信息

互斥( mutual exclusion )
- 一个进程占用资源，其他进程不会使用
死锁( deadlock )
- 多个进程各占用部分资源，形成循环等待
饥饿( starvation )
- 其他进程可能轮流占用资源，一个进程一直得不到资源

临界区( Critical Section )

entry section
	critical section
exit section
	remainder section

临界区 ( critical section )
- 进程中访问临界资源的一段需要互斥执行的代码
进入区 ( entry section )
- 检查可否进入临界区的一段代码
- 如可进入，设置相应”正在访问临界区”标志
退出区 ( exit section )
- 清除”正在访问临界区”标志
剩余区 ( remainder section )
- 代码中的其余部分

临界区的访问规则

空闲则入
- 没有进程在临界区时，任何进程可进入
忙则等待
- 有进程在临界区时，其他进程均不能进入临界区
有限等待
- 等待进入临界区的进程不能无限期等待
让权等待(可选)
- 不能进入临界区的进程，应释放 CPU (如转换到阻塞状态)

临界区的实现方法(同步方法)

禁用中断
- 没有中断，没有上下文切换，因此没有并发
  - 硬件将中断处理延迟到中断被启动之后
  - 现代计算机体系结构都提供指令来实现禁用中断
  1
  2
  3
  local_irq_save(unsigned long flags);
  critical section
  local_irq_restore(unsigned long flags);
- 进入临界区：禁止所有中断，并保存标志
- 离开临界区：使能所有中断，并恢复标志
- 缺点
  - 禁用中断后，进程无法被停止
    - 整个系统都会为此停下来
    - 可能导致其他进程处于饥饿状态
  - 临界区可能很长
    - 无法确定响应中断所需的时间(可能存在硬件影响)
  - 要小心使用

软件方法

线程可通过共享一些共有变量来同步它们的行为

Peterson 算法

满足线程 Ti 和 Tj 之间互斥的经典的基于软件的解决方法(1981年)

共享变量

1 2	int turn; //表示该谁进入临界区 boolean flag[]； //表示进程是否准备好进入临界区

进入区代码

1
2
3

flag[i] = true;
true = j;
while (flag[j] && turn == j);

退出区代码
1
flag[i] = false;

线程 Ti 的完整代码

do {
  flag[i] = true;
  true = j;
  while (flag[j] && turn == j);
  		CRITICAL SECTION
  flag[i] = false;
  		REMAINDER SECTION
} while (true);

Dekkers 算法

线程 Ti 的代码

flag[0] := false;flag[1] := false;turn := 0;	//orl
do {
  flag[i] = true;
  while flag[j] == true {
    if turn != i {
      flag[i] := false
      while turn != i { }
      flag[i] := true
    }
  }
  	CRITICAL SECTION
  turn := j
  flag[i] = false;
  	EMAINDER SECTION
} while (true);

N 线程的软件方法( Eisenbery 和 McGuire )
缺点
- 复杂：需要两个进程间的共享数据项
- 需要忙等待：浪费 CPU 时间

更高级的抽象方法
- 硬件提供了一些同步原语
  - 中断禁用，原子操作指令等
- 操作系统提供更高级的编程抽象来简化进程同步
  - 例如：锁、信号量
  - 用硬件原语来构建
不同的临界区实现机制的比较
- 性能：并发级别

锁( lock )

锁是一个抽象的数据结构
- 一个二进制变量(锁定/解锁)
- Lock::Acquire()
  - 锁被释放前一直等待，然后得到锁
- Lock::Release()
  - 释放锁，唤醒任何等待的进程

使用锁来控制临界区访问

1
2
3

lock_next_pid->Acquire();
new_pid = next_pid++;
lock_next_pid->Release();

原子操作指令

现代 CPU 体系结构都提供一些特殊的原子操作指令
测试和置位( Test-and-Set )指令
- 从内存单元中读取值
- 测试该值是否为1(然后返回真或假)
- 内存单元值设置为1
  1
  2
  3
  4
  5
  boolean TestAndSet (boolean *target){
  boolean rv = *target;
  *target = true;
  return rv;
  }

交换指令( exchange )

交换内存中的两个值

void Exchange (boolean *a, boolean *b){
  boolean temp = *a;
  *a = *b;
  *b = temp;
}

使用 TS 指令实现自旋锁( spinlock )
- 线程在等待的时候需要消耗 CPU 时间
使用 TS 指令实现无忙等待锁
原子操作指令锁的特征
- 优点
  - 适用于单处理器或者共享生存的多处理器中任意数量的进程同步
  - 简单并且容易证明
  - 支持多临界区
- 缺点
  - 忙等待消耗处理器时间
  - 可能导致饥饿：进程离开临界区时有多个等待进程的情况
  - 死锁
    - 拥有临界区的低优先级进程
    - 请求访问临界区的高优先级进程获得处理器并等待临界区

同步方法总结

并发问题
- 多线程并发导致资源竞争
同步概念
- 协调多线程对共享数据的访问
- 任何时刻只能有一个线程执行临界区代码
确保同步正确的方法
- 底层硬件支持
- 高层次的编程抽象
锁是一种高级的同步抽象方法
- 互斥可以使用锁来实现
- 需要硬件支持
常用的三种同步实现方法
- 禁用中断(仅限于单处理器)
- 软件方法(复杂)
- 原子操作指令(单处理器或多处理器均可)

操作系统（五）

操作系统（五）

处理机调度

CPU 资源的时分复用

调度时机

调度策略

处理机资源的使用模式

比较调度算法的准则

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

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

处理机调度的公平性目标

调度算法

先来先服务算法( First Come First Served，FCFS

短进程优先算法( SPN )

最高响应比优先算法( HRRN )

时间片轮转算法(RR，Round-Robin)

多级队列调度算法( MQ )

多级反馈队列算法( MLFQ )

公平分享调度(FSS，Fair Share Scheduling)

传统调度算法总结

实时操作系统

多处理器调度

优先级反置( Priority Inversion )

同步互斥

并发进程的正确性

进程并发执行的好处

并发创建新进程时的标识分配

原子操作( Atomic Operation )

进程的交互关系：相互感知程度

临界区( Critical Section )

临界区的访问规则

临界区的实现方法(同步方法)

锁( lock )

原子操作指令

同步方法总结