操作系统复习4.1.0-文件管理结构

定义

一组有意义的信息的集合

属性

文件名、标识符、类型、位置、大小、创建时间、上次修改时间、文件所有者信息、保护信息

操作系统向上提供的功能

创建文件、删除文件、读文件、写文件、打开文件、关闭文件
这6个都是系统调用

创建文件

创建文件时调用Create系统调用
首先在外存中找到文件
先在外存找到所需的空间，通过空闲链表法、位示图、成组链接法等管理策略，找到空闲空间
然后在文件存放路径的信息找到该目录对应的目录文件，在目录中创建该文件对应的目录项

删除文件

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项
根据目录项提供的外存地址，根据空闲表法、空闲链表法等回收文件占用的磁盘块
从目录表中删除文件对应的目录项

打开文件

删除文件

根据文件存放路径找到相应的目录文件，从目录中找到文件名对应的目录项，检查用户对文件的操作权限
将目标项复制到内存中的“打开文件表”中，并将对应表目的编号返回给用户，用户使用打开文件表的编号来指明要操作的文件
系统将读指针指向的外存中，将用户指定大小的数据读入用户指定的内存区域中

读文件

系统使用read系统调用完成写操作，需要指定哪个文件(打开文件表中的索引号)和读入多少数据，指明读入的数据要放在内存中的什么位置
系统从用户指定的内存区域中，将指定大小的数据写回写指针指向的外存

写文件

执行文件和写出数据大小，写回外存的数据放在内存的什么位置

文件存储

操作系统以块为单位分配存储空间，块等大，常包含2的整数幂个地址，外存也是由一个个存储单元组成，每个存储单元对应一个物理地址

逻辑结构

文件内组织结构：
无结构文件：如文本文件，由一些二进制或字符流组成，又称流式文件
有结构文件：如数据库表，由一组组相似的记录组成，又称记录式文件，记录是一组相关数据项的集合

根据记录长度又可分为定长记录和不定长记录

文件间组织结构：
目录、文件，目录内可以有目录和文件

根据有结构文件中的各条记录在逻辑上如何组织可以分为三类：顺序文件、索引文件、索引顺序文件

顺序文件

文件中的记录一个接一个顺序排列
又可细分为串结构和顺序结构，前者记录间顺序与关键字无关，后者则按关键字顺序排序
链式存储不支持随机存取
而顺序存储时，可变长记录则不支持随机存取，定长则可以

定长且顺序存储可实现随机存取，若再保证顺序结构，即可快速检索

索引文件

对于可变长记录文件，需要顺序查找
因此通过索引表，索引表本身是定长记录的顺序文件，可快速找到对应的索引项，

索引顺序文件

每个记录对应一个索引表项，因此索引表可能会很大，可能索引表比文件内容本身都大，因此改良为一个索引表项对应一组记录，但速率仍不够快

多级索引顺序文件就是最终改良，加入有10^6个组，以100个为1组，形成顶级索引表，次级索引表依次类推

文件目录实现

文件控制块FCB的有序集合称为文件目录，一个FCB就是一个文件目录项，FCB内包含了文件的基本信息、存取控制信息、使用信息，最主要为文件名和存放的物理地址

目录结构

单级目录结构、两级目录结构

多级目录结构(树型结构)

绝对路径为"/目录1/…/文件名"，为避免每次都低效地从根目录开始查找，
因此引入当前目录和相对路径，即当前已经处于目录2，就代表目录2的结构表已经载入内存中，无需再从目录1开始寻找，文件的地址用根目录从目录2开始的相对路径

但多级目录结构不利于文件共享

无环图目录结构

通过添加共享计数器记录共享结点的数量，且由于都指向同一个文件，所有用户都可看到文件数据的变化

索引结点FCB瘦身

现在的PCB除了文件名和物理位置外有许多冗余信息，如存取权限等，而FCB主要是通过文件名匹配读出文件其他信息，因此可以通过索引结点机制为FCB瘦身，通过文件名匹配索引结点指针，指针指向文件名外的所有信息

物理结构

操作系统管理磁盘块涉及两类：非空磁盘块和空闲磁盘块

非空闲磁盘块

文件数据获得分配存储空间的方式有三种：连续分配、链接分配、索引分配

磁盘中的存储单元也会被分为一个个块/磁盘块/物理块，磁盘块与内存块、页面等大

内存与磁盘间的数据交换都是以块为单位进行的，每次读入写出都为一块
由于外存管理是以块为单位，因此文件的逻辑地址空间被分为一个个的文件块，与内存相似地，也可分为(逻辑块号、块内地址)

连续分配

