操作系统-第八章课件

操作系统第八章文件系统1操作系统第八章文件系统1第八章文件系统文件系统的概念文件的逻辑结构与存取方法文件的物理结构与存储设备文件存储空间管理文件目录管理2文件存取控制文件的使用文件系统的层次模型总结第八章文件系统文件系统的概念2文件存取控制文件系统的概念文件系统的引入文件与文件系统的概念文件的分类3文件系统的概念文件系统的引入3文件系统的概念文件系统的引入操作系统对计算机的管理：硬件资源管理：CPU、存储器和设备的管理；软件资源管理：系统程序、工具软件、库函数和用户程序与数据。4编辑程序、编译程序与链接程序等。文件系统的概念文件系统的引入4编辑程序、编译程序与链接程序文件系统的概念文件系统的引入目的：如何对软件资源（程序和数据）进行透明地快速存取？透明：对文件的操作与文件的物理结构和存取介质无关。对文件的操作只需要给定的一个代表程序和数据的名称->文件名5文件系统的概念文件系统的引入5文件系统的概念文件系统的引入文件系统需要完成的工作：必须对磁盘等存储空间进行统一管理，包括分配和回收。为用户提供一个可见的文件逻辑结构，独立于物理设备，以实现按名存取。实现文件的物理结构：在存储设备上按照一定顺序存放，方便存放和加工信息。完成对文件信息的查找。完成对文件的共享和保护。6文件系统的概念文件系统的引入6文件系统的概念文件与文件系统的概念文件：一组赋名的相关联字符流集合。无结构的流式文件。（源程序和目标代码）由相关联记录（一个有意义的信息单位）的集合。记录式文件。（数据库）记录：N（N>1）个字节组成的具有特定意义的信息单位。7文件系统的概念文件与文件系统的概念7文件系统的概念文件与文件系统的概念文件：设备与文件的统一管理的问题：从字符流的角度出发，设备可以看成是特殊的文件。简化了设备管理与文件系统的接口设计。文件名问题：由英文字母、数字和其他字符组成。区分英文字母大小写。首字母建议用字母，特殊字符建议用“_”替代。8文件系统的概念文件与文件系统的概念8文件系统的概念文件与文件系统的概念文件系统：操作系统中与管理文件有关的软件和数据。功能：为用户建立、撤销、读写、修改和复制文件，对文件按名存取，和存取控制。9文件系统的概念文件与文件系统的概念9文件系统的概念文件与文件系统的概念文件系统的特点：友好的用户接口，用户不必关心文件的物理位置。按文件名存取，用户不必关心文件的物理结构。某些文件可以被多个用户共享。文件系统的存储介质容量大，磁盘，光盘等。10文件系统的概念文件与文件系统的概念10文件系统的概念文件的分类按文件的性质和用途系统文件：由操作系统核心和系统程序、数据组成，用户只能通过系统调用执行它们。库文件：由各种标准子程序库组成，用户可以读取、执行，但不能修改。用户文件：由用户的各种程序和数据库组成，只能由文件的所有者或者所有者授权的用户使用。11文件系统的概念文件的分类11文件系统的概念文件的分类按文件的组织普通文件：组织格式为系统中规定的最一般格式的文件，例如字符流组成的文件。目录文件：由文件的目录信息构成的特殊文件，用于检索普通文件的。特殊文件：输入输出设备，与设备管理程序紧密相连。12文件系统的概念文件的分类12文件系统的概念文件的分类按信息的流向：输入文件、输出文件和输入输出文件。按保护级别：只读文件、读写文件、可执行文件和不保护文件。13文件系统的概念文件的分类13逻辑结构和存取方法逻辑结构文件的逻辑结构是用户可见的结构。逻辑结构设计的原则：最少的变动最短的时间最小的体积最便捷的操作14逻辑结构和存取方法逻辑结构14逻辑结构和存取方法逻辑结构字符流的无结构文件：管理简单，查找困难。适合于对基本信息单位操作不多的文件。记录式的有结构文件：方便用户对记录进行修改、追加、查找和管理等操作。15逻辑结构和存取方法逻辑结构15逻辑结构和存取方法逻辑结构记录：一个具有特定意义的信息单位组成：记录在文件中的逻辑地址与记录名对应的一组关键字、属性和属性值。常用的记录式结构文件：连续结构、多重结构、转置结构和顺序结构。16逻辑结构和存取方法逻辑结构16逻辑结构和存取方法逻辑结构连续结构把记录按生成的先后顺序排列的结构。特点：适用性强，适用于所有文件。记录的排列顺序与记录的内容无关，有利于记录的追加和变更。对关键字搜索时，需要遍历全体文件，搜索性能差。17逻辑结构和存取方法逻辑结构17逻辑结构和存取方法逻辑结构多重结构把记录按关键字和记录名排列成行列式的结构。特点：同一个关键字可以同时属于不同的记录。对关键字搜索速度快。18逻辑结构和存取方法逻辑结构18逻辑结构和存取方法逻辑结构多重结构优化空间：将行列式中0项去掉，改以多个队列存储。19逻辑结构和存取方法逻辑结构19逻辑结构和存取方法逻辑结构转置结构将每个关键字指向记录的指针保存在关键字的域中。特点：适合于根据关键字的记录搜索。20逻辑结构和存取方法逻辑结构20逻辑结构和存取方法逻辑结构顺序结构把文件中的关键字按规定的顺序排列起来。特点：适合按某种优先顺序来搜索或追加、删除记录。例子：《人民日报》新闻按登载日期的时间先后顺序组成文件，如果想要搜索某一时期的历史事件，只需要将时间范围缩小到那一时期即可。21逻辑结构和存取方法逻辑结构21逻辑结构和存取方法存取方法文件的存取：找到文件的内容所在的逻辑地址。用途：用户通过文件的存取来完成对文件的修改、追加和搜索等操作。三种方式：顺序存取法、随机存取法和按关键字存取法。22逻辑结构和存取方法存取方法22逻辑结构和存取方法存取方法顺序存取法按照文件的逻辑地址顺序存取。记录式文件：按记录的排列顺序来存取，当前记录Ri，下一次读取为相邻记录Ri+1。字符流文件：存取指针顺序增长变化，当前指向P，下一次读取指向P+len，len为当前读取字符串长度。23逻辑结构和存取方法存取方法23逻辑结构和存取方法存取方法随机存取法根据记录的编号来存取文件的任意一个记录。根据存取命令自如地移动读写指针。24逻辑结构和存取方法存取方法24逻辑结构和存取方法存取方法按关键字存取文件的存取根据给定的关键字或记录名进行的。做法：搜索要进行存取的记录的逻辑位置；将逻辑位置转换到相应的物理地址，然后进行存取。适用于复杂的文件系统（数据库管理系统）25逻辑结构和存取方法存取方法25逻辑结构和存取方法存取方法按关键字存取搜索的过程：搜索算法：线性搜索法散列法二分搜索法26逻辑结构和存取方法存取方法26逻辑结构和存取方法存取方法按关键字存取线性搜索法：从头开始顺序查找时间复杂度：O(N)27逻辑结构和存取方法存取方法27逻辑结构和存取方法存取方法按关键字存取散列法：定义一个散列函数h(k)，使得对于给定的关键字k，散列函数都能将k变换得到其逻辑地址。散列冲突：对于k1!=k2，有h(k1)=h(k2)=A。两个关键字的散列变换冲突。时间复杂度：O(1)28逻辑结构和存取方法存取方法28逻辑结构和存取方法存取方法按关键字存取散列冲突的解决方法开放地址法：当h(k1)产生的值h1冲突，再计算一个值h2,如果h2冲突，再计算一个直到不冲突为止hihi=(h(k1)+di)%tt为搜索长度di=a*i或c*(i*i)或随机数。线性散列/平方散列/随机散列29逻辑结构和存取方法存取方法29逻辑结构和存取方法存取方法按关键字存取二分搜索法典型的二分查找时间复杂度：O(logN)条件：已排序的对象序列。30逻辑结构和存取方法存取方法30物理结构和存储设备文件的存取在搜索到目标记录的逻辑地址后要确定物理地址。逻辑地址到物理地址的映射和文件的物理结构紧密相连。文件系统的存取方法和逻辑结构也与物理存储介质有关。文件的物理结构和文件的存储设备。31物理结构和存储设备31物理结构和存储设备文件的物理结构文件的物理结构是指文件在存储设备上的存放方法。文件信息的逻辑地址到物理地址的变换是有文件的物理结构决定的。文件的存储设备通常划分为大小相等的若干物理块。常用的文件物理结构包括：连续文件、串联文件和索引文件。32物理结构和存储设备文件的物理结构32物理结构和存储设备文件的物理结构连续文件逻辑上连续的文件信息依次存放到物理块中。33物理结构和存储设备文件的物理结构33物理结构和存储设备文件的物理结构连续文件优点：地址变换简单，知道了起址和长度就能很快进行物理存取。缺点：文件建立时确定了文件长度，不能动态增长；删除后容易留下无法使用的零头空间。34物理结构和存储设备文件的物理结构34物理结构和存储设备文件的物理结构串联文件

