《数据结构域算法设计chap6(49-50)》由会员分享,可在线阅读,更多相关《数据结构域算法设计chap6(49-50)(34页珍藏版)》请在金锄头文库上搜索。
1、复习:外存分配方式p连续分配方式:文件分到一组连续的盘块。 盘块组织方式:在目录中记录文件名、起始 盘块号、长度(总盘块数) 特点:目录项中的起始盘块号+逻辑盘块号就 是某逻辑地址数据所在的物理盘块号。因此,读 取某逻辑地址中的数据只需要启动1次盘块。 优点:可实现随机访问。 缺点:需要连续的盘块外存空间利用率低 、文件扩充困难。复习:外存分配方式p链接方式:文件分到一组离散的盘块。 显式链接盘块组织方式: 在目录中记录:文件名、起始盘块号 、结束盘块号。 其它盘块号存放在上一个盘块的地址 域中。特点:只能从起始盘块开始顺序访问。因此 ,读取某逻辑地址中的数据需要多次启动磁盘 。优点:不需要连
2、续的内存空间缺点:读取数据需要多次启动磁盘复习:外存分配方式 隐示链接盘块组织方式: 在目录中记录:文件名、起始盘块号 。 其它盘块号存放于FAT上一个盘块号 。特点:从目录及FAT(在内存)中顺序查找 盘块号。因此,读取某逻辑地址中的数据需要 启动1次磁盘。优点:不需要连续的内存空间缺点:顺序查找且安全性差。复习:外存分配方式p索引方式:文件分到一组离散的盘块。 单级索引盘块组织方式: 在目录中记录:文件名、索引盘块号 文件的盘块号按顺序存放在索引表中 。特点:从目录中找到索引盘块,从索引盘块 中直接找到某逻辑地址所在的盘块号。因此, 读取某逻辑地址中的数据需要启动2次磁盘。优点:既能实现离
3、散存储,也能实现随机访 问。缺点:能够处理的文件很小。复习:外存分配方式 多级索引盘块组织方式: 在目录中记录:文件名、外层索引盘 块号 外层索引表中按顺序存放内层索引表 所在的盘块号。 内层索引表中按顺序存放文件存放的 盘块号假设某系统一个盘块大小为1K,某个索引 项需要4B,这逻辑地址A对应的 逻辑块号M=A/1K 每个物理块中的索引项数L=1K/4=256复习:外存分配方式特点: 从目录中找到外层索引盘块 从外层索引表M/L读出内层索引表所在 的物理块号 从内层索引表M%L读出数据所在的物 理块号。 因此,二级索引读取某逻辑地址中的数 据需要启动3次磁盘。优点:既能实现离散存储,也能实现
4、随机访 问。缺点:较小的文件需要多次启动磁盘。复习:外存分配方式 混合索引:UNIX系统使用的文件分配方式盘块组织方式: 在目录设置一个13地址项的索引结点 09为直接文件,即09中存放文件物理 块号 10为一级索引,即10为索引盘块号 11为二级索引,即11中为外层索引盘块 号。 12为三级索引,即12中为三级外层索引 盘块号i_addr0 i_addr1 i_addr9 i_addr10 i_addr11 i_addr12索引结点6.3 外存分配方式6.3 外存分配方式引入目的: 克服顺序方式的缺点需要连续盘块 克服链接方式的缺点无法实现随机存取 克服单级索引的缺点对应文件较小 克服多级索
5、引的缺点较小的文件需要多次 启动磁盘6.3 外存分配方式v盘块大小为1KB,记录盘块号需要4个字节混合索引能处理的最长文件的计算。计算逻辑地址:5000、15000、150000转换为 物理块号和块内位移。简述读取上述逻辑地址对应数据所在的盘块的过 程。若某文件的目录项已经在内存,采用混合索引方 式,读取文件的内容,最少需要启动几次盘块? 最多需要启动几次盘块?6.4 目 录 管 理 q目录文件由若干目录项(FCB)组成,每个目录项 记录一个文件的名字、属性、及其存储位置等信 息,供检索时使用。q目录是文件系统实现按名存取的重要手段。q对目录管理的要求如下: 实现“按名存取”。 提高对文件的检
6、索速度。 文件共享。 允许文件重名。q文件控制块和索引结点v文件控制块 (FCB):就是目录项,在文件控制块( 目录项)中,通常含有以下三类信息:(1)基本信息 类;(2)存取控制信息类;(3)使用信息类。v目录文件占用盘块数的计算:在某文件系统中,每 个盘块为512字节,文件控制块为64个字节,该系统 中共有256个文件,计算目录占用的盘块数?读取一 个FCB平均启动磁盘的次数?6.4 目 录 管 理 v索引结点索引结点的引入:文件目录占用大量的盘块,检 索时需要将盘块一一调入内存,速度慢。其实检索 时,只用到文件名,仅当找到一个目录项时,才需 从该目录项中读出所需的信息。UNIX系统,采用
7、 了把文件名与文件描述信息分开的办法。将文件描述信息单独形成一个称为索引结点的数 据结构,简称为i结点。在文件目录中的每一个目录项,仅由文件名和指 向该文件所对应的i结点的指针所构成。 6.4 目 录 管 理 文件名索引结点编号 Fa 20SQT 30文件目录索引结点编号 文件类型、长度 文件存取权限 文件物理地址 : :索引结点6.4 目 录 管 理 引入索引结点后,查找一个目录项启动盘块的平 均次数:每个盘块为512字节,其中文件名占8个字 节。如果索引结点编号占2个字节,该系统共有256 个文件,为找到其中一个文件的FCB,平均启动磁 盘的次数。6.4 目 录 管 理 q目录结构v单级目
8、录结构: 在整个系统中只建立一张目录表 ,每个文件占一条记录。缺点: (1) 查找速度慢。(2)不允许重名。文件名 物理地址文件说明 状态位 F1 ST6.4 目 录 管 理 v两级目录:为了克服单级目录所存在的缺点, 可以为每一个用户建立一个单独的用户文件目录 UFD。系统建立一个主目录。6.4 目 录 管 理 用户名 指向子目录指针 Wang ZhangWang 用户目录 文件名 Fa.aa.文件名 dd. cc.Zhang用户目录主目录6.4 目 录 管 理 cc.md.bb. Fa.优点: (1)提高了检索目录的速度。 (2)在不同的用户目录中,可以使用相同的文件名 。 (3)不同用户
9、还可使用不同的文件名来访问系统中 的同一个共享文件。6.4 目 录 管 理 单级目录和二级目录比较次数的计算: 例如:某系统有1000个用户,每个用户有100个 文件,问: (1)单级目录结构最多需要比较多少次? (2)二级目录结构最多需要比较多少次?6.4 目 录 管 理 v多级目录结构目录结构:多级目录结构又称为树型目录结构。 主目录在这里又称为根目录,把数据文件称为树叶 ,其它的目录(文件夹)均作为树的中间结点。目录项的分类: 若某个目录项指向的是文件,则称为文件的目 录项 若某个目录项指向的是下一级目录,则称为目 录的目录项6.4 目 录 管 理 ABC 。FAW 。THF 。GHC
10、。D1D2 D3 。MKJ 。AB 。B1B2 。K1K2K3 。q目录查询技术:当用户要访问文件时,系统总是要 对目录进行查询。目前主要使用两种方法:v线性检索法:也叫顺序检索法。利用用户提供的文 件名,在目录文件中顺序查找。v举例:若系统为每个文件建立一个目录项(文件名 和索引结点) ,用户给定的文件路径名是: /usr/wang/fa6.4 目 录 管 理 根目录ID 文件名 1. 2.6usri结点6ID=6132132块内容ID 文件名26 wangID=26496i结点26550块上 的内容ID 文件名60fa496块上的内容ID=60550i结点606.4 目 录 管 理 注:I
11、D为索引结点编号vHash方法:系统建立了一张Hash索引文件目录,利用hash方 法进行查询,将用户提供的文件名变换为文件目录的 索引值,再利用该索引值到目录中去查找,显著地提 高检索速度。文件名转换时要注意“冲突” 。6.4 目 录 管 理 6.5 文件存储空间管理 v文件存储空间管理:操作系统如何管理磁盘空间 (分配及回收)。 连续分配方式:空闲区表(链) 离散分配方式():位示图、成组链接法v分配磁盘空间的单位:盘块(扇区)6.5 文件存储空间管理 v对磁盘空间进行管理: (1)使用数据结构记录系统中盘块的使用情况。 (2)提供分配算法:根据数据结构,按照算法选 择空闲盘块,分配给文件
12、。 (3)提供回收算法:根据删除的文件名,找到分 给该文件的盘块号,并将它们作为空闲盘块记入 数据结构中。q连续分配方式:同内存管理中动态分区分配v特点:给文件分配一组连续的空闲盘块,因此文件 的物理结构为连续文件。v优点:文件的存取速度快,可实现随机存取。v缺点:文件扩充困难,产生较多的外存零头,外存 利用率低。v适用情况: (1)对换区空间的管理:对换区对速度要求高 (2)较小文件的存储6.5 文件存储空间管理 v空闲表法:记录磁盘使用情况的数据结构:空闲表。6.5 文件存储空间管理 序号 第一空闲盘块号空闲盘块数 1204 2411 3603状态 0 1 1存储空间的分配:采用首次适应、
13、循环首次适应、 最佳适应等算法从空闲表中选择一个合适的空闲区 域。存储空间的回收:删除文件会释放一些盘块,将释 放的盘块作为空闲区域记入空闲表中。注意合并。思考: (1)操作系统如何记载将一组连续盘块分配给某个 文件? (2)删除时,如何知道删除文件占用了哪些盘块?6.5 文件存储空间管理 q离散分配方式:v特点:不必给文件分配连续的空闲盘块,因此文件 的物理结构通常为:索引文件、链接文件。v优点:存储空间的利用率高,扩充容易。v缺点:存取速度慢v适用情况:较大文件的存储v两种离散分配方式: (1)位示图法 (2)成组链接法6.5 文件存储空间管理 q位示图:v管理方式: (1)利用二进制的一
14、位(bit)来表示磁盘中一个盘 块的使用情况。当其值为“0”时,表示对应的盘块空 闲;为“1”时表示该盘块已分配。 (2)操作系统通常使用若干个计算机字(1字32位 )来实现位示图。因此,位示图可以看成一个n行*32 列的二维矩阵。 (3)位示图的行、列编号:从0开始。6.5 文件存储空间管理 v关键问题: (1)盘块号是线性的(例如500个盘块,编号为0 499) (2)位示图是二维的(行号、列号) (3)某个盘块号在位示图中对应的行、列号 (4)位示图的某行某列对应的盘块号。6.5 文件存储空间管理 v举例:某系统的磁盘空间为600KB,每个盘块的大 小为1KB,系统使用一个计算机字(32位)来代表位 示图的一行,请计算: (位示图行、列号从0开始, 盘块号从0开始) (1)该位示图至少需要 个计算机字。 (2)第208个盘块,对应位示图的 字 列。 (3)位示图的第7字第28列对应的盘块号是 。6.5 文件存储空间管理