计算机操作系统（肆）

本文章是关于计算机操作系统的学习笔记，笔记主要来自王道的操作系统课程，总共有五个章节：

• 第一章：计算机操作系统（壹）
• 第二章：计算机操作系统（贰）
• 第三章：计算机操作系统（叁）
• 第四章：计算机操作系统（肆）
• 第五章：计算机操作系统（伍）

一、初识文件管理

文件的定义：一组有意义的信息的集合

文件的属性：文件名、标识符、类型、位置、大小、保护信息…

文件内部如何组织（文件的逻辑结构）

文件之间如何组织（目录结构）

操作系统应该向上提供的功能（create、delete、open、close、read、write等系统调用）

文件如何存储在外村中（文件的物理结构）

操作系统如何管理外存的内存块（存储空间的管理）

操作系统提供的其他文件管理功能（文件共享、文件保护）

二、文件的逻辑结构

1、文件的逻辑结构

（1）无结构文件

文件内部数据由一系列二进制流或字符流组成，又称“流式文件”，如txt文件

（2）有结构文件

由一组相似的记录组成，又称“记录式文件”，每条记录又由若干个数据项组成，如数据库文件，excel文件。

每条记录可以有一个数据项作为关键字（识别记录的ID）。

根据每条记录的长度是否相等，可以分为定长记录和可变长记录。

2、有结构文件的逻辑结构

（1）顺序文件

文件中记录按顺序排列（逻辑上），记录可以定长或者变长，各个记录物理上可以顺序存储或链式存储

顺序结构按照排序又分为串结构和顺序结构

• 串结构：记录间的顺序与关键字无关（通常按时间排序）
• 顺序结构：记录间的顺序按关键字顺序排列

考试中默认“顺序文件”就是指物理上顺序存储的顺序文件

（2）索引文件

对于可变长记录文件，要找到第i个记录，如果是顺序文件，就必须要顺序查找前i-1个记录。因此就引入了索引文件。

索引文件会建立一个索引表，每个记录对应一个表项，即表项中会有指针指向对应记录。索引表项是定长记录，即索引表是定长的顺序文件，因此查找第i个记录时，通过随机存取就可以快速找到记录。

随机存取：那数组a举例，每个元素大小为L，那么第i个元素地址就是a+i*L，存取速度很快。

（3）索引顺序文件

索引文件和顺序文件思想的结合。

索引顺序文件会将文件记录分组，每组就是一个顺序文件。之后建立一个索引表，表项不再存储每个记录，而是存储一组记录，即一组记录对应一个索引表项。

比如学生记录按姓名开头字母分组，共A~Z共26个顺序文件。索引表中，记录每组记录，即索引表共26个索引表项，每项指向一个字母开头的顺序文件。

（4）多级索引顺序文件

可以继续套娃，当记录过多时，建立多级索引表，提高检索效率

三、文件目录

1、文件控制块（FCB）

目录本身就是一种特殊的文件（目录文件），一个文件对应一个FCB，一个FCB就是一个目录项，FCB记录了文件的基本信息。

FCB的有序集合组成文件目录。

2、目录操作

搜索、创建文件、删除文件、显示目录、修改目录

3、目录结构

• 单级目录结构：一个系统只有一张目录表，不允许重名
• 两级目录结构：主文件目录（MFD）+用户文件目录（UFD），文件可以重名，单不能对文件进行分类
• 多级目录结构（树形目录结构）：当代操作系统采用方法、但不便于文件共享
• 无环图目录结构：可以实现文件共享，在树形目录结构基础上，增加指向同一结点的有向边，并为共享节点设置共享计数器，计数器为0才真正删除该结点

4、索引结点（对FCB改进）

除文件名之外的信息都放进索引结点中，每个文件对应一个索引结点。此时目录项只有文件名和索引结点指针，指针指向文件对应的索引结点。此时目录项长度大幅减小，磁盘I/O减少。

四、文件的物理结构

