《数学建模论文图书馆节点分配问题.doc》由会员分享，可在线阅读，更多相关《数学建模论文图书馆节点分配问题.doc（16页珍藏版）》请在三一办公上搜索。
1、少数民族数字图书馆信息资源节点的优化分配摘要 本论文针对西北民族大学少数民族数字图书馆图书信息资源访问时出现的信息资源资源分配节点的问题，建立了两个模型，模型一当有资源单位访问量大于当前节点数时，我们从资源空闲度最高的资源单位中抽取一个空余节点出来，采用公平席位分配模型的思想，利用Q值法将该接点分配给需要性最大的单位，实现按需分配，最优利用资源，最大化实现按需分配；模型二通过将资源综合调配和调度，借鉴内存分区存储管理的思想，对待分配空余节点总和进行内部节点数等差数列规律分区，对满访问单位资源所需节点数和各区内空余节点数进行比较性匹配，将数量最匹配的区供给给满访问单位资源；其中模型一能够最大化实
2、现按需分配，达到最优利用节点资源，但是因为每次只能对一个待分配节点进行分配，不能并行进行，因此时间利用性较差；模型二则相反，因为使用最接近所需节点数整区供给，所以加快了调配速度，但是不能实现最大化按需分配，所以并不是对资源的最优利用。其次,根据我们建立的模型,我们用VC+设计用户对图书信息资源访问的计算机模拟程序,达到数学、计算机和实际相结合的目的。关键字：公平席位，Q值法，分区，按需分配，最优。问题重述为了提高少数民族群众的科技文化素质，推动少数民族地区的社会经济发展，为东西部地区经济、文化、科技、教育交流搭建桥梁，近几年来，我校充分发挥智力优势，积极承担国家重大科研课题，致力于研究和开发少
3、数民族数字图书馆，搭建西部地区信息知识的平台，并提供相应的知识、信息服务。但在研究和建设过程中也遇到了一系列困难，如下即是经简化和提炼的一个问题：假设西北民族大学少数民族数字图书馆图书信息资源为N，西北民族大学网络中心给每单位图书信息资源资源分配节点为n，若访问第i个图书信息资源Ai的用户大于n时，该资源就无法访问，但其他图书资源用户访问量有可能小于n，这就提出了节点优化利用问题：1、试设计一个便于操作的信息资源节点的分配方案，将访问量小于n的剩余节点有效分配给Ai资源，以达到资源优化利用的目的。2、将这个节点分配问题抽象成一个明确、完整的数学模型，并给出求解模型的方法。3、设计用户对图书信息
4、资源访问的计算机模拟算法，通过不同模拟结果的比较指出你们构建的模型的优缺点。问题分析当前资源分配系统存在的问题是其他单位的空余节点不能被当前需要空余节点的单位资源利用，因此，我们的模型所要做的就是 1如何使得其他单位资源的空余节点可被利用 2 如何有效而优化的调配和使用资源，实现资源利用的最大化和浪费的最小化。1如何利用空余节点资源，我们可以使用两种方式，一种则保持原来节点状态，然后通过相关计算和分析，用最划算和合理地方式选择空余节点来源单位，供给给需要节点的单位；另一种则打破节点分配原状态，将所有空余节点资源综合起来进行调配和调度，再通过计算和分析，实现空余节点利用。2如何有效而优化的调配和
5、使用资源，实现资源利用的最大化和浪费的最小化。则有两方面需要考虑：1反应效率，即时间复杂度。2方便操作。为了满足以上两方面的要求，我们讨论出两种方法。一种则计算出各单位的资源空闲度和资源需要度，将资源空闲度最大单位的空余节点分配给资源需要度最大的单位，但鉴于该分配算法的局限性，每次只能取出一个节点进行分配；另一种方法就应该克服每次只用一个节点的限制，将所有空余节点资源进行分区调度，按照相关节点所需节点数目匹配性，整区供给。理论上可以克服前一种方法的低效性，但是会出现空余节点资源一定程度的浪费而不能实现资源最合理最优化的调度和利用。模型假设1）西北民族大学各图书信息资源在访问和使用节点方面不存在
6、不同。2）总存在空余节点，不会出现访问量超过总结点的情况。3）在一段时间内各资源的访问量波动不大。4）所有空余节点视作属性相同。模型建立及求解模型一字符定义：1）图书信息资源为N；2）每单位图书信息资源资源初始分配节点都为n；3）第i个图书信息资源Ai；4 ）Ai,Aj的访问量为,；5） Ai，Aj的节点数为，；6） Ai空余节点数为7） 某一时刻满访问Ai,Aj单位所需节点数为Xi(即-)，Xj(即-)；8） 设置每个单位的资源空闲度为Zi9）当前处于满访问状态的单位数m模型建立及求解：模型一当有资源单位访问量大于当前节点数时，我们即通过计算得出资源空闲度最高的资源单位，从中抽取一个空余节点
7、出来，采用公平席位分配模型的思想假设，利用Q值法计算出应该分配给哪个资源单位最公平，即哪个资源单位的需要性最大。将待分配节点分配给该资源单位。以此类推。1计算出资源空闲度最大的单位来抽取一个节点 资源单位数为N，Ai访问量为，当前节点数为，则Ai空余节点数：=-则Ai的资源空闲度Zi=该单位空余节点数/该单位访问量=（1）由（1）式我们可以知道Zi的值越大，该单位的空闲资源度越高，则我们应该从该单位取出空余节点来分配。2 选取资源需要度最大的单位进行节点分配（1）Q值法对于两变量一代分别配资源情况先分析Q值法对两变量Ai, Aj公平分配的过程：若 则定义（，）=为对Ai的相对不公平度若，即对A
8、i不公平。抽象假设从W中取出一个节点对多个满访问需要空余节点的单位进行分配，关于（i=1、2m）的不等式可能有以下三种情况：1 ，这说明即使将这一个节点分配给Ai，仍然对Ai不公平，所以这一个节点显然应该给Ai。2 ，说明当Aj增加一个节点时将对Ai不公平，可算出Ai的不公平度为（，+1）=-1（2）4 不可能出现。因为按需分配的原则是使得相对不公平度尽可能的小，所以如果（+1，）（，+1）（3）则这一个节点应该分配给Ai，反之则应该给Aj。由（1）（2）式可得（3）式等价于不难证明情况1也会导致（3）式，所以结论是：当（3）式成立时这一个节点应该分配给Ai，反之给Aj。记=（i=1,2m）,
9、待分配的一个节点应该给Q值最大的一方。（2）Q值法推广到多变量一待分配资源的情况以上方法推广到m方按需非配节点的情况，Ai所需节点数为，已有节点数，i=1,2m,则分配某个节点时计算=（i=1,2m）应给Q值较大的一方。模型二字符定义：1 信息资源为N2 每单位初始信息资源分配节点为n3 当前第i个图书信息资源Ai的访问量为4 每个资源的当前空余节点数为5总的空余节点数为W6 第i个区内节点数为Ci7 Ai资源所需空余节点数为Xi8 W中总区数为R9 分区中等差数列首项为常数=1(因为Xi可能出现的最小数为1)10总的需要节点总数X模型建立首先统计所有空余节点得到总和，所有的空余节点组成一个整
10、体。此时所有的信息资源都处于待分配节点状态。然后将所有空余节点所组成的大区按照等差数列划分成n区，根据资源所需要的节点数与区内部节点数进行比较，然后选取合适的区（区的大小大于或等于资源所需节点数）分配给资源，若此区大于所需要信息资源节点数则将多余出来的空余结点分割出来以待回收重新放入整体。然后再按照同样的方法将剩余节点数分配给下个所需要信息资源结点的资源。1)：计算空余节点总数资源单位数为N，Ai访问量为，当前节点数为则Ai空余节点数：=-则W=+= = 2）：按照等差数列规律对W进行分区W=+（R1）d (0d=, 1=RXi 且满足在所有内部节点数大于Xi的区中Ci-Xi的差为最小。则将i
11、区节点供给给Ai。CiXi =+Ci可能出现的情况：1一般性假设第j区为所有区中内部节点数最多的区,若CjXj，则将第j区节点供给给Ai。进行下一轮匹配检验。2 若出现两个资源同时跟某一区节点数完全匹配，由于同一资源不能被多个事件占用，所以这属于资源抢占问题。具体解法可以利用计算机进程管理中的互斥事件的加锁实现方法来解决。计算机模拟算法分析和评价模型一的计算机模拟实现：循环适应分配算法#include#include#include#define Source_Num 100 /资源数为100typedef struct int size; /每个资源的空余节点数 int flag; /节点的
12、状态node;node FQSource_Num;void fq_creat()/初始化节点的各个分区的信息 int a; for(int i=0;iai; /各资源空余节点数for(int i=0;iSource_Num;i+) FQi.size=ai; FQi.flag=1; void koxi_xuqiu(node FQ,j,k) /求出最大资源空闲度和最大需求度 int I,max,j,max1,k; int BiSource_Num,Zi,XiSource_Num,Qi; for(i=0;iBii; for(i=0;i Source_Num;i+) Zii=FQi.size/Bni;
13、 for(i=1;i Source_Num;i+) /求出资源最大空闲度的单位 max=Zi0; if(maxZii) max=Zii; j=i; for(i=0;iXii; for(i=0;i Source_Num;i+) Qii=Xii2/(Bii+FQi.size)*( Bii+FQi.size+1); for(i=1;i Source_Num;i+) /求出资源最大需求度的单位 max1=Qi0; if(max1Qii) max1=Qii; k=i; void xunhuan_fp(node FQ ) cout 你选择了循环适应分配算法endl; inti,j,k; koxi_xuqi
14、u(node FQ,j,k); for(i=0;ik;i+) FQj.size-; cout”空余节点分配成功!”;模型二的计算机模拟算法实现最先适应算法#include#include#include#define Source_Num 100 /图书信息资源数为100typedef struct int size; /每个资源的所需空余节点数 int flag; /节点的状态node;node FQSource_Num;void fq_creat()/初始化节点的各个分区的信息 int a; for(int i=0;iai; /各资源所需节点数for(int i=0;iSource_Num
15、;i+) FQi.size=ai; FQi.flag=1; void first_fp(node FQk) cout 你选择了最先适应分配算法endl; int i,j;Syjd; int An0=1; for(i=1;i100;i+) /空余节点区分块，每块大小为AniAni=2*i+1; for(j=0;j=i;j+) if(Anj信息节点分配失败，请稍等系统响应; else if(Anj=FQk.size)/当所有的内存大小等于于进程所需的空间大小时，开始分配节点 Anj=0;FQk.size=0;cout空余节点分配成功!endl; else Syjd=Anj-FQk; Anj=0;
16、FQk.size=0; cout空余节点分配成功! 还剩余Syjd个节点endl; 菜单函数void menu() coutnnnendl; coutttt+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*+*nendl; coutttt+ 图书馆资源信息空余节点分配系统 |nendl; coutttt-n); coutttt+ 1-循环适应分配算法 |nendl; coutttt+ 2-最先适应分配算法 |nendl; coutttt+*|nendl; coutttt-n);主函数：void main()int choice;struct node FQ;fq_creat(); f
17、or(; ; ) Menu(); scanf(%d, &choice); switch(choice) case 1:xunhuan_fp();break; case 2:first_fp();break; default:exit(0); while(choice!=0);计算机模拟算法的效率度量我们可以算出每个算法的时间复杂度和空间复杂度来评价算法的优劣。时间复杂度：一般情况下，算法的基本操作重复执行的次数是问题规模n的某个函数f(n),算法的时间量度记作 T(n)=O(f(n)。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同。n为频度，即执行重复最高次数。空间复杂度
18、：作为算法所需存储空间的量度，记作S(n)=O(f(n)。其中n为问题规模（或大小）。一个上机执行的程序除了要存储空间来寄存本身所用的指令、常数、变量和输入数据以外，也需要一些对数据进行操作的单元和存储一些为实现计算所需信息的辅助空间。通过我们的计算可知： 、故得出以下结论：模型二优于模型一。模型评价对于模型一是通过计算出各单位的资源空闲度和资源需要度，将资源空闲度最大单位的空余节点分配给资源需要度最大的单位，并且采用公平席位分配模型的思想，利用Q值法将该接点分配给需要性最大的单位，实现按需分配，最优利用资源，最大化实现按需分配；但鉴于分配算法的局限性，每次只能取出一个节点进行分配。这样一来就
19、会延长对资源分配空余节点的时间，系统不能及时的响应用户对资源访问的请求，从而导致了用户等待时间的增加。模型二通过将资源综合调配和调度，借鉴内存分区存储管理的思想，对待分配空余节点总和进行内部节点数等差数列规律分区，对满访问单位资源所需节点数和各区内空余节点数进行比较后找出最匹配供给给满访问单位。因为使用最接近所需节点数整区供给，提高了空余节点分配的速度。系统可以及时的响应用户对资源访问的请求，缩短了用户等待的时间。但是由于分配的空余节点数与请求访问的节点数不一定完全匹配，所以在对空余节点分区上仍存在一定程度的问题。为了实现最大程度上的提高空余节点的分配效率和利用率，可以进行如下改进，即采用对空
20、余节点的动态分区方法：任然将所有空余节点进行综合分配而不预先固定分区，而是按照每个信息资源的实际用户访问量来划分的。该方法能够极大地缩短空余节点的分配时间和用户访问资源的等待时间，还能匹配各个资源的用户请求访问量。然而，模型的真正实现还需要一系列的节点分配和回收控制机制，用户访问资源请求空余节点机制，系统响应机制等等。我们在此不作赘述。参考文献【1】数学模型第三版，姜启源，谢金星，叶俊编。【高等教育出版社】；【2】计算机操作系统教程第三版，张尧学，史美林，张高编。【清华大学出版社】【3】数据结构(C语言版)，严蔚敏，吴伟民。【清华大学出版社】【4】数学建模及典型案例分析,李志林，北京：【化学工业出版社】,2006.【5】【6】http：/数学建模网附录一在模型二中对所有剩余节点组成整体和分区的实现。将节点已分配状态设定为1，将未分配节点状态设为0，如表（一）所示。再将所有节点状态为0的节点组成一个整体后进行分区，即一定数量的剩余节点拥有相同区号，由此制成节点可用表，如表（二）所示。用户访问资源的请求空余节点表如表（三）。表（一）资源状态节点1101020101310010n0110表（二）区号分区大小状态位 0 01020i0n0表（三）资源号请求空余节点数状态 已分配 已分配 已分配
