华南农大习题与考试|操作系统(10)多处理器调度和实时调度计算机基础|后端开发

1. 多处理器调度紧耦合多处理器的调度问题：共享同一内存，且由OS完全控制的多个处理器。

文章图片

2. 设计问题 - 三个问题

把进程分配到处理器:
- 静态分配:一个进程始终在同一CPU上执行
- 动态分配:所有CPU共用一个就绪队列，于是进程可在不同时间运行于不同处理器上，利于各CPU的负载均衡。
在单个处理器上是否使用多道程序设计
- 一个进程的多个线程 应该同时在多个CPU上并行运行，而不是在单个CPU上多道运行，这时该进程运行情况好，且各CPU的负载平衡，性能最佳
进程分派(调度):选择哪个进程/线程运行
- 简单的调度算法(如:FCFS或者静态优先级)更有效，系统开销较低。

3. 进程调度:算法的选择

文章图片

由图可知:双处理器下，不同调度算法所导致的吞吐量(单位时间内完成的作业个数)差别很小。
由此图所能得出的结论就是对于多处理器，调度算法的选择不如在单处理器器中重要。因此，多处理器系统中，采用简单的FCFS或“静态优先级+FCFS”算法就足够了
4. 实时调度 4.1 实时调度的需求背景 【华南农大习题与考试|操作系统(10)多处理器调度和实时调度】实时任务的处理要求紧急，具有最高优先权
通常需要预先规定其开始或完成的最后截止期限
实时任务分类:

硬实时任务: 必须在最后期限内开始或完成
软实时任务: 时间限制较弱
非周期性实时任务: 不定期发生
周期性实时任务: 每隔T个时间单位发生一次

4.2 调度方式

轮转抢占式调度: 获得秒级响应时间。
优先级驱动非抢占式调度:秒-数十毫秒级响应
基于优先级的固定点抢占调度:毫秒级响应
基于优先级的立即抢占调度：微秒级响应

4.3 调度方法分类

静态表调度:适合于周期性任务,根据任务的到达时间、处理时间、结束期限和优先级等，确定各任务的调度顺序和开始时刻
静态优先级抢占调度:给任务指定静态优先级
动态规划调度:一个新任务到达时，当能够满足它以及已有任务的时间约束(最后期限)时，才接受这个任务，并编入调度顺序
动态尽力调度:目前商用系统中常用，新任务到达就接受并指定优先级。尽力满足所有任务的时间约束，并终止那些已开始运行但将超过最后期限的进程

4.4 最早最后期限调度 含义:调度完成期限最近的任务

文章图片

如图所示，A1和B1任务同时到达，然后查看A1的完成期限是20,B1的完成期限是50，A1的完成期限更近一些，因此A1先被调度，当CPU空闲的时候,B1可以被执行，当时刻到达第20s时，此时A2到达，此时发生调度，B1的完成期限是50，而A2的完成期限是40，因此A2先被调度，B1被换下，当CPU空闲时B1继续执行，直到下一次调度。

有自愿空闲时间的最早启动期限调度:如果事先知道各任务的启动最后期限，则调度启动期限最早的合格任务(甚至该任务还未到达)

文章图片

4.5 速率单调调度含义:为每个任务分配一个与其发生频率(hz)成正比的优先级。频率越低(周期越长)的任务优先级越低，抢占式调度优先级高者。

对周期性任务，任何调度算法都有以下式子成立:
- 有n个周期性任务，任务i的周期为Ti，处理时间为Ci，Ci/Ti是任务i的CPU利用率。则只有满足以下条件:C1/T1+C2/T2+C3/T3+...+Cn/Tn <= 1才可能处理所有的负载。满足该条件的实时系统称为任务可调度的。
- 周期就是指任务的最后期限-任务的到达时间

4.6 优先级反转现象

在任何优先级调度方案中，系统应该总是执行优先级最高的任务。但当一个高优先级任务不得不等待一个低优先级任务时，就发生了优先级反转。(低级任务先占用了一个资源，高级任务请求同一资源时将阻塞，并等待低级任务用完资源)
无界限优先级反转：优先级反转的持续时间不仅依赖于低级任务占用资源的时间，还依赖于其它不相关任务的不可预测的行为

4.7 优先级反转避免

优先级继承:当高级任务请求任务被阻塞时，低级任务的优先级临时调高至高级任务的优先级。低级任务释放资源时，调至原优先级。
优先级置顶：每个资源的优先级设定为比使用该资源的最高级任务的优先级还要高一级
- 使用资源时，该任务临时置为该资源的优先级，释放资源时调回为原先的优先级

5. Linux调度 5.1 实时调度

三类线程:实时线程优先级:0~99
- FIFO实时线程:按“优先级+FIFO”调度。当有更高级线程就绪时，当前线程立即被抢占。
- 轮转实时线程:按“优先级+时间片轮转”调度。当前进程时间片结束后，才调度下一个同级或更高级线程。
- 非实时线程（任务task）:优先级范围100~139。当没有实时线程就绪时，才调度非实时线程。当就绪进程的时间片(时间配额)用完时，将根据其优先级赋予一个新的时间片。

5.2 非实时调度

非实时任务/进程的时间片：根据其动态优先级确定，优先级高者时间片大。一般为10~200ms。
- 每个非实时进程有一初始的静态优先级(100~139)，默认为120（对应的时间片100ms）。
- 新创建的子进程继承其父进程的优先级，与父进程均分父进程的剩余时间片
- 动态优先级=max(100, min(静态优先级+5-bonus, 139))
- bonus范围0~10。<5时表示惩罚，>5时为奖励。bonus与进程的平均睡眠时间有关。
  睡眠时间越长，bonus越大，动态优先级提高。
Linux2.6进程调度算法的时间复杂度为O(1)，可在固定时间内选出优先级最高的进程，与就绪进程/处理器数目无关。
- 为每个处理器维护以下两套“优先级队列+位图”。
- 当活动队列全为空时，才调度过期队列中的进程
  
  文章图片

6.FreeBSD调度

内核线程优先级0127，实时/分时/空闲线程优先级128255。内核线程、实时线程、交互式的分时线程优先级高。
处理器亲和性：一个线程应该始终在一个处理器上运行，因为它的数据可能保存在该处理器的cache中，迁移到其它处理器时其数据和流水线被清空。
线程迁移可平衡处理器的负载。两种迁移措施：
- 拉取：将新建线程添加到空闲处理器的任务队列中
- 推送：调度程序每0.5秒平衡一次负载最大和最小的两个处理器的任务队列。