本章探讨的是操作系统对非空闲磁盘块的管理，即文件的物理结构（文件分配方式），如何将文件数据存放在外存中。

1、连续分配

连续分配方式要求每个文件在磁盘上占有一组连续的块。问了实现逻辑地址到物理地址的映射，文件目录表中会记录起始块号和长度两个属性，物理块号=起始块号+逻辑块号

优点：连续分配支持顺序访问和随机访问（直接访问），在顺序读写速度最快。

缺点：物理上采用连续分配的文件不方便拓展，存储空间利用率低，会产生难以利用的磁盘碎片。

2、链接分配

（1）隐式链接

类似动态链表，目录项中记录文件的起始块号和结束块号，除了文件最后一个磁盘块，每个磁盘块都会有一个指向下一个磁盘块的指针。

优点：方便拓展文件，不会产生碎片问题，外存利用率高

缺点：只支持顺序访问，不支持随机访问，查找效率较低

（2）显示链接

类似静态链表，目录项只需记录起始块号，然后用一个文件分配表（FAT）记录物理块号和指向的下一物理块。FAT是常驻内存的，一个磁盘对应一张。地址转换时，先从目录项找到起始块号，然后通过FAT快速查找下一块位置，无需每次访问下一块都进行磁盘I/O。

优点：支持顺序访问，也支持随机访问（访问第i块时，不用每次都顺序访问前i-1块，只需要在表中快速查找即可），由于不用访问磁盘，因此相比隐式链接速度快很多。并且不会产生外部碎片，也可以方便对文件拓展

缺点：文件分配表需要占用一定存储空间

考试中若未指明具体链接分配方式，默认指隐式链接。

3、索引分配

（1）概念

类似页表，系统会为每个文件建立一张索引表，索引表记录了文件的各个逻辑块对应的物理块。

存放索引表的磁盘块称为索引块，文件数据存放的磁盘块称为数据块。在目录项中，会记录文件对应的索引块，这个索引块保存的内容就是索引表。

优点：支持随机访问，容易实现文件拓展

缺点：索引表需要占用一定空间

（2）索引分配方案

假设一个磁盘块能够装下256个索引项，若此时一个文件大小超过256块，一个磁盘块装不下一整张索引表了，此时如何解决？

① 链接方案：分配新的索引块，并且将多个索引块链接起来存放（类似链表）。该方案的缺点就是只能顺序查找，如果文件过大时，每次访问最后一个索引块的速度很慢。

② 多层索引：建立多层索引（类似多级页表），第一层索引块指向第二层索引块，当然还可以建立更多层。缺点就是多级页表需要多次读写磁盘操作。

计算：
假设一个磁盘块只能存放256个索引项，那么两层索引就可以记录256*256=65536个索引块。
假设要访问1026号逻辑块，那么1026/256=4，1026%256=2，只需访问4号二级索引表的2号索引块即可。
采用K层所以你结构，需要进行K+1次磁盘I/O。

③ 混合索引：就是多种索引分配方式的结合，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又有一级间接索引（指向单层索引表），也可以有二级间接索引（指向两层索引表）。

该方案相较于多层索引来说，减少了磁盘I/O操作，并不必每次都通过多层间接索引查找。

4、考点总结

① 根据多层索引、混合索引结构计算文件最大长度（Key：各级索引表大小不能超过一个块）

② 计算访问某个数据块需要的都磁盘次数（Key：根据FCB读入顶级索引块，每次读入下一级索引块都进行读磁盘操作，注意题目是否说明顶级索引块已调入内存）

五、文件逻辑结构与物理结构

文件的逻辑结构是对用户来说的，文件内部的信息组织方式是怎么样的，是顺序存储、链式存储还是索引存储，完全由用户决定，操作系统并不关心。

文件的物理结构是对操作系统来说的，对操作系统来说，文件就是一堆二进制数据，它会将文件拆成一个个小部分，存储进磁盘块中，至于这些小部分如何存储，是采用连续分配，连接分配还是索引分配，由操作系统决定，用户不必关心。

