计算机操作系统

Computer Operation System

安徽师范大学——计算机与信息学院———— 作者(授课教师): 周文

第八章 磁盘存储器的管理

一、外存的组织方式

• 如前所述，文件的物理结构直接与外存的组织方式有关。对于不同的外存组织方式，将形成不同的文件物理结构。目前常用的外存组织方式有：

  (1) 连续组织方式。

  (2) 链接组织方式。

  (3) 索引组织方式。

1.1 连续组织方式

• 连续组织方式又称连续分配方式，要求为每一个文件分配一组相邻接的盘块。例如，第一个盘块的地址为b，则第二个盘块的地址为b+1，第三个盘块的地址为b+2，…。

• 通常，它们都位于一条磁道上，在进行读/写时，不必移动磁头。在采用连续组织方式时，可把逻辑文件中的记录顺序地存储到邻接的各物理盘块中，这样所形成的文件结构称为顺序文件结构，此时的物理文件称为顺序文件。

  

  • 连续组织方式的主要优点有：

    (1) 顺序访问容易。

    (2) 顺序访问速度快。

  • 连续组织方式的主要缺点如下：

    (1) 要求为一个文件分配连续的存储空间。

    (2) 必须事先知道文件的长度。

    (3) 不能灵活地删除和插入记录。

    (4) 不适合那些动态增长的文件。

1.2 链接组织方式

• 如果可以将文件装到多个离散的盘块中，就可消除连续组织方式的上述缺点。

  • 在采用链接组织方式时，可为文件分配多个不连续的盘块，再通过每个盘块上的链接指针，将同属于一个文件的多个离散的盘块链接成一个链表，由此所形成的物理文件称为链接文件。

  • 链接组织方式的主要优点是：

    (1) 消除了磁盘的外部碎片，提高了外存的利用率。

    (2) 对插入、删除和修改记录都非常容易。

    (3) 能适应文件的动态增长，无需事先知道文件的大小。

1. 隐式链接

   • 在采用隐式链接组织方式时，在文件目录的每个目录项中，都须含有指向链接文件第一个盘块和最后一个盘块的指针。

     

2. 显式链接

   • 这是指把用于链接文件各物理块的指针显式地存放在内存的一张链接表中。该表在整个磁盘中仅设置一张，如图8-3所示。

   • 这张表被称为FAT(File Allocation Table)

     

1.3 FAT技术

1.  FAT12

   1) 早期的FAT12文件系统

   • FAT12是以盘块为基本分配单位的。由于FAT是文件系统中最重要的数据结构，为了安全起见，在每个分区中都配有两张相同的文件分配表FAT1和FAT2。

   • 在FAT的每个表项中存放下一个盘块号，它实际上是用于盘块之间的链接的指针，通过它可以将一个文件的所有的盘块链接起来，而将文件的第一个盘块号放在自己的FCB中。

     

   2) 以簇为单位的FAT12文件系统

   • 稍加分析便可看出，如果把每个盘块(扇区)的容量增大n倍，则磁盘的最大容量便可增加n倍。但要增加盘块的容量是不方便和不灵活的。
   • 为此，引入了簇(cluster)的概念。

2. FAT16

   • FAT12对磁盘容量限制的原因在于，FAT12表中的表项有限制，亦即最多只允许4096个。这样，随着磁盘容量的增加，必定会引起簇的大小和簇内碎片也随之增加。

3. FAT32

   • 由于FAT16表的长度只有65535项，随着磁盘容量的增加，簇的大小也必然会随之增加，为了减少簇内碎片，也就应当增加FAT表的长度，为此需要再增加FAT表的宽度，这样也就由FAT16演变为FAT32。

     

1.4 NTFS的文件组织方式

1. NTFS新特征

   • NTFS(New Technology File System)是一个专门为Windows NT开发的、全新的文件系统，并适用于Windows 2000/XP及后续的Windows OS。

