第八章文件系统.ppt

第八章 文件系统,8.1 文件系统的概念 8.2 文件的逻辑结构和存取方法 8.3 文件的物理结构 8.4 文件存储空间的管理 8.5 文件目录管理 8.6 文件系统的可靠性和安全性 8.7 文件的使用 8.8 文件系统的性能问题,目录,8.1 文件系统的概念,操作系统的软硬件管理,文件系统必须完成下列工作,对磁盘等辅助存储器空间进行统一管理 为了实现按名存取，有一个用户可见的文件逻辑结构 为了便于存放和加工信息，文件在存储设备上应按一定的顺序存放文件的物理结构。 完成对存放在存储设备上的文件信息的查找。 完成文件的共享 提供保护,文件与文件系统概念,文件是一段程序或数据的集合。 文件被解释为一组赋名的相关联字符流的集合，或者是相关联记录( 一个有意义的信息单位 )的集合 无结构文件或流式文件：目前常用的操作系统，例如 unix，ms-dos等 记录式文件：记录是由 n (n 1) 个字节组成的具有特定意义的信息单位；记录式文件主要用于信息管理。,文件系统,操作系统中与管理文件有关的软件和数据 功能：为用户建立文件，撤消、读写、修改和复制文件，负责完成对文件的按名存取和进行存取控制。 特点： 友好的用户接口，用户只对文件进行操作，而不管文件结构和存放的物理位置。 对文件按名存取，对用户透明。 某些文件可以被多个用户或进程所共享。 文件系统大都使用磁盘、磁带和光盘等大容量存储器作为存储介质，因此，可存储大量信息。,1. 按文件性质和用途分类 系统文件：有关os及有关系统所组成文件 用户文件： 库文件：标准子程序及常用应用程 序组成文件，允许用户使用但不能修改 2. 按信息保存期限分类 临时文件；永久文件；档案文件 3. 按文件的保护方式分类 只读文件；读写文件；可执行文件 4. 按文件的逻辑结构分类 流式文件；记录式文件,文件的分类,5. 按文件的物理结构分类 顺序（连续）文件；链接文件；索引文件 6. unix系统将文件分为三类 普通文件：包含的是用户的信息，一般为ascii或二进制文件 目录文件：管理文件系统的系统文件 特殊文件：设备文件，把外部设备也看作文件 字符设备文件：和输入输出有关，用于模仿串行i/o设备，例如终端，打印机，网络等 块设备文件：模仿磁盘,文件的分类,文件系统模型,从用户角度看文件，研究文件的组织形式 分类：字符流式的无结构文件和记录式的有结构文件 选取文件的逻辑结构应遵循下述原则： 要求： 提高检索效率 便于修改 降低文件的存储费用 便于用户进行操作,8.2 文件的逻辑结构与存取方法,构成文件的基本单位是字符，文件是有逻辑意义的、无结构的一串字符的集合。 文件：一个无结构字节序列 好处：提供很大的灵活性,流式文件（无结构文件）,文件是由若干个记录组成，每个记录有一个键，可按键进行查找。 记录式文件：一个固定长度记录的序列，每条记录有其内部结构 定长记录式文件 变长记录式文件 常用的记录式文件结构有四种,记录文件（有结构文件）,记录组成例,连续结构,是一种把记录按照生成的先后顺序排列的逻辑结构。 特点： 适应性强，可用于所有文件； 顺序与内容无关，利于记录的追加与变更，搜索性能差,多重结构,行列式结构：把记录按键和记录名排列成行列式结构，则一个包含n个记录名，m(=n)个键的文件构成一个m*n维行列式。 1:说明该键在记录中，否则不在。 行列式结构浪费较多的存储空间 将行列式结构中0的项去掉，并以键为队首构成一个记录队列，这样的m个队列构成该文件的多重结构,图示,文件的记录名和关键字构成的行列式,图8.4文件的多重结构,图8.5文件的转置结构,转置结构,把含有相同键的记录指针全部指向该键，即，把所有与同一键对应的记录连续的放在目录中该键的位置下。 适合于给定键后的记录搜索,顺序结构,把文件中的键按规定的顺序排列起来就形成了顺序结构。 适合于系统按某种优先顺序来搜索或追加、删除记录,8.2.2 存取方法,顺序存取法 按照文件的逻辑顺序存取。在记录式文件中，按记录的排列顺序存取；在流式文件中，顺序存取反映了当前读写指针的变化。 随机存取法（直接存取法） 允许用户根据记录的编号来存取文件的任一记录，或者是根据存取命令把读写指针移到要读写处来进行读写。 按键存取法 在数据库管理系统中进行存取的方法，是根据给定的键或记录名进行的。首先搜索到记录的逻辑位置，再转变为相应的物理地址后进行存取。 包括：键的搜索和记录的搜索,如：unix、ms-dos等,如：unix、ms-dos等,记录ri的搜索过程,搜索算法,对键或记录的搜索与其他数据搜索问题一样，都属于表格搜索问题。 这些算法可以大致分为三种类型。 线性搜索法(linear search)， 散列法(hash coding)， 二分搜索法(binary search algorithm)。,二分搜索法的搜索过程,8.3 文件的物理结构与存储设备,8.3.1存储介质：磁盘，磁带，光盘 8.3.2 文件的物理结构,8.3.1存储介质：磁盘，磁带，光盘,1.物理块(块) 在文件系统中，文件的存储设备常常划分为若干大小相等的物理块。同时也将文件信息划分成相同大小的逻辑块（块），所有块统一编号。 以块为单位进行信息的存储、传输，分配,2.磁带,永久保存大容量数据 顺序存取设备： 前面的物理块被存取访问之后，才能存取后续的物理块的内容 存取速度较慢，主要用于后备存储，存储不经常用的信息，或用于传递数据的介质,直接（随机）存取设备： 存取磁盘上任一物理块的时间不依赖于该物理块所处的位置,3.磁盘,信息记录在磁道上，多个盘片，正反两面都用来记录信息，每面一个磁头 所有盘面中处于同一磁道号上的所有磁道组成一个柱面 物理地址形式： 磁头号（盘面号） 磁道号（柱面号） 扇区号 硬盘又分为两种： 固定头磁盘：每个磁道设置一个磁头，变换磁道时不需要磁头的机械移动，速度快但成本高 移动头磁盘：一个盘面只有一个磁头，变换磁道时需要移动磁头，速度慢但成本低,磁盘组成,磁盘系统由磁盘本身和驱动控制设备组成，实际存取读写的动作过程是由磁盘驱动控制设备按照主机要求完成的 一次访盘请求： 读/写，磁盘地址（设备号，柱面号，磁头号，扇区号），内存地址（源/目） 完成过程由三个动作组成： 寻道（时间）：磁头移动定位到指定磁道 旋转延迟（时间）：等待指定扇区从磁头下旋转经过 数据传输（时间）：数据在磁盘与内存之间的实际传输,磁盘读写,光盘容量大，速度快，价格便宜，但一般不可写 可读写光盘驱动器价格贵，写过程很麻烦 光盘的空间结构与磁盘类似,4.光盘,是从系统的角度来看文件，从文件在物理介质上的存放方式来研究文件 要考虑的主要问题： 1、怎样才能有效地利用外存空间 2、提高对文件的访问速度。,8.3.2 文件的物理结构,一个文件的信息存放在若干连续的物理块中 优点: 简单 支持顺序存取和随机存取 顺序存取速度快 所需的磁盘寻道次数和寻道时间最少,1. 连续文件,a 文件不能动态增长 预留空间:浪费 重新分配和移动 b 不利于文件插入和删除 c 外部碎片问题 d 要事先知道文件的长度,缺点,显式链接：一个文件的信息存放在若干不连续的物理块中，各块之间通过指针连接，前一个物理块指向下一个物理块 优点： 提高了磁盘空间利用率,不存在外部碎片问题 有利于文件插入和删除 有利于文件动态扩充,2. 链接文件,文件目录,缺点： 存取速度慢，不适于随机存取 可靠性问题，如指针出错 更多的寻道次数和寻道时间 链接指针占用一定的空间 隐式链接: 文件分配表fat,缺点与隐式链接,文件分配表,38,磁盘分区,39,fat表,40,the format of the traditional dos 8.3 is as follows:,41,fat16的目录项由32个字节构成，各个字节的含义如下： 00h07h文件名，其中00h的值为：00h空表项；e5h文件已删除；2eh 子目录。 08h0ah文件的扩展名。 0bh文件属性，其中b7b6未用；b5(20h)归档位；b4(10h)子目录；b3(08h)卷标(卷标也解释为一种特殊的文件)；b2(04h)系统文件；b1(02h)隐藏文件；b0(01h)只读文件，属性字节为00h为一般读写文件。 0ch15hfat16系统保留未用。 16h17h文件最后修改时间，其中：16h字节的04位是以2秒为增量的秒；16h字节的57位和17h字节的02位是分钟；17h字节的37位是小时。 18h19h文件最后修改日期，其中：18h字节04位是天号；18h字节57位和19h字节0位是月份；19h字节的17位为年号，0119分别代表19802099。 1ah1bh文件的起始簇号。 1ch1fh文件的长度(单位为字节)。,fat16的目录项,fat32长文件目录项32个字节的表示定义,一个文件的信息存放在若干不连续物理块中，系统为每个文件建立一个专用数据结构-索引表，并将这些块的块号存放在一个索引表中 一个索引表就是磁盘块地址数组,其中第i个条目指向文件的第i块,3.索引结构,优点： 保持了链接结构的优点,又解决了其缺点： 即能顺序存取,又能随机存取 满足了文件动态增长、插入删除的要求 能充分利用外存空间 缺点： 较多的寻道次数和寻道时间 索引表本身带来了系统开销 如：内外存空间，存取时间,索引结构优缺点,链接模式:一个盘块一个索引表,多个索引表链接起来 多级索引:将一个大文件的所有索引表（二级索引)的地址放在另一个索引表（一级索引)中 综合模式:,索引表组织,多重索引结构,unix的多级索引结构,文件结构、文件存取方式与文件存储介质的关系,8.4.1 文件组成 8.4.2 文件目录结构 8.4.3 便于共享的文件目录,8.4 文件目录,8.4.1 文件组成,1.文件控制块（fcb）： 文件控制块是操作系统为管理文件而设置的数据结构，存放了为管理文件所需的所有有关信息（文件属性） 文件控制块是文件存在的标志 文件控制块的内容： 文件名，文件号，用户名，文件地址，文件长度，文件类型，文件属性，共享计数，文件的建立日期，保存期限，最后修改日期，最后访问日期，口令，文件逻辑结构，文件物理结构 2.文件体：文件本身的信息,文件目录,文件目录：把所有的fcb组织在一起，就构成了文件目录，即文件控制块的有序集合 目录项：构成文件目录的项目（目录项就是fcb） 目录文件：为了实现对文件目录的管理，通常将文件目录以文件的形式保存在外存，这个文件就叫目录文件,1.一级目录结构 为所有文件建立一个目录文件(组成一线性表) 优点: 简单，易实现 缺点: 限制了用户对文件的命名 文件平均检索时间长 限制了对文件的共享,8.4.2 文件目录结构,单级目录的读写处理过程,2. 二级目录结构 为改变一级目录文件目录命名冲突，并提高对目录文件检索速度而改进 目录分为两级：一级称为主文件目录，给出用户名，用户子目录所在的物理位置；二级称为用户文件目录（又称用户子目录），给出该用户所有文件的fcb 优点：解决了文件的重名问题和文件共享问题 用户名|文件名 查找时间降低 缺点：增加了系统开销,2. 二级目录结构,二级目录结构,优点： 层次结构清晰，便于管理和保护；有利于文件分类；解决重名问题；提高文件检索速度；能进行存取权限的控制 缺点： 查找一个文件按路径名逐层检查，由于每个文件都放在外存，多次访盘影响速度,3. 多级目录结构（树型目录）,文件系统的树形结构,目录的其他实现方法,哈希表算法： 目录项信息存在一哈希表中 搜索时根据文件名计算哈希值 得到一个指向表中文件的指针 其他算法： 如b+树 ntfs文件系统就采用了b+树,8.4.3便于共享的文件目录,图8.18绕道法,采用基本文件目录的多级目录结构,链接法,链接法,例子：一个fcb有48个字节 符号目录项占 8字节 文件名6字节，文件号2字节 基本目录项占 48-6=42字节 假设，物理块大小512字节,解：分解前：占512/48=10个fcb 分解后：占512/8=64个符号目录项或512/42=12个基本目录项 假设：目录文件有128个目录项 分解前：占13块 分解后：符号文件占2块 基本文件占11块,查找一个文件的平均访盘次数 分解前：(1+13)/2=7次 分解后：(1+2)/2 +1 =2.5次 减少了访问硬盘的次数，提高了检索速度,（1）逻辑记录长度与物理块长相等 （2）逻辑记录长度为物理块长的整数因子 （3）逻辑记录长度不为物理块长的整数因子,记录的成组与分解,记录的成组：把若干个逻辑记录合成一组存放一块的工作 进行成组操作时必须使用主存缓冲区，缓冲区的长度等于逻辑记录长度乘以成组的块因子 记录的成组：提高了存储空间的利用率；减少了启动外设的次数，提高系统的工作效率 记录的分解：从一组逻辑记录中把一个逻辑记录分离出来的操作,a.根据记录号和记录长度，确定记录所在物理块的相对块号rb； b.由记录长确定记录所在的物理块块数n； c.计算记录在所占的首物理块内的位移量d1； d.计算记录所占的末物理块内的位移量d2，即记录在末块内占据的长度； e.根据物理块长bs及计算出来的d1和d2，判断记录是否跨块；若跨块则修改n值和d2值。 （允许跨块）,记录的成组与分解,8.5.1内存中所需的表目 1. 系统打开文件表（整个系统一张） 放在内存。用于保存已打开文件的fcb 此外，文件号，共享计数，修改标志 2. 用户打开文件表（每个进程一个） 文件描述符，打开方式，读写指针，系统打开文件表入口 进程的pcb中，记录了用户打开文件表的位置 3.用户打开文件表与系统打开文件表之间的关系 用户打开文件表指向系统打开文件表。 如果多个进程共享同一个文件，则多个用户打开文件表目对应系统打开文件表的同一入口,8.5 文件存储空间的管理,系统打开文件表,用户打开文件表,关系,1. 空闲文件目录 将所有空闲块记录在一个表中，即空闲块表，有两项 2. 空闲块链表 把所有空闲块链成一个链 扩展：成组链接法 3. 位示图,8.5.2 外存空间管理,成组链法的组织,空闲盘块的组织,空闲盘块号栈 所有空闲盘块分组 将每一组含有的盘块总数和该组所有的盘块号，记入其前一组的第一个盘块中。形成一条链。 将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块。 最末一组盘块中加一个结束标志“0”。,77,成组链接(空闲块号49236),78,分配一空闲块 查l单元的内容(空闲块数) 当空闲块数1 i=l+空闲块数(i为主存地址)； 从i单元得到一空闲块号； 将该块分配给申请者； 空闲块数减1。 当空闲块数=1 取出l+1单元的内容(一组中的第一块块号) 若其值=0，无空闲块，申请者等待； 若其值0，将该块中的内容复制到专用块， 并将该块分配给申请者； 把专用块内容读到主存l开始的区域。,分配算法,79,回收一空闲块 取l单元的内容(空闲块数) 当空闲块数50 空闲块数加1； j=l+空闲块数(j为主存地址)； 归还块号填入j单元。 当空闲块数=50 将主存中的信息写入归还块中； 将归还块号填入l+1单元； 将l单元置1。,回收算法,用一串二进制位反映磁盘空间中分配使用情况, 每个物理块对应一位, 分配物理块为1，否则为0 申请物理块时，可以在位示图中查找为0的位，返回对应物理块号； 归还时；将对应位转置0 描述能力强，适合各种物理结构,3. 位示图法,81,块号=字号*32+位号 字号=块号/32 位号=块号%32,位示图(共3200块),计算公式（续）,已知块号，则磁盘地址： 柱面号块号/（磁头数扇区数） 磁头号（块号mod （磁头数扇区数）/扇区数 扇区号（块号mod （磁头数扇区数）mod 扇区数 已知磁盘地址： 块号柱面号（磁头数扇区数）磁头号扇区数扇区号,8.6 文件系统的可靠性与安全性,人为因素存取控制权限 系统因素系统容错技术 自然因素备份技术,8.6.1文件的存取控制,文件的存取控制是和文件的共享、保护和保密三个不同而又相互联系的问题紧密相关的。 文件的共享是指不同的用户共同使用一个文件。 文件保护则指文件本身需要防止文件的拥有者本人或其他用户破坏文件内容。 文件保密指未经文件拥有者许可，任何用户不得访问该文件。 这三个问题实际上是一个用户对文件的使用权限，即读、写、执行的许可权问题。,文件系统的存取控制部分应做到,(1) 对于拥有读、写或执行权限的用户，应让其对文件进行相应的操作。 (2) 对于没有读、写或执行权限的用户，应禁止他们对文件进行相应的操作。 (3) 应防止一个用户冒充其他用户对文件进行存取。 (4) 应防止拥有存取权限的用户误用文件。,存取控制验证模块,这些功能是由一组称为存取控制验证模块的程序提供的。 它们分三步验证用户的存取操作。 (1) 审定用户的存取权限。 (2) 比较用户权限的本次存取要求是否一致。 (3) 将存取要求和被访问文件的保密性比较，看是否有冲突。,个方式来验证用户的存取操作,存取控制矩阵; 存取控制表; 口令; 密码。 系统设计人员根据需要选择其中一种或几种并将相应的数据结构置于文件说明(bfd等)中; 在用户访问存取文件时，对用户的存取权限、存取要求的一致性以及保密性等进行验证。,存取控制矩阵,存取控制表,口令,两种口令方式 当用户进入系统，为建立终端进程时获得系统使用权的口令。 每个用户在创建文件时，为每一个创建的文件设置一个口令，且将其置于文件说明中。,加密解密过程,8.6.2 系统容错技术,可靠性：系统抵抗和预防各种物理性破坏和人为性破坏的能力 1. 一级容错: 双份文件目录和文件分配表 磁盘热修复和写后读校验,2、二级容错技术,磁盘镜像 磁盘双工,3、三级容错技术,raid（廉价磁盘冗余阵列） raid的优点,1、通过把多个磁盘组织在一起，作为一个逻辑卷提供磁盘跨越功能 2、通过把数据分成多个数据块，并行写入/读出多个磁盘，以提高访问磁盘的速度 3、通过镜像或校验操作，提供容错能力,raid0 数据分条技术 整个逻辑盘的数据被分散分布在多个物理盘上，并行读写。（没有冗余能力） 至少两个盘 raid1 把一个磁盘的数据镜像到另一个磁盘上。（两个盘上实施，数据冗余50%） raid0+1 4个盘 raid3 3个盘（一个专为校验盘） raid5 无专门校验盘，校验数据分布在多个盘上 至少3个盘，（n-1）/n 一个磁盘故障时，控制器可从其他尚存的磁盘上重新恢复/生成丢失的数据而不影响数据的可用性,廉价磁盘冗余阵列,通过转储操作，形成文件或文件系统的多个副本 软盘，磁带（150m,8g exabyte,dat） 恢复,8.6.3 备份,海量转储：定期将所有文件拷贝到后援存储器 增量转储：只转储修改过的文件，即两次备份之间的修改，减少系统开销,类型,8.7 文件的使用,讨论文件系统对用户的接口。 文件系统以系统调用方式或命令方式为用户提供下列几类服务： (1) 关于设置和修改用户对文件的存取权限的服务; (2) 关于建立、改变和删除目录的服务; (3) 关于文件共享、设置访问路径的服务; (4) 创建、打开、读写、关闭，及撤消文件的服务。 这些服务的调用名和参数都因系统不同而异。 有关对文件操作的命令都基于操作系统提供的系统调用。这些系统调用包括建立文件用的 creat，读文件用的 read，关闭文件用的close以及撤消文件用的 delete 等。,7.8 文件系统的层次模型,练习,6. 文件系统的层次模型如下图所示。文件的目录采用基本文件目录表bfd的方法组织，其中含有文件wang/b.c的文件说明信息，wang为文件主的用户名。文件的物理结构为连续文件结构，并采用直接存取方式，每个文件的记录长度为500字节，每个物理块长为2000字节，即一个物理块可以存放4个记录。结合执行系统调用命令read(wangb.c，7，20000)（其中7为逻辑记录号，20000为内存地址），回答下列问题： (1) 第二层符号文件系统sfs的主要工作及其结果； (2) 第三层基本文件系统的主要工作； (3) 第五层逻辑文件系统得到的主要结果； (4) 第六层物理文件系统得到的主要结果。,如下图,解答：,(1) 主要功能：把用户提供的文件符号名wang/b.c转换为系统内部的唯一标识符6。call bfs（read, 6,7,20000）。 (2) 从bfd中找文件标识符6文件说明信息。 (3) 把逻辑块号转换为相对块号和块内相对地址。 逻辑字节串首址（lba）=记录号*记录长度=7*500=3500； 相对块号rbn=（lba / 物理块长pbl）的整数部分=（3500/2000）的整数=1； 块内相对地址pbo=lba mod pbl=3500 mod 2000=1500。 (4) 把相对块号和块内相对地址，根据文件的物理结构转换成物理地址。 如相对块号1的物理块号为11，块内相对地址为1500。,(1) 先来先服务：按访问请求到达的先后次序服务 优点：简单，公平； 缺点：效率不高，相临两次请求可能会造成最内到最外的柱面寻道，使磁头反复移动，增加了服务时间，对机械也不利,补充： 磁盘调度算法,假设磁盘访问序列：98，183，37，122，14，124，65，67 读写头起始位置：53 安排磁头服务序列 计算磁头移动总距离（道数）,举例,fcfs举例,(2) 最短寻道时间优先：优先选择距当前磁头最近的访问请求进行服务，主要考虑寻道优先 优点：改善了磁盘平均服务时间； 缺点