【第八章 | 文件管理】《操作系统 慕课版》课后答案 + 复习

文章目录

【第八章】文件管理

| 本章概念

1.文件和文件系统

• 数据项、记录和文件- 数据项：基本数据项：描述一个对象的某种属性；组合数据项：由若干个基本数据项组成如结构体- 记录：记录是一组相关数据项的集合，用于描述一个对象在某方面的属性；关键字：唯一能标识一个记录的数据项- 文件：具有文件名的一组相关元素的集合- 数据项 < 记录 < 文件
• 文件- 文件在文件系统中文件是最大的数据单位，描述了一个对象集- 文件的主要属性：类型、长度、物理位置、建立时间- 扩展名：文件名后面的若干个附加字符，用于表示文件类型- 文件分类：按用途（系统文件、用户文件、库文件）、数据的形式（源文件、目标文件、可执行文件）、存取控制属性（只执行文件、只读文件、读写文件）、组织形式和处理方式分类（普通文件、目录文件、特殊文件）
• 文件系统的层次结构
• 文件系统的功能- 对文件存储空间的管理- 对文件目录的管理- 用于将文件的逻辑地址转换为物理地址的机制- 对文件读和写的管理- 对文件的共享和保护
• 与文件系统有关的软件- I/O控制层：文件系统最底层，设备驱动程序层- 基本文件系统层：处理内存和磁盘之间数据块的交换- 基本I/O管理程序：完成与磁盘I/O有关的事务- 逻辑文件系统：处理与记录和文件相关的操作
• 文件操作- 最基本的文件操作：创建、删除、读写、设置文件的读写位置- 打开open：系统将文件从外存拷贝到内存打开文件表的一个表目中- 关闭close：把文件从打开文件表的表目中删除- 其它操作：重命名、改文件拥有者、查询文件状态、创建 / 删除目录

2.文件的逻辑结构

• 文件结构 - 文件的逻辑结构：从用户观点所观察的文件组织形式- 文件的物理结构：文件的存储结构，指系统将文件存储在外存上所形成的一种存储组织形式- 不仅与存储介质的存储性能有关，还与所采用的外存分配方式有关- 文件的逻辑结构和物理结构，都影响文件的检索速度
• 文件逻辑结构的类型 - 按有结构文件分类：定长记录、边长记录- 按无结构文件分类：源程序、可执行文件、库函数- 按文件的组织方式分类（针对有结构文件而言）：顺序文件、索引文件、索引顺序文件、直接文件、哈希文件

下面介绍文件的组织方式分类

• 顺序文件- 串结构：按存入时间的先后排序，记录间的顺序与关键字无关（检索比较费时）- 顺序结构：指定一个字段为关键字，所有记录按关键字排序- 检索时可利用有效的查找算法，折半查找法、插值查找法、 跳步查找法等- 优点：有利于大批记录读写、存取效率最高、可存储在顺序存储设备（磁带）上- 缺点：查找或修改单个记录：差；增加或删除一个记录：难- 顺序文件记录寻址：定长记录的地址 = Ai = i*L ；变长记录的地址 = Σ Lk + i
• 索引文件- 按关键字建立索引：为变长记录文件建立一张索引表、索引表按关键字排序、实现直接存取- 具有多个索引表的索引文件：为顺序文件建立多个索引表、为每一个可能成为检索条件的域配置一张索引表
• 索引顺序文件- 有效克服了变长记录文件不便于直接存取的缺点- 保留了顺序文件的关键特征：记录按关键字的顺序组织- 新增2个新特征：引入文件索引表：实现随机访问。增加溢出文件：记录新增、删除和修改的记录。
• 索引顺序文件的【一级索引文件】组织方式- 如果在一个顺序文件中所含有的记录数为N，则为检索到具有指定关键字 的记录，平均须查找N/2个记录对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只要查找 sqrt(N) 个记录数，因而其检索效率比顺序文件约提高sqrt(N)/2倍- 其具体的建立方法是① 首先将变长记录顺序文件中的所有记录分为若干个组， 如50个记录为一个组。② 然后为顺序文件建立一张索引表，并为每组中的第一个记录在索引表中建立一个索引项，其中含有该记录的关键字和指向该记录的指针。索引顺序文件是最常见的一种逻辑文件形式
• 索引顺序文件的【二级索引文件】组织方式：平均查找记录数为： (3/2)(N)^(1/3)
• 直接文件：关键字本身决定了记录的物理地址；键值转换：关键字到记录物理地址的转换
• 哈希文件：利用Hash函数将记录键值转换为记录的地址

3.文件目录

