操作系统第四章

519次阅读

没有评论

共计 17837 个字符，预计需要花费 45 分钟才能阅读完成。

文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。

标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。

类型：指明文件的类型。

位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）。

大小：指明文件大小。

创建时间、上次修改时间、文件所有者信息。

保护信息：对文件进行保护的访问控制信息。

无结构文件：（如文本文件）由一些二进制或字符流组成，又称 “流式文件”

有结构文件：（如数据库表）由一组相似的记录组成，又称 “记录式文件”（记录是一组相关数据项的集合）

用户可以自己创建一层层目录，各层目录中存放相应的文件。目录也是一种特殊的有结构文件（由记录组成）

可以 “创建文件”，（点击新建后，图形化交互进程在背后调用 “create 系统调用”）

可以 “读文件”，将文件数据读入内存，才能让 CPU 处理（双击后，应用程序通过 “read 系统调用，将文件数据从外存读入内存，并显示在屏幕上）

可以 “写文件”，将更改过的文件数据写回外存（在应用程序编辑文件内容，保存后，应用程序将通过 “write 系统调用”，将文件数据从内存写回外存）

可以 “删除文件”（点击 “删除” 之后，图形化交互进程通过操作系统提供的 “delete 系统调用”，将文件数据从外存中删除）

操作系统以 “块” 为单位分配存储空间，因此及时一个文件大小只有 10B，依然需要占用 1KB 的磁盘块。外存中的数据读入内存时间同样以块为单位。

类似于内存分为一个个 “内存块”，外存会分为一个个 “块 / 磁盘块 / 物理块”。每个磁盘块的大小是相等的，每块一般包含 2 的整数幂个地址。同样类似的是，文件的逻辑地址页可以分为（逻辑块号，块内地址），操作系统同样需要将逻辑地址转换为外存的物理地址（物理块号，块内地址）的形式。块内地址的位数取决于磁盘块的大小。

与内存一样，外存也是一个个存储单元组成的，每个存储单元可以存储一定量的数据。每个存储单元对应一个物理地址。

按文件是否有结构分类，可以分为无结构文件、有结构文件两种。

无结构文件：文件内部的数据就是一系列二进制流或字符流组成。又称 “流式文件”。如 .txt 文件。

有结构文件：由一组相似的记录组成，又称 “记录式文件”。每条记录由若干个数据项组成。如数据库表文件。一般来说，每条记录有一个数据项可作为 关键字。根据各条记录的长度（占用的存储空间）是否相等，又可分为 定长记录 和 可变长记录 两种。

顺序文件：文件中的记录一个接一个的顺序排列（逻辑上），记录可以是定长的或 可变长的。各个记录在物理上可以 顺序存储 或 链式存储。

顺序存储–逻辑上相邻的记录，物理上也相邻（类似于顺序表）

链式存储–逻辑上相邻的记录，物理上不一定相邻（类似于链表）

结论：定长记录的顺序文件，若物理上采取顺序存储，则可实现随机存取；若能再保证记录的顺序结构，则可实现快速检索（即根据关键字快速找到对应记录）

注：一般来说，题目中的 “顺序文件”，指的是 物理上顺序存储的顺序文件。

可见，顺序文件的缺点是 增加 / 删除一个记录比较困难（如果是串结构则相对简单）

索引表 本身是 定长记录的顺序文件。因此可以快速找到第 i 个记录对应的索引项。

可将关键字作为索引号内容，若按关键字顺序排列，则还可以支持按照关键字折半查找。

每当要增加 / 删除一个记录时，需要对索引表进行修改。由于索引文件有很快的检索速度，因此 主要用于对信息处理的及时性要求比较高的场合。

另外，可以用不用的数据项建立多个索引表。如：学生信息表中，可用关键字 “学号” 建立一张索引表。也可用 “姓名” 建立一张索引表。这样就可用 “姓名” 快速检索文件。

索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。比如：文件的每个记录平均只占 8B，而每个索引表项占 32 个字节，那么索引表比文件本身大 4 倍，存储空间利用率太低了。

索引顺序文件是索引文件和顺序文件的结合。索引顺序文件中，同样会为文件建立一张索引表，但不同的是，并不是每个记录对应一个索引表项，而是 一组记录对应一个索引表项。

在此例中，学生记录按照学生姓名的开头字母进行分组。每个分组就是一个顺序文件，分组内的记录不需要按关键字排序。

若一个 顺序文件 有10000个记录，则根据关键字检索文件，只能从头开始顺序查找（这里指的并不是定长记录、顺序结构的顺序文件），平均查找 5000 个记录。

若采用 索引顺序文件 结构，可把 10000 个记录分为 √10000 = 100 组，每组 100 个记录。则需要先顺序查找索引表找记录（每个分组 100 个记录，因此平均需要查 50 次）。可见，采用索引顺序文件结构后，平均查找次数减少为 50 + 50 = 100 次。

同理，若文件共有 10^6 个记录，则可分为 1000 个分组，每个分组 1000 个记录。根据关键字检索一个记录，平均需要查找 500 + 500 = 1000 次。这个查找次数依旧很多，如何解决？