2. 磁盘组织

   • NTFS是以簇作为磁盘空间分配和回收的基本单位的。一个文件占用若干个簇，一个簇只属于一个文件。 这样，在为文件分配磁盘空间时，就无须知道盘块的大小，只要根据不同的磁盘容量，选择相应大小的簇，NTFS具有了与磁盘物理块大小无关的独立性。

3. 文件的组织

   • 在NTFS中，以卷为单位，将一个卷中的所有文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT(Master File Table)中。
   • 该表是NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表中占有一行，其中还包括MFT自己的这一行。每行大小固定为1 KB，每行称为该行所对应文件的元数据(metadata)，也称为文件控制字。

1.5 典型练习

• 某磁盘大小为120MB，每个盘块大小为512B，假设每个FAT表项占用12位，则FAT表占用多大的存储空间?

  A. 360KB B. 240KB C.960MB D. 8KB

• 假定一个文件系统的组织方式与MS-DOS类似，在FAT中可有64K个指针，盘块大小为512B,试问该文件系统是否可以指引一个512MB的磁盘？

1.6 索引组织方式

1. 单级索引组织方式

   • 链接组织方式虽然解决了连续组织方式所存在的问题(即不便于随机访问)，但又出现了另外两个问题，即：

     ① 不支持高效的直接存取，要对一个较大的文件进行存取，须在FAT中顺序地查找许多盘块号；

     ② FAT需占用较大的内存空间，由于一个文件所占用盘块的盘块号是随机地分布在FAT中的，因而只有将整个FAT调入内存，才能保证在FAT中找到一个文件的所有盘块号。

     

2. 多级索引组织方式

   • 在为一个大文件分配磁盘空间时，如果所分配出去的盘块的盘块号已经装满一个索引块时，OS须再为该文件分配另一个索引块，用于将以后继续为之分配的盘块号记录于其中。

   • 依此类推，再通过链指针将各索引块按序链接起来。

     

• 例题

  • 上图中，如果一个盘块的大小是1KB，每个盘块号占4个字节，则采用两级索引时，所允许的最大的文件长度是多少？如果盘块是4KB，所允许的最大文件长度是多少？

• 答案

  • 盘块大小为1KB时，索引块中存放盘块号数为256个，两级索引，可放在盘块号为$256 \times256=64K$个，对应于64K个盘块，则允许最大文件文件长度$64K\times1K=64M$。
  • 同理，索引块中盘块号的数量为1K个，采用二级索引，可存放盘块号为$1K\times1K=1M$个，对应于1M个盘块，最大文件长度为$1M\times4K=4G$。

3. 增量式索引组织方式

   1) 增量式索引组织方式的基本思想

   • 为了能较全面地照顾到小、中、大及特大型作业，可以采取多种组织方式来构成文件的物理结构。
   • 如果盘块的大小为1 KB或4 KB，对于小文件(如1 KB～10 KB或4 KB～40 KB)而言，最多只会占用10个盘块
   • 为了能提高对数量众多的小型作业的访问速度，最好能将它们的每一个盘块地址都直接放入文件控制块FCB(或索引结点)中，这样就可以直接从FCB中获得该文件的盘块地址。

   2)  UNIX System V的组织方式

   • 在UNIX System V的索引结点中设有13个地址项，即$i.addr(0)～i.addr(12)$，如图8-8所示。

     (1) 直接地址。

     (2) 一次间接地址。

     (3) 多次间接地址。

     

1.7 典型例题

• 在 UNIX 中，如果一个盘块的大小为1KB ，每个盘块号占4 个字节，即每块可放256个地址。请转换下列文件的字节偏移量为物理地址。

  1. $9999$
  2. $18000$
  3. $420000$

