第 4 章文件管理

傷城~ 2022-11-05 08:59 226阅读 0赞

# 第 4 章 文件管理 #

## 1、初识文件管理 ##

### 1.1、前情回顾 ###

> **操作系统所需提供的功能**

操作系统作为最接近硬件的软件系统，向下需要与硬件打交道，向上需要为应用软件和用户提供相应接口

![image-20210216203513946][]

操作系统需要提供处理机管理、存储器管理、文件管理、设备管理等功能，我们日常编辑的 Word 文档、PPT 文档都需要存储在硬盘上，操作系统为我们提供了文件管理相关的接口

![image-20210216203434096][]

> **文件就是一组有意义的信息/数据集合**

下面思考这一系列的问题：

1.  计算机中存放了各种各样的文件，一个文件有哪些属性？
2.  文件内部的数据应该怎样组织起来？
3.  文件之间又应该又应该怎么组织起来？
4.  从下往上看，OS应提供哪些功能，才能方便用户、应用程序使用文件？
5.  从上往下看，文件数据应该怎么存放在外存（磁盘）上？

### 1.2、Windows 系统的文件属性 ###

> **从最熟悉的 Windows 操作系统出发**

右击文件，可以在【详细信息】面板看到文件相关的属性，比如文件名称、文件类型、文件路径、文件创建和修改日期等等

![image-20210216204255647][]

> **文件的各种属性**

一个文件有哪些属性？

1.  文件名：由创建文件的用户决定文件名，主要是为了方便用户找到文件，同一目录下不允许有重名文件。
2.  标识符：一个系统内的各文件标识符唯一，对用户来说毫无可读性，因此标识符只是操作系统用于区分各个文件的一种内部名称。
3.  类型：指明文件的类型
4.  位置：文件存放的路径（让用户使用）、在外存中的地址（操作系统使用，对用户不可见）
5.  大小：指明文件大小
6.  创建时间、上次修改时间
7.  文件所有者信息
8.  保护信息：对文件进行保护的访问
9.  控制信息

### 1.3、文件内部数据的组织方式 ###

> **无结构文件**

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

![image-20210216204637079][]

> **有结构文件**

有结构文件（如数据库表）——由一组相似的记录组成，又称“记录式文件”，比如 Excel 文件

相关术语：数据项是文件系统中最基本的数据单位；记录是一组相关数据项的集合

![image-20210216204833843][]

> **无结构稳健与有结构文件的对比图**

有结构文件中，各个记录间应该如何组织的问题——应该顺序存放？还是用索引表来表示记录间的顺序？——这是“文件的逻辑结构”重点要探讨的问题

![image-20210216204957483][]

### 1.4、文件之间的组织方式 ###

> **如何管理各个目录以及各目录之内的文件**

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

目录其实也是一种特殊的有结构文件（由记录组成），如何实现文件目录是之后会重点探讨的问题，所谓的“目录”其实就是我们熟悉的“文件夹”

![image-20210216205142673][]

### 1.5、操作系统向上提供的功能 ###

> **创建、读写、删除文件**

**1、创建文件**

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

![image-20210216210359372][]

--------------------

**2、读写文件**

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

可以“写文件”，将更改过的文件数据写回外存（我们在“记事本”应用程序中编辑文件内容，点击“保存”后，“记事本”应用程序通过操作系统提供的“写文件”功能，即write系统调用，将文件数据从内存写回外存）

![image-20210216210426389][]

**3、删除文件**

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

![image-20210216210442202][]

> **操作系统为上层提供的文件服务**

可用几个基本操作完成更复杂的操作，比如：“复制文件”：先创建一个新的空文件，再把源文件读入内存，再将内存中的数据写到新文件中

读/写文件之前，需要“打开文件”；读/写文件结束之后，需要“关闭文件”

![image-20210216210110276][]

> **其他需要由操作系统实现的文件管理功能**

**文件共享**：使多个用户可以共享使用一个文件

**文件保护**：如何保证不同的用户对文件有不同的操作权限

### 1.6、文件在外存的存储格式 ###

> **从上往下看，文件应如何存放在外存？**

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

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

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

![image-20210216210837136][]

> **文件在外存中的存储方式**

**1、连续存储**：文件数据放在连续的几个磁盘块中

![image-20210216211058451][]

--------------------

**2、离散存储**：文件数据放在离散的几个磁盘块中。此时，应该如何记录各个磁盘块之间的先后顺序呢？操作系统又应该怎么管理空闲磁盘块？

![image-20210216211146830][]

--------------------

**PS**：“文件的物理结构”部分会探讨文件如何存储在外存中

### 1.7、本节课小结 ###

![image-20210216211401361][]

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

### 2.1、思维导图 ###

> **文件的逻辑结构**

所谓的“逻辑结构”，就是指在用户看来，文件内部的数据应该是如何组织起来的。而“物理结构”指的是在操作系统看来，文件的数据是如何存放在外存中的。

![image-20210216212342357][]

类似于数据结构的“逻辑结构”和“物理结构”。

比如“线性表”就是一种逻辑结构，在用户角度看来，线性表就是一组有先后关系的元素序列，如：a, b, c, d, e ……

“线性表”这种逻辑结构可以用不同的物理结构实现，如：顺序表/链表。顺序表的各个元素在逻辑上相邻，在物理上也相邻；而链表的各个元素在物理上可以是不相邻的。因此，顺序表可以实现“随机访问”，而“链表”无法实现随机访问。

可见，算法的具体实现与逻辑结构、物理结构都有关（文件也一样，文件操作的具体实现与文件的逻辑结构、物理结构都有关）

### 2.2、无结构文件 ###

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

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

**有结构文件**：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）

> **无结构文件**

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

文件内部的数据其实就是一系列字符流，没有明显的结构特性。因此也不用探讨无结构文件的“逻辑结构”问题。

![image-20210216212601107][]

### 2.3、有结构文件 ###

> **有结构文件**

有结构文件：由一组相似的记录组成，又称“记录式文件”。每条记录又若干个数据项组成。如：数据库表文件。一般来说，每条记录有一个数据项可作为关键字（作为识别不同记录的ID）

![image-20210216212755852][]

> **根据各条记录的长度（占用的存储空间）是否相等，又可分为定长记录和可变长记录两种**

**1、定长记录**：每条记录占用的存储空间都相等

![image-20210216213001021][]

--------------------

**2、可变长记录**：由于某些原因，导致各条记录占用的存储空间可能不相等

![image-20210216213120077][]

### 2.4、有结构文件的逻辑结构 ###

> **有结构文件按照逻辑结构来分类**

根据有结构文件中的各条记录在逻辑上如何组织，可以分为三类

![image-20210216213420478][]

#### 2.4.1、顺序文件 ####

> **顺序文件的定义**

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

--------------------

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

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

![image-20210216214521297][]

> **顺序文件的分类（按照记录和关键字的相对顺序进行分类）**

串结构中通常按照记录存入的时间决定记录的顺序

![image-20210216214717646][]

> **顺序文件的分类（按照各个记录在物理上的存储方式进行分类）**

各个记录在物理上可以顺序存储或链式存储

![image-20210216215002375][]

--------------------

**顺序文件查找记录需要解决的几个问题**

假设：已经知道了文件的起始地址（也就是第一个记录存放的位置）

思考1：能否快速找到第i个记录对应的地址？（即能否实现随机存取）

思考2：能否快速找到某个关键字对应的记录存放的位置？

--------------------

**顺序文件查找记录的结论**

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

注：一般来说，考试题目中所说的“顺序文件”指的是物理上顺序存储的顺序文件。之后的讲解中提到的顺序文件也默认如此。可见，顺序文件的缺点是增加/删除一个记录比较困难（如果是串结构则相对简单）

![image-20210216215421568][]

#### 2.4.2、索引文件 ####

> **为什么要使用索引文件**

对于可变长记录文件，要找到第i个记录，必须先顺序第查找前i-1个记录，但是很多应用场景中又必须使用可变长记录。如何解决这个问题？

可以建立一张索引表用于加快文件检索的速度，每条记录对应一个索引项，每一个索引项的 `ptr` 指针都指向对应记录的逻辑地址，我们查询索引表就能得到某条记录在文件中的逻辑地址，经过换算即可得到物理地址

![image-20210216215544932][]

> **为什么索引表可以加快记录的查询速度**

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

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

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

--------------------

**注意事项**：可以用不同的数据项建立多个索引表。如：学生信息表中，可用关键字“学号”建立一张索引表。也可用“姓名”建立一张索引表。这样就可以根据“姓名”快速地检索文件了。（Eg：SQL就支持根据某个数据项建立索引的功能）

#### 2.4.3、索引顺序文件 ####

> **索引文件的缺点**

思考索引文件的缺点：每个记录对应一个索引表项，因此索引表可能会很大。

比如：文件的每个记录平均只占8B，而每个索引表项占32个字节，那么索引表都要比文件内容本身大4倍，这样对存储空间的利用率就太低了。

> **索引顺序文件**

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

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

![image-20210216221027486][]

> **索引顺序文件（检索效率分析）**

**问题分析**：用索引顺序文件这种策略确实可以让索引表“瘦身”，但是是否会出现不定长记录的顺序文件检索速度慢的问题呢？

--------------------

**举个栗子说明索引顺序文件的检索效率**

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

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

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

![image-20210216221322788][]

> **多级索引顺序文件**

为了进一步提高检索效率，可以为顺序文件建立多级索引表。

例如，对于一个含106个记录的文件，可先为该文件建立一张低级索引表，每100个记录为一组，故低级索引表中共有10000个表项（即10000个定长记录），再把这10000个定长记录分组，每组100个，为其建立顶级索引表，故顶级索引表中共有100个表项。

