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