设备管理_文件的物理结构及存储设备

8 2 2文件的物理结构及存储设备 3 索引文件索引文件是由系统为每个文件建立一张索引表 表中标明文件的逻辑块号所对应物理块号 索引表自身的物理地址由FCB给出 索引表结构 索引文件 这种方法克服了链接文件对随机存取的限制 把所有的指针放在一起 索引块每个文件都有它自己的索引块索引块的第i个条目指向文件的第i个块 随机存取 一个索引块类似于内存分配中的一个页表索引文件的开销要比链接文件大 尤其如果每个文件只有很少的块时 会造成其余索引块的浪费 索引分配 a out 16 目录项 条目 文件名 索引块 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 21 22 23 44 53 56 nil 012345678910111213 索引块 16 8 2 2文件的物理结构及存储设备 如果索引表很大 超过了一个物理块 则系统势必要像处理其他文件一样 来处理索引表的物理存放方式 这样不利于索引表的动态增删 解决的办法是采用多重索引的方式 也就是说 当索引表所指的物理块超过一块时 再增加一个次级索引表 这样 在高一级索引表表项里所指向的物理块中并不存放实际的文件信息 而是存放的一个索引表 在这个次一级的索引表中所指向的物理块才是存放的文件信息 如果需要 可以增加到3级以上的多级索引 链接索引块 a out 16 directoryentry filename indexblock 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 39 21 22 23 44 53 56 0123456789101112 255 indexblock 16 nil 57 59 40 41 nil 0123456789101112 255 indexblock 39 多层索引 a out 16 directoryentry filename indexblock 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 26 34 10 43 nil 0123456789101112 255 toplevelindexblock 16 0123456789101112 255 0123456789101112 255 0123456789101112 255 0123456789101112 255 secondaryindexblocks 组合链接 多层索引 TheUnixinode owner group timestamps size directblocks singleindirect doubleindirect tripleindirect block data block data block data block data block data block data block data block data block data filenameisnotstoredintheinode indexblock UsedinBSDUnix 8 2 2文件的物理结构及存储设备 2 文件的存储设备文件的存储设备分为不可重复使用的和可重复使用的两类 不可重复使用的文件存储设备也称为I O式字符设备 如打印纸等 可重复使用的文件存储设备有磁带 磁盘 光盘等 也称块设备 8 2 2文件的物理结构及存储设备 两种典型的存储设备特性及存取方法 1 顺序存取设备顺序存取设备通常是指那些容量大 价格低的存储设备 2 直接存取设备光盘 磁盘都是一种可直接存取的存储设备 磁盘又分为硬盘和软盘 磁盘磁盘是一种可直接存取 按地址存取 的存储设备 它把信息记录在盘片上 每个盘片有正反两面 只读型光盘光盘存储器是利用光学原理存取信息的存储设备 8 2 2文件的物理结构及存储设备 3 文件结构 存储设备与存取方式综上所述 文件的物理结构 必须适应文件的存储设备 而不同的存储设备的特性 又决定了其上的文件的存取方式 下面以磁盘和磁带存储设备为例 简要说明3者的关系 磁盘上的文件结构为连续时 其存取方式一般为顺序或随机 当文件为连续方式时 存取方式通常为顺序的 磁带上的文件结构为连续时 其存取方式一般为顺序存取 当其上文件为索引文件时 存取方式可为顺序 随机两种形式 8 3文件管理 8 3 1文件目录结构1 文件目录文件系统为程序和用户提供了按文件名存取文件的机制 而将文件名转换为存储地址 以及对文件实施控制管理则需通过文件目录来实现 文件目录的管理和文件存储空间的管理已成为文件管理的重要内容 8 3 1文件目录结构 一个文件由文件说明和文件体组成 文件说明部分包括文件的基本信息 存取控制信息和文件使用信息 基本信息包括 文件名 用于标识一个文件的符号名 文件物理位置 标明文件内容在外存上的存储位置 文件结构 指示文件的逻辑结构和物理结构 它决定了文件的寻址方式 存取信息包括 各类用户 包括文件主 核准用户 普通用户等 的存取权限 实现文件的共享及保密 使用信息包括 文件创建 修改的日期和时间 以及当前使用的状态信息 8 3 1文件目录结构 文件系统将这些说明部分的全部信息集中起来 以一个数据结构的形式表示 称此结构为文件控制块FCB FileControlBlock 文件目录由文件控制块组成 文件系统在每个文件建立时都要为它建立一个文件目录 文件目录用于文件描述和文件控制 实现按名存取和文件信息共享与保护 随文件的建立而创建 随文件的删除而消亡 不同的操作系统有不同的文件目录 8 3 1文件目录结构 下面以UNIX文件目录为例加以说明 UNIX系统的文件目录由目录项和索引节点两部分组成 i节点 加快文件检索方法之一 目录项占16B 其中14B为文件名 2B为指向文件说明信息的索引节点的指针 每个索引节点占64B 包括文件属性 文件共享目录数 时间 文件存放块号 文件长度等说明信息 8 3 1文件目录结构 2 文件目录结构文件目录是由文件说明组成的 若干个文件目录组成一个专门的目录文件 目录文件的结构如何 关系到文件的存取速度和文件的共享及安全特性 文件目录结构是指专门的目录文件的组织形式 常用的目录结构有单级目录 二级目录和多级目录 8 3 1文件目录结构 1 单级目录文件系统在每个存储设备上仅建立一个目录文件的目录结构 称为单级目录 或称一级目录 目录文件中的每一目录项 或称一条记录 对应一个文件目录 它包含相对的数据项 文件名及扩展名 物理地址 说明信息 如图所示 8 3 1文件目录结构 单级目录的优点是结构简单 通过管理其目录文件 便可实现对文件信息的管理 单级目录的特点是 搜索范围宽 不允许文件重名 不便于文件共享 8 3 1文件目录结构 2 二级目录结构二级目录结构将存储在设备上的目录文件分成两级 第一级为系统目录 称主目录MFD 它包含了用户目录名和指向该用户目录的指针 第二级为用户目录 称UFD 它包含了该用户所有文件的文件目录 该文件目录和上述单级的目录一样 包含了相应文件的名字 物理地址等 8 3 1文件目录结构 二级目录结构 8 3 1文件目录结构 3 多级目录结构采用树型数据结构方法 便形成一种树型的结构目录 这种文件目录的第一级系统目录为树的根节点 定义为根目录 文件目录的第二级和以下各级目录均为树的分支节点 非终节点 均定义为子目录 只有树的叶节点 终节点 才为文件 注 树型目录的每一级既可定义目录也可定义文件 树型目录 root 8 3 1文件目录结构 从根目录经各级子目录到达文件的通路上的所有子目录名称为文件的存取路径 文件的绝对路径 从根目录开始 文件的相对路径 从当前目录开始 在多级目录结构中 要访问一个文件必须从根目录开始 逐级查找各级子目录 直到文件 无疑这样查找速度较慢 有必要为系统建立一个称之为 工作目录 的当前目录 加快文件检索方法之二 它不一定是根目录 当用户不另外指定缺省目录时 系统从该目录起进行查找 不同的文件系统都可以设置这种工作目录 将多级目录结构进一步推广 就产生了无环结构目录图状结构目录 8 3 1文件目录结构 3 文件目录与文件共享为了有效的实现文件共享 文件系统在建立文件目录的过程中 采用了以下两种方法 使文件只需保存一个副本 达到多个用户共享的目的 1 绕道法 交叉法 绕道法查找共享文件的方法是每个用户从各自当前目录开始 向上返回到共享文件所在路径的交叉节点 然后沿交叉节点顺序向下访问到共享文件 8 3 1文件目录结构 绕道法 链接 文件共享的另一种方法 真正的树型结构目录仅允许每个文件存在于该结构中的一个地方 一个文件或子目录出现在目录结构的几个地方常常是方便的 例如 两个程序员正在某个相同的项目上工作 都希望与项目关联的若干文件保存在自己的目录中 共享文件 或目录 不同于文件拷贝 链接 在Unix系统中 共享文件可以通过创建链接来实现 Unix支持两种类型的链接 硬链接是复制指向相同存储区的目录条目软链接 符号链接 是别名或其它文件或目录的指针 在MSWindows中的快捷方式 链接 root 硬链接 directorya directoryb disk 软链接 directorya directoryb disk 链接问题 链接可能引入一致性问题 对于硬链接当文件被删除时会发生什么 对Unix系统 每个文件有链接计数 当指向一个文件的新链接建立时 该链接计数增加 当一个文件被从目录中删除时 该链接计数减少 如果链接计数是0 该文件所占据的空间被释放 链接问题 对于软链接如果原来的文件被删除 那么所有软链接被留下悬空 这就像发生在MSWindows的快捷方式 8 3 1文件目录结构 2 基本文件目录表法 为了有效实现系统文件的共享 文件系统需建立一基本文件目录BFD 它包括了文件的结构 物理块号 存取控制和管理信息 另外 需增加符号文件目录表SFD 包括用户给定的符号名和系统文件赋予的文件说明信息的内部标识符 主目录 MFD 记录了文件名和系统给定的惟一标识 8 3 1文件目录结构 文件目录表 8 3 1文件目录结构 在实现文件共享时 可以有以下的两种模式 不同时使用同一文件 同时使用同一文件 当所有进程都不修改文件时 情况比较简单 如果某些进程要求对文件修改 那么就必需加以控制 否则数据一致性就得不到保证 控制的方法有两种 一种是不允许读者与写者 或者写者与写者同时打开文件 但这会降低文件并发性 并可能导致死锁 另一种是允许其同时打开文件 由OS为用户提供相应的互斥手段 文件使用者借用这种手段保证对文件的同时共享不发生冲突 8 3 2文件目录管理 如上所述 文件的目录是以目录文件的形式存放的 当存取一个文件时 往往需要访问多级文件目录 如果对每一级目录访问都需要到文件存储设备上去搜索 势必占用过多的CPU时间 若在系统启动时 把全部目录文件读入内存 由系统直接在内存实施对各级目录的搜索则虽然提高了访问速度 但需要的内存容量太大 一般来说 系统只把当前正在使用的那些文件的目录表 打开文件表 加快文件检索方法之三 复制到内存中 为此 系统提供两种特殊操作 其一是把有关的目录文件复制到内存指定区 通常称为打开文件 Open 其二是提供用户不再访问的有关文件的目录文件删除的操作 通常称为关闭文件 Close 8 4文件存储空间的分配与管理 由文件的存储结构可知 文件信息的交换都是以块为单位进行的 因此 将文件存储设备称为块设备 这里介绍的存储空间的管理实际上是对文件块空间而言的 具体说是指空闲块的组织与回收 一般来说 空闲块空间的分配常常有两种方式 一种静态分配 另一种是动态分配 另外在分配的区域上 可以将一个文件分配在一个完整的分区中 以块或簇为单位 常使用包含文件名 起始地址 长度的文件分配表FAT等 8 4 1文件存储空间的分配 文件空间分配常采用 连续分配 索引分配 链接分配3种方法 1 连续分配连续分配方式是将文件存放在辅存的连续存储区中 8 4 1文件存储空间的分配 2 索引分配索引分配方法主要是利用文件分配表FAT给每个文件分配一个指出该文件的索引表所在的物理块号的表目 索引表所在的索引块与存储文件的文件块是分离的 文件索引的每个表目的设置有两种情况 一种是直接给出索引文件各物理块 另一种是设置文件的起始块和长度 这有利于连续分配 也有利于节省索引表空间 提高效率 如图所示 8 4 1文件存储空间的分配 8 4 1文件存储空间的分配 3 链接分配链接分配文件空间的方法是一种离散分配方式 适用于文件长度需动态增减 或用户对其文件的应用不十分明确的情况 一般分配非连续的辅存空间 采用链接表方法链接存储空间 链接空间的大小大多以区或段为单位 8 4 1文件存储空间的分配 1 以扇区为链接单位这是给需动态变化的文件分配若干磁盘扇区 这些扇区在磁盘上可以不连续 而分配给同一文件的各扇区按其上文件逻辑记录的次序用链指针链接起来 2 以区段 或簇 为单位分配这不是以扇区为单位进行分配 而是以区段 或称簇 为单位进行分配的 8 4 2磁盘空间管理 文件的磁盘存储空间的管理包括磁盘空间块的分配和回收 1 盘块盘块是操作系统传输数据的基本单位 盘块大 I O操作传输数据量多 传输性能好 但也会造成盘空间的浪费 既要提高传输率 又要减少盘空间的浪费 是文件系统追求的目标 盘块是重要因素之一 8 4 2磁盘空间管理 1 逻辑块逻辑磁盘是文件系统中一个抽象的存储概念 系统将逻辑磁盘视为一些有固定大小可随机存取的逻辑块的线性序列 磁盘驱动程序将逻辑块映射到物理介质上 一般情况下 一个物理磁盘被分成物理上连续的几个分区 每个分区就是一个逻辑磁盘 又称磁盘分区 通常所说的磁盘分区就是将每一个分区定义为一个盘 此盘就是一个逻辑磁盘 2 盘区磁盘分区是将磁盘上一组连续的柱面空间组成一体 定义为一个盘区 其上可有一个独立的文件系统 不同类的文件系统可占有不同的盘 各自定义自己盘块的大小 8 4 2磁盘空间管理 2 磁盘块大小 磁盘块大小 可以理解为磁盘分配的单位 它规定了文件系统的分配粒度和磁盘I O粒度 盘块大 有利于增加系统性能 不同的文件系统块大小也不同 FFS FreeBSD的快速文件系统 可大于等于4KB NTFS NT内核的文件系统 簇的大小并不依赖于磁盘或分区的大小 可大到64KB FAT32的簇大小可达到32KB 片断 是盘块的组成单位 8 4 2磁盘空间管理 3 盘块管理盘块管理常用盘图 链表和i节点等手段 因文件系统而异 1 盘图法盘图也称字位映像图 是一种常用的方法 它用位 bit 的值0 1来表示磁盘上相应物理块是否被分配 bit值为1表示对应物理块被分配 为0表示对应物理块为空闲 对应一串连续的bit值 按字节构成一张表 此表可以把一个完整磁盘的使用情况记载下来 盘图法 分配时 b 块号 n 字长 i 行号 j 列号 回收时 i 行号 b 块号 divn 字长 j 列号 b 块号 modn 字长 8 4 2磁盘空间管理 2 链接法 链接索引块 这是一种常用的方法 它首先是选择若干空闲物理块建立索引表块 假设这样块的大小为1KB 可以设512个表目 每个表目占用16位 以此表示一个空闲物理块的块号 则每个表目对应一个空闲物理块 而后将这些含有空闲块号的索引块之间用链接方式链接起来 即每个索引块的第0个表目作为链表的指针 指