王道操作系统___第四章01

4.1_1_初识文件管理

• 文件的属性：文件名、标识符、类型、位置、创建时间、上次修改时间、文件所有者信息、保护信息。

• 文件内部数据的组织形式：无结构文件(由一系列二进制或字符流组成)，有结构文件(由一系列记录组成，每条记录又有若干数据项)。

• 文件之间的组织：用户可以自己创建一层一层的目录，各层目录中存放相应的文件。系统中的各个文件就通过一层一层的目录合理有序的组织起来。

• 操作系统向上层提供的功能：

  • 创建文件：点击新建后，图形化交互进程在背后调用了create系统调用
  • 读文件：双击后，记事本应用程序通过操作系统提供的读文件功能，即read系统调用，将文件数据从外存读入内存，这样数据才能被CPU处理，并将数据显示到屏幕上。
  • 写文件：记事本应用程序通过操作系统提供的写文件功能，即write系统调用，将文件数据从内存写回外存。
  • 删除文件：图形化交互进程通过操作系统提供的删除文件功能，即delete系统调用，将文件数据从外存中删除。
  • 打开文件(open系统调用)，关闭文件(close系统调用)：读写文件前需要打开文件，读写文件结束之后需要关闭文件。

• 文件存放在外存的组织形式：

  • 外存也是由一个个存储单元组成的，每个存储单元可以存储一定量的数据。每个存储单元对应一个物理地址。
  • 外存会分为一个个快/磁盘块/物理块。每个磁盘块的大小是相等的，每块一般包含2的整数幂个地址。
  • 文件的逻辑地址可以分为(逻辑块号，块内地址)，操作系统同样需要将逻辑地址转换为外存的物理地址(物理块号，块内地址)的形式。块内地址的位数取决于磁盘块的大小。

• 文件共享：使多个用户可以共享使用一个文件、文件保护：如何保证不同的用户对文件有不同的操作权限。

4.1_2_文件的逻辑结构

• 逻辑结构指在用户看来，文件内部的数据应该是如何组织起来的。而物理结构指在操作系统看来数据是如何存放在外存的。
• 有结构文件的逻辑结构：顺序文件、索引文件、索引顺序文件。

顺序文件

• 文件中的记录一个接一个地顺序排列(逻辑上)，记录可以是定长的或可变长的，各个记录在物理上可以顺序存储或链式存储。
• 串结构：记录之间的顺序与关键字无关，顺序结构：记录之间的顺序按关键字顺序排列。

索引文件

• 索引表本身是定长记录的顺序文件，因此可以快速找到第i个记录对应的索引项。
• 可以将关键字作为索引号的内容，若关键字顺序排列，则还可以支持按照关键字折半查找。
• 每当要增加/删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此主要用于对信息处理的及时性要求比较高的场合。

索引顺序文件

• 是索引文件和顺序文件思想的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是：并不是每个记录对应一个索引表项，而是一组记录对应一个索引表项。
• 索引顺序文件的索引项也不需要按关键字顺序排列，这样可以极大地方便新表项的插入。

4.1_3_文件目录

文件控制块

• 目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个放在该目录下的文件。
• 目录文件中的一条记录就是一个文件控制块(FCB)，FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。FCB最重要，最基本还是文件名和文件存放的物理地址。
• FCB实现了文件名和文件之间的映射。使用户程序可以实现按名存取
• 对目录的操作：搜索、创建文件、删除文件、显示目录、修改目录。

目录结构

• 单级目录结构：早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。单级目录实现了按名存取，但是不允许文件重名。其并不适用多用户操作系统
• 两级目录结构：分为主文件目录和用户文件目录。主文件目录记录用户名及相应用户文件目录的存放位置。用户文件目录由该用户的文件FCB组成。允许不同用户的文件重名。但仍缺乏灵活性不能对自己的文件进行分类。
• 多级目录结构：也叫树形目录结构，不同目录下的文件可以重名，各级目录用 “/” 隔开。用户要访问某个文件时要用文件路径名标识文件。从根目录出发的路径称为绝对路径，从当前目录出发的路径称为相对路径。树形目录结构不便于实现文件的共享。
• 无环图目录结构：在树形目录结构的基础上，增加一些指向同一个节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。
  • 可以用不同的文件名指向同一个文件，甚至可以指向同一个目录
  • 需要为每一个节点设置一个共享计数器，用于记录此时有多少个地方在共享该节点。
  • 用户提出删除节点的请求时，只是删除该用户的FCB，并使共享计数器减1，并不会直接删除共享节点。只有共享计数器减为0时，才删除节点。

索引节点

• 除了文件名之外的文件描述信息都放到索引节点处，来简化目录表，提升文件检索速度。
• 当找到文件名对应的目录项时，才需要将索引节点调入内存，索引节点中记录了文件的各种信息，包括文件在外存中的存放位置，根据存放位置即可找到文件。

