聊聊跟三哥三姐面试和共事的经历

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 990|回复: 2
收起左侧

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

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

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

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

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

使用道具 举报

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

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-22 11:57

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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