408操作系统第四章文件管理 文件系统

这是一篇关于408操作系统第四章文件管理 文件系统的思维导图，主要内容有初识文件管理、文件的逻辑结构、文件目录(Windows操作系统的“文件夹”)、文件的物理结构(文件分配方式)。

第四章 文件管理 4.1文件系统基础

• 初识文件管理
  • 文件的定义：一组有意义的信息的集合
  • 文件的属性
    • 文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
    • 标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
    • 类型：指明文件的类型
    • 位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
    • 大小：指明文件大小
    • 创建时间、上次修改时间、文件所有者信息
    • 保护信息：对文件进行保护的访问控制信息
  • 文件内部如何被组织（文件的逻辑结构）
    • 无结构文件（如文本文件）——由一些二进制或字符流组成，又称“流式文件”。
    • 有结构文件（如数据库表）——由一组相似的记录组成，又称“记录式文件”。
    • 数据项：文件系统中最基本的数据单位。
    • 记录：一组相关数据项的集合
  • 文件之间如何被组织（目录结构）
    • 用户可以自己创建一层一层的目录，各层目录中存放相应的文件。系统中的各个文件就通过一层一层的目录合理有序的组织起来。
    • 目录其实也是一种特殊的有结构文件（由记录组成），如何实现文件目录是之后会重点探讨的问题。
    • “目录”其实就是我们熟悉的“文件夹”
  • 操作系统应向上提供的功能
    • 创建文件（create系统调用）：点击新建后，图形化交互进程在背后调用了“create系统调用”。
    • 删除文件（delete系统调用）：点了“删除”之后，图形化交互进程通过操作系统提供的“删除文件”功能，即delete系统调用，将文件数据从外存中删除。
    • 读文件（read系统调用）：将文件数据读入内存，才能让CPU处理（双击后，“记事本”应用程序通过操作系统提供的“读文件”功能，即read系统调用，将文件数据从外存读入内存，并显示在屏幕上）。
    • 写文件（write系统调用）：将更改过的文件数据写回外存（我们在“记事本”应用程序中编辑文件内容，点击“保存”后，“记事本”应用程序通过操作系统提供的“写文件”功能，即write系统调用，将文件数据从内存写回外存）。
    • 打开文件（open系统调用）：读/写文件之前，需要“打开文件”。
    • 关闭文件（close系统调用）：读/写文件结束之后，需要“关闭文件”。
    • 可用几个基本操作完成更复杂的操作，比如：“复制文件”：先创建一个新的空文件，再把源文件读入内存，再将内存中的数据写到新文件中。
  • 文件如何存放在外存中（文件的物理结构）
    • 操作系统以“块”为单位为文件分配存储空间，因此即使一个文件大小只有10B，但它依然需要占用1KB的磁盘块。外存中的数据读入内存时同样以块为单位。
    • 类似于内存分为一个个“内存块”，外存会分为一个个“块/磁盘块/物理块”。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址（如本例中，一块包含2的10次方个地址，即1KB）。同样类似的是，文件的逻辑地址也可以分为（逻辑块号，块内地址），操作系统同样需要将逻辑地址转换为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块的大小。
    • 与内存一样，外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据（如1B）。每个存储单元对应一个物理地址。
  • 操作系统如何管理外存中的空闲块（存储空间的管理）
  • 其他需要由操作系统实现的文件管理功能
    • 文件共享：使多个用户可以共享使用一个文件
    • 文件保护：如何保证不同的用户对文件有不同的操作权限
• 文件的逻辑结构
  • 无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称“流式文件”。如：Windows操作系统中的.txt文件。
  • 有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种。
    • 顺序文件：默认各记录在物理上顺序存储
      • 串结构：记录顺序与关键字无关
      • 顺序结构：记录按关键字顺序排列
      • 可变长记录的顺序文件无法实现随机存取，定长记录可以（可变长记录的顺序文件在每次查询时只能从头依次查找）
      • 定长记录、顺序结构的顺序文件可以快速检索（根据关键字快速找到记录）
      • 最大缺点：不方便增加/删除记录
    • 索引文件
      • 建立一张索引表，每个记录对应一个表项。各记录不用保持顺序，方便增加/删除记录
      • 索引表本身就是定长记录的顺序文件，一个索引表项就是一条定长记录，因此索引文件可支持随机存取
      • 若索引表按关键字顺序排列，则可支持快速检索
      • 解决了顺序文件不方便增删记录的问题，同时让不定长记录的文件实现了随机存取。但索引表可能占用很多空间
    • 索引顺序文件
      • 将记录分组，每组对应一个索引表项
      • 检索记录时先顺序查索引表，找到分组，再顺序查找分组（要会计算平均查找次数）
      • 当记录过多时，可建立多级索引表
