文件控制块和索引结点
文件的属性
除了文件数据,操作系统还会保存与文件相关的信息,如所有者、创建时间等,这些附加信息称为文件属性或文件元数据。
操作系统通过文件控制块 (FCB) 来维护文件元数据。
文件控制块
- 文件控制块 (FCB) 是用来存放控制文件需要的各种信息的数据结构
- FCB 的有序集合称为文件目录,一个FCB 就是一个文件目录项。
- 系统将分配一个 FCB 并存放在文件目录中,称为目录项
- 一个文件目录也被视为一个文件,称为目录文件
FCB 主要包含以下信息:
- 基本信息,如文件名、文件的物理位置、文件的逻辑结构、文件的物理结构等。
- 存取控制信息,包括文件主的存取权限、核准用户的存取权限以及一般用户的存取权限。
- 使用信息,如文件建立时间、上次修改时间等。
索引结点
有的系统(如UNIX)便采用了文件名和文件描述信息分开的方法,使文件描述信息单独形成一个称为索引结点的数据结构,简称i结点(inode)。在文件目录中的每个目录项仅由文件名和指向该文件所对应的i结点的指针构成。
- 磁盘索引结点:是指存放在磁盘上的索引结点。每个文件有一个唯一的磁盘素引结点
- 内存索引结点:指存放在内存中的索引结点,当文件被打开时,要将磁盘索引结点复制到内存的索引结点中,便于以后使用[1]
文件的操作
文件的基本操作
- 创建文件。创建文件有两个必要步骤:
- 一是为新文件分配必要的外存空间;
- 二是在目录中为之创建一个目录项,目录项记录了新文件名、在外存中的地址及其他可能的信息。
- 写文件。为了写文件,执行一个系统调用。对于给定文件名,搜索目录以查找文件位置。系统必须为该文件维护一个写位置的指针。每当发生写操作时,便更新写指针。
- 读文件。为了读文件,执行一个系统调用。同样需要搜索目录以找到相关目录项,系统维护一个读位置的指针。每当发生读操作时,更新读指针。一个进程通常只对一个文件读或写,因此当前操作位置可作为每个进程当前文件位置的指针。由于读和写操作都使用同一指针,因此节省了空间,也降低了系统复杂度。
- 重新定位文件,也称文件定位。搜素目录以找到适当的条目,并将当前文件位置指针重新定位到给定值。重新定位文件不涉及读、写文件。
- 删除文件。为了删除文件,先从目录中检索指定文件名的目录项,然后释放该文件所占的存储空间,以便可被其他文件重复使用,并删除目录条目。
- 截断文件。允许文件所有属性不变,并删除文件内容,将其长度置为0。并释放其空间
文件的打开与关闭
- 所谓“打开”,是指调用 open 根据文件名搜索目录,将指明文件的属性(包括该文件在外存上的物理位置),从外存复制到内存打开文件表的一个表目中, 并将该表目的编号 (也称索引)返回给用户。当用户再次向系统发出文件操作请求时,可通过索引在打开文件表中查到文件信息,从而节省再次搜索目录的开销。当文件不再使用时,可利用系统调用 close 关闭它,操作系统将会从打开文件表中删除这一条目。
- 在多个不同进程可以同时打开文件的操作系统中,通常采用两级表:整个系统表和每个进程表。
- 只要文件未被关闭,所有文件操作就通过打开文件表来进行
提示
一个文件被用户进程首次打开即被执行了 open 操作,会把文件的 FCB 调入内存,而不会把文件内容读到内存中，将目录项中的信息复制到内存中的打开文件表中，并将打开文件表的**索引号（文件描述符）**返回给用户,只有进程希望获取文件内容时才会读入文件内容
文件保护
- 文件保护通过口令保护、加密保护和访问控制等方式实现
- 口令和加密是为了防止用户文件被他人存取或窃取,而访问控制则用于控制用户对文件的访问方式
提示
- 访问控制必须有系统实现，不然没法保证系统本身的安全性
- 加密机制不能有系统控制，不然没法扩展
- 加密机制更安全
- 访问控制更灵活
文件的逻辑结构
无结构文件(流式文件)
无结构文件将数据按顺序组织成记录并积累、保存, 它是有序相关信息项的集合,以宇节(Byte)为单位。
有结构文件(记录式文件)
顺序文件
- 可以顺序存储或以链表形式存储
- 串结构,记录之间的顺序与关键字无关,通常是按存入时间的先后进行排列,对串结构文件进行检素必须从头开始顺序依次查找,比较费时
- 顺序结构,指文件中的所有记录按关键字顺序排列,可采用折半查找法,提高了检索效率。
索引文件
逻辑文件+索引表
为主文件的每个记录在索引表中分别设置一个表项,包含指向变长记录的指针(即逻辑起始地址)和记录长度,索引表按关键字排序,因此其本身也是一个定长记录的顺序文件。这样就把对变长记录顺序文件的检索转变为对定长记录索引文件的随机检素,从而加快了记录的检索速度。
索引顺序文件
为顺序文件建立一张素引表,在索引表中为每组中的第一条记录建立一个索引项
若记录数很多,则可采用两级或多级索引。这种方式就是数据结构中的分块查找。
直接文件或散列文件(Hash File)
给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址
文件的物理结构
文件的物理结构就是研究文件的实现,即文件数据在物理存储设备上是如何分布和组织的。
同一个问题有两个方面的回答:
- 一是文件的分配方式,讲的是对磁盘非空闲块的管理;
- 二是文件存储空间管理,讲的是对磁盘空闲块的管理
连续分配
- 连续分配方法要求每个文件在磁盘上占有一组连续的块
- 作业访问磁盘时需要的寻道数和寻道时间最小
- 连续分配支持顺序访问和直接访问
链接分配
链接分配是一种采用离散分配的方式。它消除了磁盘的外部碎片,提高了磁盘的利用率。可以动态地为文件分配盘块,因此无须事先知道文件的大小
隐式链接
目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表;磁盘块分布在磁盘的任何地方,除最后一个盘块外,每个盘块都含有指向文件下一个盘块的指针,这些指针对用户是透明的。
显式链接
显式链接是指把用于链接文件各物理块的指针,从每个物理块的末尾中提取出来,显式地存放在内存的一张链接表中。
该表在整个磁盘中仅设置一张,称为文件分配表 (File Allocation Table, FAT)，并在开机后常驻内存。每个表项中存放链接指针,即下一个盘块号。文件的第一个盘块号记录在目录项 “物理地址”字段中,后续的盘块可通过查 FAT 找到
FAT 表在系统启动时就会被读入内存,因此查找记录的过程是在内存中进行的,因而不仅显著地提高了检索速度,而且明显减少了访问磁盘的次数。
提示
链接分配默认为隐式链接分配
索引分配
注意
在显式链接的链式分配方式中，文件分配表FAT是一个磁盘对应一张。而索引分配方式中，索引表是一个文件对
应一张。
索引分配将每个文件所有的盘块号都集中放在一起构成索引块(表)
但索引块太小就无法支持大文件，可以采用以下机制来处理这个问题。
- 链接方案。一个索引块通常为一个磁盘块,因此它本身能直接读写。为了支持大文件,可以将多个索引块链接起来。
- 多层索引。通过第一级索引块指向一组第二级的索引块,第二级索引块再指向文件块。查找时,通过第一级索引查找第二级索引,再采用这个第二级索引查找所需数据块。这种方法根据最大文件大小,可以继续到第三级或第四级。例如,4096B 的块,能在索引块中存入 1024 个4B 的指针。两级索引支持 1048576个数据块,即支持最大文件为 4GB。
- 混合索引。将多种素引分配方式相结合的分配方式。例如,系统既采用直接地址,又采用单级索引分配方式或两级素引分配方式。
此外,访问文件需两次访问外存,先读取索引块的内容,然后访问具体的磁盘块,因而降低了文件的存取速度。为了解决这一问题,通常将文件的索引块读入内存,以提高访问速度。
混合索引分配
- 对于小文件,为了提高对众多小文件的访问速度,最好能将它们的每个盘块地址直接放入 FCB,这样就可以直接从 FCB 中获得该文件的盘块地址,即为直接寻址。
- 对于中型文件,可以采用单级索引方式,需要先从 FCB 中找到该文件的索引表,从中获得该文件的盘块地址,即为一次间址。
- 对于大型或特大型文件,可以采用两级和三级素引分配方式。
文件长度的分析
- 直接地址。为了提高对文件的检索速度，在索引结点中可设置 10 个直接地址项，即
i.addr(0) ~i.addr(9)来存放直接地址，即文件数据盘块的盘块号。假如每个盘块的大小为4KB，当文件不大于 40KB时，便可直接从索引结点中读出该文件的全部盘块号。 - 一次间接地址。对于中、大型文件，只采用直接地址并不现实的。为此，可再利用索引结点中的地址项 i.addr(10)来提供一次间接地址。这种方式的实质就是一级索引分配方式。图中的一次问址块也就是索引块，系统将分配给文件的多个盘块号记入其中。在一次间址块中可存放1024 个盘块号，因而允许文件长达 4MB。
- 多次间接地址。当文件长度大于 4MB +40KB（一次间接地址与10 个直接地址项）时，系统还需采用二次间接地址分配方式。这时，用地址项 i.addr(11)提供二次间接地址。该方式的实质是两级索引分配方式。系统此时在二次间址块中记入所有一次间址块的盘号。地址项 iaddr(L)作为二次间址块，允许文件最大长度可达 4GB。同理，地址项 iaddr(12)作为三次间址块，其允许的文件最大长度可达 4TB。
警告
- 要会根据多层索引、混合索引的结构计算出文件的最大长度（Key：各级索引表最大不能超过一个块）；
- 要能自己分析访问某个数据块所需要的读磁盘次数（Key：FCB中会存有指向顶级索引块的指针，因此可以根据FCB读入顶级索引块。每次读入下一级的索引块都需要一次读磁盘操作。另外，要注意题目条件--顶级索引块是否已调入内存）
逻辑结构与物理结构的对比
逻辑结构
- 用户的视角所看到的样子
- 在用户看来，整个文件占用连续的逻辑地址空间
- 文件内部的信息组织完全由用户自己决定，操作系统并不关心
物理结构
- 由操作系统决定文件采用什么物理结构存储
- 操作系统负责将逻辑地址转变为（逻辑块号，块内偏移量）的形式，并负责实现逻辑块号到物理块号的映射
提示
类比于数据结构中，也存在逻辑结构与物理结构之分，如下所示:
就比如说，二叉树，我们用户所看到的视角就是一颗树状的结构（逻辑结构），但我们定义这个数据类型的时候，可以用链式存储（即常规方式）也可以顺序存储（用一个表格存储，记录对应的父节点的索引），此即对应的物理结构
放到操作系统中也是类似的，我们看到的文件如此，但是它究竟是如何存储的，是由操作系统决定的
内存索引结点中增加了一些内容，例如状态、访问计数 ↩︎