【操作系统】文件管理

曾经终败给现在 2023-01-07 07:08 392阅读 0赞

### 文章目录 ###

*   *  一、文件系统概述
     *  二、文件系统的实现
     *   *  2.1 连续分配
         *  2.2 链接分配
         *  2.3 索引分配
     *  三、文件存储空间管理
     *   *  3.1 位示图法

## 一、文件系统概述 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70][]  
`FCB` 就是文件目录项，文件控制块。

对一个文件的访问由 `用户访问权限` 和 `文件属性` 共同限制。

**例题**

> 设文件 F1 的当前引用级数值为 1 ，先建立文件 F1 的符号链接（软链接）文件 F2 ，再建立文件 F1 的硬链接文件 F3，然后删除文件 F1，此时文件 F2 和文件 F3 的引用计数值分别是`（1，1）`。

怎么算出来的呢？看下面的脑图你就懂了。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 1][]

当建立 F2 时，F1 和 F2 的引用计数值都为 1 ，再建立 F3 时，F1 和 F3 的引用计数值就都变成了 2 。后来删除 F1 时， F3 的引用计数值为 `2-1=1`，F2 的引用计数值不变。

此类题目为常考体型。

`存取控制矩阵` 方法用来协调多用户之间的文件管理。

## 二、文件系统的实现 ##

这部分是将逻辑地址转化为物理地址的具体方法。

常考的知识点有两个：

*  求文件的最大长度；
 *  求访问磁盘次数；

文件分配方式的物理结构包括：`连续`、`链式`、`索引` 3 种；

他们各有利弊，其中 `连续` 不利于扩展，`链式` 不能随机访问，而 `索引` 既能扩展，也能随机访问。

![分配方式][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 2]

### 2.1 连续分配 ###

*  连续分配中，起始块号+逻辑块号=物理块号。
 *  读取某个磁盘块时，需要移动磁头，访问的两个磁盘块离得越远，移动磁头所需的时间就越长。
 *  连续分配的文件在顺序读写时 `速度最快` 。

文件目录表中存放块的 `开始地址` 和 `分配的长度` 。该分配方式的缺点是不宜扩展，一旦要扩展，就要移动很多的盘块。

### 2.2 链接分配 ###

分为隐式链接和显示链接，二者的区别在于显示链接单独拿出一个表存储链式关系，这个表叫做 文件分配表 `FAT` 。

**隐式链接**

目录表中记录 `起始块号` 和 `结束块号` ，对于每一个盘块，都有指向下一个盘块的指针。

优点是方便扩展，缺点是只支持顺序访问，不支持随机访问，要想访问 `i` 号块，需要 `i+1` 次磁盘 IO。

**显示链接**

目录表中记录 `起始块号` 。

把用于链接文件各物理快的指针显示地存放到一张表中，文件分配表 `FAT`，它常驻内存。表中记录着物理块号和下一块地址，相当于数组模拟链表，实现静态链表。

### 2.3 索引分配 ###

目录表中存放的是 `索引块` 的地址。

索引分配为每一个文件建立了一个索引块，索引块其实就是一张表，它记录了各个逻辑块对应的物理块地址。

使用索引分配，每个文件都有其索引块，但是索引块能存储的记录数有限，如果一个文件的大小超过了一个索引块能存储的最大容量，就要考虑扩容了，有以下 3 种方式扩容：

*  将索引块按照链接的方式连接起来；
 *  建立多层索引（套娃）
    
        假设磁盘块的大小为 1KB，一个索引表占 4B，则一个磁盘块能存放 256 个索引项；
        如果某文件采用两层索引，则该文件的最大长度可以到 256 * 256 * 1KB = 64MB；
        如果要找 1026，1026 / 256 = 4 号索引块，1026 % 256 = 2，4 号索引块的 2 号索引项。
        
        采用 2 层索引，需要读 3 次磁盘IO。以此类推。
    
    ![二级索引表][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 3]
 *  混合索引，这个索引表中有直接地址、一级间接、二级间接；
    
        假设磁盘块的大小为 1KB，一个索引表占 4B，则一个磁盘块能存放 256 个索引项；
        如果采用混合索引，假如一个索引块总共有10个索引，其中直接地址有 8 块，一级 1 块，2 级 2 块；
        那么总共的 1 级就是 256 块，2 级就是 256 * 256 = 65536 块，所以总共有 8 + 256 + 65536 块。
        
        如果顶级索引表还没有读入内存，那么需要的读磁盘次数分别是：2、3、4.。

**例题**

关于计算文件大小的题目：

例一：

> 设文件索引节点中有 7 个地址项，其中 4 个地址项是直接地址索引，2 个地址项是一级间接地址索引，1 个地址项是二级间接地址索引，每个地址项大小为 4B，若磁盘索引块和磁盘数据块大小均为 256B，则可表示的单个文件最大长度是？

每个索引块能放的地址块数：256/4=64
    
    总共有 7 个地址项：
    4 个直接地址，所以 4*256 B
    2 个一级间接地址，所以 2*64*256 B
    1 个二级间接地址，所以 1*64*64*256 B
    
    最大长度就是 3 者之和，即 1082368 B = 1057 KB

例二：

> 文件系统采用两级索引分配方式，若每个磁盘块的大小为 1KB，每个盘块号占 4 B，则该系统中单个文件的最大长度是？

索引块=磁盘块=1KB
    每个索引块中能放的地址块数：1KB/4B = 256
    采用二级索引，文件的最大长度为：256*256*1KB=2^26B=64MB

例三：

> 假定磁盘块的大小为 1KB，对于 540MB 的硬盘，其文件分配表 FAT 最少需要占用多少存储空间？

