海量备份的优化BFD算法

兵工自动化软件技术O. I. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No, 4文章编号: 1006-1576 (2001) 04-0037-03海量备份的优化BFD算法韩祥兰，李东波，徐平，林海凡.(南京理工大学制造工程学院，江苏南京210094)摘要:在研究解决装箱问题的递降最佳适合算法(BFD算法)的基础上，提出了文档管理备份的优化BFD算法。同时，给出了包括文件队列、盘队列、备份队列、解队列、解空间、选出低维最优解、合成高维最优解在内的相应的运算步骤和流程图，对算法的优点和误差进行了分析。并举例加以说明。关健词: BFD算法;优化;队列中图分类号: TP301.6文献标识码: AThe Optimized BFD Algorithm of Mass Backup-fileHAN Xiang-lan, LI dong-bo, XU Ping, LIN Hai-fan(College of Manufacture Engineering, Nanjing University of Science & Technology, Nanjing 210094, China)Abstract: Based on the study of the optimal and descending algorithm (BFD algorithm) which is used toresolve the case question, the optimized BFD algorithm for mass backup-file in Document Management ispresented. At same time, file queue, disk queue, backup queue, result queue, result room, selecting the optimalsolution of low dimension and compound and the optimal solution of high dimension, and corresponding stepsand flow chart are introduced. The advantages and error about the algorithm are analyzed, and an example isgiven at last.Key Words: BFD algorithm; Optimize; Queue1 前言次序排序，然后对每一个货物，依次检查箱子的随着先进制造技术的深入推广和应用，企业空隙，如果哪个箱子放入此货物后的空隙最小，中越来越多的信息以电子图档和文档的形式存储就把此货物放入这个箱子中。在计算机中，故对各种文件进行定期备份就显得2.2存储容量问题十分重要。在江苏省CAD应用示范工程中实施如有n个文件须进行备份，其文件大小分PDM系统时，遇到了图文档文件备份的存储介别为F小、F2、...F。又有m张(盒)光盘或质容量优化问题，即如何按照文件的大小选择各磁带可用于备份，其剩余的空间大小分别为D.自的备份路径，使存储介质的容量达到最优的利D2、.、Dm。存储容量问题是说，采用何种文用效果。该问题与组合数学中的装箱问题类似,件分配方案使得光盘或磁带的利用效果最优。在分析研究了解决装箱问题的BFD算法后，提2.3两者的异同出了一个更加符合存储介质优化的BFD算法。上述分析可知，装箱和文件备份有很大的相2装箱问题与存储容量问题同之处，但也存在差异。相同之处在于这两个问2.1装箱问题题要解决的都是容量分配问题，实质是一个数值装箱问题说的是，大小不等的货物装入容量匹配问题。不同之处在于两个问题的优化方向,一致的箱子中，如何选择装箱方案使所须的箱子装箱问题的优化方向是箱子的使用数最少，而文数最少川。解决此类问题的方法一般采用FFD件备份问题却以备份剩余空间相对集中为最优。算法或BFD算法。这里介绍最常用的BFD算法，中于!YH中国煤化工得存储剩余空间集即递降最佳适合算法。该算法首先将货物按递降CNMHG为最优。收稿日期: 200-11-14; 修回日期: 2001-05-22作者简介:韩祥兰(1976-), 女。辽宁人，1999 年获南京理工大学学士学位，现南京理工大学在读硕士研究生，从事先进制造技术及PDM研究.37●兵工自动化软件技术0. 1. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No.4例1:唯- -解。现有3个文件F、F2、 F,光盘D、D,，剩余空间都为40。现有2种分配大小分别是10、20、30(单位忽略)，又有2张.方案，如图1.F,(30)F:(20)剩余空间F (30)F(10)1F1 (10)2F2(20)方案A方案B图1唯一解方案示意图 .方案A的2张盘剩余空间都是10，下次存例2:多种解。现有3个文件F、F2、 Fj、储时虽然可以存储2个大小不超过10 的文件, .Fs， 大小分别是10、10、20、30 (单位忽略)，但对于一个大小超过10的文件就必须启用新又有2张光盘D、D,，, 剩余空间都为40.现有盘。而方案B在下次存储时不仅可以存储2个3种分配方案，如图2。大小不超过10 的文件，而且可以存储一个大小3种情况空间利用效果相同，这时需要选择超过10 而不超过20的文件，所以方案B的空其中一种方案作为最终解决方案。根据企业要间利用效果更加优化。求，本算法采取动态交互方式加以选择。F(20) .F4 (30)Fz (10)FA (30)剩氽空饲Fj (20)剩汆空间F3(20)0F2(10)10F (10)方案C图2多种解方 案示意图3优化BFD算法文件队列，并分别标识序号为1、2、3、4.....接着定义文件队列尾为LOF (last of file)。3.1 有关定义(2)将所有光盘按剩余空间大小递升排序,先给出如下定义:组成盘队列。文件队列:所有没有备份路径的文件序列号(3)选择盘队列中的第1张光盘D, (i=1),的队列。初始时所有文件都在此队列中，且按并初始化变量。大小递降排序，随着算法的进行某些文件可能会(4)处理2种特例。第1种情况为所选光盘被分配备份路径而离开此队列。剩余空间小于文件队列尾LOF的大小，这样就盘队列:所有可用于备份文件的光盘序列号必须换下一.张光盘或增加新盘D, (i=i+1), 重复的队列，初始时按递升排序。步骤(4);第2种情况是文件队列中所有文件大备份队列:某张光盘所存储文件序列号的临小之和小于所选光盘剩余空间，这样可以直接生时队列。成高维最优解即将文件队列中的所有文件存入这解队列:某张光盘所存储的文件序列号的队张光盘，结束算法。列。在算法中该队列以二维数组Res(p,q)的形(5)如果没有出现上述的2种特例，那么选式出现，其中p表示解队列号，q表示队列位置。取文件队列中的第1个文件Fk (k=1)。解空间:某张光盘所有解队列的集合。(6)判断当前所选文件F,是否可以存入所选低维最优解:某张光盘的解空间中最符合优光盘D,如果可以存入则转执行(10);反之则此化方向的解队列。文件不入队，执行下一步。高维最优解:所有光盘低维最优解的集合。是则中国煤化工否为LOF,如果不YHCN MH G文件F (k=k+1),3.2运算步骤返回(6)执行;如果是LOF则说明文件队列已经优化BFD算法的运算步骤为:比较完毕，执行下一步。(1)将需要备份的文件按大小递降排序组成(8)记录这组备份队列为解队列，并将解队38.兵工自动化软件技术O. L. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No.4列数加1 (p=p+1)。定义文件选第一 张光盘(开始)→文件递降排序队列尾LOF(9)使这个解队列中的最后-个文件(LOQ光盘递升排序J_Dlast of queue)出队，并选取文件队列中此文件YI 满足第二h, N, 满足第-的下一个文件Fk (k=L0Q+1),返回到(6)。、种特例队列)种特例队列>+一变量初始化(10)此文件入备份队列，并记录队列尾| 选取下一张盘L0Q，使LOQ= k. .(11)判断LOQ是否等于LOF,如果不相选取文件队列第一个文件或增加新盘等则选取下一文件Fk (k=k+1), 返回(6);否则选取下一个文件]记录此备份队列为解队列，并从记录的所有解队当前文件可NT在入当前盘列中选取文件总和最大的一-组解队列作为此盘的YYN是否为文件低维最优解，并标识最优解中的文件，将它们文文件入备份队列、 队列尾件队列中剔除。记录队列尾L0Q=kY↓(12)判断文件队列是否为空，如果不为空记录此解队列↓则重新标识LOF,并选取下- -光盘D; (i=i+1),l文件LOQ出队返回到(4);否则执行下一-步。t选取下一个文件 选出低维最优解J(13)判断低维最优解是否唯- -，不唯一则选取LOQ的将解交给人机交互，由管理者选择一组最优解。将最优解中文件清除出文件队列」下一个文件(14)合并所有低维最优解形成高维最优文件队列是否为空重标文件解，结束算法。其算法流程图如图2所示。↓y低维最优解唯N _人机交互选择3.3算法说明及分析低维解(1)算法第4步为处理2种特殊情况，第1种情况为光盘剩余空间无法容纳文件队列中的最[合成高维最优解十小文件，则必须选择剩余空间较大的光盘;第2图2优化BFD算法流程图种情况为光盘剩余空间可以容纳所有文件，则将举例如下:为简化说明，队列以按要求排序,这些文件存入这张光盘而无须再继续执行本算有文件队列: F=14、F=12、F;=8、 F=5、Fs=4.法。在实际大部分情况下，因为光盘的存储容量F。=2，光盘队列: D,=20、 D2=23、 Dj=25. BFD远远大于文件大小，所以本算法比较适合于文件算法、本算法及最优算法运算结果如下:备份工作进行了-段时期，光盘的存储剩余空间BFD算法优化BFD算法最优算法相对较小的情况，这种情况虽然较少遇到，但也余剩余存储文件| 存储文件存储文件:时常发生，届时本算法将充分发挥其作用。空间|空间(2)本算法没有考虑旧光盘用完，而尚有文D:-20F F 1F、FS、FOFFF 0D,=23F F. F.1FF23件没有备份路径的情况。因为此种情况下，考虑D-=25FsF20 TF、F.FO到新光盘的存储容量，只须将所剩文件存入新光4结束语盘中即可。(3)从算法步骤中可以看出，本算法的优化文件及重要资料的备份是当今信息化社会飞实质在于步骤9的备份队列尾的出队，这样就给速发展不可或缺的重要手段，而合理优化地利用其后面的文件提供了更加优化的可能性，而BFD存储介质进行备份，将有利于企业提高备份效算法则没有这-一步。率，节省备份成本。本算法从实际情况出发，并(4)步骤9中，只让备份队列尾的文件出队在原YH中国煤化工已在企业PDM软而其前面的文件不再出队，明显减少了优化搜索件中CNMHG的经济效益。范围，这也是本算法与最优算法的误差所在。参考文献:3.4算法举例1[屈婉玲.组合数学[M|.北京:北京大学出版社, 1989..39●