操作系统——文件管理

1、第四章：文件管理

通过下面的思维导图来依次分享「文件管理」里面重要知识点的笔记。

2、第一节：文件系统基础 

1.  文件：是以计算机硬件为载体存储在计算机上的信息集合，文件可以是文本文档、图片、程序等。在系统运行时，计算机以进程为基本单位进行资源的调度和分配；而在用户进行的输入、输出中，则以文件为基本单位。

2.  文件系统(File System)：用于实现用户对文件的维护管理要求，如：访问文件、修改文件和保存文件等。

3.  文件的结构自底向上依次定义如下：

①数据项:  数据项是文件系统中最低级的数据组织形式。可分为以下两种类型：

a.  基本数据项：用于描述一个对象的某种属性的一个值，如姓名、日期或证件号等，是数据中可命名的最小逻辑数据单位，即原子数据。

b.  组合数据项：由多个基本数据项组成。

②记录：记录是一组相关的数据项的集合，用于描述一个对象在某方面的属性，如一个考生报名记录包括考生姓名、出生日期、报考学校代号、身份证号等一系列域。

③文件:  指由创建者所定义的一组相关信息的集合，逻辑上可分为有结构文件和无结构文件两种。在有结构文件中，文件由一组相似记录组成，如报考某学校的所有考生的报考信息记录，又称为记录式文件；而无结构文件则被看成是一个字符流，比如一个二进制文件或字符文件，又称为流式文件。

4.  文件的属性通常包括以下属性：

①名称：文件名称唯一，以容易读取的形式保存。

②标识符:  标识文件系统内文件的唯一标签，通常为数字，它是对人不可读的一种内部名称。

③类型：被支持不类型的文件系统所使用。

④位置：指向设备和设备上文件的指针。

⑤大小：文件当前大小(用字节、字或块表示)，也可包含文件允许的最大值。

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

⑦时间、日期和用户标识：文件创建、上次修改和上次访问的相关信息，用于保护、安全和跟踪文件的使用。

说明：所有文件的信息都保存在目录结构中，而且目录结构也保存在外存上。文件信息当需要时再调入内存。目录条目包括文件名称及其唯一标识符，而标识符定位其他属性的信息。

5.  文件的基本操作：

①创建文件：创建文件有两个必要步骤，一是在文件系统中为文件找到空间; 二是在目录中为新文件创建条目，该条目记录文件名称、在文件系统中的位置及其他可能信息。

②写文件：为了写文件，执行一个系统调用，指明文件名称和要写入文件的内容。对于给定文件名称，系统搜索目录以查找文件的位置。系统必须为该文件维护一个写位置的指针。每当发生写操作，便更新写指针。

③读文件：为了读文件，执行一个系统调用，指明文件名称和要读入文件块的内存位置。同样，需要搜索目录以找到相关目录项，系统维护一个读位置的指针。每当发生读操作时，更新读指针。一个进程通常只对一个文件读或写，所以当前操作位置可作为每个进程当前文件位置指针。由于读和写操作都使用同一指针，节省了空间也降低了系统复杂度。

④文件重定位(文件寻址)：按某条件搜索目录，将当前文件位置设为给定值，并且不会读、写文件。

⑤删除文件：先从目录中找到要删除文件的目录项，使之成为空项，然后回收该文件所占用的存储空间。

⑥截断文件：允许文件所有属性不变，并删除文件内容，即将其长度设为0并释放其空间。

6.  文件的打开与关闭：系统在首次使用文件时需要使用系统调用open，将指明文件的属性(包括该文件在外存上的物理位置)从外存拷贝到内存打开文件目录表的一个表目中，并将该表目的编号(或称为索引)返回给用户。操作系统维护一个包含所有打开文件信息的表(打开文件表，open-file-table)。当用户需要一个文件存在时，可通过该表的一个索引指定文件，就省略了搜索环节。当文件不再使用时，进程可以关闭它，操作系统从打开文件表中删除这一条目。

说明：如果调用open的请求(如创建、只读、读写、添加等)得到允许。进程就可以打开文件，而open通常返回一个指向打开文件表中的一个条目的指针，通常使用该指针(而非文件名)进行所有的I/O操作，以简化步骤并节省资源。在open调用完成之后，操作系统对该文件的任何操作，都不再需要文件名，只需要open调用的返回指针。

7.  有结构文件(记录式文件)按记录的组织形式可以分为：

