处理机调度层次和算法目标

一：处理机调度层次

1：High Level Scheduling 高级调度

又称长调度或者作业调度，调度对象是作业。主要功能是根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为其创建进程，分配必须的资源。

2：Low Level Scheduling低级调度

又称短调度或者进程调度，调度对象是进程（or内核级线程）。功能是根据某种算法决定就绪队列中哪个进程获得处理机。

3：Intermediate Scheduling中级调度

又称内存调度，主要用用于提高内存利用率和系统吞吐量，把那些暂时不能运行的程序调至外存，此时进程状态称为就绪驻外存状态（或挂起状态）。

二：目标

1：处理机调度的目标

①：资源利用率
C P U 利 用 率 = C P U 有 效 工 作 时 间 / （ C P U 有 效 工 作 时 间 + C P U 空 闲 等 待 时 间 ） CPU利用率 = CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间） CPU利用率=CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）
②：公平性

③：平衡性

④：策略强制性：对定制的策略强制执行，即使造成某些工作延迟。

2：批处理系统目标

作业与作业调度

1：作业与作业步

①：作业是比程序更广泛的概念，包含了数据，程序和作业说明书

②：作业步即运行步骤

2：作业控制块（Job Control Block ——JCB）

PS: 类似于进程控制块PCB（Process Control Block)

3：作业运行三种状态

①：后备状态：此时为该作业建立JCB，放入后备队列

②：运行状态

③：完成状态

★★★★几种作业调度算法★★★★

一：先来先服务算法FCFS（first-come first-served）

原理：程序会按照作业到达的先后次序来调度，也可以说是优先考虑等待时间最长的作业，而不管该作业的执行时间。

几点说明 1：系统会按照等待时间长短进行排序，将等待时间长的作业调度，只有当调度的作业执行完或者是出现阻塞后，才会将处理机分配给其他作业。

​ 2：现在很少将FCFS作为主调度算法，因为可能会出现其他作业死等的情况。

​ 3：广义上来说，FCFS也是一种优先级调度算法，把等待时间作为优先级。

二：短作业优先算法SJF（short job first)

说明：SJF原理和FCFS相似，但是SJF调度中，系统不是按照等待时间长短来调度作业的，而是按照作业执行所需时间长短来进行分配，将所需时间更短的作业优先调度。从后备队列中选择若干满足条件的作业调入内存中运行。

**★缺点：1：必须事先知道每个作业执行所需的时间。 **

​ **2：对长作业非常不利，长作业的周转时间明显增强。 **

​ 3：该调度算法完全没有考虑作业的紧迫程度。

三：优先级调度算法PSA（priority-scheduling algorithm)

1：在优先级调度算法中，基于作业的紧迫程度，由外部赋予作业相应的优先级，系统再根据优先级，选择高优先级的作业放入内存。

四：高响应比优先调度算法HRRN（Highest Response Ratio Next）

再FCFS算法中，只考虑了等待时间而不考虑执行时间。而在SJF算法中，只考虑了执行时间，而忽略了等待时间。HRRN则兼顾两者。

优先权公式：
优 先 权 = ( 等 待 时 间 + 要 求 服 务 时 间 ) / 要 求 服 务 时 间 = 响 应 时 间 / 要 求 服 务 时 间 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间 优先权=(等待时间+要求服务时间)/要求服务时间=响应时间/要求服务时间
响应时间：
响 应 时 间 = 等 待 时 间 + 要 求 服 务 时 间 响应时间=等待时间+要求服务时间 响应时间=等待时间+要求服务时间
说明：

1：该优先权是动态的，与PSA不同，PSA是外部直接赋予一个静态的优先权，PSA中的优先权不会变化。HRRN中的优先权会随着时间变化。

2：如果等待时间相同，则要求服务时间越短，其优先权越高，有利于短作业，类似于SJF。

3：当要求服务时间相同，等待时间越长，优先级越高，有利于先等待的作业，类似于FCFS。

4：对于长作业，其优先级随着时间的增长而提高。

5：在折中SJF和FCFS的同时，每次都需要计算响应比，系统开销增大。

★★★进程调度

一：进程调度的任务

