操作系统复习 第七章
第七章 文件管理
文件和文件系统
现代OS中是通过文件系统来组织和管理计算机中存储的数据
文件则是指具有文件名的若干相关元素的集合
基于文件系统的概念，可以把数据组成分为数据项、记录和文件三级
文件名
文件名
扩展名
文件类型
按用途分类:系统文件、用户文件和库文件
按文件中数据的形式分类:源文件、目标文件和可执行文件
按存取控制属性分类:只执行文件、只读文件和读写文件
组织形式和处理方式分类:普通文件、目录文件、和特殊文件
文件系统模型
对象及其属性。文件管理系统的对象有:文件、目录和磁盘存储空间。
对对象操纵和管理的软件集合。是文件管理的核心部分。实现了文件系统的大部分功能——对文件存储空间的管理、对文件目录的管理、将文件的地址转换机制、对文件读写管理以及对文件的共享和保护。
文件系统的接口。命令接口(用户与文件系统)和程序接口(用户程序和文件系统)。
文件操作
用户通过文件系统所提供的系统调用实施对文件的操作。最基本的文件操作有:创建文件、删除文件、读文件、写文件和设置文件的读/写位置。
但对于一个实际的OS,为了方便用户使用文件而提供了更多地对文件的操作，如打开和关闭一一个文件及改变文件名等操作。
文件的逻辑结构
类型
按文件是否有结构分类
有结构文件:是指由-一个以上的记录构成的文件，又把它称为记录式文件;
无结构文件，这是指由字符流构成的文件，故又称为是流式文件。
根据文件的组织方式，可把有结构文件分为三类:
顺序文件。由一系列记录按某种顺序排列所形成的文件。通常是定长记录
逻辑记录的排序
串结构：各记录之间的顺序与关键字无关。通常由时间来决定(从头开
始逐个查找)顺序结构:文件中的所有记录按关键字排列。可以按关键字的长短或英文字母书写排序。顺序结构的检索效率更高(可利用折半查找、插值查找法等)
优点:
顺序文件的最佳应用场合是在对文件中的记录进行批量存取时(即每次要读或写一大批记录)。
对于顺序存储设备(如磁带),也只有顺序文件才能被存储并能有效地工作。
缺点:
- 查找和增删记录比较困难
顺序寻址
隐性寻址
- 确定下一个记录的逻辑地址
显性寻址
可对定长记录实现直接或随机访问
通过文件中记录的位置
定长记录文件，可实现随机存储
变长记录文件，无法实现随机存储
通过关键字
索引文件。当记录可变长时，通常为之建立一张索引表，并为每个记录设置一个表项以加快对记录检索的速度。
按关键字建立索引
索引表本身是定长记录的顺序文件。因此可以快速找到第i个记录对应的索引项。
可将关键字作为索引号内容若按关键字顺序排列,则还可以支持按照关键字折半查找。
每当要增加/删除一个记录时,需要对索引表进行修改。
具有多个索引表的索引文件
- 可以用不同的数据项建立多个索引表
索引顺序文件。上述两种方式的结合。为文件建立一张索引表，为每一组记录中的第一个记录设置一个表项。
将变长记录顺序文件中的所有记录分为若干个组，如50个记录为一个组。然后为顺序文件建立一张索引表，并为每组中的第一个记录在索引表中建立一个索引项，其中含有该记录的关键字和指向该记录的指针。
若一个顺序文件有10000个记录,则根据关键字检索文件,只能从头开始顺序
查找(这里指的并不是定长记录),平均须查找5000(N/2)个记录。若采用索引顺序文件结构,可把10000个记录分为100组,每组100个记录。则需要先顺序查找索引表找到分组(共1 00个分组,因此索引表长度为100,平均需要查50次),找到分组后,再在分组中顺序查找记录(每个分组100个记录,因此平均需要查50次)。可见,采用索引顺序文件结构后,平均查找次数减少为50+50= 100次(根号N)
二级索引顺序文件
- 为了进一步提高检索效率,可以为顺序文件建立多级索引表。例如，对于一个含106个记录的文件,可先为该文件建立- -张低级索引表,每 100个记录为一组,故低级索引表中共有10000个表项(即10000个定长记录),再把这10000个定长记录分组,每组100个,为其建立顶级索引表,故顶级索引表中共有100个表项。
直接文件
可根据给定的关键字直接获得指定记录的物理地址。换而言之,
关键字本身就决定了记录的物理地址。
哈希(Hash)文件
这是目前应用最为广泛的一种直接文件。
它利用Hash函数(或称散列函数)可将关键字转换为相应记录的地址。
文件目录
通常在现代计算机系统中，都要存储大量的文件。为了能对这些文件实施有
效的管理,必须对它们加以妥善组织
实现”按名存取”
提高对目录的检索速度
文件共享
允许文件重名
文件控制块
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为”文件控制块(FCB)
FCB通常含有三类信息:
基本信息类。包括:文件名，文件物理位置，文件逻辑结构，文件的物理结构
存取控制信息类。包括:文件主的存取权限，核准用户的存取权限和一般用户的存取权限
使用信息类。包括:文件的建立日期和时间、文件上次修改的日期和时间及当前使用信息。
文件目录
- 把所有的FCB组织在一-起，就构成了文件目录，即文件控制块的有序集合
目录文件
- 为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件
索引节点
文件目录通常是存放在磁盘上的，当文件很多时，文件目录要占用大量的盘块。在检索目录文件的时候，需要将目录调入内存后比较文件名，但是只用到文件名，而不需要其它那些对文件的描述信息。所以便把文件名与文件信息分开，使文件描述信息单独形成-个索引结点。
磁盘索引结点
存放在磁盘上的索引结点。每个文件有唯一-的一 个磁盘索引结点，主要包括以下内容:
文件主标识符
文件类型
文件存取权限
文件物理地址
文件长度
文件链接计数
文件存取时间
内存索引结点、
放在内存中的索引结点。当文件被打开后，将磁盘索引结点拷贝到内存索引
结点中以便使用。比磁盘索引结点增加了以下内容:
索引结点编号
状态
访问计数;
文件所属文件系统的逻辑设备号
链接指针。
读取文件的流程
根据文件名找到其所在目录中的目录项，获取该目录的对应文件的inode
根据文件inode号，找到inode在磁盘的位置
根据inode中的对应关系，找到对应文件的盘块block;
读取文件
文件目录
目录结构的组织，关系到文件系统的存取速度，也关系到文件的共享性和安全性。因此，组织好文件的目录是设计好文件系统的重要环节。
单级目录
最简单的目录结构。整个文件系统中只建立一张目录表， 每个文件一个目
录项,目录项含有文件相关信息。状态位表明每个目录项是否空闲。优点
简单且能实现目录管理的基本功能
实现了”按名存取”
缺点
查找速度慢
不允许重名。多用户环境下重名难以避免
不便于实现文件共享
两级目录
为了克服单级目录所存在的缺点，可以为每个用户建立一个单独的用户文件目录UFD。由该用户所有文件的文件控制块组成。
在系统中再建立一个主文件目录MFD。在主文件目录中每个用户目录文件都占有一个目录项，其中包括用户名和指向该用户文件的指针。
基本克服了单级目录的缺点，并具有以下优点:
提高了检索目录的速度。
在不同的目录中可以有相同的文件名。
不同用户还可以使用不同的文件名来访问系统中的同一个共享文件。
用户不能对自己的文件进行分类
多级目录
现代操作系统通常采用三级或三级以上的目录结构，以提高目录的检索速度和文件系统的性能。多级目录结构又称为树型目录结构,主目录称为根目录，数据文件为树叶，其它目录为结点。
路径名
- 用户(或用户进程)要访问某个文件时要用文件路径名标识文件,文件路径名是个字符串。各级目录之间用”/“隔开。从根目录出发的路径称为绝对路径
当前目录
- 很多时候,用户会连续访问同一目录内的多个文件。显然，每次都从根目录开始查找是很低效的因此可以设置一个”当前目录”。 当用户想要访问某个文件时,可以使用从当前目录出发的相对路径
目录操作
创建目录
删除目录
不删除非空目录
可删除非空目录
改变目录
移动目录
链接(Link)操作
查找
目录查询技术
当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询，找出该文件控制块或对应索引结点;
然后根据FCB或索引结点中所记录的文件物理地址，换算出文件在磁盘上的物理位置;
最后通过磁盘驱动程序,将所需文件读入内存
线性检索法
Hash方法
- 建立了一张Hash索引文件目录，利用Hash方法进行查询，即系统利用用户提供的文件名并将它变换为文件目录的索引值，再利用该索引值到目录中去查找，显著地提高检索速度。
文件打开过程
用户访问某文件时，调用open(),系统的工作过程:
查找目录，找到指定的文件目录;
核对访问权限;
将文件目录项复制到“打开文件表(open-file table) “中
- “打开文件表”是open()系统调用关联的主要数据结构，用于记录系统中所有已打开的文件的信息。当用户再次需要访问文件时，不需要重复查找目录，而是通过返回的文件指针，直接找到“打开文件表”对应表项，进而得到文件在外存的地址。这样大大的减少了检索目录所带来的开销，提高了系统工作效率。
返回用户该文件在“打开文件表”中的指针fd。
文件关闭过程
当一个文件暂不使用时，就应撤消该文件在“已打开表”中的相应表目，以释放所占内存空间，这就是文件的关闭。及时关闭不用的文件，一方面节约了内存的开支， 另一方面把FCB的内容及时写回外存， 以免被意外情况破坏。
当用户调用close系统调用时，系统的工作过程:
核对用户的使用权限，一般只有文件的建立者和打开者才有权关闭文件;
根据fd查找“用户打开文件表”，释放该文件占用的表目;
检查读入内存的文件目录和文件索引节点是否已被修改，若已被修改，则需将该文件的文件目录项和文件索引节点重新写回外存，以保存做过的修改。
文件共享
操作系统为用户提供文件共享功能,可以让多个用户共享地使用同一个文件
注意:多个用户共享同一个文件,意味着系统中只有”一份”文件数据。并且只要某个用户修改了该文件的数据,其他用户也可以看到文件数据的变化。
如果是多个用户都”复制”了同一个文件,那么系统中会有”好几份”文件数据。
其中一个用户修改了自己的那份文件数据,对其他用户的文件数据并没有影响。
基于有向无环图的文件共享
有多个属于不同用户的多个目录，同时指向同-个文件,这样虽会破坏树的特性，但这些用户可用对称的方式实现文件共享，而不必再通过其属主目录来访问。
在文件目录中只设置文件名及指向相应索引结点的指针
索引结点中设置一个链接计数变量count ,用于表示链接到本索引结点上的用户目录项数。
利用符号链接实现文件共享
利用符号链接实现文件共享的基本思想，是允许一个文件或子目录有多个父目录，但其中仅有一个作为主(属主)父目录，其它的几个父目录都是通过符号链接方式与之相链接的(简称链接父目录)。
为使链接父目录D5能共享文件F8,可以由系统创建一个LINK类型的新文件， 也取名为F8,并将F8写入链接父目录D5中，以实现D5与文件F8的链接。在新文件F中只包含被链接文件F8的路径名。这样的链接方法被称为符号链接。新文件F中的路径名则只被看做是符号链。
优点
- 在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的
指针;而共享该文件的其他用户则只有该文件的路径名，不会出现指针悬
空的情况。
- 在利用符号链方式实现文件共享时，只是文件主才拥有指向其索引结点的
问题
当其他用户去读共享文件时，系统是根据给定的文件路径名逐个分量(名)地去查找目录，直至找到该文件的索引结点。因此，在每次访问共享文件时，都可能要多次地读盘。这使每次访问文件的开销甚大，且增加了启动磁盘的频率。
要为每个共享用户建立一条符号链，而由于链本身实际上是一个文件，尽管该文件非常简单，却仍要为它配置一个索引结点，这也要耗费一定的磁盘空间。
文件保护
访问权
- 我们把一个进程能对某对象执行操作的权力，称为访问权(Access right)。
保护域
“域”是进程对一组对象访问权的集合，进程只能在指定域内执行操作
“域”规定了进程所能访问的对象和能执行的操作
进程和域间的静态联系
- 在进程和域之间可以一对应，即一个进程只联系着一个域。这意味着,在进程的整个生命期中，其可用资源是固定的，我们把这种域称为’静态域”
进程和域间的动态联系方式
在进程和域之间，也可以是一对多的关系，即一个进程可以联系着多个域
可将进程的运行分为若干个阶段，其每个阶段联系着一个域，这样便可根据运行的实际需要来规定在进程运行的每个阶段中所能访问的对象。
基本的访问矩阵
- 访问矩阵中的行代表域，列代表对象，矩阵中的每一项是由一组访问权组成的。
访问控制表(Access Control List)
对访问矩阵按列(对象)划分，为每一列建立一张访问控制表ACL
在该表中，已把矩阵中属于该列的所有空项删除，此时的访问控制表是由一有序对(域，权集)所组成的。
使用访问控制表可以显著地减少所占用的存储空间，并能提高查找速度。
在每个文件的FCB (或索引结点)中增加一个访问控制列表(Access-Control List, ACL)该表中记录了各个用户可以对该文件执行哪些操作。
精简的访问列表:以“组”为单位，标记各“组”用户可以对文件执行哪些操作。
如果把访问矩阵按行(即域)划分，便可由每一行构成一张访问权限表。换言之，这是由一个域对每一个对象可以执行的一组操作所构成的表。