用非连续的物理块存放文件信息，每个物理块设有指向后继物理块的指针。35物理结构和存储设备文件的物理结构35物理结构和存储设备文件的物理结构串联文件特点：建立文件时不需要指明长度，只需第一个块号。可以动态增长，增删、插入操作容易实现。搜索效率低，链表式搜索需要遍历整个链。36物理结构和存储设备文件的物理结构36物理结构和存储设备文件的物理结构索引文件系统为每个文件建立一张索引表，表中记录逻辑块和物理块的对应。37物理结构和存储设备文件的物理结构37物理结构和存储设备文件的物理结构索引文件当一个索引表大于一个物理块，如何存放？多重索引。38物理结构和存储设备文件的物理结构38物理结构和存储设备文件的物理结构索引文件索引结构的特点：适合顺序存取也适合随机存取。增加了索引表增加了存储空间开销。每次读取文件需要访问磁盘两次。（可以将索引表放入内存）39物理结构和存储设备文件的物理结构39物理结构和存储设备文件存储设备顺序存取存储设备——磁带直接存取存储设备——磁盘磁盘设备允许文件系统直接存取磁盘上的任意物理块。40物理结构和存储设备文件存储设备40物理结构和存储设备文件存储设备磁盘硬盘结构包括：盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部份。所有的盘片（一般硬盘里有多个盘片，盘片之间平行）都固定在一个主轴上。在每个盘片的存储面上都有一个磁头，磁头与盘片之间的距离很小（所以剧烈震动容易损坏），磁头连在一个磁头控制器上，统一控制各个磁头的运动。磁头沿盘片的半径方向动作，而盘片则按照指定方向高速旋转，这样磁头就可以到达盘片上的任意位置了。41物理结构和存储设备文件存储设备41物理结构和存储设备文件存储设备磁盘42物理结构和存储设备文件存储设备42物理结构和存储设备文件存储设备磁盘的容量：磁头数×磁道(柱面)数×每道扇区数×每扇区字节数磁头（head）数：每个盘片一般有上下两面，分别对应1个磁头，共2个磁头；磁道（track）数：磁道是从盘片外圈往内圈编号0磁道，1磁道...，靠近主轴的同心圆用于停靠磁头，不存储数据；柱面（cylinder）数：同磁道数量；扇区（sector）数：每个磁道都别切分成很多扇形区域，每道的扇区数量相同；圆盘（platter）数：就是盘片的数量。 43物理结构和存储设备文件存储设备43物理结构和存储设备文件存储设备44物理结构和存储设备文件存储设备44物理结构和存储设备文件存储设备磁盘的数据定位：LBA(逻辑扇区号)=磁头数×每磁道扇区数×当前所在柱面号+每磁道扇区数×当前所在磁头号+当前所在扇区号–1例如：CHS=0/0/1，则根据公式LBA=255×63×0+63×0+1–1=0物理0柱面0磁头1扇区，是逻辑0扇区45物理结构和存储设备文件存储设备45文件存储空间管理文件的存储设备以大小相等的物理块为单位。文件存储空间的管理实质是空闲块的组织和管理问题。有3种不同的空闲块管理方法：空闲文件目录、空闲块链和位示图。46文件存储空间管理46文件存储空间管理空闲文件目录文件存储设备中的空闲块的块号统一放在一个空闲文件目录的物理块中。每个表项存储一个空闲区，一个空闲区包括一个或多个空闲块。空闲文件目录管理的空闲区的申请和释放类似于内存空闲区的管理。47文件存储空间管理空闲文件目录47文件存储空间管理空闲块链空闲块链把文件存储设备上的所有空闲块链接在一起。申请空间时，从链表头部摘取所需要的空闲块，然后调整头指针。释放空间时，新的空闲块插入链尾上。空闲块的链接方式：按空闲区大小顺序链接、按释放先后顺序链接和成组链接。48文件存储空间管理空闲块链48文件存储空间管理空闲块链成组链接法前两种方式在增加或移动空闲块时需要对空闲块链做较大的调整，系统开销大。基本原理：所有空闲块50块一组，组的划分从后向前，每组的第一块用来存放前一组的各块的块号和总块数。49文件存储空间管理空闲块链49文件存储空间管理空闲块链成组链接法第一组前面没有其他组，所以第一组为49块；最后一组的块数可能不到50块，因为总的块数可能不是50的倍数。最后一组的各块号和总块数存放在文件资源表中。50文件存储空间管理空闲块链50文件存储空间管理空闲块链成组链接法分配和释放过程51文件存储空间管理空闲块链51文件存储空间管理位示图从系统内存中划分若干个字节，为每个文件存储设备建立一张位示图，反映各设备的使用情况。位示图中的每个比特位对应一个物理块的分配情况，0表示未分配，1表示已分配。位示图法分配与回收时不需要再文件存储设备上查找文件目录或链接块号，即不需要启动外设即可完成，因此速度快。52文件存储空间管理位示图52文件目录管理文件名及其结构信息需要按一定的组织结构排列，以方便搜索查找。文件目录管理：存储空间有效利用、快速搜索、解决文件命名冲突以及文件共享。文件的组成文件目录的介绍便于共享的文件目录目录管理53文件目录管理文件名及其结构信息需要按一定的组织结构排列，以文件目录管理文件的组成文件说明和文件体文件体：文件本身的信息文件说明：文件控制块（FCB）文件名、与文件名相对应的文件内部表示以及在文件存储设备上的第一个物理块地址。文件说明组成文件目录54文件目录管理文件的组成54文件目录管理文件目录文件目录：单级目录、二级目录和多级目录单级目录：文件系统为所有文件建立一张目录表，每个文件占用一个表项。目录表存放在存储设备的固定区域，系统启动后调入内存。文件系统通过该表完成对文件的创建、搜索和删除等操作。55文件目录管理文件目录55文件目录管理文件目录单级目录的读写处理过程56文件目录管理文件目录56文件目录管理文件目录单级目录的问题：命名冲突问题：单表目录中只能按连续结构或顺序结构存放，文件名与文件一一对应，相同文件名被视为同一文件。搜索速度问题：单表目录每次搜索需要对所有文件遍历，因此速度慢。57文件目录管理文件目录57文件目录管理文件目录二级目录各个文件的说明信息被组织成目录文件，且以用户为单位化为不同的组。MFD主目录：不同组名的存取控制信息存放的目录。UFD用户文件目录：用户文件说明所组成。58文件目录管理文件目录58文件目录管理文件目录二级目录59文件目录管理文件目录59文件目录管理文件目录二级目录同名冲突问题：可以轻易解决，因为同名不同组。文件共享问题：可以通过将共享的文件设置相应的共享指针。查找速度：n个文件划分成m个子集，r为每个用户子集的文件数，则n<=m*r(存在共享文件）。查找速度有n变为m+r，一般m+r<=n，因此查找速度>单级目录。60文件目录管理文件目录60文件目录管理文件目录多级目录：二级目录层次关系的推广61文件目录管理文件目录61文件目录管理文件目录多级目录特点：层次清楚，便于管理。解决了文件的重名冲突问题。查找速度块。62文件目录管理文件目录62文件目录管理便于共享的文件目录共享文件的必要性：节约存储空间。实现文件共享的3种方法：绕道法链接法基本文件目录表（BFD）63文件目录管理便于共享的文件目录63文件目录管理便于共享的文件目录绕道法根据文件的固有名，从当前目录出发向上返回到与共享文件所在路径的交叉点，再顺序下访。固有名：目录名+文件名绕道法需要绕弯路访问多级目录，搜索效率不高。64文件目录管理便于共享的文件目录64文件目录管理便于共享的文件目录链接法在相应目录表之间进行链接，一个目录中的链指针指向被共享文件所在目录。65文件目录管理便于共享的文件目录65文件目录管理便于共享的文件目录基本文件目录表66文件目录管理便于共享的文件目录66文件目录管理目录管理BFD,MFD,SFD等构成了目录文件。目录文件的存放位置？外存文件存储设备中：每次访问文件需要多次读写外部文件存储设备，耗时严重。内存中：系统启动时读入内存，将消耗较大内存。折中的办法：把当前正在使用的目录表copy到内存中。67文件目录管理目录管理67文件目录管理目录管理将当前使用的文件目录表copy到内存需要完成：把有关的目录文件复制到内存指定区域（打开文件fopen）用户不再访问时，删除有关文件的目录文件（关闭文件fclose）fopen，fclose以系统调用的方式提供。68文件目录管理目录管理68文件目录管理目录管理打开文件的步骤：1.把主目录MFD中相应的表项copy到内存；2.根据1得到的标识符对应的BDF的表项复制到内存；3.搜索2提供的SFD，知道找到文件名对应的标识符ID；4.根据3得到的标识符查找BDF，把相应的表项复制到内存。69文件目录管理目录管理69文件存取控制

文件的存取控制：一个用户对文件的使用权限，即读、写、执行的许可权问题。对拥有读、写、执行权限的用户，允许对文件进行相应操作。对没有读、写、执行权限的用户，禁止对文件进行相应操作。防止一个用户冒充其他用户对文件进行存取。防止拥有存取权限的用户误用文件。70文件存取控制文件的存取控制：70文件存取控制

文件的存取控制的步骤：审定用户的存取权限；比较用户权限与用户的本次存取要求是否一致；将存取要求和被访问的文件的保密性比较，查看是否有冲突。验证用户存取操作的4中方式：存取控制矩阵、存取控制表、口令和密码术。71文件存取控制文件的存取控制的步骤：71文件存取控制

存取控制矩阵二维矩阵：一维用户，一维文件，每个矩阵元素为相应的权限。特点：占用空间大，查找速度慢。72文件名

用户WangLeeZhangA.CRWEERWEB.CRWRRWED.CRWWEE.CRWRW文件存取控制存取控制矩阵72文件名文件存取控制

存取控制表每个文件都有一张存取控制表，按权限将用户分组。文件打开时，存取控制表copy到内存中，以保证高效验证。73用户组

文件A.CZhangRWEA组RWB组REWangR文件存取控制存取控制表73用户组文件存取控制

口令方式为每一个文件设置一个口令，访问文件时先验证口令。口令存在文件说明中；共享的实现通过分享口令；口令的占用空间小，验证耗时短；口令的保密性弱，修改权限不便。74文件存取控制口令方式74文件存取控制

密码方式密码方式与口令方式的不同：编解码的代码键并没有存放在系统中，而是由用户掌握。密码方式的特点：保密性高，编解码耗时。75文件存取控制密码方式75文件的使用文件系统提供的几种系统调用关于设置和用户对文件的存取权限的服务；关于建立、改变和删除目录的服务；关于文件共享、设置访问路径的服务；创建、打开、读写、关闭以及撤销文件的服务。chmod、mkdir、cd、rmdir、create、open、write、close等76文件的使用文件系统提供的几种系统调用76文件系统的层次模型定义：层次结构按照系统提供的功能划分各种不同的层次，下层为上层提供服务，上层使用下层的功能。特点：上下层无需了解对方的内部结构和实现方法，只需要关心接口。系统出错时，容易查错和调整。77文件系统的层次模型定义：77文件系统的层次模型Madnick的8层文件系统78文件系统的层次模型Madnick的8层文件系统78总结与作业总结：文件和文件系统的基本概念文件的逻辑结构和物理结构存储空间的管理方法文件目录（文件名与物理地址之间的映射）作业：8.1479总结与作业总结：79操作系统第八章文件系统80操作系统第八章文件系统1第八章文件系统文件系统的概念文件的逻辑结构与存取方法文件的物理结构与存储设备文件存储空间管理文件目录管理81文件存取控制文件的使用文件系统的层次模型总结第八章文件系统文件系统的概念2文件存取控制文件系统的概念文件系统的引入文件与文件系统的概念文件的分类82文件系统的概念文件系统的引入3文件系统的概念文件系统的引入操作系统对计算机的管理：硬件资源管理：CPU、存储器和设备的管理；软件资源管理：系统程序、工具软件、库函数和用户程序与数据。83编辑程序、编译程序与链接程序等。文件系统的概念文件系统的引入4编辑程序、编译程序与链接程序文件系统的概念文件系统的引入目的：如何对软件资源（程序和数据）进行透明地快速存取？透明：对文件的操作与文件的物理结构和存取介质无关。对文件的操作只需要给定的一个代表程序和数据的名称->文件名84文件系统的概念文件系统的引入5文件系统的概念文件系统的引入文件系统需要完成的工作：必须对磁盘等存储空间进行统一管理，包括分配和回收。为用户提供一个可见的文件逻辑结构，独立于物理设备，以实现按名存取。实现文件的物理结构：在存储设备上按照一定顺序存放，方便存放和加工信息。完成对文件信息的查找。完成对文件的共享和保护。85文件系统的概念文件系统的引入6文件系统的概念文件与文件系统的概念文件：一组赋名的相关联字符流集合。无结构的流式文件。（源程序和目标代码）由相关联记录（一个有意义的信息单位）的集合。记录式文件。（数据库）记录：N（N>1）个字节组成的具有特定意义的信息单位。86文件系统的概念文件与文件系统的概念7文件系统的概念文件与文件系统的概念文件：设备与文件的统一管理的问题：从字符流的角度出发，设备可以看成是特殊的文件。简化了设备管理与文件系统的接口设计。文件名问题：由英文字母、数字和其他字符组成。区分英文字母大小写。首字母建议用字母，特殊字符建议用“_”替代。87文件系统的概念文件与文件系统的概念8文件系统的概念文件与文件系统的概念文件系统：操作系统中与管理文件有关的软件和数据。功能：为用户建立、撤销、读写、修改和复制文件，对文件按名存取，和存取控制。88文件系统的概念文件与文件系统的概念9文件系统的概念文件与文件系统的概念文件系统的特点：友好的用户接口，用户不必关心文件的物理位置。按文件名存取，用户不必关心文件的物理结构。某些文件可以被多个用户共享。文件系统的存储介质容量大，磁盘，光盘等。89文件系统的概念文件与文件系统的概念10文件系统的概念文件的分类按文件的性质和用途系统文件：由操作系统核心和系统程序、数据组成，用户只能通过系统调用执行它们。库文件：由各种标准子程序库组成，用户可以读取、执行，但不能修改。用户文件：由用户的各种程序和数据库组成，只能由文件的所有者或者所有者授权的用户使用。90文件系统的概念文件的分类11文件系统的概念文件的分类按文件的组织普通文件：组织格式为系统中规定的最一般格式的文件，例如字符流组成的文件。目录文件：由文件的目录信息构成的特殊文件，用于检索普通文件的。特殊文件：输入输出设备，与设备管理程序紧密相连。91文件系统的概念文件的分类12文件系统的概念文件的分类按信息的流向：输入文件、输出文件和输入输出文件。按保护级别：只读文件、读写文件、可执行文件和不保护文件。92文件系统的概念文件的分类13逻辑结构和存取方法逻辑结构文件的逻辑结构是用户可见的结构。逻辑结构设计的原则：最少的变动最短的时间最小的体积最便捷的操作93逻辑结构和存取方法逻辑结构14逻辑结构和存取方法逻辑结构字符流的无结构文件：管理简单，查找困难。适合于对基本信息单位操作不多的文件。记录式的有结构文件：方便用户对记录进行修改、追加、查找和管理等操作。94逻辑结构和存取方法逻辑结构15逻辑结构和存取方法逻辑结构记录：一个具有特定意义的信息单位组成：记录在文件中的逻辑地址与记录名对应的一组关键字、属性和属性值。常用的记录式结构文件：连续结构、多重结构、转置结构和顺序结构。95逻辑结构和存取方法逻辑结构16逻辑结构和存取方法逻辑结构连续结构把记录按生成的先后顺序排列的结构。特点：适用性强，适用于所有文件。记录的排列顺序与记录的内容无关，有利于记录的追加和变更。对关键字搜索时，需要遍历全体文件，搜索性能差。96逻辑结构和存取方法逻辑结构17逻辑结构和存取方法逻辑结构多重结构把记录按关键字和记录名排列成行列式的结构。特点：同一个关键字可以同时属于不同的记录。对关键字搜索速度快。97逻辑结构和存取方法逻辑结构18逻辑结构和存取方法逻辑结构多重结构优化空间：将行列式中0项去掉，改以多个队列存储。98逻辑结构和存取方法逻辑结构19逻辑结构和存取方法逻辑结构转置结构将每个关键字指向记录的指针保存在关键字的域中。特点：适合于根据关键字的记录搜索。99逻辑结构和存取方法逻辑结构20逻辑结构和存取方法逻辑结构顺序结构把文件中的关键字按规定的顺序排列起来。特点：适合按某种优先顺序来搜索或追加、删除记录。例子：《人民日报》新闻按登载日期的时间先后顺序组成文件，如果想要搜索某一时期的历史事件，只需要将时间范围缩小到那一时期即可。100逻辑结构和存取方法逻辑结构21逻辑结构和存取方法存取方法文件的存取：找到文件的内容所在的逻辑地址。用途：用户通过文件的存取来完成对文件的修改、追加和搜索等操作。三种方式：顺序存取法、随机存取法和按关键字存取法。101逻辑结构和存取方法存取方法22逻辑结构和存取方法存取方法顺序存取法按照文件的逻辑地址顺序存取。记录式文件：按记录的排列顺序来存取，当前记录Ri，下一次读取为相邻记录Ri+1。字符流文件：存取指针顺序增长变化，当前指向P，下一次读取指向P+len，len为当前读取字符串长度。102逻辑结构和存取方法存取方法23逻辑结构和存取方法存取方法随机存取法根据记录的编号来存取文件的任意一个记录。根据存取命令自如地移动读写指针。103逻辑结构和存取方法存取方法24逻辑结构和存取方法存取方法按关键字存取文件的存取根据给定的关键字或记录名进行的。做法：搜索要进行存取的记录的逻辑位置；将逻辑位置转换到相应的物理地址，然后进行存取。适用于复杂的文件系统（数据库管理系统）104逻辑结构和存取方法存取方法25逻辑结构和存取方法存取方法按关键字存取搜索的过程：搜索算法：线性搜索法散列法二分搜索法105逻辑结构和存取方法存取方法26逻辑结构和存取方法存取方法按关键字存取线性搜索法：从头开始顺序查找时间复杂度：O(N)106逻辑结构和存取方法存取方法27逻辑结构和存取方法存取方法按关键字存取散列法：定义一个散列函数h(k)，使得对于给定的关键字k，散列函数都能将k变换得到其逻辑地址。散列冲突：对于k1!=k2，有h(k1)=h(k2)=A。两个关键字的散列变换冲突。时间复杂度：O(1)107逻辑结构和存取方法存取方法28逻辑结构和存取方法存取方法按关键字存取散列冲突的解决方法开放地址法：当h(k1)产生的值h1冲突，再计算一个值h2,如果h2冲突，再计算一个直到不冲突为止hihi=(h(k1)+di)%tt为搜索长度di=a*i或c*(i*i)或随机数。线性散列/平方散列/随机散列108逻辑结构和存取方法存取方法29逻辑结构和存取方法存取方法按关键字存取二分搜索法典型的二分查找时间复杂度：O(logN)条件：已排序的对象序列。109逻辑结构和存取方法存取方法30物理结构和存储设备文件的存取在搜索到目标记录的逻辑地址后要确定物理地址。逻辑地址到物理地址的映射和文件的物理结构紧密相连。文件系统的存取方法和逻辑结构也与物理存储介质有关。文件的物理结构和文件的存储设备。110物理结构和存储设备31物理结构和存储设备文件的物理结构文件的物理结构是指文件在存储设备上的存放方法。文件信息的逻辑地址到物理地址的变换是有文件的物理结构决定的。文件的存储设备通常划分为大小相等的若干物理块。常用的文件物理结构包括：连续文件、串联文件和索引文件。111物理结构和存储设备文件的物理结构32物理结构和存储设备文件的物理结构连续文件逻辑上连续的文件信息依次存放到物理块中。112物理结构和存储设备文件的物理结构33物理结构和存储设备文件的物理结构连续文件优点：地址变换简单，知道了起址和长度就能很快进行物理存取。缺点：文件建立时确定了文件长度，不能动态增长；删除后容易留下无法使用的零头空间。113物理结构和存储设备文件的物理结构34物理结构和存储设备文件的物理结构串联文件

用非连续的物理块存放文件信息，每个物理块设有指向后继物理块的指针。114物理结构和存储设备文件的物理结构35物理结构和存储设备文件的物理结构串联文件特点：建立文件时不需要指明长度，只需第一个块号。可以动态增长，增删、插入操作容易实现。搜索效率低，链表式搜索需要遍历整个链。115物理结构和存储设备文件的物理结构36物理结构和存储设备文件的物理结构索引文件系统为每个文件建立一张索引表，表中记录逻辑块和物理块的对应。116物理结构和存储设备文件的物理结构37物理结构和存储设备文件的物理结构索引文件当一个索引表大于一个物理块，如何存放？多重索引。117物理结构和存储设备文件的物理结构38物理结构和存储设备文件的物理结构索引文件索引结构的特点：适合顺序存取也适合随机存取。增加了索引表增加了存储空间开销。每次读取文件需要访问磁盘两次。（可以将索引表放入内存）118物理结构和存储设备文件的物理结构39物理结构和存储设备文件存储设备顺序存取存储设备——磁带直接存取存储设备——磁盘磁盘设备允许文件系统直接存取磁盘上的任意物理块。119物理结构和存储设备文件存储设备40物理结构和存储设备文件存储设备磁盘硬盘结构包括：盘片、磁头、盘片主轴、控制电机、磁头控制器、数据转换器、接口、缓存等几个部份。所有的盘片（一般硬盘里有多个盘片，盘片之间平行）都固定在一个主轴上。在每个盘片的存储面上都有一个磁头，磁头与盘片之间的距离很小（所以剧烈震动容易损坏），磁头连在一个磁头控制器上，统一控制各个磁头的运动。磁头沿盘片的半径方向动作，而盘片则按照指定方向高速旋转，这样磁头就可以到达盘片上的任意位置了。120物理结构和存储设备文件存储设备41物理结构和存储设备文件存储设备磁盘121物理结构和存储设备文件存储设备42物理结构和存储设备文件存储设备磁盘的容量：磁头数×磁道(柱面)数×每道扇区数×每扇区字节数磁头（head）数：每个盘片一般有上下两面，分别对应1个磁头，共2个磁头；磁道（track）数：磁道是从盘片外圈往内圈编号0磁道，1磁道...，靠近主轴的同心圆用于停靠磁头，不存储数据；柱面（cylinder）数：同磁道数量；扇区（sector）数：每个磁道都别切分成很多扇形区域，每道的扇区数量相同；圆盘（platter）数：就是盘片的数量。 122物理结构和存储设备文件存储设备43物理结构和存储设备文件存储设备123物理结构和存储设备文件存储设备44物理结构和存储设备文件存储设备磁盘的数据定位：LBA(逻辑扇区号)=磁头数×每磁道扇区数×当前所在柱面号+每磁道扇区数×当前所在磁头号+当前所在扇区号–1例如：CHS=0/0/1，则根据公式LBA=255×63×0+63×0+1–1=0物理0柱面0磁头1扇区，是逻辑0扇区124物理结构和存储设备文件存储设备45文件存储空间管理文件的存储设备以大小相等的物理块为单位。文件存储空间的管理实质是空闲块的组织和管理问题。有3种不同的空闲块管理方法：空闲文件目录、空闲块链和位示图。125文件存储空间管理46文件存储空间管理空闲文件目录文件存储设备中的空闲块的块号统一放在一个空闲文件目录的物理块中。每个表项存储一个空闲区，一个空闲区包括一个或多个空闲块。空闲文件目录管理的空闲区的申请和释放类似于内存空闲区的管理。126文件存储空间管理空闲文件目录47文件存储空间管理空闲块链空闲块链把文件存储设备上的所有空闲块链接在一起。申请空间时，从链表头部摘取所需要的空闲块，然后调整头指针。释放空间时，新的空闲块插入链尾上。空闲块的链接方式：按空闲区大小顺序链接、按释放先后顺序链接和成组链接。127文件存储空间管理空闲块链48文件存储空间管理空闲块链成组链接法前两种方式在增加或移动空闲块时需要对空闲块链做较大的调整，系统开销大。基本原理：所有空闲块50块一组，组的划分从后向前，每组的第一块用来存放前一组的各块的块号和总块数。128文件存储空间管理空闲块链49文件存储空间管理空闲块链成组链接法第一组前面没有其他组，所以第一组为49块；最后一组的块数可能不到50块，因为总的块数可能不是50的倍数。最后一组的各块号和总块数存放在文件资源表中。129文件存储空间管理空闲块链50文件存储空间管理空闲块链成组链接法分配和释放过程130文件存储空间管理空闲块链51文件存储空间管理位示图从系统内存中划分若干个字节，为每个文件存储设备建立一张位示图，反映各设备的使用情况。位示图中的每个比特位对应一个物理块的分配情况，0表示未分配，1表示已分配。位示图法分配与回收时不需要再文件存储设备上查找文件目录或链接块号，即不需要启动外设即可完成，因此速度快。131文件存储空间管理位示图52文件目录管理文件名及其结构信息需要按一定的组织结构排列，以方便搜索查找。文件目录管理：存储空间有效利用、快速搜索、解决文件命名冲突以及文件共享。文件的组成文件目录的介绍便于共享的文件目录目录管理132文件目录管理文件名及其结构信息需要按一定的组织结构排列，以文件目录管理文件的组成文件说明和文件体文件体：文件本身的信息文件说明：文件控制块（FCB）文件名、与文件名相对应的文件内部表示以及在文件存储设备上的第一个物理块地址。文件说明组成文件目录133文件目录管理文件的组成54文件目录管理文件目录文件目录：单级目录、二级目录和多级目录单级目录：文件系统为所有文件建立一张目录表，每个文件占用一个表项。目录表存放在存储设备的固定区域，系统启动后调入内存。文件系统通过该表完成对文件的创建、搜索和删除等操作。134文件目录管理文件目录55文件目录管理文件目录单级目录的读写处理过程135文件目录管理文件目录56文件目录管理文件目录单级目录的问题：命名冲突问题：单表目录中只能按连续结构或顺序结构存放，文件名与文件一一对应，相同文件名被视为同一文件。搜索速度问题：单表目录每次搜索需要对所有文件遍历，因此速度慢。136文件目录管理文件目录57文件目录管理文件目录二级目录各个文件的说明信息被组织成目录文件，且以用户为单位化为不同的组。MFD主目录：不同组名的存取控制信息存放的目录。UFD用户文件目录：用户文件说明所组成。137文件目录管理文件目录58文件目录管理文件目录二级目录138文件目录管理文件目录59文件目录管理文件目录二级目录同名冲突问题：可以轻易解决，因为同名不同组。文件共享问题：可以通过将共享的文件设置相应的共享指针。查找速度：n个文件划分成m个子集，r为每个用户子集的文件数，则n<=m*r(存在共享文件）。查找速度有n变为m+r，一般m+r<=n，因此查找速度>单级目录。139文件目录管理文件目录60文件目录管理文件目录多级目录：二级目录层次关系的推广140文件目录管理文件目录61文件目录管理文件目录多级目录特点：层次清楚，便于管理。解决了文件的重名冲突问题。查找速度块。141文件目录管理文件目录62文件目录管理便于共享的文件目录共享文件的必要性：节约存储空间。实现文件共享的3种方法：绕道法链接法基本文件目录表（BFD）142文件目录管理便于共享的文件目录63文件目录管理便于共享的文件目录绕道法根据文件的固有名，从当前目录出发向上返回到与共享文件所在路径的交叉点，再顺序下访。固有名：目录名+文件名绕道法需要绕弯路访问多级目录，搜索效率不高。143文件目录管理便于共享的文件目录64文件目录管理便于共享的文件目录链接法在相应目录表之间进行链接，一个目录中的链指针指向被共享文件所