为了进一步提高检索效率，可以为顺序文件 建立多级索引表。例如，对于一个含 10^6 个记录文件，可先为该文件建立一张低级索引表，每 100 个记录为一组，故低级索引表中共有 10000 个表项（即 10000 个定长记录），再把这 10000 个定长记录分组，每组 100 个，为其建立顶级索引表，故顶级索引表中共有 100 个表项。

我们双击 “照片” 后，操作系统会在这个目录表中找到关键字 “照片” 对应的目录项（也就是记录），然后从外存中将 “照片” 目录的信息读入内存，于是，“照片”目录中的内容就可以显示出来了。

FCB 的有序集合称为 “文件目录”，一个 FCB 就是一个文件 目录项。FCB 中包含了文件的 基本信息（文件名、物理地址、逻辑结构、物理结构等），存取控制信息（是否可读 / 可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）。最重要，最基本的 还是 文件名、文件存放的物理地址。（FCB 实现了文件名和文件之间的映射。使用户（用户程序）可以实现 “按名存取”）

需要对目录进行哪些操作？

搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项。

创建文件： 创建一个新文件时，需要在其所属的目录中增加一个目录项。

删除文件： 当删除一个文件时，需要在目录中删除相应的目录项。

显示目录： 用户可以请求显示目录的内容，如显示该目录中所有文件及相应属性。

修改目录： 某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

早期操作系统并不支持多级目录，整个系统中只建立一张目录表，每个文件占一个目录项。

单级目录实现了 “按名存取”，但是 不允许文件重名。

在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。

显然，单级目录结构不适用于多用户操作系统。

早期的多用户操作系统，采用两级目录结构。分为 主文件目录 和 用户文件目录。

两级目录结构 允许不同用户的文件重名，也可以在目录上实现访问限制（检查此时登录的用户名是否匹配）。但是两级目录结构依然缺乏灵活性，用户不能对自己的文件进行分类。

用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径是个字符串。各级目录之间用 “ / ” 隔开。从根目录触发 的路径称为 绝对路径。

系统根据绝对路径一层层找到下一级目录。刚开始 从外存读入根目录的目录表；找到 “照片” 目录的存放位置后，从外存读入对应的目录表；再找到 “2015-08” 目录的存放位置，再 从外存读入对应目录表；最后才找到对应文件的存放位置。整个过程 需要 3 次读磁盘 I / O 操作。

很多时候，用户会连续访问同一目录内的多个文件，故每次都从根目录开始查找，是很低效的。因此可以设置一个 “当前目录”。从当前目录出发查询到的文件存放位置即为 “相对路径。

引入 “当前目录” 和 “相对路径” 后，磁盘 I / O 的次数减少了，就提升了访问文件的效率。

树形目录结构 可以很方便的对文件进行分类，层次结构清晰，也能够更有效的进行文件的管理和保护。但是，树形结构 不便于实现文件的共享。为此，提出了 “无环图目录结构。

可以用不同的文件名指向同一个文件，甚至可以指向同一个目录（共享同一目录下的所有内容）。

需要为 每个结点设置一个共享计数器，用于记录此时有多少个地方在共享该结点。用户提出删除结点的请求时，只是删除该用户的 FCB、并使 共享计数器减 1，并不会直接删除共享结点。

注意：共享文件不同于复制文件。在 共享文件中，由于各用户指向的是同一个文件，因此只要其中一个用户修改了文件数据，那么所有用户都可以看到文件数据的变化。

有何好处：

假设一个 FCB 是64B,磁盘块的大小为 1KB，则每个盘块中只能存放 16个 FCB。若一个文件目录中共有 640 个目录项，则共需要占用 640 / 16 = 40 个盘块。因此按照某文件名检索该目录，平均需要查询 320 个目录项，平均需要启动磁盘 20 次（每次磁盘 I / O 读入一块）。

若 使用索引结点机制，文件名占 14B，索引结点指针占 2B，则每个盘块可存放 64 个目录项，那么按文件名检索目录 平均只需要读入 320 / 64 = 5 个磁盘块。显然，这将 大大提升文件检索速度。

当找到文件名对应的目录项时，才需要将索引结点调入内存，索引结点中记录了文件的各种信息，包括文件在外存中的存放位置，根据 “存放位置” 即可找到文件。

存放 在外存中 的索引结点称为 “磁盘索引结点”，当索引结点 放入内存 后称为 “内存索引结点”。相比之下 内存索引结点中需要增加一些信息，比如：文件是否被修改、此时有几个进程正在访问该文件等。

类似于内存分页，磁盘中的存储单元也会被分为一个个 “块 / 磁盘块 / 物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。

内存与磁盘之间的数据交换（即读 / 写操作、磁盘 I / O）都是以 “块”为单位进行的。即每次读入一块，或每次写出一块。

在内存管理中，进程的逻辑地址空间被分为一个个页面，同样的，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分为一个个的文件 “块”。于是文件的逻辑地址也可以表示为 （逻辑块号，块内地址） 的形式。

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

用户通过逻辑地址来操作自己的文件，操作系统如何实现从逻辑地址到物理地址的映射？

