14 第六章 文件管理 6.4-6.6.pptx

第1页：第六章 文件管理封面

第六章 文件管理：本页为《计算机操作系统》课件封面，标注课程名称与英文名称 Operating Systems，并列出 WINDOWS、UNIX、LINUX 等常见操作系统类型。

第2页：6.4目录管理

6.4目录管理

• 对目录管理的要求如下
• (1)实现“按名存取”
• 目录管理中最基本的功能
• (2)提高对目录的检索速度
• (3)文件共享
• 须在外存中只保留一份文件的副本
• (4)允许文件重名
• 允许不同用户对不同文件取相同的名字

第3页：6.4.1文件控制块和索引结点

6.4.1文件控制块和索引结点

• 文件控制块（FCB）
• 是用于描述和控制文件的数据结构
• 文件管理程序可借助FCB中的信息对文件施以各种操作
• 文件控制块的有序集合称为文件目录，即一个文件控制块就是一个文件目录项
• 通常，一个文件目录本身也被看作是一个文件，称为目录文件

第4页：文件控制块

文件控制块

• 基本信息类
• 文件名、物理位置、逻辑结构、物理结构
• 文件控制信息类
• 文件拥有者权限、核准用户权限、一般用户权限
• 使用信息类
• 文件建立日期、文件修改日期如：MS-DOS中的文件控制块，FCB的长度为32个字节

第5页：索引结点的引入：减少检索开销

索引结点的引入：减少检索开销

• 索引结点的引入
• 文件目录通常是存放在磁盘上的
• 在查找目录的过程中：1.先将存放目录文件的第一个盘块中的目录调入内存，2.把用户所给定的文件名与目录项中的文件名逐一比较3.若未找到指定文件，便再将下一个盘块中的目录项调入内存

第6页：索引结点引入的磁盘访问计算

索引结点引入的磁盘访问计算

• 索引结点的引入
• 假如一个FCB为64 B，盘块大小为1 KB，若一个文件目录中共有640个FCB，需占用个盘块
• 每个盘块中只能存放：个FCB
• 平均查找一个文件需启动磁盘次
• 平均查找一文件需启动磁盘次数太多
• 在检索目录文件的过程中，只用到了文件名
• 仅当一目录项中的文件名与指定要查找的文件名相匹配时，才需从该目录项中读出文件的物理地址。40个1620

第7页：UNIX系统——索引结点的引入

UNIX系统——索引结点的引入：UNIX系统采用了把文件名与文件描述信息分开的办法文件名属性、长度、地址等信息文件目录项FCB文件名索引节点编号属性、长度、地址等信息文件目录项索引节点。

第8页：索引结点(i结点)

索引结点(i结点)

• 2．索引结点
• 索引结点(i结点)
• 使文件描述信息单独形成一个称为索引结点的数据结构
• UNIX的文件目录
• 在UNIX系统中一个目录仅占16个字节，其中14个字节是文件名，2个字节为i结点指针

第9页：索引结点的盘块目录项计算

索引结点的盘块目录项计算

• 索引结点
• 若每个目录项占16B，盘块大小为1 KB
• 每盘块可存64个目录项
• 640个目录项只占10个盘块
• 为检索到一个文件，平均启动磁盘次数=5
• 查找目录时间大大缩短

第10页：索引结点

索引结点

• 磁盘索引结点
• 每个文件有惟一的一个磁盘索引结点
• 存放在磁盘上的索引结点
• 内存索引结点
• 当文件被打开时，要将磁盘索引结点拷贝到内存的索引结点中

第11页：磁盘索引结点包含的内容

磁盘索引结点包含的内容

• 磁盘索引结点
• (1)文件主标识符
• (2)文件类型
• (3)文件存取权限
• (4)文件物理地址：iaddr
• (12)以直接或间接方式给出数据文件所在盘块的编号
• (5)文件长度
• (6)文件链接计数
• (7)文件存取时间

第12页：内存索引结点

内存索引结点

• 增加了以下内容
• (1)索引结点编号--用于标识内存索引结点
• (2)状态
• 指示i结点是否上锁或被修改
• (3)访问计数
• 每当有一进程要访问此i结点时，将该访问计数加1，访问完再减1
• (4)文件所属文件系统的逻辑设备号
• (5)链接指针--设置有分别指向空闲链表和散列队列的指针

