操作系统文件管理相关习题2

文件管理的任务和功能文件管理
任务：对用户文件和系统文件进行组织管理，以方便用户使用，并保证文件的安全
功能：文件存储空间的管理，目录管理，文件读写管理和保护

目录管理

对目录管理的要求

1. 实现按名存取
2. 提高对目录的检索速度
3. 文件共享
4. 允许文件重名

文件控制块和索引结点

• 为了能对文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称为“文件控制块（FCB）
• 一个文件对应一个FCB（目录项），若干目录项组成一个目录文件。

1. 文件控制块
   通常包含三类信息：
   基本信息类：
   1. 文件名
   2. 文件物理位置
   3. 文件逻辑结构
   4. 文件物理结构存取
      控制信息类：
   5. 文件主的存取控制权限
   6. 核准用户的存取控制权限
   7. 一般用户的存取控制权限
      使用信息类：
   8. 文件建立的日期、时间
   9. 文件上一次修改的日期、时间
   10. 当前使用信息：已打开文件的进程数；是否被其他用户锁住；文件在内存中是否已被修改但尚未拷贝到磁盘上
2. 索引结点

   1. 索引结点的引入
      设目录文件所占盘块数为N，则查找一个目录项平均需要调入盘块(N+1)/2次。假如一个FCB为64B，盘块大小为1KB，则每个盘块可存放16个FCB，对于640个FCB的目录文件，需占40个盘块，平均查找一个文件需启动磁盘20次。假如每个FCB占16B，则每个盘块可存放64个FCB，对于640个FCB的目录文件，需占10个盘块，平均查找一个文件需启动磁盘5次。大大节省了系统开销。
      为此，UNIX采用索引结点，每个目录项占16B，其中14B为文件名，2B为i结点指针（索引结点号）

   2. 磁盘索引结点
      主要包括以下内容：

      1. 文件模式：包括文件类型（正规文件、目录文件、字符特别文件、块特别文件、管道文件等)和存取权限(9位二进制表示）。
      2. 文件主标识符uid——拥有该文件的个人·同组用户标识符gid
      3. 文件物理地址一一每一个索引结点中含有13个地址项iaddr(0)～iaddr（12)，混合索引
      4. 文件长度一以字节为单位
      5. 文件连接计数一一在本文件系统中所有指向该文件名的指针计数(一个文件可以对应多个文件名)
      6. 文件存取时间一一文件最近被进程存取的时间、最近被修改的时间及索引结点最近被修改的时间
         

   3. 内存索引|结点
      文件打开时，要将磁盘索引结点拷贝到内存的索引结点中，以便以后使用。
      在内存索引结点中增加了以下内容：

      1. 索引结点编号——用于标识内存素引结点
      2. 状态一一指示结点是否上锁或被修改
      3. 访问计数一一每当有一进程访问此i结点时，将该访问计数加1，访问完再减1
      4. 文件所属文件系统的逻辑设备号
      5. 链接指针一一设置有分别指向空闲内存i结点链表和散列队列的指针（内存i接点采用散列搜索，相同散列地址的i 接点构成一队列，队列内用顺序查找方式。）

目录结构

目录结构的组织，关系到文件系统的存取速度，也关系到文件的共享性和安全性。

1. 单级目录结构
   最简单的目录结构。
   

   状态位用来表示该目录项是否空闲。
   单级目录可以实现按名存取，但有如下缺点：

   1. 查找速度慢
   2. 不允许重名
   3. 不便于实现文件共享，只适用于单用户环境

2. 两级目录
   第一级是主文件目录，第二级是用户文件目录。
   为每个用户建立一个单独的用户文件目录UFD
   系统建立一个主文件目录MFD，在MFD 中，每个用户目录文件占有一个目录项，其目录项
   中包含用户名和指向该用户目录文件的指针

   同一个UFD中文件不能重名
   两级目录基本克服了单级目录的缺点，并有以下优点：

   1. 提高了检索目录的速度
   2. 在不同的用户目录中，可以使用相同的文件名。
   3. 不同用户还可以使用不同的文件名来访问系统中的同一个共享文件。
      

   如果在主目录中有n个子目录（用户目录），每个用户目录最多为m个目录项，则查找指定的目录项，最多只需要检索 n+m个目录项。但如果采用单级目录，则最多需检索n×m个目录项。假定m=n，可以看出，采用两级目录可使检索效率是单级目录的n/2倍。

3. 多级目录结构

   1. 目录结构
      大型文件系统，常采用三级或三级以上目录结构
      多级目录结构又称树型目录结构
      主目录在这里被称为根目录
      

   2. 路径名
      从根目录到任何数据文件，都只有一条唯一的通路。在该通路上，从根目录开始，把全部目录文件名与数据文件名，依次用"/"连接起来，就构成该数据文件的路径名。
      系统中每个文件都有唯一的路径名

   3. 当前目录
      又称工作目录。
      为方便、提高检索速度，为每个进程设置一个“当前目录”，进程对文件的访问都相对于当前目录进行
      相对路径名一从当前目录开始
      绝对路径名—从根目录开始

   4. 增加和删除目录
      在树型目录结构中，用户可以为自己建立UFD，并可再创建子目录。
      创建子目录时，只需注意不要同名（文件名也不行）。
      删除子目录，可采用下述两种方法处理：

      1. 不删除非空子目录(MS-DOS)
      2. 可删除非空子目录(Windows)
         第二种方法比较方便，但却比较危险