• 答案

  • 先将逻辑文件的字节偏移量转换为逻辑块号和块内偏移量,就是将 [字节偏移量 ]/[ 盘块大小]，商为逻辑块号，余数是块内偏移量。
  • 在Unix 中，FCB第 0-9 个地址为直接地址，第10 个为一次间接地址，第11个地址为二次间接地址，第12个地址为三次间接地址。
  • 再将文件的逻辑块号转换为物理块号。使用多重索引结构，在索引节点中根据逻辑块号通过直接索引或间接索引找到对应的物理块号。
  • $\frac{9999}{1024}=9余783$，则逻辑块号为9，直接索引第9 个地址得到物理块号，块内偏移地址为783。
  • $\frac{18000}{1024}=17余592$ ，则逻辑块号为$10<17<10+256$，通过一次间接索引在第10个地址可得到物理块号，块内偏移地址为592
  • $\frac{420000}{1024}=410 余 160$ ，则逻辑块号为$10+256<410$ ，通过二次间接索引在第 11个地址可得到一次间址，再由此得到二次间址，再找到物理块号，其块内偏移地址160。

• 为了快速访问，又易于更新，当数据为以下形式时，应选用何种文件组织方式。

  • 不经常更新，经常随机访问
  • 经常更新，经常按一定顺序访问
  • 经常更新，经常随机访问

• 答案

  • 顺序结构
  • 索引顺序结构
  • 索引结构的组织方式

二、文件存储空间的管理

2.1 空闲表法和空闲链表法

1. 空闲表法

   1) 空闲表

   • 空闲表法属于连续分配方式，它与内存的动态分配方式雷同，它为每个文件分配一块连续的存储空间。即系统也为外存上的所有空闲区建立一张空闲表，每个空闲区对应于一个空闲表项。

   • 其中包括表项序号、该空闲区的第一个盘块号、该区的空闲盘块数等信息。再将所有空闲区按其起始盘块号递增的次序排列，形成空闲盘块表，如图8-9所示。

     

   2) 存储空间的分配与回收

   • 空闲盘区的分配与内存的分区(动态)分配类似，同样是采用首次适应算法和最佳适应算法等，它们对存储空间的利用率大体相当，都优于最坏适应算法。
   • 在系统为某新创建的文件分配空闲盘块时，先顺序地检索空闲表的各表项，直至找到第一个其大小能满足要求的空闲区，再将该盘区分配给用户(进程)，同时修改空闲表。

2. 空闲链表法

   1) 空闲盘块链

   • 这是将磁盘上的所有空闲空间以盘块为单位拉成一条链，其中的每一个盘块都有指向后继盘块的指针

   2) 空闲盘区链

   • 这是将磁盘上的所有空闲盘区(每个盘区可包含若干个盘块)拉成一条链。在每个盘区上除含有用于指示下一个空闲盘区的指针外，还应有能指明本盘区大小(盘块数)的信息。

2.2 位示图法

1. 位示图

   • 位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况。

   • 当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已分配。有的系统把“0”作为盘块已分配的标志，把“1”作为空闲标志。(它们在本质上是相同的，都是用一位的两种状态来标志空闲和已分配两种情况)

   • 磁盘上的所有盘块都有一个二进制位与之对应，这样，由所有盘块所对应的位构成一个集合，称为位示图。

     

2. 盘块的分配

   • 根据位示图进行盘块分配时，可分三步进行：

     (1) 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位(“0”表示空闲时)。

     (2) 将所找到的一个或一组二进制位转换成与之相应的盘块号。假定找到的其值为“0”的二进制位位于位示图的第i行、第j列，则其相应的盘块号应按下式计算：

     $$b = n(i - 1) + j$$
     • 式中，n代表每行的位数。

     (3) 修改位示图，令$map[i, j] = 1$。

3. 盘块的回收

   • 盘块的回收分两步：

     (1) 将回收盘块的盘块号转换成位示图中的行号和列号。转换公式为：

     $$i = (b - 1) \div n + 1$$

     　　　　

     $$j = (b - 1)\mod n + 1$$

     (2) 修改位示图。令$map[i, j] = 0$。

2.3 成组链接法

