下面我们来讨论文件分配
文件分配是指我们把哪些块
分配给一个文件来存它的数据
在具体讨论分配方法之前呢
我们有必要来分析一下文件的大小
也就是说我分配的方法
跟文件的大小是有直接关系的
那首先我们来看
文件大小的分布情况
在我们现在想象里头
或者说 在我们现在
实际数据统计里头
可以发现这样一些情况
就是大多数的文件都是很小的
所以在我们的分配方法里头呢
那个数据块的大小不能太大
因为如果说你的大部分数据
放到一块里有很大的剩余的话
那么这时候呢
它的存储效率是比较低的
所以我们在这儿呢
需要对小文件提供很好的支持
当然这个文件小呢实际上也是相对的
比如说在我们用计算机早期
我的数据呢 你比如说像邮件
通常情况下就是几百个字节
几千个字节就已经算是比较少的了
但是现在的邮件呢
实际上我们上头有一图片签名
这一下子就是多少K出去了
所以这个大小呢也是一种相对的
并且随着时间的变化
和应用的变化而不同
与此同时我们还有一些非常大的文件
所以在我们分配办法里头呢
必须考虑到如何能支持这些大的文件
比如说我们来描述
分配给一个文件的数据块有多少个
那这时候呢你有一个标识
这个标识呢比如说用个整数来表示
整数有多少位
就跟你这儿能表示的
最大个的文件的大小是直接相关的
如果说你不足以表示
实际用到的最大文件的大小
那么你这个文件系统就没法来使用了
所以我们需要对大文件有很好的支持
要考虑到这个文件可能会比较大
比如说像我们现在
看到的一张光盘映像
这个映像文件通常是几个G
如果说我是一个虚拟机的镜像
那这个镜像
可能会是几十个G或者更多了
那对于这种情况呢我们也需要做考虑
所以针对这种文件大小的分布呢
我们来看如何来进行文件分配
分配是指说
我把哪些数据块给一个文件
但实际上这种分配的办法呢
它背后的本质实际上是
用什么样的方法来表示
一个文件的数据块的位置和顺序
因为这个位置和顺序的表示方法
直接决定着你如何来分配
那我们看有怎样一些分配方法
这些分配方法呢在这儿
一个是连续分配
我分配一个起点
然后连续的若干个数据块
用来存在这个文件
也可以用链式分配
我告诉你在第一块里记第二块的位置
一直到最后一块
也可以采用索引分配
我分配一块里头专门用来存序号
说我这里都有哪些块存了数据
这些块的顺序是啥样子
这是几种常见的办法
这几种办法呢
我们在选择的时候
考虑的因素呢一个是存储效率
一个是读写性能
存储效率呢是说
我每次分配的最小单位是一块
所以内碎片我们就没办法进行处理了
我们在这里能做的处理就是
你在选择数据块大小的时候做些考虑
假定这个问题我们忽略
我们来看外碎片
也就相当于如果我是连续分配
中间块数不够的时候
你想表示大文件就是不行的
所以在这儿呢
你的选择算法有存储效率的问题
当然我们说后两种算法
它就没有外碎片
所以这个问题就没有了
但是它有后面的问题
读写性能问题
说如果我是顺序分配
那我知道起点
然后我就按照序号往下算
我就能知道
我要访问的任何一个位置在哪
这样的话我的随机读取的速度会很快
但是如果说你是链式分配的话
那么这时候我要想找中间某一块
我必须从头往后去找
去遍历这个链表
那这时候呢它的读写性能就会比较差
这些都是我们在这里讨论
文件分配的时候必须考虑的指标
那我们对三种分配办法呢
做一个简要的描述
首先是连续分配
连续分配呢是在文件头也就是
我们所说的文件控制块里头呢
记录起始第一块的位置和长度
因为我是连续的
所以我知道第一块和长度之后
那么能说清楚每一块这个文件分配的
所有的块都在什么位置
我们用一个图示来表示
这就是你的索引结点
也就说文件控制块
里头有一个指针指向第一块
并且里头记录了它的长度在这儿
就从这儿到这儿
这是我的一个文件所占用的数据块
那在这里头我怎么去找
这个连续的这块区域呢
最先匹配 最佳匹配
我们在前面跟内存分配
也有类似的讨论
那些讨论的特征在这儿
都有一定程度的体现
在这儿我们就不仔细去讨论了
这些做法它的特点有什么样呢
文件的读取性能表现非常好
也可以有很好的顺序
和随机读取的性能
它的麻烦是什么
它的麻烦是碎片
我想分配十块结果现在就剩五块了
那这五块没法用了
如果说我在这里头碎片很多
实际上这时候
它的存储效率会比较差的
再有一个问题
这是我们在前面
内存分配里不太遇到的
或者说不是很重要的问题
就是文件长度的变化
我减少长度这事还好说
增加长度如果说分配的正好是这一块
你给它增加
那后面块已经被其它文件占用了
那这时候怎么办
因为我们是持久数据保存
那这个保存完之后
这数据长度会增加这是极有可能的
对于这个问题呢我们不能忽视
那怎么办 在这里说到
我可以后面预留几块
还是说我分配的时候再把它整个搬
所以从这个角度来讲呢
这个长度发生变化 特别是增加
对于它来说是一个比较棘手的事
这是第一种做法
接下来我们讨论第二种做法 链式分配
链式分配呢是指说
我用一个数据块的链表来表示
在文件头里头有指向第一块的指针
然后第一块有指向第二块的指针
这时候呢顺序走下去
同时呢在头里头呢
再加上一个指向最后一块的指针
这样一来我们就可以表示清楚
一个文件所占用的数据块
第一块是在哪 都占用哪些块
它的这些块的顺序是什么样子
这种做法它有什么样的特征呢
优点是这时候说我在这里头
增加删除占用的数据块
这都会比较方便
由于任何一个数据块我都可以
插到这里头来所以它没有外碎片
但是它有什么问题
它没有办法很方便地实现随机访问
我想找第一块最后一块
那这是你是直接从文件控制块里头
就可以找到的
但是我想找中间这一块怎么办
我只能找到第一块然后顺序往后找
我才能找到后面这一块
由于我是单向的链表
我想找倒数第二块
我只能从正着数的第一块一直找过去
从这个角度来讲呢
它的访问特征呢是比较差的
再有一条呢是它的可靠性
我们在这里存到磁盘上
数据放一段时间之后
或者说多次读写之后
里头数据可能会出错的
如果说我在这里头
指向下一块这个指针出了错
那么从这个指针往后的数据你就丢了
所以从这个角度来讲呢
它的可靠性是比较差的
这是第二种做法 链式分配
第三种做法呢是索引分配
也就说为每一个文件
创建一个索引数据块
里头来存都有哪些数据块我存了数据
这时候这是这个索引数据块里的内容
是指向所有数据块的指针的列表
然后在你文件头里头
有一个指向索引数据块的指针
那么这样的话
从文件头就知道这个索引块在哪
然后在索引块里呢
我能知道每一块的位置
和它们之间的顺序
从这个角度来说
这种做法好像不错
这是它的图示
我在文件头里指向索引块
索引块里呢
有每一块的序号和它们的顺序
这时候说它的好处有什么
创建 增加 缩小都比较容易
然后也没有碎片
你想直接访问哪一块呢
我读到这一块索引块也就行了
所以这样一来它也可以支持直接访问
那它有什么缺点
这时候说如果我的文件很小
它一块就能存得下
你还分配一个索引块
那么这时候我又得要两块
这时候呢它的存储开销是很大的
这是文件比较小的时候
如果文件比较大呢 大到什么程度
大到我索引块里存的这些序号
它也用一块存不下了
那这时候呢
我这地方就得再加索引块
如果说你在你这里头
不支持加多个索引块的话
那么这时候
对大文件的表示呢也会有麻烦
所以这是我们这几种办法呢
我们看下来
它都各自有各自的优点和缺点
那在实际用的时候呢
我们基本上会把这几种呢
组合到一起来用
那这时候对于大个的索引文件呢
我们又可以在这里呢
再往下组合新的方式
链式索引块
也就是各个索引块之间它怎么来组织
总体上来说它是索引分配方法
指向这里的块
然后这地方是索引块
索引块之间呢我用一个链式
或者索引块之间呢再做一个索引
这就变成了多级索引块
这是对大文件的表示方法
我们下面呢
来看一个实际的索引分配方法
看它怎么做的
怎么来把我们前面说到的
各种算法的优点集中到一起
把缺点都去掉
这就是我们这里的UFS的多级索引分配
UFS是unix file system
unix文件系统
它的做法是什么呢
在这个文件控制块里头
我前面10个是直接索引
你直接这10块的位置都标在这里头
如果说你存的数据比较少
只有10块以内
我就索引直接到文件对应的数据块
如果说大于10块
那这时候呢我第11个指针呢
写的是一个一级间接索引
那在这儿呢 它指向一个索引块
这个索引块里头呢
再指向实际的数据块
这是一个间接索引
这时候我在间接索引块里
能放多少个序号呢 假定说能放N个
根据你每一个序号所占用的空间不同
和你块的大小呢这个地方是不一样的
有了一级索引
那这时候我只需要11个指针在前面
如果说你仍然加一个一级索引
和前面十块加在一起还不够用 怎么办呢
不是我在这里再给你加一个一级索引
它是加一个二级索引
这是索引块的索引 这是二级索引
那么只要你大到一定程度之后
我就不再采用一级索引了
我采用二级索引
那二级索引如果仍然不够用怎么办呢
它会再加一级 三级索引
相当于这是索引块
然后这是一级索引
然后这是二级索引
那这时候我们看到后面这一块的话
你要想访问到实际的数据块
它前面是有大量要查询的
这是我们多级索引它所面临的麻烦
但是把这几个搁到一个实际系统里头
我们就看到
它表示文件的大小比较小的时候
它的效率呢是直接索引
文件比较大的时候呢
它也能表示
当然这个效率它是会有一定下降的
我们看到在这里头呢
这就把前面讲的几种办法呢
很好地组合到一起
从而呢变成一个实际的索引分配方案
这是我们用一个实际的例子来说情况
说10个然后在这里呢
文件控制块里呢只有13个指针
那下面我们看一下它所带来的效果
这时候对于文件大小的限制
我由于有三级索引
那我可以表示很大的文件
具体有多大
我们会在练习里来进行计算
然后说我对于动态分配
我增加缩小都比较容易
那这是索引分配方案的好处
然后我对付小文件呢
它的开销也比较小
因为我直接在控制块里头
填这个数据块的序号
而对于大文件来说呢
我使用间接索引
所以这样它也能表示大文件
只是说它的查询速度呢会有所下降
到这个地方呢
我们就把文件分配的几种方法呢
有了一个大致的介绍
也说明了它们各自的
适用场景和优缺点