硬盘总块数为 540MB/1KB = 540K 个；
    因为 540K 刚好小于 2^20，所以文件分配表的每个表目可用 20 位，即 20/8=2.5B；
    这样 FAT 占用的空间为 2.5*540KB=1350KB；

关于计算访盘次数的习题：

例一：

> 一个文件系统中，其 FCB 占 64B，一个盘块大小为1KB，采用一级目录。假定文件目录中有 3200 个目录项。则查找一个文件平均需要多少次访问磁盘？

一个盘块可以放多少个 FCB？ 1KB/64B=16个
    该文件目录需要多少个磁盘块用来存放目录？3200 / 16 = 200 个
    所以总共有 200 个磁盘，平均访问次数就是一半，即 100 。

例二：

> 【2015统考真题】在文件的索引节点中存放直接索引指针 10 个，一级和二级索引指针各 1 个。磁盘块大小为 1KB，每个索引指针占 4B，若某文件的索引节点已在内存中，则把该文件偏移量（按字节编址）为 1234 和 307400 处所在的磁盘块读入内存，需访问的磁盘块个数分别是？

索引块=磁盘块=1KB，则每个索引块能存放的记录数为 1KB / 4B = 256 个。
    直接索引指针能存放的文件大小最多为 10*1KB=10KB；
    一级索引指针能存放的文件大小为：1*256*1KB=256KB；
    二级索引指针能存放的文件大小为：1*256*256*1KB=64MB；
    
    因为 1234B 大于 1KB，又小于 2KB，所以他应该是第二个直接索引，访盘次数为 1。
    而 307400B 大于 256Kb，小于 64MB，所以踏实二级索引，访盘次数为 3 次，先访问两次得到文件所在的磁盘块地址，再访盘一次即可读出文件内容。

## 三、文件存储空间管理 ##

![存储空间管理][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 4]  
上面的脑图只是为了让大家从宏观上了解一下关于存储空间管理的几种方法，对于做题，我们只需要掌握好 **位示图法** 即可。

### 3.1 位示图法 ###

*  位示图利用 `二进制` 来表示磁盘中一个盘块的使用情况。
 *  当其值为 `0` 时，表示对应的盘块空闲；为 `1` 时，表示已分配。
 *  磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。

关于位示图的计算，分为两类，一种是盘块的分配，另一种是盘块的回收。

注意：默认字号和位号都是从 `0` 开始的。

先来看盘块的分配：

找到一个值为零的二进制位，假设他位于第 i 行，第 j 列，注意这里是第几行而不是他本身的值，那么他对应的盘块号就是：
    b = n(i - 1) + j；
    n 代表每行的位数。

然后是盘块的回收：

主要是求行号 i 和列号 j ：
    i = (b - 1) DIV n + 1；
    j = (b - 1) MOD n + 1；

**例题**

例一：

> 若用 8 个字（字长 32 位）组成的位示图管理内存，假定用户归还一个块号为 `100` 的内存块时，它对应位示图的位置是？

这题考的是盘块的回收，套公式即可：
    i = (100 - 1) DIV 32 + 1 = 99/32 + 1 = 4
    j = (100 - 1) MOD 32 + 1 = 99%32 + 1 = 4
    所以位置坐标是（4，4）

例二：

> 文件系统采用位图法表示磁盘空间的分配情况，位图存于磁盘的 32~127 号块中，每个盘块占 1024B，盘块和块内字节均从 0 开始编号。假设要释放的盘块号为 409612，则位图中要修改的位所在的盘块号和块内字节序号分别是？

字长为 1024*8
    盘块数：32+(409612/(1024*8)) = 82
    块内字节序号还需除以8，所以结果是 （盘块号%（1024*8）/ 8）= 1；

例三：

> 假定一个磁盘组共有65536个柱面，每个柱面上有16个磁道（即有16个读写磁头），每个盘面分成256个扇区。问：  
> （1）整个磁盘空间共有多少个存储块（扇区）？  
> （2）如果用字长为32位的单元来构造位示图，共需多少个字？  
> （3）位示图中18字，16位对应的块号是多少？（字号和位号皆从0开始编号，块号从1开始编号）  
> （4）由（2）的计算结果分析，你认为大容量磁盘空间的管理，是否适宜采用位示图？

（1）65536 × 16 × 256 = 268435456，即整个磁盘空间共有 268435456 个存储块（扇区）；
    （2）268435456 ÷ 32 = 8388608，即用字长为 32 位的单元来构造位示图，共需 8388608 个字，即 32MB。
    （3）块号 = 字号 × 字长 + 位号 + 1 = 18 × 32 + 16 + 1 = 593。
    （4）由（2）可知，构造位示图需要8388608个字，即 32MB，占用磁盘空间相当大，
    系统启动后，位示图调入内存后占用内存空间相当大，查找如此巨大的位示图，效率不高。
    由此可知，大容量磁盘空间的管理不宜采用位示图。

文章的最后附上文件的基本操作：  
![文件的基本操作][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 5]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70]: /images/20221119/8c9ca4c24fa14c1c87e5347cfbbb20fa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 1]: /images/20221119/875b2a01cb74423ab2ef3c8747cbcc38.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 2]: /images/20221119/525bb1b0a8ba45adba6afce1b6d70351.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 3]: /images/20221119/88e19e6aecf247f5bd25461f56a76523.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 4]: /images/20221119/26544e7171c44fa78dd312279dca367c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0MTM2NA_size_16_color_FFFFFF_t_70 5]: /images/20221119/e12266b0595242018561bbc0d85deba1.png