1：保护现场：保存处理机现场信息，如计数器和多个寄存器的内容。

2：按算法选取进程：按照某种算法从就绪队列选取进程，将状态改为运行状态，并准备把处理机分配给它。

3：把处理器分配给进程：此时将所选的进程的PCB中有关处理机现场信息放入各寄存器中，并把处理器控制权交给该进程，让他从上次的断点处恢复运行。

二：进程调度机制

三：进程调度方式

★1：抢占方式（Preemptive Mode）：将当前的进程放入内存执行，当满足某种原则的进程到达时，停止当前的任务，把新的进程放入内存执行。

抢占不是一种任意行为，必须遵守一定的原则：

①：优先权原则：指允许优先级高的进程抢占当前进程的处理机。

②：短进程优先原则：指新到的短进程可以抢占当前长进程的处理机。

③：时间片原则：指各进程按时间片轮转运行时，当正在执行的进程的时间片用完后，便停止该进程的执行，而重新进行调度。

★2：非抢占方式（Nonpreemptive Mode）：与抢占优先算法不同，当新进程达到时，系统只有当前进程执行完后或者当前进程出现阻塞，才会将新进程放入内存。

当该方式采用，却引起进程调度，可能是以下几个原因：

①：正在进行的进程执行完毕，或者出现阻塞。

②：正在执行的进程因发出IO请求而停止。

③：在进程通信或同步中，执行了某种原语操作。

四：进程的调度算法

1：轮转调度算法RR-----时间片原则

​ 1）进程切换时机：

​ ①：当该进程时间片未使用完，就已经完成后，立即**调度程序，将该进程从就绪队列中移除，将就绪队列队首的进程运行。

​ ②：当该进程时间片已使用完，进程尚未完成，计时器中断程序被**。该进程送入就绪队列。

​ 2）时间片选择：如果时间片太短，意味着需要频繁切换进程，增加系统开销。如果时间片太短，使得每个进程都可在一个时间片内完成，则RR算法退化为FCFS算法。

2：优先级调度—基于优先权原则的抢占方式

​ 1）优先级的类型可分为：静态优先级和动态优先级。

​ ①：静态优先级在开始的时候就已经确定，在整个运行时间内不会发生改变。确定优先级的方式①：进程类型：通常系统进程优先级高于用户进程。②：进程对资源的需求：对资源需求越少的优先级越高。③：用户要求：根据进程紧迫程度和用户付费的多少确定。

​ ②：动态优先级指在开始时赋予进程一个优先级，但是优先级的值随着时间的推移而改变，以便获得更好的调度性能。当规定随着时间推移，优先级下降，可以防止长作业垄断处理机。

3：多队列调度算法：事先将进程分为多个队列，给每个队列设置不同的优先级。对每个队列实施不同的调度，可以针对不同的用户提供多种调度策略。

4：多级反馈队列：多队列调度的进一步改进，在基于时间片原则的基础上，给每个队列设置一个不同的优先级，将队列按照优先级从高到低排列，分别依次执行时间片S1，····，Sn。最高优先级队列中的进程执行时间片S1，若进程完成，则将该进程撤离系统，若没有完成，则将该进程送入第二高优先级队列，重复上述过程，如果执行到第n优先级仍没有完成，则在第n优先级队列中进行轮转调度（RR）。

★★★★死锁★★★★

一：死锁的产生

1：竞争不可抢占性资源引起死锁。

2：竞争可消耗资源引起死锁。

3：进程推进顺序不当引起死锁。

二：死锁的定义：

如果一组进程中的每一个进程都在等待仅由该组进程中的其他进程才能引发的时间，那么改组进程是死锁（Deadlock）。

三：产生死锁的必要条件

★1）产生死锁必须同时具备以下四个条件：

①互斥条件：进程对所分配到的资源进行排他性使用，即在一段时间内，某资源只能被一个进程占用。如果此时还有其他进程请求该资源，则请求进程只能等待。直至占有该资源的单位将其释放。

②请求和保持条件：进程已经保持了至少一个资源，但又提出新的资源请求，而该资源已经被其他进程占用，此时请求进程被阻塞，但对自己保持的资源不释放。

