处理机调度

目录

处理机调度概述

处理机调度的层次

低级调度

中级调度

高级调度

进程调度

进程调度的时机

进程调度的方式

非抢占式调度方式

抢占式调度方式

调度算法的评价指标

调度算法

先来先服务调度算法（FCFS，First Come First Serve）

短作业优先调度算法（SJF）

非抢占式短作业优先调度算法

抢占式短作业优先调度算法

优先级调度算法

优先级的类型

非抢占式的优先级调度算法

抢占式优先级调度算法

高响应比优先调度算法（HRRN）

---

---

处理机调度总结

---

---

处理机调度概述

  在多道程序的环境中，内存中存在多个进程，进程的数目多于处理机数目。此时在为进程分配处理机时需要进行处理机的调度。处理机的调度就是分配处理机。处理机调度算法就是按照处理机分配策略按照规定分配处理机的算法。

---

处理机调度的层次

低级调度、中级调度、高级调度。运行频率：低级 > 中级 > 高级。

低级调度

低级调度又称为短程调度或进程调度，调度的对象是进程。按照某种算法，决定就绪队列中哪个进程优先分配处理机。

中级调度

中级调度又称为内存调度。作用是：提高内存的利用率和系统的吞吐量。中级调度是将内存中暂时不能运行的进程调入外存，进程的状态变为挂起状态。当进程能够运行且处理机有空闲时，调入内存中，并修改进程的状态为就绪状态。

高级调度

高级调度又称为长程调度，调度的对象是作业。高级调度是按照某种算法，决定处于后备队列中的作业哪几个作业调入内存，并为他们创建进程，分配资源，为这些进程放入就绪队列。

高级调度周期长，运行效率低。

---

进程调度

进程调度的时机

进程在停止或放弃继续执行分为两种：

第一种：主动放弃

进程结束；进程执行过程中因异常中断；进程在I/0主动请求时，发生阻塞；

第二种：被动放弃

进程的时间片完；有更紧急的事件需要处理；有更高优先级的进程进入就绪队列。

进程调度的方式

非抢占式调度方式

 只允许进程主动放弃处理机。只要进程在执行，即使有更紧急的事件需要处理，处理机依然执行，直到进程主动放弃处理机。

优点：实现简单，系统开销小。但无法处理及时紧急的任务。

抢占式调度方式

在一个进程执行的过程中，如果遇到紧急的事件需要处理，该进程或立即停止执行，处理机优先分配给紧急的任务。

抢占不是任意的行为，需要遵循优先级原则、短进程优先原则、时间片原则。

---

调度算法的评价指标

CPU利用率：cpu有效工作时间 / (CPU总时间）

系统吞吐量：单位时间内完成的作业数。 作业数 / 时间

周转时间: 作业完成时间 - 作业提交时间；

平均周转时间：周转时间 / 作业数   ；

带权周转时间： 作业周转时间 / 作业实际运行时间。

等待时间：等待被服务的时间。

---

调度算法

先来先服务调度算法（FCFS，First Come First Serve）

算法思想：按照作业/ 进程到达的时间进行调度。  FCFS算法为非抢占式的调度方式，即可用哦关于作业调度，也可进程调度。

优点：公平、实现简单。缺点：对于长作业后的短作业来说，需要等待很长时间，长作业的带权周转时间很大。

是否会产生饥饿现象？

饥饿（进程/ 作业长期得不到服务），FCFS算法不会导致饥饿。

短作业优先调度算法（SJF）

算法思想：最短的作业 / 进程优先得到服务。（运行时间最短的优先），短作业优先调度算法可以是抢占式的方式也可非抢占式的方式。

优点：平均等待时间和平均周转时间较短。缺点：对短作业有利，对长作业不利。

是否会产生饥饿现象？

会导致饥饿现象，如果短作业/ 短进程不断的进入就绪队列，长作业/ 进程就无法执行，产生饥饿现象。

非抢占式短作业优先调度算法

抢占式短作业优先调度算法

优先级调度算法

优先级调度算法是把处理机优先分配给优先级高的作业/ 进程。

优先级的类型

静态优先级：创建进程时确定静态优先级，在运行期间保持不变。确定的依据：进程的类型、进程所需要的资源大小、用户需求的紧急程度。

动态优先级：创建进程时确定优先级，在运行的期间是根据进程的要求服务时间和等待时间不断调整优先级的大小。

优先级调度算法，如果在进程运行的过程中不断的有优先级较高的进程加入就绪队列，优先级低的会持续等待执行，会产生饥饿现象。

非抢占式的优先级调度算法

（优先数越大，优先级越高）

抢占式优先级调度算法

高响应比优先调度算法（HRRN）

综合考虑作业/进程的要求服务时间和等待时间，解决先来先服务调度算法和短作业优先调度算法缺陷。非抢占式调度算法。

优先级=（等待时间+要求服务的时间）/要求服务时间，优先级也相当于响应比。

该算法的优点：

1、如果作业的等待时间相同，要求服务时间越短，优先级越高。

2、如果作业的要求服务时间相同，等待时间越长，优先级越高。

3、对于长作业，随着短进程/作业的加入，等待时间会变长，优先级不断调整。