一、处理机调度的层次

概念

• 按什么原则分配CPU：调度算法。
• 何时分配CPU：调度时机。
• 如何分配CPU：调度过程。
• 周转时间：完成时间-进入时间。（注意：从进入系统到执行完成包括在后备队列中等待调度、在就绪队列中等待进程调度、执行以及等待I/O操作完成四部分时间，作业进入是指作业准备好被调度的状态）。
• 平均周转时间：周转时间/执行时间。
• 资源利用率：CPU有效工作时间/（CPU有效工作时间+CPU空闲等待时间）。

处理机调度的层次

  1、高级调度（作业调度）：调度对象是作业，主要功能：根据某种算法，决定将外存上处于后备队列中的哪几个作业调入内存，为它们创建进程、分配必要的资源，并将其放在就绪队列中。
  2、低级调度（进程调度）：调度对象是进程，主要功能：根据某种算法，决定就绪队列中哪个进程应获得处理机，并由分派程序将处理机分配给被选中的进程。（即分配哪个进程进入运行状态）
  3、中级调度（内存调度）：其主要目的是提高内存利用率和系统吞吐量。当一个进程暂时不能运行时，它被调至外存等待，此时该进程为挂起状态。当这个进程具备继续运行条件又稍有空闲时，由中级调度来决定，把外存上的那些已经具备运行条件的就绪进程重新调入内存，并修改其状态为就绪状态，挂在就绪队列上等待。

二、作业与作业调度

  作业：不仅包含通常的程序和数据，还应配有一份作业说明书，系统根据该说明书对程序的运行进行控制。在批处理系统中，是以作业为基本单位从外存调入内存的。

2.1 先来先服务（FCFS）调度算法

  就绪队列中最先进入队列的进程，先为之分配处理机运行，直至其结束或阻塞，将处理机分配给其他进程。有利于长作业，CPU繁忙型作业。可用于作业调度，也可用于进程调度。

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

  作业越短，优先级越高（注意：若一个进程已进入，而其他进程未进入，尽管未进入的进程作业更短，但仍先执行已进入的作业）。可用于作业调度，也可用于进程调度。

2.3 优先级调度算法（PSA）

  可用于作业调度，也可用于进程调度。作业调度：选择-创建进程-放入就绪队列。进程调度：选择-分配处理机。

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

  主要用于作业调度。每次计算所有符合被调度条件（已经进入）的作业的响应比（响应比=周转时间/处理时间），响应比高的先处理，然后再继续计算下一步中所有符合被调度条件的作业的响应比，直到所有作业被调度完毕。

2.5 时间片轮转调度算法

  主要用于进程调度，时间片大小需选择合适：太大退化为FCFS，太小切换频繁，用于运行时间太少。其举例具体实现过程如下：

2.6 多级队列调度算法

  主要用于进程调度。将就绪队列分成若干子队列，每个进程属于一个就绪队列，每个就绪队列采用一种调度算法。

2.7 多级反馈队列调度算法

  调度机制：

• 设置多个就绪队列，并为每一个就绪队列赋予不同的优先级，第一个队列优先级最高，依次降低。该算法为不同队列中的进程所赋予的执行时间片的大小也各不相同，在优先级越高的队列中，时间片越小。
• 每个队列都采用FCFS算法。新进程进入内存后，先将其放在第一个队列末尾，按FCFS算法等待调度，轮到该进程执行时，若它能在时间片内完成，便可撤离系统，否则将其转入第二个队列的末尾，等待调度，若在第二个队列中运行一个时间片后仍未完成，转入第三个队列，依次类推。当进程最后被降到第n队列后，在第n队列中便采取RR方式运行。
• 按队列优先级调度。仅当前面队列都空闲时，当前队列才能够执行。

三、死锁

3.1 死锁

3.1.1 死锁定义

  一组进程中，每个进程都无限等待被该组进程中另一进程所占有的资源，因而永远无法得到该资源，这种现象称为进程死锁，这一组进程就称为死锁进程。
  结论：

• 参与死锁的进程最少是两个。
• 参与死锁的进程至少两个已经占有资源。
• 参与死锁的所有进程都在等待资源。
• 参与死锁的进程是当前系统中所有进程的子集。

3.1.2 产生死锁的必要条件

• 互斥条件：涉及的资源是非共享的。
• 不可抢占条件（不可剥夺条件）：不能强行剥夺进程拥有的资源。
• 请求和保持条件：进程在等待一新资源时继续占有已分配的资源。
• 循环等待条件：存在一种进程的循环链，链中每一个进程已获得的资源同时被链中下一个进程请求。

