3.1处理机调度的基本概念
处理机的调度与死锁
作业-任务实体
进程-执行实体
一个作业由多个进程组成
3.1.1三种调度
1 高级调度
高级调度也称为作业调度
分配除cpu以外的资源
外存->内存就绪队列
2 低级调度
低级调度也称为进程调度
分配cpu
进程调度的两种调度方式
-
非抢占方式
-
抢占方式
3 中级调度
对挂起操作的调度
外存->内存
实际上就是存储器管理的对换功能
3.1.2调度队列模型
...
3.1.3选择调度方法和调度模型的准则
3.1.3.1 不同系统下的调度指标
| 系统类别 | 指标 |
|---|---|
| 批处理系统 | 周转时间 |
| 分时系统 | 响应时间 |
| 实时系统 | 截止时间 |
3.1.3.2 调度指标的计算方法
$$ {\small 周转时间T=外存后备队列等待作业调度+就绪队列等待进程调度+cpu执行时间+I/O阻塞等待} $$
$$ 周转时间T=完成时间-到达时间 $$
$$ 带权周转时间W=\frac{T}{服务时间T_{s} } $$
带权周转时间W越高说明等待时间越长
服务时间：作业被CPU调度的时间
$$ 平均周转时间\bar{T}=\frac{1}{作业个数n}[\sum_ {i=1}^{n} T_{i}] $$
$$ 平均带权周转时间\bar{W} =\frac{1}{n}[\sum_{i=1}^{n} \frac{T}{T_{s} }] $$
带权周转时间-反应作业的等待时间长短=作业的周转时间/系统提供服务的时间
$$ {\small 响应时间=外设传输时间+处理机处理时间+终端显示时间} $$
$$ 截止时间=开始执行的最迟时间或完成的最迟时间 $$
3.1.3.3 调度模型的准则
1 面向用户的准则
2 面向系统的准则
3.2调度算法
| 名词 | 计算方法 |
|---|---|
| 周转时间 | 完成时间-到达时间 |
| 带权周转时间 | 周转时间/服务时间 |
3.2.1 FCFS 先来先服务
先入就绪队列的先分配
利于长作业
利于CPU繁忙型
不利于I/O繁忙型
3.2.2 SJF & SPF 短作业(短进程)优先
服务时间短的作业优先（到达时间最早的依旧先执行 ）
利于提高吞吐量
不利于长作业、紧迫性作业
不一定真正做到短优先
3.2.3 FPF 高优先权优先
HRRN高响应比优先调度算法。
进程分为抢占式、非抢占式：
graph LR
A(进程)
A --- B(抢占式)
A --- C(非抢占式)
优先权的类型：
graph LR
A(优先权)
A --- B(动态)
A --- C(静态)
优先权计算方法： $$ 优先权Rp=\frac{等待时间+要求服务时间}{要求服务时间}=\frac{响应时间}{要求服务时间} $$
优先权越大，优先级越高
等待时间=上一个进程的完成时间-这个到达时间
3.2.4 RR 时间片轮转的调度算法
常用于分时系统
-
RR时间片轮转算法
时间片大小的确定
-
多级反馈队列调度算法
目前公认最好
(1) 时间片短优先权高
(2) 就绪队列采用FCFS；上一个队列没完成的进程会调入下一个就绪队列
(3) 仅当上一个队列空闲时才会进入下一个队列
3.3实时调度算法
硬实时
软实时
3.3.1实时调度的基本条件
-
提供必要信息
就绪时间、截至时间、处理时间、资源要求、优先级
-
系统处理能力强 $$ \sum_{i=0}^{n} \frac{Ci}{Pi}\le N $$ n个(硬)实时任务，Ci处理时间，Pi周期时间，N处理机数(默认为1)
-
*抢占式调度
-
具有快速切换机制
中断快速相应、任务快速分派
3.3.2实时调度算法分类
graph LR
A(实时调度算法)
A --- B(非抢占调度)
B --- D(非抢占式轮转调度)
B --- G(非抢占式优先级调度)
A --- C(抢占调度)
C --- E(基于时钟中断的抢占式优先权调度算法)
C --- F(立即抢占的优先权调度)
3.4多机处理的实时调度
3.4.1常用的几种实时调度算法
1 最早截止时间优先EDF(Earliest Deadline First)算法
截止时间早的优先权高
2 最低松弛度优先LLF(Least Laxity First)算法
紧急程度高（松弛度小）优先权高
松弛度计算： $$ 松驰度=必须完成时间-本身的运行时间-当前时间 $$ 发生切换的情况：当前任务完成或下一个任务的松弛度=0
3.5产生死锁的原因和必要条件
死锁(Deadlock):是指多个进程在运行过程中因争夺资源而造成的 一种僵局，当进程处于这种状态时，若无外力作用，它们都将无法再 向前推进。
产生死锁的原因：
graph LR
A(产生死锁的原因)
A --- B(资源竞争)
A --- C(进程间推进顺序非法)
3.5.1产生死锁的原因
-
资源竞争
(1) 可剥夺资源-不会引起进程死锁
CPU、主存
(2) 不可剥夺资源-可能会发生死锁-临界资源
磁带机、打印机
(3) 独占资源
-
进程间推进顺序非法
3.5.2产生死锁的必要条件
-
互斥条件
访问的临界资源
-
请求和保持条件
请求别的资源但不放弃自己的资源
-
不剥夺条件
不能抢其他进程拿到的资源
-
环路等待条件
死锁环形链
3.6预防死锁的方法
-
预防死锁
破坏产生死锁的必要条件
-
避免死锁
防止系统进入不安全状态
不是所有的不安全状态都是死锁状态
-
检测死锁
-
解除死锁
避免死锁-银行家算法
1) 数据结构：
m类资源，n个进程
(1) 可利用资源Avaliable - 一维数组
Avaliable[j]=k，j类资源有k个(2) 最大需求矩阵Max - n*m矩阵
Max[i,j]=k，进程i需要j类资源的最大数是k个
(3) 分配矩阵Allocation - n*m矩阵
Allocation[i,j]=k，进程i已分配j类资源k个
(4) 需求矩阵Need - n*m矩阵
Need[i,j]=k ，进程i需要j类资源k个
三个矩阵的关系：Need[i,j] = Max[i,j] - Allocation[i,j]
2) 处理步骤：
用于求解进程i请求k个j类资源
(1) Request[j] <= Need[i,j] 成立则进行第二步
(2) Requese[j] <= Allocation[i,j] 成立则进入第三步
(3) 系统试探着给i分配资源
| 分配前 | 分配后 |
|---|---|
| Avaliable[j] | Avaliable[j] - Request[j] |
| Allocation[i,j] | Allocation[i,j] + Request[j] |
| Need[i,j] | Need[i,j] - Request[j] |
(4) 系统执行安全性算法
3) 安全性算法：
(1) step1:设置两个向量
| 向量 | 解释 | 类型 |
|---|---|---|
| work[j] | 工作向量，表示系统可供给的j类资源数目；初始work=Avaliable | |
| Finish[i] | 初始Finish[i]=false(i=1...n)，分配资源后Finish[i]=true | 含n个元素的一维数组 |
安全性检测就是要验证程序按照某顺序执行完n个进程后，Finish是否都为true
goto step2
(2) step2:判断进程是否有资源可以分配
满足 Finish[i] = false; Need[i,j] <= work[j];则goto step3，否则goto step4
(3) step3:待进程运行完成后收取进程释放的资源 Allocation[i,j] ，并对进程的 Finish[i]进行标记。跳转至step2，直到没有资源分配或没有进程需要资源。
work[j] = work[j] + Allocation[i,j];
Finish[i] = true;
goto step 2
(4) step4:如果所以进程的 Finish[i] = true;都满足，则系统处于安全状态，否则系统处于不安全状态
4) 例子：
3.7死锁的检测与解除
3.7.1死锁的检测
基本思路：
- 保存资源请求分配信息；
- 提供一种解析信息的算法判断是否进入死锁
资源分配图可以用来描述系统的死锁
死锁状态 ——> 资源分配不可完全简化
3.7.2死锁的解除
- 剥夺资源
- 撤销进程
😍
🤣怎么样