分类： 第6章 处理器调度及死锁

单种资源的银行家算法

问题：研究一个银行家如何将其总数一定的现金，安全地借给若干个顾客，使这些顾客既能满足对资金的要求又能完成其交易，也使银行家可以收回自己的全部现金不至于破产。
操作系统在若干个并行进程间分配单位数量一定的某共享资源就是这样一个问题，既要使每个进程均能满足其对资源的要求，使之完成其运行任务，同时又要使整个系统不会产生死锁。
假如银行家能使他当前的全部顾客在有限的时间内完成他们的交易（也归还了他们的借款），那么当前的状态是安全的，反之状态就是不安全的。

多种资源的银行家算法

定义两个向量和两个矩阵：
 系统资源向量：表示系统中拥有每类资源的数量；
 系统当前可用资源向量：表示系统中尚未分给进程的每类资源的数量；
 各进程当前对资源的请求矩阵；
 当前资源分配矩阵。

即，如果将所有已被指派的资源j的数量和所有可供使用的资源数相加，结果就获得该类资源的总数。

死锁模型—有向图

可通过画有向图来判断是否发生了死锁

从死锁恢复

剥夺法恢复
 将某一资源从一个进程强占过来给另一个进程使用，并在不影响原进程执行的情况下返回，这种作法取决于该资源的特性；
 用这种方法恢复通常比较困难或者说不太可能，因为选择中止某进程很大程度上取决于哪一类资源比较容易被收回；

回退法恢复
 系统设计人员以及主机操作员周期性地对进程进行检查，在检查点将进程的状态写入文件以备重启，文件中不仅包括内存图象，还包括了资源状态，既哪些资源对应哪些进程；
 一旦检测到死锁，恢复时，进程会回滚到较早的检查点，该检查点后做的所有工作都丢失了；

杀死进程来恢复
 杀掉环中的一个进程；
 将一个环外的进程作为牺牲品放入环中以释放被死锁的资源。

防止死锁的发生

防止死锁的发生，根本办法是使必要条件之一（或多个条件）永不存在，即破坏其必要条件使之永不成立，如果有一条或若干条不具备，那么死锁就不会产生；
 破坏互斥条件，允许多个进程同时访问资源；（但不太实际）
 破坏不可抢占条件，强迫进程暂时把资源释放出来给其他进程；（考虑到资源在进程间转移的开销和对资源的有效利用，必须小心地控制破坏该条件）
 破坏部分分配条件；
 破坏循环等待条件。

预先静态分配法

是针对部分分配条件的策略；
在进程开始运行前，一次分配给其所需的全部资源，若系统不能满足，则进程阻塞，直到系统满足其要求；
将导致严重的资源浪费；
改进策略：把程序分成几个相对独立的“程序步”来运行，并且资源分配以程序步为单位来进行，而不以整个进程为单位来静态地分配资源；
可以得到较好的资源利用率，减少资源浪费，但增加了应用系统的设计和执行的开销；
而且，为满足一个进程所需的全部资源，要逐渐积累，造成资源的浪费。

有序资源使用法

针对循环等待条件的；
系统设计者把系统中所有资源类都分给一个唯一的序号，并且要求每个进程均应严格按照递增的次序请求资源；
这样，系统中不可能形成几个进程对资源的环行请求链，破坏了循环等待条件；
把各进程经常用到的、比较普通的资源安排成低序号，而把比较贵重或稀少的资源安排成高序号，可能使最有价值的资源的利用率大为提高，但也有可能造成低序号资源的空闲等待浪费现象；
存在的问题：
 各类设备的资源序号一经安排，不宜经常地随意加以改动，至少应该维持一个较长的时期，在此期间，若要添置一些新设备，就必须重新改写已经存在的程序和系统；
 资源序号的安排要反映大多数进程实际使用资源的正常顺序，对于与此序号相匹配的进程，资源能得到有效利用，否则，资源浪费现象虽然有所改善，但仍然存在。

死锁：在系统中的一组进程，由于竞争系统资源或由于彼此通信而永远阻塞，称
这些进程处于死锁状态；

资源

资源：分可抢占资源和不可抢占资源
可抢占资源是指虽然资源占有者进程任然需要使用该资源，但另一个进程却可以强行把资源从占有者进程处抢过来，归自己使用
不可抢占资源是指除非资源占有者进程不再需要使用该资源而主动释放资源，否则其他进程不得在占有进程使用资源的过程中强行抢占
一个资源是否属于可抢占的资源，完全依赖于资源的属性
CPU、主存属于可抢占资源
打印机、读卡器等资源属于不可抢占资源

死锁的必要条件