• 文件目录（Windows操作系统的“文件夹”）
  • 文件目录的实现
    • FCB的有序集合称为“文件目录”，一个FCB就是一个文件目录项。
    • FCB中包含了文件的基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。
    • 最重要，最基本的还是文件名、文件存放的物理地址。
    • 需要对目录进行的操作？ 搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项； 创建文件： 创建一个新文件时，需要在其所属的目录中增加一个目录项 ； 删除文件：当删除一个文件时，需要在目录中删除相应的目录项； 显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性； 修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）
  • 目录结构
    • 单级目录结构：早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。
      • 单级目录实现了“按名存取”，但是不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适用于多用户操作系统。
    • 两级目录结构：早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。
      • 允许不同用户的文件重名。文件名虽然相同，但是对应的其实是不同的文件。也可以在目录上实现实现访问限制（检查此时登录的用户名是否匹配）。但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。
    • 多级（树形）目录结构
      • 用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。
        • 例如：自拍.jpg的绝对路径是“/照片/2015-08/自拍.jpg”系统根据绝对路径一层一层地找到下一级目录。刚开始从外存读入根目录的目录表；找到“照片”目录的存放位置后，从外存读入对应的目录表；再找到“2015-08”目录的存放位置，再从外存读入对应目录表；最后才找到文件“自拍.jpg”的存放位置。整个过程需要3次读磁盘I/O操作。很多时候，用户会连续访问同一目录内的多个文件（比如：接连查看“2015-08”目录内的多个照片文件），显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。
        • 例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前出发的“相对路径”。引入“当前目录”和“相对路径”后，磁盘I/O的次数减少了。这就提升了访问文件的效率。
      • 树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护。但是，树形结构不便于实现文件的共享。为此，提出了“无环图目录结构”。
    • 无环图目录结构
      • 在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
      • 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。需要为每个共享结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的FCB、并使共享计数器减1，并不会直接删除共享结点。只有共享计数器减为0时，才删除结点。
      • 注意：共享文件不同于复制文件。在共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。
  • 索引结点：除了文件名之外的所有信息都放到索引结点中，每个文件对应一个索引节点。
    • 目录项中只包含文件名、索引结点指针，因此每个目录项的长度大幅减少
    • （理解）由于目录项长度减少，因此每个磁盘块可以存放更多个目录项，因此检索文件时磁盘I/O的次数就少了很多
• 文件的物理结构（文件分配方式）
  • 文件块、磁盘块
    • 类似于内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。内存与磁盘之间的数据交换（即读/写操作、磁盘I/O）都是以“块”为单位进行的。即每次读入一块，或每次写出一块。
    • 在内存管理中，进程的逻辑地址空间被分为一个一个页面同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为了一个一个的文件“块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
    • 若块的大小是1KB，则1MB大小的文件可以被分为1K个块； 操作系统为文件分配存储空间都是以块为单位的； 用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。
  • 连续分配：连续分配方式要求每个文件在磁盘上占有一组连续的块。
    • 优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快。缺点：不方便文件拓展；存储空间利用率低，会产生磁盘碎片。
  • 链接分配：采取离散分配的方式，可以为文件分配离散的磁盘块。
    • 隐式链接：除文件的最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。
      • 优点：很方便文件拓展，不会有碎片问题，外存利用率高。缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。（考试题目中遇到未指明隐式/显式的“链接分配”，默认指的是隐式链接的链接分配。）
    • 显式链接：把用于链接文件各物理块的指针显式地存放在一张表中，即文件分配表（FAT，File Allocation Table）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并常驻内存。
      • 优点：很方便文件拓展，不会有碎片问题，外存利用率高，并且支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件的访问效率更高。缺点：文件分配表的需要占用一定的存储空间。
  • 索引分配：索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。若文件太大，索引表项太多，可以采取以下三种方法：
    • ①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。 缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。
    • ②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。 缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。
    • ③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。 优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。
    • 超级超级超级重要考点
      • ①要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；
      • ②要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件——顶级索引块是否已调入内存）