（逻辑块号，块内地址） => （物理块号，块内地址）。只需要转换块号即可，块内地址保持不变。

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）… 物理块号 = 起始块号 + 逻辑块号，还需哟啊验证用户提供的逻辑块号是否合法（逻辑块号 ≥ 长度就不合法）

优点一：

可以直接算出逻辑块号对应的物理块号，因此 连续分配支持顺序访问和直接访问（即随机访问）

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需的时间就越长。

优点二：

连续分配的文件在顺序读 / 写时速度最快。

若此时文件 A 要拓展，需要再增加一个磁盘块（总共需要连续的 4 个磁盘块）。由于采用连续结构，因此文件 A 占用的磁盘块必须是连续的。

因此只能将文件 A 全部 “迁移” 到绿色区域。

缺点一：

物理上采用 连续分配的文件不方便拓展。

缺点二：

物理上采用 连续分配，存储空间利用率低，会产生难以利用的磁盘碎片。

可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

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

优点：支持顺序访问和直接访问（即随机访问）；连续分配的文件在顺序访问时速度最快。

缺点： 不方便文件拓展；存储空间利用率低，会产生磁盘碎片

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

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号，操作系统找到该文件对应的目录项（FCB）…

从目录项中找到起始块号（即 0 号块），将 0 号逻辑块读入内存，因此知道 1 号逻辑块存放的物理块号，于是读入 1 号逻辑块，再找到 2 号逻辑块的存放位置…以此类推。

因此读入 i 号逻辑块，总共需要 i + 1 次磁盘 I / O。

结论：采用 链式分配（隐式链接） 方式的文件，只支持顺序访问，不支持随机访问，查找效率低。另外，指向下一个盘块的指针也需要耗费少量的存储空间。

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的 FCB。

结论：采用隐式链接的 链接分配方式，很方便文件拓展。另外，所有空闲磁盘块都可以被利用，不会有碎片问题，外存利用率高。

显式链接 把用于链接文件个物理块的指针显示的存放在一张表中，即 文件分配表（FAT）。

假设某个新创建的文件 “aaa” 依次存放在磁盘块 2 => 5 => 0 => 1

假设某个新创建的文件 “bbb” 依次存放在磁盘块 4 => 23 => 3

注意：一个磁盘仅设置一张 FAT。开机时，将 FAT 读入内存，并常驻内存。FAT 的各个表项在物理上连续存储，且每一个表项长度相同，因此 “物理块号” 字段可以是隐含的。

如何实现文件的逻辑块号到物理块号的转变？

用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项 FCB…

从目录项中找到起始块号，若 i > 0，则查询内存中的文件分配表 FAT，往后找到 i 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

结论：采用 链式分配（显示链接） 方式的文件，支持顺序访问，也 支持随机访问，由于块号转换过程不需要访问磁盘，因此相比于隐式链接来说，访问速度也快很多。

显然，显示链接也 不会产生外部碎片，也可以很方便的对文件进行拓展。

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

隐式链接–除文件最后一个盘块之外，每个盘块中都存有指向下一个盘块的指针。文件目录包括文件第一块的指针和最后一块的指针。

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

缺点： 只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针也需要耗费少量的存储空间。

显式链接：把用于链接文件个物理块的指针显示的存放在一张表中，即 文件分配表（FAT）。一个磁盘只会建立一张文件分配表。开机时文件分配表放入内存，并 常驻内存。

优点： 很方便文件拓展，不会有碎片问题，外存利用率高，并且 支持随机访问。相比于隐式链接来说，地址转换时不需要访问磁盘，因此文件访问效率更高。

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

索引分配 允许文件离散地分配在各个磁盘块中，系统会 为每个文件建立一张索引表，索引表中 记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页之间的映射关系）。索引表存在的磁盘块称为 索引块。文件数据存放的磁盘块称为 数据块。

假设某个新创建的文件 “aaa” 的数据依次存放在磁盘块 2 => 5 => 13 => 9。7号磁盘块作为 “aaa” 的索引块，索引块中保存了索引表的内容。

注：在显示链接的链式分配方式中，文件分配表 FAT 是一个磁盘对应一张。而索引分配方式中，索引表示一个文件对应一张。而索引分配方式中，索引表是一个文件对应一张。

可以用固定的长度表示物理块号（如：假设磁盘总容量为 1TB = 2^40 B，磁盘块大小为 1KB，则共有 2^30 个磁盘块，则可用 4B 表示磁盘块号），因此，索引表中的 “逻辑块号” 可以是隐含的。

如何实现文件的逻辑块号到物理块号的转换？

用户给出要访问的逻辑块号 i，操作系统找到该文件对应的目录项（FCB）…

从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只 i 号逻辑块在外存中的存放位置。

可见，索引分配方式可以支持随机访问。文件拓展也很容易实现（只需要给文件分配一个空闲块，并增加一个索引表项即可）但是 索引表需要占用一定的存储空间。

若每个磁盘块 1KB，一个索引表项 4B，则一个磁盘块只能存放 256 个索引项。
如果一个文件的大小超过了 256 块，那么一个磁盘块是装不下文件的整张索引表的，如何解决这个问题？

如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。

假设磁盘块大小为 1KB，一个索引表项占 4B，则一个磁盘块只能存放 256 个索引项。若一个文件大小为 256*256KB = 65,536 KB = 64 MB。

