一道defragmentation的题目求解

是在模拟的diskdrive上有很多file 每个file分散在多个disk block里面
如何能做到defragment（就是让 每个file的piece都是continuous）

楼主想到用hash table存储每个file然后再重新写入。。。
但是有RAM限制所以并不能把每个file都hash。。

有没有同学有灵感的提点我一下？
我是新手

比如这个disk使用FAT格式，那么FAT表中应该已经有以下信息：
1、每个文件的起始簇（就是你说的block）编号；
2、每个文件的大小和占用的簇个数；
3、每个簇的下一个簇的序号。

所以，这个题说白了就是每个文件都是一个链表，要把链表节点重新安排到连续空间中。

假设磁盘尾部还有足够可用空间，我想可以用这些空间当做缓存空间来进行交换：

1. 1、维护变量 i = 0表示当前可用的簇序号，iFile = 0表示当前正在处理的文件，iClus = GET_FIRST_CLUSTER_OF_FILE(iFile)表示当前正在处理的簇序号。
   
2. 2、如果disk(i)不为空，且正好是当前文件的当前簇序号（即i == iClus），就直接i++，重复2；否则3：
   
3. 3、如果disk(i)处不为空，那么先将disk(i)处的内容拷贝至磁盘尾部第一个空闲簇disk(j)。同时令FAT(j) = FAT(i), FAT(i) = j，然后抹去disk(i)处内容。
   
4. 4、此时disk(i)一定为空，所以可将disk(iClus)处内容直接拷贝至disk(i)，同时获得此文件中下一个簇的序号：iClus = FAT(iClus)。这里有一点特别注意就是得到的新iClus如果 < i（这说明下一个簇本来是在 i 之前，但此时肯定已经被覆盖了，但是还好我们在3中保留了一个指向拷贝后位置的连接），那么就再执行一次iClus = FAT(iClus)。
   
5. 5、如果此时iFile的所有簇已经处理完毕，则iFile，然后重新初始化iClus。
   
6. 6、如果所有的iFile都处理完毕，则转到7，否则重复2.
   
7. 7、根据原始文件的数目和大小，重建FAT表。

复制代码

以上纯属个人见解，我其实并不知道实际的defragger是怎么运作的，仅供参考。

lz 要不你查查buddy system，虽然是内存管理策略，但是对disk也是启发