第四章 文件管理 四、文件的物理结构（文件分配方式）

目录

一、文件块，磁盘块

二、连续分配

1、定义：

2、计算方式：

3、注意：

4、优点：

5、缺点：

6、总结

三、链接分配----隐式链接

1、定义：

2、如何实现逻辑块号转物理块号

3、优点：

4、总结

四、链接分配----显式链接

1、定义：

2、如何实现逻辑块号转物理块号

3、优点：

4、总结：

五、索引分配

1、定义：

2、例子：

3、注意

4、优点：

5、缺点：

6、一个磁盘块不够装怎么办？

（1）链接方案

1.定义：

2.缺点：

（2）多层索引

1.定义：

2.文件最大长度：

3、如何实现逻辑块号转物理块号

4、注意：

（3）混合索引

1.定义：

2.优点：

（4）总结

六、总结

---

一、文件块，磁盘块

1、类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同.

2、优点：方便内存的交换。

3、同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。

二、连续分配

1、定义：

连续分配方式要求每个文件在磁盘上占有一组连续的块。

2、计算方式：

物理块号=起始块号＋逻辑块号

3、注意：

（1）逻辑块号 ≥ 长度 ，就不合法.

4、优点：

（1）可以直接算出逻辑块号对应的物理块号，因此连续分配支持顺序访问和直接访问（即随机访问)

（2）因为读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长，所以，连续分配的文件在顺序读/写时速度最快.

5、缺点：

（1）当黄色区域想要扩展的时候，发现后面的磁盘块已经被占用了，所以就必须整体将黄色块迁移到绿色块才能拓展，因为只有绿色块才有连续的4个块。连续分配的文件不方便拓展。

（2）当有文件想要存储进绿色块时，却发现没有连续的块，所以无法存储，造成了空间的浪费。

结论:物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

6、总结

三、链接分配----隐式链接

1、定义：

2、如何实现逻辑块号转物理块号

（1）类似于链表，每个物理块号只知道它的前驱和后继，若要访问第i个物理块号，只有先把前面i-1个都访问了才行.

结论:

采用链式分配（隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

3、优点：

（1）方便拓展

结论:

采用隐式链接的链接分配方式，很方便文件拓展。另外，所有的空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

4、总结

四、链接分配----显式链接

1、定义：

注意：物理块号可以是隐含的。

2、如何实现逻辑块号转物理块号

（1）一个用户要找aaa的2号逻辑块。

（2）我们首先在FCB中找到aaa的起始块号为2

（3）根据FAT表可知，

物理块号2，是aaa的0号块；

物理块号5，是aaa的1号块;

物理块号0，是aaa的2号块;

（4）所以，aaa的2号块为存放在物理块号为0的磁盘块中。

3、优点：

（1）采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问i号逻辑块时，并不需要依次访问之前的0~ i-1号逻辑块)，由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

（2）显式链接也不会产生外部碎片，也可以很方便地对文件进行拓展。

4、总结：

五、索引分配

1、定义：

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表――建立逻辑页面到物理页之间的映射关系）。

索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

2、例子：

假设我们有一个文件“aaa”,它的数据依次存放在2，5，13，9四个物理块内。

而7号物理块作为它的索引块，里面存的是索引表。

（1）若我们要找aaa的0号逻辑块，首先就得根据FCB目录中的索引块找到索引表。

（2）7号块中存的就是这个索引表

（3）根据逻辑块号0，找到物理块号2中的数据。

3、注意

4、优点：

（1）索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可)

5、缺点：

（1）索引表要占据一定的存储空间。

6、一个磁盘块不够装怎么办？

（1）链接方案

1.定义：

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

2.缺点：

（2）多层索引

1.定义：

使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

2.文件最大长度：

3、如何实现逻辑块号转物理块号

4、注意：

 采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

（3）混合索引

1.定义：

多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表)、还包含两级间接索引（指向两层索引表)。

• 若顶级索引表还没读入内存
• 访问0~7号逻辑块:两次读磁盘
• 访问8~263:三次读磁盘
• 访问264~65799:四次读磁盘

2.优点：

对于小文件，只需较少的读磁盘次数就可以访问目标数据块。(一般计算机中小文件更多)

（4）总结

六、总结