1. 空闲盘块的组织

   (1) 空闲盘块号栈，用来存放当前可用的一组空闲盘块的盘块号(最多含100个号)，以及栈中尚有的空闲盘块(号)数N。顺便指出，N还兼作栈顶指针用。

   (2) 文件区中的所有空闲盘块被分成若干个组

   • 比如，将每100个盘块作为一组。假定盘上共有10000个盘块，每块大小为1 KB，其中第201～7999号盘块用于存放文件，即作为文件区
   • 这样，该区的最末一组盘块号应为7901～7999；次末组为7801～7900，…，倒数第二组的盘块号为301～400；第一组为201～300，如图8-11所示。

   (3) 将每一组含有的盘块总数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)～S.free(99)中。这样，由各组的第一个盘块可链成一条链。

   

   (4) 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。

   (5) 最末一组只有99个盘块，其盘块号分别记入其前一组的S.free(1)～S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。

   • (注：最后一组的盘块数应为99，不应是100，因为这是指可供使用的空闲盘块。其编号应为(1～99)，0号中放空闲盘块链的结尾标志。)

2. 空闲盘块的分配与回收

   • 当系统要为用户分配文件所需的盘块时，须调用盘块分配过程来完成。
   • 该过程首先检查空闲盘块号栈是否上锁，如未上锁，便从栈顶取出一空闲盘块号，将与之对应的盘块分配给用户，然后将栈顶指针下移一格。
   • 若该盘块号已是栈底，即S.free(0)，这是当前栈中最后一个可分配的盘块号。

三、提高磁盘I/O速度的途径

(1) 改进文件的目录结构以及检索目录的方法来减少对目录的查找时间；

(2) 选取好的文件存储结构，以提高对文件的访问速度；

(3) 提高磁盘的I/O速度，能将文件中的数据快速地从磁盘传送到内存中，或者相反。

• 其中的第1和第2点已在上一章或本章作了较详细的阐述，本节主要对如何提高磁盘的I/O速度作一简单介绍。

3.1 磁盘高速缓存(Disk Cache)

• 在设计磁盘高速缓存时需要考虑的问题有：

  (1) 如何将磁盘高速缓存中的数据传送给请求进程

  (2) 采用什么样的置换策略；

  (3) 已修改的盘块数据在何时被写回磁盘。

1. 数据交付(Data Delivery)方式

   • 如果I/O请求所需要的数据能从磁盘高速缓存中获取，此时就需要将磁盘高速缓存中的数据传送给请求进程

   • 所谓的数据交付就是指将磁盘高速缓存中的数据传送给请求者进程。系统可以采取两种方式将数据交付给请求进程：

     (1) 数据交付

     (2) 指针交付

2. 置换算法

   • 现在不少系统在设计其高速缓存的置换算法时，除了考虑到最近最久未使用这一原则外，还考虑了以下几点：

   (1) 访问频率。

   (2) 可预见性。

   (3) 数据的一致性。

3. 周期性地写回磁盘

   • 还有一种情况值得注意，那就是根据LRU算法，那些经常要被访问的盘块数据可能会一直保留在高速缓存中，长期不会被写回磁盘。

3.2 提高磁盘I/O速度的其它方法

• 能有效地提高磁盘I/O速度的方法还有许多，如提前读、延迟写等，现介绍如下：

  1. 提前读
  2. 延迟写
  3. 优化物理块的分布

  4. 虚拟盘

     • 由于访问内存的速度远高于访问磁盘的速度，于是有人试图利用内存空间去仿真磁盘，形成所谓虚拟盘，又称为RAM盘。
     • 该盘的设备驱动程序也可以接受所有标准的磁盘操作，但这些操作的执行不是在磁盘上而是在内存中。这对用户都是透明的。

3.3 廉价磁盘冗余阵列(RAID)

1. 并行交叉存取

   • 这是把在大、中型机中，用于提高访问内存速度的并行交叉存取技术应用到磁盘存储系统中，以提高对磁盘的I/O速度。

   • 在该系统中，有多台磁盘驱动器，系统将每一盘块中的数据分为若干个子盘块数据，再把每一个子盘块的数据分别存储到各个不同磁盘中的相同位置上。以后当要将一个盘块的数据传送到内存时，采取并行传输方式，将各个盘块中的子盘块数据同时向内存中传输，从而使传输时间大大减少。

     