![image-20210216221605776][]

--------------------

**Tips**

要为N个记录的文件建立K级索引，则最优的分组是每组N1/(K+1)个记录。

检索一个记录的平均查找次数是(N1/(K+1)/2) \* (K+1)

如：本例中，建立2级索引，则最优分组为每组1000001/3 = 100个记录，平均查找次数是(100/2) \*3 = 150次

### 2.5、本节课小结 ###

> **文件的逻辑结构**

![image-20210216221931618][]

> **有结构文件的逻辑结构**

一般我们说的顺序文件默认就是各记录在物理上顺序存储的文件

可变长记录的顺序文件在每次查询时只能从头依次查找

对于索引顺序文件，要会计算平均查找次数

![image-20210216221954753][]

## 3、文件目录 ##

### 3.1、思维导图 ###

> **树形结构的目录**

**问**：这种目录结构对于用户来说有什么好处？

**答**：文件之间的组织结构清晰，易于查找；编程时也可以很方便的用文件路径找到一个文件。如：`FILE *fp;fp=fopen(“F:\data\myfile.dat”);`用户可以轻松实现“按名存取”

![image-20210216223038470][]

那么从操作系统的角度来看，这些目录结构应该是如何实现的？

> **文件目录**

目录就是我们很熟悉的Windows操作系统的“文件夹”

![image-20210216223049920][]

### 3.2、文件控制块 ###

> **文件控制块 FCB**

目录本身就是一种有结构文件，由一条条记录组成。每条记录对应一个在该放在该目录下的文件，目录文件中的一条记录就是一个“文件控制块（FCB）”

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

最重要，最基本的还是文件名（FCB实现了文件名和文件之间的映射。使用户（用户程序）可以实现“按名存取”）、文件存放的物理地址。

![image-20210216223750554][]

--------------------

**举个栗子**

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

![image-20210216223837242][]

> **思考：需要对目录进行哪些操作？**

1.  搜索：当用户要使用一个文件时，系统要根据文件名搜索目录，找到该文件对应的目录项
2.  创建文件：创建一个新文件时，需要在其所属的目录中增加一个目录项
3.  删除文件：当删除一个文件时，需要在目录中删除相应的目录项
4.  显示目录：用户可以请求显示目录的内容，如显示该目录中的所有文件及相应属性
5.  修改目录：某些文件属性保存在目录中，因此这些属性变化时需要修改相应的目录项（如：文件重命名）

![image-20210216224225399][]

### 3.3、单级目录结构 ###

> **单击目录结构：整个系统中只有一张目录表**

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

单级目录实现了“按名存取”，但是不允许文件重名。在创建一个文件时，需要先检查目录表中有没有重名文件，确定不重名后才能允许建立文件，并将新文件对应的目录项插入目录表中。显然，单级目录结构不适用于多用户操作系统。

![image-20210216224513225][]

### 3.4、两级目录结构 ###

> **两级目录结构：适用于多用户操作系统**

早期的多用户操作系统，采用两级目录结构。分为主文件目录（MFD，Master File Directory）和用户文件目录（UFD，User Flie Directory）。

主文件目录记录用户名及相应用户文件目录的存放位置；用户文件目录由该用户的文件FCB组成；因此允许不同用户的文件重名，文件名虽然相同，但是对应的其实是不同的文件

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

![image-20210216230219234][]

### 3.5、多级目录结构 ###

> **多级（树形）目录结构：不同目录下的文件可以重名**

用户（或用户进程）要访问某个文件时要用文件路径名标识文件，文件路径名是个字符串。各级目录之间用“/”隔开。从根目录出发的路径称为绝对路径。例如：`自拍.jpg`的绝对路径是`/照片/2015-08/自拍.jpg`

![image-20210216230330289][]

--------------------

**访问文件所需的 IO 操作**

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

很多时候，用户会连续访问同一目录内的多个文件（比如：接连查看“2015-08”目录内的多个照片文件），显然，每次都从根目录开始查找，是很低效的。因此可以设置一个“当前目录”。

--------------------

**当前目录**

例如，此时已经打开了“照片”的目录文件，也就是说，这张目录表已调入内存，那么可以把它设置为“当前目录”。当用户想要访问某个文件时，可以使用从当前目录出发的“相对路径”。

在Linux中，“.”表示当前目录，因此如果“照片”是当前目录，则”自拍.jpg”的相对路径为：  
“./2015-08/自拍.jpg”。从当前路径出发，只需要查询内存中的“照片”目录表，即可知道”2015-08”目录表的存放位置，从外存调入该目录，即可知道“自拍.jpg”存放的位置了。

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

### 3.6、无环图目录结构 ###

> **为什么提出无环图目录结构**

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

> 无环图目录结构

在树形目录结构的基础上，增加一些指向同一节点的有向边，使整个目录成为一个有向无环图。可以更方便地实现多个用户间的文件共享。

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

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

![image-20210216231239631][]

--------------------

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

### 3.7、索引结点（FCB的改进） ###

> **对目录表进行瘦身**

其实在查找各级目录的过程中只需要用到“文件名”这个信息，只有文件名匹配时，才需要读出文件的其他信息。因此可以考虑让目录表“瘦身”来提升效率。

![image-20210216232403906][]

--------------------

**思考有何好处？**

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

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

> **改进后的文件访问操作**

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

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

![image-20210216232454948][]

### 3.8、本节课小结 ###

![image-20210216232614346][]

## 4、文件的物理结构 ##

### 4.1、思维导图 ###

> **操作系统需要对磁盘进行哪些管理**

【对非空闲磁盘块的管理】是【文件的物理结构/文件分配方式】要探讨的问题

【对空闲磁盘的管理】是“文件存储空间管理”要探讨的问题

![image-20210217150110059][]

> **文件的物理结构**

文件的物理结构主要研究文件数据应该怎样存放在外存中？

![image-20210217150229969][]

### 4.2、磁盘块 & 文件块 ###

> **磁盘块的概念**

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

![image-20210217150442011][]

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

![image-20210217150545450][]

> **文件块的概念**

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

操作系统为文件分配存储空间都是以块（磁盘块）为单位的；用户通过逻辑地址来操作自己的文件，操作系统要负责实现从逻辑地址到物理地址的映射

在下图的例子中，文件块的大小是1KB，则1MB大小的文件可以被分为1K个文件块

![image-20210217151142563][]

### 4.3、文件分配方式——连续分配 ###

> **连续分配：每个文件占有在物理上连续的磁盘块**

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

![image-20210217151346403][]

> **连续分配方式的地址转换**

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

--------------------

**连续分配方式的地址转换**

在连续分配方式中，文件目录中记录存放的起始块号和长度（总共占用几个磁盘块），这样我们查询文件目录就能知道文件的起始块号，再根据偏移地址就能找到目标磁盘块

![image-20210217151803343][]

文件块的大小一般和磁盘块的大小相等，因此从（逻辑块号，块内地址）→（物理块号，块内地址）的转换，只需转换块号就行，块内地址保持不变

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

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

> **连续分配的读写速度**

读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动磁头所需时间就越长。因此连续分配的文件在顺序读/写时速度最快

![image-20210217152324761][]

> **连续分配方式下的文件拓展**

初始状态：文件 A 占用了三个连续的磁盘块

![image-20210217161006179][]

若此时文件A要拓展，需要再增加一个磁盘块（总共需要连续的4个磁盘块）。由于采用连续结构，因此文件A占用的磁盘块必须是连续的。因此只能将文件A全部“迁移”到上图中的绿色区域。

![image-20210217161308240][]

--------------------

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

> **连续分配方式下的磁盘碎片**

**结论**：物理上采用连续分配，存储空间利用率低，会产生难以利用的磁盘碎片；可以用紧凑来处理碎片，但是需要耗费很大的时间代价。

![image-20210217161553600][]

> **连续分配方式的总结**

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

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

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

### 4.4、文件分配方式——链接分配 ###

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

#### 4.4.1、链接分配——隐式链接 ####

> **隐式链接分配方式**

文件目录中记录了文件存放的起始块号和结束块号。当然，也可以增加一个字段来表示文件的长度。除了文件的最后一个磁盘块之外，每个磁盘块中都会保存指向下一个盘块的指针，这些指针对用户是透明的

![image-20210217162545697][]

> **隐式链接分配方式的地址转换**

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

--------------------

**隐式链接地址变换的过程**

用户给出要访问的逻辑块号i，操作系统找到该文件对应的目录项（FCB），从目录项中找到起始块号（即 0 号块），将 0 号逻辑块读入内存，由此知道 1 号逻辑块存放的物理块号，于是读入 1 号逻辑块，再找到 2 号逻辑块的存放位置，…… ，以此类推。

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

--------------------

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

> **隐式链接分配方式下的文件拓展**

思考：是否方便拓展文件？初始状态：文件结束块号为 16

![image-20210217163553270][]

若此时要拓展文件，则可以随便找一个空闲磁盘块，挂到文件的磁盘块链尾，并修改文件的FCB（将结束块号设置为 8）

![image-20210217163744819][]

--------------------

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

> **隐式链接分配方式的总结**

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

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

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

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

#### 4.4.2、链接分配——显式链接 ####

> **显式链接分配方式**

显示分配：把用于链接文件各物理块的指针显式地存放在一张表中。即文件分配表（FAT，File Allocation Table），并且在文件目录中只需记录文件的起始块号

> **举些栗子说明显示连接分配方式**

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

![image-20210217164447660][]

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

![image-20210217164551486][]

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

> **显示链接分配方式的地址转换**

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

--------------------

**显示链接分配方式的地址变换过程**