该文件共有 256 * 256 个块，也就对应 256 * 256 个索引项，也就需要 256 个索引块来存储，这些索引块用链接方案连起来。

若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块（第 256 个索引块），而各个索引块之间是用指针链接起来的，因此必须先顺序的读入前 255 个索引块。

建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。

假设磁盘块大小为 1KB，一个索引表项占 4B，则一个磁盘块只能存放 256 个索引项。

若某文件采用 两层索引，则该 文件的最大长度 可以到 256 * 256 * 1KB = 65,536 KB = 64 MB，可根据逻辑块号算出应该查找索引表中的哪个表项。如：要访问 1026 号逻辑块，则 1026 / 256 = 4，1026 % 256 = 2。

因此可以先将一级索引表调入内存，查询 4 号表项，将其对应的二级索引表调入内存，再查询二级索引表的 2 号表项，即可知道 1026 号逻辑块存放的磁盘块号了。访问目标数据块，需要 3 次磁盘 I / O。（采用 K 层索引结构，且 顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作）。

若采用 三层索引，则 文件的最大长度为 256 * 256 *256 *1KB = 16 GB，类似的，访问目标数据块，需要 4 次磁盘 I / O。

多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含 直接地址索引（直接指向 数据块），又包含 一级简介索引（指向单层索引表）、还包含 两级间接索引（指向两层索引表）。

若顶级索引表 还没读入内存：

访问 0~7 号逻辑块：两次读磁盘（对于小文件，只需较少的读磁盘次数就可以访问目标数据块。）
访问 8~263：三次读磁盘
访问 264~65799：四次读磁盘

这种结构的索引支持的最大文件长度为 65800 KB。

索引分配 允许文件离散的分配在各个磁盘块中，系统会 为每个文件建立一张索引表，索引表中 记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表–建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为 索引块。文件数据存放的磁盘块称为 数据块。

若文件太大，索引表项太多，可以采取以下三种方法解决：

链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到 i 号索引块，必须先依次读入 0~i-1 号索引块，这就导致磁盘 I / O 次数过多，查找效率低下。
多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用 K 层索引结构，且 顶级索引表未调入内存，则访问一个数据块只需要 K + 1 次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要 K + 1 次读磁盘。
混合索引：多种索引分配方式的结合。例如一个文件的顶级索引表中，即包含 直接地址索引（直接指向数据块），又包含 一级间接索引（指向单层索引表）、还包含 两级间接索引（指向两层索引表）。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

考点：

要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）。
要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB 中会存有指向顶级索引块的指针，因此可以根据 FCB 读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外要注意 顶级索引块是否已调入内存）

如何分配磁盘块：与内存管理中的动态分区分配类似，为一个文件 分配连续的存储空间。同样可采用 首次适应、最佳适应、最坏适应 等算法来决定要为文件分配哪个区间。

如何回收磁盘块：与内存管理中的动态分区分配类似，当回收某个存储区时，有四种情况：

回收区的前后都没有相邻空闲区
回收区的前后都是空闲区
回收区的前面是空闲区
回收区的后面是空闲区

总之，回收时需要注意表项的合并问题

操作系统保存着 链头、链尾指针。

如何分配：若某文件申请 K 个盘块，则从链头开始依次摘下 K 个盘块分配，并修改空闲链的链头指针。

如何回收：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。（适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作）

操作系统保存着 链头、链尾指针。

如何分配：若某文件申请 K 个盘块，则可以采用首次适应、最佳适应等算法，从链头开始检索，按照算法规则找到一个大小符合要求的空闲盘区，分配给文件。若没有合适的连续空闲块，也可以将不同盘区的盘块同时分配给一个文件，注意分配后可能要修改相应的链指针、盘区大小等数据。

如何回收：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，则将回收区作为单独的一个空闲盘区挂到链尾。（离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高）

位示图：每个二进制位对应一个盘块。在本例中，“0” 代表盘块空闲，“1” 代表盘块已分配。位示图一般用连续的 “字” 来表示，如本例中一个字的 字长是 16 位，字中的每一位对应一个盘块。因此 可以用（字号，位号）对应一个盘块号。有的题目也描述为 （行号，列号）。

要能自己推出盘块号与（字号，位号）相互转换的公式。

注意题目条件：盘块号、字号、位号 是从 0 还是从 1 开始，本例从 0 开始，若 n 表示字长，则：

（字号，位号）=（i，j）的二进制位对应的 盘块号 b = ni + j

b 号盘块对应的 字号 i = b / n，位号 j = b % n

（0，1） => b = 16 * 0 + 1 = 1

（1,10） => b = 16 * 1 + 10 = 26

b = 13 => i = 13 / 16 = 0，j = 13 % 16 = 13

b = 31 => i = 31 / 16 = 1，j = 31 % 16 = 15

注意：

若盘块号从 1 开始，行列号（字号与位号）从 0 开始，则：
盘块号 b = ni + j + 1

字号 i = (b-1) / n

位号 j = (b -1) % n
若盘块号从 0 开始，行列号从 1 开始，则：
盘块号 b = n(i – 1) + j – 1

字号 i = b / n + 1

