一、处理机调度

三种调度 （得背熟）

1. 高级调度（作业调度）

• 功能：根据调度算法和计算状态，从外存中选择一个或多个作业调入内存，投入运行。
• 功能细分：创建进程、分配内存等资源、将进程放入就绪队列等待CPU调度

2. 中级调度 （进程交换调度）

• 地位：决定了哪些进程可以参与CPU竞争
• 功能：让暂停的进程腾出内存，调到外存，执行挂起或者唤醒。

3. 低级调度 （进程调度）

• 地位：决定哪个进程获得CPU
• 功能：保存现场，调度新进程、新进程获取CPU控制权
• 三个基本机制：排队器、分派器、上下文切换机制

• 抢占和非抢占：
  非抢占：进行的进程运行完毕或者发生阻塞，才把CPU分配到其他经常，主动让出CPU。
  非抢占优点：实现简单、开销小；难以满足紧急实时任务；适用于批处理而非实时系统。
  抢占：允许暂停当前执行进程，重新分配CPU给另外的进程。
  抢占原则：优先权原则、短作业优先原则、时间片原则

  
  三级调度

4. 总结：
   高级调度：作业为调度对象。从外存到内存，主管进程创建。
   中级调度：进程为调度对象。外存内存互换，主管挂起与唤醒。
   低级调度：进程为调度对象。一直在内存，主管分配CPU执行程序。

调度准则

1. 一些时间
   到达时间：进入系统时间
   开始时间：首次使用CPU时间
   服务时间：CPU使用运行时间
   完成时间：退出系统时间
   周转时间：完成时间-达到时间
   带权周转：周转除以服务时间T1/T2
2. 面向用户的原则
   周转时间短
   响应时间快
   截止时间的保证
   优先权准则
3. 面向系统的原则
   系统吞吐量高
   处理机利用率好
   各类资源的平衡使用

调度算法

1. 先来先服务
   非抢占式，作业按时间到达先后顺序，进程按最先进入队列顺序。
   优点：实现简单，算法开销小，有利于长时间作业。
   缺点：不利于短时间作业。

2. 短作业优先
   非抢占式，优先运行运行时间短的作业。
   优点：有利于短作业或短进程。
   缺点：导致长作业不被调度，不能保证实时性，执行时间准确性不足。

   
   FCFS & SJF

3. 高优先权优先调度
   算法调度：非抢占式、抢占式
   优先权类型：静态优先权（进程类型、进程的需求、用户的要求）动态优先权（等待时间之类的）

4. 高响应比优先调度算法

   
   公式
   

   优点：
   对于等待时间相同的，服务时间越短优先权越高，有利于短作业
   对于服务时间相同的，等待时间越长优先权越高，先来先服务。
   对于长作业，作业优先级可以随等待是增高提高。
   缺点：
   优先权计算耗时

5. 时间片的轮转调度算法

• 将所有就绪进程按先来先服务排成队列
• 队首执行一个时间片后送到就绪队尾
• 下一个队首

E在17秒插入系统

6. 多级反馈队列调度算法

• 多个就绪队列 优先级逐个降低 时间片逐个增加
• 整合时间片 FCFS 优先级
• 低级只有等高级队列变空才能执行，当高级有新进程，低级在运行会被立刻抢占，被抢占的放回低级队列末尾。
  多级反馈算法示例

7. 实时调度
   博客
   开始截止时间、完成截止时间（最晚开始时间，最晚结束时间）

最早截止时间优先 EDF
截止时间越早，优先级越高。

EDF示例

最低松弛度优先 LLF
松弛度 = 完成截止时间 – 处理时间 – 当前时间
松弛度为0直接抢占，在两者都未到0的时候比较谁的松弛度低。

LLF示例
LLF示例

死锁

1. 概念：多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能再向前进
2. 原因：- 竞争资源 - 进程间推进顺序非法
3. 必要条件：互斥条件、请求和保持条件、不剥夺条件、环路等待条件。
4. 基本应对方法：预防死锁、避免死锁、检测死锁、解除死锁
5. 预防死锁具体手段：摒弃“请求和保持”条件、摒弃“不剥夺”条件、摒弃“环路等待”条件
6. 避免死锁：银行家
   Work：完成后给系统剩多少 - 初始就是Available 系统可用多少
   Need：还需要多少
   Allocation：占据多少
   Max：最大需求Allocation+Need
   银行家：虚拟执行这个，如果下个请求没资源的话，就拒绝这个请求。
   执行流程：
   （1）前置检查。request(1,2,3,0) <= Need不是直接error，request(1,2,3,0) <= Available 不是就等待。
   （2）虚拟执行：Available = Available-request
   Allocation = Allocation + request
   Need = Need - request
   （3）执行安全性算法，若安全，分配，不安全撤回并让进程等待。

• 安全序列就是按照这个序列银行家能借能还最终能成功让所有人都借到钱。

7. 检测死锁

   
   image.png

在资源分配图中，找到既不阻塞又不是孤点的进程 Pi （即找出一条有向边与它相连，且该有向边对应资源的申请数量小于等于系统中已有空闲资源数量）。消去它所有的请求边和分配边，使之成为孤立的结点。

8. 接触死锁
   剥夺资源、撤销进程