最大族群法整理磁盘碎片

一般是FAT32或NTFS文件系统，使用一段时间后，整个磁盘比较零乱(如下图的FAT32文件系统)，使得文件的存取效率大大降低，这时往往会使用磁盘工具来整理磁盘。但一般的 磁盘工具整理速度慢，效率不高，能否通过分析磁盘的文件结构，提出某种最优原则，建立切实可行的数学模型，找到一种高效的整理文件的算法是非常有意义的一件工作。 数据的说明:计算机在读取文件时，先查文件名表，如读800.com文件时，查到文件800.com 的起始族号为2，然后查FAT表第0行第2列(该坐标对应于第2族)的元素为3，表示它的下一族为3，查第3族位置对应的元素为4，又表示下一族为4，一直到第56族，此时第56族的元素为4095为文件结束标记。因此整个文件的起止族号依次为:2，3，4，5，6，7，8，9，10，11，12，13，14，15，16，17，18，19，20，23，25，26，27，28，29，30，31，32，33，34，35，36，37，38，39，40，41，42，43，44，45，46，47，48，49，50，51，52，53，54，55，56。 题目要求利用附一中的数据分步骤解决下列问题: 1、将同一文件的起止族号按次序移动到一组新的连续的族号，使整个磁盘上所 有族的移动次数最少，建立该问题的数学模型并求解。 2、设计相应算法具体实现问题1最优解中族的移动。给出相应结果。 二 问题分析 对于FAT32文件系统的整理，我们主要基于问题所给的数据进行分析。因此对于问题的解决需要抓住关键有用的数据，对数据进行处理。 首先我们将附表处理成一个矩阵，然后基于矩阵对最简单的模型进行讨论，接着在简单模型的基础上逐步深入探讨问题，不断进行进一步的深入研究，逐步建立起相关的概念。最终建立用最大族群法整理磁盘碎片的模型。 三 模型假设 1. 计算机有一块不小于磁盘空间20%的空白区域。 2. 文件顺次相交。 3 最大族群的族数与它所在文件的大小成正相关，且一般较大。 四 符号系统 A,B,C,D,E,F,G,H,I,J,K,L,M 分别代表是十三个文件 A1,B1,C1,D1，E1,F1,G1,H1,I1,J1,K1,L1,M1 分别代表各个文件所占的族数 A2,B2,C2,D2，E2,F2,G2,H2,I2,J2,K2,L2,M2 分别代表在磁盘内仅有一个文件的情况下，该文件的最大族群不动时，将各个文件排列的紧密连续所需要的移动次数。 A3,B3,C3,D3,E3,F3,G3,H3,I3,J3,K3,L3,M3 分别代表各个文件的最大族群占有的族数。 五 模型建立 模型一: 如果只考虑将同一文件的起止族号按次序移动到一组新的连续的族号，我们先可以在计算机硬盘上找一块大的空白区域，将文件一个一个地移动到那片空白区域，每一个文件在移动的过程中，同时就将文件的各族按照顺序排列好。 这个模型非常简单，易于实现，但是缺点也是显而易见的，就是移动的次数最多。因此开始考虑另一种模型。 模型二: 找到一个文件的起始族号，起始族号不动，然后将后续族依次移动连接起来。具体实施过程如下: 模型:假设有这么一个文件，其族与族之间的排列为: 1 --2 3 4--5--6--7 8--9 10 11 12 13 14 15--16 17 (--表示族之间的间隔) 文件分析:连在一起的族有2 3 4，7 8，9 10 11 12 13 14 15，16 17。第一块有3族，第二块有2族，第三块有7族，第四块有2族。第三块有最多的7个族。 如果按照第二种模型，即起始族不动，然后将后续族依次移动连接起来，移动的次数为16次(除1外其余的族都要移动)。 第三块不动，把文件第三块两端的族向第三块移动，易得移动的次数为10次。(十个族要移动)比第二个模型少移了6次，减少工作的比例为37.5%。 分析可得:要使移动的次数尽量小，族数最多的块应该不能动。以此分析 基础进一步得到模型三。 模型三: (1) 以最大族群为基础确定移动。 最大族群定义:属于同一文件且具有最多连续族的块。 现在有13个文件，找到每一个文件之中最大族群位置及最大族群含有 族数。 的 文件名 最大族群起始位置 最大族群终点位置 最大族群族数 A 2136 2146 11 B 25 56 32 C 365 412 48 D 783 841 59 E 21 22 2 F 2224 2228 5 G 1233 1238 6 H 204 211 8 I 1734 1738 5 J 1049 1053 5 K 1865 1873 9 L 63 63 1 M 414 414 1 总数:192 那么最理想的做法便是13个最大族群不动，移动其他的碎部即可。得到各个文件排列结果: 文件名 文件起始位置 文件终点位置 文件族数 A 2131 2158 28 B 5 56 52 C 365 553 189 D 783 912 130 E 21 22 2 F 2220 2228 9 G 1170 1238 69 H 203 250 48 I 1725 1738 14 J 1026 1055 30 K 1794 1879 86 L 63 63 1 M 414 414 1 总数:659 若没有重叠则所需移动次数为659-192=467。 (2)但是文件会有重叠。如B与E发生重叠，C与M 发生重叠。 对两个文件重叠的定义:假设在磁盘内仅有一个文件的情况下，让文件的最大族群不动，将各个文件排列的紧密连续。然后比较它们在磁盘内所在位置，当位置发生重复时即为两个文件的重叠。 两个文件分别为1,2，第一个文件的族用绿色字体，第二个文件用红色字体，文件族号排列如下: 1 1 2 2 3 3 4 5 4 5 6 6 7 7 8 9 10 11 8 9 12 13 10 11 12 13 14 15 14 如上可得，第一个文件最大族群为8 9 10 11，一共有四个族;第二个文件最大族群为10 11 12 13 14 15，一共有六个族。如果按照上述的排列方法，则此两块不动，移动其他的碎块即可，但我们就会马上发现一个问题，那就是如果两个最大族群不动，而两个最大族群之间只有四个族，第一个文件最大族群后面还有3个族，第二个文件最大族群前面有9个族，3+9=12>4，也就是说两个最大块之间的区域是不够的，这样便没法移了。所以，第一个文件与第二个文件之中一定有一个是要全部移动的，为的就是给另外一个文件腾出空白区域。 接下来要探讨的就是移动哪个文件的问题。 现假设移动第一个文件: 在计算机中找一块大小与第一个文件一样的空白区域，将第一个文件移动到空白区域，在移动的同时即将第一个文件中的族按次序连接起来。移动第一个文件所需的次数为14次，接下来将第二个文件按次序紧密连接，第二个文件最大族群不动，移动的次数为9次，一共要移动的次数为14+9=23。 假设整体移动的是第二个文件: 在计算机中找一块大小与第二个文件一样的空白区域，将第二个文件移动到空白区域，在移动的同时即将第二个文件中的族按次序连接起来，移动的次数为15次，接下来将第二个文件按次序紧密连接，第二个文件最大族群不动，移动的次数为10次，一共要移动的次数为15+10=25>23。 结论:当两个文件有重叠时，满足最大族群具有最多族数条件的文件不动;满足最大族群具有最少族数条件的文件要整体移动到一片空白区域。 空白区域指不会使文件重叠的未被利用的区域。 如下:设A，B文件有重叠。且A3>B3，A1,B1的大小关系不定。 整体移动A:移动A所需要的次数为A1 ，再就是B文件内部的整理，所需的次数为B1-B3，所以，总的次数为A1+B1-B3. 整体移动B:移动B所需要的次数为B1 ，再就是A文件内部的整理，所需的次数为A1-A3，所以，总的次数为A1+B1-A3. A1+B1-B3-( A1+B1-A3)=A3-B3.所以移动文件A所需的次数大于移动文件B。同时我们会发现，移动的次数与两个文件的各自的整体大小没有关系。问题得证。 所以，B，C不动，E与M要整体移动到一个空白区域。最终13个文件移动总次数为s= (659-2-1)-(192-2-1)+(2+1)=470。 六 模型推广 1 考虑到实际情况，将上述模型推广到N个文件顺次相交的情况. 顺次相交定义:仅相邻两文件发生交叠，含有N-1个这样的重叠区域 证明如下:先令N=3 如图三条横线代表三个交叠的文件，且第二个文件与其余两个文件都有交叠，第一个文件与第三个文件没有交叠。很自然的，其实现在我们有两种做法:第一种，移动第二个文件;第二种，移动第一个与第三个文件。 假设着三个文件分别为A,B,C。 移动B:先移动B所需的次数为B1，整理A,C所需要的次数为A1-A3+C1-C3。总共的次数为A1-A3+C1-C3+ B1 移动A,C:先移动A,C所需的次数为A1+C1,整理B所需的次数为B1-B3, 总共的次数为A1 +C1 + B1-B3。 A1-A3+C1-C3+ B1-(A1 +C1 + B1-B3)=B3-A3-C3. 当B3>A3+C3时移动文件B ，反之移动文件A,C. 令N=6，上部分(红色不连续线条)是独立文件的集合，下部分(黑色不连续线条)也是独立文件的集合。 假设文件依次为A,B,C,D,E,F。其中，A与B有重叠，B与C有重叠，C与D有重叠……不难想到，有两种移动的方法，要么移动A，C，E，要么移动B，D，F。 移动文件A，C，E:整体移动A,C,E所需的次数为A1+C1+E1。再整理B，D，F所需的次数为B1-B3+D1-D3+F1-F3,总共所需的次数为A1+C1+E1+(B1-B3+D1-D3+F1-F3)。 移动文件B，D，F:整体移动B,D,E所需的次数为B1+D1+F1。再整理A，C，E所需的次数为A1-A3+C1-C3+E1-E3,总共所需的次数为B1+D1+F1(A1-A3+C1-C3+E1-E3). 比较:A1+C1+E1+(B1-B3+D1-D3+F1-F3)-[ B1+D1+F1+(A1-A3+C1-C3+E1-E3)]=A3+C3+E3-(B3+D3+F3)。 结论:移动上下部中最大族群和较小的那一部文件。 这个规律推广到N个文件 就表述为:按照N个文件起始族在磁盘内的先后顺序依次从一编号到N，当N个文件顺次相交，分别计算出奇数位及偶数位所有文件的最大族群族数和，假设分别记为m，n，当m>n，奇数位的文件不动，偶数位的文件都移动到空白区域;m