• 目录是一种数据结构
• 对目录管理的要求：实现“按名存取”、提高对目录的检索速度、文件共享、允许文件重名
• 文件控制块和索引结点- 目的：为了保证对一个文件进行正确的存取- 文件控制块(FCB)：管理和控制文件的数据结构，与文件一一对应- 文件目录：文件控制块的集合，即一个文件控制块就是一个文件目录项- 目录文件：文件目录也被看做是一个文件
• 文件控制块包含的信息：- 基本信息类：文件名、文件物理位置、文件逻辑结构、文件物理结构- 存取控制信息类：文件主的存取权限、核准用户的存取权限以及一般用户的 存取权限- 使用信息类：文件的建立日期和时间、文件上一次修改的日期和时间及当前 使用信息
• 索引结点- 索引结点的引入：目的是为了减少磁盘访问次数（把文件名与文件描述信息分开，文件描述信息用索引结点（iNode）保存， 简称为i节点（UNIX））- 磁盘索引结点：存放在磁盘上的索引结点（①文件拥有者标识符，②文件类型， ③文件存取权限， ④文件物理地址， ⑤文件长度， ⑥文件连接计数，⑦文件存取时间）- 内存索引结点：存放在内存上的索引结点（①索引节点编号，②状态， ③访问计数， ④文件所属文件系统的逻辑设备号 ⑤链接指针）
• 目录结构- 目录结构和文件都驻留在磁盘上- 单级文件目录：所有用户的文件都在同一目录中，最简单的文件目录。目录项：文件名、扩展名、文件长度、文件类型、物理地址、文 件说明以及其他文件属性缺点：查找速度慢、不允许重名、不便于实现文件共享- 两级文件目录：每个用户有自己的目录结构优点：提高了检索目录的速度，不同用户可 以有相同的文件名，不同用户可以使用不同文件名访问同一个共享文件缺点：不便于共享文件- 树形结构目录：路径名 – 从根目录到任何数据文件的通路优点：明显提高对目录的检索速度、更加有效地进行文件管理和保护- 无环图目录结构：有共享的子目录和文件
• 目录操作：创建、移动、链接、查找、改变、删除
• 目录查询技术：线性检索法、Hash方法

4.文件共享

• 基于有向无环图实现共享 - 有向无环图：树形目录中，允许一个文件有多个父目录- 利用索引结点实现共享，设置链接计数count
• 利用符号链接实现共享 - 基本思想：允许一个文件有多个父目录，但其中仅有一个作为主父目录， 其它的都是通过符号链接方式与之相链接。- 优点： 不会发生在文件拥有者删除一个共享文件后留下一个悬空指针的情况。- 缺点： 每次访问共享文件时都可能要多次地读盘，这使每次访问文件的开销甚大，且增加了启动磁盘的频率。

| 本章算法

1.检索具有指定关键字记录的【平均查找次数】计算

假设文件中所含有的记录数为N

顺序文件：检索到具有指定关键字的记录平均须查找 N/2 次

一级索引顺序文件：检索到具有指定关键字的记录平均要查找 sqrt(N) 次

二级索引顺序文件：检索到具有指定关键字的记录平均要查找 (3/2)(N)^(1/3) 次

2.FCB与磁盘访问次数的相关计算

例题1

【单级文件目录】

所需盘块数量 = FCB大小*目录项的大小 / 一个盘块的大小

磁盘访问次数 = （所需盘块数量 + 1）/2 向上取整

例题2

【引入了索引的文件目录】

所需盘块数量 = FCB大小 x (文件名大小 + 索引结点编号大小) / 一个盘块的大小

磁盘访问次数 = （所需盘块 + 1）/2 + 1 （因为在得到索引编号后，还需要启动磁盘，将对应文件的索引节点读入内存，因此要额外 + 1）

| 课后简答题

1．何谓数据项、记录和文件?

①数据项是最低级的数据组织形式，可分为基本数据项和组合数据项。基本数据项是描述一个对象某种属性的字符集，是数据组织中可以命名的最小逻辑数据单位，又称为数据元素或字段。组合数据项是若干个基本数据项所构成的数据项。

②记录是一组相关数据项的集合，用于描述一个对象某方面的属性。

③文件是由创建者定义的、具有文件名的一组相关信息的集合。

2.一个比较完善的文件系统应具备哪些功能?

①文件存储空间管理。通过文件存储空间管理，能使文件“各得其所”，并且能尽量提高文件存储空间的利用率。

