进程的调度

1️⃣调度的概念、层次

⭕️ 调度的基本概念

单由一堆任务要处理，但是由于资源有限，这些事情根本没法处理，这时候就需要有一种规则来决定分配这些任务的顺序，这就是”调度“的问题

且在多道程序系统中，进程的数量往往是多余处理机的个数的，这样不可能同时并行地处理各个进程。处理机的调度就是从就绪队列中按照一定的算法选择一个进程，并将处理机分配给他运行，以实现进程的并发执行

• 调度： 系统将计算机资源分配给进程
• 处理调度：多道程序环境下将处理器分配给各进程

调度要解决的问题： 三原则 What：按什么原则分配CPU、When：什么时候分配CPU，How：如何分配CPU

⭕️ 调度的三个层次：

🌟 高级调度（作业调度）：

按一定的原则从外存（磁盘、软盘等）上处于后备队列的作业中挑选一个（或者多个）作业调度到内存中，给他们分配内存等必要的资源，并建立相应的

PCB，以使得他们获得竞争处理及的权利，每个作业只调入一次，调出一次。作业调入时才会建立 PCB，调出时才撤销 PCB

作业的状态：

1. 提交状态
2. 后备状态
3. 执行状态
4. 完成状态

🌟 中级调度（内存调度）:

在有虚拟存储技术之后，可将暂时不能运行的进程使用进程对换调至外存等待，将这些进程内存空间释放，让内存能够重新接纳新的进程或使得内存中的进程能够更快推进。这么做是为了提高内存利用率和系统的吞吐量

🔴 暂时调到外存等待的进程状态为挂起状态，进程被调出内存后PCB并不会被调出到外存，而是会常驻内存，且被挂起的PCB会放到挂起队列中

🔵 中级调度就是决定哪个处于挂起状态的进程重新调入内存，一个进程可能会被多次调出，调入内存，因此中级调度发生的频率要必高级调度更高

🌟 低级调度（进程调度/处理机调度）

🔴 进程调度主要任务是按照某种方法和策略从就绪队列中选取一个进程，将处理机分配给它。

进程调度是操作系统中最基本的一种调度，在一般的操作系统中都必须配置进程调度，而且它的频率很高，一般是几十毫秒一次

引起进程调度的主要原因有：

• 处理器执行的进程完成任务，处理器空闲
• 处理器执行的进程转入阻塞状态，此时处理器空闲
• 处理器执行的进程被其他进程抢占
• 处理器执行的进程被挂起

🌟 对比:

2️⃣ 进程调度（低级调度）的时机与过程调度方式

⭕️ 进程调度的时机

🔴 需要进行调度与切换的情况：

1. 当前运行进程主动放弃处理（有的系统只允许进程主动放弃处理机）
2. 1. 进程正常终止
   2. 运行过程中发生异常而终止
   3. 进程主动请求阻塞（如等待I/O）
3. 当前运行的进程被动放弃处理机（有的系统、进程可以主动放弃处理机，当有更紧急的任务需要处理时，也会强行剥夺处理机）
4. 1. 分给进程的时间片用完了
   2. 有更紧急的需要处理
   3. 有更高级优先级的进程进入就绪队列

🔴 不能进行进程调度与切换的情况：

1. 在处理中断过程中，中断处理过程复杂，与硬件密切相关
2. 进程在操作系统内核的临界区中，但是进程在普通临界区中可以进行调度、切换
3. 在原子操作过程中，原子操作不可中断

❓ 为什么进程在操作系统内核程序临界区中不能进行调度与切换

临界资源：一个时间段内只允许一个进程使用的资源。各进程需要互斥的坊问临界资源

临界区：坊问临界资源的那段代码

内核程序的临界区一般是用来坊问某种内核数据结构的，比如进程的就绪队列，

假如进程此时访问的是打印机（普通的临界资源），所以，如果进程在访问一个普通的临界资源，在一种普通的临界区中，这个时候是应该进行进程调度和切换的，来增加系统的并发度，增加cpu的利用率。

但是如果是在内核程序临界区坊问的临界资源如果不尽快释放的画，即有可能影响到系统内核的其他管理工作，因此在坊问内核临界区间不能进程调度和切换

⭕️ 进程调度的方式

由系统是否会强行剥夺处理机引出进程调度的方式：所谓进程的调度方式，是指当某个进程在处理机上执行时，若有某个进程更为紧迫，需要处理时，即有优先权更高的进程进入就绪队列，此时应如何分配处理机，有两种方法：

1. 非剥夺调度方式（非抢占式）：只允许进程主动放弃处理机。在运行过程中即便有更加紧迫的任务到站，当前进程依然会继续运行，知道进程主动终止，或进入阻塞态；
2. 剥夺调度方式（抢占方式）：与上相反

3️⃣ 调度算法的评价指标

利用率越高越好：

🔴 利用率= CPU有效的工作时间 / CPU总的运行时间

CPU总的运行时间 = CPU的有效工作时间 + CPU的空闲时间

吞吐量越多越好

🔴 系统吞吐量= 总共完成了多少道作业 / 总共花了多少时间

周转时间：是指从作业提交给系统，到作业完成为止的这段时间间隔。它包括4个部分：

1. 作业在外存后备队列上等待调度的时间，只会发生一次
2. 进程在就绪队列上等待进程调度的时间（可能发生多次）
3. 进程在CPU上执行的时间（可能发生多次）
4. 进程等待I/O操作外存的时间（可能发生多次）

