数据结构域算法设计chap6(49-50)

《数据结构域算法设计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 文件存储空间管理