基于银行家算法的分布式互斥请求集生成算法研究

作     者：林岚 

作者单位：内蒙古农业大学 

学位级别：硕士

导师姓名：李美安

授予年度：2012年

学科分类：08[工学] 081202[工学-计算机软件与理论] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：分布式 互斥 请求集 银行家算法 剩余长度 

摘      要：分布式互斥系统的效率极大程度上取决于生成请求集的效率,目前的请求集生成算法已经将请求集长度降到最低,但是时间复杂度过高;如果想要获得快捷的生成效果,又需增加请求集长度。所以设计出一种集最优长度和较优时间复杂度为一体的请求集生成算法成为目前亟待解决的问题。 本文详细分析分布式互斥算法的研究背景和发展历程。在此基础上,重点探讨分布式互斥系统的特征、请求集序列对于系统的重大意义。同时也对比介绍原有请求集生成算法的优缺点,针对其时间复杂度和空间复杂度不可兼得的状况提出一种新型的请求集生成方案。 本文的重点内容和创新点有以下几个方面： 1、建立分布式互斥请求集生成算法的数学模型,通过比对现有的请求集算法的特点,确定了一个优秀的请求集该具有的标准,明确了研究方向。 2、分析银行家算法和请求集生成算法的理念的相似之处。将银行家算法为避免死锁,获取安全进程序列的递归思想,借鉴到请求集生成算法中。增设一个请求集剩余长度的变量,以该变量及节点状态数组作为边界条件,可以确定申请进入请求集节点的合法性。该算法能获得最优请求集长度,其时间复杂度远远小于同样具有最优请求集长度的LUK算法。 3、提出一种动态确定请求集初始化节点数与初始化位置的局部递归的请求集生成算法。它通过增加初始化节点数量,可以减少在计算请求集时需要寻找的节点数量的方式,以达到降低生成请求集的时间复杂度的目的,理论上能将算法的时间复杂度降低到N(?)/6+N/2+(?)/3。本文还采用局部递归的方式来保证在降低请求集生成算法的时间复杂度时请求集长度不显著增加,从而使得本文提出的算法所生成的请求集与LUK算法生成的请求集长度基本相同。