第三章处理机调度与死锁本章重点3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.1处理机调度的基本概念3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法3.2调度算法例：有5个进程P1,P2,P3,P4,P5,他们依次进入就绪队列(时间差距忽略不计）,他们的优先数(优先数值小的优先级高)和需要的处理器时间如下表所示：忽略进行调度等待所花费的时间，请回答下列问题：1、写出分别采用先来先服务和非抢占式的优先数调度算法选中进程执行的次序。2、分别计算两种算法使各进程在就绪队列中的等待时间以及平均等待时间。3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件3.3产生死锁的原因和必要条件五、处理死锁的方法预防死锁。通过设置某些限制条件，去破坏产生死锁的四个必要条件中的一个或几个条件，来防止发生死锁。避免死锁。是在资源的动态分配过程中，用某种方法去防止系统进入不安全状态，从而避免发生死锁。检测死锁。允许死锁发生，通过设置检测机构，及时检测出死锁的发生。解除死锁检测出死锁的发生，然后采取适当措施解除死锁。不太可能避免死锁，因为有些进程无法事先提供最大资源需求量。因产生死锁须四个必要条件。若能破坏其中的一个或几个条件，则死锁不发生。一、预防死锁(1)破坏互斥条件资源的互斥使用条件是由资源本身的性质决定的，因此不能破坏。但如果采用spooling技术，就可以将一台独享设备改造成多台设备，满足多个进程的需求，可预防死锁。实际中，不是所有设备都能采用spooling技术的。即使采用spooling技术，由于多个进程竞争磁盘空间，磁盘空间的不足，仍可能导致死锁。(2)破坏保持和请求条件让进程在开始运行前，必须获得其所需的全部资源。若系统不能满足，则该进程等待。然而，许多进程在开始运行之前，不能精确提出所用资源数量。如果它能提出，那么就可以采用银行家算法避免死锁了。(3)破坏非剥夺条件当一个进程已占有某些资源，又申请新的资源而不能立即得到满足时，则在进入阻塞状态前强行使其释放已经占有的资源。以后运行时，再重新申请。这个办法显然也不行，因为保护进程放弃资源时的现场以及之后的恢复现场，系统要付出很高的代价。(4)破坏环路等待条件将系统全部资源按类进行全局编号排序。进程对资源的请求必须按照资源的序号（递增或递减顺序）申请，这样，在资源分配图中就不会出现环路，使进程一直运行，而不出现死锁。[例]系统拥有资源为：输入机=1，打印机=2，绘图机=3，磁带机=4，光盘=5。系统有两个进程A和B。所有进程对资源的请求必须严格按序号递增顺序进行。如果A请求到资源j，B请求到资源i。若i>j，允许A请求B占有的资源i，但绝不允许B请求A占有的资源j，故进程资源图绝不会形成环路。但找到能满足所有进程要求的资源编号不可能。到目前为止，还没有一个有效办法来预防死锁。3.4预防死锁的方法三、利用银行家算法(Banker′sAlgorithm)避免死锁最具代表性的避免死锁的算法是Dijkstra的银行家算法，是在1965年提出的。这是由于该算法能用于银行系统现金贷款的发放而得名。这个算法正是利用了前面介绍的避免进程进入不安全区的原理。[例]银行家算法是用来模拟一个小城镇的银行家为一批顾客贷款的问题。有四个顾客：A，B，C，D，每个顾客提出的最大贷款数量分别为6、5、4、7(以千美元为单位)。银行家知道不是所有顾客都马上需要其全部贷款（22）。因此，他只保留10个单位数量(而不是全部22个单位)为这些顾客服务。在这个模型中，顾客是进程，资源单位是磁带驱动，而银行家就是操作系统。如图3.3所示。3.4预防死锁的方法银行家算法：Available：可用资源向量。一个含有m个元素的数组，每个元素代表一类资源可用的数目。Max：最大需求矩阵。n×m矩阵，Max(i,j)=k表示进程i需要j类资源最大数目为k。Allocation：分配矩阵。n×m矩阵，Allocation(i,j)=k表示进程i当前已分得j类资源数目为k。Need：需求矩阵。n×m矩阵，Need(i,j)=k表示进程i还需要j类资源k个