每个文件在磁盘上占有一组连续的块用户通过逻辑地址操作文件
(逻辑块号、块内地址)—>(物理块号、块内地址)
物理块号 = 起始块号 + 逻辑块号
而文件目录中记录了文件名和起始块号和块数，因此可以随机访问

连续分配优势在连续读写时的速度快
但文件的拓展不方便，需要经常挪位，且会产生碎片

链接分配

为文件分配离散的磁盘块

隐式链接

目录中记录文件名、起始块号和结束块号
每个磁盘块会保存指向下一个盘块的指针，且对用户透明
隐式链接的文件只支持顺序访问，外存利用率高，不会有碎片问题

显式链接

目录中记录文件名和起始块号，另设置文件分配表FAT，用于记录文件各个物理块的指针，每个磁盘仅设置一张FAT，开机后将FAT读入内存，并常驻内存，由于FAT表项等大，因此同样隐含块号

逻辑块号转换成物理块号的过程不需要读磁盘操作，且显示链接支持随机访问和顺序访问，过程间不需访问磁盘，速度更快，且不产生外部碎片，文件拓展方便

索引分配

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

逻辑块号—>物理块号
用户给出逻辑块号，系统查找对应的FCB，从FCB中可知索引表位置，再由索引表和逻辑块号得知物理块号，由此可知索引分配方式可以支持随机访问，文件拓展也容易实现，但索引表占用一定存储空间

但磁盘块大小有限，索引表放不下怎么办？

链接方案

一个文件比较大，需要多个索引块，那么将索引块间链接起来，但查询时效率低

多层索引

类同多级页表，磁盘块大小b/索引表项大小 = 每个磁盘块最多存放在的索引项数量a
文件最大长度：k层索引， a^k*b
k层索引，k+1磁盘读取操作

混合索引

两种模式混合，针对文件大小进行了方式的区分和选择，小文件就无需多次读取磁盘

空闲磁盘块

存储空间的划分和存储化

存储空间的划分：将物理磁盘划分为一个个文件卷(逻辑卷、逻辑盘)
磁盘分区：C、D、E盘
盘内分区为：目录区、文件区
目录区：存放文件目录信息FCB、用于磁盘存储空间管理的信息
文件区：用于存放文件数据

空闲表法

适用于连续分配方式，通过表记录第一个空闲盘块号和连续的空闲盘块号，当请求块时，使用首次适应算法，其他算法也可采用
回收时根据前后有无空闲区进行合并表项

空闲链表法

空闲盘块链

分配时，从链头开始一次摘下k个盘块分配，并修改空闲链的链头指针
回收时，回收的盘块依次挂到链尾，并修改链尾指针

空闲盘区链

分配时，采用首次适应、最佳适应等算法，从链头开始检索，若没有合适的连续空闲块，也可将不同盘区同时分配给一个文件
回收时，若回收区和某个空闲盘区相邻，则需要将回收区合并到空闲盘区，否则将回收区作为单独空闲盘区挂到链尾

位示图法

位示图法使用(字号i、位号j)，盘块号b = ni+j
字号i = b / n，位号j = b%n
0为空闲，1为盘块已分配

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

回收时
根据回收的盘块号计算出对应的字号、位号
将对应位设为0

成组链接法

空闲表法和空闲链表法不适用于大型文件系统，因为空闲表或空闲链表过大时，UNIX系统中采用了成组链接法对磁盘空闲块进行管理
文件卷的目录区中专门用一个磁盘块作为超级块，当系统启动时需要将超级块读入内存，并保证内存和外存中的超级块数据一致

超级块中存储下一组空闲盘块数和空闲块号

当需要分配内存块时，先检查第一个分组的块数是否充足，若充足则使用第一个分组里面取出需要数量的空闲块，若此时第一分组存放着下一组的信息，则需要将下一组的信息复制到超级块中

当第一组未满时，直接添加

第一组满了之后，将原本超级块信息复制到新回收块中，新回收块成为第一个分组

文件共享

基于索引结点的硬链接

索引结点有助于文件目录瘦身，因为文件检索只要文件名，其余信息放到索引结点，索引结点中设置链接计数变量count，用于表示链接到本索引结点上的用户目录项数，用户删除文件时count-1，count=0时系统删除文件

基于符号链的软链接

增添Link类型文件，存放指向目标文件的路径，类同快捷方式
当文件1被删除了，文件2仍存在，只是不能执行文件1

文件保护

口令保护

口令存放在文件对应的FCB或者索引结点，访问文件前需输入口令
口令空间开销小，验证也快
但口令放在系统内部，不够安全

加密保护

通过密码加密文件，加密后文件数据和原始数据不一样
保密性强，不需要存储密码
但编码和译码耗时

访问控制

每个文件的FCB中都有一个访问控制列表，记录各个用户可以对该文件执行哪些操作

文件系统层次结构