2.  RAID的分级

   • RAID在刚被推出时，是分成6级的，后来又增加了RAID 6级和RAID 7级。

     (1)  RAID 0级。

     (2)  RAID 1级。

     (3)  RAID 3级。

     (4)  RAID 5级。

     (5)  RAID 6级和RAID 7级。

3.  RAID的优点

   (1) 可靠性高，除了RAID 0级外，其余各级都采用了容错技术。当阵列中某一磁盘损坏时，并不会造成数据的丢失。此时可根据其它未损坏磁盘中的信息来恢复已损坏的盘中的信息。其可靠性比单台磁盘机高出一个数量级。

   (2) 磁盘I/O速度高，由于采取了并行交叉存取方式，可使磁盘I/O速度提高N-1倍。

   (3) 性能/价格比高，RAID的体积与具有相同容量和速度的大型磁盘系统相比，只是后者的1/3，价格也只是后者的1/3，且可靠性高。换言之，它仅以牺牲1/N的容量为代价，换取了高可靠性。

四、提高磁盘可靠性的技术

4.1 第一级容错技术SFT-Ⅰ

• 第一级容错技术(SFT-Ⅰ)是最基本的一种磁盘容错技术，主要用于防止因磁盘表面缺陷所造成的数据丢失。它包含双份目录、双份文件分配表及写后读校验等措施。

1. 双份目录和双份文件分配表

   • 在磁盘上存放的文件目录和文件分配表FAT，是文件管理所用的重要数据结构。
   • 为了防止这些表格被破坏，可在不同的磁盘上或在磁盘的不同区域中分别建立(双份)目录表和FAT。
   • 其中一份为主目录及主FAT，另一份为备份目录及备份FAT。一旦由于磁盘表面缺陷而造成主文件目录或主FAT的损坏时，系统便自动启用备份文件目录及备份FAT，从而可以保证磁盘上的数据仍是可访问的。

2. 热修复重定向和写后读校验

   • 由于磁盘价格昂贵，在磁盘表面有少量缺陷的情况下，则可采取某种补救措施后继续使用。一般主要采取以下两个补救措施：

     (1) 热修复重定向。

     • 建立热修复定向区，存放磁盘缺陷时待写数据

     (2) 写后读校验方式。

     • 每次写入磁盘后，立即读取校验。

4.2 第二级容错技术SFT-Ⅱ

1. 磁盘镜像(Disk Mirroring)

   • 为了避免磁盘驱动器发生故障而丢失数据，便增设了磁盘镜像功能。为实现该功能，须在同一磁盘控制器下，再增设一个完全相同的磁盘驱动器，如图8-13所示。

     

2. 磁盘双工(Disk Duplexing)

   • 如果控制这两台磁盘驱动器的磁盘控制器发生故障，或主机到磁盘控制器之间的通道发生故障，磁盘镜像功能便起不到数据保护的作用。

   • 因此，在第二级容错技术中，又增加了磁盘双工功能，即将两台磁盘驱动器分别接到两个磁盘控制器上，同样使这两台磁盘机镜像成对，如图8-14所示。

     

4.3 基于集群技术的容错功能

1. 双机热备份模式

   • 如图8-15所示，在这种模式的系统中，备有两台服务器，两者的处理能力通常是完全相同的，一台作为主服务器，另一台作为备份服务器。

     

2. 双机互为备份模式

   • 在双机互为备份模式中，平时，两台服务器均为在线服务器，它们各自完成自己的任务，例如，一台作为数据库服务器，另一台作为电子邮件服务器。

   • 为了实现两者互为备份的功能，在两台服务器之间，应通过某种专线将其连接起来。如果希望两台服务器之间能相距较远，最好利用FDDI单模光纤来连接两台服务器。在此情况下，最好再通过路由器将两台服务器互连起来，作为备份通信线路。图8-16示出了双机互为备份系统的情况。

     