第13页：6.4.2目录结构

6.4.2目录结构

• 6.4.2目录结构1．单级目录结构
• 在整个文件系统中只建立一张目录表
• 每个文件占一个目录项
• 目录项中含文件名、文件扩展名、文件长度、文件类型、文件物理地址以及其它文件属性
• 为表明每个目录项是否空闲，又设置了一个状态位

第14页：单级目录结构

单级目录结构

• 单级目录
• 单级目录的优点
• 是简单且能实现目录管理的基本功能
• 按名存取
• 缺点
• (1)查找速度慢
• (2)不允许重名
• (3)不便于实现文件共享
• 应当允许不同用户使用不同的文件名来访问同一个文件
• 单用户环境

第15页：两级目录的组成

两级目录的组成

• 2．两级目录
• 可为每一个用户建立一个单独的用户文件目录
• 所有用户的文件目录具有相似的结构
• 它由用户文件控制块组成。主文件目录

第16页：两级目录结构的优点

两级目录结构的优点

• 两级目录结构
• 两级目录结构的优点
• (1)提高了检索目录的速度
• (2)在不同的用户目录中，可使用相同的文件名
• (3)不同用户可用不同的文件名访问同一共享文件

第17页：多级目录结构

多级目录结构

• 3．多级目录结构
• 目录结构（又称树型目录结构）
• 主目录被称为根目录，把数据文件称为树叶，其它目录作为树的结点

第18页：路径名

路径名

• 每个文件有又惟一的路径名
• 从根目录始，把全部目录文件名与数据文件名依次地用“/”连接起来，构成该数据文件的路径名。/B/F/J/B/E/J/B/F/K

第19页：当前目录

当前目录

• 当前目录(工作目录)
• 进程对各文件的访问都相对于“当前目录”而进行
• 在UNIX/Linux系统中，“ . ”是指当前目录，“..”是指父目录

第20页：相对路径名和绝对路径名

相对路径名和绝对路径名

• 相对路径名
• 从当前目录开始直到数据文件为止所构成的路径名
• 绝对路径名
• 从树根开始的路径名称当前目录是/B/F

第21页：Linux层次目录结构

Linux层次目录结构：Linux层次目录结构Btestfile.ctty00／devusrlibetchometty01binlibmantmppasswdvarwangmyfile.cgettylotlabfei4fei5。

第22页：增加和删除目录

增加和删除目录

• 4．增加和删除目录
• (1)不删除非空目录
• 为删除一非空目录，须先删除目录中的所有文件，使之先成为空目录
• (2)可删除非空目录
• 当要删除一个目录时，如果在该目录中还包含有文件，则目录中的所有文件和子目录也同时被删除
• 上述两种方法实现起来都比较容易，第二种方法虽方便，但较危险

第23页：6.4.3目录查询技术——线性检索法

6.4.3目录查询技术——线性检索法：6.4.3目录查询技术——线性检索法1．在树型目录中，用户提供的文件名是由多个文件分量名组成的路径名。/usr/ast/mbox。

第24页：目录查询技术：Hash法

目录查询技术：Hash法

• 目录查询技术
• 建立一张Hash索引文件目录
• 系统利用用户提供的文件名并将它变换为文件目录的索引值
• 再利用该索引值到目录中去查找，这将显著地提高检索速度
• 对于使用了通配符的文件名，系统此时便无法利用Hash方法检索目录

第25页：练习：UNIX目录路径

练习：UNIX目录路径

• 练习
• 在UNIX/LINUX系统中，如果当前目录是／home/ f1，那么，相对路径为..／f2/b.c文件的绝对路径名是什么？答：在本题中当前目录是／home/ f1，故相对路径为..／f2/b.c文件实际上是home目录下的文件，故绝对路径名是：／home/ f2 /b.c。homef2f1a.cb.c／

第26页：6.5文件存储空间的管理解决的问题

6.5文件存储空间的管理解决的问题

• 6.5文件存储空间的管理解决的问题：如何为新创建的文件分配存储空间？解决的方法：1、分配方式
• （1）连续分配：访问速度高，但会产生外存零头
• （2）离散分配：访问速度慢，但能有效利用外存空间。2、分配时数据结构3、分配回收算法

第27页：文件存储空间的管理方法

文件存储空间的管理方法