简单来说就是：用户只需关心文件的逻辑结构，至于文件实际如何存储在磁盘中，用户不用关心，由操作系统完成。

六、文件存储的空间管理

本章探讨的是操作系统对空闲磁盘块的管理，即文件存储的空间管理。

1、存储空间的划分与初始化

（1）存储空间的划分：将物理磁盘划分为为一个个文件卷（C盘、D盘等等）

（2）存储空间的初始化：将各个文件卷划分为目录区（存储FCB、磁盘空间管理的信息）和文件区（存储文件数据）。

2、存储空间的管理方法

盘区：多个连续存放的盘块组成一个盘区

（1）空闲表法

类似动态分区分配的空闲表。空闲表记录空闲盘的起始块号和连续的空闲盘块数，即每个表项记录一个盘区，存储磁盘中的所有空闲块。

• 分配：这种方法适用于连续分配方式，同样可采用首次适应、最佳适应、最坏适应等算法。

• 回收：和动态分区分配也很像，回收时如果前后有空闲区，就进行表项合并

（2）空闲链表法

使用链表的方式连接空闲盘，这又分为两种：

① 空闲盘块链：每个空闲盘块为一个单位，组成链表，每个盘块存储指向下一个盘块的指针。适用于离散分配的结构

• 分配：分配K个盘块时，则从链头依次遍历，摘下K个盘块进行分配，并修改链头指针。

• 回收：回收的盘块依次挂到链尾，并修改链尾指针。

② 空闲盘区链：每个空闲盘区为一个单位，组成链表，每个盘区存储盘区长度和指向下一个盘区的指针。离散分配、连续分配都适用，分配多个盘块时效率更高（摘下一个盘区可以获得多个盘块）。

• 分配：可以用首次适应、最佳适应、最坏适应等算法找到合适大小的空闲盘区并分配，若没有合适的，则可以将不同盘区的盘块同时分配给同一个文件。
• 回收：和之前的空闲表法类似，回收时若空闲区前后相邻，要进行合并；否则单独作为空闲盘区挂到链尾。

（3）位示图法（常考）

用位示图表示盘块是否空闲，每个二进制位表示一个盘块，0代表空闲，1代表已分配。

位示图通常用连续的“字”表示，如下图一个字长16位，每一位对应一个盘块，可以用（字号，位号）表示一个盘块号。

计算块号时，用二维数组的计算方式即可，比如(i,j)对应盘块号b=n*i + j

• 分配：分配K个块时，顺序扫描位示图，找到K个“0”，算出对应盘块号并分配，并将其改为“1”

• 回收：计算出回收的盘块号，将其设为“0”

（4）成组连接法（了解即可）

之前鹅空闲表法、空闲链表法，如果数量大了，链就会很长，检索速度会很慢，因此引入了成组连接法。

成组连接法就将盘块分成多个组，然后通过指针将各个组连接起来。其中每个组第一个盘块是比较特殊的，指向下一组所有的磁盘块。

其中这个1号块是最为特殊的，称之为“超级块”，只有它需要事先调入内存。

在超级块以及每组第一个块中，内部都有一个栈，其中N记录下一组有多少个盘块，然后栈S存储下一组所有的盘块。

• 分配：从超级栈中出栈一个磁盘块并分配，若超级栈此时只剩1个磁盘块，即下一组第一个磁盘块，那么就会将这个磁盘块分配出去，并且将这个磁盘块的栈信息复制到超级栈中。也就相当于少了一组。
• 回收：向超级块中入栈一个磁盘块，若此时超级栈满了，就将这个磁盘块作为新一组的第一个磁盘块，将超级栈信息复制到这个磁盘块中，然后更新超级栈，即把超级栈N设为1，栈第一个元素指向这个磁盘块。也就相当于往头节点插入新一组。

七、文件的基本操作

• 创建文件（create）

  • 在外存中找到文件所需的空间

  • 创建该文件对应的目录项