用户给出要访问的逻辑块号 `i`，操作系统找到该文件对应的目录项（FCB），从目录项中找到起始块号，若 `i>0`，则查询内存中的文件分配表 FAT，往后找到 `i` 号逻辑块对应的物理块号。逻辑块号转换成物理块号的过程不需要读磁盘操作。

![image-20210217165144662][]

--------------------

**结论**

采用链式分配（显式链接）方式的文件，支持顺序访问，也支持随机访问（想访问 `i` 号逻辑块时，并不需要依次访问之前的 `0 ~ i-1` 号逻辑块），由于块号转换的过程不需要访问磁盘，因此相比于隐式链接来说，访问速度快很多。

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

> **链接分配方式总结**

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

--------------------

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

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

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

--------------------

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

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

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

### 4.5、文件分配方式——索引分配 ###

> **索引分配方式**

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

--------------------

**举个栗子说明索引分配方式**

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

![image-20210217170034436][]

--------------------

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

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

> **索引分配方式的地址转换**

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

--------------------

**索引分配方式的地址转换**

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。

用户给出要访问的逻辑块号 `i`，操作系统找到该文件对应的目录项（FCB），从目录项中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只 `i` 号逻辑块在外存中的存放位置。

![image-20210217170235389][]

--------------------

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

> **索引分配方式面临的问题**

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

**有三种解决方式**：①链接方案；②多层索引；③混合索引

![image-20210217170722591][]

--------------------

**1、链接方案**

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

假设磁盘块大小为1KB，一个索引表项占4B，则一个磁盘块只能存放256个索引项。若一个文件大小为256\*256KB = 65,536 KB = 64MB。该文件共有256\*256个块，也就对应256\*256个索引项，也就需要256个索引块来存储，这些索引块用链接方案连起来。

若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块（第256个索引块），而各个索引块之间是用指针链接起来的，因此必须先顺序地读入前255个索引块。这显然是很低效的。如何解决呢？

![image-20210217173727301][]

--------------------

**2、多层索引**

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

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

因此可以先将一级索引表调入内存，查询4号表项，将其对应的二级索引表调入内存，再查询二级索引表的2号表项即可知道1026号逻辑块存放的磁盘块号了。访问目标数据块，需要3次磁盘I/O。

若采用三层索引，则文件的最大长度为256\*256\*256\*1KB = 16GB，类似的，访问目标数据块，需要4次磁盘I/O。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

![image-20210217174538418][]

**注**：若采用多层索引，则各层索引表大小不能超过一个磁盘块

--------------------

**3、混合索引**

混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表），这种结构的索引支持的最大文件长度为65800KB

![image-20210217174831320][]

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

1.  访问0~7号逻辑块：两次读磁盘
2.  访问8~263：三次读磁盘
3.  访问264~65799：四次读磁盘

**结论**：使用混合索引方式读取于小文件，只需较少的读磁盘次数就可以访问目标数据块。（一般计算机中小文件更多）

> **索引分配方式的总结**

索引分配允许文件离散地分配在各个磁盘块中，系统会为每个文件建立一张索引表，索引表中记录了文件的各个逻辑块对应的物理块（索引表的功能类似于内存管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块称为数据块。若文件太大，索引表项太多，可以采取以下三种方法解决：

①链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：若文件很大，索引表很长，就需要将很多个索引块链接起来。想要找到i号索引块，必须先依次读入0~i-1号索引块，这就导致磁盘I/O次数过多，查找效率低下。

②多层索引：建立多层索引（原理类似于多级页表）。使第一层索引块指向第二层的索引块。还可根据文件大小的要求再建立第三层、第四层索引块。采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K + 1次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘。

③混合索引：多种索引分配方式的结合。例如，一个文件的顶级索引表中，既包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含两级间接索引（指向两层索引表）。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少。

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

### 4.6、本节课小结 ###

![image-20210217173244155][]

## 5、逻辑结构 VS 物理结构 ##

### 5.1、思维导图 ###

> **文件的逻辑结构**

![image-20210217175744889][]

> **文件的物理结构**

![image-20210217175756764][]

### 5.2、无结构文件的结构 ###

#### 5.2.1、C 语言创建无结构文件 ####

> **例：C 语言创建无结构文件**

C 语言创建无结构的代码

![image-20210217181015164][]

执行代码生成的 test.txt 文本文件

![image-20210217181141460][]

#### 5.2.2、逻辑结构（从用户视角看） ####

> **读取文件指定位置的字符**

Eg：你要找到第16个字符（编号从0开始），用户可以根据逻辑地址访问文件特定位置的内容

![image-20210217181959960][]

从用户的角度来看看 text.txt 文本文件：在用户看来，整个文件占用一片连续的逻辑地址空间

![image-20210217182023673][]

程序运行结果

![image-20210217182113489][]

#### 5.2.3、物理结构（从操作系统视角看） ####

> **连续分配方式**

操作系统视角：反正就是一堆二进制数据，每个磁盘块可存储1KB，拆就完了！

![image-20210217182349665][]

操作系统将文件拆分为若干个块，逻辑块号相邻的文件块在物理磁盘上也相邻

![image-20210217182405747][]

--------------------

**对于用户来讲**

使用C语言库函数`fseek`，将文件读写指针指向位置n（指明待读取的内容在文件中的逻辑地址）

使用C语言库函数`fgetc`，从读写指针所指位置读出1B内容

`fgetc`底层使用了`Read`系统调用，操作系统将（逻辑块号，块内偏移量）转换为（物理块号，块内偏移量）

> **链接分配方式**

操作系统视角：反正就是一堆二进制数据，每个磁盘块可存储1KB，拆就完了！

![image-20210217182349665][image-20210217182349665 1]

操作系统将文件拆分为若干个块，逻辑块号相邻的文件块离散地分配在物理磁盘中，并通过链接指针将各个文件块链接起来

![image-20210217182624750][]

--------------------

**对于用户来讲**

使用C语言库函数`fseek`，将文件读写指针指向位置n（指明待读取的内容在文件中的逻辑地址）

使用C语言库函数`fgetc`，从读写指针所指位置读出1B内容

> **索引分配方式**

操作系统视角：反正就是一堆二进制数据，每个磁盘块可存储1KB，拆就完了！

![image-20210217182349665][image-20210217182349665 2]

操作系统将文件拆分为若干个块，逻辑块号相邻的文件块离散地分配在物理磁盘中，我们可以通过索引表找到离散的文件块

![image-20210217190426689][]

--------------------

**对于用户来讲**

使用C语言库函数`fseek`，将文件读写指针指向位置n（指明待读取的内容在文件中的逻辑地址）

使用C语言库函数`fgetc`，从读写指针所指位置读出1B内容

### 5.3、有结构文件的结构 ###

#### 5.3.1、C 语言创建顺序文件 ####

> **例：C 语言创建顺序文件**

`Student_info` 结构体对应于学生表中的一条记录

![image-20210217191118062][]

将学生记录保存在 students.info 文件中

![image-20210217191219858][]

#### 5.3.2、逻辑结构（从用户视角看） ####

> **读取指定编号的学生记录**

从用户的角度来看，文件就是一条一条的记录

![image-20210217201712176][]

用户用逻辑地址访问文件

![image-20210217201719418][]

#### 5.3.3、物理结构（从操作系统视角看） ####

> **先将文件砍成文件块，再分配到磁盘块上**

文件对操作系统说：是兄弟就来砍我！

![image-20210217210044970][]

--------------------

**1、连续分配方式**：逻辑相邻的文件块在物理磁盘上也相邻

![image-20210217210127114][]

**2、链接分配方式**：文件块离散地分配在磁盘中，通过链接指针的方式表示其先后顺序

![image-20210217210141504][]

**3、索引分配方式**：文件块离散地分配在磁盘中，通过查询索引表就能找到对应的磁盘块

![image-20210217210157213][]

### 5.4、在？进来绕一下 ###

> **懵逼点：顺序文件采用顺序存储或者链式存储**

顺序文件：各个记录可以顺序存储或链式存储

--------------------

**1、顺序文件的顺序存储**

`Student_info` 结构体的定义

![image-20210217213025937][]

顺序存储，各条记录相邻着存放

![image-20210217213138845][]

--------------------

**2、顺序文件的链式存储**

`Student_info` 结构体的定义：多了 `next` 指针，用于指向下一条记录

![image-20210217213042857][]

链式存储，各条记录离散着存放，用指针表示先后关系

![image-20210217213155718][]

> **链式存储的顺序文件采用连续分配方式**

链式存储，各条记录离散着存放，用指针表示先后关系；但对于操作系统来说，都是二进制玩意儿，直接砍成文件块

![image-20210217213737973][]

将这些文件块离散地分配在磁盘中，并通过链接指针表示其先后顺序

![image-20210217214159334][]

--------------------

**总结**

文件内部各条记录链式存储：由创建文件的用户自己设计的

文件整体用链接分配：由操作系统决定

> **索引文件采用索引分配**

`Student_info` 结构体：定义了文件的每行记录

![image-20210217221444296][]

索引的定义：根据学生学号查找索引表，就能得到学生记录的逻辑地址

![image-20210217221519394][]

索引文件：从用户视角来看，整个文件依然是连续存放的。如：前1MB存放索引项，后续部分存放记录

![image-20210217221844050][]

管你是链式分配方式还是索引分配方式，在操作系统看来就是一堆二进制，拆就完事儿~

![image-20210217222513054][]

拆完之后再磁盘中离散分配，并通过索引表建立起各个磁盘块之间的联系

![image-20210217222337428][]

--------------------

**总结**

索引文件的索引表：用户自己建立的，映射：关键字→记录存放的逻辑地址

索引分配的索引表：操作系统建立的，映射：逻辑块号→物理块号