3. 公用磁盘模式

   • 为了减少信息复制的开销，可以将多台计算机连接到一台公共的磁盘系统上去。该公共磁盘被划分为若干个卷。每台计算机使用一个卷。
   • 如果某台计算机发生故障，此时系统将重新进行配置，根据某种调度策略来选择另一台替代机器，后者对发生故障的机器的卷拥有所有权，从而可接替故障计算机所承担的任务。这种模式的优点是消除了信息的复制时间，因而减少了网络和服务器的开销。

4.4 后备系统

1. 磁带机

   • 它是最早作为计算机系统的外存储器。但由于它只适合存储顺序文件，故现在主要把它作为后备设备。磁盘机的主要优点是容量大，一般可达数GB至数十GB，且价格便宜，故在许多大、中型系统中都配置了磁带机
   • 其缺点是只能顺序存取且速度也较慢，为数百KB到数MB，为了将一个大容量磁盘上的数据拷贝到磁带上，需要花费很多时间。

2. 硬盘

   (1) 移动磁盘。

   (2) 固定硬盘驱动器。

   

3. 光盘驱动器

   • 光盘驱动器是现在最流行的多媒体设备，可将它们分为如下两类：

     (1) 只读光盘驱动器CD-ROM和DVD-ROM。

     (2) 可读写光盘驱动器。

五、数据一致性控制

• 在实际应用中，经常会在多个文件中都含有同一个数据。

• 所谓数据一致性问题是指，保存在多个文件中的同一数据，在任何情况下都必需能保证相同。

5.1 事务

1. 事务的定义

   • 事务是用于访问和修改各种数据项的一个程序单位。事务也可以被看做是一系列相关读和写操作。

2. 事务记录(Transaction Record)

   • 为了实现上述的原子修改，通常须借助于称为事务记录的数据结构来实现。这些数据结构被放在一个非常可靠的存储器(又称稳定存储器)中，用来记录在事务运行时数据项修改的全部信息，故又称为运行记录(Log)。

3. 恢复算法

   • 由于一组被事务Ti修改的数据以及它们被修改前和修改后的值都能在事务记录表中找到，因此，利用事务记录表系统能处理任何故障而不致使故障造成非易失性存储器中信息的丢失。恢复算法可利用以下两个过程:

     (1) undo〈Ti〉。该过程把所有被事务Ti修改过的数据恢复为修改前的值。

     (2) redo〈Ti〉。该过程能把所有被事务Ti修改过的数据设置为新值。

5.2 检查点

1. 检查点(Check Points)的作用

   • 如前所述，当系统发生故障时，必须去检查整个Log表，以确定哪些事务需要利用redo〈Ti〉过程去设置新值，而哪些事务又需要利用undo〈Ti〉过程去恢复数据的旧值。
   • 由于在系统中可能存在着许多并发执行的事务，因而在事务记录表中就会有许多事务执行操作的记录。随着时间的推移，记录的数据也会愈来愈多。因此，一旦系统发生故障，在事务记录表中的记录清理起来就非常费时。

2. 新的恢复算法

   • 在引入检查点后，可以大大减少恢复处理的开销。因为在发生故障后，并不需要对事务记录表中的所有事务记录进行处理，而只需对最后一个检查点之后的事务记录进行处理
   • 因此，恢复例程首先查找事务记录表，确定在最近检查点以前开始执行的最后的事务Ti。在找到这样的事务后，再返回去搜索事务记录表，便可找到第一个检查点记录，恢复例程便从该检查点开始返回搜索各个事务的记录，并利用redo和undo过程对它们进行处理。

5.3 并发控制(Concurrent Control)