• 删除文件(delete)

  • 找到文件名对应的目录项

  • 回收文件占用的磁盘块

  • 删除文件对应的目录项

• 打开文件(open)

  • 找到文件名对应的目录项

  • 将目录项复制到内存中的“打开文件表”中，并返回打开文件表的 索引号（文件描述符） 给用户

  • 注意点：

    • 打开文件并不会将文件数据直接读入内存（读文件时才读入内存）
    • 打开文件后，对文件的操作不需要每次都查询目录，可根据内存的打开文件表进行操作
    • 打开文件表分为进程打开文件表和系统打开文件表，每个进程有自己的打开文件表，而系统只有一张总的打开文件表
    • 进程打开文件表特有属性：读写指针、访问权限
    • 系统打开文件表特有属性：打开计数器（记录多少进程打开该文件）

  

• 关闭文件(close)

  • 删除进程的打开文件表对应表项
  • 回收分配给该文件的内存空间等资源
  • 系统文件表的打开计数器-1，若为0，则删除对应表项

• 读文件(read)

  • 从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域

• 写文件(write)

  • 从用户指定的内存区域中，将指定大小的数据写回到写指针指向的外存

八、文件共享

1、基于索引结点的共享方式（硬链接）

目录项的索引节点指针，直接指向文件的索引结点。

索引结点需要一个链接计数器count，记录链接到本结点的用户目录项数。如果count>1，说明多个用户共享此文件。

如果删除文件，则只是把用户目录中的对应目录项删除，并且索引结点count减1，当count=0时系统负责删除文件。

2、基于符号链的共享方式（软链接）

相当于win的快捷方式。这种方式会创建一个Link类型文件，文件中记录了另一个文件的存放路径。

如下图中，User3目录的ccc文件是Link型文件，记录了文件1的存放路径，最终会通过该路径找到文件1的索引结点。

即使软链接指向的共享文件已删除，但是Link文件依然存在，只是查找共享文件时会失败（win的快捷方式失效）

九、文件保护

1、口令保护

为文件设置一个“口令”，用户访问文件时需要提供口令，由系统验证口令是否正确

优缺点：实现开销小，但“口令”一般存放在FCB或索引结点中（即存放在系统中），因此不太安全

2、加密保护

用一个“密码”对文件进行加密，用户访问文件时需要提供相同的“密码”才可以解密

优缺点：保密性强，不需要在系统中存储“密码”，但编码/译码需要花费一定时间

3、访问控制

在每个文件的FCB中增加一个访问控制表（ACL），该表记录了各个用户（或各组用户）可以对该文件执行哪些操作（读/写/执行/删除等）

优点：实现灵活，可以实现复杂的文件保护功能

十、文件系统的层次结构

十一、文件系统布局

1、文件系统在外存的建立

① 物理格式化：即低级格式化——划分扇区，检测坏扇区，并用备用扇区替换坏扇区

② 逻辑格式化：磁盘分区（分卷），完成各个分区的文件系统初始化

2、文件系统在内存中的结构

内存中的内核区存储了目录的缓存、系统打开文件表、进程打开文件表；用户区存储着文件描述符fd/文件句柄

十二、虚拟文件系统（VFS）

虚拟文件系统的特点

• 向上层用户进程提供统一标准的系统调用接口，屏蔽底层具体文件系统的实现差异
• VFS要求下层文件系统必须实现某些规定的函数功能，如open/read/write
• 每打开一个文件，VFS就在主存中新建一个vnode，用统一的数据结构表示文件，无论该文件存储在哪个文件系统

文件系统挂载（mounting）

概念：即文件系统安装——如何将一个文件系统挂载到操作系统（如U盘插入）

文件系统挂载要做的事：

• 在VFS中注册新挂载的文件系统（内存中的挂载表，包含每个文件系统的相关信息）
• 新挂载的文件系统，要向VFS提供一个函数地址列表
• 将新文件系统加到挂载点，也就是将新文件系统挂载到某个父目录下