一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 649|回复: 2
收起左侧

[系统设计/OOD] 一道defragmentation的题目求解

[复制链接] |试试Instant~ |关注本帖
ttttttmix 发表于 2016-2-19 13:11:40 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

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

有没有同学有灵感的提点我一下?
我是新手
stellari 发表于 2016-2-20 14:14:53 | 显示全部楼层
比如这个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是怎么运作的,仅供参考。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

3652ltc 发表于 2016-2-20 16:27:22 | 显示全部楼层
lz 要不你查查buddy system,虽然是内存管理策略,但是对disk也是启发
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 10:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表