操作系统原理：文件系统

文件系统概念文件逻辑结构与存取方法文件的物理结构与存储设备文件存储空间管理文件系统(外存管理）文件目录管理文件存取控制文件使用文件系统层次模型文件系统(外存管理）1、信息的存储单位是文件；2、文件系统功能：负责信息的组织、存储和访问；3、文件系统的特点

提供高效、快速和方便的信息存储和访问功能。6.1文件系统概念6.1.1文件系统功能1、操作系统的软硬件管理2、文件管理功能（1）方便用户对文件的访问和控制（2）并发文件访问和控制（3）统一的用户接口6.1.1文件系统功能2、文件管理功能（4）设置多种文件访问权限（5）优化性能：存储效率、检索性能、读写性能；（6）差错恢复：验证文件的正确性，具有一定的差错恢复能力。2、文件管理的目的1.文件概念与文件名文件是具有名字的一段程序或数据的集合，是相关字符流的集合或相关记录的集合。文件名是文件的标识符号。6.1.2文件与文件系统的基本概念2、文件组成（1）文件体：文件本身的信息（2）文件说明：文件存储和管理信息6.1.2文件与文件系统的基本概念对操作系统的文件系统而言,一个源程序、一批数据、一篇文章或一张图片等都可以被称为文件,只要它是()连续分布在一片磁盘区域中的信息集合A采用链接方式连接起来的多个磁盘块组成的信息集合B逻辑上具有完整意义的信息集合C属于同一个用户的一个信息集合D提交单选题1分3.文件系统基本概念文件系统是操作系统中管理文件的机构，是与管理文件有关的软件以及数据的统称；它负责为用户建立、撤销、读写、修改和复制文件，能提供文件存储和访问功能。6.1.2文件与文件系统的基本概念4.文件系统特点（1）友好的用户界面；（2）文件操作对用户透明：对文件按名存取；（3）容易实现文件共享：文件可以被多个用户共享；（4）存储介质空间大、价格便宜。6.1.2文件与文件系统的基本概念5、文件分类（1）按存放时限临时文件、永久文件和档案文件。（2）按设备类型磁盘文件、磁带文件、卡片文件和打印文件等。6.1.2文件与文件系统的基本概念5.文件分类（3）按文件的组织结构文件的逻辑结构：流式文件和记录式文件。文件的物理结构（物理文件）：顺序文件、链接文件和索引文件等。6.1.2文件与文件系统的基本概念逻辑文件可以有_________这几种形式。目录文件A永久文件B流式文件C文本文件D记录式文件E提交多选题1分5、文件分类（4）按文件的性质和用途划分系统文件。用户只能调用，不能修改；库文件。允许用户读取和执行，不允许修改；用户文件。文件的建立者能够拥有所有的权限6.1.2文件与文件系统的基本概念如果按文件的用途来分类,可将文件分为_________。系统文件A永久文件B用户文件C逻辑文件D库文件E提交多选题1分5、文件分类（5）按组织形式普通文件。包括系统文件、用户文件和库函数文件和实用程序等；目录文件。由目录信息构成的特殊文件；特殊文件。所有输入、输出设备组成的文件6.1.2文件与文件系统的基本概念6、文件分类的原因为了更好地管理和使用，不仅提高了文件的存取速度，对文件的共享和保护也有利。6.1.2文件与文件系统的基本概念使用文件的用户需要记住的是()存储块的状况,即已用还是空闲A文件在磁盘上的存储位置B文件中各个记录所在的块的块号C文件的名字D提交单选题1分磁盘设备驱动程序磁带设备驱动程序基本文件系统基本I/O管理程序逻辑I/O堆顺序索引顺序索引哈希用户程序1、文件系统结构图6.1.3文件系统的结构和功能元素2、文件系统结构组成（1）设备驱动程序：负责启动该设备上的I/O操作，处理I/O请求的完成；（2）基本文件系统（物理I/O层）：处理与磁盘或磁带交换的数据块。（3）基本I/O管理程序：负责所有文件I/O的开始或结束、选择执行文件的I/O设备和外存的分配。6.1.3文件系统的结构和功能元素2、文件系统结构组成（4）逻辑I/O：使用户和应用程序能够访问到记录。物理I/O层处理的是数据块，逻辑I/O处理的是文件记录。（5）访问方法层：与用户最近的一层。6.1.3文件系统的结构和功能元素3.文件系统服务功能元素（1）文件访问：文件的创建、打开、关闭和读写；（2）目录管理：用于文件访问和控制的信息（3）文件结构管理：划分记录，包括顺序与索引结构6.1.3文件系统的结构和功能元素3.文件系统服务功能元素（4）访问控制：并发访问和用户权限；（5）限额(quota)：限制每个用户能够建立的文件数目、占用外存空间大小等；（6）审计(auditing)：记录对指定文件的使用信息，保存在日志中；6.1.3文件系统的结构和功能元素3.文件系统服务功能元素（7）文件的分块存储：与外存的存储块相配合（8）I/O缓冲和调度：性能优化（9）文件定位：在外存上查找文件的各个存储块6.1.3文件系统的结构和功能元素3.文件系统服务功能元素（10）外存存储空间管理：如硬盘空间分配和释放；（11）外存设备访问和控制：包括由设备驱动程序支持的各种基本文件系统如硬盘等。6.1.3文件系统的结构和功能元素文件系统应具有的功能包括()。实现“按名存取”外存上的文件A分配文件的存储空间B实现文件目录管理C提供合适的存取方法以适应各种不同的应用D实现文件的共享、保护和保密E提交多选题1分6.2文件的逻辑结构与存取方法文件逻辑结构主要讨论文件的内部逻辑结构，主要考虑因素是文件存储性能和访问性能。6.2.1文件的逻辑结构1、文件的逻辑结构定义是指文件内部信息的组织方式，即文件内部的逻辑结构，是用户可以直接处理的数据及其结构。它独立于在外存上的物理存储。6.2.1文件的逻辑结构2、文件逻辑结构的设计要求（1）访问性能：便于检索和修改；（2）存储性能：向物理存储转换方便、节省空间3、文件信息的不同组织层次：域、记录、文件文件的逻辑结构是指()文件所在的设备的结构A文件在设备中的存储方式B文件目录的结构C文件的使用者组织文件中信息的方式D提交单选题1分4、文件的逻辑结构分类（1）无结构文件文件体为字节流，不划分记录，顺序访问，每次读写访问可以指定任意数据长度；当前操作系统中常用的文件组织。6.2.1文件的逻辑结构4、文件的逻辑结构分类（2）有结构文件－记录式文件

记录概念：一个具有特殊意义的完整的信息单位6.2.1文件的逻辑结构图6.2记录组成典型记录的组成元素4、文件的逻辑结构分类（2）记录式结构文件分类连续结构多重结构转置结构顺序结构6.2.1文件的逻辑结构连续结构概念：把记录按生成的先后顺序连续排列的逻辑结构；特点：记录的排列顺序与记录内容无关，有利于记录的追加和变更；缺点：查找性能比较差。（2）记录式结构文件分类6.2.1文件的逻辑结构多重结构概念：把记录按关键字和记录名排列成行列式结构，则一个包含n个记录名、m个关键字的文件构成一n×m维行列式。特点：能根据关键字和记录名快速定位某条记录缺点：浪费空间，n条记录需要n*m的空间（2）记录式结构文件分类多重结构改进措施：采用多重队列。将行列式中为0的项去除，以关键字ki为队首，以包含关键字ki的记录为队列元素构成一个记录队列。M个关键字就构成了多个队列。（2）记录式结构文件分类多重结构及改进图图6.3文件的记录名和关键字构成的行列式图6.4文件的多重结构转置结构把含有相同关键字的记录指针全部指向该关键字，即把所有与同一关键字对应的记录指针连续置于目录中该关键字位置，是对多重结构的变化。（2）记录式结构文件分类转置结构

图6.5文件的转置结构（2）记录式结构文件分类顺序结构（索引结构）概念：按照某种关键字排序进行存放优点：能够根据待查记录的关键字快速找到某个记录（2）记录式结构文件分类（1）累积文件——pile堆文件文件体为无结构记录序列，通过分隔符来划分记录，各记录大小和组成可变。新记录总是添加到文件末尾。如日志log，或电子邮件的邮箱文件(mailbox)。检索必须从头开始。是一种简单的文件组织方式，当数据难以组织时使用。5、记录式文件结构具体实例（1）累积文件——pile堆文件5、记录式文件结构具体实例（2）顺序文件文件体为大小相同、格式固定的排序记录序列；它由一个主文件和一个临时文件组成；记录按某个关键字域排序，存放在主文件中；5、记录式文件结构具体实例（2）顺序文件新记录暂时保存在日志或事务文件等临时文件中，定期归并入主文件，并按正确顺序产生一个新文件；访问时可以采用二分搜索。5、记录式文件结构具体实例（2）顺序文件5、记录式文件结构具体实例（3）索引顺序文件在顺序文件的基础上，另外建立索引和溢出文件；在索引文件中，可将关键字域中的取值划分若干个区间，每个区间对应一个索引项。新记录暂时保存在溢出文件中，定期归并入主文件；主文件中记录要求做到分块有序。5、记录式文件结构具体实例（3）索引顺序文件5、记录式文件结构具体实例5、记录式文件结构具体实例（3）索引顺序文件（4）哈希文件或直接文件

（记录逻辑地址通过关键字哈希之后直接获得）直接访问磁盘中任何一个地址已知的块；由主文件和溢出文件组成；记录位置由哈希函数确定。访问速度快；5、记录式文件结构具体实例1、文件内容操作类型（1）读：存储介质→内存（2）写：内存→存储介质6.2.2文件的存取方法2.文件存取方法（1）顺序存取法:按照文件信息的逻辑顺序依次存取；（2）随机存取法(直接存取）:可以按任意的次序对文件进行读写操作；（3）索引存取：对文件中的记录按某个数据项的值进行排列，可根据键值来快速存取。6.2.2文件的存取方法3、记录搜索算法（1）线性搜索法（用在顺序文件）（2）散列法（用在哈希文件）（3）二分搜索法（用在是有序文件）6.2.2文件的存取方法3、记录搜索算法（1）线性搜索法特点：从第一个记录开发搜索，直到找到或在未找到情况下搜索到最后一个记录结束。缺点：搜索效率低。6.2.2文件的存取方法3、记录搜索算法（2）散列法定义：根据关键字值，采用相应的散列函数，得到某个记录在文件中的逻辑地址。特点：能够根据关键字快速定位相同关键字的记录，在最理想情况下能够一次定位。6.2.2文件的存取方法3、记录搜索算法（3）二分搜索法首先要根据关键字大小进行排序，每次取记录中间值和待查关键字进行比较，以此类推。6.2.2文件的存取方法4、影响文件存取方法的因素（1）文件的使用

文件的性质决定了文件的使用，也决定了存取方式的选择。例如，如源程序文件用顺序存取法、数据库文件用随机存取法6.2.2文件的存取方法4、影响文件存取方法的因素（2）存储介质的特性磁带：适合顺序存取。磁盘：既可采用顺序存取方式，又可采用随机存取方式。6.2.2文件的存取方法6.3文件的物理结构与存储设备（重点）1、文件的物理结构2、文件的存储设备从文件在物理介质上的存放方式来研究文件。连续结构（顺序）串联结构索引结构(重点）6.3.1文件的物理结构（1）一个文件的信息存放在若干连续物理块中。目录文件名起始地址大小Hello.c22Zl.c95z.out21301516311、连续结构(顺序结构)（2）优点简单，适用于一次性写入的操作；支持顺序存取和随机存取，速度快；所需的磁盘寻道次数和寻道时间最少。1、连续结构(顺序)（3）缺点

文件不能动态增长（可能文件末尾处的空块已经分配给别的文件）不利于文件插入和删除外部碎片问题（反复增删文件后）1、连续结构(顺序)文件A第一个物理块号文件长度（4）文件说明信息10131211…...物理存储设备0123物理块号逻辑块号1.连续结构(顺序)类似于数组1.连续结构－存储图示连续存储结构图（1）概念一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块。2、串联结构第一个物理块号……文件说明信息2215物理存储设备0123物理块号逻辑块号连接指针250201522252、串联结构2.串联结构—图示链式存储结构图2.串联结构—优缺点（2）优点提高了磁盘空间利用率,不存在外部碎片问题；有利于文件插入和删除，但效率不高；

有利于文件动态扩充。（3）缺点存取速度慢，不适于随机存取；可靠性问题，如指针出错；

更多的寻道次数和寻道时间；链接指针占用一定的空间。2.串联结构—优缺点某文件共有4个记录L0~L3,采用链接存储结构,每个记录及链接指针占用一个磁盘块,主存储器中的磁盘缓冲区的大小与磁盘块的大小相等。为了在L2和L3之间插入一个记录L2',需要进行的磁盘操作有()4次读盘和2次写盘A4次读盘和1次写盘B3次读盘和2次写盘C3次读盘和1次写盘D提交单选题1分3、索引结构（重点）主流的文件物理结构。（1）概念一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构--索引表，并将这些块的块号存放在一个索引表中。（索引表类似于目录表）（2）索引表

一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块。索引表每个条目是逻辑块号与物理块号的映射，需要占据一定的外存空间。3、索引结构思考索引表的存放？大文件如何处理？3、索引结构3、索引结构3、图示索引存储结构图3.索引结构——优缺点（3）优点：保持了链接结构的优点,又解决了其缺点。即能顺序存取,又能随机存取满足了文件动态增长、插入删除的要求（只要有空闲块）能充分利用外存空间（4）缺点

较多的寻道次数和寻道时间，索引表本身带来了系统开销。如：内外存空间，存取时间。3.索引结构——优缺点文件在相应存储介质上的组织方式也有差异。通常文件的存储结构有_________。流式结构A顺序结构B链接结构C记录式结构D索引结构E提交多选题1分4、索引表组织（考试重点）（1）索引表组织又称多级索引，除了最后一层索引表所指的物理块存放文件信息以外，其它层次的索引表存放着下一层索引表的物理块地址。多重索引结构图6.11多重索引（二级索引）结构案例：UNIX文件系统采用的多级索引结构Unix多级索引存储结构图分析：每个文件的索引表为13个索引项，每项2个字节；直接寻址：前10项直接登记存放文件信息的物理块号;一次间接寻址：第11项指向一个物理块，该块中最多可放256个文件物理块的块号；UNIX文件系统采用的是多级索引结构。分析：二次和三次间接寻址：分别为第12和第13项；采用了三级间接索引结构后，Unix文件最大可达16兆个物理块（10+256+2562+2563）=（10+256+216+224）UNIX文件系统采用的是多级索引结构设文件索引节点中有7个地址项,其中4个地址项为直接地址索引,2个地址项是一级间接地址索引,1个地址项是二级间接地址索引,每个地址项大小为4字节,若磁盘索引块和磁盘数据块大小均为256字节,则可表示的单个文件的最大长度是()。33KBA519KBB1057KBC16513KBD提交单选题1分下列文件物理结构中,适合随机访问且易于文件扩展的是()。连续结构A索引结构B链式结构且磁盘块定长C链式结构且磁盘块变长D提交单选题1分某旅行社实行会员制,成为会员的游客的信息都登记在会员文件中。会员文件的主要用途是存储、检索、增删和修改会员信息,每个会员占用文件中的一条记录。由于生意兴隆,会员文件的规模很大。为了快速完成对该文件的每一次操作,并充分利用存储该文件的设备的存储空间,适宜于该文件的存储结构是()记录结构A索引结构B链接结构C顺序结构D提交单选题1分某文件系统采用索引文件结构，设文件索引表的每个表目占2个字节，磁盘块大小为512B。试问该文件系统采用直接、一次间接和二次间接索引能管理的最大磁盘空间为多少字节?作答正常使用主观题需2.0以上版本雨课堂主观题10分解答：解：计算索引表项的大小，索引表项=512/2=256个直接索引，每项对应一个物理块，能管理的最大磁盘空间=256*512B=217B=128KB二级索引，能管理的最大磁盘空间=256*256*512B=216*512B=32MB三级索引，能管理的最大磁盘空间=256*256*256*512B=224*512B=8GB4.存取设备、物理结构和存取方法之间的关系存取设备

磁盘磁带物理结构顺序结构链接结构索引结构顺序结构存取方法随机或顺序顺序随机或顺序顺序文件长度固定可变，固定可变，固定固定文件的存储方法依赖于()。文件的物理结构A存放文件的存储设备的特性BA和BC文件的逻辑结构D提交单选题1分1、顺序存取设备

只有在前面的物理块被访问过之后，才能存取后续的物理块的内容。如：磁带6.3.2文件的存储设备2、直接（随机）存取设备：存取磁盘上任一物理块的时间不依赖于该物理块所处的位置。如：磁盘6.3.2文件的存储设备2、直接（随机）存取设备磁盘分类：固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高；移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低。6.3.2文件的存储设备

1、磁带－顺序存储设备图6.12磁带的结构影响磁带设备的存取速度或数据传输率因素：（1）信息密度（2）磁带速度（3）块间间隙2、直接存储设备（随机存取）图6.13磁盘的结构柱面扇区磁臂磁头2、直接存储设备图示磁盘存储相关专业名词：（1）扇区：介质划分的最小单位；（2）块(簇)：与内存交换数据的最小单位，由多个扇区组成，又

称为物理块。（3）文件卷：一个独立的可装卸的文件存储介质。（4）柱面（5）磁道（6）物理地址形式：磁头号、磁道号、簇号（块号）2、直接存储设备（随机存取）磁盘上一物理块的位置可由参数()确定。字节号A柱面号B簇号C磁头号D缓存地址E提交多选题1分假设磁盘有256个柱面,4个磁头,每个磁道有8个簇(它们的编号均从0开始)。文件ABC在盘面上连续存放。如果ABC中的一个块放在5号柱面、1号磁头下的第7簇,那么ABC的下一块应该在()5号柱面、2号磁头下的第7簇A5号柱面、2号磁头下的第0簇B6号柱面、1号磁头下的第7簇C6号柱面、1号磁头下的第0簇D提交单选题1分2、直接存储设备磁盘存取数据时间组成：（1）寻道时间：磁头水平移动定位到指定磁道；（2）旋转延迟时间：等待指定扇区从磁头下旋转经过；（3）数据传输时间：数据在磁盘与内存之间的实际传输。2、直接存储设备（随机存取）3.光盘（1）光盘容量大，速度快，价格便宜，但一般不可写；（2）可读写光盘驱动器价格贵，写过程很麻烦；（3）光盘的空间结构与磁盘类似。6.4磁盘设备管理

磁盘I/O访问时间的组成磁盘I/O调度策略（重点）磁盘缓存置换算法6.4磁盘设备管理6.4磁盘设备管理6.4.1磁盘I/O访问时间的组成1、磁盘存取数据时间磁道定位时间：磁头移动到指定磁道的机械运动时间旋转延迟时间：磁盘旋转到指定扇区的机械运动时间；它与磁盘转速相关。数据传送时间：从指定扇区读写数据的时间2、影响磁盘存取时间因素由于磁道定位时间在访问时间中占主要部分，合理组织磁盘数据的存储位置可提高磁盘I/O性能。6.4.1磁盘I/O访问时间的组成例：读一个128KB大小的文件(1)文件由8个连续磁道(每个磁道32个扇区)上的256个扇区构成：20ms+(7ms+16ms)*8=204ms;其中，磁道定位时间为20ms，旋转延迟时间为7ms，每个扇区数据传输时间为0.5ms，32扇区数据传送时间为16ms；6.4.1磁盘I/O访问时间的组成例：读一个128KB大小的文件(2)文件由256个随机分布的扇区构成：(20ms+7ms+0.5ms)*256=7040ms;其中，1扇区数据传送时间为0.5ms；随机分布时的访问时间为连续分布时的34.5倍。6.4.1磁盘I/O访问时间的组成6.4.2磁盘I/O调度策略（重点）1.问题的提出有若干个访问者请求磁盘执行输入输出操作，应先让哪一个访问者完成操作？当多个访盘请求在等待时，采用一定的策略，对这些请求的服务顺序调整安排，旨在降低平均磁盘服务时间，达到公平、高效2.磁盘调度策略考虑的问题根据移动臂的当前位置使寻道时间尽可能小的那个访问者优先得到服务。6.4.2磁盘I/O调度策略（重点）3.磁盘调度算法－移臂调度（1）先进先出算法（2）优先级算法（3）后进先出算法（4）短查找时间优先算法3.磁盘调度算法－移臂调度（5）扫描(SCAN)算法（重点）（6）循环扫描(C-SCAN)算法（7）N步扫描(N-step-SCAN)算法（8）双队列扫描(FSCAN)算法（1）先进先出(FIFO)算法原理：磁盘I/O执行顺序为磁盘I/O请求的先后顺序；优点：公平；缺点：效率不高。3.磁盘调度算法－移臂调度（1）先进先出算法例：磁盘访问序列：

98，183，37，122，14，124，65，67。读写头起始位置：53；磁头正往高磁道方向走；计算磁头移动总距离（道数）。3.磁盘调度算法－移臂调度（1）先进先出算法3.磁盘调度算法－移臂调度（2）后进先出(LIFO)算法算法思想：后产生的磁盘I/O请求，先执行。算法设计依据：是基于磁盘I/O的局部性特征，相邻访问的位置也相邻。缺点：可能有进程的磁盘I/O永远不能执行，处于饥饿状态。3.磁盘调度算法－移臂调度（3）短查找时间优先(SSTF)算法思想：选择从当前磁头位置出发，移动最少的磁盘I/O请求。特点：是使每次磁头移动时间最少。缺点：对中间的磁道有利，可能会有进程处于饥饿状态。3.磁盘调度算法－移臂调度短查找时间优先(SSTF)算法案例：访问磁道顺序为98，183，37，122，14，124，65，67。3.磁盘调度算法－移臂调度（4）扫描(SCAN)算法－电梯式算法（重点）算法思想：在磁头前进方向上，选择从当前位置移动最少的磁盘I/O请求执行，没有前进方向上的请求时才改变方向。3.磁盘调度算法－移臂调度（4）扫描(SCAN)算法－电梯式算法优点：该算法是对SSTF算法的改进，是一种简单、实用且高效的调度算法，没有进程会饿死；缺点：实现时除了要记住读写磁头的当前位置外，还必须记住移动臂的移动方向。3.磁盘调度算法－移臂调度

扫描(SCAN)算法－电梯式算法

案例：98，183，37，122，14，124，65，67。

3.磁盘调度算法－移臂调度（4）扫描(SCAN)算法－电梯式算法3.磁盘调度算法－移臂调度假设磁头当前位于第105道,正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45,12,68,110,180,170,195,采用SCAN调度(电梯调度)算法得到的磁道访问序列是()。110,170,180,195,68,45,35,12A110,68,45,35,12,170,180,195B110,170,180,195,12,35,45,68C12,35,45,68,110,170,180,195D提交单选题1分（5）循环扫描(C-SCAN)算法（单向扫描算法）算法思想：在一个方向上使用扫描算法，当到达边沿时直接移动到另一沿的第一个位置。调度实现：总是从0号磁道开始向里扫描，依次选择所遇到的访问者；移动臂到达最后一个磁道时，立即带动读写磁头快速返回到0号磁道，返回后再次进行扫描。3.磁盘调度算法－移臂调度可以作为磁盘移臂调度的算法有__________。先来先服务算法A最短寻找时间优先算法B扫描(电梯)算法C时间片轮转D可抢占优先级调度E提交多选题1分1.新创建文件的存储空间分配方法（1）预分配：创建时一次分配指定的存储空间；（2）动态分配：需要存储空间时才分配，如写入数据到文件。6.5文件存储空间管理（重点）2.文件存储单位:簇（cluster）文件的存储空间通常由多个分立的簇组成，而每个簇包含若干个连续的扇区(sector)。

簇是外部存储介质分配的基本单位，又称为物理块。6.5文件存储空间管理2.文件存储单位:簇（1）簇较大：提高I/O访问性能，减小管理开销；但簇内碎片浪费问题较严重；（2）簇较小：簇内的碎片浪费较小，特别是大量小文件时有利；但存在簇编号空间不够的问题（如FAT32）。6.5文件存储空间管理3.文件存储空间分配方法（1）连续分配：只需记录第一个簇的位置，适用于预分配方法；（2）链式分配：在每个簇中有指向下一个簇的指针；（3）索引分配：文件的第一个簇中记录了该文件的其他簇的位置。6.5文件存储空间管理4、磁盘空闲空间管理方法（1）磁盘分配表

磁盘空闲空间管理的数据结构。

磁盘分配的基本单位是簇。6.5文件存储空间管理4、磁盘空闲空间管理方法（1）空闲文件目录：在一个空闲簇中记录其他几个空闲簇的位置；（2）位示图(bitmap):块寻址算法；（3）空闲空间链接；（4）成组链接法(重点）。上述4种方法都可以实现整个硬盘空间管理的数据结构6.5文件存储空间管理（1）空闲文件目录将文件存储设备上的每个连续空闲区看作一个空白文件，每个空白文件在这个目录表中占用一个表目；表目的内容包括第一个空白块的地址（物理块号）和空白块的数目；分配和回收过程：扫描目录表，找到符合条件的项。4、磁盘空闲空间管理方法（1）空闲文件目录序号第一个空白块号空白块个数备注：物理块号153（5，6，7）2135（13，14，15，16，17）3206（20，21，22，23，24，25）4-----思考：空闲文件目录存储在哪里？4、磁盘空闲空间管理方法（2）空闲块链在每个空白块中建立一个链接指针，指向下一个空白块的位置；分配时，从头指针的位置依次取下几块空白块分配给文件；遍历的效率低。4、磁盘空闲空间管理方法YWZ……

首指针XXYWZ改进：一块中存放多个空闲块的块号，成组块链法。（2）空闲块链4、磁盘空闲空间管理方法（3）成组链法4、磁盘空闲空间管理方法（3）成组链法（3）成组链法1）成组链法的工作原理把文件存储设备的所有空闲块按100块划分为一组，组的划分从后往前进行；每组的第一块用来存放前一组中各块的块号和总块数（相当于指针域），总块数基本固定为100；4、磁盘空闲空间管理方法（3）成组链法

1）成组链法的工作原理

第一组为99空闲块，因为第一组前面没有其他组；最后一组有可能不够100，存储设备的空闲块不一定是100的倍数，该组的物理块号和总块数放在文件资源管理表中；4、磁盘空闲空间管理方法（3）成组链法2）成组链法的磁盘空闲空间的分配和释放系统启动，文件资源管理表复制到内存，在内存中存放最后一组空闲块的块号和总块数的堆栈，在内存中进行空闲块的分配和释放；在分配和释放空闲块中始终有堆栈指针为Ptr，Ptr的初始值为该组空闲块的总块数，在分配时该指针值减1；4、磁盘空闲空间管理方法（3）成组链法2）成组链法的分配和释放当堆栈中只剩下最后一个空闲块号时，系统启动设备管理程序，将下一组的块号和总块数读入内存，并重设Ptr指针大小；在删除文件进行空间回收时，Ptr值加1；当Ptr值为100，当有新的块需要回收时，回收该块；然后Ptr值重设为1另起一个新组。4、磁盘空闲空间管理方法某个系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态如下图所示。

（1）

该磁盘中目前最后一组有多少个空闲盘块？

最后一组的空闲物理块编号范围多少？（2）

在下图基础上，在为某个文件分配102个盘块后，请画出分配该文件后的盘块链接情况；（3）在下图基础上，系统删除某个文件，该文件大小为6个盘块，它们的盘块号依次为100、111、103、188、101，122，请画出回收该文件物理块后的盘块链接情况。作答主观题10分（4）位示图（重点）4、磁盘空闲空间管理方法磁盘上空闲块的管理方法,通常可采用_________。位示图法A逻辑文件法B物理文件法C空闲块链接法D索引文件法E提交多选题1分为实现磁盘空间的高效分配与回收,操作系统一般采用的是()位示图法A单块链接法B成组链接法C索引链接法D提交单选题1分5、文件卷（1）磁盘分区：通常把一个物理磁盘的存储空间划分为几个相互独立的部分；（2）文件卷：格式化的分区。在同一个文件卷中使用同一份管理数据进行文件分配和外存空闲空间管理。（3）格式化：在一个文件卷上建立文件系统。建立并初始化用于进行文件分配和外存空闲空间管理的管理数据；进行格式化使得一个文件卷上原有的文件都被删除。5、文件卷

目录内容目录结构类型文件别名的实现目录是由文件说明组成的用于文件检索的特殊文件。6.5文件目录管理6.5.1目录内容1、文件的组成（1）组成部分：文件说明和文件体；（2）文件体：文件本身信息；（3）文件说明：又叫文件控制块（FCB)，是文件的控制信息。6.5.1目录内容2、目录文件（1）组成内容：由多个文件说明组成；（2）作用：文件系统利用目录文件完成按名存取和对文件信息的共享与保护。1、基本信息文件名：有多个别名；别名的数目；文件类型。目录的内容是文件属性信息。6.5.1目录内容文件类型有无结构（记录文件，流式文件）内容（二进制，文本）用途（源代码，目标代码，可执行文件，数据）属性attribute（如系统，隐含等）文件组织（如顺序，索引等）按组织形式分：目录文件、特殊文件、普通文件6.5.1目录内容2、地址信息存放位置：包括哪个设备或文件卷，以及各个存储块位置；文件长度：以字节、字或存储块为单位。6.5.1目录内容3、访问控制信息文件所有者：通常是创建文件的用户，或者改变已有文件的属主；访问权限：控制各用户可使用的访问方式。如读、写、执行、删除等；6.5.1目录内容4、使用信息创建时间；最后一次读访问的时间和用户；最后一次写访问的时间和用户；6.5.1目录内容目录文件所存放的信息是()。某一文件存放的数据信息A某一个文件的文件目录B该目录中所有数据文件目录C该目录中所有子目录文件和数据文件的目录D提交单选题1分磁盘上的文件目录由若干目录项组成,目录项中应该包含_________。文件在内存地址A文件名B存取权限C文件的建立日期D在磁盘的存放地址E提交多选题1分

1、单级目录

整个目录组织是一个线性结构，系统中的所有文件都建立在一张目录表中。它主要用于单用户操作系统。6.5.2文件目录类型

1、单级目录

特点：结构简单；文件多时，目录检索时间长；有命名冲突6.5.2文件目录类型单级目录的读写处理过程

2、二级目录（1）定义：在根目录下，每个用户对应一个目录称为第二级目录；主目录（MFD）:不同用户的目录的有关信息；用户文件目录（UFD）：用户文件的说明信息所组成的目录文件。6.5.2文件目录类型二级目录结构图2、二级目录（2）特点适用于多用户系统，各用户可有自己的专用目录；提高了文件的检索速度；部分的允许文件名重名；便于文件共享6.5.2文件目录类型根目录ZImagebashmore一级目录根目录ZImagebashmorerootzhaoQianreadmeZ1.cZ2.c二级目录6.5.2文件目录类型（1）目录相关专业名词目录名：可以修改;目录树：中间结点是目录，叶子结点是目录或文件；目录的上下级关系：当前目录、父目录、子目录等；路径(path)：绝对路径、相对路径。6.5.2文件目录类型多级目录树形结构在一个采用二级目录结构的文件系统中,用户在访问文件时,先后给出过两个文件名:\A\X和\B\X,这样的做法是()。不允许的A允许的,且这两次访问肯定是访问同一个文件B允许的,且这两次访问肯定是访问两个不同的文件C允许的,但不能肯定这两次访问的是同一个文件,还是两个不同的文件D提交单选题1分（2）多级目录特点适用于较大的文件系统管理；方便用户查找文件，将不同类型和不同用途的文件分类；允许文件重名；查找速度加快。3、多级目录目录查询速度对比假如有一个文件系统有1000个文件，系统中有10个用户，假定平均每个用户100个文件，问一级索引和二级索引平均查找时间复杂度为多少？3、多级目录可以解决文件重名问题的目录结构有_________。一级目录A二级目录B三级目录C多级目录D树形结构目录E提交多选题1分6.5.3便于共享的文件目录1、文件共享

多个用户可以访问同一个文件副本，而一个被共享的文件只需要在存储设备中只要保持一个副本即可。6.5.3便于共享的文件目录2、文件共享方法绕道法链接法基本文件(BFD)目录表2、文件共享方法（1）绕道法用户文件固有名：由用户当前目录到信息文件通路上所有各级目录的目录名加上该信息文件的符号名组成。2、文件共享方法（1）绕道法共享实现原理：用户从当前目录出发向上返回到与所要共享文件所在路径的交叉点，再顺序下放到共享文件；另外需要用户指定所要共享文件的逻辑位置。(1)绕道法2、文件共享方法(2)链接法链接（一处存储而多处出现）：指一个文件或目录在目录树中多处出现，但实际在外存介质上只有一份物理存储。2、文件共享方法(2)链接法（文件别名法）Unix下，建立链接的命令是ln。例如：

ln/usr/lib/mad/lib：

含义是：使/usr/lib下的mad文件在/usr/lib和/lib下都出现，但实际上mad文件在盘上只有一份物理存储。2、文件共享方法2、链接法（文件别名法）2、文件共享方法设文件F1的当前引用计数值为1,先建立F1的符号链接(软链接)文件F2,再建立F1的硬链接文件F3,然后删除F1。此时,F2和F3的引用计数值分别是()。0、1A1、1B1、2C2、1D提交单选题1分2、链接法（文件别名法）(3)基本文件目录表符号文件目录（SFD）：由文件名和文件内部标识组成的树状结构，按文件名排序；基本文件目录（BFD，索引节点目录）：由其余文件说明信息组成的线性结构，按文件内部标识排序；2文件共享方法采用基本文件目录和符号文件目录的多级目录结构(3)基本文件目录表1）预设目录基本文件目录（BFD）空白文件目录主目录（MFD)：内容主要是用户信息符号文件目录：每个用户都有一个2、文件共享方法(3)基本文件目录表

2）基于BFD和SFD多级目录文件打开步骤

把主目录MFD中的相应表目，也就是与待打开文件相关系的有关表目复制到内存；

根据①所复制得到的标识符，再复制此标识符所指明的基本文件目录表BFD的有关表目(SFD)；2、文件共享方法(3)基本文件目录表2）基于BFD和SFD多级目录文件打开步骤

根据②所得到的子目录说明信息搜索SFD，以找到与待打开相对应的目录表项；

根据③所搜索到的文件名所对应的内部标识符id，把相应的BFD的表目项复制到内存2、文件共享方法6.5.4目录管理1、目录存放位置全部存放在外存全部存放在内存部分在内存，部分在外存2、文件目录的打开和关闭文件目录打开（fopen）把文件存储设备上的目录文件复制到内存的操作文件目录关闭（fclose）删除文件的内存副本的操作6.5.4目录管理3、文件系统实现时的相关表目系统打开文件表：放在内存，用于保存已打开文件的FCB。用户打开文件表：每个进程一个，包括文件描述符、打开方式、读写指针、系统打开文件表入口；6.5.4目录管理3、文件系统实现时的相关表目6.6文件存取控制1.文件的访问控制2.文件的访问权限3.文件的并发访问相关概念：（1）文件共享:不同的用户共同使用一个文件（2）文件保护:防止文件内容被破坏（3）文件保密