### 5.5、本节课小结 ###

![image-20210217222808482][]

## 6、文件存储空间管理 ##

### 6.1、思维导图 ###

> **操作系统需要对磁盘进行哪些管理**

【对非空闲磁盘块的管理】是【文件的物理结构/文件分配方式】要探讨的问题

【对空闲磁盘的管理】是“文件存储空间管理”要探讨的问题

![image-20210217223428573][]

> **文件存储空间管理**

学习时注意从三个方面进行理解：

1.  用什么方式记录、组织空闲块？
2.  如何分配磁盘块
3.  如何回收磁盘块

![image-20210217223453415][]

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

> **磁盘存储空间的划分与初始化**

**存储空间的划分**：将物理磁盘划分为一个个文件卷（逻辑卷、逻辑盘），比如安装Windows操作系统的时候，一个必经步骤是——为磁盘分区（C:盘、D:盘、E:盘等）

**存储空间的初始化**：将各个文件卷划分为目录区、文件区。其中目录区主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息；文件区用于存放文件数据

![image-20210217224114702][]

--------------------

**多个物理磁盘组成一个文件卷**：有的系统支持超大型文件，可支持由多个物理磁盘组成一个文件卷

![image-20210217224219296][]

### 6.3、存储空间管理——空闲表法 ###

> **空闲表法**

空闲表法适用于“连续分配方式”，在操作系统中维护着一张空闲表，记录了哪些磁盘块是空闲状态（起始块号和空闲盘块数）

> **空闲表法的磁盘分配**

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

![image-20210217225448233][]

--------------------

**举个栗子**：新创建的文件请求3个块，采用首次适应算法为文件分配空闲磁盘块，

空闲表中第一项的空闲盘块数为 2，不符合要求

![image-20210217225515090][]

空闲表中第二项的空闲盘块数为 1，符合要求

![image-20210217225603713][]

空闲表中第三项的空闲盘块数为 5，符合要求

![image-20210217225608033][]

将磁盘块 10~12 分配给文件后，修改空闲表状态：第一个空闲盘块号变为 13，空闲盘块数变为 2

![image-20210217225617558][]

> **空闲表法的磁盘回收**

**如何回收磁盘块**：与内存管理中的动态分区分配很类似，当回收某个存储区时需要有四种情况——①回收区的前后都没有相邻空闲区；②回收区的前后都是空闲区；③回收区前面是空闲区；④回收区后面是空闲区。总之，回收时需要注意表项的合并问题。

--------------------

**举个栗子**

情况② Eg：假设此时删除了某文件，系统回收了它占用的15、16、17号块

![image-20210217225857311][]

磁盘块 15~17 前后都是空闲区，因此回收后要进行空闲表项的合并

![image-20210217225921284][]

### 6.4、存储空间管理——空闲链表法 ###

> **空闲链表法**

空闲链表法又可以分为：空闲盘块链和空闲盘区链

![image-20210217230517600][]

空闲盘块链的单位是空闲磁盘块，空闲盘块中存储着下一个空闲盘块的指针

![image-20210217230629081][]

空闲盘区链的单位是空闲磁盘区（连续的空闲盘块组成一个空闲盘区），空闲盘区中的第一个盘块内记录了盘区的长度、下一个盘区的指针

![image-20210217230903249][]

> **空闲链表法的磁盘分配与回收**

**1、空闲盘块链法的磁盘分配与回收**

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

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

**如何回收**：回收的盘块依次挂到链尾，并修改空闲链的链尾指针。

**适用场景**：适用于离散分配的物理结构。为文件分配多个盘块时可能要重复多次操作

![image-20210217231404123][]

--------------------

**2、空闲盘区链法的磁盘分配与回收**

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

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

**如何回收**：若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区中。若回收区没有和任何空闲区相邻，将回收区作为单独的一个空闲盘区挂到链尾。

**适用场景**：离散分配、连续分配都适用。为一个文件分配多个盘块时效率更高

![image-20210217231521485][]

### 6.5、存储空间管理——位示图法 ###

> **位示图法**

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

![image-20210217231745916][]

--------------------

**重要重要重要**：要能自己推出盘块号与（字号,位号）相互转换的公式