3.1.3 处理死锁的方法

• 预防死锁：通过设置某些限制条件，去破坏死锁四个必要条件中的一个或多个，来防止死锁。
• 避免死锁：在资源动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免死锁的发生。
• 检测死锁
• 解除死锁：与检测死锁配套。

3.2 预防死锁

  互斥条件是非共享设备所必须的，不能改变

• 破坏不可剥夺条件：一个已拥有资源的进程，若它再提出新资源要求而不能立即得到满足时，必须释放已经拥有的所有资源。以后需要时再申请。
• 破坏请求和保持条件：系统要求所有进程一次性地申请在整个运行过程中所需的全部资源。若系统有足够资源则全部分配。
• 破坏循环等待条件：系统中的所有资源都有一个确定的唯一号码，所有分配请求必须以序号上升的次序进行。

3.3 避免死锁

  死锁避免定义：在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。
  安全状态：如果系统能按某种顺序（如P 4，P 1，·,Pn，称为安全序列）为每个进程分配其所需的资源，直至所有进程都能运行完成。称系统处于安全状态。若不存在这样一个安全序列称系统处于不安全状态。

银行家算法

1、数据结构

• 可利用资源向量Available。含有m个元素的数组，每一个元素代表一类可利用的资源数目。
• 最大需求矩阵MAX。n×m矩阵，定义系统中n个进程中的每一个进程对m类资源的最大需求。
• 分配矩阵Allocation。系统中每一类资源已分配给每一进程的资源数。
• 需求矩阵Need。每一个进程尚需要的各类资源数。
• Need[i,j]=Max[i,j]-Allocation[i,j]。

2、银行家算法

• 若Request i[j]<=Need[i,j]，继续检查；否则认为出错，请求大于需求。
• 若Request i[j]<=Available[i,j]，继续检查，否则，等待，资源不够。
• 试探分配给进程Pi:Available[i,j]-=Request i[j];Allocation[i,j]+=Request i[j];Need[i,j]-=Request i[j]。
• 系统执行安全性算法，若系统新状态是安全的，则分配完成，若系统新状态是不安全的，则恢复原状态，进程等待。

3、安全性算法

• 设置两个向量：可利用资源work，work=Available；标记进程是够结束Finish=false（还未释放）
• 从进程集合中选择满足条件的进程：1、Finish[i]=false；2、Need[i,j]<=work[j]；若不存在，转（4）。
• 执行Work[j]+=Allocation[i,j]；Finish[j]=true；go to step2。
• 若所有进程Finish[i]=true都满足，表示系统处于安全状态，否则，处于不安全状态。

4、银行家算法例子
  假定系统中有五个进程{P0,P1,P2,P3,P4}和三类资源{A,B,C}，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图所示。

  T0时刻的安全性：利用安全性算法对To时刻的资源分配情况进行分析（如图所示）可知，在To时刻存在着一个安全序列{P1,P3,P4,P2,P0}，故系统是安全的。

  将剩下的资源执行银行家算法，看是否处于安全状态。

3.4 死锁的检测与解除

  死锁检测：允许死锁发生，操作系统不断监视系统进展情况，判断死锁是否发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行。
  死锁解除：重要的是以最小的代价恢复系统的运行。方法如下：1、重新启动；2、撤消进程；3、剥夺资源；4、进程回退。
  用有向图描述进程的死锁。 系统由若干类资源构成，一类资源称为一个资源类；每个资源类中包含若干个同种资源，称为资源实例。二元组G=（V，E），V：结点集，分为P，R两部分，进程P={p1,p2,…,pn}，资源R={r1,r2,…,rm}，E：边的集合，其元素为有序二元组请求资源(pi,rj)或分配资源(rj,pi)。表示法：方框表示资源，圆圈表示进程，方框中的黑圆点表示资源实例。例如：

  死锁定理：如果资源分配图中没有环路，则系统中没有死锁，如果图中存在环路则系统中可能存在死锁。如果每个资源类中只包含一个资源实例，则环路是死锁存在的充分必要条件。
  资源分配图化简：

• 找一个非孤立进程结点且只有分配边，去掉分配边，将其变为孤立结点
• 再把相应的资源分配给一个等待该资源的进程，即将某进程的申请边变为分配边
• 重复以上步骤，若所有进程成为孤立结点，称该图是可完全简化的，否则称该图是不可完全简化的。

死锁状态的充分条件是：当且仅当资源分配图是不可完全简化的。