位号 j = b % n + 1

如何分配：若文件需要 K 个块：

顺序扫描位示图，找到 K 个相邻或不相邻的 “0”
根据字号、位号算出对应的盘块号，将相应盘块分配给文件
将相应位设置为 “1”

如何回收：

根据回收的盘块号计算出对应的字号、位号
将相应二进制位设为 “0”

空闲表法、空闲链表法不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX 系统中采用了 成组链接法 对磁盘空闲块进行管理。

文件卷的目录区 中专门用一个磁盘块作为 “超级块”，当系统启动时需要将 超级块读入内存，并且要保证内存与外存中的 “超级块” 数据一致。

如何分配：

EG 1 :需要一个空闲块
1. 检查第一个分组的块数是否足够。1 < 100，因此是足够的。
2. 分配第一个分组中的 1 个空闲块，并修改相应数据。
EG 2 :需要 100 个空闲块
1. 检查第一个分组的块数是否足够。100 = 100，足够。
2. 分配第一个分组中的 100 个空闲块。但是 由于 300 号块内存放了再下一组的信息，因此 300 号块的数据需要复制到超级块中。

如何回收：

EG：假设每个分组最多为 100 个空闲块，此时第一个分组已有 100 个块，还要再回收一块。需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

“创建文件”（点击新建后，图形化交互进程在背后调用了 “create 系统调用）

进行 Create 系统调用时，需要提供的几个主要参数：

所需的外存空间大小（如：一个盘块，即 1KB）
文件存放路径（“D:/Demo）
文件名

操作系统在处理 Create 系统调用时，主要做了两件事：

在外存中找到文件所需的空间（结合上节空间链表法、位示图、成组链接法等管理策略，找到空闲空间）
根据文件存放路径的信息找到该目录对应的目录文件，在目录中 创建该文件对应的目录项。目录项中包含了文件名、文件在外存中的存放位置等信息。

“删除文件”（点击删除后，图形化交互进程通过操作系统提供的 “删除文件” 即delete 系统调用，将文件数据从外存中删除）

进行 Delete 系统调用时，需要提供的几个主要参数：

文件存放路径（“D:/Demo）
文件名

操作系统在处理 Delete 系统调用时，主要做了几件事：

根据文件存放路径找到相应的目录文件，从目录中 找到文件名对应的目录项。
根据该目录项记录的文件在外存的存放位置、文件大小等信息，回收文件占用的磁盘块。（回收磁盘块时，根据空闲表法、空闲链表法、位图法等管理策略的不同做不同处理）
从目录表中 删除文件对应的目录项。

在很多操作系统中，在对文件进行操作之前，要求用户先使用 open 系统调用 “打开文件”，需要提供的几个主要参数：

文件存放路径
文件名
要对文件的操作类型（如：r 只读；rw 读写等）

操作系统在处理 open 系统调用时，主要做了几件事：

根据文件存放路径找到相应的目录文件，从目录中 找到文件名对应的目录项，并检查该用户是否有指定的操作权限。
将目录项复制到内存中的 “打开文件表” 中。并将对应表目的编号返回给用户。之后 用户使用打开文件的编号来指明要操作的文件。

进程使用完文件后，要 “关闭文件”

操作系统在处理 Close 系统调用时，主要做了几件事：

将进程的打开文件表相应表项删除
回收分配给该文件的内存空间等资源
系统打开文件表的打开计数器 count 减一，若 count = 0，则删除对应表项

“读文件”，将文件数据读入内存，才能让 CPU 处理（双击后，应用程序通过操作系统提供的 “读文件” 即 read 系统调用，将文件数据从外存读入内存，并显示在屏幕上）

进程使用 read 系统调用完成读操作。需要指明是哪个文件（在支持 “打开文件” 操作系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据（如：读入 1KB）、指明读入的数据要放在内存中的什么位置。

操作系统在处理 read 系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存数据中。

“写文件”，将更改过的文件数据写回外存（编辑文件内存，点击 “保存” 后，应用程序通过操作系统提供的 “写文件” 即 write 系统调用，将文件数据从内存写回外存）

进程使用 write 系统调用完成写操作。需要指明是哪个文件（在支持 “打开文件” 操作系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如：写出 1KB）、指明写回外存的数据要放在内存中的什么位置。

操作系统在处理 write 系统调用时，会从用户指定的内存区域中，将指定大小的数据写回指针指向的外存。

注意： 多个用户共享同一个文件，意味着系统中只有 “一份” 文件数据。并且只要某个用户修改了该文件的数据，其他用户也可以看到文件数据的变化。

如果是多个用户 “复制” 了同一个文件，那么系统中会有 “好几份” 文件数据，其中一个用户修改了自己那份文件数据，对其他用户文件数据没有影响。

回顾：索引结点，是一种文件目录的瘦身策略。由于检索文件时只需用到文件名，因此可以将除了文件名之外的其他信息放到索引结点中。这样目录项只需要包含文件名、索引结点指针。

索引结点中设置一个链接计数变量 count，用于表示链接到本索引结点上的用户目录项数。

若 count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。

若某个用户决定 “删除” 该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的 count 值减 1。