②目录管理。通过目录管理，能实现文件“按名存取”，提高文件的检索速度，解决文件的命名冲突问题(允许文件重名），并能实现文件共享。

③文件读/写管理。通过文件读/写管理，可以实现文件数据的快速读/写。

④文件安全性管理。通过采取多级文件保护等措施，可以实现对系统中文件的保护，防止文件被偷窃、修改和破坏。

⑤用户接口管理。文件系统向用户提供一个统–的、方便使用的接口，用户通过该接口可以方便地获得如文件存取、创建、删除、修改等文件管理服务。

3．为什么在大多数OS中都引入了“打开”这一文件系统调用?打开的含意是什么?

①当用户要求对一个文件实施多次读/写或者其他操作时，每次都要从检索目录开始。为了避免多次重复检索目录，在大多数OS中都引人了“打开”这一文件系统调用，当用户第–次请求对某文件进行操作时,须先利用open系统调用将该文件打开。

②所谓"打"开”，是指系统将指定文件的属性(包括该文件在外存上的物理位置)从外存复制到内存中已打开文件表的一个表目中，并将该表目的编号(或称索引号)返回给用户。“打开”就是在用户和指定文件之间建立起一个连接。此后，用户通过该连接可直接得到文件信息，避免了再次通过目录检索文件，即当用户再次向系统发出文件操作请求时，系统可根据用户提供的索引号直接在已打开文件表中查找到文件信息。这样不仅节省了检索开销，而且提高了文件操作速度。如果用户不再对该文件实施操作，则可以利用“关团”系统调用来关闭此文件，即断开此连接，此时，OS将会把该文件从已打开文件表的表目中删除。

4．什么是文件的逻辑结构?逻辑文件有哪几种组织形式?

①文件的逻辑结构是指从用户的角度出发所观察到的文件组织形式，也就是用户可以直接处理的数据及其结构。

②逻辑文件根据其结构可分为两种:

一种是无结构的流式文件，是指文件信息由一串字符流构成;

另一种是有结构的记录式文件，是指将文件信息按照在逻辑上独立的含义划分为信息单位，每个信息单位称为一个逻辑记录(简称记录)。

5．如何提高变长记录顺序文件的检索速度?

为了提高变长记录顺序文件的检索速度，可建立一张索引表，以主文件中每条记录的长度及指向对应记录的指针（即该记录在逻辑地址空间的起始地址）为表项的内容。由于索引表是一个定长记录的顺序文件，其可实现方便快速的直接存取。但是，如果文件较大，则可建立多级索引以提高检索效率。

6.什么是“按名存取”?文件系统如何实现文件的按名存取?

①“按名存取”指用户只要给出文件名就能存取外存空间中的文件信息而不必给出文件的具体物理地址。

②文件系统实现文件按名存取的步骤为:首先利用用户提供的文件名，检索文件目录中该文件的FCB ( file control block，文件控制块）或索引节点;然后根据FCB中的文件物理地址，将文件读入内存。

8.目前广泛采用的目录结构是哪种?它有什么优点?

目前广泛采用的目录结构是多级树形目录，它具有以下优点。
(1）能有效提高对目录的检索速度。假定文件系统中有N个文件，在单级目录中，最多要检索N个日录项:但对于i级树形目录，在目录中每检索一个指定的文件，最多可能要检索ix √N项。
(2）允许文件重名。在树形结构的文件系统中，不仅允许每个用户在自己的分目录中使用与其他用户的文件相同的名字，而且允许同一个用户的不同分目录中的文件重名。
(3）便于实现文件共享。在树形目录中，用户可通过路径名共享他人的文件;也可将共享文件链接到自己的目录下实现共享,实现方式是系统在用户目录中增设一个目录项，并在其中填上用户赋予共享文件的新文件名，以及该共享文件的唯一标识符(或索引节点编号)
(4）能更有效地进行文件的管理和保护。在多级目录中，用户可按文件性质的不同，将它们存放到不同的子目录中，并且可以赋子各目录不同的存取权限,因此，能更有效地管理和保护文件。

9．试说明在树形目录中线性检索法的检索过程,并画出相应的流程图。

在树形目录中，用户提供的是从根目录(或当前目录）开始的、由多个文件分量名所组成的文件路径名。系统在检索一个文件时:

①系统读人给定文件路径名中的第一个文件分量名，用它与根目录(或当前目录)文件中各目录项的文件名进行顺序比较，若能找到匹配的目录项，则在它的FCB或索引节点编号中找到对应的文件;

②系统读入第二个文件分量名，用它与刚检索到的目录文件中的各目录项文件名进行顺序比较、若能找到匹配者，则重复上述过程;

③如此逐级检索指定文件的分量名，最后将会得到指定文件的FCB或索引节点编号。

10．在树形目录中，利用链接方式共享文件有何好处?

利用链接方式共享文件主要有以下几方面的好处。

(1）方便用户。此共享方式允许用户将共享文件链接到自己的子目录下，并赋予它新的文件名，方便用户管理和使用共享文件。

(2)可防止共享文件被任意删除。每次链接时，系统对索引节点中的链接计数字段i_nlink执行加1操作;删除时，先对该字段执行减I操作，只有当i_nlink值为0时，共享文件才会被真正删除,因此可防止共享文件被任意删除。

(3)可加快检索速度。为了加快检索文件的速度，一般系统都引入了当前目录。若共享文件已被链接到当前目录下，则系统无须再逐级检索目录，进而提高了检索速度。