对于用户来说，更关心自己单个作业的周转时间

一个上厕所十分钟的人和一个上厕所一分钟的人，前者只需要从十分钟到十一分钟，后者需要从一分钟到十一分钟

🔴 周转时间=作业完成时间 - 作业提交时间

平均周转时间=各作业周转时间之和 / 作业数

带权周转时间：带权周转时间必然大于1，且周转时间与带权周转时间是越小越好

🔴 带权周转时间= 作业周转时间 / 作业实际运行时间

平均带权周转时间= 各个作业带权周转时间之和 / 作业数

等待时间 计算机的用户希望自己的作业尽可能少的等待处理机：

等待时间 = 作业处于等待处理器状态时间之和，等待时间越长用户满意度越低

响应时间：响应时间是交互环境下用户从键盘提交的第一个请求开始，到系统首次产生响应为止的时间，

响应时间 = 用户提交请求到首次产生响应的时间

4️⃣ 调度算法（先来先服务，最短作业优先、最高响应必优先）

⭕️ 先来先服务（FCFS First Come First Serve）

• 算法思想: 从“公平”的角度来说，“先到先用”，先进入到后备队列的作业，先调度
• 用于作业/进程调度：用于作业调度有先考虑时哪个作业优先进入到后备队列，用于进程调度时，考虑的时哪个进程先到达就绪队列
• 是否可抢占：是非抢占式的算法
• 🔴 优点：公平、算法实现简单
• 🔴 缺点：如果先进来的是一个长作业，那么后面的短作业需要等待很长的时间，带权的周转时间很大，即它对于长作业有利，对短作业不利

⭕️ 短作业优先算法（SJF、Shortest Job First）

• 算法思想：在所有进程几乎都同时到达时，追求最少的平均等待时间、最少的平均周转时间、最少的平均带权周转时间
• 算法规则：最短的作业/进程优先，这里所谓最短为服务时间最短
• 用于作业/进程调度：两者都可以用，但是用于进程调度时被称为“短进程优先”（SPF，Shortest Process First）算法
• 是否可抢占：SJF和SPF都是非抢占式算法，但是它们也有抢占式的版本--最短剩余时间优先算法（SRTN，Shortest Remaining Time Next）
• • 最短剩余时间优先算法：每当有进程加入就绪队列改变时就需要调度，如果新到达的进程剩余时间必当前运行的进程剩余的时间更短，则有新进程抢占处理机，当前运行进程重新回到就绪队列。另外，当一个进程完成时也需要调度
• 优点：“最短的”平均等待时间、平均周转时间
• 缺点：不公平，对短作业有利，对于长作业不利。会产生饥饿现象，也就是前面有很多短作业，而后面又长作业在等，这样会导致长作业长时间得不到服务，会“饿死”

⭕️ FCFS和SJF引起的思考－－高响应比优先算法

FCFS算法在每次进行调度的时候会安装到达的顺序执行，但是如果前面是一个长进程，需要时间很长，这样就不利于短进程了。

而SJF算法是选择一个时间最短的作业来执行，也不考虑作业的等待时间，会造成长进程的饥饿问题，这样就引出了“响应比高者优先”

• 算法思想：是FCFS和SJF的折中想法，要综合考虑作业/进程的等待时间和要求服务时间
• 算法规则：每次调度时先计算各个作业/进程的响应比，选择响应比最高的作业/进程执行
• • 🔴 响应比计算　＝　（等待时间＋处理时间）／　处理时间
• 用于作业/进程调度：两者都可
• 是否可抢占：非抢占式算法；只有当前运行的作业／进程主动放弃处理机时，才需要调度，才需要计算响应比
• 优缺点：等待时间相同时，处理时间短的优先，处理时间相同时，等待时间长的优先，对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了饥饿问题

⭕️ 时间片轮转算法

• 算法思想：公平的，轮流的为各个进程执行，让每个进程在一定时间间隔内都可以得到响应
• 算法规则：按照各进程到达的就绪队列的顺序，轮流的让各个进程执行一个时间片，若进程未在一个时间片内执行完，则剥夺处理器，将进程重新放到就绪队列对尾部
• 用于作业／进程调度：用于进程调度（只有作业放入内存建立了相应的进程后，才能被分配处理机时间片）
• 是否可抢占：是，进程未在时间片内完成，就会被强行剥夺处理机使用泉
• 如果时间片太大，使得每个进程都可以在一个时间片内完成，则时间片轮转调度算法就会退化未先来先服务算法，并且会增大进程响应时间，所有时间片不能太大
• 如果时间片太小，会导致进程切换过于频繁，系统会花大量的时间来处理进程切换，从而导致实际用于进程执行的实际比列减少

⭕️ 优先级调度算法

• 算法规则：根据作业的优先权进行作业调度，每次总是选取优先权高的作业／进程调度
• 是否可抢占：两者都有
• 优点：　用于优先级区分紧急程度、重要程度、适用于实时操作系统
• 🔴 缺点： 若源源不断地有高优先级进来，可能会导致低优先级的程序饿死
• 静态优先权：创建进程的时候久确定了，而且在进程的整个运行期间都保持不变
• 动态优先权：可以随着进程的推进或者随其等待时间的增加而改变，以便获得更好的调度性能

⭕️ 多级反馈队列调度算法