• 文件存储空间的管理
• 空闲表法和空闲链表法
• 位示图法
• 成组链接法

第28页：6.5.1空闲表法和空闲链表法

6.5.1空闲表法和空闲链表法

• 6.5.1空闲表法和空闲链表法1．空闲表法
• 属连续方式，与内存的动态分配类似
• 为外存上的所有空闲区建立一张空闲表
• 每个空闲区对应于一个闲表项
• 将所有空闲区按起始盘块号递增的顺序排列

第29页：空闲盘区的分配与回收

空闲盘区的分配与回收

• 空闲盘区的分配
• 采用首次适应算法、循环首次适应算法等
• 回收

第30页：外存与内存分配方式的比较

外存与内存分配方式的比较

• 存储空间的分配与回收
• 在内存分配上
• 很少采用连续分配方式
• 在外存的管理中
• 连续分配方式具有较高的分配速度，故它在诸多分配方式中仍占有一席之地
• 对换空间
• 一般都采用连续分配方式
• 当文件较小(1～4个盘块)时，仍采用连续分配方式
• 当文件较大时，便采用离散分配方式

第31页：空闲链表法

空闲链表法

• 2．空闲链表法
• 空闲链表法是将所有空闲盘区拉成一条空闲链
• 可把链表分成两种形式
• 空闲盘块链
• 空闲盘区链

第32页：空闲盘块链

空闲盘块链

• 将磁盘上的所有空闲盘块拉成一条链
• 当请求分配存储空间时
• 系统从链首开始，依次摘下适当数目的空闲盘块分配给用户
• 因删除文件而释放存储空间时

第33页：空闲盘块链的优缺点

空闲盘块链的优缺点

• 空闲盘块链
• 优点是
• 用于分配和回收一个盘块的过程非常简单
• 但在为一个文件分配盘块时，可能要重复操作多次

第34页：空闲盘区链

空闲盘区链

• 将磁盘上的所有空闲盘区拉成一条链
• 在每盘区上含有指示下一个空闲盘区的指针和指明本盘区大小的信息。012345678910111213141516171819202122232425262728293031

第35页：空闲盘区链的分配与回收

空闲盘区链的分配与回收

• 空闲盘区链分配和回收盘
• 分配盘区的方法
• 通常采用首次适应算法
• 为了提高对空闲盘区的检索速度，可以采用显式链接方法，在内存中为空闲盘区建立一张链表
• 在回收盘区时
• 也要将回收区与相邻接的空闲盘区相合并4239515-1

第36页：6.5.2位示图法

6.5.2位示图法

• 6.5.2位示图法1．位示图
• 利用二进制的一位来表示磁盘中一盘块的使用情况
• 磁盘上所有盘块都有一二进制位与之对应，由所有盘块所对应的位构成一个集合，称为位示图
• m×n等于磁盘的总块数

第37页：位示图盘块号计算

位示图盘块号计算：位示图第 i 行、第 j 列对应的盘块号按下式计算：b = 16 × (i − 1) + j，式中 16 为每行二进制位数。

注：源文件该页公式处粘连有图像噪声数字「12」，已按教材标准式 b = 16 × (i − 1) + j 修正。

第38页：位示图法盘块的分配

位示图法盘块的分配

• 2．盘块的分配
• (1)顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)
• (2)将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应盘块号应按下式计算：b = n(i-1) + j式中，n代表每行的位数

第39页：位示图法盘块的回收

位示图法盘块的回收

• 3．盘块的回收
• (1)将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：i =(b-1)DIV n + 1j =(b-1)MOD n + 1
• 该方法的优点是
• 很容易找到一个或一组相邻接的空闲盘块
• 位示图很小，占用空间少，因而可将它保存在内存中

第40页：位示图盘块分配例题

位示图盘块分配例题：有一计算机系统利用图中所示的位示图来管理空闲盘块，块的大小为1KB，现要为某文件分配两个盘块，试具体说明盘块的分配过程。（假设可以离散分配）161514131211109876543211111111111111111111111111111111112111111111111101131111111110111111400000000000000005。

第41页：位示图例题解答

位示图例题解答：(1)顺序检索位示图，从中找到第一个值为0的二进制位，行号i1=3，列号j1=3；第二个值为0的二进制位，行号i2=4，列号j2=7。

第42页：作业

作业：作业。