当 User3 访问 “ccc” 时，操作系统判断文件 “ccc”属于 Link 类型文件，于是会根据其中记录的路径层层查找目录，最终找到 User1 的目录表中的 “aaa” 表项，于是找到了文件 1 的索引结点。

为文件设置一个 “口令”（如： abc123），用户请求访问该文件时必须提供 “口令”。

口令一般存放在文件对应的 FCB 或索引结点中，用户访问文件前需要先输入 “口令”，操作系统会将用户提供的口令与 FCB 中存储的口令进行对比，若正确，则允许访问。

优点：保存口令的空间开销不多，验证口令的时间开销也很小。

缺点：正确的 “口令” 存放在系统内部，不够安全。

使用某个 “密码” 对文件进行加密，在访问文件时需要提供正确的 “密码” 才能对文件进行正确的解密。

Eg：一个最简单的加密算法–异或加密

假设用于加密 / 解密的 “密码” 为 “01001”

优点：保密性强，不需要在系统中存储 “密码”

缺点：编码 / 译码，需要花费一定时间。

在每个文件的 FCB（或索引结点）中增加一个 访问控制列表，该表中记录了各个用户可以对该文件执行哪些操作。

有的计算机可能会有多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题。

精简的访问列表：以 “组” 为单位，标记各 “组” 用户可以对文件执行哪些操作。如：分为系统管理员、文件主、文件主的伙伴、其他用户几个分组。当某用户想要访问文件时，系统会检查该用户所属的分组是否有相应的访问权限。（系统需要管理分组的信息）

若想要让某个用户能够读取文件，只需要把该用户放入 “文件主的伙伴” 这个分组即可。

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

一个例子辅助记忆文件系统的层次结构：

假设某用户请求删除文件 “D:/工作目录/学生信息.xlsx” 的最后 100 条记录。

用户需要通过操作系统提供的接口发出上述请求 —— 用户接口
由于用户提供的是文件的存放路径，因此需要操作系统一层层查找目录，找到对应的目录项 —— 文件目录系统
不同的用户对文件有不同的操作权限，因此为了保证安全，需要检查用户是否有访问权限 —— 存取控制模块（存取控制验证层）
验证了用户的访问权限后，需要把用户提供的 “记录号” 转变为对应的逻辑地址 —— 逻辑文件系统与文件信息缓冲区
知道了目标记录对应的逻辑地址后，还需要转换成实际的物理地址 —— 物理文件系统
要删除这条记录，必定要对磁盘设备发出请求 —— 设备管理程序模块
删除这些记录后，会有一些盘块空闲，因此要将这些空闲盘块回收 —— 辅助分配模块

磁盘的表面由一些磁性物质组成，可以用这些磁性物质来记录二进制数据。

需要把 “磁头” 移动到想要读 / 写的扇区所在的通道。磁盘会转起来，让目标扇区从磁头下面划过，才能完成对扇区的读 / 写操作。

=

可用 （柱面号，盘面号，扇区号） 来定位任意一个 “磁盘块”。在 “文件的物理结构” 小节中，我们曾提到文件数据存放在外存中的几号块，这个块号就可以转换成（柱面号，盘面号，扇区号）的地址形式。

可根据该地址读取一个 “块”

根据 “柱面号” 移动磁臂，让磁头指向指定柱面。
激活指定盘面对应的磁头。
磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读 / 写。

盘片可以更换的称为 可换盘磁盘
盘片不可更换的称为 固定盘磁盘

寻找时间（寻道时间） Ts：在读 / 写数据前，将磁头移动到指定磁道所花的时间。

启动磁头臂 是需要时间的。假设耗时为 s；
移动磁头 也需要时间。假设磁头匀速移动，每跨越一个磁道耗时为 m，总共需要跨越 n 条磁道。则：寻道时间 Ts = s + m * n

延迟时间 Tr：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为 r（单位：转 / 秒，或转 / 分），则 平均所需的延迟时间 Tr = (1 / 2) * (1 / r) = 1 / (2r)（ 1 / r 就是转一圈需要的时间。找到目标扇区平均需要转半圈，因此再乘以 1 / 2）

传输时间 Tt：从磁盘读出或项磁盘写入数据所经历的时间，假设磁盘转速为 r，此次读 / 写的字节数为 b，每个磁道上的字节数为 N。则：传输时间 Tt = (1 / r) * (b / N)= b / (rN)（每个磁道要可存 N 字节的数据，因此 b 字节的数据需要 b / N 个磁道才能存储。而读 / 写一个磁道所需的时间刚好又是转一圈所需要的时间 1/r ）

总的平均存取时间 Ta = Ts + 1/ (2r) + b / (rN)

延迟时间和传输时间都与磁盘转速相关，且为线性相关。而转速是硬件的固有属性，因此操作系统也无法优化延迟时间和传输时间，但是操作系统的 磁盘调度算法会直接影响寻道时间。

根据进程请求访问磁盘的先后顺序进行调度。

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

按照 FCFS 的规则，按照请求到达的顺序，磁头需要依次移动到 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 45 + 3 + 19 + 21 + 72 + 70 + 10 + 112 + 146 = 498 个磁道