4.1_4_文件的物理结构上

文件快、磁盘块

• 磁盘中的存储单元也会被分为一个个快/磁盘块/物理块。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。
• 在内存管理中，进程的逻辑地址空间被分为一个一个页面，同样的在外存管理中，为了方便对文件数据进行管理，文件的逻辑地址空间也被分为一个一个的文件快。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
• 操作系统为文件分配存储空间都是以快为单位的，用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射。

文件分配方式

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

  • 逻辑地址–>物理地址：只需要转换块号就行，块内地址保持不变。
  • 用户要给出要访问的逻辑块号，操作系统找到该文件对应的目录项：物理块号 = 起始块号 + 逻辑块号 。
  • 文件目录中记录存放的起始块号和长度。连续分配支持顺序访问和直接访问。
  • 读取某个磁盘块时，需要移动磁头。访问的两个磁盘块越远，移动磁头所需时间就越长。连续分配的文件在顺序读/写时速度最快。
  • 物理上采用连续分配的文件不方便拓展。存储空间利用率低，会产生难以利用的磁盘碎片。

• 连接分配采用离散分配的方式，可以为文件分配离散的磁盘块。分为隐式链接和显示链接两种。

• 隐式链接

  • 目录中记录了文件存放的起始块号和结束块号。
  • 除了文件的最后一个磁盘块外，每个磁盘块中都会保存指向下一个磁盘块的指针，这些指针对用户是透明的。
  • 采用链式分配(隐式链接)方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。
  • 方便文件的拓展，所有空闲的磁盘块都可以被利用，不会有碎片问题，外存利用率高。

• 显式链接

  • 目录中只需记录文件的起始块号
  • 把用于连接文件各物理块的指针显式地存放在一张表中，即文件分配表FAT。
  • 一个磁盘仅设置一张FAT。开机时将FAT读入内存，并常驻内存。FAT的各个表项在物理上连续存储，且每一个表项长度相同，因此物理块号字段可以是隐含的。
  • 逻辑块号转换为物理块号的过程不需要读磁盘操作。
  • 支持顺序访问，也支持随机访问，由于块号转移的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快的多。

4.1_4_文件的物理结构下

索引分配

• 索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一个索引表，索引表中记录了文件的各个逻辑快对应的物理块。索引表存放的磁盘块称为索引快。文件数据存放的磁盘块称为数据块。目录中需要记录文件的索引块是几号磁盘块。
• 查找过程：从目录项中可知索引表存放的位置，将索引表从外存读入内存，并查找索引表即可知i号逻辑块在外存中的存放位置。索引分配方式可支持随机访问，文件拓展也很容易，但是索引表需要占用一个索引空间。
• 如何解决一个磁盘块装不下整张索引表
  • 连接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。想要找到i号磁盘块，必须先依次读入0~i-1号索引快，这就导致磁盘I/O次数过多，查找效率底下。
  • 多层索引：原理类似于多级页表。使第一层索引快指向第二层索引块，还可根据文件的大小建立第三层、第四层索引快。若采用多级索引，则各级索引表的大小不能超过一个磁盘块。采用K级索引结构，且顶级索引表为调入内存，则访问一个数据块只需要K+1次读磁盘操作。即使是小文件，访问一个数据块仍然需要K+1次读磁盘。
  • 混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引，又包含一级间接索引，还包含两级索引。对于小文件来说，访问一个数据块所需读磁盘操作更少。

4.1_5_文件存储空间管理

• 存储空间的划分：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘）
• 存储空间的初始化：将各个文件卷划分为目录区和文件区。
• 目录区主要存放文件目录信息(FCB)、用于磁盘存储空间管理的信息。文件区用于存放文件数据。

存储空间管理—空闲表法

• 分配磁盘块：为一个文件分配连续的存储空间，同样可采用首次适应、最佳适应、最坏适应等算法来决定要为文件分配哪个区间。
• 回收磁盘块：回收时需要注意表项的合并问题。
• 空闲盘块表：第一列为第一个空闲盘块号，第二列为空闲盘块数。

存储空间管理—空闲链表法

• 空闲盘块链：以盘块为单位组成一条空闲链。空闲盘块中存储着下一个空闲盘块的指针
  • 操作系统保存着链头、链尾指针
  • 若某个文件申请K个盘块，则从链头开始依次摘下K个盘块分配，并修改空闲链的链头指针
  • 回收的盘块依次挂到链尾，并修改空闲链的链尾指针。
  • 适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作。
• 空闲盘区链：以盘区为单位组成一条空闲链。空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针。
  • 操作系统保存着链头、链尾指针
  • 若某个文件申请K个盘块，则可以采用首次适应、最佳适应算法，从链头开始索引，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针，盘区大小等数据。
  • 若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。
  • 离散分配、连续分配都适用，为一个文件分配多个盘块时效率更高。