①顺序文件：文件中的记录一个接一个地顺序排列，记录通常是定长的，可以顺序存储或以链表形式存储，在访问时需要搜索文件。顺序文件有以下两种结构：

a.  串结构。记录之间的顺序与关键字无关。

b.  顺序结构。指文件中的所有记录按关键字顺序排列。

特点：在对记录进行批量操作时，对顺序文件的效率是所有逻辑文件中最高的；只有顺序文件才能存储在磁带上，并能有效地工作，但顺序文件对查找、修改、增加或删除单个记录的操作比较困难。

②索引文件：为满足可变长记录文件的查找要求，引入索引表，建立一张索引表以加快检索速度，索引表本身是定长记录的顺序文件。索引表中包括索引号、长度和指针，具体索引表与逻辑文件之间的关系如下图：

③索引顺序文件：是顺序和索引两种组织形式的结合。索引顺序文件将顺序文件中的所有记录分为若干组，为顺序文件建立一张索引表，在索引表中为每组中的第一个记录建立以索引项，其中含有该记录的关键字值和指向该记录的指针。如下图：

说明：索引表中为每一组的第一个记录(不是每一个记录)的关键字值，用指针指向主文件中该记录的起始位置。在查找一个记录时，通过索引表找到其所在的组，然后在改组中使用顺序查找就能很快地找到记录。

④直接文件或散列文件(Hash File)：给定记录的键值或通过Hash函数转换的键值直接决定记录的物理地址。其映射结构不同于顺序文件或索引文件，没有顺序的特性。散列文件有很高的存取速度，但是会引起冲突，即不同关键字的散列函数值相同。 

8.  文件控制块(file control block，FCB)：是用来存放控制文件需要的各种信息的数据结构，以实现“按名存取”。FCB的有序集合称为文件目录，一个FCB就是一个文件目录项。在创建一个新文件时，系统将分配一个FCB并存放在文件目录中，成为目录项。

FCB主要包含以下信息：

①基本信息：如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等；

②存取控制信息：如文件存取权限；

③使用信息：如文件建立时间、修改时间等。

9.  索引结点：因采用文件名和文件描述信息分开的方法，文件描述信息单独形成一个称为索引结点的数据结构，在文件目录中的每一个目录项仅由文件名和指向该文件所对应结点的指针构成。因此，在检索目录文件的过程中，只需要用到文件名，仅当找到一个目录项时，才需要从该目录项中读出该文件的物理地址。

说明：FCB或索引结点相当于图书馆中书本的索引号，可以在图书馆网站上找到图书的索书号，然后根据索书号找到想要的书本。

10.  文件目录：与文件管理系统和文件集合相关联，包含有关文件的信息，包含属性、位置和所有权等，这些信息主要由操作系统进行管理。主要有以下几种目录结构：

①单级目录结构：即在整个文件系统中只建立一张目录表，每个文件占一个目录项。当访问一个文件时，先按文件名在该目录中查找到相应的FCB，经合法性检查后执行相应的操作；当建立一个新文件时，必须先检索所有目录项以确保没有“重名”的情况，然后在该目录中增设一项，把FCB的全部信息保存在该项中；当删除一个文件时，先从该目录中找到该文件的目录项，回收该文件所占用的存储空间，然后再清除该目录项。

单级目录结构实现了“按名存取”，但是存在查找速度慢、文件不允许重名、不便于文件共享等缺点，而且对于多用户的操作系统不适用。

②两级目录结构：将文件目录分成主文件目录(Master File Directory，MFD)和用户文件目录(User File Directory，UFD)两级。主文件目录项记录用户及相应用户文件目录所在的存储位置；用户文件目录项记录该用户文件的FCB信息。当某用户欲对其文件进行访问时，只需搜索该用户对应的UFD。这样可解决不同用户文件的“重名”问题，同时在一定程度上保证了文件的安全；但两级目录结构缺乏灵活性，不能对文件分类。

③多级目录结构(树形目录结构)：将两级目录结构的层次关系加以推广，就形成了多级目录结构，即树形目录结构。用户要访问某个文件时用文件的路径名标识文件，文件路径名是个字符串，由从根目录出发到所找文件的通路上的所有目录名与数据文件名用分隔符“/”连接起来而成。从根目录出发的路径称为绝对路径。

当层次较多时，每次从根目录查询浪费时间，于是加入了当前目录，进程对各文件的访问都是相对于当前目录进行的，当用户要访问某个文件时，使用相对路径，进程对各文件的访问都是相对于当前目录进行的。当用户要访问某个文件时，使用相对路径标识文件，相对路径由从当前目录出发到所找文件通路上所有目录名与数据文件名用分隔符“/”链接而成。