(字号,位号)=(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

> **位示图法的磁盘分配与回收**

**位示图**：每个二进制位对应一个盘块。在本例中，“0”代表盘块空闲，“1”代表盘块已分配。

**如何分配**：若文件需要K个块，①顺序扫描位示图，找到K个相邻或不相邻的“0”；②根据字号、位号算出对应的盘块号，将相应盘块分配给文件；③将相应位设置为“1”。

**如何回收**：①根据回收的盘块号计算出对应的字号、位号；②将相应二进制位设为“0”

**适用场景**：连续分配、离散分配都适用

![image-20210217232112742][]

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

> **成组链接法**

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

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

![image-20210217232656706][]

--------------------

**成组链法的表示方式**

超级块中第一个元素记录了当前组空闲盘块数（100，哈哈，老师应该是写错了），第二个元素记录了下一个超级块的盘块号（300），紧接着后面记录了各个空闲盘块号（299~201）

**注**：若已经没有下一组空闲快，此处设为某特殊值；一个分组中的块号不需要连续，此处只是为了让大家更方便看出各个分组的数量

![image-20210217232832280][]

> **成组链接法的磁盘分配**

**Eg：需要 1 个空闲块**

①检查第一个分组的块数是否足够。1<100，因此是足够的（超级块中有 100 个空闲盘块）

![image-20210217233619104][]

②分配第一个分组中的1个空闲块（编号为 201 的磁盘块）之后，更新超级块的相应数据

![image-20210217233407429][]

--------------------

**Eg：需要100个空闲块**

①检查第一个分组的块数是否足够。100=100，是足够的（超级块中有 100 个空闲盘块）

![image-20210217234230928][]

②需要分配第一个分组中的100个空闲块。但是由于超级块中存放了再下一组的信息，因此300号块的数据需要复制到超级块中。

![image-20210217234401027][]

③将300号块的数据需要复制到超级块中后的状态

![image-20210217234541339][]

> **成组链接法的磁盘回收**

**Eg：假设每个分组最多为100个空闲块，此时第一个分组已有99个块，还要再回收一块**

初始状态：第一个分组中还可以再回收 1 个空闲块

![image-20210218000149386][]

回收空闲块之后更新超级块的相应数据

![image-20210218000155634][]

--------------------

**Eg：假设每个分组最多为100个空闲块，此时第一个分组已有100个块，还要再回收一块。**

初始状态：第一个分组中空闲块已满

![image-20210218000212384][]

此时需要将超级块中的数据复制到新回收的块中，并修改超级块的内容，让新回收的块成为第一个分组。

![image-20210218000216598][]

回收 100 个空闲块之后超级块的状态

![image-20210218000226158][]

### 6.7、本节课小结 ###

![image-20210218000103808][]

## 7、文件的基本操作 ##

### 7.1、思维导图 ###

![image-20210218100725072][]

### 7.2、创建文件 ###

> **创建文件 & create系统调用**

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

![image-20210218100756856][]

--------------------

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

1.  所需的外存空间大小（如：一个盘块，即1KB）
2.  文件存放路径（“D:/Demo”）
3.  文件名（这个地方默认为“新建文本文档.txt”）

--------------------

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

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

### 7.3、删除文件 ###

> **删除文件 & delete系统调用**

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

![image-20210218101242342][]

--------------------

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

1.  文件存放路径（“D:/Demo”）
2.  文件名（“test.txt”）

--------------------

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

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

### 7.4、打开文件 ###

> **打开文件 & open系统调用**

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

1.  文件存放路径（“D:/Demo”）
2.  文件名（“test.txt”）
3.  要对文件的操作类型（如：r只读；rw读写等）

--------------------

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

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

--------------------

**注**：当用户进程A打开文件时，就会将外存中的文件目录项复制到内存中的“打开文件表”中，之后用户进程A再操作文件就不需要每次都重新查目录了，这样可以加快文件的访问速度

![image-20210218102013509][]

> **打开文件时的操作权限**

**用户进程中的“打开文件表”**

1.  读/写指针记录了该进程对文件的读/写操作进行到的位置
2.  如果打开文件时声明的是“只读”，则该进程不能对文件进行写操作

![image-20210218102330823][]

--------------------

**系统的“打开文件表”**

整个系统只有一张系统“打开文件表”，打开计数器记录此时有多少个进程打开了此文件，打开计数器可以方便实现某些文件管理的功能。例如：在Windows系统中，我们尝试删除某个txt文件，如果此时该文件已被某个“记事本”进程打开，则系统会提示我们“暂时无法删除该文件”。其实系统在背后做的事就是先检查了系统打开文件表，确认此时是否有进程正在使用该文件。

![image-20210218103417595][]

### 7.5、关闭文件 ###

> **关闭文件 & close系统调用**

**进程使用完文件后，要“关闭文件”，操作系统在处理close系统调用时，主要做了几件事**

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

> **举个栗子说明打开计数器**

当用户进程 A 和用户进程 B 同时在访问 text.txt 文件时，系统的打开文件表中打开计数器为 2

![image-20210218102712790][]

当用户进程 B 结束对 text.txt 文件的访问时，系统的打开文件表中打开计数器减 1

![image-20210218102719114][]

### 7.6、读文件 ###

> **读文件 & read系统调用**

![image-20210218103825636][]

记事本进程的打开文件表

![image-20210218103923853][]

--------------------

**进程使用read系统调用完成写操作**

使用read系统调用需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要读入多少数据（如：读入1KB）、指明读入的数据要放在内存中的什么位置。操作系统在处理read系统调用时，会从读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中。

### 7.7、写文件 ###

> **写文件 & write系统调用**

![image-20210218104058253][]

记事本进程的打开文件表

![image-20210218104054642][]

--------------------

**进程使用write系统调用完成写操作**

使用write系统需要指明是哪个文件（在支持“打开文件”操作的系统中，只需要提供文件在打开文件表中的索引号即可），还需要指明要写出多少数据（如：写出1KB）、写回外存的数据放在内存中的什么位置操作系统在处理write系统调用时，会从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存。

### 7.8、本节课小结 ###

> **索引号（文件描述符）的作用**

“索引号”也称“文件描述符”，打开文件时并不会把文件数据直接读入内存，只需要返回文件表的索引号即可，之后“读/写文件”用“文件描述符”即可指明文件，不再需要用到“文件名”

![image-20210218104127294][]

## 8、文件共享 ##

### 8.1、思维导图 ###

> **文件共享**

操作系统为用户提供文件共享功能，可以让多个用户共享地使用同一个文件

--------------------

**注意**

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

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

![image-20210218205820570][]

### 8.2、硬链接 ###

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

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

--------------------

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

1.  若count = 2，说明此时有两个用户目录项链接到该索引结点上，或者说是有两个用户在共享此文件。
    
    ![image-20210218211330977][]
2.  若某个用户决定“删除”该文件，则只是要把用户目录中与该文件对应的目录项删除，且索引结点的count值减1。若count>0，说明还有别的用户要使用该文件，暂时不能把文件数据删除，否则会导致指针悬空。
    
    ![image-20210218211347683][]
3.  当count = 0时系统负责删除文件（将索引节点和文件从系统中移除）
    
    ![image-20210218211454777][]

**注**：User1 和 User2 两个用户的索引节点指针都指向同一个索引节点，通过索引节点可找到文件存放的外存地址

### 8.3、软链接 ###

> **基于符号链的共享方式（软链接）**

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

![image-20210218211629508][]

当文件被删除后，软链接依然可以存在，只不过通过软链接已经找不到目标文件（链接了个寂寞）

![image-20210218211930270][]

--------------------

**举个 Windows 的栗子说明软链接**

在 Windows 下创建快捷方式（软链接）

![image-20210218212209162][]

Link类型的文件名可以原文件不同，双击打开时，操作系统判断这个文件是Link类型的“快捷方式”文件，于是会根据其中记录的“路径信息”检索目录，最终找到“QQScLauncher.exe”

![image-20210218212249238][]

把“QQScLauncher.exe”删除，双击快捷方式会弹出如下对话框

![image-20210218212138131][]

### 8.4、本节课小结 ###

![image-20210218211957446][]

## 9、文件保护 ##

### 9.1、思维导图 ###

> **文件保护：保护文件数据的安全**

![image-20210218221132665][]

### 9.2、口令保护 ###

> **口令保护**

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

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

--------------------

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

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

### 9.3、加密保护 ###

> **加密保护**

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

--------------------

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

**缺点**：编码/译码，或者说加密/解密要花费一定时间。

> **举个栗子说明文件的加密保护**

**Eg**：一个最简单的加密算法——异或加密，假设用于加密/解密的“密码”为“01001”

--------------------

**加密过程**

加密的“密码”为“01001”，加密操作为异或运算

![image-20210218222044355][]

加密后的密文如下，磁盘中的文件存储的就是加密后的密文

![image-20210218222132455][]

--------------------

**解密过程（使用正确的解密密码进行解密）**

解密的“密码”为“01001”，解密操作为异或运算

![image-20210218222203594][]

经过解密后可恢复原始文件数据

![image-20210218222209449][]

--------------------

**解密过程（使用错误的解密密码进行解密）**

解密的“密码”为“01111”（与加密密码不一致），解密操作为异或运算

![image-20210218222221627][]

在不知道加密密码的前提下，经过解密后得到错误的文件数据，无法恢复原始文件数据

![image-20210218222229328][]

### 9.4、访问控制 ###

> **访问控制**

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

![image-20210218222931311][]

某文件的访问控制列表

![image-20210218222956077][]

> **文件访问控制列表的精简**

**文件访问控制列表存在的问题**：有的计算机可能会有很多个用户，因此访问控制列表可能会很大，可以用精简的访问列表解决这个问题）

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

![image-20210218230802587][]

### 9.5、Windows 的访问控制 ###

> **添加用户到这台电脑**

在【家庭和其他用户】界面中，点击【将其他人添加到这台电脑】，并为新用户设置【用户名】和【访问密码】，点击【下一步】

![image-20210218235631540][]

创建了名为【临时访客】的本地账户

![image-20210218235742456][]

在【开始菜单栏中】可以点击【临时访客】进行切换

![image-20210218235808153][]

> **添加文件访问权限**

右击文件或者目录，选择【属性】

![image-20210218235848466][]

在【安全】面板中点击【编辑】按钮，并在新弹出的对话框中点击【添加】按钮，为该目录添加一个访问账户

![image-20210218235957558][]

填入【访问账户名称】，并点击确定按钮添加此账户

![image-20210219000142954][]

更改临时访客的【访问权限】：不让临时访客访问该目录

![image-20210219000256265][]

点击【确定】按钮后会弹出如下对话框，这是因为临时访客本来是有【读取和执行、列出文件夹内容、读取】这三个权限，但是现在将这三个权限也剥夺了，因为拒绝权限项的优先级大于大于权限项的优先级，所以给出了如下提示

![image-20210219000349025][]

设置完成后，临时访问没有该目录的任何访问权限

![image-20210219000726236][]

> **验证文件访问权限是否设置成功**

点击【开始菜单栏】中的【临时访客】按钮，切换至临时访客视角

![image-20210219000907591][]

临时访问的读访问被拒绝

![image-20210219000954160][]

### 9.6、本节课小结 ###

![image-20210218231316748][]

## 10、文件系统的层次结构 ##

### 10.1、层次结构图 ###

![image-20210218233139582][]

### 10.2、文件系统的层次结构 ###

> **文件系统中各个层次的作用**

**用户接口**：文件系统需要向上层的用户提供一些简单易用的功能接口。这层就是用于处理用户发出的系统调用请求（Read、Write、Open、Close等系统调用）

**文件目录系统**：用户是通过文件路径来访问文件的，因此这一层需要根据用户给出的文件路径找到相应的FCB或索引结点。所有和目录、目录项相关的管理工作都在本层完成，如：管理活跃的文件目录表、管理打开文件表等

**存取控制模块**：为了保证文件数据的安全，还需要验证用户是否有访问权限。这一层主要完成了文件保护相关功能

**逻辑文件系统与文件信息缓冲区**：用户指明想要访问文件记录号，这一层需要将记录号转换为对应的逻辑地址

**物理文件系统**：这一层需要把上一层提供的文件逻辑地址转换为实际的物理地址

**辅助分配模块**：负责文件存储空间的管理，即负责分配和回收存储空间

**设备管理模块**：直接与硬件交互，负责和硬件直接相关的一些管理工作。如：分配设备、分配设备缓冲区、磁盘调度、启动设备、释放设备等

![image-20210218233227028][]

### 10.3、本节课小结 ###

> **用一个例子来辅助记忆文件系统的层次结构**

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

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

## 11、磁盘的结构 ##

### 11.1、思维导图 ###

![image-20210219001526665][]

### 11.2、磁道、扇区 ###

> **磁盘的结构图**

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

磁盘的盘面被划分成一个个磁道，下图中的一个“圈”就是一个磁道。一个磁道又被划分成一个个扇区，每个扇区就是一个“磁盘块”，各个扇区存放的数据量相同（如1KB）。

最内侧磁道上的扇区面积最小，因此数据密度最大

![image-20210219001924420][]

--------------------

磁盘实物图

![image-20210219002043265][]

> **如何在磁盘中读/写数据?**

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

### 11.3、柱面 ###

> **盘面**

![image-20210219002201899][]

> **柱面**

所有盘面中相对位置相同的磁道组成柱面

![image-20210219002229137][]

### 11.4、磁盘的物理地址 ###

> **磁盘的物理地址：（柱面号，盘面号，扇区号）**

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

--------------------

**读写磁盘块的操作步骤（柱面号，盘面号，扇区号）**

①根据“柱面号”移动磁臂，让磁头指向指定柱面；

②激活指定盘面对应的磁头；

③磁盘旋转的过程中，指定的扇区会从磁头下面划过，这样就完成了对指定扇区的读/写。

### 11.5、磁盘的分类 ###

> **按照磁头是否可移动分类**

磁头可以移动的称为活动头磁盘。磁臂可以来回伸缩来带动磁头定位磁道

![image-20210219002651415][]

磁头不可移动的称为固定头磁盘。这种磁盘中每个磁道有一个磁头

![image-20210219002702883][]

> **按照盘片是否可更换进行分类**

盘片可以更换的称为可换盘磁盘

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

### 11.6、本节课小结 ###

![image-20210219002749791][]

## 12、磁盘调度算法 ##

### 12.1、思维导图 ###

![image-20210219103324126][]

### 12.2、一次磁盘读/写操作的耗时 ###

> **1、寻找时间（寻道时间）TS**

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

①启动磁头臂是需要时间的。假设耗时为s；

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

**注**：现在的硬盘移动一个磁道大约需要0.2ms，磁臂启动时间约为2ms

--------------------

**举个栗子说明移动磁头所需的时间**

假设磁头正在最外圈的磁道上，启动磁头臂需要花费 s 毫秒

![image-20210219103758262][]

现将磁头从最外圈的的磁道移动到最内圈的磁道，需要花费 m\*n 毫秒（每跨越一个磁道耗时为 m 毫秒，总共需要跨越 n 条磁道）

![image-20210219103821676][]

> **2、延迟时间TR**

**延迟时间 TR**：通过旋转磁盘，使磁头定位到目标扇区所需要的时间。设磁盘转速为r（单位：转/秒，或转/分），则平均所需的延迟时间 TR = (1/2)\*(1/r) = 1/2r

**注**：1/r 就是转一圈需要的时间。找到目标扇区平均需要转半圈，因此再乘以 1/2，硬盘的典型转速为 5400 转/分，或 7200 转/分

--------------------

**举栗说明延迟时间**

此时磁头已经定位到了想要访问的磁道上，但是还没有定位到想要访问的扇区上

![image-20210219104820806][]

当磁盘转了 1/4 圈之后，磁头才定位到待访问的盘区

![image-20210219104759643][]

> **3、传输时间Tt**

**传输时间Tt**：从磁盘读出或向磁盘写入数据所经历的时间，假设磁盘转速为r，此次读/写的字节数为b，每个磁道上的字节数为N。则：传输时间Tt= (1/r) \* (b/N) = b/(rN)

**注**：每个磁道要可存N字节的数据，因此b字节的数据需要b/N个磁道才能存储。而读/写一个磁道所需的时间刚好又是转一圈所需要的时间1/r

--------------------

**举栗说明传输时间**

上一步已经将磁头定位到待访问盘区了

![image-20210220183610297][]

接下来磁盘转动，磁头将读取盘区数据，这部分用的时间就是传输时间

![image-20210220183600929][]

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

**总的平均存取时间**：Ta =TS\+TR\+Tt= TS \+ 1/2r + b/(rN)

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

### 12.3、先来先服务算法（FCFS） ###

> **先来先服务算法（FCFS）**

**算法思想**：根据进程请求访问磁盘的先后顺序进行调度

--------------------

**举个栗子**

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

--------------------

**算法执行过程**

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

![image-20210220184547792][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

**优点**：公平；如果请求访问的磁道比较集中的话，算法性能还算过的去

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

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

> **最短寻找时间优先（SSTF）**

**算法思想**：SSTF算法会优先处理的磁道是与当前磁头最近的磁道。可以保证每次的寻道时间最短，但是并不能保证总的寻道时间最短。（其实就是贪心算法的思想，只是选择眼前最优，但是总体未必最优）

--------------------

**举个栗子**

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

--------------------

**算法执行过程**

每次都选择与当前磁头最近的磁道进行访问

![image-20210220185207708][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

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

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

**比如**：本例中，如果在处理18号磁道的访问请求时又来了一个38号磁道的访问请求，处理38号磁道的访问请求时又来了一个18号磁道的访问请求。如果有源源不断的18号、38号磁道的访问请求到来的话，150、160、184号磁道的访问请求就永远得不到满足，从而产生“饥饿”现象

### 12.5、扫描算法（SCAN） ###

> **扫描算法（SCAN）**

**算法思想**：SSTF算法会产生饥饿的原因在于：磁头有可能在一个小区域内来回来去地移动。为了防止这个问题，可以规定，只有磁头移动到最外侧磁道的时候才能往内移动，移动到最内侧磁道的时候才能往外移动。这就是扫描算法（SCAN）的思想。由于磁头移动的方式很像电梯，因此也叫电梯算法

--------------------

**举个栗子**

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

--------------------

**算法执行过程**

注意：只有到了最边上的磁道才能改变磁头移动方向

![image-20210220185517642][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

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

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

### 12.6、LOOK调度算法 ###

> **LOOK调度算法**

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

--------------------

**举个栗子**

--------------------

**算法执行过程**

注：如果在磁头移动方向上已经没有别的请求，就可以立即改变磁头移动方向

![image-20210220190311051][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

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

### 12.7、循环扫描算法（C-SCAN） ###

> **循环扫描算法（C-SCAN）**

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

--------------------

**举个栗子**

--------------------

**算法执行过程**

注：只有到了最边上的磁道才能改变磁头移动方向。磁头返回途中不处理任何请求

![image-20210220205450187][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

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

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

### 12.8、C-LOOK调度算法 ###

> **C-LOOK调度算法**

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

--------------------

**举个栗子**

--------------------

**算法执行过程**

注：磁头只需要返回到最靠近边缘的、并且需要访问的磁道上即可；如果在磁头移动方向上已  
经没有别的请求，就可以立即让磁头返回

![image-20210220205724096][]

--------------------

**算法指标衡量**

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

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

--------------------

**优缺点**

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

### 12.9、本节课小结 ###

> **寻道时间：磁盘调度算法影响的指标**

![image-20210220205734598][]

## 13、减少延迟时间的方法 ##

### 13.1、前请回顾 ###

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

![image-20210220210135487][]

> **读取连续扇区存在的问题**

假设要连续读取橙色区域的2、3、4扇区：磁头读取一块的内容（也就是一个扇区的内容）后，需要一小段时间处理，而盘片又在不停地旋转

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

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

![image-20210220210238129][]

### 13.2、交替编号 ###

> **交替编号的好处**

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

![image-20210220210505497][]

### 13.3、磁盘地址结构的设计 ###

> **对于磁盘地址的思考**

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

--------------------

**举个栗子**

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

![image-20210220210853269][]

> **若物理地址结构是（盘面号，柱面号，扇区号）**

若物理地址结构是（盘面号，柱面号，扇区号），且需要连续读取物理地址（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 ），由于柱面号/磁道号相同，只是盘面号不同，因此不需要移动磁头臂。只需要激活相邻盘面的磁头即可

> **结论**

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

### 13.4、错位命名 ###

> **方案一：若相邻的盘面相对位置相同处扇区编号相同**

读取完磁盘块（000,00, 111）之后，需要短暂的时间处理，而盘面又在不停地转动，因此当（000, 01, 000）第一次划过1号盘面的磁头下方时，并不能读取数据，只能再等该扇区再次划过磁头。

![image-20210220211416495][]

> **方案二：错位命名**

由于采用错位命名法，因此读取完磁盘块（000, 00, 111）之后，还有一段时间处理，当（000, 01, 000）第一次划过1号盘面的磁头下方时，就可以直接读取数据。从而减少了延迟时间

![image-20210220211553601][]

### 13.5、本节课小结 ###

![image-20210220212615171][]

## 14、磁盘的管理 ##

### 14.1、思维导图 ###

![image-20210220221054789][]

### 14.2、磁盘初始化 ###

> **磁盘初始化**

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

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

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

![image-20210220221332586][]

### 14.3、引导块 ###

> **引导块**

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

> **引导块最初存放在 ROM 芯片中**

**思考**：初始化程序程序（自举程序）放在ROM中存在什么问题？

答：初始化程序可以放在ROM（只读存储器）中。ROM中的数据在出厂时就写入了，并且以后不能再修改（注：ROM一般是出厂时就集成在主板上的），万一需要更新自举程序，将会很不方便，因为ROM中的数据无法更改。如何解决呢？

> **后来将引导块放在磁盘分区中**

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

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

![image-20210220221924681][]

### 14.4、坏块的管理 ###

> **什么是坏块**

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

> **坏块的处理**

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

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

### 14.5、本节课小结 ###

![image-20210220222321638][]

[image-20210216203513946]: /images/20221023/fe4001fac4a44c9f8b06c1987443e4f9.png
[image-20210216203434096]: /images/20221023/6b0d1185727e4291a8cce61657ae9785.png
[image-20210216204255647]: /images/20221023/a63a25db042642b78f77ef86f820b13d.png
[image-20210216204637079]: /images/20221023/5a5bded8e5044d35bfac2c5a74a10340.png
[image-20210216204833843]: /images/20221023/58897ca0fcb642f883768b0e2a8c0d9a.png
[image-20210216204957483]: /images/20221023/2aa83dcdb72f4bb79233132662df9bbb.png
[image-20210216205142673]: /images/20221023/9ef0b52957e44deaa7cff80cca26b749.png
[image-20210216210359372]: /images/20221023/88a5ebb7869b41a889e74d79594c64cf.png
[image-20210216210426389]: /images/20221023/aab2fb076b974423a3acb977b3280b80.png
[image-20210216210442202]: /images/20221023/f805c8a37f524960aef98f0fba122af8.png
[image-20210216210110276]: /images/20221023/50e3e652bc76426f9b377cbb91b87a66.png
[image-20210216210837136]: /images/20221023/c88fd74c067448f98811f4f3bfc71649.png
[image-20210216211058451]: /images/20221023/25d07d8c843b4d5bbcd7817bad2426ad.png
[image-20210216211146830]: /images/20221023/c08417a2bb7c4877a567b12d90246ebf.png
[image-20210216211401361]: /images/20221023/7170ecc7601d4758a0e162c42ba146a0.png
[image-20210216212342357]: /images/20221023/d800e044ede6456282146c0718cb05cf.png
[image-20210216212601107]: /images/20221023/63e0ee35489e476885b0ec007ad9e319.png
[image-20210216212755852]: /images/20221023/edd0de65362a4ed7b5b4e497cdbaac1e.png
[image-20210216213001021]: /images/20221023/26a2202a282a436893e9ad599511511c.png
[image-20210216213120077]: /images/20221023/6659071cff89462baf8ae27067547e00.png
[image-20210216213420478]: /images/20221023/5672576f40064cb78bdac5b72022538f.png
[image-20210216214521297]: /images/20221023/560bc5feec884e06b60c965d76619554.png
[image-20210216214717646]: /images/20221023/a37ff323482b4aba876f7f98512459ba.png
[image-20210216215002375]: /images/20221023/716b11cf278d4b13b2db326396e915a3.png
[image-20210216215421568]: /images/20221023/bcd0c8070d614933b469760e1190b5e5.png
[image-20210216215544932]: /images/20221023/3b4047eeb4bf462bb0e059b00884b786.png
[image-20210216221027486]: /images/20221023/99d55403755e4f51b016d48fe32ee703.png
[image-20210216221322788]: /images/20221023/74191187c9b24107867326f80c559c11.png
[image-20210216221605776]: /images/20221023/6e6ab6c18ad44bcf953b7da0afa6b8ee.png
[image-20210216221931618]: /images/20221023/d24d90b2781945f1995e98ead55d0adf.png
[image-20210216221954753]: /images/20221023/f8d4aacc4c7d49dd8f7be96e395eb777.png
[image-20210216223038470]: /images/20221023/f7ee390c14b94ff3aa7688bb33218d5f.png
[image-20210216223049920]: /images/20221023/52eaa3c5549145f6ad60324f7b06480e.png
[image-20210216223750554]: /images/20221023/9ce31d9c1cda45caba1b917fa738fc2d.png
[image-20210216223837242]: /images/20221023/bc5983d943fd42a78393eb12c17483de.png
[image-20210216224225399]: /images/20221023/9cf8bd863b6f4abab6f9029e943cef33.png
[image-20210216224513225]: /images/20221023/7446fe2aba4c4f71a10043b45aff41dd.png
[image-20210216230219234]: /images/20221023/a1dc33983b1e4617a2b48a2b5e48a11e.png
[image-20210216230330289]: /images/20221023/2ebdd3cd040242c0a9a27b5bc74e6980.png
[image-20210216231239631]: /images/20221023/a3865939843748f4b66acc2d70d4d959.png
[image-20210216232403906]: /images/20221023/7b3a38becbe7412e9132d1e612c42a52.png
[image-20210216232454948]: /images/20221023/0ea3bbf236df47d0ae653d854eaaa8fb.png
[image-20210216232614346]: /images/20221023/322cb0044800408b813acfc3f88e31c7.png
[image-20210217150110059]: /images/20221023/4c853e9dc508499a82423f89c45dd503.png
[image-20210217150229969]: /images/20221023/8647b608b0e840319d0aa215744eb47c.png
[image-20210217150442011]: /images/20221023/80fb96706caa4f36a8a73866436ff05c.png
[image-20210217150545450]: /images/20221023/770b3f8b21294ece87d5172dd78a9b5c.png
[image-20210217151142563]: /images/20221023/7e8cf30476314427ae8c02f05e2d5db3.png
[image-20210217151346403]: /images/20221023/d969469600e441bc98e15dd76ae21397.png
[image-20210217151803343]: /images/20221023/0c8757a9c307466ca0c6791b03843e6c.png
[image-20210217152324761]: /images/20221023/f44b41164926428a8d8824b626b56da7.png
[image-20210217161006179]: /images/20221023/ae5d14239a694b018acb545ff9384cbb.png
[image-20210217161308240]: /images/20221023/538d3ecf12514b48bc1e96d0fe99ebb5.png
[image-20210217161553600]: /images/20221023/7641be7ee8464e40a1ff560ce88a79eb.png
[image-20210217162545697]: /images/20221023/fb54bcfbb1ae48b09eb16e960135f524.png
[image-20210217163553270]: /images/20221023/99ef5a6ec8fd4727baa3accfdda28db2.png
[image-20210217163744819]: /images/20221023/229def489b9d4d1da1f72faf97efb9b4.png
[image-20210217164447660]: /images/20221023/183459fbe769475c81282d266f01a612.png
[image-20210217164551486]: /images/20221023/0c305c1746c5477badd85bd190044607.png
[image-20210217165144662]: /images/20221023/a4315484c41a4be0930006b51c56e1e9.png
[image-20210217170034436]: /images/20221023/4cb8849d211342d5a59683864b21fe29.png
[image-20210217170235389]: /images/20221023/1d1a67ceb6104162ad0daf69fbf743da.png
[image-20210217170722591]: /images/20221023/7440e3a081d849f782e6c443b6c04172.png
[image-20210217173727301]: /images/20221023/370e20f6794b410bbfea99f823446fa9.png
[image-20210217174538418]: /images/20221023/3e65d2efda544c67b820185733409520.png
[image-20210217174831320]: /images/20221023/9cbea85480bc4225ae2baabec0bb5f0f.png
[image-20210217173244155]: /images/20221023/9901a2e9f8434eb5b1bd2ff158c5913e.png
[image-20210217175744889]: /images/20221023/7714eb0f9a1c41eeacdd31243264e007.png
[image-20210217175756764]: /images/20221023/c3b3af99ceb24b6ebbe5cfc647017744.png
[image-20210217181015164]: /images/20221023/c955366d14ed419f9ccfbb8d543a1d88.png
[image-20210217181141460]: /images/20221023/8850020b5b9147149f26d9cd9f120875.png
[image-20210217181959960]: /images/20221023/df3501f26ba9403c914e49686693730e.png
[image-20210217182023673]: /images/20221023/1384431eaf4546568c0af23c93ed9185.png
[image-20210217182113489]: /images/20221023/eeb8dd99f66c44c3935738e75fea49fd.png
[image-20210217182349665]: /images/20221023/9413787357f447d68f0a535e3c375102.png
[image-20210217182405747]: /images/20221023/1569306fa6324903a96d2062de3a221c.png
[image-20210217182349665 1]: /images/20221023/6fd1a96bf7f54457a75850783d997dcb.png
[image-20210217182624750]: /images/20221023/e3e1fca06d4348819b3c033ac38010e8.png
[image-20210217182349665 2]: /images/20221023/4a3deafd9e40454f9beca1ff0edf8d76.png
[image-20210217190426689]: /images/20221023/e24c50bcb521420c9566feee8b216b69.png
[image-20210217191118062]: /images/20221023/29e1ac35d7b44dfa9758d4fbc4c55d21.png
[image-20210217191219858]: /images/20221023/e582d122dccf4f138c403186c8b84fdd.png
[image-20210217201712176]: /images/20221023/6fffa266ab0345938933c0c705e7809f.png
[image-20210217201719418]: /images/20221023/b466c77845f7483398329e522a27e848.png
[image-20210217210044970]: /images/20221023/60f6c1e3201a48e1bbfff550c55ed930.png
[image-20210217210127114]: /images/20221023/ec768b37be234543945b1aff424fca88.png
[image-20210217210141504]: /images/20221023/04fd2efa9b314071a9209860b0fd5512.png
[image-20210217210157213]: /images/20221023/15cd8825a4c54e89a67be61ebdb7af61.png
[image-20210217213025937]: /images/20221023/bc2882520d3944988c8dc5dd9596d002.png
[image-20210217213138845]: /images/20221023/cdfc9d0b05fa4b89bad44040f6a344ab.png
[image-20210217213042857]: /images/20221023/1b7b38acea8842de923db2bdd61d5608.png
[image-20210217213155718]: /images/20221023/839c373d2c1c4606b7ae082c1f929d3a.png
[image-20210217213737973]: /images/20221023/b7e035b5f96045529b5af5dd0717dcf1.png
[image-20210217214159334]: /images/20221023/8b7aa2b363704bf3a2f3bc140ee2facd.png
[image-20210217221444296]: /images/20221023/f26cc13a356940519b65a6dd460ce839.png
[image-20210217221519394]: /images/20221023/dab7d0845b15403aaef115b9bb7e3f91.png
[image-20210217221844050]: /images/20221023/f24b7f406a5a4e75bfc29ad2f3965e3f.png
[image-20210217222513054]: /images/20221023/5c78ffb0467442a8b24d5355ea250dcd.png
[image-20210217222337428]: /images/20221023/3a1cfe88a8674dcd88d9979a103aff2c.png
[image-20210217222808482]: /images/20221023/fb13e1b24c31413998912b2a2898e227.png
[image-20210217223428573]: /images/20221023/51f7d609727f443facbd69dfeddc29cb.png
[image-20210217223453415]: /images/20221023/72c1ff344520492eabc84be31bd408dd.png
[image-20210217224114702]: /images/20221023/a19b3f83a60c477fbcebef16ffa5cb58.png
[image-20210217224219296]: /images/20221023/18df914dc1e9450d82788bea6645a995.png
[image-20210217225448233]: /images/20221023/31a2335ba6f14149a24b764e892e1d58.png
[image-20210217225515090]: /images/20221023/487e7f4350e540e1b9a8d2697f2df0b8.png
[image-20210217225603713]: /images/20221023/9f1793066ad047a1829cfd29686f0d6f.png
[image-20210217225608033]: /images/20221023/3721947a68914e809a4715342c33688b.png
[image-20210217225617558]: /images/20221023/49595561a0d1483abaa931fcc754b691.png
[image-20210217225857311]: /images/20221023/091eccff432645a8a95c0459c1ebd58b.png
[image-20210217225921284]: /images/20221023/0da23a940b524935ac5d9a1da7b1c30f.png
[image-20210217230517600]: /images/20221023/fce87084a27a45378652b3f2b4ddbd69.png
[image-20210217230629081]: /images/20221023/6f1484716b474f80983cb5c440e9f83c.png
[image-20210217230903249]: /images/20221023/cd0ce9f9dcd64ff799a6a15fa2bd7541.png
[image-20210217231404123]: /images/20221023/b856dcece3374dd182f074e2f3203672.png
[image-20210217231521485]: /images/20221023/1120daa9f0a44eb0a70392e2fa89a938.png
[image-20210217231745916]: /images/20221023/d13d7f206831418da828e2d53a7cbc19.png
[image-20210217232112742]: /images/20221023/d46e895cfa674deaaebd95ca0f9ffb08.png
[image-20210217232656706]: /images/20221023/f5179111bf484e0f8f20156d484bf78e.png
[image-20210217232832280]: /images/20221023/e0d1c307ebed4a19be4baf59d8d52187.png
[image-20210217233619104]: /images/20221023/18e78bb851c046cfae82b8402026d6b9.png
[image-20210217233407429]: /images/20221023/3bf5a6f8384841f8b699a5cfe06028a8.png
[image-20210217234230928]: /images/20221023/547c9637b9a74c7688d52e6a1f0a8dfd.png
[image-20210217234401027]: /images/20221023/0bad870c1e6e4fd69a741b54dea48080.png
[image-20210217234541339]: /images/20221023/15f9fc5796a4406fb782c5b43494ebb0.png
[image-20210218000149386]: /images/20221023/0a75387abc5e44ee8706f00c05caa2a2.png
[image-20210218000155634]: /images/20221023/46a73f497b024551950260a5931f1271.png
[image-20210218000212384]: /images/20221023/62c7c9b7d47a4d589b5fb588153a1102.png
[image-20210218000216598]: /images/20221023/118f6bb4b936450897acb743d1c3342a.png
[image-20210218000226158]: /images/20221023/191d7531a1d64ba7a539e98c6ee5f3af.png
[image-20210218000103808]: /images/20221023/0b27e24e5a484085aa85cadf98f5f806.png
[image-20210218100725072]: /images/20221023/3666d3cf10744dcd9b942dc1a53ba6a5.png
[image-20210218100756856]: /images/20221023/2879b857c0f642e9b101ecd0e1bff842.png
[image-20210218101242342]: /images/20221023/8ec5a0d6e2854dea99e69cf1f9fce1e8.png
[image-20210218102013509]: /images/20221023/1ceb9e90e63c45a681a228ebef92b5ee.png
[image-20210218102330823]: /images/20221023/6d646290128241e5bae911f1fb269e96.png
[image-20210218103417595]: /images/20221023/382b98cb4c574e7897e9fb5da2d31a1b.png
[image-20210218102712790]: /images/20221023/72b2981311ae4db4a95438643c0f445e.png
[image-20210218102719114]: /images/20221023/1f2ecbe6301d4f9881efd3222e232cfd.png
[image-20210218103825636]: /images/20221023/c9a4a31af4354a4a82cd22bbdf37a9be.png
[image-20210218103923853]: /images/20221023/bc02e40334e84295802fc0270c763370.png
[image-20210218104058253]: /images/20221023/80f951ff244145f88be4bf61d6995d2d.png
[image-20210218104054642]: /images/20221023/cb8c05950a9a475097cd3ffb5e8d23b9.png
[image-20210218104127294]: /images/20221023/bd8b60e182f44a30bd9185da1c08af9a.png
[image-20210218205820570]: /images/20221023/74014e99bd4f4426b7165450747cb50f.png
[image-20210218211330977]: /images/20221023/b3e3d3f7a988497d998931969418115d.png
[image-20210218211347683]: /images/20221023/20528580249f46fda973f1b652da0f4c.png
[image-20210218211454777]: /images/20221023/dc4c36d7156f43039e7a86e87c874d5c.png
[image-20210218211629508]: /images/20221023/4d429b1653c34a66be606a0f52cc34b6.png
[image-20210218211930270]: /images/20221023/29bd73f66cc749efa7c12ec74b51fb8b.png
[image-20210218212209162]: /images/20221023/5e846d952df249ca829861a004572702.png
[image-20210218212249238]: /images/20221023/786b238e9c90402ea508fcd8488210b6.png
[image-20210218212138131]: /images/20221023/20f60daf63124cabb7b26fd875f3749a.png
[image-20210218211957446]: /images/20221023/a67f89fe330640338bf86f725054fad4.png
[image-20210218221132665]: /images/20221023/9a225b6b7b7b4aada1fe9db4c67dc3d9.png
[image-20210218222044355]: /images/20221023/572be93e2cdf410f95cb7bca6f69f26f.png
[image-20210218222132455]: /images/20221023/1804cf0b39d54b298a2cf6ef570dc358.png
[image-20210218222203594]: /images/20221023/ecc15d5b45b243b99418f803e9b717e5.png
[image-20210218222209449]: /images/20221023/f07bdce9adb644d1bec54e0f3c312fd2.png
[image-20210218222221627]: /images/20221023/304ad662fcda4a23aad43a0a9358b740.png
[image-20210218222229328]: /images/20221023/bb16c8f8faae4f42a8d5de443188525c.png
[image-20210218222931311]: /images/20221023/b51faeb91e98490aaf77b96ee4c8d7c3.png
[image-20210218222956077]: /images/20221023/094ab30cd0d04965b2acaac1e1422dc0.png
[image-20210218230802587]: /images/20221023/3f4b5169738f42f99906bead4fba82ff.png
[image-20210218235631540]: /images/20221023/54259a65f42a489cbb98d6bade539af5.png
[image-20210218235742456]: /images/20221023/003cc18f49a7493283a1b0d27761562b.png
[image-20210218235808153]: /images/20221023/3fee9d77a26e4698b1328edf51e5f02d.png
[image-20210218235848466]: /images/20221023/7b5a4eca9e174d0981d5e3701586ec98.png
[image-20210218235957558]: /images/20221023/2d6cc718d9514c82a466a60a3a8c53b1.png
[image-20210219000142954]: /images/20221023/5d3a1451cc014919958603e1435c41ac.png
[image-20210219000256265]: /images/20221023/db5052c287a748df8b276a9574841436.png
[image-20210219000349025]: /images/20221023/1c0f7cfb89d54bc4b37d0c21ec6b8fdb.png
[image-20210219000726236]: /images/20221023/37fd3089b2c44ea680b783889ba3b3e0.png
[image-20210219000907591]: /images/20221023/74f6a2bef6024cb8a814630be4d466d4.png
[image-20210219000954160]: /images/20221023/ca35c6f81a3049c1904a6702e9f2e646.png
[image-20210218231316748]: /images/20221023/f1cc6c8a42b34896a8fe433d919fc767.png
[image-20210218233139582]: /images/20221023/819cff25647e4becbf6aa0e65f60aa82.png
[image-20210218233227028]: /images/20221023/ce95bb59252543fe9e2bdb089655b77b.png
[image-20210219001526665]: /images/20221023/4c90fc3b35e24bdfa2e3e4c5c38db9d4.png
[image-20210219001924420]: /images/20221023/fbaf7999e3e54a6c8071cc839aa2c148.png
[image-20210219002043265]: /images/20221023/72007cdb597a4ad4928d400e95427a8d.png
[image-20210219002201899]: /images/20221023/129340d16bfb401eb761722aecb650f3.png
[image-20210219002229137]: /images/20221023/b8e8e6e6087d4b668af104e114b81651.png
[image-20210219002651415]: /images/20221023/2dde9eb33f394145b24c3d2249dc6689.png
[image-20210219002702883]: /images/20221023/e95e4a1bf2e34c6e9f04f61c90712fb2.png
[image-20210219002749791]: /images/20221023/ef6679394cf54b81aec3099e969beb68.png
[image-20210219103324126]: /images/20221023/533520e01cec410f844ccbf3b1fdb9a2.png
[image-20210219103758262]: /images/20221023/d137542b370b4ae1818dc2f913303ef2.png
[image-20210219103821676]: /images/20221023/1763f9731fcc43b38a802bf40a72c20e.png
[image-20210219104820806]: /images/20221023/99689598b12a4adda0adc253036d893c.png
[image-20210219104759643]: /images/20221023/1a7b9c332e144656aeb33fc2db1bcec2.png
[image-20210220183610297]: /images/20221023/c3ddc8044a6e4063b745bf4a095e81c3.png
[image-20210220183600929]: /images/20221023/1dc32bc3bea14852bda6b0ccc7719375.png
[image-20210220184547792]: /images/20221023/206568bd524b47bd9abb77c86fc94c5f.png
[image-20210220185207708]: /images/20221023/ad70fa6aa2e749eaab261e9658c1fc13.png
[image-20210220185517642]: /images/20221023/c8234473c00348e19fb44d28834a6f7f.png
[image-20210220190311051]: /images/20221023/4be28580d22b4d8f9f0ba16d1b046e30.png
[image-20210220205450187]: /images/20221023/daadccb184534445aa0ca755bef2502f.png
[image-20210220205724096]: /images/20221023/88a5adedc09448528d92c93381a69fd8.png
[image-20210220205734598]: /images/20221023/c027e5a3d6604fff8338b77b63302993.png
[image-20210220210135487]: /images/20221023/94dca809dcbd47ec868f8c7cca0a181b.png
[image-20210220210238129]: /images/20221023/e5fcbe877b584510a527abc7d8c5adc6.png
[image-20210220210505497]: /images/20221023/73344d6cbb904bf68c3f502110adb253.png
[image-20210220210853269]: /images/20221023/940340d699ee449f90a6bf15ca890df5.png
[image-20210220211416495]: /images/20221023/5a4df9241826418698a0f96756f169fe.png
[image-20210220211553601]: /images/20221023/b3f89afb5c4d40fcb91b6ab916b0fea9.png
[image-20210220212615171]: /images/20221023/63183cfc872848149a27b4f2685ffcd3.png
[image-20210220221054789]: /images/20221023/94b4287129704261aac990b4d589c6de.png
[image-20210220221332586]: /images/20221023/df7fcfb469c349438aad49833557a102.png
[image-20210220221924681]: /images/20221023/f9babaad755743d0a6225e4a3699d45e.png
[image-20210220222321638]: /images/20221023/92974734036345b68418dea07832073b.png