响应一个请求平均需要移动 498 / 9 = 55.3 个磁道（平均寻找长度）

优点：公平，如果请求访问的磁道比较集中，算法性能还算可以。

缺点：如果有大量进程竞争使用磁盘，请求访问的磁道很分散，则 FCFS 在性能上很差，寻道时间长。

SSTF 算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是不能保证总的寻道时间最短。

假设磁头的初始位置是 100 号磁道，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 (100-18) + (184-18) = 248 个磁道

响应一个请求平均需要移动 248 / 9 = 27.5 个磁道（平均寻找长度）

优点：性能较好，平均寻道时间短。

缺点：可能产生 “饥饿” 现象。

Eg：本例中，如果在处理 18 号磁道的访问请求时又来了一个 38 号磁道的访问请求，处理 38 号磁道的访问请求时又来了个 18 号磁道的访问请求。如果有源源不断的 18 号、38 号磁道的访问请求到来的话，150、 160、 184 号磁道的访问请求就永远得不满足，从而产生 “饥饿” 现象。（产生饥饿的原因在于：磁头在一个小区域内来回的移动）

SSTF 算法会产生 “饥饿” 现象，为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是 扫描算法 的思想。由于磁头的移动方式很像电梯，因此也叫 电梯算法。

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且 此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 (200 – 100) + (200 -18) = 282 个磁道

响应一个请求平均需要移动 282 / 9 = 31.3 个磁道（平均寻找长度）

优点：性能较好，平均寻道时间较短，不会产生饥饿现象

缺点：

只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往有移动磁头了。
SCAN 算法 对于各个位置磁道的响应频率不平均（如：假设此时磁头正在往右移动，且刚处理过 90 号磁道，那么下次处理 90 号磁道的请求就需要等磁头移动很长一段距离；而响应了 184 号磁道的请求之后，很快又可以再次响应 184 号磁道的请求了）

扫描算法（SCAN） 中，只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往右移动磁头了。LOOK 调度算法 就是为了解决这个问题，如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向。（边移动边观察，因此叫做 LOOK）

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且 此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 (184 – 100) + (184 – 18) = 250 个磁道

响应一个请求平均需要移动 250 / 9 = 27.5 个磁道（平均寻找长度）

优点：比起 SCAN 算法，不需要每次都移动到最外侧或最内侧才改变侧头方向，使寻道时间进一步缩短。

SCAN 算法对于各个位置磁道的响应频率不平均，而 C-SCAN 算法 就是为了解决这个问题。规定只有磁头朝某个特定的方向移动时才处理磁道访问请求，而 返回时直接快速移动至起始端而不处理任何请求。

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且 此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 (200 – 100) + (200 – 0) + (90 – 0) = 390 个磁道

响应一个请求平均需要移动 390 / 9 = 43.3 个磁道（平均寻找长度）

优点：比起 SCAN，对于各个位置磁道的响应频率很平均。

缺点：只有到达最边上的磁道时才能改变磁头移动方向，事实上，处理了 184 号磁道的访问请求之后就不需要再往右移动磁头了；并且，磁头返回时其实只需要返回到 18 号磁道即可，不需要返回到最边缘的磁道。另外，比起 SCAN 算法来，平均寻道时间更长。

C-SCAN 算法的主要缺点是只有到达最边上的磁道时才能改变磁头移动方向，并且磁头返回时不一定需要返回到最边缘的磁道上。C-LOOK 算法就是为了解决这个问题。如果磁头移动的方向上已经没有磁道访问请求了，就可以立即让磁头返回，并且磁头只需要返回到有磁道访问请求的位置即可。

假设某磁盘的磁道为 0~200 号，磁头的初始位置是 100 号磁道，且 此时磁头正在往磁道号增大的方向移动，有多个进程先后陆续的请求访问 55、 58、 39、 18、 90、 160、 150、 38、 184 号磁道。

磁头总共移动了 (184 – 100) + (184 – 18) + (90 – 18) = 322 个磁道

响应一个请求平均需要移动 322 / 9 = 35.8 个磁道（平均寻找长度）

优点：比起 C-SCAN 算法来，不需要每次都移动到最外侧或最内侧才改变磁头方向，使寻道时间进一步缩短。

假设要连续读取橙色区域的 2、 3、 4 扇区：

磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停的旋转

因此，如果2、 3 号扇区相邻着排列，则读完 2 号扇区后无法连续不断的读入 3 号扇区，必须等盘片继续旋转，3 号扇区再次划过磁头，才能完成扇区读入。

结论：磁头读入一个扇区数据后需要一小段时间处理，如果逻辑上相邻的扇区在物理上也相邻，则读入几个连续的逻辑扇区，可能需要很长的 “延迟时间”。

若采用交替编号的策略，即让逻辑上相邻的扇区在物理上有一定的间隔，可以使读取连续的逻辑扇区所需要的延迟时间更小。

为什么磁盘的物理地址是（柱面号，盘面号，扇区号）而不是（盘面号，柱面号，扇区号）？

假设某磁盘有 8 个柱面 / 磁道（假设最内侧柱面 / 磁道号为 0），4 个盘面，8 个扇区。则可用 3 个二进制位表示柱面，2 个二进制位表示盘面，3 个二进制位表示扇区。

