文件的物理结构
文件快、磁盘块
文件分配方式
连续分配
连续分配方式要求每个文件在磁盘上占有一组连续的块。
用户通过逻辑地址来操作自己的文件,操作系统如何实现从逻辑地址到物理地址的映射?
(逻辑块号,块内地址)→(物理块号,块内地址)。
只需转换块号就行,块内地址保持不变
用户给出要访问的逻辑块号,操作系统找到该文件对应的目录项(FCB)
物理块号=起始块号+逻辑块号。当然,还需要检査用户提供的逻辑块号
是否合法(逻辑块号≥长度就不合法)可以直接算出逻辑块号对应的物理块号,因此连续分配支持顺序访问和直接访问(即随机访问)
读取某个磁盘块时,需要移动磁头。访问的两个磁盘块相隔越远,移动磁头所需时间就越长。
结论:连续分配的文件在顺序读/写时速度最快
若此时文件A要拓展,需要再增加一个磁盘块(总共需要连续的4个磁盘块)。
由于采用连续结构,因此文件A占用的磁盘块必须是
连续的。因此只能将文件A全部“迁移”到绿色区域。
结论:物理上采用连续分配的文件不方便拓展。
结论:物理上采用连续分配,存储空间利用率低,会产生难以利用的磁盘碎片可以用紧凑来处理碎片,但是需要耗费很大的时间代价
总结
连续分配方式要求每个文件在磁盘上占有一组连续的块。
优点: 支持顺序访问和直接访问(即随机访问):连续分配的文件在顺序访问时速度最快
缺点: 不方便文件拓展;存储空间利用率低,会产生磁盘碎片
链接分配
链接分配采取离散分配的方式,可以为文件分配离散的磁盘块。分为隐式链接和显式链接两种。
隐式链接
如何实现文件的逻辑块号到物理块号的转变?
用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB)。
从目录项中找到起始块号(即0号块),将0号逻辑块读入内存,由此知道1号逻辑块存放的物理块号,于是读入1号逻辑块,再找到2号逻辑块的存放位置…以此类推。因此,读入i号逻辑块,总共需要i+1次磁盘i/o
结论:采用链式分配(隐式链接)方式的文件, 只支持顺序访问,不支持随机访问, 查找效率低。另外,指向下一个盘块的指针也需要耗费少量的存储空间。
若此时要拓展文件,则可以随便找一个空闲磁盘块,挂到文件的
磁盘块链尾,并修改文件的FCB
结论: 采用隐式链接的链接分配方式,很方便文件拓展。另外,所有的空闲磁盘块都可以被利用,不会有碎片问题,外存利用率高。
总结：
隐式链接一一除文件的最后一个盘块之外,每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针
优点: 很方便文件拓展,不会有碎片问题,外存利用率高。
缺点: 只支持顺序访问,不支持随机访问,査找效率低,指向下一个盘块的指针也需要耗费少量的存储空间。
显示链接
如何实现文件的逻辑块号到物理块号的转变?
用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项
(FCB）。
从目录项中找到起始块号,若i>0,则查询内存中的文件分配表FAT
往后找到ⅰ号逻辑块对应的物理块号。逻辑块号转换成物理块号的过
程不需要读磁盘操作。
文件分配表中“-1” 代表其为最后一块，没有下一块
结论: 采用链式分配(显式链接)方式的文件,支持顺序访问,也支持随机访问 (想访问i号逻辑块时,并不需要依次访问之前的0~1号逻辑块),由于块号转换的过程不需要访问磁盘,因此相比于隐式链接来说,访问速度快很多。显然,显式链接也不会产生外部碎片,也可以很方便地对文件进行拓展
总结
显式链接一一把用于链接文件各物理块的指针显式地存放在一张表中,即文件分配表(FAT,File Allocation Table），一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存,并常驻内存
优点: 很方便文件拓展,不会有碎片问题,外存利用率高,并且支持随机访问。相比于隐式链接来说,地址转换时不需要访问磁盘,因此文件的访问效率更高。
缺点: 文件分配表的需要占用一定的存储空间。
考试题目中遇到未指明隐式/显式的“链接分配”,默认指的是隐式链接的链接分配
索引分配
索引分配允许文件离散地分配在各个磁盘块中,系统会为每个文件建立一张索引表,索引表中记录了文件的各个逻辑块对应的物理块(索引表的功能类似于内存管理中的页表一一建立逻辑页面到物理页之间的映射关系)。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块
假设某个新创建的文件“aa”的数据依次存放在磁盘块2→5→13→9。
7号磁盘块作为“aa”的索引块，索引块中保存了索引表的内容。
注:在显式链接的链式分配方式中,文件分配表FAT 是一个磁盘对应一张。而索引分配方式中,索引表是一个文件对应一张。
可以用固定的长度表示物理块号(如:假设磁盘总容量为1TB=2的40次方B,磁盘块大小为1KB,则共有2的30次方个磁盘块,则可用4B表示磁盘块号),因此,索引表中的“逻辑块号”可以是隐含的。
如何实现文件的逻辑块号到物理块号的转换?
用户给出要访问的逻辑块号i,操作系统找到该文件对应的目录项(FCB)，从目录项中可知索引表存放位置,将索引表从外存读入内存,并查找索引表即可只i号逻辑块在外存中的存放位置。
可见,索引分配方式可以支持随机访问。文件拓展也很容易实现(只需要给文件分配个空闲块,并增加一个索引表项即可)，但是索引表需要占用一定的存储空间。
若每个磁盘块1KB,一个索引表项4B,则一个磁盘块只能存放256个索引项。
如果一个文件的大小超过了256块,那么一个磁盘块是装不下文件的整张索引表的,如何解决这个问题?
①链接方案
②多层索引
③混合索引
①链接方案
如果索引表太大,一个索引块装不下,那么可以将多个索引块链接起来存放。
②多层索引
多层索引: 建立多层索引(原理类似于多级页表)。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。
③混合索引
混合索引: 多种索引分配方式的结合。例如,一个文件的顶级索引表中,既包含直接地址索引(直接指向数据块),又包含一级间接索引(指向单层索引表)、还包含两级间接索引(指向两层索引表)
总结
难点
