兵工自動化軟件技術(shù)O. I. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No, 4文章編號: 1006-1576 (2001) 04-0037-03海量備份的優(yōu)化BFD算法韓祥蘭，李東波，徐平，林海凡.(南京理工大學(xué)制造工程學(xué)院，江蘇南京210094)摘要:在研究解決裝箱問題的遞降最佳適合算法(BFD算法)的基礎(chǔ)上，提出了文檔管理備份的優(yōu)化BFD算法。同時，給出了包括文件隊列、盤隊列、備份隊列、解隊列、解空間、選出低維最優(yōu)解、合成高維最優(yōu)解在內(nèi)的相應(yīng)的運算步驟和流程圖，對算法的優(yōu)點和誤差進行了分析。并舉例加以說明。關(guān)健詞: BFD算法;優(yōu)化;隊列中圖分類號: TP301.6文獻標(biāo)識碼: 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 前言次序排序，然后對每一個貨物，依次檢查箱子的隨著先進制造技術(shù)的深入推廣和應(yīng)用，企業(yè)空隙，如果哪個箱子放入此貨物后的空隙最小，中越來越多的信息以電子圖檔和文檔的形式存儲就把此貨物放入這個箱子中。在計算機中，故對各種文件進行定期備份就顯得2.2存儲容量問題十分重要。在江蘇省CAD應(yīng)用示范工程中實施如有n個文件須進行備份，其文件大小分PDM系統(tǒng)時，遇到了圖文檔文件備份的存儲介別為F小、F2、...F。又有m張(盒)光盤或質(zhì)容量優(yōu)化問題，即如何按照文件的大小選擇各磁帶可用于備份，其剩余的空間大小分別為D.自的備份路徑，使存儲介質(zhì)的容量達到最優(yōu)的利D2、.、Dm。存儲容量問題是說，采用何種文用效果。該問題與組合數(shù)學(xué)中的裝箱問題類似,件分配方案使得光盤或磁帶的利用效果最優(yōu)。在分析研究了解決裝箱問題的BFD算法后，提2.3兩者的異同出了一個更加符合存儲介質(zhì)優(yōu)化的BFD算法。上述分析可知，裝箱和文件備份有很大的相2裝箱問題與存儲容量問題同之處，但也存在差異。相同之處在于這兩個問2.1裝箱問題題要解決的都是容量分配問題，實質(zhì)是一個數(shù)值裝箱問題說的是，大小不等的貨物裝入容量匹配問題。不同之處在于兩個問題的優(yōu)化方向,一致的箱子中，如何選擇裝箱方案使所須的箱子裝箱問題的優(yōu)化方向是箱子的使用數(shù)最少，而文數(shù)最少川。解決此類問題的方法一般采用FFD件備份問題卻以備份剩余空間相對集中為最優(yōu)。算法或BFD算法。這里介紹最常用的BFD算法，中于!YH中國煤化工得存儲剩余空間集即遞降最佳適合算法。該算法首先將貨物按遞降CNMHG為最優(yōu)。收稿日期: 200-11-14; 修回日期: 2001-05-22作者簡介:韓祥蘭(1976-), 女。遼寧人，1999 年獲南京理工大學(xué)學(xué)士學(xué)位，現(xiàn)南京理工大學(xué)在讀碩士研究生，從事先進制造技術(shù)及PDM研究.37●兵工自動化軟件技術(shù)0. 1. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No.4例1:唯- -解?，F(xiàn)有3個文件F、F2、 F,光盤D、D,，剩余空間都為40?，F(xiàn)有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:多種解?，F(xiàn)有3個文件F、F2、 Fj、儲時雖然可以存儲2個大小不超過10 的文件, .Fs， 大小分別是10、10、20、30 (單位忽略)，但對于一個大小超過10的文件就必須啟用新又有2張光盤D、D,，, 剩余空間都為40.現(xiàn)有盤。而方案B在下次存儲時不僅可以存儲2個3種分配方案，如圖2。大小不超過10 的文件，而且可以存儲一個大小3種情況空間利用效果相同，這時需要選擇超過10 而不超過20的文件，所以方案B的空其中一種方案作為最終解決方案。根據(jù)企業(yè)要間利用效果更加優(yōu)化。求，本算法采取動態(tài)交互方式加以選擇。F(20) .F4 (30)Fz (10)FA (30)剩氽空飼Fj (20)剩汆空間F3(20)0F2(10)10F (10)方案C圖2多種解方 案示意圖3優(yōu)化BFD算法文件隊列，并分別標(biāo)識序號為1、2、3、4.....接著定義文件隊列尾為LOF (last of file)。3.1 有關(guān)定義(2)將所有光盤按剩余空間大小遞升排序,先給出如下定義:組成盤隊列。文件隊列:所有沒有備份路徑的文件序列號(3)選擇盤隊列中的第1張光盤D, (i=1),的隊列。初始時所有文件都在此隊列中，且按并初始化變量。大小遞降排序，隨著算法的進行某些文件可能會(4)處理2種特例。第1種情況為所選光盤被分配備份路徑而離開此隊列。剩余空間小于文件隊列尾LOF的大小，這樣就盤隊列:所有可用于備份文件的光盤序列號必須換下一.張光盤或增加新盤D, (i=i+1), 重復(fù)的隊列，初始時按遞升排序。步驟(4);第2種情況是文件隊列中所有文件大備份隊列:某張光盤所存儲文件序列號的臨小之和小于所選光盤剩余空間，這樣可以直接生時隊列。成高維最優(yōu)解即將文件隊列中的所有文件存入這解隊列:某張光盤所存儲的文件序列號的隊張光盤，結(jié)束算法。列。在算法中該隊列以二維數(shù)組Res(p,q)的形(5)如果沒有出現(xiàn)上述的2種特例，那么選式出現(xiàn)，其中p表示解隊列號，q表示隊列位置。取文件隊列中的第1個文件Fk (k=1)。解空間:某張光盤所有解隊列的集合。(6)判斷當(dāng)前所選文件F,是否可以存入所選低維最優(yōu)解:某張光盤的解空間中最符合優(yōu)光盤D,如果可以存入則轉(zhuǎn)執(zhí)行(10);反之則此化方向的解隊列。文件不入隊，執(zhí)行下一步。高維最優(yōu)解:所有光盤低維最優(yōu)解的集合。是則中國煤化工否為LOF,如果不YHCN MH G文件F (k=k+1),3.2運算步驟返回(6)執(zhí)行;如果是LOF則說明文件隊列已經(jīng)優(yōu)化BFD算法的運算步驟為:比較完畢，執(zhí)行下一步。(1)將需要備份的文件按大小遞降排序組成(8)記錄這組備份隊列為解隊列，并將解隊38.兵工自動化軟件技術(shù)O. L. Automation2001年第20卷第4期Software Techlique2001. Vol. 20. No.4列數(shù)加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);否則選取下一個文件]記錄此備份隊列為解隊列，并從記錄的所有解隊當(dāng)前文件可NT在入當(dāng)前盤列中選取文件總和最大的一-組解隊列作為此盤的YYN是否為文件低維最優(yōu)解，并標(biāo)識最優(yōu)解中的文件，將它們文文件入備份隊列、 隊列尾件隊列中剔除。記錄隊列尾L0Q=kY↓(12)判斷文件隊列是否為空，如果不為空記錄此解隊列↓則重新標(biāo)識LOF,并選取下- -光盤D; (i=i+1),l文件LOQ出隊返回到(4);否則執(zhí)行下一-步。t選取下一個文件 選出低維最優(yōu)解J(13)判斷低維最優(yōu)解是否唯- -，不唯一則選取LOQ的將解交給人機交互，由管理者選擇一組最優(yōu)解。將最優(yōu)解中文件清除出文件隊列」下一個文件(14)合并所有低維最優(yōu)解形成高維最優(yōu)文件隊列是否為空重標(biāo)文件解，結(jié)束算法。其算法流程圖如圖2所示。↓y低維最優(yōu)解唯N _人機交互選擇3.3算法說明及分析低維解(1)算法第4步為處理2種特殊情況，第1種情況為光盤剩余空間無法容納文件隊列中的最[合成高維最優(yōu)解十小文件，則必須選擇剩余空間較大的光盤;第2圖2優(yōu)化BFD算法流程圖種情況為光盤剩余空間可以容納所有文件，則將舉例如下:為簡化說明，隊列以按要求排序,這些文件存入這張光盤而無須再繼續(xù)執(zhí)行本算有文件隊列: F=14、F=12、F;=8、 F=5、Fs=4.法。在實際大部分情況下，因為光盤的存儲容量F。=2，光盤隊列: D,=20、 D2=23、 Dj=25. BFD遠遠大于文件大小，所以本算法比較適合于文件算法、本算法及最優(yōu)算法運算結(jié)果如下:備份工作進行了-段時期，光盤的存儲剩余空間BFD算法優(yōu)化BFD算法最優(yōu)算法相對較小的情況，這種情況雖然較少遇到，但也余剩余存儲文件| 存儲文件存儲文件:時常發(fā)生，屆時本算法將充分發(fā)揮其作用?？臻g|空間(2)本算法沒有考慮舊光盤用完，而尚有文D:-20F F 1F、FS、FOFFF 0D,=23F F. F.1FF23件沒有備份路徑的情況。因為此種情況下，考慮D-=25FsF20 TF、F.FO到新光盤的存儲容量，只須將所剩文件存入新光4結(jié)束語盤中即可。(3)從算法步驟中可以看出，本算法的優(yōu)化文件及重要資料的備份是當(dāng)今信息化社會飛實質(zhì)在于步驟9的備份隊列尾的出隊，這樣就給速發(fā)展不可或缺的重要手段，而合理優(yōu)化地利用其后面的文件提供了更加優(yōu)化的可能性，而BFD存儲介質(zhì)進行備份，將有利于企業(yè)提高備份效算法則沒有這-一步。率，節(jié)省備份成本。本算法從實際情況出發(fā)，并(4)步驟9中，只讓備份隊列尾的文件出隊在原YH中國煤化工已在企業(yè)PDM軟而其前面的文件不再出隊，明顯減少了優(yōu)化搜索件中CNMHG的經(jīng)濟效益。范圍，這也是本算法與最優(yōu)算法的誤差所在。參考文獻:3.4算法舉例1[屈婉玲.組合數(shù)學(xué)[M|.北京:北京大學(xué)出版社, 1989..39●