1. 利用互斥锁实现“顺序性”

   • 实现顺序性的一种最简单的方法，是设置一种用于实现互斥的锁，简称为互斥锁(Exclusive Lock)。在利用互斥锁实现顺序性时，应为每一个共享对象设置一把互斥锁。
   • 当某一事务Ti要去访问某对象时，应先获得该对象的互斥锁。若成功，便用该锁将该对象锁住，于是事务T便可对该对象执行读或写操作；而其它事务由于未能获得该锁，因而不能访问该对象。如果Ti需要对一批对象进行访问，则为了保证事务操作的原子性，Ti应先获得这一批对象的互斥锁，以将这些对象全部锁住。

2. 利用互斥锁和共享锁实现顺序性

   • 利用互斥锁实现顺序性的方法简单易行。目前有不少系统都是采用这种方法来保证事务操作的顺序性，但这却存在着效率不高的问题。
   • 因为一个共享文件虽然只允许一个事务去写，但却允许多个事务同时去读；而在利用互斥锁来锁住文件后，则只允许一个事务去读。为了提高运行效率而又引入了另一种形式的锁——共享锁(Shared Lock)。
   • 共享锁与互斥锁的区别在于：互斥锁仅允许一个事务对相应对象执行读或写操作，而共享锁则允许多个事务对相应对象执行读操作，但不允许其中任何一个事务对对象执行写操作。

5.4 重复数据的数据一致性问题

1. 重复文件的一致性

   • 我们以UNIX类型的文件系统为例来说明如何保证重复文件的一致性问题。对于通常的UNIX文件目录，其每个目录项中含有一个ASCII码的文件名和一个索引结点号，后者指向一个索引结点。

   • 当有重复文件时，一个目录项可由一个文件名和若干个索引结点号组成，每个索引结点号都是指向各自的索引结点。图8-18示出了UNIX类型的目录和具有重复文件的目录。

     

2. 链接数一致性检查

   • 在UNIX类型的文件目录中，其每个目录项内都含有一个索引结点号，用于指向该文件的索引结点。对于一个共享文件，其索引结点号会在目录中出现多次。

六、典型例题

例题一、磁盘组织方式

• 设磁盘盘块的大小为1KB，对于540MB的硬盘，则其文件分配表需要占用多大的存储空间？当磁盘大小为1.2GB时，FAT需要占用多大的空间？

• 答案

  • 磁盘盘块个数为$540MB/1KB=540K，512KB<540KB<1024KB$,即需要20位的地址来表示这些盘块。20位地址占用的大小为$\frac{20}{8}=2.5B$，则FAT的大小为$2.5B\times40KB = 1350KB$
  • 磁盘盘块个数为$1.2GB/1KB=1.2M，1M<1.2M<2MB$,即需要21位的地址来表示这些盘块,但是为了方便管理，采用FAT的位数为24，所以FAT的大小为$1.2M\times4/8 B =3.6MB$。

例题二、文件系统

• 某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB，每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度4B，请回答下列问题。

  • 该文件系统能支持最大的文件长度是多少？
  • 文件系统用1M个簇存放文件索引节点，用512M个簇存放文件数据。若一个图像文件为5KB，则该文件系统最多存放多少个这样的图像文件？
  • 若文件A的大小为6KB,文件B的大小是40KB,则该文件系统获取A和B最后一个簇的簇号所需时间是否相同？为什么？

• 答案

  • 簇大小4KB,每个地址项长度为4B，则每个簇可以存放地址项数量为4KB/4B = 1024,则最大磁盘盘块数是$8+1024+10242+10243$。即系统支持最大的文件长度为$(8+1024+10242+10243)*4KB = 32KB+4MB+4GB+4TB$

  • 系统存放的索引节点数$1M\times4KB/64B = 64M$,5KB占用2个簇，512M个簇可以存放文件总个数是512M/2 =256M。但是表示的文件总个数受限于文件索引节点的总个数，故只能存放64M个5600B图像数据。

  • 文件A大小为6KB, 因为$6KB<8*4KB =32KB$,则可通过直接访问方式得到索引节点。而文件B大小为40KB，因为$32KB<40KB<32KB+1024*4KB$,故获取B的最后一个簇的簇号需要读取一级索引表，所以两者所需时间不相同。

     

本节结束 2019年10月7日

返回目录