存储空间管理—位示图法

• 每个二进制位对应一个盘块。位示图一般用连续的字来表示，字中的每一位代表一个盘快。
• 若文件需要K各块，顺序扫描位示图，找到K个相邻或不相邻的0。根据字号、位号算出对应的盘块号，将相应的盘块分配给文件，将相应的位设置为1。
• 根据回收的盘块号计算出对应的字号、位号；将相应的二进制位设为0。

存储空间管理—成组链接法

• 文件卷的目录区中专门用一个磁盘块作为超级快，当系统启动时需要将超级快读入内存。并且要保证内存与外存中的超级快数据一致。
• 分配：检查第一个分组的块数是否足够。分配第一个分组中的空闲块，并修改相应的数据。

4.1_6_文件的基本操作

• 创建文件：create系统调用需要提供的主要参数：所需的外存空间大小，文件存放路径，文件名。
• 操作系统在处理create系统调用时做的工作：在外存中找到文件所需的存储空间。根据文件的存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。
• 删除文件：delete系统调用需要提供的主要参数：文件存放路径，文件名
• 操作系统在处理delete系统调用时做的工作：根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项。根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。从目录表中删除文件对应的目录项。
• 打开文件：open系统调用的参数：文件存放路径，文件名，要对文件的操作类型。
• 根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，并检查该用户是否有指定的操作权限。将目录项复制到内存中的打开文件表中。并将对应表目的编号返回给用户。之后用户使用打开文件表的编号来指明要操作的文件。
• 打开文件时并不会把文件数据直接读入内存。内存中有两种打开文件表系统的打开文件表(打开计数器)和进程的打开文件表(读写指针、访问权限)，系统打开文件表包含了所有正在被使用的信息，进程打开文件表只包含了这个进程打开的文件信息。
• 关闭文件：close系统调用做的工作：将进程的打开文件表相应表项删除。回收分配给该文件的内存空间等资源。系统打开文件表的打开计数器减1，若count=0，则删除对应表项。
• 读文件：read系统调用：需要指明是哪个文件，还需要指明要读入多少数据，指明读入的数据要放在内存中的什么位置。
• 操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。
• 写文件：write系统调用：需要指明是哪个文件，还需要指出要写出多少数据，写回外存的数据放在内存中的什么位置。
• 操作系统会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

4.1_7_文件共享

基于索引节点的共享方式—硬链接

• 索引节点中设置一个连接计数器count，用于表示链接到本索引节点上的用户目录数。
• 各个用户的目录项指向同一个索引节点
• 若某用户想删除文件时，只是删除该用户的目录项，且count–
• 只有count==0时才能真正删除文件数据和索引节点，否则会导致指针空悬。

基于符号链的共享方式—软链接

• Link类型的文件，操作系统会根据其中记录的路径层层查找目录。
• 在一个Link型的文件中记录共享文件的存放路径
• 即使软连接指向的共享文件已被删除，Link型文件依然存在，只是通过Link型文件中的路径去查找共享文件时会失败
• 由于用软链接的方式访问共享文件时要查询多级目录，会有多次磁盘I/O，因此访问速度较硬链接慢。

4.1_8_文件保护

口令保护

• 为文件设置一个口令，用户请求访问该文件时必须提供口令
• 口令一般存放在文件对应的FCB或索引节点中。用户访问文件前需要先输入口令，操作系统会将用户提供的口令与FCB中存储的口令进行对比，如果正确，则允许该用户访问文件
• 优点：保存口令的空间开销不多，验证口令的时间开销也很小。
• 缺点：正确的口令存放在系统内部，不够安全。

加密保护

• 使用某个密码对文件进行加密，在访问文件时需要提供正确的密码才能对文件进行正确的解密。
• 优点：保密性强、不需要再系统中存储密码
• 缺点：编码/译码，或者说加密/解密需要花费一定的时间。

访问控制

• 在每个文件的PCB中增加一个访问控制列表，该表中记录了各个用户可以对该文件执行的哪些操作。
• 有的计算机可能会有很多用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题。
• 精简的访问列表：以组为单位，标记各组用户可以对文件执行哪些操作。当用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。

4.1_9_文件系统的层次结构

• 用户接口：用于处理用户发出的系统调用请求(Read、Write、Open、Close等系统调用)。文件系统需要向上层的用户提供一些简单易用的功能接口
• 文件目录系统：用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引节点。所有和目录、目录项相关的管理工作都在本层完成。
• 存取控制模块：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能。
• 逻辑文件系统与文件信息缓冲区：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址。
• 物理文件系统：这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址。
• 辅助分配模块：负责文件存储空间的管理，即负责分配和回收存储空间
• 设备管理模块：直接与硬件交互，负责和硬件直接相关的一些管理工作。