目录查询技术

当用户要访问一个已存文件时，系统首先利用用户提供的文件名对目录进行查询，找到该文件的文件控制块或索引结点；然后根据FCB或索引|结点中所记录的文件物理地址（盘块号），换算出文件在磁盘上的物理位置。
目前，目录查询的方式有两种：线性检索法和Hash方法。

1. 线性检索法（顺序检索法）
   对单级目录：根据用户提供的文件名，用顺序查找法直接从文件目录中找到指定文件的目录项
   对树型目录：须对多级目录进行查找。用下面的例子说明
   假定用户提供的文件路径名是/usr/ast/mbox，系统的目录项采用索引结点。
   

2. 文件检索 Hash方法
   针对Hash文件的目录查找方法。
   如果我们建立了一张Hash索引文件目录，便可利用Hash方法进行查询，即系统利用用户提供的文件名并将它转变为文件自录的索引值，再利用该索引值到自录中去查找，将显著地提高检索速度。
   使用通配符星号或？时，不能用Hash法查找。

文件存储空间的管理

与内存分配相似，可采用连续分配方式和离散分配方式
前者具有较高的文件访问速度，但可能产生较多的外存零头;
后者能有效地利用外存空间，但访问速度较慢。
外存空间的分配的基本单位都是磁盘块而非字节。
为实现存储空间的分配，系统必须记住存储空间的使用情况。为此，需：

1. 设置相应的数据结构
2. 提供存储空间分配和回收的手段

空闲表法和空闲链表法

1. 空闲表法

   1. 空闲表
      类似空闲分区表
      属于连续分配方法，与内存的动态分配方式雷同
      每个文件分配一块连续的存储空间
      为外存上的所有空闲块建立一张空闲表，每个空闲区对应一个空闲表项
      空闲表项包括：表项序号、该空闲区的第一个盘块号、空闲块数等。
      将所有空闲区按其起始盘块号递增次序排列
      

   2. 存储空间的分配和回收
      与内存动态分配相似，同样可以采用首次适应算法、循环首次适应算法等
      回收时，相邻接的空闲区应合并。
      与内存的动态分配不同的是空闲表法在磁盘空间分配中仍占有一席之地。例如：
      对换方式中，对换空间一般都采用连续分配方式；
      当文件较小（1～4个盘块）时，仍采用连续分配方式。当文件较大时，采用离散分配。

位示图法

1. 位示图
   位示图是用二进制的一位来表示磁盘中一个盘块的使用情况。
   “0”——空闲；
   “1”——已分配。
   通常用m×n个位数来构成位示图。m×n等于磁盘的总块数。
   

2. 位示图盘块的分配
   顺序扫描位示图，从中找出一个或一组其值为0的二进制位。
   将找到的二进制位，转换成相应的盘块号。

   • 设行号为i，列号为j，则对应的盘块号b为：
   • b = i x n + j
   • n为每行的位数。32位机每个字为32位，上图中是16位。
     修改位示图，令map[i][j] = 1

3. 位示图盘块的回收
   步骤：

   1. 将回收盘块号转换成位示图的行号和列号
      • i = b / n(整数除法，结果取整数)
      • j = b % n
   2. 修改位示图，令map[i][j] = 0
      位示图小，可以调入内存，节省了许多磁盘操作
      位示图常用于微型机和小型机，如CP/M、Apple DOS等OS中

文件共享与文件保护

基于索引结点的共享方式

索引节点中应增加一个链接计数count
任何用户对共享文件的修改，都是其他用户可见的

此种共享方式，如果文件主不再需要此文件时，不能删除。
如果系统采用记帐收费，则文件主C必须为共享者B使用此文件而付费

利用符号链实现文件共享

为使B能共享C的一个文件F，可以由系统创建一个LINK类型的新文件，也取名为F，并将它写入B的目录中，以实现B的目录与文件F的链接。
在新文件中只包含链接文件F的路径名。这种方法称为符号链接。
允许文件主删除文件。只不过当B要使用文件F时，会“找不到文件”，不会产生其他影响。
缺点:

1. 共享文件时，可能要按路径多次读盘
2. 新文件也要占用磁盘空间。

2

设某系统的磁盘空间共有2500块，计算机字长32位。系统用位示图方法管理磁盘空间

1. 位示图需用多少字构造
2. 画出申请一块的工作流程图

---

位示图一行代表一个字
字长有32位，代表bit位，一个字长32，位示图有32列
序号默认从0开始
行数等于2500除以32=78.125，向上取整79
2.
1. 检查位示图是否有空闲块
2. 若有空闲块，找到第一个空闲块的位置
3. 将该位标记为已使用
4. 返回该块的物理地址，完成申请
5. 若没有空闲块，返回申请失败

2015

用一张8个16位字长的字组成的”位示图”来管理一个高速存储器，现规定字号，位号和块号均从1开始计，试问：

1. 该位示图可表示多少块？
2. 字号为7，位号13所对应的块号是多少？
3. 块号55对应的字号和位号分别是多少？

---

8 x 16 = 128
2.
i = 7，j = 13
b = n( i - 1 ) + j = (7 - 1) x 16 + 13 = 109
3.
i = (b - 1) DIV n + 1 = (55 - 1) / 16 + 1 = 3 + 1 = 4
j = (b - 1) MOD n + 1 = (55 - 1) % 16 + 1 = 6 + 1 = 7
或
55 / 16 = 3 … 7，（从0开始）
所以字号是1，位号为7