树形目录结构可以很方便地对文件进行分类，层次结构清晰，也能够更有效地进行文件的管理和保护；但是在树形结构中查找一个文件，需要按路径名逐级访问中间结点，这就增加了磁盘访问次数，影响查询速度，也不便于实现文件共享。

④无环图目录结构：在树形目录结构的基础上增加一些指向同一结点的有向边，使整个目录成为一个有向无环图。引入无环图目录结构是为了实现文件共享。

文件共享的实现：每一个共享结点都设置一个共享计数器，每当图中增加对该结点的共享链时，计数器加1；每当某用户提出删除该结点时，计数器减1,。仅当共享计数器为0时，才真正删除请求用户的共享链。

共享文件(或目录)不同于文件拷贝(副本)。如果有两个文件拷贝，每个程序员看到的是拷贝而不是原件；但如果一个文件被修改，那么另一个程序员的拷贝不会有改变。对于共享文件，只存在一个真正文件，任何改变都会被其他用户所见。

11.  文件保护：为了防止因文件共享可能导致的文件被破坏或未经核准的用户修改文件，文件系统必须控制用户对文件的存取，即解决对文件的读、写、执行的许可问题。因而，必须在文件系统中建立相应的文件保护机制。文件保护通过访问控制、口令保护和加密保护等方式实现。

①访问控制：基于用户身份访问进行控制，为每个文件和目录增加一个访问控制列表(Access-Control List，ACL)，从而规定每个用户名及其所允许的访问类型(权限)。

②口令保护：指用户在建立一个文件时提供一个口令，系统为其建立FCB时附上相应口令，同时告诉允许共享该文件的其他用户。用户请求访问时必须提供相应的口令，这种方法时间和空间的开销不多，缺点是口令直接存在系统内部，不够安全。

③加密保护：指用户对文件进行加密，文件被访问时需要使用**。这种方法保密性强，节省了存储空间，不过编码和译码要花费一定的时间。

说明：访问控制是用于控制用户对文件的访问方式；口令保护和加密保护是为了防止用户文件被他人存取或窃取。

 

3、第二节：文件系统的实现

1.  文件系统的层次结构自上而下通常为下图所示：

①用户接口：此层由若干程序模块组成，每一模块对应一条系统调用，用户发出系统调用时，控制即转入相应的模块。

②文件目录系统：主要功能是管理文件目录，其任务有管理活跃文件目录表、管理读写状态信息表、管理用户进程的打开文件表、管理与组织在存储设备上的文件目录结构、调用下级存取控制模块。

③存取控制验证：此层实现文件保护，它把用户的访问要求与FCB中指示的访问控制权限进行比较，以确认访问的合法性。

④逻辑文件系统与文件信息缓冲区：主要功能是根据文件的逻辑结构将用户要读写的逻辑记录转换成文件逻辑结构内的相应块号。

⑤物理文件系统：主要功能是把逻辑记录所在的相应块号转换成实际的物理地址。

⑥分配模块：主要功能是管理存储空间，即负责分配辅存空间和回收辅存空间。

⑦设备管理程序模块：主要功能是分配设备、分配读写用缓冲区、磁盘调度、启动设备、处理设备中断、释放设备读写缓冲区、释放设备等。

2.  目录的实现：在读文件前，必须先打开文件。打开文件时，操作系统利用路径名找到相应目录项，目录项中提供了查找文件磁盘块所需要的信息。目录实现的基本方法有：

①线性列表：使用存储文件名和数据块指针的线性表。特点是实现简单，比较费时。

②哈希表：哈希表根据文件名得到一个值，并返回一个指向线性列表中元素的指针。特点是查找非常迅速，插入和删除也较简单，不过需要一些预备措施来避免冲突；最大困难是哈希表长度固定以及哈希函数对表长的依赖性。

3.  文件的分配方式：对应文件的物理结构，是指如何为文件分配磁盘块常用的磁盘分配空间分配方式有：

①连续分配：要求每个文件在磁盘上占有一组连续的块磁盘地址定义了磁盘上的一个线性排序，文件的连续分配可以用第一块的磁盘地址和连续快的数量定义。

