有序资源分配法

第五章资源分配与调度（一）资源管理功能（二）资源分配的机构和策略（三）死锁概念（一）资源管理功能一.资源管理功能1.目的：保证资源的高利用率；在“合理”时间内使所有顾客有获得所需资源的机会；对不可共享的资源实施互斥使用；防止由资源分配不当而引起的死锁。2.资源管理的任务：资源管理的描述－－数据结构确定资源的分配原则（调度原则）执行资源分配（实施）存取控制和安全保护二.资源的静态分配和动态分配1.资源的静态分配系统对作业一级采用资源静态分配方法。当一个进程（或程序）运行前，将它要求的资源一次分配给该进程，直到该进程终止，释放其占用的所有资源。效率太低2.资源的动态分配系统对进程一级采用资源动态分配方法。系统在进程运行中，根据进程提出的资源需求，进行资源的动态分配和回收。资源利用率提高，但有可能造成死锁（二）资源分配的机构和策略一.资源分配机构1.资源描述器（1）什么是资源描述器描述各类资源的最小分配单位的数据结构称为资源描述器rd（resourcedescriptor）。如：主存的最小分配单位：在分页分配中——主存页面磁盘的最小分配单位：磁盘面中的一个扇区（2）资源描述器的内容资源名资源类型最小分配单位的大小最小分配单位的地址分配标志描述器链接信息存取权限密级最后一次存取时间记帐信息2.资源信息块（1）什么是资源信息块描述某类资源的请求者、可用资源情况和该类资源分配程序等必要信息的数据结构。（2）资源信息块的内容（3）中央处理机资源信息块二.资源分配策略1.先请求先服务（FIFO策略）排序原则：按请求的先后次序排序。每个新产生的请求均排在队尾，而当资源可用时，资源分配程序从队列中选取第一个请求，并满足其需要。适用范围：系统中的一切资源。优点：简单、系统开销小。缺点：有时显得不合理，系统无法进行干预。2.优先调度在优先调度策略下，对于每一个进程（或作业）要指定一个优先级，优先级反映了进程要求处理的紧迫程度。排序原则：按优先级的高低排序。每一个新产生的请求，按其优先级的高低插到相应的位置上。而当资源可用时，选取队列中第一个请求，并满足其需要。优先级的确定：主要由系统来确定，并可动态改变。使用范围：由于系统开销大，主要适用于系统中的紧缺资源。便于资源的动态分配。3、适应调度4、均衡调度5、针对设备特性的调度移臂调度旋转调度（三）死锁一.什么是死锁1.死锁的例子（1）设备共享进程PA、PB，共享一台打印机和一台磁带机时刻t1：进程PA——占用打印机进程PB——占用磁带机时刻t2：进程PA——又请求磁带机进程PB——又请求打印机问：以后会发生什么情况？（2）用信号灯的P、V操作描述死锁上例中，用信号灯的P、V操作表示资源的申请和释放。信号灯设置：S1：表示设备R1可用，初值为1S2：表示设备R2可用，初值为1讨论两种资源请求序列，哪种情况可能产生互相死等的局面。在这两个进程并发执行时，当P1进程占有R1、P2进程占用R2时，P1要求R2，由于P2已占R2有而得不到，P1进程只有等待；P2申请R1，由于P1已占有R1，而得不到，P2进程只有等待，就出现了死等的情况。2例2：三个进程共享使用一台打印机的程序若有一个进程少写了一个V操作。2.什么是死锁死锁简单的定义：死锁就是两个或两个以上的进程等候着一个永远不会发生的事件时所取的一种系统状态。教材上关于死锁的定义：两个或两个以上并发进程，如果每个进程持有某种资源，而又等待着别的进程释放它或它们现在保持着的资源，否则就不能向前推进。此时，每个进程都占用了一定的资源，但又都不能向前推进。这种现象称为死锁。二.死锁的起因和条件1.引起死锁的原因系统资源不足；进程推进顺序非法。2.死锁的图解3.产生死锁的四个必要条件：1.互斥条件2.不可剥夺条件3.部分分配4.环路条件三.死锁的预防和避免基本点：破坏死锁的某一个必要条件1.解决死锁问题的几个策略为了不发生死锁，必须设法破坏产生死锁的四个必要条件之一。条件2（不可剥夺条件）：容易否定，可制定相应的规则即可，例如，当一个进程（程序）申请某资源被拒绝，则必须释放已占用的资源，如需要再与其它所需资源一起申请。对CPU还可进行可剥夺分配。条件1（互斥条件）：难以否定，但可采用相应的技术，如利用假脱机技术，即用可共享使用的设备模拟非共享的设备；条件4（环路条件）：实际上系统不采用部分分配，也就破坏了环路条件。条件3（部分分配）：也是很容易否定的，只要分配策略上规定一个进程（或程序）一次将所需资源一次申请到位。用完后释放。可以全部用完后，统一释放，也可使用完后立即释放，只要是一次申请到的，系统就不会出现死锁。2.静态预防死锁的方法在作业调度时为选中的作业分配它所需的所有资源，当资源一旦分配给该作业，在其整个运行期间这些资源为它独占。讨论：（1）这种方法破坏了死锁的必要条件中的哪一条？（2）这种方法的资源利用率高不高？为什么？这种方法安全而简单的方法，但设备的使用效率太低。其缺点也是明显的：1.一个用户（进程）在程序运行之前艰难提出将要使用的全部设备；2.用户作业必须等待，直到所有资源满足时才能投入运行。3.设备（资源）的浪费太大，有些资源在进程运行过程中可能只有很少的时间才用到，有的甚至不会用到，例如，一个分支语句。3.动态避免死锁的方法为了提高设备的利用率，应采用动态的设备分配方法，但应设法避免发生死锁，若存在发生死锁的可能性，则拒绝分配。预防死锁：采用的分配策略本身就否定了产生死锁的四个必要条件之一，这就保证了不会发生死锁；死锁避免：是在动态分配资源的策略下采用某种算法来预防可能发生的死锁，从而拒绝可能产生死锁的某个资源的请求。系统中所有资源都按某种规则统一编号（例如打印机为1、磁带机为2、磁盘为3、等等），所有分配请求必须以上升的次序进行。当遵守上升次序的规则时，若资源可用，则预以分配；否则，请求者等待。系统要求申请进程：1.对它所必须使用的而且属于同一类的所有资源，必须一次申请完；2.在申请不同类资源时，必须按各类设备的编号依次申请。讨论：这种方法破坏了死锁的必要条件中的哪一条？为什么？（1）有序资源分配法例如：进程PA，使用资源的顺序是R1，R2；进程PB，使用资源的顺序是R2，R1；若采用动态分配有可能形成环路条件，造成死锁。采用有序资源分配法：R1的编号为1，R2的编号为2；PA：申请次序应是：R1，R2PB：申请次序应是：R1，R2这样就破坏了环路条件，避免了死锁的发生。（2）银行算法避免死锁算法中最有代表性的算法是DijkstraE.W于1968年提出的银行家算法：该算法需要检查申请者对资源的最大需求量，如果系统现存的各类资源可以满足申请者的请求，就满足申请者的请求。这样申请者就可很快完成其计算，然后释放它占用的资源，从而保证了系统中的所有进程都能完成，所以可避免死锁的发生。例子：假定系统有10个资源（为了说明问题的简单，不管它是什么资源），目前分配的情况如上表：此时，系统中只剩下2个资源，这时就要考察能满足哪个进程，不能满足P和R的最大要求，能满足Q，于是将剩下的2个资源分配给Q，Q就能完成，然后释放所占用的6个资源。可满足P，也可满足R，这时不论分给谁都能保证完成。第五章小结一.资源管理概念：任务、资源分配方式二.资源分配机制资源描述器资源信息块三.资源分配策略先请求先服务优先调度策略四.死锁1.定义、举例2.引起死锁的原因3.产生死锁的必要条件4.死锁的预防：资源静态分配5.死锁的避免：有序资源分配方法银行家算法