第四章 文件管理

• 4.1文件系统基础
  • 文件的基本操作
    • 创建文件：分配外存空间，创建目录项
    • 删除文件：回收外存空间，删除目录项
    • 打开文件
      • 将目录项中的信息复 制到内存中的打开文件表中，并将打开文件表的索引号返回给用户。（打开文件时并不会把文件数据直接读入 内存。“索引号” 也称“文件描述符）
      • 打开文件之后，对文件的操作不再需要每次都查询目录，可以根据内存中的打开文件表进行操作
      • 每个进程有自己的打开文件表，系统中也有一张总的打开文件表
      • 进程打开文件表中特有的属性:读写指针、访问权限(只读?读写? )
      • 系统打开文件表中特有的属性:打开计数器(有多少个进程打开了该文件)
    • 关闭文件
      • 将进程打开文件表中的相应表项删除
      • 系统打开文件表的打开计数器减1，若打开计数器为0，则删除系统表的表项
    • 读文件：根据读指针、读入数据量、内存位置将文件数据从外存读入内存（“ 读/写文件”用“文件描述符”即可指明文件，不再需要用到“文件名”）
    • 写文件：根据写指针、 写出数据量、内存位置将文件数据从内存写出外存
  • 文件共享：操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件
    • 基于索引结点的共享方式（硬链接）
      • 各个用户的目录项指向同一个索引结点
      • 索引结点中需要有链接计数count
      • 某用户想删除文件时，只是删除该用户的目录项，且count--
      • 只有count == 0时才能真正删除文件数据和索引结点，否则会导致指针悬空
    • 基于符号链的共享方式（软链接）
      • 在一个Link型的文件中记录共享文件的存放路径(Windows 快捷方式)
      • 操作系统根据路径一层层查找目录，最终找到共享文件
      • 即使软链接指向的共享文件已被删除，Link 型文件依然存在，只是通过Link型文件中的路径去查找共享文件会失败(找不到对应目录项)
      • 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此用软链接访问共享文件的速度要比硬链接更慢
  • 文件保护
    • 口令保护
      • 为文件设置一个“口令"， 用户想要访问文件时需要提供口令，由系统验证口令是否正确
      • 实现开销小，但"口令"一般存放在FCB或索引结点中（也就是存放在系统中）因此不太安全
    • 加密保护
      • 用一个"密码”对文件加密，用户想要访问文件时，需要提供相同的"密码"才能正确的解密
      • 安全性高，但加密/解密需要耗费一定的时间（Eg: 异或加密）
    • 访问控制
      • 如果对某个目录进行了访问权限的控制，那也要对目录下的所有文件进行相同的访问权限控制
      • 用一个访问控制表(ACL) 记录各个用户(或各组用户)对文件的访问权限
      • 对文件的访问类型可以分为：读/写/执行/删除等
      • 实现灵活，可以实现复杂的文件保护功能
• 4.3 文件系统
  • 文件系统的层次结构（408大纲不考察）
    • 例：假设某用户请求删除文件“D:/工作目录/学生信息.xIsx”的最后100条记录。
      • 1.用户需要通过操作系统提供的接口发出上述请求——用户接口
      • 2.由于 用户提供的是文件的存放路径，因此需要操作系统一层一层地查找目录，找到对应的目录项——文件目录系统
      • 3.不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限——存取控制模块(存取控制验证层)
      • 4.验证了用户的访问权限之后，需要把用户提供的“记录号”转变为对应的逻辑地址——逻辑文件系统与文件信息缓冲区
      • 5.知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址——物理文件系统
      • 6.要删除这条记录，必定要对磁盘设备发出请求——设备管理程序模块
      • 7.删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收——辅助分配模块
  • 文件系统的全局结构（布局）
    • 原始磁盘
      • 物理格式化：即低级格式化——划分扇区，检测坏扇区，并用备用扇区替换坏扇区
      • 逻辑格式化：磁盘分区（分卷Volume），完成各分区的文件系统初始化
    • open系统调用打开文件的背后过程
      • ①根据路径一级一级读入目录
      • ②找到目标文件的FCB，复制到系统打开文件表
      • ③在进程打开文件表中新建一个条目，并返回文件描述符