连续分配支持顺序访问和直接访问。其特点是实现简单、存取速度快，但文件长度不宜动态增加，一旦增加需要大量移动盘块，反复增删文件会产生外部碎片，并且很难确定一个文件需要的空间大小，因而只适用于长度固定的文件。

②链接分配：采用离散分配方式，消除了外部碎片，故而显著地提高了磁盘空间的利用率，又因为是根据文件的当前需求，为它分配必须的盘块，当文件动态增长时，可以动态地再为它分配盘块，故无需事先知道文件的大小。

③索引分配：把每个文件的所有的盘块号都集中放在一起构成索引块(表)。每个文件都有其索引块，是一个磁盘块地址的数组。如索引块的第i个条目指向文件的第i个块，目录条目包括索引块的地址，要读第i块，通过索引块的第i个条目的指针来查找和读入所需的块。索引分配解决了链接分配不能支持直接访问的缺点。

4.  文件存储空间管理：

①文件存储器空间的划分与初始化：一个文件存储在一个文件卷中(又叫逻辑卷)，文件卷可以是物理盘的一部分，也可以是整个物理盘，支持超大型文件的文件卷也可以由多个物理盘组成。

在一个文件卷中，存放文件数据信息的空间称为文件区；存放文件控制信息FCB的空间称为目录区。

②文件存储器空间管理：文件存储设备分成许多大小相同的物理块，并以块为单位交换信息。因而，文件存储设备的管理实质上是对空闲块的组织和管理。

 

4、第三节：磁盘组织与管理

1.  磁盘(Disk)：是由表面涂有磁性物质的金属或塑料构成的圆形盘片，通过一个称为磁头的导体线圈从磁盘中存取数据。在读/写操作期间，磁头固定，磁盘在下面高速旋转。磁盘的盘面上的数据存储在一组同心圆中，称为磁道。每个磁道与磁头一样宽，一个盘面有上千个磁道。磁道又划分为几百个扇区，每个扇区固定存储大小(通常为512B)，一个扇区称为一个盘块。如下图：

2.  磁盘调度算法：

①先来先服务(First Come First Served，FCFS)算法：根据进程请求访问磁盘的先后顺序进行调度。该算法简单，具有公平性，算法性能上接近随机调度。

②最短寻找时间优先(Shortest Seek Time First，SSTF)算法：该算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道，以使每次的寻找时间最短。此算法比FCFS性能好，但会产生“饥饿”现象。

③扫描(SCAN)算法(又称为电梯算法)：该算法在磁头当前移动方向上选择与当前磁头所在磁盘距离最近的请求作为下一次服务的对象，实际上就是在最短寻找时间优先算法的基础上规定了磁头运动的方向。SCAN算法，避免“饥饿”现象，寻道性能好，但对最近扫描过的区域不公平，因此在访问局部性方面不如FCFS算法和SSTF算法好。

④循环扫描(Circular SCAN，C-SCAN)算法：在扫描算法的基础上规定磁头单向移动来提供服务，回返时直接快速移动至起始端而不服务如何请求。该算法可消除对两端磁道请求的不公平。

3.  磁盘的管理：

①磁盘初始化：在磁盘能存储数据之前，必须将其分成扇区以便磁盘控制器能进行读和写操作，这个过程称为低级格式化(物理分区)。低级格式化为磁盘的每个扇区采用特别的数据结构。每个扇区的数据结构通常由头、数据区域和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。

为了使用磁盘存储文件一操作系统还需要将自己的数据结构记录在磁盘上: 第一步将磁盘分为由一个或多个柱面组成的分区)(即我们熟悉的C盘、D盘等形式的分区)；第二步对物理分区进行逻辑格式化(创建文件系统)，操作系统将初始的文件系统数据结构存储到磁盘上，这些数据结构包括空闲和已分配的空间以及一个初始为空的目录。

②引导块：计算机启动时需要运行一个初始化程序(自举程序)，它初始化CPU、寄存器、设备控制器和内存等，接着启动操作系统。为此，该自举程序应找到磁盘上的操作系统内核，装入内存，并转到起始地址，从而开始操作系统的运行。自举程序通常保存在ROM中，为了避免改变自举代码需要改变ROM硬件的问题，故只在ROM中保留很小的自举装入程序，将完整功能的自举程序保存在磁盘的启动块上，启动块位于磁盘的固定位。

③坏块：由于磁盘有移动部件且容错能力弱，所以容易导致一个或多个扇区损坏。部分磁盘甚至从出厂时就有坏扇区。根据所使用的磁盘和控制器，对这些块进行处理。