③不可抢占条件：进程已获得的资源在未使用完之前不能被抢占，只能在进程是用完时自己释放。

④循环等待条件：在发生死锁时，必然存在一个进程—资源的循环链，即进程{P0，P1，P2，P3，P4，P5，P6，P7}中，P1请求一个P0占有的资源，P0在等待P2占有的资源。

四：处理死锁的方法

★1）预防死锁：事先预防的方法，使用某些技术破坏四个必要条件（spooling)。

1：破坏“请求和保持”条件：通过两种协议完成

①第一种协议：在所有进程开始前，必须一次性申请所有资源，当系统可分配的资源足够时，才允许分配，只要一个资源不满足，都不允许分配。

优点：简单，易行，安全；缺点：资源被严重浪费，恶化资源利用率。是进程经常发生饥饿显现。

②第二种协议：第一种协议的改进，允许一个进程只获得处器运行资源后，便开始运行。运行过程中逐步释放自己使用完的资源，再请求新的资源。

2：破坏”不可抢占“条件

协议规定：当某个已经拥有不可抢占资源的进去申请新资源却不能得到满足时，必须释放已经保持的资源，待以后重新申请。

缺点：该方法实现复杂。而且需要很大的代价，因为不可抢占资源释放后，为保证进程完整无误，需要重新执行任务。（例如打印机打印一半后释放资源，又重新申请，为保证打印信息连续完整，必须从头开始），加大了系统开销，降低系统吞吐量。

3：破坏”循环等待“条件

对所有资源排序，规定每个进程必须按照资源号递增的顺序申请资源，当需要申请资源号低的资源时，需要将资源号高的资源释放掉。

相对前两中方法，资源利用率和吞吐量有所提升。同时也有几个问题：首先是资源号的排序，限制了增加新设备。其次是虽然资源号排序是考虑了大部分任务给定的，但是仍有少数任务的资源请求顺序不服从大多数的请求规律。第三，会限制用户的简单自主编程。

★2）避免死锁：同样是事先预防，不过不是通过技术破坏产生死锁的必要条件，而是在资源分配过程中，用某种方法方式系统进入不安全状态，防止死锁产生。

1：安全状态：当系统不会出现死锁时，称为安全状态，可避免死锁发生。相反，当系统处于不安全状态时，可能进入死锁。

★★★★★★★★★★★★★★★★★2：利用银行家算法避免死锁

①：银行家算法数据结构：

-1-可利用资源向量Available：一个m元素的数组，表示m个资源的可分配数量。

-2-最大需求矩阵Max：一个n x m的矩阵，n是n个进程，m是资源，Max[n,m]表示第n个进程对第m个资源的最大需求量。

-3-分配矩阵Allocation：n x m 矩阵，表示当前已经分配的资源量。

-4-需求矩阵Need：nxm矩阵，Need[n,m]表示第n个进程对第m个资源仍需的量。

②：银行家算法：

例子《计算机操作系统》第四版，西安电子科技大学出版社，page：122。

★3）检测死锁：这种方法不采用任何限制措施，允许进程产生死锁，然后通过某些方法及时检测出死锁，并把进程从死锁中解脱出来。

★4）解除死锁：当检测到发生死锁时，就采取相应措施，将其解脱出来，通常是撤回进程，将资源释放出来，分配给及其他进程。

3） + 4）操作：

①：死锁检测算法

-1- 资源分配图（Resource Allocation Graph）

◯表示进程，▢表示资源，▢中的点数表示该资源的个数。◯—>▢表示该进程申请该资源，◯<—▢表示该资源分配给该进程。

-2- 当资源配图中每个资源只有一个，且出现环路时，表明该组进程处于死锁状态。

-3- 死锁定理：先找出一个既不阻塞又不独立的进程节点。在顺利的进程下，该进程顺利完成，释放资源，使之成为独立节点。重复上述过程化简资源分配图，如果最后能让资源分配图完全简化，则成为可完全简化，否则成为不可完全简化。若该图不可完全简化，则是死锁状态。

②：死锁解出算法

-1- 抢占资源

-2- 终止或撤销进程：终止所有进程 和 逐个终止进程。