若物理地址结构是（盘面号，柱面号，扇区号），且需要连续读取物理地址 (00,000,000) ~ (00,001,111) 的扇区：

(00,000,000) ~ (00,000,111) 转两圈可读完，之后再读取物理地址相邻的区域，即：

(00,001,000) ~ (00,001,111)，需要启动磁头臂，将磁头移动到下一个磁道

若物理地址结构是（柱面号，盘面号，扇区号），且需要连续读取物理地址 (000,00,000) ~ (000,01,111) 的扇区：

(000,00,000) ~ (000,00,111) 由盘面 0 的磁头读入数据之后再读取物理地址相邻的区域，即：

(000,01,000) ~ (000,01,111)，由于柱面号 / 磁道号相同，只是盘面不同，因此不需要移动磁头臂。只需要激活相邻盘面的磁头即可

结论：读取地址连续的磁盘块时，采用（柱面号，盘面号，扇区号）的地址结构可以减少磁头移动消耗的时间。

磁盘初始化：

Step 1：进行 低级格式化（物理格式化），将磁盘的各个磁道 划分为扇区。一个扇区通常可分为头、数据区域（如 512 B 大小）、尾三个部分。管理扇区所需要的各种数据结构一般存放在头、尾两个部分，包括扇区校验码（如奇偶校验、CRC 循环冗余校验码等，校验码用于校验扇区中的数据是否发生错误）

Step 2：将磁盘分区，每个分区由若干柱面组成（即分为 C、 D 、E 盘等）

Step 3：进行 逻辑格式化，创建文件系统。包括创建文件系统的根目录、初始化存储空间管理所用的数据结构（如：位示图、空闲分区表）

计算机开机时需要进行一系列初始化的工作，这些初始化工作是通过执行 初始化程序（自举程序） 完成的。

ROM：初始化程序可以放在 ROM（只读存储器）中。ROM 中的数据在出厂时就写入了，并且 以后不能再修改。

若需要更新自举程序，将很不方便，因为 ROM 中的数据无法更改，如何解决？

ROM 中只存放很小的 “自举装入程序”，开机时计算机先运行 “自举装入程序”，通过执行该程序就可找到引导块，并将完整的 “自举程序” 读入内存，完成初始化。

完整的自举程序放在磁盘的启动块（即引导块 / 启动分区）上，启动块位于磁盘的固定位置。拥有启动分区的磁盘称为 启动磁盘 或 系统磁盘（C 盘）

坏了、无法正常使用的扇区就是 “坏块”。这属于硬件故障，操作系统是无法修复的。应该将坏块标记出来，以免错误的使用到他。

对于简单的磁盘，可以在逻辑格式化时（建立文件系统时）对整个磁盘进行坏块检查，标明哪些扇区是坏扇区，比如：在 FAT 表上标明。（在这种方式中，坏块对操作系统不透明）

对于复杂的磁盘，磁盘控制器（磁盘设备内部的一个硬件部件）会维护一个坏块链表。在磁盘出厂前进行低级格式化（物理格式化）时就将坏块链进行初始化。会保留一些 “备用扇区”，用于替换坏块。这种方案称为 扇区备用。且这种处理方式中，坏块对操作系统透明。

正文完

操作系统计算机基础

发表至：操作系统

2022-09-22

0

转载提示：此文章非本站原创文章，若需转载请联系原作者获得转载授权。

操作系统第三章

操作系统 第四章

初识文件管理

一、前情回顾

二、文件的属性

三、文件内部数据应怎样组织起来

四、操作系统应该向上提供哪些功能

五、从上往下看，文件应如何存放在外存

总结

文件的逻辑结构

一、无结构文件

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

1.顺序文件

2.索引文件

3.索引顺序文件

索引顺序文件–检索效率分析

4.多级索引顺序文件

总结

文件目录

一、文件控制块

二、目录结构

1.单级目录结构

2.两级目录结构

3.多级目录结构

4.无环图目录结构

三、索引结点（FCB 的改进）

总结

文件的物理结构（文件分配方式）*

一、文件块、磁盘块

二、文件分配方式

1.连续分配

连续分配总结

2.链接分配

隐式链接

显式链接

链接分配总结

3.索引分配

1.链接方案

2.多层索引

3.混合索引

索引分配总结

总结

文件存储空间管理*

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

二、存储空间管理

1.空闲表法

2.空闲链表法

空闲盘块链

空闲盘区链

3.位示图法

4.成组链接法

总结

文件的基本操作

一、创建文件

二、删除文件

三、打开文件

四、关闭文件

五、读文件

六、写文件

总结

文件共享

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

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

总结

文件保护

一、口令保护

二、加密保护

三、访问控制

总结

文件系统的层次结构

总结回顾

磁盘的结构

一、磁盘、磁道、扇区

二、如何在磁盘中读 / 写数据

三、盘面、柱面

四、磁盘的分类

总结

磁盘调度算法*

一、一次磁盘读 / 写操作需要的时间

二、先来先服务算法（FCFS）

三、最短寻找时间优先 （SSTF）

操作系统第四章

三、最短寻找时间优先（SSTF）

四、扫描算法（SCAN）