互斥条件：一个资源一次只能被一个进程所使用；
不可抢占条件：一个资源仅能被占有它的进程所释放，而不能被别的进程强行抢占；
请求又保持（部分分配）条件：一个进程已占有了分给它的资源，但仍然要求其他资源；
循环等待条件：在系统中存在一个由若干进程形成的环形请求链，其中的每一个进程均占有若干种资源中的某一种，同时每一个进程还要求（链上）下一个进程所占有的资源。

调度的层次

长期调度（又称作业调度）：主要功能是按照某种原则从磁盘某些盘区的作业队列和交互作业中选取作业进入主存，并为作业做好运行前的准备工作和作业完成后的善后工作。
中期调度：决定哪些进程被允许参与竞争处理器资源；
主要起到短期调整系统负荷的作用，以平顺系统的操作。
短期调度（又称处理器调度）：主要功能是按照某种原则将处理器分配给就绪进程或线程。

作业状态

作业在每一阶段中所处的状况称为作业的状态；
系统中的作业通常分为四种状态：
 提交状态（动态的，作业录入，提交给系统）
 后备状态（静态的，提交完成）
 运行状态（动态的，从后备队列挑选运行）
 完成状态（静态的，运行完成后）

作业状态及其转换

作业的调度

按照某种调度算法从后备队列中挑选作业进入主存中运行
作业调度程序
作业调度程序要完成以下工作：
 按照某种调度算法从后备作业队列中挑选作业；
 为选中的作业分配主存和外设资源；（前期准备工作）
 为选中的作业建立相应的进程；（前期准备工作）
 构造和填写作业运行时所需的有关表格；（前期准备工作）
 作业结束时完成该作业的善后处理工作，如收回资源，输出必要的信息，撤消该作业的全部进程和作业控制块。
通常在一个作业完成或处理器空闲时调入一个或多个作业。

作业控制块（ JCB ）

• 作业名：由用户提供，经系统登记在JCB中；
• 估计执行时间：指作业完成计算所需的时间，由用户根据经验估计的；
• 最迟完成时间：用户要求完成该作业的截止时间；
• 要求的主存量：该作业执行时所需占用的主存数量；
• 外设类型及台数：指作业执行时所需的外设类型及每类设备的台数；
• 要求的文件量和输出量：指本作业将存储在文件空间的文件信息总量，和将输出数据的总量；
• 进入系统时间：该作业的全部信息进入主存，其状态转变为后备状态的时间；
• 开始执行时间：该作业被作业调度程序选中，其状态由后备状态转变为执行状态的时间；
• 主存地址：指分配给该作业的主存区开始地址；
• 外设台号：分配给该作业的外设实际台号；
• 控制方式：有联机和脱机两种；
• 作业类型：指系统根据作业运行特性所规定的类型，可分三类：占CPU时间偏多的作业、I/O量偏大的作业以及使用CPU和I/O比较均衡的作业；
• 优先级：反映这个作业运行的紧急程度，可由用户自己指定，也可由系统根据作业类型、要求的资源、要求的运行时间与系统当前状况动态地给定；
• 状态：指本作业当前所处的状态，它可为后备状态、执行状态或完成状态中的任一种状态。
• 作业运行结束后，在释放了该作业所使用的全部资源后，作业调度程序调用存储管理程序，收回该作业的JCB空间，从而撤消了该作业。

单机系统的处理器调度

调度算法
先进先出调度算法
优先级调度算法——非抢占的、可抢占的
时间片轮转算法
最短进程优先调度算法
最短剩余时间优先调度算法
最高响应比优先调度算法
多级反馈队列调度算法

#假设处理完前处理器资源不会被剥夺 #假设单处理器

调度性能的衡量

通常采用平均周转时间和平均带权周转时间来衡量作业调度算法性能的好坏
周转时间：从作业提交完成到完成所经历的事件（运行时间+等待时间）
带权周转时间：周转时间除以执行时间

先进先出调度算法

按作业来到的先后次序进行调度，优先考虑在系统中等待时间最长的作业，而不管它要求执行时间的长短；
算法容易实现，但效率较低
对短作业不利，因为短作业执行时间很短，若令它等待较长时间，则带权周转时间会很高。

最短作业优先调度算法

按作业执行时间长短调度，优先考虑作业预期执行之间的长短
对先来的长作业不利

最高响应比优先调度算法

先进先出调度算法只考虑作业的等候时间而忽略了作业的执行时间；
最短作业优先调度算法只考虑用户估计的作业执行时间而忽略了作业的等待时间；
最高响应比优先调度算法是介于上述两算法之间的一种折衷算法，既照顾了短作业，又不使长作业的等待时间过长。