第7章文件管理本章主要介绍OS如何通过文件系统来管理程序、数据等信息资源,具体包括文件和文件系统的基本概念、文件的逻辑结构和物理组织、文件存储空间的管理、目录的管理、文件的共享和保护以及数据一致性控制等内容。
7.1基本内容
7.1.1文件和文件系统
1.文件和文件系统
(1)文件:文件是一个具有符号名的一组相关联元素的有序序列。
(2)文件系统:操作系统中负责管理和存取文件信息的软件机构称为文件管理系统,简称文件系统。
它由三部分组成:
①与文件管理有关的软件;②被管理的文件;③实施文件管理所需的数据结构。
(3)文件系统的作用
① 从系统角度来看,文件系统是对文件存储器的存储空间进行组织和分配,负责文件的存储并对存入的文件进行保护和检索的系统。
② 从用户角度来看,文件系统实现了按名存取,并具有使用的方便性、数据的安全性和接口的统一性等特性。
2.文件的类型
(1)按性质和用途分类:系统文件;库文件;用户文件。
用户文件又可分为临时文件、档案文件和永久文件。
(2)按保护方式分类:只读文件;读写文件;不保护文件。
(3)按信息流向分类:输入文件;输出文件;输入输出文件。
(4)UNIX系统中的文件分类:普通文件(这种文件可以是系统文件、库文件、用户文件。);目录文件(目录文件是由文件目录组成的文件);特别文件(这类文件由I/0慢速字符设备构成)。
3.文件系统的基本功能
(1)文件的结构及有关存取方法。
(2)文件的目录机构和有关处理。
(3)文件存储空间的管理。
(4)文件的共享和存取控制。
(5)文件操作和使用。
7.1.2 文件的结构与存取设备
1.文件的结构,
(1)文件的逻辑结构文件的逻辑结构是呈现在用户面前的文件结构。可以分为两种:
①有结构的记录文件。它又分为两种:定长记录文件;变长记录文件。
②无结构的流式文件是有序字符的集合。文件长度为文件所包含的字符总数。
(2)文件的物理结构文件的物理结构是指逻辑文件在文件存储器上的存储结构。
为了有效地分配文件存储的空间,通常把它们分成若干块,并以块为单位进行分配和传送。每个块称为物理块,而块中的信息称为物理记录。物理块长通常是固定的。允许一个逻辑记录占用几块,也可以在一块中存放几个逻辑记录。
文件在逻辑上都可以看成是连续的,但在物理介质上存放时,却可以有多种形式。以下是几种基本的文件物理结构:
①连续结构:是将逻辑文件信息存放在文件存储器上相邻的物理块中。
连续结构的优点是结构简单,存取速度较快;缺点是建立文件时,要求给出文件的最大长度,且不便于增删,一般只能在末端进行。
②串联结构:也称为链接结构。其物理块可以不连续,也不必顺序排列;在每个物理块中设置一个指针(也称链接字),它指向该文件的下一个物理块号。
串联结构的优点是文件可动态增删,不必事先知道文件的最大长度p缺点是只适合顺序存取,必须从头开始查找,查找速度低,且因每块都要设置链接字,破坏了物理信息的完整性。
③索引结构:要求为每个文件建立一张索引表,其中每个表目指出文件逻辑记录所在的物理块号。索引表是由系统自动建立的。
索引结构的优点是有串联结构的所有优点,克服了它的缺点,可随机存取;缺点是增加了索引表的空间开销,增加了一次访问盘的操作而降低了丈件访问速度。
当文件很大时,文件的索引表也会很大。如果索引表的大小超过了一个物理块时,可以将索引表本身作为一个文件,再为其建立一个"索引表",这个"索引表"作为文件索引的索引,从而构成了二级索引。第一级索引表的表目指向第二级索引,第二级索引表的表目指向相应信息所在的物理块号。以此类推可再逐级建立索引,进而构成多级索引。
④Hash(散列)文件:是采用计算寻址结构,把链值通过某种计算处理,转换成相应记录的相应地址。计算寻址就是通过Hash函数计算后求得的地址。
Hash文件的优点是不需索引,节省查找时间;缺点是需要使用Hash(散列)函数计算。
2.文件的存取方法文件的存取方法是指读写文件存储器上的一个物理块的方法。
存取方法有三类:顺序存取法、直接存取法和按键存取法。
(1)顺序存取法严格按物理记录排列的顺序依次存取。
(2)直接存取法允许用户随意存取文件中的任何一个物理记录,而不管上次存取了哪一个记录。
(3)按键存取法实质上也是直接存取法,它不是根据记录编号或地址来存取的,而是根据文件中各记录内容进行存取的。
文件的物理结构密切依赖于文件存储器的特性和存取方法。
如果采用直接存取法,则索引文件效率最高,连续文件效率居中,串联文件效率最低。
3.文件存储设备文件的存储设备主要有磁带、磁盘、光盘等。由于存储设备的特性可以决定文件的存取方法,因此这里介绍以磁带为代表的顺序存储设备和以磁盘为代表的直接存储设备的特性,以及存储设备、文件物理结构与存取方法之间的关系。
（1）磁带：是一种典型的顺序存取设备,这种设备只有在前面的物理块被存取访问过之后,才能存取后续物理块的内容。由于磁带机的启动和停止都要花费一定的时间,因此在磁带的相邻物理块之间设计有一段间隙将它们隔开,如下所示:
磁 带
…
间隙
第i块
间隙
第i+1块
间隙
…
磁带的存取速度与信息密度(字符数/英寸〉、磁带带速(英寸/秒)和块间间隙有关。如果带速高,信息密度大且所需块间隙(磁头启动和停止时间〉小,则磁带存取速度高。反之,若磁带带速低,信息密度小且所需块间隙〈磁带启动和停止时间〉大,则磁带存取速度低。由于磁带读写时只有在第i块被存取之后,才能对第i+1块进行存取操作,因此,某个特定物理块的存取访问与该物理块到磁头当前位置的距离有很大关系。
（2）磁盘是典型的直接存取设备,这种设备允许文件系统直接存取磁盘上的任意物理块。磁盘机一般由若干磁盘片组成,可沿一个固定方向高速旋转。每个盘面对应一个磁头,磁臂可沿半径方向移动。磁盘上的一系列同心圆称为磁道,磁道沿径向又分成大小相等的多个扇区,与盘片中心有一定距离的所有磁道称为一个柱面。因此,磁盘上的每个物理块可用柱面号,磁头号和扇区号表示。
访问磁盘时间由三部分组成,即寻道时间、旋转延迟时间和传输时间,其中寻道自才间是指将磁头从当前位置移动到指定磁道所经历的时间,旋转延迟时间是指定扇区移动到磁头下面所经历的时间,传输时间是指将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间。
表7.1存取设备、存取方法和物理结构之间的关系存取设备
磁盘
磁带
物理结构
顺序结构
链接结构
索引结构
顺序结构
存取方法
直接或顺序
顺序
直接或顺序
顺序
文件长度
固定
可变、固定
可变、固定
固定
7.1.3文件目录管理
1.编排文件目录的原则
(1)系统中的文件种类繁多、数量庞大,为了使用户方便地找到文件,需要在系统中建立一套目录机构。
(2)编排目录的原则是,能够实现"按名存取",使查找文件准确、快速;解决命名的冲突及文件共享等问题。
2.文件控制块、目录项和索引结点为了能对一个文件进行正确的存取,必须为它设置用于描述和控制文件的数据结构,称之为"文件控制块(FCB)"。文件控制块中最基本的内容是文件名和文件的物理地址,其他的内容通常有文件的逻辑结构、文件的物理结构、文件的长度、文件的存取权限、文件的建立日期和时间、文件最后一次修改的臼期和时间、文件的连接计数及文件主的标识符等文件属性信息。
文件控制块与文件一一对应,并分别存放,我们将文件控制块的有序集合称作目录,而其中的每个文件控制块被称为目录项。目录通常也是以文件的方式存放在外存上,因此,也将它称为目录文件。
文件目录通常跟文件一起存放在外存上,当文件很多时,文件目录可能要占用大量的物理块。此时,在文件目录中查找一个指定的文件可能要多次启动外存,故十分费时。而在检索目录的过程中,实际上只用到了其中的文件名信息,仅当找到了匹配的目录项(即其中的文件名与指定的文件名相同)后,才需要从该目录项中读出该文件的物理地址等信息。
为此,有些系统,如UNIX系统,便采用把文件名和文件描述信息分开的办法,即将文件最描述信息单独形成一个称为索引结点的数据结构,存放在外存的索引结点区,而组成文件目录的目录项中仅有文件名和指向该文件所对应的索引绪点的指针。这样,便可大大减少一文件目录所占的物理块数,从而加快检索目录的速度。
3.目录结构目录结构是指文件目录的组织方式,它将直接关系到文件的存取速度以及文件的共享性和安全性。常用的目录结构有：
（1）单级目录结构单级目录结构是指在整个文件系统中只建立一张目录表,每个文件占其中的一个表项。
每当要建立一个新文件时,必须先检索所有的目录项,以保证新文件名在目录中是惟-的；然后再从目录表中找出一个空白目录项,填入新文件的文件名和其他说明信息。删除文件时,先从目录中找到该文件的目录项,然后再根据其中的物理地址回收外存空间,并清除该目录项。
单级目录的管理和实现十分简单。但它不能满足对目录管理的要求,例如它不允许文件重名,因此也不便于实现文件共享；而且,当文件数目较多时,它的检索速度会变得十分缓慢。
(2)两级目录结构为克服简单文件目录的缺点,可采用二级目录。二级目录由主目录表(MFD〉和用户文件目录表(UFD)组成。主目录表是管理用户目录表的总文件目录。用户文件目录表由各用户建立自己的名空间构成。二级目录的优点是解决了"重名"、"别名"问题,提高了查找速度,比一级目录快得多。
(3)多级目录结构为了进一步提高对目录的检索速度,使用户更加方便地组织和使用自己的文件,现代操作系统普遍使用多级目录结构(又称为树形目录结构)来进行文件管理。主目录在这里被称为根目录,数据文件被称为树叶,而其他的目录均作为树的结点。
通常,一个用户进程在一给定的时间内所访问的文件仅局限于某个文件目录之下。为了简化文件的查找过程,可将该文件目录设置成"当前目录"或"工作目录",以后用户进程对各文件的访问都可相对于"当前目录"而进行,而将当前目录到数据文件之间的所有目录文件名(不包括当前目录文件名)与数据文件名用"/"依次连接起来,便构成了文件的相对路径名。
4.文件目录项的组织和查询技术
（1）文件目录项的组织文件目录项的组织随系统而异。不同系统的文件目录项的组织如下：
①CP/M中的目录项：CP/M是一个早期的8位微机操作系统,该系统采用简单目录结构,其目录项包含文件名、文件类型、盘驱动器号、范围、磁盘块数和磁盘块号。
②MS -DOS中的目录项。MS -DOS采用树型目录结构。其目录项包含文件名、类型、属性、时间、日期、首簇号、文件长度。MS -DOS采用串联(链接〉结构,其第一个磁盘块的块号(称为首簇号〉放在目录项中,根据首簇号,按链接表(文件分配表FAT)可以找出该文件的所有块。
③UNIX中的目录项。UNIX中使用的目录结构非常简单,每个目录项仅包含一个文件名及其i节点号,而有关文件目录项中的其余文件结构信息、文件控制信息、文件管理等信息均放在i节点中。
（2）目录查询系统当用户要访问一个文件时,系统首先要利用用户提供的路径名对目录进行查询,只要找到对应的文件控制块或索引结点,便可找到具体的文件并对之进行相应的操作。在读/写文件前,必须先打开文件。打开文件时,操作系统利用用户给出的文件路径名到相应的目录项中查找该文件相关信息:文件结构信息、文件管理信息和文件控制信息。
7.1.4文件存储空间管理
1.存储空间管理程序应解决的几个问题一个大容量的文件存储器为系统本身和许多用户所共享。为方便用户"按名存取"所需之文件,系统应能自动为用户分配及管理系统和用户的存储空间。为此,应解决以下三个问题。、
(1)登记空闲区的分布情况。
(2)按需要给一个文件分配存储空间。
(3)收回不再需要保留的文件所占的存储空间。
以上问题都归结为盘空闲区的管理问题。
2.常用的盘空闲区管理方法
（1)空白文件目录盘空间上一个连续的未分配区域称为空白文件。系统为所有这些空白文件单独建立一个目录。对每个空白文件,在这个目录中建立一个表目。表目的内容包括第一个空白块地址(物理块号)、空白块个数等。在进行存储空间的分配时,同样可采用首次适应、最佳适应等算法；而回收时,同样要进行空闲区的合并。
这种方法的优点是空闲区的分配和回收都相当容易,但用来管理空闲区的空闲表需要占用大量的存储空间。
（2）空白块链该方法是将所有空白块用链接指针或索引结构把它们组成一个空白文件。释放和分配空白块都可以在链首进行,只需要修改几个有关的链接字。本方法只要求在主存中保存一个指针,令它指向第一个空白块。
这种方法的优点是实现简单;但工作效率低,因为每当在链上增加或移去空白块时需要对空白块链做较大的调整,因而会有较大的系统开销。
一种改进方法是将空白块分成若干组,再用指针将组与组链接起来,将这种管理空白块的方法称为成组链接法。这种成组链接法,在进行空白块的分配与回收时要比空白块链法节省时间。
（3）位示图法位示图是利用二进制的一位来表示文件存储空间中的一个块的使用情况。一个m行、n
列的位示图,可用来描述m×n块的文件存储空间,当行号、列号和块号都是从0开始编号时,第i行、第j列的二进制位对应的物理块号为i×n+j。如果"0"表示对应块空闲,"1"表示对应块己分配,则在进行存储空间的分配时,可顺序扫描位示图,从中找出一个或一组其值为"0"的二进制位,将对应的块分配出去,并将这些位置1；而在回收某个块时,只需找到对应的位,并将其值清0便可。
位示图法适合于所有的分配方式,它简单易行,而且位示图通常较小,故可将其读入内存,从而进一步加快文件存储空间分配和回收的速度。
（4)MS -DOS的盘空间管理
MS-DOS盘空间的分配采用文件分配表FAT;盘空间的分配单位称为簇(相当于块),簇的大小因盘而异,每个簇在FAT表中占一个项。FAT表是一个简单的线性表,它由若干项组成。FAT表的头两项用来标记盘的类型,其余的每个项包含三个十六进制的字符；若为000,表示空闲簇；FFF表示该簇是一个文件的最后一簇；若为其它任何十六进制字符,表示该簇是某一文件的下一簇号。
（5）UNIX文件存储空间的管理（成组链接法）
成组链接法是UNIX系统采用的空闲盘块管理方式。它将一个文件卷的所有空闲盘块按固定大小(如每组100块)分成若干组,并将每一组的盘块数和该组所有的盘块号记入前一组的最后一个盘块中,第一组的盘块数(可小于100)和该组所有的盘块号则记入超级块的空闲盘块号楼中。
当系统要为用户分配文件所需的盘块时,若第一组不只一块,则将超级块中的空闲盘块数减1,并将空闲盘块钱校顶的盘块分配出去:若第一组只剩一块且钱顶的盘块号不是结束标记0,则先将该块的内容(记录有下一组的盘块数和盘块号)读到超级块中,然后再将该块分配出去:否则,若楼顶的盘块号为结束标记0,则表示该磁盘上己无空闲盘块可供分配。
在系统回收空闲盘块时,若第一组不满1∞块,则只需将回收块的块号填入超级块的空闲盘块钱钱顶,并将其中的空闲盘块数加1:若第一组已有100块,则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中,然后将盘块数1和回收块的块号记入超级块中,值得注意的是,超级块中的空闲盘块钱是临界资源,对该校的操作必须互斥地进行,因此,系统为空闲盘块钱设置了一把锁,并通过上锁和解锁来实现对空闲盘块钱的互操作。
成组链接法除了第一组空闲盘块外,其余空闲盘块的登记不占额外的存储空间;而超级块(即文件卷的第1块)已在安装磁盘时拷入内存,因此,绝大部分的分配和回收工作可在国内存中进行,从而使之具有较高的效率。
7.1.5 文件的共享文件共享是指系统允许多个用户(进程)使用同一份文件。在允许文件共享的系统中,如果用户知道共享文件的路径名,并有访问该文件的权限,则可直接使用文件的路径名来访问该共享文件。为了使用户能更方便地共享文件,很多系统还允许一个共享文件同时出现在多个用户的目录下,这种共享可通过下述方法来实现。
1.目录结构中的共享在目录结构中,可以采用同名或异名的方式来实现文件的共享。这时文件系统的目录结构已不再是树型结构,而是一个有向的非循环图。异名共享所采用的方法称为文件的勾连。实现勾连的方法有两种：基于索引节点的共享和基于符号链的共享。
（1）基于索引结点的共享方式在文件的索引结点中设置一个链接计数字段,用来表示链接到本索引结点(亦即文件)上的用户目录项的数目。当用户C创建一个新文件时,其链接计数被置为1。如果用户B要共享该文件,则可在B的目录中增加一目录工页,并填上新的文件名和指向该共享文件的索引结点的指针,索引结点中的链接计数将被加1。
这种方式的缺点是文件主无法删除被他人共享的文件。如果C将共享文件删除并清除相应的索引结点,则B中将有一个指向无效索引结点的目录工页,若该索引结点以后被分配给另一个文件,则B将去共享一个错误的文件:如果C留下了索引结点,并将其链接计数减仁由于C是文件主,若系统要记账收费,C将继续为该文件付账,直至其他用户执行删除操作时,发现其链接计数为0,将其真正删除为止。
（2）利用符号链实现文件共享为了使B能共享C的一个文件,可以由系统为B建立一个类型为LINK的新文件,并把该文件放在B的目录下,在新文件中只包含了被链接文件的路径名。当B读该LINK类型的文件时,将被os截获,并根据新文件中的路径名去读那小文件。这种实现文件共享的方式叫做符号链接。在这种方式下,文件主删除被他人共享的文件后,其他用户再去访问该共享文件时,会因找不到文件而失败,于是可再将符号链(即LINK类型的文件)删除,此时不会造成任何影响。它的问题是其他用户访问共享文件时,必须根据路径中的分量名逐级地去检索目录,因此加大了访问文件的开销:另外,尽管LINK类型的文件十分简单,但仍需为它配置一个索引结点,飞并分配一个盘块来存放被链接文件的路径名,这同样会增加系统的的开销。符号链接有一个很大的优点,即只要简单地提供一个机器的网络地址以及文件在该机器中的文件路径名,便可链接全球任何一处机器上的文件。
2.打开支件结构中的共享文件目录结构中的共享是一种静态的共享。当多个用户同时打开某一文件对其访问时,将在内存中建立打开文件结构,这时的共享称为打开文件结构中的共享,这是一种动,态的共享。
文件系统中的打开文件结构由三部分组成z进程打开文件表、系统打开文件表和内存
Inode。
（1）父、子进程打开文件的共享父进程创建子进程时,除状态、标识以及与时间有关的少数控制项外,子进程基本上是复制父进程的所有信息。子进程与父进程可以共享父进程所打开的文件。父、子进程可以并发运行。它们也可以各自独立地打开文件,但这些各自独立打开的文件不能共享。
（2）同名或异名打开文件的共享不同进程通过同名或异名方式打开同一文件实现共享时,各进程使用各自的进程打开文件表和各自的名方式打开同一文件实现共享。
3.管道文件采用管道进行通信就像在两个进程之间架设了一个管道,一方能够将消息源源不断地写入管道,另一方连续从管道中将消息读出。它能够实现大量消息的通信。l
UNIX系统中,管道是一种特殊的文件,是一个特殊的打开文件,由三部分组成：一个外存索引节点、相应的内存索引节点和两个系统打开文件表。进程创建一个管道文件后,通常接着创建一个或几个子进程。管道文件实际上是一个临时文件,它以磁盘为中介实现进程间的通信。与内存相比,管道通信速度较慢,而且它只适用父、子进程之间的通信。管道文件能实现读写的同步和互斥。
7.1.6 文的存取控制系统中的文件既存在保护问题,又存在保密问题。所谓保护是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。所谓保密是指文件本身不得被未授权的用户访问。这两个问题都涉及用户对文件的访问权限,即文件的存取控制。
文件的保护机构应做到：
(1)防止未核准的用户存取文件;
(2)防止一个用户冒充另一个用户存取文件;
(3)防止核准用户〈包括文件主〉误用文件。
文件保护机构通常由存取控制验证模块来实现,其基本任务是:
(1)审定用户的存取权限;
(2)比较用户的存取权限和本次的存取要求;
(3)比较本次存取要求和被访问文件的存取保护信息。
以下介绍几种常用的文件存取控制方法。
1.存取控制矩阵存取控制矩阵是一个二维矩阵:一维列出系统中的所有用户z另一维列出系统中的全部文件。矩阵中的每个元素用来表示某一用户对某一文件的存取权限。
2.存取控制表由于存取控制矩阵是一个稀疏矩阵,浪费存储,因此,可为每一个文件建立一张存取控制表,仅存放与该文件有关的用户或用户组。
3.用户权限表与存取控制表相似,以用户或用户组为单位建立存取控制表,这样的表称为用户权限表。将一个用户或用户组所要存取的文件集中起来存入一张表中,其中每个表目指明用户(组)对相应文件的存取权限。
4.口令文件主在建立一个文件时,一方面进行口令登记,另一方面把口令告诉允许访问该文件的用户。访问该文件时首先核对口令,当口令正确时才允许访问,否则拒绝访问。本方法的优点是保护信息少,简单,易实现;缺点是保密性不强,且改换口令时需通知所有能访问该文件的用户。
5.密码文件写入时先进行编码F读出时要先译码再使用。只有掌握了译码方法的用户才能读出正确的信息。本方法保密性强,节省存储空间,但编码和译码都需大量的时间。
6.文件系统的安全性为了防止由于软、硬件故障而造成系统失败,保证被破坏了的文件能进行有效的恢复,系统应保存所有文件的双份拷贝。一旦一份拷贝被破坏,就可以使用另一份拷贝恢复系统。文件拷贝的方法有两种:一种是周期性的全量转存,另一种是增量转存。
文件系统和用户间的接口是通过系统调用实现的。一般文件系统为用户提供的系统调用主要有建立/删除、打开/关闭、读/写文件等。
7.1.7.文件的使用用户可通过文件系统所提供的命令和系统功能调用来实施对文件的操作。基本的文件操作有以下几种:
(1)创建文件。在创建一个新文件时,系统要为它分配必要的外存空间,并在文件系统的目录中,为它建立一个目录项,用来登记该文件的文件名及其在外存的地址等属性。
(2)删除文件。当不再使用某个文件时,可将它从文件系统中删除。此时,系统应先从目录中找到要删除文件的目录项,并根据其中的外存地址信息回收该文件所占的存储空间,
最后还必须释放它的目录项。
(3)读文件。当用户需要某个文件中的数据时,可将相应数据从外存读入内存。此时,系统同样要查找目录,找到指定文件的目录项,从中得到文件在外存中的地址信息,然后启动设备将数据读入内存。
(4)写文件。当用户要求添加或修改某个文件的内容时,可对它进行写操作。为此,也同样需要查找目录,找到指定文件的目录项,从中得到文件在外存中的地址信息,然后启动设备将数据写到相应的外存位置。
(5)设置文件的读/写指针。文件的读/写指针指出了要读/写的信息距离文件首字节的偏移量。在读/写文件时,将根据读/写指针和相应文件目录项中的外存地址信息计算出欲读/写的信息在外存中的地址。通过设置文件读/写指针的操作,可将读/写指针设置到文件的任一位置,从而实现对该文件内容的随机访问。
(6)打开文件。打开文件的主要功能是将指定文件的属性信息复制到内存中,并返回指向内存中的该文件属性信息的指针。以后,用户需要对该文件进行操作时,便可直接在内存中找到文件的外存地址等属性,从而显著地提高对文件的操作速度。
(7)关闭文件。当用户目前不再要求访问某个打开文件时,可对它进行关闭操作。此时,将从内存中删除指定文件的属性信息,如果其中的文件属性信息已被修改过,则还需将它写回外存。关闭文件后,若要再次访问该文件,则必须重新进行打开文件的操作。
7.2重点难点学习提示本章的目的是掌握文件系统的基本概念和实现过程,为此应对以下几个重点、难点问题作认真的学习,切实地掌握其基本内容。
1.顺序文件、索引文件和索引顺序文件根据用户和系统管理上的需要,可将有结构文件的记录组织成顺序文件、索引文件和--z
索引顺序文件三种形式。
(1)顺序文件：应了解如何对定长记录的顺序文件进行读/写操作,这种文件形式有何优缺点,它主要用于何种场合。
(2)索引文件：应能较好地理解为什么要引入索引文件,并能用图来说明索引文件的组形式,以及索引文件的优缺点。
(3)索引顺序文件：应了解索引顺序文件是为了解决什么样的问题而引入的,如何对索引顺序文件进行检索,当文件非常大时又应如何处理。
2.连续分配、链接分配和索引分配在为文件分配存储空间时,通常可采用连续分配、链接分配和索引分配三种方式。
(1)连续分配：应了解如何连续分配的文件进行顺序访问或随机访问,这种分配方式有何优缺点。
(2)链接分配：这是指为每个文件分配多个离散的盘块,并通过链接指针将它们链成个链表的分配方式。在学习时应较好地理解隐式链接分配方式是为了解决什么问题而引入;再的,它有何不足之处,而显式链接结构是如何解决上述不足的,它较适合用于哪种场合；并能用图来说明这两种分配方式是如何将多个离散的盘块链成一个链表的。
(3)索引分配：应能很好地掌握为什么要引入索引分配方式,采用索引分配方式时应如何对文件进行访问,当文件很大时又应如何处理。另外,还必须很好地了解和掌握混合索引分配方式是为了解决什么问题而引入的,此时,应如何将文件的逻辑地址转换成物理地址。
3.位示图法和成组链接法
(1)位示图法：应了解使用位示图如何来进行磁盘块的分配或回收,这种管理方式有何优点。
(2)成组链接法：应掌握它是如何将盘块进行分组并将各个盘块组链成一个成组链的,它应如何进行盘块的分配和回收,这种管理方式有什么优点。
4.目录管理必须对下述与目录管理有关的内容有较清晰的认识：
(1)文件控制块(FCB)：应了解FCB通常应包含哪些内容,它与文件之间存在着什么样的关系。
(2)索引结点：应理解磁盘索引结点是为了解决什么问题而引入的,它与FCB、目录项之间存在着什么样的关系。另外,还应了解为什么要引入内存索引结点,以及在内存索引结点中还应增加哪些数据项,原因是什么。
(3)单级目录和两级目录结构：应清楚地了解在单级目录结构中应如何创建或删除文件,它在哪些地方无法满足对目录管理的要求,而两级文件目录是如何解决这些问题的。
(4)多级目录结构：应很好地理解和掌握目录结构由单级发展为两级、并进一步发展为多级带来了哪些好处,应如何根据绝对路径名或相对路径名在多级目录结构中线性地检索一个文件或子目录,要创建或删除一个文件或子目录时应如何进行处理。
5.文件共享方式文件共享的主要目的:一是提高文件存储空间的利用率,二是方便用户对文件的使用，当前常用的文件共享方式有基于索引结点的共享方式和利用符号链实现文件共享两种。
(1)基于索引结点的共享方式：应了解如果不引入索引结点,而直接通过FCB来共享文件会产生什么问题,这种共享方式应如何进行文件的删除操作,它有何优缺点。
(2)利用符号链实现文件共享：应了解当用户访问LINK类型的文件时,系统应如何进行处理,通过这种方式共享文件有何优缺点。
7.3典型问题分析和解答
1.文件系统有哪些基本功能?
答:文件系统有以下基本功能：(1)文件的结构及有关的存取方法;（2）文件的目录结构及有关处理;(3)文件的存储空间管理;（4)文件共享的存取控制；(5)文件的操作和使用。
2.文件系统提供的基本操作都有哪些?
答:文件系统提供的基本操作有：(1)建立/删除文件；（2）打开/关闭文件;(3)读/写文件。
3.设某系统的磁盘有500块,块号为：0,1,2,3,…,499。
（1)若用位示图法管理这500块的盘空间,当字长为32位时,需要多少个字的位示图?
(2)第i字的第j位对应的块号是多少?（其中：i=0,1,2,…,j=0,1,2,3,…）
答:(1)位示图法就是在内存用一些字建立一张位示图,用其中的每一位表示一个盘块的使用情况,通常用"1"表示占用,"0"表示空闲。因此,本问题中位示图所占的字数为：
「500/32〡=16。
(2)第i字的第j位对应的块号N=32*i+j。
4.请分别解释在连续分配方式、隐式链接分配方式、显式链接分配方式和索引分配有式中如何将文件的字节偏移量3500转换为物理块号和块内位移量(设盘块大小为1KB,盘块号需占4个字节)。
答:首先,将字节偏移量35ω转换成逻辑块号和块内位移量:
3500/1024得到商为3,余数为428,即逻辑块号为3,块内位移量为428。
(1)在连续分配方式中,可从相应文件的FCB中得到分配给该文件的起始物理盘块号,例如a0,故字节偏移量3500相应的物理盘块号为aO+3,块内位移量为428。
(2)在隐式链接方式中,由于每个盘块中需留出4个字节(如最后的4个字节)来存放分配给文件的下一个盘块的块号,因此字节偏移量3500的逻辑块号为3500/1020的商3,而块内位移量为余数440。
从相应文件的FCB中可获得分配给该文件的首个(即第0个)盘块的块号,如bO；然后可通过读第bO块获得分配给文件的第1个盘块的块号,如b1再从b1块中得到第2块的块号,如b2;从b2块中得到第3块的块号,如b3。如此,便可得到字节偏移量3500对应的物理块号b3,而块内位移量则为440。
(3)在显式链接方式中,可从文件的FCB中得到分配给文件的首个盘块的块号,如c0;然后可在FAT的第cO项中得到分配给文件的第1个盘块的块号,如cl;再在FAT的第cl项中得到文件的第2个盘块的块号,如c2;在FAT的第c2项中得到文件的第3个盘块的块号,如c3。如此,便可获得字节偏移量3500对应的物理块号c3,而块内位移量则为428。
(4)在索引分配方式中,可从文件的FCB中得到索引表的地址。从索引表的第3项(距离索引表首字节12字节的位置)可获得字节偏移量3500对应的物理块号,而块内位移量为428。
5.假定一个当前含有100块的文件,如果
(1)在开头加入一块；
(2)在中间加入一块；
(3)在末端加入一块；
(4)在开头删除一块；
(5)在中间删除一块；
(6)在末端删除一块。
那么,使用毗连、链接和索引分配策略各涉及到多少次盘I/O操作?
解：它们所涉及的操作次数如下表所示。
表7.
序号
毗连
链接
索引
（1）
201
1
1
（2）
101
51
1
（3）
1
2
1
（4）
0
1
1
（5）
98
52
1
（6）
0
100
1
6.存放在某个磁盘上的文件系统,采用混合索引分配方式,其FCB中共有13个地址工页,第O-9个地址项为直接地址,第10个地址项为一次间接地址,第11个地址项为二次间接地址,第12个地址项为三次间接地址。如果每个盘块的大小为512字节,若盘块号需要用3个字节来描述,而每个盘块最多存放170个盘块地址:
(1)该文件系统允许文件的最大长度是多少?
(2)将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。
(3)假设某个文件的FCB己在内存,但其他信息均在外存,为了访问该文件中某个位置的内容,最少需要几次访问磁盘,最多需要几次访问磁盘?
分析：在混合索引分配方式中,FCB的直接地址中登记有分配给以件的前n块(第0到n-1块)的物理块号(n的大小由直接地址项数决定,本题中为10);一次间址中登记有一个一次间址块的块号,而在一次问址块中则登记有分配给文件的第n到第n+k-1块的块号(k的大小由盘块大小和盘块号的长度决定,本题中为170);二次间址中登记有一个二次问址块的块号,其中可给出k个一次间址块的块号,而这些一次间址块被用来登记分配给文件的第n+K块到第n+k+k^2-1块的块号;三次间址中则登记有一个三次间址块的块号,其中可给出k个二次间址块的块号,这些二次间址块又可给出k^2个一次问址块的块号,而这些一次间址块则被用来登记分配给文件的第n+k+k^2块n+k+k^2+k^3-1块的物理块号。
答:(1)该文件系统中一个文件的最大长度可达:
10+170+170×170+170×170×170=4942080块=4942080×512字节=247104OKB
(2)5000/512得到商为9,余数为392,即字节偏移量5000对应的逻辑块号为9,块内偏移量为392。由于9<10,故可直接从该文件的FCB的第9个地址项处得到物理盘块号,块内偏移量为392。
15000/512得到商为29,余数为152,即字节偏移量15000对应的逻辑块号为29,块内偏移量为152。由于10≤29<10+170,而29-10=19,故可从FCB的第10个地址项,即一次间址项中得到一次问址块的地址；并从一次间址块的第19项(即该块的第57—59这3个字节)中获得对应的物理盘块号,块内偏移量为152。
150000/512得到商为292,余数为496,即字节偏移量150000对应的逻辑块号为292,块内偏移量为496。由于10+170≤292<10+170+170×170,而292一(10+170)=112,112/170得到商为0,余数为112,故可从FCB的第11个地址项,即二次问址项中得到二次间址块的地址,并从二次间址块的第0项中获得一个一次间址块的地址,再从该一次间址块的第112项中获得对应的物理盘块号,块内偏移量为496。
(3)由于文件的FCB己在内存,为了访问文件中某个位置的内容,最少需要1次访问磁盘(即可通过直接地址直接读文件盘块),最多需要4次访问磁盘(第一次是读三次问址块,第二次是读二次间址块,第三次是读一次间址块,第四次是读文件盘块)。
7.有一磁盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有16个扇区。假定分配以扇区为单位,若使用位示图管理磁盘空间,问位示图需要占用多少空间?若空白文件目录的每个表目占用5个字节,问什么时候空白文件目录大于位示图?
分析：空白文件目录是管理磁盘空间的一种方法,该方法将文件存储设备上的每个连续空闲区看作一个空白文件。系统为所有空白文件单独建立一个目录,每个空白文件在这个目录中占一个农目。表目的内容至少包括第一个空白块的地址(物理块号)、空白块的数目。
位示图是另一种常用的管理磁盘空间的方法,该方法通过建立一张位示图来反映整个存储空间的分配情况。其中,每一个二进制位都对应一个物理块,当某位为1时表示该块已分配,当某位为0时表示该块空闲。
答:由题目所给条件可知,磁盘组扇区总数为:16×100×10=16000
因此,使用位示图描述扇区状态需要的位数为:16000位=2000字节又由题目所给条件可知,空白文件目录的每个表目占5个字节,由上述计算知位示图需要占2000字节,2000字节可存放表目数为:2000/5=400
所以当空白区数目大于400时,空白文件目录大于位示图。
8.在某个文件系统中,每个盘块为512字节,文件控制块占64个字节,其中文件名占8个字节也如果索引结点编号占2个字节,对一个存放在磁盘土的256个目录项的目录,试比较引入索引结点前后,为找到其中一个文件的FCB,平均启动磁盘的次数。
答:在引入索引结点前,每个目录项中存放的是对应文件的FCB,故256个目录项的目录总共需要占用256×64/12=32个盘块。因此,在该目录中检索到一个文件,平均启动磁盘次数为（1+32）/2=16.5。
在引入索引结点之后,每个目录项中只需存放文件名和索引结点的编号,因此256个目录项的目录总共需要占用256×(8+2)/512=5个盘块。因此,找到匹配的目录项平均需要启动。+5归,即3次磁盘:而得到索引结点编号后j还需启动磁盘将对应文件的索引结点读入内存,故平均需要启动磁盘4次。可见,引入索引结点后,可大大减少启动磁盘的次数,从而有效地提高检索文件的速度。
9.使用文件系统时,通常要显式地进行open、close操作。
(1)这样做的目的是什么?
(2)能否取消显式的open、close操作?应如何做?
(3)取消显式的open、close有什么不利?
答:(1)显式的open操作,即打开文件操作的基本功能是在用户进程和指名文件之间建立一条通路,它将相应文件的FCB读入内存,并返回给用户一个文件描述符,以后,用户对文件进行的任何操作,都只需使用文件描述符而非路径名,而系统则无需再对各级目录进行检索,便可通过文件描述符直接找到内存中的文件FCB,然后为用户进行相应的操作。可见,open操作的主要目的是提高对文件访问的速度。显式的close操作,即关闭文件操作的基本功能是切断用户进程和指定文件间的通路,如果文件FCB的内容被修改过,则需要将它写回磁盘,然后释放内存FCB和文件描述符。
(2)可以取消显式的open和close操作。具体做法是:在首次使用某个文件时,由系统自动打开该文件,并在相关作业终止时自动关闭该文件:或者干脆取消open和dose操作,而在每次读写文件时,都通过路径名来检索目录,然后再进行相应操作。
(3)取消显式的open与close操作将增加系统的开销。首先,用户每次使用路径名来读写文件时,系统都必须检查该文件是否EA经打开:其次,当一个文件使用完毕后,只要相应的作业没终止,则它的FCB将仍然占用内存资源,这不仅是对资源的浪费,而且还有可能造成其他文件因得不到该资源而无法打开的现象。如果,每次对文件操作前,都必须先通过路径名到外存上去检索目录,则开销会更大。
10.考虑这样一个文件系统,其中文件可被删除,并且在指向它的链路仍然存在的情况下可重新使用其盘空间.若在同一盘空间建立一新文件,将会出现什么问题?如何避免该问题?
答:令F1是老文件,F2是新文件,那么,希望通过现有链路访问文件Fl的用户实际上访问的是文件F2；这里使用的是对文件Fl的存取保护而不是与文件F2相关的存储保护。采用删除指向一个已删除文件的所有链路的方法可避免该问题。这可用几种方式实现:
(1)保留一张记录指向一个文件的所有链路的表,当删除该文件时,就删除这些链路；
(2)保留这些链路,当试图访问一个已删除的文件时,就删去相应的链路；
(3)保留一个文件访问表,仅当对某文件的访问被删除后或所有链路都被删除之后才删除文件访问表中的相应文件。
11.在许多系统中,一个授权的用户可像对通常的文件那样读、写子目录。
(1)这样做会出现什么保护问题?
(2)试提出一个处理这些问题的方案。
答：(1)保存在目录项目中的信息之一是文件位置，如果用户可以修改这个位置信息,那么,他也会访问其他文件,从而违犯了存取保护的规定。
(2)不允许用户直接向子目录写人信息,而应提供系统操作来完成这些事情。
12.能否用一个可使用任意长度文件名的单级目录结构来模拟多级目录结构?若能,则说明如何模拟？如果文件名限制为7个字符,你的方案应作哪些修改?
答：如果允许使用任意长的名字,则可模拟多级目录结构.例如,可用符号"."指明子目录的结束.这样,名字h.lisp.Fl指明Fl是子目录lisp中的文件,而lisp是根目录h的文件。
若名字限制为7个字符,那么上面的方案可能无用.一个变通的方案是使用一个特定的文件作为符号表(目录).它将随意长的文件名(如h.lisp.Fl)映射为较短的文件名(如XX00101),然后将后者作为实际的文件名来使用。
13.信息在外存空间的排列方式也会影响存取等待时间。考虑几个逻辑记录A、B、C、…、J,它们被存放于磁盘上,每个磁道存放10个记录,安排如下：
物理块
1
2
3
4
5
6
7
8
9
10
逻辑记录
A
B
C
D
E
F
G
H
I
J
假定要经常顺序处理这些记录,旋转速度为2Oms/转,处理程序读出每个记录后花4ms
进行处理,试问:
(1)处理的总时间为多少?
(2)考虑对信息的分布进行优化,信息分布优化后,处理的总时间为多少?
物理块
1
2
3
4
5
6
7
8
9
10
逻辑记录
A
H
E
B
I
F
C
J
G
D
答:在本题中,设备旋转速度为20ms/转,每道存放10个记录,因此读出1个记录的时间是:20/10=2ms
(1)对于第一种记录分布情况,读出并处理记录A需要6ms,则此时读写头已转到了记录D的开始处,因此为了读出记录B,必须再转一圈少两个记录(从记录D到记录B)。后续8个记录的读取及处理与此相同,但最后一个记录的读取与处理只需6ms。于是,处理10个记录的总时间为:9×(2+4+16)+(2+4)=204ms
(2)对于第二种记录分布情况,读出并处理记录A后,读写头刚好转到记录B的开始处,因此立即就可读出并处理,后续记录的读取与处理情况相同。故处理10个记录的总时间为:
10×(2+4)=6Oms
14.有一个交叉存放信息的磁盘,信息在其上的存放方法如图7.8所示。每磁道有8个扇区,每扇区512字节,旋转速度为3000转/分。假定磁头已在要读取信息的磁道上,0扇区转到磁头下需要1/2转,且设备对应的控制器不能同时进行输入/输出,在数据从控制器传送至内存的这段时间内,从磁头下通过的扇区数为2,问依次读出一个磁道上的所有扇区需要多少时间?其数据传输速度为多少?
分析：在磁盘数据的读取过程中,当控制器将整块信息从设备读入其内部缓冲区后,再将缓冲区中的数据传送至内存。在数据从控制器传送至内存的同时,后续扇区中的数据将从磁头下通过并传输到控制器。但某些简单的控制器不能同时进行输入/输出,因此在数据从控制器传送至内存的这段时间内,从磁头下通过的扇区信息丢失。为此,应将数据以交叉方式存放,信息块应间隔的扇区数与控制器传输信息至内存的速度相关。
答:从图7.8可知,信息块之间的间隔为2个扇区。
由题目所给条件可知,旋转速度为:3000转/分=50转/秒,即2Oms/转。
读一个扇区需要时间:20/8=2.5ms
读一个扇区并将扇区数据送入内存需要时间:2.5×3=75ms
读出一个磁道上的所有扇区需要时间:20/2+8×75=7Oms=0.07s
每磁道数据量:8×512=4KB
数据传输速度为:4KB/0.07=57.lKB/秒所以,依次读出一个磁道上的所有扇区需要0.07秒。其数据传输速度为57.1KB/秒。
15.有一文件系统如图7.10(a)所示。图中的框表示目录,圈表示普通文件。根目录常驻内存,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2个字节,共4个字节).若下级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512字节,与普通文件的一页等长。
(a)
该文件的有关描述信息
磁盘地址
磁盘地址
磁盘地址
︰
磁盘地址
磁盘地址
磁盘地址
（b）
图7.10 文件系统结构示意图及普通文件的控制块组织普通文件的文件控制块组织如图110(b〉所示。其中,每个磁盘地址占2个字节,前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文件页地址:第12个地址指示二级索引表地址,二级索引表中每个地址指示一个一级索引表地址:第13个地址指示三级索引表地址,三级索引表中每个地址指示一个二级索引表地址。
(1)一个普通文件最多可有多少个文件页?
(2)若要读文件J中某一页,最多启动磁盘多少次?
(3)若要读文件W中的某一页,最少启动磁盘多少次?
(4)就(3〉而言,为最大限度减少启动磁盘的次数,可采用什么方法?此时,磁盘最多启动多少次?
答:(1)由题目中所给条件可知,磁盘块大小为512字节,每个磁盘地址占2个字节。因此,一个一级索引表可容纳256个磁盘地址。同样地,一个二级索引表可容纳256个一级索引表地址,一个三级索引表可容纳256个二级索引表地址。这样,一个普通文件最多可有页数为：
10+256+256×256+256×256×256=16843018
(2)从图7.10(a)中可以看出,目录文件A和目录文件D中,目录项都只有两个,因此这两个目录文件都不需拉链。若要读文件J中的某一页,首先从内存的根目录中找到目录文件A的磁盘地址,将其读入内存(第1次访问磁盘)。然后再从目录A中找出目录文件D的磁盘地址,并将其读入内存(第2次访问磁盘〉。从目录D中找出文件J的文件控制块地址,将文件J的文件控制块读入内存(第3次访问磁盘〉。在最坏情况下,要访问页的磁盘地址需通过三级索引才能找到,这时要三次访问磁盘才能将三级索引表读入内存(第4、5、6次访问磁盘〉。最后读入文件J中的相应页〈第7次访问磁盘〉。
由此可知,若要读文件J中的某一页,最多启动磁盘7次。
(3)从图7.10(a〉中可以看出,目录文件C和目录文件U中,目录项数目较多,若目录项数超过127(512/4一1=127),则目录文件的读入可能需要多次磁盘读(因目录文件组织成链接文件)。在最好情况下,所找的目录项都在目录文件的第一个磁盘块中。若要读文件W中的某一页,首先从内存的根目录中找到目录文件C的磁盘地址,将其读入内存(第1次访问磁盘〉。在最好情况下,能从目录C的第一个磁盘块中找出目录文件I的磁盘地址,并将其读入内存(第2次访问磁盘〉。从目录I中找出目录文件P的的磁盘地址,将其读入内存〈第3次访问磁盘〉。从目录P中找到目录文件U的磁盘地址,将其读入内存(第4次访问磁盘〉。在最好情况下,能从目录U的第一个磁盘块中找出文件W的文件控制块地址,将文件W的文件控制块读入内存(第5次访问磁盘〉。在最好情况下,要访问的页在前10页中,这时可直接得到该页的磁盘地址。最后读入文件W中的相应页(第6次访问磁盘〉。
由此可知,若要读文件W中的某一页,最少启动磁盘6次。
(4)由于通过文件控制块访问文件所需的访问磁盘次数无法改变,要减少访问磁盘的次数,只有通过减少访问目录文件的次数来达到。为最大限度地减少启动磁盘的次数,可以将文件W直接链接在根目录的最左端(或其目录项在根目录的前127个项内〉。这样,若要读文件W中的某页时,首先从内存的根目录中找到文件W的文件控制块地址,将文件W的文件控制块读入内存〈第1次访问磁盘)。在最坏情况下,要访问页的磁盘地址需通过三级索引才能找到,这时要三次访问磁盘才能将三级索引表读入内存(第二3、4次访问磁盘〉。最后读入文件W中的相应页(第5次访问磁盘〉。
由此可知,若将文件W直接链接在根目录的最左端,要读文件J中的某一页,最多启动磁盘5次。
7.4习题
7.4.1 基本题
一．判断题(正确的在括号中记√,错误的记×)
1.如果用户极其频繁地访问其当前目录中的文件,那么应将该目录放在内存。 ( )
2,打开文件操作的目的是建立用户和文件的联系。 （ ）
3.连续文件的缺点之一是不便于扩充。 ( )
4.文件保护就是禁止对文件的进行存取。 （ ）
5.树结构目录的层次和隶属关系清晰,有利于文件和目录的共享。 ( )
6.多重索引结构适合于有大量大文件的系统。 ( )
7.隐式链接结构可以提高文件存储空间的利用率,但不适合文件的随机存取。 ( )
8.访问控制矩阵比访问控制表更节约空间。 ( )
9.对物理文件来说,顺序文件必须采用连续分配方式,而链接文件和索引文件可采用离散分配方式。 ( )
10.文件系统中,所有文件的目录信息集中存放在内存的一个特定区域中。 ( )
二.单项选择题
1.文件系统是指___________。
A.文件的集合 B.文件的目录
C.实现文件管理的一组软件 D.文件、管理文件的软件及数据结构的总体
2.按逻辑结构可把文件分为记录式文件和________两类。
A.读、写文件 B.只读文件 C.索引文件 D.流式文件
3.文件系统中文件存储空间的分配是以_______为单位进行的。
A.字 B.块 C.字节 D.文件
4.从用户角度看,引入文件系统的主要目的是_______。
A.实现虚拟存储 B.保存系统文档
C.实现对文件的按名存取 D,保存用户和系统文档
5.一个文件系统采用二级目录结构,它的两张目录分别是__________。
A.系统目录和子目录 B.根目录和子目录
C.主目录和用户目录 D.用户目录和子目录
6、Hash文件采用的寻址方法是________。
A.计算 B.比较 C.索引 D.顺序
7.文件系统中用__________管理文件。
A.作业控制块 B.外页表 C.目录 D.软硬件结合的方法
8.可以解决文件重名问题的最简单的文件目录结构是______。
A.单级目录 B.树型结构目录 C.二级目录 D.便于共享的目录
9.为了对文件系统中的文件进行安全管理,任何一个用户在进入系统时都必须进行注册,这一级安全管理是_________安全管理。
A.系统级 B.目录级 C.用户级 D.文件级
10、可以实现文件保护的方案是_______。
A.用户权限表 B.在段中设置段长 C.删除文件 D.使用界限寄存器
11.为了解决不同用户文件的"命名冲突"问题,通常在文件系统中采用______。
A.约定的方法 B.多级目录 C.路径 D.索引
12.一个文件的绝对路径名是从_________开始,逐步沿着每一级子目录向下追溯,最后到指定文件的整个通路上所有子目录名组成的一个字符串。
A.当前目录 B.根目录 C.多级目录 D.二级目录
13.空白文件目录法用于______________。
A.主存空间的管理 B.文件存储空间的管理
C.虚存空间的管理 D.外设的分配与回收
14.对一个文件的访问,常由________共同限制。
A.用户访问权限和文件属性 B.用户访问权限和用户优先级
C.优先级和文件属性 D.文件属性和口令
15.使用文件前必须先_________文件。
A.命名 B.建立 C.打开 D.备份
16.文件使用完毕后应该________。
A.释放 B.关闭 C.卸下 D.备份答,B
17.一般来说,文件名及属性可以收纳在__________中以便查找。
A.目录 B.索引 C.字典 D.作业控制块
18.最常用的流式文件是字符流文件,它可看成是________的集合。
A.字符序列 B.数据 C.记录 D.页面
19.在文件系统中,文件的不同物理结构有不同的优缺点。在下列文件的物理结构中,_____不具有直接读写文件任意一个记录的能力。
A.顺序结构 B.链接结构 C.索引结构 D.Hash结构
20.在下列文件的物理结构中,_______不利于文件长度动态增长。
A.顺序结构 B.链接结构 C.索引结构 D.Hash结构
21.如果文件采用直接存取方式且文件大小不固定,则宜选择________文件结构。
A.直接 B.顺序 C.随机 D.索引
22.文件系统采用二级目录结构,这样可以__________。
A.缩短访问文件存储器时间 B.实现文件共享
C.节省主存空间 D.解决不同用户之间的文件名冲突问题三．填空题
1.组织目录时可采取的数据结构有________、______、______、____和______。
2.利用Hash法查找文件时,如果目录中相应的目录项是空,则表示_________;如果目录项中的。文件名与指定的文件名相匹配,则表示_______;如果目录项中的文件名与指定的文件名不匹配,则表示______________。
3.分配磁盘空间的三种主要方法是______、_______和__________。
4.在文件系统中是利用______来管理文件的,为了允许不同用户的文件使用相同的文件名,通常文件系统中采用______;在目录文件中的每个目录项通常就是_______。
5.毗连文件分配空间中常用的适配方法是________、________和__________。
6.在下列物理文件中,_______将使文件顺序访问的速度最快;_________最不适合对文件进行随机访问;____________能直接将记录键值转换成物理地址。
7.目录上的主要操作有______、_____、_____、_____和______。
8.文件系统最基本的目标是_________,它主要是通过__________功能实现的,文件系统所追求的最重要的目标是_______________。
9．基于磁盘文件模式,将文件视为编上号的块的文件存取方法称为_______。
10.在文件系统中可命名的最小数据单位是_________,用户以________为单位对文件进行存取、检索等,对文件存储空间的分配则以_________为单位。
11.二级目录结构由_______目录和各用户自己的__________目录组成.
12.索引文件大体上由______区和______区构成。其中______区一般按关键字的顺序存放。
13.对操作系统而言,打开文件广义指令的主要作用是装入_____目录表。
14.操作系统实现按名存取进行检索等关键在于解决文件名与______的转换。
15.文件的物理组织有顺序、_____和索引。
16._______是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。
17.磁盘与主机之间传递数据是以_____为单位进行的。
18.在文件系统中,要求物理块必须连续的物理文件是_______。
19.文件系统为每个文件另建立一张指示逻辑记录和物理块之间的对应关系表,由此表和文件本身构成的文件是_______。
20.______算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象.
21.访问磁盘时间由三部分组成,即_____、_________和 __________。
22.文件的结构就是文件的组织形式,从用户观点出发所看到的文件组织形式称为文件的________;从实现观点出发,文件在外存上的存放组织形式称为文件的_________。
四．简答题
1.什么是文件、文件东统?文件系统有哪些功能?
2.什么是文件的逻辑结构?什么是记录?
3.文件的物理结构有哪几种?为什么说串联文件结构不适于随机存取?
4.什么是文件系统?通常由哪几部分组成?
5.设置文件目录的目的是什么？
6.文件的逻辑结构与物理结构有何不同?
7.考虑一个支持毗连、链接和索引分配策略的系统,对一给定文件,决定采用每种策略时的条件是什么?
8.假定一系统中,自由空间通过自由空间表管理:
(1)如果指向该自由空间表的指针丢失了,那么,系统能否重构该自由空间表?
(2)提出一种不因内存故障而丢失该指针的方案。
9.当用户自愿撤离或终止一个作业时,某些系统自动删除所有相关的文件,除非用户明显地请求保留它们:而另一些系统则保留所有文件,除非用户明显的请求删除它们；试叙述这两种途径的特点。
10.文件一般按什么分类?可以分为哪儿类?
11.什么是文件目录?文件目录中包含哪些信息?
12.二级目录和多级目录的好处是什么?符号文件目录表和基本文件目录表是二级目录吗?
13.有些系统通过保留文件的单一副本来提供文件共享,有些系统则通过对每一共享文件的用户各保留一个副本的方式来提供文件共享,试叙述它们各自的优缺点。
论述题：
1.什么是文件?它包含哪些内容及特点?
2.文件系统要解决哪些问题?
3.文件系统中常采用的物理结构有哪些?
4.试述文件管理系统设置打开文件、关闭文件命令的原因。
5.常用的文件存储设备的管理才法有哪些?试述主要优缺点。
6.试述成组链法的基本原理,并描述成组链法的分配与释放过程。
7.删除文件时,存放文件的盘块常常返回到空闲盘块链中,有些系统同时清除盘块中的内容,而另一些系统则不清除,请对这两种方式加以比较。
8.在树形目录结构中,利用链接方式共享文件有何好处?
9.文件存取控制方式有哪几种?试比较它们各自的优缺点。
10.假定磁带记录密度为每英寸800字符,每一逻辑记录为160个字符,块间隙为0.6英寸。今有1500个逻辑记录需要存储,试计算磁带利用率?若要使磁带空间利用率不少于50%,至少应以多少个逻辑记录为一组?
11.设磁盘组共有n个柱面,编号顺序为0、1、2、…、n一1;共有m个磁头,编号顺序为0、1、2、…、m一1;每个磁道内的k个信息块从1开始编号,依次为1、2、…、k。现用x表示逻辑磁盘块号,用a、b、c分别表示任一逻辑磁盘块的柱面号、磁头号、磁道内块号,则x与a、b、c可通过如下公式进行转换:
x=k×m×a+k×b+c
a =(x-1〉DIV (k×m)
b=((x-1〉MOD (k×m)) DIV K
c =((x-1) MOD k×m)）MOD K+1
若某磁盘组为n=200,m=20,K=10,问:
(1)柱面号为185,磁头号为12,道内块号为5的磁盘块的逻辑磁盘块号为多少?
(2)逻辑磁盘块号为1200,它所对应的柱面号、磁头号及磁道内块号为多少?
(3)若每一磁道内的信息块从0开始编号,依次为0、1、…、k-1,其余均同题设,试写出x与a、b、c之间的转换公式。
12.假定磁盘块的大小为lk,对于540M的硬盘,其文件分配表FAT需要占用多少存储空间?当硬盘容量为1.2G时,FAT需要占用多少空间?
13.如磁盘的每个磁道分成9个块,现有一文件共有A、B、…、I 9个记录,每个记录的大小与块的大小相等,设磁盘转速为27ms/转,每读出一块后需要2ms的处理时间。若忽略其他辅助时间,试问:
(1〉如果顺序存放这些记录并顺序读取,处理该文件要多少时间?
(2〉如果要顺序读取该文件,记录如何存放处理时间最短?
14.有一计算机系统利用图7.9所示的位示图(行号、列号都从0开始编号)来管理空闲盘块。如果盘块从1开始编号,每个盘块的大小为1KB。
(1)现要为文件分配两个盘块二试具体说明分配过程。
(2)若要释放磁盘的第300块,应如何处理?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
1
2
3
4
5
6
图7.9位示图
15.许多操作系统中提供了文件重命名功能,它能赋予文件一个新名字。若进行文件复制,并给复制文件起一个新名字,然后删除旧文件,也能达到给文件重命名的目的。试问这两种方法在实现上有何不同?
16.某软盘有40个磁道,磁头从一个磁道移至另一磁道需要6ms。文件在磁盘上非连续存放,逻辑上相邻数据块的平均距离为13磁道,每块的旋转延迟时间及传输时间分别为100ms、25ms,问读取一个100块的文件需要多少时间?如果系统对磁盘进行了整理,让同一文件的磁盘块尽可能靠拢,从而使逻辑上相邻数据块的平均距离降为2磁道,这时读取一个100块的文件需要多少时间?
17.一个树形结构的文件系统如图7.9所示:
该图中的框表示目录,圈表示文件。
(1)可否进行下列操作:
a.在目录D中建立一个文件,取名为A。
b.将目录C改名为A。
(2)若E和G分别为两个用户的目录:
a.用户E欲共享文件Q,应有什么条件,如何操作?
b.在一段时间内,用户G主要使用文件S和T。为简便操作和提高速度,应如何处理?
c.用户E欲对文件I加以保护,不许别人使用,能否实现?如何实现?
图7.9 文件系统结构示意图
18.使用文件系统时,通常要显式地进行OPEN,CLOSE操作。
〈1〉这样做的目的是什么?
〈2〉能否取消显式的OPEN,CLOSE操作?应如何做?
〈3〉取消显式的OPEN,CLOSE操作有什么不利?
6.4自测练习答案一．判断题
1.√ 2,√ 3,4.× 5,× 6.× 7,√ 8,× 9,√ 10,×
二．选择题
1.D 2.D 3.B 4.C 5.C 6.A 7.C 8.C 9.A 10.A 11.B
12.B 13.B 14.A 15.C 16.B 17.A 18.A 19.B 20.A 21.D 22.D
三．填空
1.线性表 链接表 排序表 链接二叉树 杂凑表
2.系统中无指定文件名 找到了指定文件 发生了冲突
3.毗连分配 链接分配 索引分配
4.目录 多级目录 FCB
5.首次适配 最佳适配 最差适配
6.顺序文件 隐式链接文件 直接文件
7.查找文件 创建文件 删除文件 列文件名 复制文件
8.按名存取 目录管理 提高对文件的存取速度
9.随机存取方法.
10,数据项 记录 文件
11.主文件目录 用户文件目录组成
12.索引 数据 索引
13.文件
14.文件的存储地址
15.链接
16.文件保护
17.数据块
18.顺序文件
19.索引文件
20.最短寻道时间优先
21.寻道时间 旋转延迟时间 传输时间
22.逻辑结构 物理结构四、简答题
1.答:在计算机系统中,文件被解释为一组赋名的相关字符流的集合,或者是相关记录的集合。
文件系统是操作系统中与管理文件有关的软件和数据。
文件系统的功能是为用户建立文件,撤销、读写修改和复制文件,以及完成对文件的按名存取和进行存取控制。
2.答:文件的逻辑结构就是用户可见的结构,可分为字符流式的无结构文件和记录式的有结构文件两大类。
记录是一个具有特定意义的信息单位,它由该记录在文件中的逻辑地址(相对位置)与记录名所对应的一组关键字,属性及其属性值所组成。
3.答:文件的物理结构是指文件在存储设备上的存放方法。常用的文件物理结构有连续t
文件,串联文件和索引文件3种。
串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系,链接成一个串联队列。搜索时只能按队列中的串联指针顺序搜索,存取方法应该是顺序存取的。否则,为了读取某个信息块而造成的磁头大幅度移动将花去较多的时间。因此,串联文件结构不适于随机存取。
4.答:文件系统即文件管理系统,它在操作系统中是负责管理和存取文件信息的软件。通常它由三部分组成：（1）与文件管理有关的软件;(2)被管理的文件;(3)实施文件管理所需的数据结构。
5.答：由于文件系统中文件的种类多、数量大，所以设置文件目录的目的是为了便于查找文件、操作文件、共享文件及保护文件。
文件目录组织有三种形式:（1）简单（一级）目录；（2）二级目录；（3）树型目录。
6.答:文件的逻辑结构是文件在用户面前所呈现的形式。文件的物理结构,是文件在文件存储器上的存放形式。
7.答。采用毗连分配策略的条件是,对文件的访问通常是顺序的,而且文件比较小；
采用链接分配策略的条件是,文件较大且通常是顺序访问的；
采用索引分配策略的条件是,文件较大并通常是随机访问的。
8.答(1)为了重构自由空间表,必须执行"无用单元收集程序"。这需要查寻整个目录结构以判定哪些页面已分配给作业,而将那些未被分配的页面重新链结为一个自由空间表。
(2)可将自由空间表指针存取在磁盘上。
9.答:对于前一种途径,由于不必保留不(再)需要的文件,可使每一用户所需的文件空间变成最小.后一种途径则对用户更为安全,因为用户不会由于疏忽没有保存文件而使文件丢失。
10.答:文件系统一般按性质,用途,组织形式,文件中的信息流向或文件的保护级别等分类。
按文件的性质与用途可以分为系统文件,库文件和用户文件。按文件的组织形式可以分为普通文件,目录文件和特殊文件。按文件中的信息流向可以分为输入文件,输出文件和输入/输出文件。按文件的保护级别可以分为只读文件,读写文件,可执行文件和不保护文件。
11.答:一个文件的文件名和对该文件实施控制管理的说明信息称为该文件的说明信息,又称为该文件的目录。
文件目录中包含文件名、与文件名相对应的文件内部标识以及文件信息在文件存储设备上第一个物理块的地址等信息。另外还可能包含关于文件逻辑结构、物理结构、存取控制和管理等信息。
12.答:二级目录和多级目录的好处是可以减少文件命名冲突和提高对自录表的搜索速度。
符号文件目录表和基本文件目录表是实现文件共享的一种方法,并不是二级目录。
13.答:保留单一副本,对于一个文件的多次并发更新,可能导致用户得到不正确的信息,并使结果文件处于不正确的状态.保留多个副本则浪费了一些存储空间而且各副本彼此可能会不一致。
7.4.2解析题一．论述题
1.答:文件是信息的一种组织形式,是存储在外存上的具有标识名的一组相关信息集合。
文件包含的内容有:源程序、-二进制代码、文本文档、数据、表格、声音和图像等。
文件的特点如下:
（1）文件具有保存性,它被存储在某种存储介质上,长期保存和多次使用。
（2）文件是按名存取的,每个文件具有惟一的标识名,通过标识名〈文件名〉来存取文件中的信息,而不需了解文件在存储介质上的具体物理位置。
（3）文件的内容是一组信息的集合,信息可以是源程序、二进制代码、文本文档、数据、表格、声音和图像等。
2.答:文件系统的主要目标是提高存储空间的利用率,它要解决的主要问题有:完成文件存储空间的管理,实现文件名到物理地址的转换,实现文件和目录的操作,提供文件共享能力和安全措施,提供友好的用户接口。文件系统向用户提供了有关文件和目录操作的各种功能接口和系统调用,如命令接口、程序接口和交互接口等。
3.答:文件的物理结构侧重于提高存储空间的利用率和减少存取时间,它对文件的存取方法有较大的影响。由于外存设备的不同,文件被划分为大小相等的物理块,它是存放文件信息或分配存储空间的基本单位,也是文件系统与主存之间传输和交换信息的基本单位。物理块大小一般是固定的,物理块与逻辑记录的关系可以是:一个物理块可以存放一个或多个逻辑记录,或者多个物理块存放一个逻辑记录。
目前操作系统中常采用如下物理结构文件:
(1)顺序文件:它是按照逻辑文件中的记录顺序,依次把逻辑记录存储到连续的物理块中而形成的文件。
(2)链接文件:它的物理块不是连续的,也不必顺序排列,但每个物理块中设置一个指针,指向下一个物理块的地址,这样,所有的物理块被链接起来,形成一个物理文件,称为链接文件或串联文件。
(3)索引文件:它是文件系统为每个文件另外建立一张指示逻辑记录和物理块之间的对应关系表,此表称为索引表,文件本身和索引表组成的文件称为索引文件。
4.答:操作系统需要处理大量用户文件,而访问一个文件需要查询目录,有时甚至需要多次查询目录。由于文件目录与文件一起存放在辅存上,当存取文件时,必须先到辅存中读取文件目录信息,从中获得文件的存放地址,然后再去存取文件。这样一来,文件信息的存取将花费很多时间。如果将整个文件目录放入主存,虽然可以提高存取速度,但这需要占用大量主存空间,显然这也是不可取的。实际上,在一段时间内使用的文件数总是有限的,因此只要将目录中当前要使用的那些文件的目录表目复制到内存中就可以了。这样既不占用太多的主存空间,又可显著提高查询文件目录的速度。为此,大多数操作系统中设置了两个文件操作:打开文件和关闭文件。打开文件操作完成的功能是将文件的有关目录信息复制到主存活动文件表中,以建立用户和这个文件的联系。关闭文件操作的功能是用户宣布这个文件当前不再使用,系统将其在主存中的相应目录信息删去,因而也就切断了用户同这个文件的联系。
5.答:文件存储设备的管理实质上是一个空闲块的组织和管理问题。有3种不同的空闲块管理方法。即空闲文件目录,空闲块链和位示图。
空闲文件目录管理方法就是把文件存储设备中的空闲块的块号统一放在一个称为空闲文件目录的物理块中,其中空闲文件目录的每个表项对应一个由多个空闲块构成的空闲区。量该方法实现简单,适于连续文件结构的文件存储区的分配与回收。但是由于回收时不进行合并,所以使用该方法容易产生大量的小块空闲区。
空闲块链法把文件存储设备上的所有空闲块链接在一起,从链头分配空闲块,把回收的空闲块插入到链尾。该方法不占用额外的空间,但实现复杂。
位示图法是从内存中划出若干字节,每个比特位对应一个物理块的使用情况。如果该位为0则表示对应的是空闲块,为1则表示对应的物理块已分配出去。位示图法在查找空闲块时无需启动外设,但要占用内存空间。
6.答:成组链法首先把文件存储设备中的所有空闲块按50块一组分组。组的划分是从后往前进行的。其中,每组的第一块用来存放前一组中各块的块号和总块数。第一组为49块。
最后一组的物理块号与总块数只能放在管理文件存储设备用的文件资源表中。
分配和释放过程:
首先,系统在初始化时把文件资源表复制到内存,从而把文件资源表中放有最后一组空闲块块号与总块数的堆找载入内存,并使得空闲块的分配与释放可以在内存中进行。用于空闲块分配与回收的堆楼有校指针Ptr,且Ptr的初值等于该组空闲块的总块数。当申请者申请n块空闲块时,按照后进先出的原则,分配程序在取走Ptr所指的块号之后,再做Ptr=Ptr-1的操作。这个过程一直持续到所要求的n块空间都分配完毕或堆校中只剩下最后一个空闲块的块号时。当堆楼中只剩下最后一个空闲块号时,系统启动设备管理程序,将该块中存放的下一组的块号与总块数读入内存之后再把该块分配给申请者。然后,系统重新设置Ptr指针,并继续为申请者分配空间。
文件存储设备的最后一个空闲块中设置有尾标识,以指示空闲块分配完毕。
如果用户进程不再使用有关文件并删除这些文件时,回收程序回收这些文件占用的物理块。成组链法的回收过程仍利用文件管理堆械进行。在回收时,回收程序先做Ptr=Ptr+1操作,然后把回收的物理块号放入当前Ptr指针所指的位置。如果Ptr等于50,则表示该组已经全部回收。此时,如果还有物理块需要回收的话,那么回收该块并启动I/0设备管理程序,把回收的50个块号与块数写入新回收的块中。然后将Ptr置1另起一个新组。对空闲块的分配和释放必须互斥进行。
7.答:(1)从性能上考虑,因后一种方式在删除文件时减少了访问磁盘的次数,故其速度比前一种方式更快。
(2)从安全性上考虑,把一个内容没有清除的盘块分配给下一个用户使用,则有可能使其获取盘块中的内容,故前一种方式比后一种方式更安全。
(3)从方便性上考虑,如果盘块中的内容没被清除,则当用户因误操作而删除文件时,他有可能通过某种办法恢复被删除的文件,故后一种方式更为方便。
8.答:利用链接方式共享文件主要有以下几方面的好处:
(1)方便用户:这种共享方式允许用户按自己的方式将共享文件组织到某个子目录下;并赋予它新的文件名,从而使用户可更方便地管理和使用共享文件。
(2)防止共享文件被删除。每次链接时,系统将对索引结点中的链接计数字段i-_nlink
进行加1操作,而删除时,必须先对它进行减1操作,只有当i_nlink的值为0时,共享文件才被真正删除,因此可避免用户仍要共享的文件被删除的现象。
(3)加快检索速度。为了加快检索文件的速度,一般系统都引入了当前目录的概念。用户在设置了工作目录后,若共享文件已被链接到该工作目录下,则系统无需再去逐级检索树形目录,从而可加快检索速度。
9.答:文件存取控制方式一般有存取控制矩阵、存取控制表、口令和密码术4种方式。
存取控制矩阵方式以一个二维矩阵来进行存取控制。而且矩阵的一维是所有的用户,另一维是所有的文件。对应的矩阵元素则是用户对文件存取控制权。存取控制矩阵的方法在概念上比较简单,但是当用户和文件较多时,存取控制矩阵将变得非常庞大,从而时间和空间的开销都很大。
存取控制表以文件为单位,把用户按某种关系划分为若干组,同时规定每组的存取限制。这样,所有用户组对文件权限的集合就形成了该文件的存取控制表。存取控制表方式占用空间较小,搜索效率也较高,但要对用户分组,引入了额外的开销。
口令方式有两种。一种是当用户进入系统,为建立终端进程时获得系统使用权的口令。另一种口令方式是,每个用户在创建文件时,为每一个创建的文件设置一个口令,且将其置于文件说明中。当任一用户想使用该文件时,都必须首先提供口令。口令方式比较简单,占用的内存单元以及验证口令所费时间都非常少。不过,相对来说,口令方式保密性能较差。
密码方式在用户创建源文件并写入存储设备时对文件进行编码加密,在读出文件时对其进行译码解密。加密方式具有保密性强的优点。但是,由于加密解密工作要耗费大量的处理时间,因此,加密技术是以牺牲系统开销为代价的。
10.答:(1)因磁带记录密度为每英寸800字符,则一个逻辑记录占据的磁带长度为:
160/800=0.2英寸
1500个逻辑记录要占据的磁带长度为:
(0.2+0.6〉×1500=1200英寸磁带利用率为,02/(0.2+0.6)=25%
(2)要使磁带利用率不少于50%,即磁带利用率大于或等于50%,则一组逻辑记录所占的磁带长度应与间隙长度相等,所以一组中的逻辑记录数至少为:
0.6/0.2=3
11.答：(1)由上述公式可得,逻辑磁盘块号x为:
x=k×m×a+k×b+c=10×20×185+10×12+5=37125
所以,柱面号为185,磁头号为12,磁道内块号为5的磁盘块的逻辑磁盘块号为37125。
(2)由上述公式可得
a =(x-1)DIV (k×m)=(1200-l) DIV (10×20)=1199 DIV 200=5
b =((x-1) MOD (k×m)) DIV K=((1200-1)MOD (10×20)) DIV 10=(1199 MOD 200) DIV lO
=199 DIV 10=19
c =((x-1) MOD (k×m)) MOD K+1=((1200-1) MOD (10×20)) MOD 10+1
=(1199 MOD 200〉MOD 10+1
=199 MOD 10+1
=9+1
=10
所以,逻辑磁盘块号为1200的盘块所对应的柱面号是5、磁头号是19、磁道内块号是10。
(3)对于磁盘组空间中的任一磁盘块,除了它的磁道内块号比原来小1以外,别的参数值均无变化,因此只要对转换公式中出现磁道内块号的公式作相应修改即可,x与a、b、c之间的转换公式如下:
x=k×m×a+k×b+c+1
a =(X-1) DIV (k×m)
b =（x-1）MOD (k×m)) DIV k
c =((x-1)MOD (k×m)) MOD K
12.分析：文件分配表FAT是一个数据结构,用在以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块。该表整个磁盘仅设一张,其结构如图7.7所示。表的序号是物理块号,从O开始直至N-1(N为盘块总数)。在每个表项中,存放下一个盘块号(即表项的内容为存放文件数据的下一个盘块号)。文件的首地址(第一个盘块号)存放在目录中。因此,从目录中找到文件的首地址后,就能找到文件在磁盘上的所有存放地址.例如图7.7中文件存放的盘块号依次为2、5、7。
物理块号
0 1 2 3 4 5 6 7 8 9
5
7
∧
某文件首块地址
图7.7 文件分配表答:由题目所给条件可知,硬盘大小为540M,磁盘块的大小为胀,所以该硬盘共有盘块:
540M/lk=540K(个)
又512K<540K<1024K故540K个盘块号要用20位二进制表示,即文件分配表的每个表目为2.5个字节。FAT要占用的存储空间总数为：25×540K=1350K
当硬盘大小为1.2G,硬盘共有盘块：1.2G/1K=1.2M〈个)
又
lM<1.2M<2M故1.2M个盘块号要用31位二进制表示。为方便文件分配表的存取,每个表目用32位二进制表示,即文件分配表的每个表目大小为4个字节。
FAT要占用的存储空间总数为:4×1.2M=4.8M
13.答:由题目所给条件可知,磁盘转速为每转27ms,每磁道存放9个记录,因此读出1个记录的时间是:27/9=3ms
(1)读出并处理记录A需要5ms,此时读写头己转到了记录B的中间,因此为了读出记录B,必须再转将近一圈〈从记录B的中间到记录B〉。后续8个记录的读取及处理与此相同,但最后一个记录的读取与处理只需5ms。于是,处理9个记录的总时间为:8×(27+3)+(3+2)=245ms
（2)由于读出并处理一个记录需要5ms,当读出并处理记录A时,不妨设记录A放在第1个盘块中,读写头已移到第2个盘块的中间,为了能顺序读到记录B,应将它放到第3个盘块中,即应将记录按如下顺序存放:
盘块
1
2
3
4
5
6
7
8
9
记录
A
F
B
G
C
H
D
I
E
这样,处理一个记录并将磁头移到下一个记录的时间是:
3(读出)+2(处理)+1(等待〉=6ms
所以,处理9个记录的总时间为:6×8+5=53ms
14.答:(1)为某文件分配两个盘块的过程如下:
①顺序检索位示图,从中找到第一个值为0的二进制位,得到其行号il=2,列号jl=2:第二个值为0的二进制位,得到其行号i2=3,列号j2=6。
②计算出找到的两个空闲块的盘块号分别为:
b1=i1×16十j1+1=2×16+2+1=35
b2=i2×16十j2+1=3×16+6+1=55
③修改位示图,令map[2,2]=map[3,6]=1,并将对应块35、55分配出去。
(2)释放磁盘的第300块时,应进行如下处理:
①计算出磁盘第300块所对应的二进制位的行号i和列号j:
i=(300-1)/16=18,j =(300-1)%16=11
②修改位示图,令map[18,11]=0,表示对应块为空闲块。
15.答:使用文件重命名功能时,用户必须提供两个参数:旧文件名,新文件名。实现该功能时,系统使用旧文件名查找文件目录,若找到旧文件名所对应的目录表目,则将目录表目中文件名字段对应的值改为新文件名值。从实现过程看,文件重命名功能完成的工作是修改目录表目中的文件名字段,除文件名外,文件的其他特性都未改变。
在后一种实现方法中,先进行文件复制并给复制文件起一个新名,此时系统完成了一次物理文件的复制工作,然后删除旧文件。虽然这样也能达到给文件重命名的目的,但其实现过程比前一种方式复杂,并且新文件与旧文件的物理存放地址肯定不同。
16.答:磁盘整理前,逻辑上相邻数据块的平均距离为13磁道,读一块数据需要的时间为:
13×6+100+25=203ms
因此,读取一个100块的文件需要时间:203×100=20300ms
磁盘整理后,逻辑上相邻数据块的平均距离为2磁道,读一块数据需要时间:
2×6+100+25=137ms
因此,读取一个100块的文件需要时间:137×100=13700ms
17.分析：在树形目录结构中,同一目录下的文件不可重名,不同目录下的文件可以重名。实现文件共享有多种方法,其中的一种方法是由系统实现对文件的共享,即当用户知道要共享文件的路径时,可以通过提供从根目录出发的路径名来共享访问这些文件;另一种方法是对需要共享的文件进行链接,即一个目录中的表目直接指向另一个目录的表目。所谓文件保护是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏,对文件的保护可采用进行文件存取控制的任何一种方法。
答:在本题中,文件系统采用了多级目录组织方式。
(1)a.由于目录D中没有己命名为A的文件,因此在目录D中,可以建立一个取名为A的文件。
b.因为在文件系统的根目录下已存在一个取名为A的目录,所以根目录下的目录C不能改名为A。
(2)a.用户E欲共享文件Q,需要用户E有访问文件Q的权限。在访问权限许可的情况下,用户E可通过相应路径来访问文件Q,即用户E通过自己的主目录E找到其父目录C,再访问到目录C的父目录根目录,然后依次通过目录D、目录G、目录K和目录O访问到文件Q。若用户E当前目录为E，则访问路径为：../../D/G/K/O/Q,其中符号".."表示一个目录的父目录,符号"/"用于分隔路径中的各目录名。
b.用户G需要通过依次访问目录K和目录P,才能访问到文件S及文件T。为了提高访问速度,可以在目录G下建立两个链接文件,分别链接到文件s及文件T上.这样,用户G就可以直接访问这两个文件了。
c.用户E可以通过修改文件I的存取控制表来对文件I加以保护,不让别的用户使用。具体实现方法是,在文件I的存取控制表中,只留下用户E的访问权限,其他用户对该文件无操作权限,从而达到不让其他用户访问的目的。
18.分析：OPEN操作主要完成建立用户与文件联系的工作.为了避免用户在每次访问文件时从外存中查找文件目录,系统提供了OPEN命令。该命令的功能是将待访问文件的目录信息读入内存活动文件表中,建立起用户和文件的联系.一旦文件被打开就可以多次使用,直到文件被关闭为止。
CLOSE操作主要完成撤消用户与文件联系的工作.若文件暂时不用,应将其关闭。
CLOSE命令的功能是撤消主存中有关该文件的目录信息,切断用户与该文件的联系;若在文件打开期间,该文件作过某种修改,则应将其写回辅存。
答：(1)显式的OPEN操作完成文件的打开功能。它将待访问文件的目录信息读入内存活动文件表中,建立起用户进程与文件的联系。显式CLOSE操作完成文件的关闭操作。该命令撤消主存中有关该文件的目录信息,切断用户与该文件的联系;若在文件打开期间,该文件作过某种修改,还应将其写回辅存。
（2）可以取消显式的OPEN与CLOSE操作。如果取消了显式的OPEN与CLOSE操作,系统在进行文件操作之前需判断文件是否己打开,若文件未打开,则应自动完成文件的打开功能,以建立用户与文件间的联系。同时,在系统结束时,还应自动关闭所有打开文件。
(3)取消显式的OPEN与CLOSE操作使得文件的读写的系统开销增加。因为在每次读写前都需要判断文件是否已被打开。系统在结束时也要做一些额外的工作,以完成CLOSE命令的功能。当用户进程己使用完一个文件但尚未执行完时,因无显式的CLOSE命令也无法关闭文件,从而不利于系统资源的回收。
7.1基本内容
7.1.1文件和文件系统
1.文件和文件系统
(1)文件:文件是一个具有符号名的一组相关联元素的有序序列。
(2)文件系统:操作系统中负责管理和存取文件信息的软件机构称为文件管理系统,简称文件系统。
它由三部分组成:
①与文件管理有关的软件;②被管理的文件;③实施文件管理所需的数据结构。
(3)文件系统的作用
① 从系统角度来看,文件系统是对文件存储器的存储空间进行组织和分配,负责文件的存储并对存入的文件进行保护和检索的系统。
② 从用户角度来看,文件系统实现了按名存取,并具有使用的方便性、数据的安全性和接口的统一性等特性。
2.文件的类型
(1)按性质和用途分类:系统文件;库文件;用户文件。
用户文件又可分为临时文件、档案文件和永久文件。
(2)按保护方式分类:只读文件;读写文件;不保护文件。
(3)按信息流向分类:输入文件;输出文件;输入输出文件。
(4)UNIX系统中的文件分类:普通文件(这种文件可以是系统文件、库文件、用户文件。);目录文件(目录文件是由文件目录组成的文件);特别文件(这类文件由I/0慢速字符设备构成)。
3.文件系统的基本功能
(1)文件的结构及有关存取方法。
(2)文件的目录机构和有关处理。
(3)文件存储空间的管理。
(4)文件的共享和存取控制。
(5)文件操作和使用。
7.1.2 文件的结构与存取设备
1.文件的结构,
(1)文件的逻辑结构文件的逻辑结构是呈现在用户面前的文件结构。可以分为两种:
①有结构的记录文件。它又分为两种:定长记录文件;变长记录文件。
②无结构的流式文件是有序字符的集合。文件长度为文件所包含的字符总数。
(2)文件的物理结构文件的物理结构是指逻辑文件在文件存储器上的存储结构。
为了有效地分配文件存储的空间,通常把它们分成若干块,并以块为单位进行分配和传送。每个块称为物理块,而块中的信息称为物理记录。物理块长通常是固定的。允许一个逻辑记录占用几块,也可以在一块中存放几个逻辑记录。
文件在逻辑上都可以看成是连续的,但在物理介质上存放时,却可以有多种形式。以下是几种基本的文件物理结构:
①连续结构:是将逻辑文件信息存放在文件存储器上相邻的物理块中。
连续结构的优点是结构简单,存取速度较快;缺点是建立文件时,要求给出文件的最大长度,且不便于增删,一般只能在末端进行。
②串联结构:也称为链接结构。其物理块可以不连续,也不必顺序排列;在每个物理块中设置一个指针(也称链接字),它指向该文件的下一个物理块号。
串联结构的优点是文件可动态增删,不必事先知道文件的最大长度p缺点是只适合顺序存取,必须从头开始查找,查找速度低,且因每块都要设置链接字,破坏了物理信息的完整性。
③索引结构:要求为每个文件建立一张索引表,其中每个表目指出文件逻辑记录所在的物理块号。索引表是由系统自动建立的。
索引结构的优点是有串联结构的所有优点,克服了它的缺点,可随机存取;缺点是增加了索引表的空间开销,增加了一次访问盘的操作而降低了丈件访问速度。
当文件很大时,文件的索引表也会很大。如果索引表的大小超过了一个物理块时,可以将索引表本身作为一个文件,再为其建立一个"索引表",这个"索引表"作为文件索引的索引,从而构成了二级索引。第一级索引表的表目指向第二级索引,第二级索引表的表目指向相应信息所在的物理块号。以此类推可再逐级建立索引,进而构成多级索引。
④Hash(散列)文件:是采用计算寻址结构,把链值通过某种计算处理,转换成相应记录的相应地址。计算寻址就是通过Hash函数计算后求得的地址。
Hash文件的优点是不需索引,节省查找时间;缺点是需要使用Hash(散列)函数计算。
2.文件的存取方法文件的存取方法是指读写文件存储器上的一个物理块的方法。
存取方法有三类:顺序存取法、直接存取法和按键存取法。
(1)顺序存取法严格按物理记录排列的顺序依次存取。
(2)直接存取法允许用户随意存取文件中的任何一个物理记录,而不管上次存取了哪一个记录。
(3)按键存取法实质上也是直接存取法,它不是根据记录编号或地址来存取的,而是根据文件中各记录内容进行存取的。
文件的物理结构密切依赖于文件存储器的特性和存取方法。
如果采用直接存取法,则索引文件效率最高,连续文件效率居中,串联文件效率最低。
3.文件存储设备文件的存储设备主要有磁带、磁盘、光盘等。由于存储设备的特性可以决定文件的存取方法,因此这里介绍以磁带为代表的顺序存储设备和以磁盘为代表的直接存储设备的特性,以及存储设备、文件物理结构与存取方法之间的关系。
（1）磁带：是一种典型的顺序存取设备,这种设备只有在前面的物理块被存取访问过之后,才能存取后续物理块的内容。由于磁带机的启动和停止都要花费一定的时间,因此在磁带的相邻物理块之间设计有一段间隙将它们隔开,如下所示:
磁 带
…
间隙
第i块
间隙
第i+1块
间隙
…
磁带的存取速度与信息密度(字符数/英寸〉、磁带带速(英寸/秒)和块间间隙有关。如果带速高,信息密度大且所需块间隙(磁头启动和停止时间〉小,则磁带存取速度高。反之,若磁带带速低,信息密度小且所需块间隙〈磁带启动和停止时间〉大,则磁带存取速度低。由于磁带读写时只有在第i块被存取之后,才能对第i+1块进行存取操作,因此,某个特定物理块的存取访问与该物理块到磁头当前位置的距离有很大关系。
（2）磁盘是典型的直接存取设备,这种设备允许文件系统直接存取磁盘上的任意物理块。磁盘机一般由若干磁盘片组成,可沿一个固定方向高速旋转。每个盘面对应一个磁头,磁臂可沿半径方向移动。磁盘上的一系列同心圆称为磁道,磁道沿径向又分成大小相等的多个扇区,与盘片中心有一定距离的所有磁道称为一个柱面。因此,磁盘上的每个物理块可用柱面号,磁头号和扇区号表示。
访问磁盘时间由三部分组成,即寻道时间、旋转延迟时间和传输时间,其中寻道自才间是指将磁头从当前位置移动到指定磁道所经历的时间,旋转延迟时间是指定扇区移动到磁头下面所经历的时间,传输时间是指将扇区上的数据从磁盘读出或向磁盘写入数据所经历的时间。
表7.1存取设备、存取方法和物理结构之间的关系存取设备
磁盘
磁带
物理结构
顺序结构
链接结构
索引结构
顺序结构
存取方法
直接或顺序
顺序
直接或顺序
顺序
文件长度
固定
可变、固定
可变、固定
固定
7.1.3文件目录管理
1.编排文件目录的原则
(1)系统中的文件种类繁多、数量庞大,为了使用户方便地找到文件,需要在系统中建立一套目录机构。
(2)编排目录的原则是,能够实现"按名存取",使查找文件准确、快速;解决命名的冲突及文件共享等问题。
2.文件控制块、目录项和索引结点为了能对一个文件进行正确的存取,必须为它设置用于描述和控制文件的数据结构,称之为"文件控制块(FCB)"。文件控制块中最基本的内容是文件名和文件的物理地址,其他的内容通常有文件的逻辑结构、文件的物理结构、文件的长度、文件的存取权限、文件的建立日期和时间、文件最后一次修改的臼期和时间、文件的连接计数及文件主的标识符等文件属性信息。
文件控制块与文件一一对应,并分别存放,我们将文件控制块的有序集合称作目录,而其中的每个文件控制块被称为目录项。目录通常也是以文件的方式存放在外存上,因此,也将它称为目录文件。
文件目录通常跟文件一起存放在外存上,当文件很多时,文件目录可能要占用大量的物理块。此时,在文件目录中查找一个指定的文件可能要多次启动外存,故十分费时。而在检索目录的过程中,实际上只用到了其中的文件名信息,仅当找到了匹配的目录项(即其中的文件名与指定的文件名相同)后,才需要从该目录项中读出该文件的物理地址等信息。
为此,有些系统,如UNIX系统,便采用把文件名和文件描述信息分开的办法,即将文件最描述信息单独形成一个称为索引结点的数据结构,存放在外存的索引结点区,而组成文件目录的目录项中仅有文件名和指向该文件所对应的索引绪点的指针。这样,便可大大减少一文件目录所占的物理块数,从而加快检索目录的速度。
3.目录结构目录结构是指文件目录的组织方式,它将直接关系到文件的存取速度以及文件的共享性和安全性。常用的目录结构有：
（1）单级目录结构单级目录结构是指在整个文件系统中只建立一张目录表,每个文件占其中的一个表项。
每当要建立一个新文件时,必须先检索所有的目录项,以保证新文件名在目录中是惟-的；然后再从目录表中找出一个空白目录项,填入新文件的文件名和其他说明信息。删除文件时,先从目录中找到该文件的目录项,然后再根据其中的物理地址回收外存空间,并清除该目录项。
单级目录的管理和实现十分简单。但它不能满足对目录管理的要求,例如它不允许文件重名,因此也不便于实现文件共享；而且,当文件数目较多时,它的检索速度会变得十分缓慢。
(2)两级目录结构为克服简单文件目录的缺点,可采用二级目录。二级目录由主目录表(MFD〉和用户文件目录表(UFD)组成。主目录表是管理用户目录表的总文件目录。用户文件目录表由各用户建立自己的名空间构成。二级目录的优点是解决了"重名"、"别名"问题,提高了查找速度,比一级目录快得多。
(3)多级目录结构为了进一步提高对目录的检索速度,使用户更加方便地组织和使用自己的文件,现代操作系统普遍使用多级目录结构(又称为树形目录结构)来进行文件管理。主目录在这里被称为根目录,数据文件被称为树叶,而其他的目录均作为树的结点。
通常,一个用户进程在一给定的时间内所访问的文件仅局限于某个文件目录之下。为了简化文件的查找过程,可将该文件目录设置成"当前目录"或"工作目录",以后用户进程对各文件的访问都可相对于"当前目录"而进行,而将当前目录到数据文件之间的所有目录文件名(不包括当前目录文件名)与数据文件名用"/"依次连接起来,便构成了文件的相对路径名。
4.文件目录项的组织和查询技术
（1）文件目录项的组织文件目录项的组织随系统而异。不同系统的文件目录项的组织如下：
①CP/M中的目录项：CP/M是一个早期的8位微机操作系统,该系统采用简单目录结构,其目录项包含文件名、文件类型、盘驱动器号、范围、磁盘块数和磁盘块号。
②MS -DOS中的目录项。MS -DOS采用树型目录结构。其目录项包含文件名、类型、属性、时间、日期、首簇号、文件长度。MS -DOS采用串联(链接〉结构,其第一个磁盘块的块号(称为首簇号〉放在目录项中,根据首簇号,按链接表(文件分配表FAT)可以找出该文件的所有块。
③UNIX中的目录项。UNIX中使用的目录结构非常简单,每个目录项仅包含一个文件名及其i节点号,而有关文件目录项中的其余文件结构信息、文件控制信息、文件管理等信息均放在i节点中。
（2）目录查询系统当用户要访问一个文件时,系统首先要利用用户提供的路径名对目录进行查询,只要找到对应的文件控制块或索引结点,便可找到具体的文件并对之进行相应的操作。在读/写文件前,必须先打开文件。打开文件时,操作系统利用用户给出的文件路径名到相应的目录项中查找该文件相关信息:文件结构信息、文件管理信息和文件控制信息。
7.1.4文件存储空间管理
1.存储空间管理程序应解决的几个问题一个大容量的文件存储器为系统本身和许多用户所共享。为方便用户"按名存取"所需之文件,系统应能自动为用户分配及管理系统和用户的存储空间。为此,应解决以下三个问题。、
(1)登记空闲区的分布情况。
(2)按需要给一个文件分配存储空间。
(3)收回不再需要保留的文件所占的存储空间。
以上问题都归结为盘空闲区的管理问题。
2.常用的盘空闲区管理方法
（1)空白文件目录盘空间上一个连续的未分配区域称为空白文件。系统为所有这些空白文件单独建立一个目录。对每个空白文件,在这个目录中建立一个表目。表目的内容包括第一个空白块地址(物理块号)、空白块个数等。在进行存储空间的分配时,同样可采用首次适应、最佳适应等算法；而回收时,同样要进行空闲区的合并。
这种方法的优点是空闲区的分配和回收都相当容易,但用来管理空闲区的空闲表需要占用大量的存储空间。
（2）空白块链该方法是将所有空白块用链接指针或索引结构把它们组成一个空白文件。释放和分配空白块都可以在链首进行,只需要修改几个有关的链接字。本方法只要求在主存中保存一个指针,令它指向第一个空白块。
这种方法的优点是实现简单;但工作效率低,因为每当在链上增加或移去空白块时需要对空白块链做较大的调整,因而会有较大的系统开销。
一种改进方法是将空白块分成若干组,再用指针将组与组链接起来,将这种管理空白块的方法称为成组链接法。这种成组链接法,在进行空白块的分配与回收时要比空白块链法节省时间。
（3）位示图法位示图是利用二进制的一位来表示文件存储空间中的一个块的使用情况。一个m行、n
列的位示图,可用来描述m×n块的文件存储空间,当行号、列号和块号都是从0开始编号时,第i行、第j列的二进制位对应的物理块号为i×n+j。如果"0"表示对应块空闲,"1"表示对应块己分配,则在进行存储空间的分配时,可顺序扫描位示图,从中找出一个或一组其值为"0"的二进制位,将对应的块分配出去,并将这些位置1；而在回收某个块时,只需找到对应的位,并将其值清0便可。
位示图法适合于所有的分配方式,它简单易行,而且位示图通常较小,故可将其读入内存,从而进一步加快文件存储空间分配和回收的速度。
（4)MS -DOS的盘空间管理
MS-DOS盘空间的分配采用文件分配表FAT;盘空间的分配单位称为簇(相当于块),簇的大小因盘而异,每个簇在FAT表中占一个项。FAT表是一个简单的线性表,它由若干项组成。FAT表的头两项用来标记盘的类型,其余的每个项包含三个十六进制的字符；若为000,表示空闲簇；FFF表示该簇是一个文件的最后一簇；若为其它任何十六进制字符,表示该簇是某一文件的下一簇号。
（5）UNIX文件存储空间的管理（成组链接法）
成组链接法是UNIX系统采用的空闲盘块管理方式。它将一个文件卷的所有空闲盘块按固定大小(如每组100块)分成若干组,并将每一组的盘块数和该组所有的盘块号记入前一组的最后一个盘块中,第一组的盘块数(可小于100)和该组所有的盘块号则记入超级块的空闲盘块号楼中。
当系统要为用户分配文件所需的盘块时,若第一组不只一块,则将超级块中的空闲盘块数减1,并将空闲盘块钱校顶的盘块分配出去:若第一组只剩一块且钱顶的盘块号不是结束标记0,则先将该块的内容(记录有下一组的盘块数和盘块号)读到超级块中,然后再将该块分配出去:否则,若楼顶的盘块号为结束标记0,则表示该磁盘上己无空闲盘块可供分配。
在系统回收空闲盘块时,若第一组不满1∞块,则只需将回收块的块号填入超级块的空闲盘块钱钱顶,并将其中的空闲盘块数加1:若第一组已有100块,则必须先将超级块中的空闲盘块数和空闲盘块号写入回收块中,然后将盘块数1和回收块的块号记入超级块中,值得注意的是,超级块中的空闲盘块钱是临界资源,对该校的操作必须互斥地进行,因此,系统为空闲盘块钱设置了一把锁,并通过上锁和解锁来实现对空闲盘块钱的互操作。
成组链接法除了第一组空闲盘块外,其余空闲盘块的登记不占额外的存储空间;而超级块(即文件卷的第1块)已在安装磁盘时拷入内存,因此,绝大部分的分配和回收工作可在国内存中进行,从而使之具有较高的效率。
7.1.5 文件的共享文件共享是指系统允许多个用户(进程)使用同一份文件。在允许文件共享的系统中,如果用户知道共享文件的路径名,并有访问该文件的权限,则可直接使用文件的路径名来访问该共享文件。为了使用户能更方便地共享文件,很多系统还允许一个共享文件同时出现在多个用户的目录下,这种共享可通过下述方法来实现。
1.目录结构中的共享在目录结构中,可以采用同名或异名的方式来实现文件的共享。这时文件系统的目录结构已不再是树型结构,而是一个有向的非循环图。异名共享所采用的方法称为文件的勾连。实现勾连的方法有两种：基于索引节点的共享和基于符号链的共享。
（1）基于索引结点的共享方式在文件的索引结点中设置一个链接计数字段,用来表示链接到本索引结点(亦即文件)上的用户目录项的数目。当用户C创建一个新文件时,其链接计数被置为1。如果用户B要共享该文件,则可在B的目录中增加一目录工页,并填上新的文件名和指向该共享文件的索引结点的指针,索引结点中的链接计数将被加1。
这种方式的缺点是文件主无法删除被他人共享的文件。如果C将共享文件删除并清除相应的索引结点,则B中将有一个指向无效索引结点的目录工页,若该索引结点以后被分配给另一个文件,则B将去共享一个错误的文件:如果C留下了索引结点,并将其链接计数减仁由于C是文件主,若系统要记账收费,C将继续为该文件付账,直至其他用户执行删除操作时,发现其链接计数为0,将其真正删除为止。
（2）利用符号链实现文件共享为了使B能共享C的一个文件,可以由系统为B建立一个类型为LINK的新文件,并把该文件放在B的目录下,在新文件中只包含了被链接文件的路径名。当B读该LINK类型的文件时,将被os截获,并根据新文件中的路径名去读那小文件。这种实现文件共享的方式叫做符号链接。在这种方式下,文件主删除被他人共享的文件后,其他用户再去访问该共享文件时,会因找不到文件而失败,于是可再将符号链(即LINK类型的文件)删除,此时不会造成任何影响。它的问题是其他用户访问共享文件时,必须根据路径中的分量名逐级地去检索目录,因此加大了访问文件的开销:另外,尽管LINK类型的文件十分简单,但仍需为它配置一个索引结点,飞并分配一个盘块来存放被链接文件的路径名,这同样会增加系统的的开销。符号链接有一个很大的优点,即只要简单地提供一个机器的网络地址以及文件在该机器中的文件路径名,便可链接全球任何一处机器上的文件。
2.打开支件结构中的共享文件目录结构中的共享是一种静态的共享。当多个用户同时打开某一文件对其访问时,将在内存中建立打开文件结构,这时的共享称为打开文件结构中的共享,这是一种动,态的共享。
文件系统中的打开文件结构由三部分组成z进程打开文件表、系统打开文件表和内存
Inode。
（1）父、子进程打开文件的共享父进程创建子进程时,除状态、标识以及与时间有关的少数控制项外,子进程基本上是复制父进程的所有信息。子进程与父进程可以共享父进程所打开的文件。父、子进程可以并发运行。它们也可以各自独立地打开文件,但这些各自独立打开的文件不能共享。
（2）同名或异名打开文件的共享不同进程通过同名或异名方式打开同一文件实现共享时,各进程使用各自的进程打开文件表和各自的名方式打开同一文件实现共享。
3.管道文件采用管道进行通信就像在两个进程之间架设了一个管道,一方能够将消息源源不断地写入管道,另一方连续从管道中将消息读出。它能够实现大量消息的通信。l
UNIX系统中,管道是一种特殊的文件,是一个特殊的打开文件,由三部分组成：一个外存索引节点、相应的内存索引节点和两个系统打开文件表。进程创建一个管道文件后,通常接着创建一个或几个子进程。管道文件实际上是一个临时文件,它以磁盘为中介实现进程间的通信。与内存相比,管道通信速度较慢,而且它只适用父、子进程之间的通信。管道文件能实现读写的同步和互斥。
7.1.6 文的存取控制系统中的文件既存在保护问题,又存在保密问题。所谓保护是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。所谓保密是指文件本身不得被未授权的用户访问。这两个问题都涉及用户对文件的访问权限,即文件的存取控制。
文件的保护机构应做到：
(1)防止未核准的用户存取文件;
(2)防止一个用户冒充另一个用户存取文件;
(3)防止核准用户〈包括文件主〉误用文件。
文件保护机构通常由存取控制验证模块来实现,其基本任务是:
(1)审定用户的存取权限;
(2)比较用户的存取权限和本次的存取要求;
(3)比较本次存取要求和被访问文件的存取保护信息。
以下介绍几种常用的文件存取控制方法。
1.存取控制矩阵存取控制矩阵是一个二维矩阵:一维列出系统中的所有用户z另一维列出系统中的全部文件。矩阵中的每个元素用来表示某一用户对某一文件的存取权限。
2.存取控制表由于存取控制矩阵是一个稀疏矩阵,浪费存储,因此,可为每一个文件建立一张存取控制表,仅存放与该文件有关的用户或用户组。
3.用户权限表与存取控制表相似,以用户或用户组为单位建立存取控制表,这样的表称为用户权限表。将一个用户或用户组所要存取的文件集中起来存入一张表中,其中每个表目指明用户(组)对相应文件的存取权限。
4.口令文件主在建立一个文件时,一方面进行口令登记,另一方面把口令告诉允许访问该文件的用户。访问该文件时首先核对口令,当口令正确时才允许访问,否则拒绝访问。本方法的优点是保护信息少,简单,易实现;缺点是保密性不强,且改换口令时需通知所有能访问该文件的用户。
5.密码文件写入时先进行编码F读出时要先译码再使用。只有掌握了译码方法的用户才能读出正确的信息。本方法保密性强,节省存储空间,但编码和译码都需大量的时间。
6.文件系统的安全性为了防止由于软、硬件故障而造成系统失败,保证被破坏了的文件能进行有效的恢复,系统应保存所有文件的双份拷贝。一旦一份拷贝被破坏,就可以使用另一份拷贝恢复系统。文件拷贝的方法有两种:一种是周期性的全量转存,另一种是增量转存。
文件系统和用户间的接口是通过系统调用实现的。一般文件系统为用户提供的系统调用主要有建立/删除、打开/关闭、读/写文件等。
7.1.7.文件的使用用户可通过文件系统所提供的命令和系统功能调用来实施对文件的操作。基本的文件操作有以下几种:
(1)创建文件。在创建一个新文件时,系统要为它分配必要的外存空间,并在文件系统的目录中,为它建立一个目录项,用来登记该文件的文件名及其在外存的地址等属性。
(2)删除文件。当不再使用某个文件时,可将它从文件系统中删除。此时,系统应先从目录中找到要删除文件的目录项,并根据其中的外存地址信息回收该文件所占的存储空间,
最后还必须释放它的目录项。
(3)读文件。当用户需要某个文件中的数据时,可将相应数据从外存读入内存。此时,系统同样要查找目录,找到指定文件的目录项,从中得到文件在外存中的地址信息,然后启动设备将数据读入内存。
(4)写文件。当用户要求添加或修改某个文件的内容时,可对它进行写操作。为此,也同样需要查找目录,找到指定文件的目录项,从中得到文件在外存中的地址信息,然后启动设备将数据写到相应的外存位置。
(5)设置文件的读/写指针。文件的读/写指针指出了要读/写的信息距离文件首字节的偏移量。在读/写文件时,将根据读/写指针和相应文件目录项中的外存地址信息计算出欲读/写的信息在外存中的地址。通过设置文件读/写指针的操作,可将读/写指针设置到文件的任一位置,从而实现对该文件内容的随机访问。
(6)打开文件。打开文件的主要功能是将指定文件的属性信息复制到内存中,并返回指向内存中的该文件属性信息的指针。以后,用户需要对该文件进行操作时,便可直接在内存中找到文件的外存地址等属性,从而显著地提高对文件的操作速度。
(7)关闭文件。当用户目前不再要求访问某个打开文件时,可对它进行关闭操作。此时,将从内存中删除指定文件的属性信息,如果其中的文件属性信息已被修改过,则还需将它写回外存。关闭文件后,若要再次访问该文件,则必须重新进行打开文件的操作。
7.2重点难点学习提示本章的目的是掌握文件系统的基本概念和实现过程,为此应对以下几个重点、难点问题作认真的学习,切实地掌握其基本内容。
1.顺序文件、索引文件和索引顺序文件根据用户和系统管理上的需要,可将有结构文件的记录组织成顺序文件、索引文件和--z
索引顺序文件三种形式。
(1)顺序文件：应了解如何对定长记录的顺序文件进行读/写操作,这种文件形式有何优缺点,它主要用于何种场合。
(2)索引文件：应能较好地理解为什么要引入索引文件,并能用图来说明索引文件的组形式,以及索引文件的优缺点。
(3)索引顺序文件：应了解索引顺序文件是为了解决什么样的问题而引入的,如何对索引顺序文件进行检索,当文件非常大时又应如何处理。
2.连续分配、链接分配和索引分配在为文件分配存储空间时,通常可采用连续分配、链接分配和索引分配三种方式。
(1)连续分配：应了解如何连续分配的文件进行顺序访问或随机访问,这种分配方式有何优缺点。
(2)链接分配：这是指为每个文件分配多个离散的盘块,并通过链接指针将它们链成个链表的分配方式。在学习时应较好地理解隐式链接分配方式是为了解决什么问题而引入;再的,它有何不足之处,而显式链接结构是如何解决上述不足的,它较适合用于哪种场合；并能用图来说明这两种分配方式是如何将多个离散的盘块链成一个链表的。
(3)索引分配：应能很好地掌握为什么要引入索引分配方式,采用索引分配方式时应如何对文件进行访问,当文件很大时又应如何处理。另外,还必须很好地了解和掌握混合索引分配方式是为了解决什么问题而引入的,此时,应如何将文件的逻辑地址转换成物理地址。
3.位示图法和成组链接法
(1)位示图法：应了解使用位示图如何来进行磁盘块的分配或回收,这种管理方式有何优点。
(2)成组链接法：应掌握它是如何将盘块进行分组并将各个盘块组链成一个成组链的,它应如何进行盘块的分配和回收,这种管理方式有什么优点。
4.目录管理必须对下述与目录管理有关的内容有较清晰的认识：
(1)文件控制块(FCB)：应了解FCB通常应包含哪些内容,它与文件之间存在着什么样的关系。
(2)索引结点：应理解磁盘索引结点是为了解决什么问题而引入的,它与FCB、目录项之间存在着什么样的关系。另外,还应了解为什么要引入内存索引结点,以及在内存索引结点中还应增加哪些数据项,原因是什么。
(3)单级目录和两级目录结构：应清楚地了解在单级目录结构中应如何创建或删除文件,它在哪些地方无法满足对目录管理的要求,而两级文件目录是如何解决这些问题的。
(4)多级目录结构：应很好地理解和掌握目录结构由单级发展为两级、并进一步发展为多级带来了哪些好处,应如何根据绝对路径名或相对路径名在多级目录结构中线性地检索一个文件或子目录,要创建或删除一个文件或子目录时应如何进行处理。
5.文件共享方式文件共享的主要目的:一是提高文件存储空间的利用率,二是方便用户对文件的使用，当前常用的文件共享方式有基于索引结点的共享方式和利用符号链实现文件共享两种。
(1)基于索引结点的共享方式：应了解如果不引入索引结点,而直接通过FCB来共享文件会产生什么问题,这种共享方式应如何进行文件的删除操作,它有何优缺点。
(2)利用符号链实现文件共享：应了解当用户访问LINK类型的文件时,系统应如何进行处理,通过这种方式共享文件有何优缺点。
7.3典型问题分析和解答
1.文件系统有哪些基本功能?
答:文件系统有以下基本功能：(1)文件的结构及有关的存取方法;（2）文件的目录结构及有关处理;(3)文件的存储空间管理;（4)文件共享的存取控制；(5)文件的操作和使用。
2.文件系统提供的基本操作都有哪些?
答:文件系统提供的基本操作有：(1)建立/删除文件；（2）打开/关闭文件;(3)读/写文件。
3.设某系统的磁盘有500块,块号为：0,1,2,3,…,499。
（1)若用位示图法管理这500块的盘空间,当字长为32位时,需要多少个字的位示图?
(2)第i字的第j位对应的块号是多少?（其中：i=0,1,2,…,j=0,1,2,3,…）
答:(1)位示图法就是在内存用一些字建立一张位示图,用其中的每一位表示一个盘块的使用情况,通常用"1"表示占用,"0"表示空闲。因此,本问题中位示图所占的字数为：
「500/32〡=16。
(2)第i字的第j位对应的块号N=32*i+j。
4.请分别解释在连续分配方式、隐式链接分配方式、显式链接分配方式和索引分配有式中如何将文件的字节偏移量3500转换为物理块号和块内位移量(设盘块大小为1KB,盘块号需占4个字节)。
答:首先,将字节偏移量35ω转换成逻辑块号和块内位移量:
3500/1024得到商为3,余数为428,即逻辑块号为3,块内位移量为428。
(1)在连续分配方式中,可从相应文件的FCB中得到分配给该文件的起始物理盘块号,例如a0,故字节偏移量3500相应的物理盘块号为aO+3,块内位移量为428。
(2)在隐式链接方式中,由于每个盘块中需留出4个字节(如最后的4个字节)来存放分配给文件的下一个盘块的块号,因此字节偏移量3500的逻辑块号为3500/1020的商3,而块内位移量为余数440。
从相应文件的FCB中可获得分配给该文件的首个(即第0个)盘块的块号,如bO；然后可通过读第bO块获得分配给文件的第1个盘块的块号,如b1再从b1块中得到第2块的块号,如b2;从b2块中得到第3块的块号,如b3。如此,便可得到字节偏移量3500对应的物理块号b3,而块内位移量则为440。
(3)在显式链接方式中,可从文件的FCB中得到分配给文件的首个盘块的块号,如c0;然后可在FAT的第cO项中得到分配给文件的第1个盘块的块号,如cl;再在FAT的第cl项中得到文件的第2个盘块的块号,如c2;在FAT的第c2项中得到文件的第3个盘块的块号,如c3。如此,便可获得字节偏移量3500对应的物理块号c3,而块内位移量则为428。
(4)在索引分配方式中,可从文件的FCB中得到索引表的地址。从索引表的第3项(距离索引表首字节12字节的位置)可获得字节偏移量3500对应的物理块号,而块内位移量为428。
5.假定一个当前含有100块的文件,如果
(1)在开头加入一块；
(2)在中间加入一块；
(3)在末端加入一块；
(4)在开头删除一块；
(5)在中间删除一块；
(6)在末端删除一块。
那么,使用毗连、链接和索引分配策略各涉及到多少次盘I/O操作?
解：它们所涉及的操作次数如下表所示。
表7.
序号
毗连
链接
索引
（1）
201
1
1
（2）
101
51
1
（3）
1
2
1
（4）
0
1
1
（5）
98
52
1
（6）
0
100
1
6.存放在某个磁盘上的文件系统,采用混合索引分配方式,其FCB中共有13个地址工页,第O-9个地址项为直接地址,第10个地址项为一次间接地址,第11个地址项为二次间接地址,第12个地址项为三次间接地址。如果每个盘块的大小为512字节,若盘块号需要用3个字节来描述,而每个盘块最多存放170个盘块地址:
(1)该文件系统允许文件的最大长度是多少?
(2)将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。
(3)假设某个文件的FCB己在内存,但其他信息均在外存,为了访问该文件中某个位置的内容,最少需要几次访问磁盘,最多需要几次访问磁盘?
分析：在混合索引分配方式中,FCB的直接地址中登记有分配给以件的前n块(第0到n-1块)的物理块号(n的大小由直接地址项数决定,本题中为10);一次间址中登记有一个一次间址块的块号,而在一次问址块中则登记有分配给文件的第n到第n+k-1块的块号(k的大小由盘块大小和盘块号的长度决定,本题中为170);二次间址中登记有一个二次问址块的块号,其中可给出k个一次间址块的块号,而这些一次间址块被用来登记分配给文件的第n+K块到第n+k+k^2-1块的块号;三次间址中则登记有一个三次间址块的块号,其中可给出k个二次间址块的块号,这些二次间址块又可给出k^2个一次问址块的块号,而这些一次间址块则被用来登记分配给文件的第n+k+k^2块n+k+k^2+k^3-1块的物理块号。
答:(1)该文件系统中一个文件的最大长度可达:
10+170+170×170+170×170×170=4942080块=4942080×512字节=247104OKB
(2)5000/512得到商为9,余数为392,即字节偏移量5000对应的逻辑块号为9,块内偏移量为392。由于9<10,故可直接从该文件的FCB的第9个地址项处得到物理盘块号,块内偏移量为392。
15000/512得到商为29,余数为152,即字节偏移量15000对应的逻辑块号为29,块内偏移量为152。由于10≤29<10+170,而29-10=19,故可从FCB的第10个地址项,即一次间址项中得到一次问址块的地址；并从一次间址块的第19项(即该块的第57—59这3个字节)中获得对应的物理盘块号,块内偏移量为152。
150000/512得到商为292,余数为496,即字节偏移量150000对应的逻辑块号为292,块内偏移量为496。由于10+170≤292<10+170+170×170,而292一(10+170)=112,112/170得到商为0,余数为112,故可从FCB的第11个地址项,即二次问址项中得到二次间址块的地址,并从二次间址块的第0项中获得一个一次间址块的地址,再从该一次间址块的第112项中获得对应的物理盘块号,块内偏移量为496。
(3)由于文件的FCB己在内存,为了访问文件中某个位置的内容,最少需要1次访问磁盘(即可通过直接地址直接读文件盘块),最多需要4次访问磁盘(第一次是读三次问址块,第二次是读二次间址块,第三次是读一次间址块,第四次是读文件盘块)。
7.有一磁盘组共有10个盘面,每个盘面上有100个磁道,每个磁道有16个扇区。假定分配以扇区为单位,若使用位示图管理磁盘空间,问位示图需要占用多少空间?若空白文件目录的每个表目占用5个字节,问什么时候空白文件目录大于位示图?
分析：空白文件目录是管理磁盘空间的一种方法,该方法将文件存储设备上的每个连续空闲区看作一个空白文件。系统为所有空白文件单独建立一个目录,每个空白文件在这个目录中占一个农目。表目的内容至少包括第一个空白块的地址(物理块号)、空白块的数目。
位示图是另一种常用的管理磁盘空间的方法,该方法通过建立一张位示图来反映整个存储空间的分配情况。其中,每一个二进制位都对应一个物理块,当某位为1时表示该块已分配,当某位为0时表示该块空闲。
答:由题目所给条件可知,磁盘组扇区总数为:16×100×10=16000
因此,使用位示图描述扇区状态需要的位数为:16000位=2000字节又由题目所给条件可知,空白文件目录的每个表目占5个字节,由上述计算知位示图需要占2000字节,2000字节可存放表目数为:2000/5=400
所以当空白区数目大于400时,空白文件目录大于位示图。
8.在某个文件系统中,每个盘块为512字节,文件控制块占64个字节,其中文件名占8个字节也如果索引结点编号占2个字节,对一个存放在磁盘土的256个目录项的目录,试比较引入索引结点前后,为找到其中一个文件的FCB,平均启动磁盘的次数。
答:在引入索引结点前,每个目录项中存放的是对应文件的FCB,故256个目录项的目录总共需要占用256×64/12=32个盘块。因此,在该目录中检索到一个文件,平均启动磁盘次数为（1+32）/2=16.5。
在引入索引结点之后,每个目录项中只需存放文件名和索引结点的编号,因此256个目录项的目录总共需要占用256×(8+2)/512=5个盘块。因此,找到匹配的目录项平均需要启动。+5归,即3次磁盘:而得到索引结点编号后j还需启动磁盘将对应文件的索引结点读入内存,故平均需要启动磁盘4次。可见,引入索引结点后,可大大减少启动磁盘的次数,从而有效地提高检索文件的速度。
9.使用文件系统时,通常要显式地进行open、close操作。
(1)这样做的目的是什么?
(2)能否取消显式的open、close操作?应如何做?
(3)取消显式的open、close有什么不利?
答:(1)显式的open操作,即打开文件操作的基本功能是在用户进程和指名文件之间建立一条通路,它将相应文件的FCB读入内存,并返回给用户一个文件描述符,以后,用户对文件进行的任何操作,都只需使用文件描述符而非路径名,而系统则无需再对各级目录进行检索,便可通过文件描述符直接找到内存中的文件FCB,然后为用户进行相应的操作。可见,open操作的主要目的是提高对文件访问的速度。显式的close操作,即关闭文件操作的基本功能是切断用户进程和指定文件间的通路,如果文件FCB的内容被修改过,则需要将它写回磁盘,然后释放内存FCB和文件描述符。
(2)可以取消显式的open和close操作。具体做法是:在首次使用某个文件时,由系统自动打开该文件,并在相关作业终止时自动关闭该文件:或者干脆取消open和dose操作,而在每次读写文件时,都通过路径名来检索目录,然后再进行相应操作。
(3)取消显式的open与close操作将增加系统的开销。首先,用户每次使用路径名来读写文件时,系统都必须检查该文件是否EA经打开:其次,当一个文件使用完毕后,只要相应的作业没终止,则它的FCB将仍然占用内存资源,这不仅是对资源的浪费,而且还有可能造成其他文件因得不到该资源而无法打开的现象。如果,每次对文件操作前,都必须先通过路径名到外存上去检索目录,则开销会更大。
10.考虑这样一个文件系统,其中文件可被删除,并且在指向它的链路仍然存在的情况下可重新使用其盘空间.若在同一盘空间建立一新文件,将会出现什么问题?如何避免该问题?
答:令F1是老文件,F2是新文件,那么,希望通过现有链路访问文件Fl的用户实际上访问的是文件F2；这里使用的是对文件Fl的存取保护而不是与文件F2相关的存储保护。采用删除指向一个已删除文件的所有链路的方法可避免该问题。这可用几种方式实现:
(1)保留一张记录指向一个文件的所有链路的表,当删除该文件时,就删除这些链路；
(2)保留这些链路,当试图访问一个已删除的文件时,就删去相应的链路；
(3)保留一个文件访问表,仅当对某文件的访问被删除后或所有链路都被删除之后才删除文件访问表中的相应文件。
11.在许多系统中,一个授权的用户可像对通常的文件那样读、写子目录。
(1)这样做会出现什么保护问题?
(2)试提出一个处理这些问题的方案。
答：(1)保存在目录项目中的信息之一是文件位置，如果用户可以修改这个位置信息,那么,他也会访问其他文件,从而违犯了存取保护的规定。
(2)不允许用户直接向子目录写人信息,而应提供系统操作来完成这些事情。
12.能否用一个可使用任意长度文件名的单级目录结构来模拟多级目录结构?若能,则说明如何模拟？如果文件名限制为7个字符,你的方案应作哪些修改?
答：如果允许使用任意长的名字,则可模拟多级目录结构.例如,可用符号"."指明子目录的结束.这样,名字h.lisp.Fl指明Fl是子目录lisp中的文件,而lisp是根目录h的文件。
若名字限制为7个字符,那么上面的方案可能无用.一个变通的方案是使用一个特定的文件作为符号表(目录).它将随意长的文件名(如h.lisp.Fl)映射为较短的文件名(如XX00101),然后将后者作为实际的文件名来使用。
13.信息在外存空间的排列方式也会影响存取等待时间。考虑几个逻辑记录A、B、C、…、J,它们被存放于磁盘上,每个磁道存放10个记录,安排如下：
物理块
1
2
3
4
5
6
7
8
9
10
逻辑记录
A
B
C
D
E
F
G
H
I
J
假定要经常顺序处理这些记录,旋转速度为2Oms/转,处理程序读出每个记录后花4ms
进行处理,试问:
(1)处理的总时间为多少?
(2)考虑对信息的分布进行优化,信息分布优化后,处理的总时间为多少?
物理块
1
2
3
4
5
6
7
8
9
10
逻辑记录
A
H
E
B
I
F
C
J
G
D
答:在本题中,设备旋转速度为20ms/转,每道存放10个记录,因此读出1个记录的时间是:20/10=2ms
(1)对于第一种记录分布情况,读出并处理记录A需要6ms,则此时读写头已转到了记录D的开始处,因此为了读出记录B,必须再转一圈少两个记录(从记录D到记录B)。后续8个记录的读取及处理与此相同,但最后一个记录的读取与处理只需6ms。于是,处理10个记录的总时间为:9×(2+4+16)+(2+4)=204ms
(2)对于第二种记录分布情况,读出并处理记录A后,读写头刚好转到记录B的开始处,因此立即就可读出并处理,后续记录的读取与处理情况相同。故处理10个记录的总时间为:
10×(2+4)=6Oms
14.有一个交叉存放信息的磁盘,信息在其上的存放方法如图7.8所示。每磁道有8个扇区,每扇区512字节,旋转速度为3000转/分。假定磁头已在要读取信息的磁道上,0扇区转到磁头下需要1/2转,且设备对应的控制器不能同时进行输入/输出,在数据从控制器传送至内存的这段时间内,从磁头下通过的扇区数为2,问依次读出一个磁道上的所有扇区需要多少时间?其数据传输速度为多少?
分析：在磁盘数据的读取过程中,当控制器将整块信息从设备读入其内部缓冲区后,再将缓冲区中的数据传送至内存。在数据从控制器传送至内存的同时,后续扇区中的数据将从磁头下通过并传输到控制器。但某些简单的控制器不能同时进行输入/输出,因此在数据从控制器传送至内存的这段时间内,从磁头下通过的扇区信息丢失。为此,应将数据以交叉方式存放,信息块应间隔的扇区数与控制器传输信息至内存的速度相关。
答:从图7.8可知,信息块之间的间隔为2个扇区。
由题目所给条件可知,旋转速度为:3000转/分=50转/秒,即2Oms/转。
读一个扇区需要时间:20/8=2.5ms
读一个扇区并将扇区数据送入内存需要时间:2.5×3=75ms
读出一个磁道上的所有扇区需要时间:20/2+8×75=7Oms=0.07s
每磁道数据量:8×512=4KB
数据传输速度为:4KB/0.07=57.lKB/秒所以,依次读出一个磁道上的所有扇区需要0.07秒。其数据传输速度为57.1KB/秒。
15.有一文件系统如图7.10(a)所示。图中的框表示目录,圈表示普通文件。根目录常驻内存,目录文件组织成链接文件,不设文件控制块,普通文件组织成索引文件。目录表目指示下一级文件名及其磁盘地址(各占2个字节,共4个字节).若下级文件是目录文件,指示其第一个磁盘块地址。若下级文件是普通文件,指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级目录文件中的次序在图中为从左至右。每个磁盘块有512字节,与普通文件的一页等长。
(a)
该文件的有关描述信息
磁盘地址
磁盘地址
磁盘地址
︰
磁盘地址
磁盘地址
磁盘地址
（b）
图7.10 文件系统结构示意图及普通文件的控制块组织普通文件的文件控制块组织如图110(b〉所示。其中,每个磁盘地址占2个字节,前10个地址直接指示该文件前10页的地址。第11个地址指示一级索引表地址,一级索引表中每个磁盘地址指示一个文件页地址:第12个地址指示二级索引表地址,二级索引表中每个地址指示一个一级索引表地址:第13个地址指示三级索引表地址,三级索引表中每个地址指示一个二级索引表地址。
(1)一个普通文件最多可有多少个文件页?
(2)若要读文件J中某一页,最多启动磁盘多少次?
(3)若要读文件W中的某一页,最少启动磁盘多少次?
(4)就(3〉而言,为最大限度减少启动磁盘的次数,可采用什么方法?此时,磁盘最多启动多少次?
答:(1)由题目中所给条件可知,磁盘块大小为512字节,每个磁盘地址占2个字节。因此,一个一级索引表可容纳256个磁盘地址。同样地,一个二级索引表可容纳256个一级索引表地址,一个三级索引表可容纳256个二级索引表地址。这样,一个普通文件最多可有页数为：
10+256+256×256+256×256×256=16843018
(2)从图7.10(a)中可以看出,目录文件A和目录文件D中,目录项都只有两个,因此这两个目录文件都不需拉链。若要读文件J中的某一页,首先从内存的根目录中找到目录文件A的磁盘地址,将其读入内存(第1次访问磁盘)。然后再从目录A中找出目录文件D的磁盘地址,并将其读入内存(第2次访问磁盘〉。从目录D中找出文件J的文件控制块地址,将文件J的文件控制块读入内存(第3次访问磁盘〉。在最坏情况下,要访问页的磁盘地址需通过三级索引才能找到,这时要三次访问磁盘才能将三级索引表读入内存(第4、5、6次访问磁盘〉。最后读入文件J中的相应页〈第7次访问磁盘〉。
由此可知,若要读文件J中的某一页,最多启动磁盘7次。
(3)从图7.10(a〉中可以看出,目录文件C和目录文件U中,目录项数目较多,若目录项数超过127(512/4一1=127),则目录文件的读入可能需要多次磁盘读(因目录文件组织成链接文件)。在最好情况下,所找的目录项都在目录文件的第一个磁盘块中。若要读文件W中的某一页,首先从内存的根目录中找到目录文件C的磁盘地址,将其读入内存(第1次访问磁盘〉。在最好情况下,能从目录C的第一个磁盘块中找出目录文件I的磁盘地址,并将其读入内存(第2次访问磁盘〉。从目录I中找出目录文件P的的磁盘地址,将其读入内存〈第3次访问磁盘〉。从目录P中找到目录文件U的磁盘地址,将其读入内存(第4次访问磁盘〉。在最好情况下,能从目录U的第一个磁盘块中找出文件W的文件控制块地址,将文件W的文件控制块读入内存(第5次访问磁盘〉。在最好情况下,要访问的页在前10页中,这时可直接得到该页的磁盘地址。最后读入文件W中的相应页(第6次访问磁盘〉。
由此可知,若要读文件W中的某一页,最少启动磁盘6次。
(4)由于通过文件控制块访问文件所需的访问磁盘次数无法改变,要减少访问磁盘的次数,只有通过减少访问目录文件的次数来达到。为最大限度地减少启动磁盘的次数,可以将文件W直接链接在根目录的最左端(或其目录项在根目录的前127个项内〉。这样,若要读文件W中的某页时,首先从内存的根目录中找到文件W的文件控制块地址,将文件W的文件控制块读入内存〈第1次访问磁盘)。在最坏情况下,要访问页的磁盘地址需通过三级索引才能找到,这时要三次访问磁盘才能将三级索引表读入内存(第二3、4次访问磁盘〉。最后读入文件W中的相应页(第5次访问磁盘〉。
由此可知,若将文件W直接链接在根目录的最左端,要读文件J中的某一页,最多启动磁盘5次。
7.4习题
7.4.1 基本题
一．判断题(正确的在括号中记√,错误的记×)
1.如果用户极其频繁地访问其当前目录中的文件,那么应将该目录放在内存。 ( )
2,打开文件操作的目的是建立用户和文件的联系。 （ ）
3.连续文件的缺点之一是不便于扩充。 ( )
4.文件保护就是禁止对文件的进行存取。 （ ）
5.树结构目录的层次和隶属关系清晰,有利于文件和目录的共享。 ( )
6.多重索引结构适合于有大量大文件的系统。 ( )
7.隐式链接结构可以提高文件存储空间的利用率,但不适合文件的随机存取。 ( )
8.访问控制矩阵比访问控制表更节约空间。 ( )
9.对物理文件来说,顺序文件必须采用连续分配方式,而链接文件和索引文件可采用离散分配方式。 ( )
10.文件系统中,所有文件的目录信息集中存放在内存的一个特定区域中。 ( )
二.单项选择题
1.文件系统是指___________。
A.文件的集合 B.文件的目录
C.实现文件管理的一组软件 D.文件、管理文件的软件及数据结构的总体
2.按逻辑结构可把文件分为记录式文件和________两类。
A.读、写文件 B.只读文件 C.索引文件 D.流式文件
3.文件系统中文件存储空间的分配是以_______为单位进行的。
A.字 B.块 C.字节 D.文件
4.从用户角度看,引入文件系统的主要目的是_______。
A.实现虚拟存储 B.保存系统文档
C.实现对文件的按名存取 D,保存用户和系统文档
5.一个文件系统采用二级目录结构,它的两张目录分别是__________。
A.系统目录和子目录 B.根目录和子目录
C.主目录和用户目录 D.用户目录和子目录
6、Hash文件采用的寻址方法是________。
A.计算 B.比较 C.索引 D.顺序
7.文件系统中用__________管理文件。
A.作业控制块 B.外页表 C.目录 D.软硬件结合的方法
8.可以解决文件重名问题的最简单的文件目录结构是______。
A.单级目录 B.树型结构目录 C.二级目录 D.便于共享的目录
9.为了对文件系统中的文件进行安全管理,任何一个用户在进入系统时都必须进行注册,这一级安全管理是_________安全管理。
A.系统级 B.目录级 C.用户级 D.文件级
10、可以实现文件保护的方案是_______。
A.用户权限表 B.在段中设置段长 C.删除文件 D.使用界限寄存器
11.为了解决不同用户文件的"命名冲突"问题,通常在文件系统中采用______。
A.约定的方法 B.多级目录 C.路径 D.索引
12.一个文件的绝对路径名是从_________开始,逐步沿着每一级子目录向下追溯,最后到指定文件的整个通路上所有子目录名组成的一个字符串。
A.当前目录 B.根目录 C.多级目录 D.二级目录
13.空白文件目录法用于______________。
A.主存空间的管理 B.文件存储空间的管理
C.虚存空间的管理 D.外设的分配与回收
14.对一个文件的访问,常由________共同限制。
A.用户访问权限和文件属性 B.用户访问权限和用户优先级
C.优先级和文件属性 D.文件属性和口令
15.使用文件前必须先_________文件。
A.命名 B.建立 C.打开 D.备份
16.文件使用完毕后应该________。
A.释放 B.关闭 C.卸下 D.备份答,B
17.一般来说,文件名及属性可以收纳在__________中以便查找。
A.目录 B.索引 C.字典 D.作业控制块
18.最常用的流式文件是字符流文件,它可看成是________的集合。
A.字符序列 B.数据 C.记录 D.页面
19.在文件系统中,文件的不同物理结构有不同的优缺点。在下列文件的物理结构中,_____不具有直接读写文件任意一个记录的能力。
A.顺序结构 B.链接结构 C.索引结构 D.Hash结构
20.在下列文件的物理结构中,_______不利于文件长度动态增长。
A.顺序结构 B.链接结构 C.索引结构 D.Hash结构
21.如果文件采用直接存取方式且文件大小不固定,则宜选择________文件结构。
A.直接 B.顺序 C.随机 D.索引
22.文件系统采用二级目录结构,这样可以__________。
A.缩短访问文件存储器时间 B.实现文件共享
C.节省主存空间 D.解决不同用户之间的文件名冲突问题三．填空题
1.组织目录时可采取的数据结构有________、______、______、____和______。
2.利用Hash法查找文件时,如果目录中相应的目录项是空,则表示_________;如果目录项中的。文件名与指定的文件名相匹配,则表示_______;如果目录项中的文件名与指定的文件名不匹配,则表示______________。
3.分配磁盘空间的三种主要方法是______、_______和__________。
4.在文件系统中是利用______来管理文件的,为了允许不同用户的文件使用相同的文件名,通常文件系统中采用______;在目录文件中的每个目录项通常就是_______。
5.毗连文件分配空间中常用的适配方法是________、________和__________。
6.在下列物理文件中,_______将使文件顺序访问的速度最快;_________最不适合对文件进行随机访问;____________能直接将记录键值转换成物理地址。
7.目录上的主要操作有______、_____、_____、_____和______。
8.文件系统最基本的目标是_________,它主要是通过__________功能实现的,文件系统所追求的最重要的目标是_______________。
9．基于磁盘文件模式,将文件视为编上号的块的文件存取方法称为_______。
10.在文件系统中可命名的最小数据单位是_________,用户以________为单位对文件进行存取、检索等,对文件存储空间的分配则以_________为单位。
11.二级目录结构由_______目录和各用户自己的__________目录组成.
12.索引文件大体上由______区和______区构成。其中______区一般按关键字的顺序存放。
13.对操作系统而言,打开文件广义指令的主要作用是装入_____目录表。
14.操作系统实现按名存取进行检索等关键在于解决文件名与______的转换。
15.文件的物理组织有顺序、_____和索引。
16._______是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏。
17.磁盘与主机之间传递数据是以_____为单位进行的。
18.在文件系统中,要求物理块必须连续的物理文件是_______。
19.文件系统为每个文件另建立一张指示逻辑记录和物理块之间的对应关系表,由此表和文件本身构成的文件是_______。
20.______算法选择与当前磁头所在磁道距离最近的请求作为下一次服务的对象.
21.访问磁盘时间由三部分组成,即_____、_________和 __________。
22.文件的结构就是文件的组织形式,从用户观点出发所看到的文件组织形式称为文件的________;从实现观点出发,文件在外存上的存放组织形式称为文件的_________。
四．简答题
1.什么是文件、文件东统?文件系统有哪些功能?
2.什么是文件的逻辑结构?什么是记录?
3.文件的物理结构有哪几种?为什么说串联文件结构不适于随机存取?
4.什么是文件系统?通常由哪几部分组成?
5.设置文件目录的目的是什么？
6.文件的逻辑结构与物理结构有何不同?
7.考虑一个支持毗连、链接和索引分配策略的系统,对一给定文件,决定采用每种策略时的条件是什么?
8.假定一系统中,自由空间通过自由空间表管理:
(1)如果指向该自由空间表的指针丢失了,那么,系统能否重构该自由空间表?
(2)提出一种不因内存故障而丢失该指针的方案。
9.当用户自愿撤离或终止一个作业时,某些系统自动删除所有相关的文件,除非用户明显地请求保留它们:而另一些系统则保留所有文件,除非用户明显的请求删除它们；试叙述这两种途径的特点。
10.文件一般按什么分类?可以分为哪儿类?
11.什么是文件目录?文件目录中包含哪些信息?
12.二级目录和多级目录的好处是什么?符号文件目录表和基本文件目录表是二级目录吗?
13.有些系统通过保留文件的单一副本来提供文件共享,有些系统则通过对每一共享文件的用户各保留一个副本的方式来提供文件共享,试叙述它们各自的优缺点。
论述题：
1.什么是文件?它包含哪些内容及特点?
2.文件系统要解决哪些问题?
3.文件系统中常采用的物理结构有哪些?
4.试述文件管理系统设置打开文件、关闭文件命令的原因。
5.常用的文件存储设备的管理才法有哪些?试述主要优缺点。
6.试述成组链法的基本原理,并描述成组链法的分配与释放过程。
7.删除文件时,存放文件的盘块常常返回到空闲盘块链中,有些系统同时清除盘块中的内容,而另一些系统则不清除,请对这两种方式加以比较。
8.在树形目录结构中,利用链接方式共享文件有何好处?
9.文件存取控制方式有哪几种?试比较它们各自的优缺点。
10.假定磁带记录密度为每英寸800字符,每一逻辑记录为160个字符,块间隙为0.6英寸。今有1500个逻辑记录需要存储,试计算磁带利用率?若要使磁带空间利用率不少于50%,至少应以多少个逻辑记录为一组?
11.设磁盘组共有n个柱面,编号顺序为0、1、2、…、n一1;共有m个磁头,编号顺序为0、1、2、…、m一1;每个磁道内的k个信息块从1开始编号,依次为1、2、…、k。现用x表示逻辑磁盘块号,用a、b、c分别表示任一逻辑磁盘块的柱面号、磁头号、磁道内块号,则x与a、b、c可通过如下公式进行转换:
x=k×m×a+k×b+c
a =(x-1〉DIV (k×m)
b=((x-1〉MOD (k×m)) DIV K
c =((x-1) MOD k×m)）MOD K+1
若某磁盘组为n=200,m=20,K=10,问:
(1)柱面号为185,磁头号为12,道内块号为5的磁盘块的逻辑磁盘块号为多少?
(2)逻辑磁盘块号为1200,它所对应的柱面号、磁头号及磁道内块号为多少?
(3)若每一磁道内的信息块从0开始编号,依次为0、1、…、k-1,其余均同题设,试写出x与a、b、c之间的转换公式。
12.假定磁盘块的大小为lk,对于540M的硬盘,其文件分配表FAT需要占用多少存储空间?当硬盘容量为1.2G时,FAT需要占用多少空间?
13.如磁盘的每个磁道分成9个块,现有一文件共有A、B、…、I 9个记录,每个记录的大小与块的大小相等,设磁盘转速为27ms/转,每读出一块后需要2ms的处理时间。若忽略其他辅助时间,试问:
(1〉如果顺序存放这些记录并顺序读取,处理该文件要多少时间?
(2〉如果要顺序读取该文件,记录如何存放处理时间最短?
14.有一计算机系统利用图7.9所示的位示图(行号、列号都从0开始编号)来管理空闲盘块。如果盘块从1开始编号,每个盘块的大小为1KB。
(1)现要为文件分配两个盘块二试具体说明分配过程。
(2)若要释放磁盘的第300块,应如何处理?
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0
1
2
3
4
5
6
图7.9位示图
15.许多操作系统中提供了文件重命名功能,它能赋予文件一个新名字。若进行文件复制,并给复制文件起一个新名字,然后删除旧文件,也能达到给文件重命名的目的。试问这两种方法在实现上有何不同?
16.某软盘有40个磁道,磁头从一个磁道移至另一磁道需要6ms。文件在磁盘上非连续存放,逻辑上相邻数据块的平均距离为13磁道,每块的旋转延迟时间及传输时间分别为100ms、25ms,问读取一个100块的文件需要多少时间?如果系统对磁盘进行了整理,让同一文件的磁盘块尽可能靠拢,从而使逻辑上相邻数据块的平均距离降为2磁道,这时读取一个100块的文件需要多少时间?
17.一个树形结构的文件系统如图7.9所示:
该图中的框表示目录,圈表示文件。
(1)可否进行下列操作:
a.在目录D中建立一个文件,取名为A。
b.将目录C改名为A。
(2)若E和G分别为两个用户的目录:
a.用户E欲共享文件Q,应有什么条件,如何操作?
b.在一段时间内,用户G主要使用文件S和T。为简便操作和提高速度,应如何处理?
c.用户E欲对文件I加以保护,不许别人使用,能否实现?如何实现?
图7.9 文件系统结构示意图
18.使用文件系统时,通常要显式地进行OPEN,CLOSE操作。
〈1〉这样做的目的是什么?
〈2〉能否取消显式的OPEN,CLOSE操作?应如何做?
〈3〉取消显式的OPEN,CLOSE操作有什么不利?
6.4自测练习答案一．判断题
1.√ 2,√ 3,4.× 5,× 6.× 7,√ 8,× 9,√ 10,×
二．选择题
1.D 2.D 3.B 4.C 5.C 6.A 7.C 8.C 9.A 10.A 11.B
12.B 13.B 14.A 15.C 16.B 17.A 18.A 19.B 20.A 21.D 22.D
三．填空
1.线性表 链接表 排序表 链接二叉树 杂凑表
2.系统中无指定文件名 找到了指定文件 发生了冲突
3.毗连分配 链接分配 索引分配
4.目录 多级目录 FCB
5.首次适配 最佳适配 最差适配
6.顺序文件 隐式链接文件 直接文件
7.查找文件 创建文件 删除文件 列文件名 复制文件
8.按名存取 目录管理 提高对文件的存取速度
9.随机存取方法.
10,数据项 记录 文件
11.主文件目录 用户文件目录组成
12.索引 数据 索引
13.文件
14.文件的存储地址
15.链接
16.文件保护
17.数据块
18.顺序文件
19.索引文件
20.最短寻道时间优先
21.寻道时间 旋转延迟时间 传输时间
22.逻辑结构 物理结构四、简答题
1.答:在计算机系统中,文件被解释为一组赋名的相关字符流的集合,或者是相关记录的集合。
文件系统是操作系统中与管理文件有关的软件和数据。
文件系统的功能是为用户建立文件,撤销、读写修改和复制文件,以及完成对文件的按名存取和进行存取控制。
2.答:文件的逻辑结构就是用户可见的结构,可分为字符流式的无结构文件和记录式的有结构文件两大类。
记录是一个具有特定意义的信息单位,它由该记录在文件中的逻辑地址(相对位置)与记录名所对应的一组关键字,属性及其属性值所组成。
3.答:文件的物理结构是指文件在存储设备上的存放方法。常用的文件物理结构有连续t
文件,串联文件和索引文件3种。
串联文件结构用非连续的物理块来存放文件信息。这些非连续的物理块之间没有顺序关系,链接成一个串联队列。搜索时只能按队列中的串联指针顺序搜索,存取方法应该是顺序存取的。否则,为了读取某个信息块而造成的磁头大幅度移动将花去较多的时间。因此,串联文件结构不适于随机存取。
4.答:文件系统即文件管理系统,它在操作系统中是负责管理和存取文件信息的软件。通常它由三部分组成：（1）与文件管理有关的软件;(2)被管理的文件;(3)实施文件管理所需的数据结构。
5.答：由于文件系统中文件的种类多、数量大，所以设置文件目录的目的是为了便于查找文件、操作文件、共享文件及保护文件。
文件目录组织有三种形式:（1）简单（一级）目录；（2）二级目录；（3）树型目录。
6.答:文件的逻辑结构是文件在用户面前所呈现的形式。文件的物理结构,是文件在文件存储器上的存放形式。
7.答。采用毗连分配策略的条件是,对文件的访问通常是顺序的,而且文件比较小；
采用链接分配策略的条件是,文件较大且通常是顺序访问的；
采用索引分配策略的条件是,文件较大并通常是随机访问的。
8.答(1)为了重构自由空间表,必须执行"无用单元收集程序"。这需要查寻整个目录结构以判定哪些页面已分配给作业,而将那些未被分配的页面重新链结为一个自由空间表。
(2)可将自由空间表指针存取在磁盘上。
9.答:对于前一种途径,由于不必保留不(再)需要的文件,可使每一用户所需的文件空间变成最小.后一种途径则对用户更为安全,因为用户不会由于疏忽没有保存文件而使文件丢失。
10.答:文件系统一般按性质,用途,组织形式,文件中的信息流向或文件的保护级别等分类。
按文件的性质与用途可以分为系统文件,库文件和用户文件。按文件的组织形式可以分为普通文件,目录文件和特殊文件。按文件中的信息流向可以分为输入文件,输出文件和输入/输出文件。按文件的保护级别可以分为只读文件,读写文件,可执行文件和不保护文件。
11.答:一个文件的文件名和对该文件实施控制管理的说明信息称为该文件的说明信息,又称为该文件的目录。
文件目录中包含文件名、与文件名相对应的文件内部标识以及文件信息在文件存储设备上第一个物理块的地址等信息。另外还可能包含关于文件逻辑结构、物理结构、存取控制和管理等信息。
12.答:二级目录和多级目录的好处是可以减少文件命名冲突和提高对自录表的搜索速度。
符号文件目录表和基本文件目录表是实现文件共享的一种方法,并不是二级目录。
13.答:保留单一副本,对于一个文件的多次并发更新,可能导致用户得到不正确的信息,并使结果文件处于不正确的状态.保留多个副本则浪费了一些存储空间而且各副本彼此可能会不一致。
7.4.2解析题一．论述题
1.答:文件是信息的一种组织形式,是存储在外存上的具有标识名的一组相关信息集合。
文件包含的内容有:源程序、-二进制代码、文本文档、数据、表格、声音和图像等。
文件的特点如下:
（1）文件具有保存性,它被存储在某种存储介质上,长期保存和多次使用。
（2）文件是按名存取的,每个文件具有惟一的标识名,通过标识名〈文件名〉来存取文件中的信息,而不需了解文件在存储介质上的具体物理位置。
（3）文件的内容是一组信息的集合,信息可以是源程序、二进制代码、文本文档、数据、表格、声音和图像等。
2.答:文件系统的主要目标是提高存储空间的利用率,它要解决的主要问题有:完成文件存储空间的管理,实现文件名到物理地址的转换,实现文件和目录的操作,提供文件共享能力和安全措施,提供友好的用户接口。文件系统向用户提供了有关文件和目录操作的各种功能接口和系统调用,如命令接口、程序接口和交互接口等。
3.答:文件的物理结构侧重于提高存储空间的利用率和减少存取时间,它对文件的存取方法有较大的影响。由于外存设备的不同,文件被划分为大小相等的物理块,它是存放文件信息或分配存储空间的基本单位,也是文件系统与主存之间传输和交换信息的基本单位。物理块大小一般是固定的,物理块与逻辑记录的关系可以是:一个物理块可以存放一个或多个逻辑记录,或者多个物理块存放一个逻辑记录。
目前操作系统中常采用如下物理结构文件:
(1)顺序文件:它是按照逻辑文件中的记录顺序,依次把逻辑记录存储到连续的物理块中而形成的文件。
(2)链接文件:它的物理块不是连续的,也不必顺序排列,但每个物理块中设置一个指针,指向下一个物理块的地址,这样,所有的物理块被链接起来,形成一个物理文件,称为链接文件或串联文件。
(3)索引文件:它是文件系统为每个文件另外建立一张指示逻辑记录和物理块之间的对应关系表,此表称为索引表,文件本身和索引表组成的文件称为索引文件。
4.答:操作系统需要处理大量用户文件,而访问一个文件需要查询目录,有时甚至需要多次查询目录。由于文件目录与文件一起存放在辅存上,当存取文件时,必须先到辅存中读取文件目录信息,从中获得文件的存放地址,然后再去存取文件。这样一来,文件信息的存取将花费很多时间。如果将整个文件目录放入主存,虽然可以提高存取速度,但这需要占用大量主存空间,显然这也是不可取的。实际上,在一段时间内使用的文件数总是有限的,因此只要将目录中当前要使用的那些文件的目录表目复制到内存中就可以了。这样既不占用太多的主存空间,又可显著提高查询文件目录的速度。为此,大多数操作系统中设置了两个文件操作:打开文件和关闭文件。打开文件操作完成的功能是将文件的有关目录信息复制到主存活动文件表中,以建立用户和这个文件的联系。关闭文件操作的功能是用户宣布这个文件当前不再使用,系统将其在主存中的相应目录信息删去,因而也就切断了用户同这个文件的联系。
5.答:文件存储设备的管理实质上是一个空闲块的组织和管理问题。有3种不同的空闲块管理方法。即空闲文件目录,空闲块链和位示图。
空闲文件目录管理方法就是把文件存储设备中的空闲块的块号统一放在一个称为空闲文件目录的物理块中,其中空闲文件目录的每个表项对应一个由多个空闲块构成的空闲区。量该方法实现简单,适于连续文件结构的文件存储区的分配与回收。但是由于回收时不进行合并,所以使用该方法容易产生大量的小块空闲区。
空闲块链法把文件存储设备上的所有空闲块链接在一起,从链头分配空闲块,把回收的空闲块插入到链尾。该方法不占用额外的空间,但实现复杂。
位示图法是从内存中划出若干字节,每个比特位对应一个物理块的使用情况。如果该位为0则表示对应的是空闲块,为1则表示对应的物理块已分配出去。位示图法在查找空闲块时无需启动外设,但要占用内存空间。
6.答:成组链法首先把文件存储设备中的所有空闲块按50块一组分组。组的划分是从后往前进行的。其中,每组的第一块用来存放前一组中各块的块号和总块数。第一组为49块。
最后一组的物理块号与总块数只能放在管理文件存储设备用的文件资源表中。
分配和释放过程:
首先,系统在初始化时把文件资源表复制到内存,从而把文件资源表中放有最后一组空闲块块号与总块数的堆找载入内存,并使得空闲块的分配与释放可以在内存中进行。用于空闲块分配与回收的堆楼有校指针Ptr,且Ptr的初值等于该组空闲块的总块数。当申请者申请n块空闲块时,按照后进先出的原则,分配程序在取走Ptr所指的块号之后,再做Ptr=Ptr-1的操作。这个过程一直持续到所要求的n块空间都分配完毕或堆校中只剩下最后一个空闲块的块号时。当堆楼中只剩下最后一个空闲块号时,系统启动设备管理程序,将该块中存放的下一组的块号与总块数读入内存之后再把该块分配给申请者。然后,系统重新设置Ptr指针,并继续为申请者分配空间。
文件存储设备的最后一个空闲块中设置有尾标识,以指示空闲块分配完毕。
如果用户进程不再使用有关文件并删除这些文件时,回收程序回收这些文件占用的物理块。成组链法的回收过程仍利用文件管理堆械进行。在回收时,回收程序先做Ptr=Ptr+1操作,然后把回收的物理块号放入当前Ptr指针所指的位置。如果Ptr等于50,则表示该组已经全部回收。此时,如果还有物理块需要回收的话,那么回收该块并启动I/0设备管理程序,把回收的50个块号与块数写入新回收的块中。然后将Ptr置1另起一个新组。对空闲块的分配和释放必须互斥进行。
7.答:(1)从性能上考虑,因后一种方式在删除文件时减少了访问磁盘的次数,故其速度比前一种方式更快。
(2)从安全性上考虑,把一个内容没有清除的盘块分配给下一个用户使用,则有可能使其获取盘块中的内容,故前一种方式比后一种方式更安全。
(3)从方便性上考虑,如果盘块中的内容没被清除,则当用户因误操作而删除文件时,他有可能通过某种办法恢复被删除的文件,故后一种方式更为方便。
8.答:利用链接方式共享文件主要有以下几方面的好处:
(1)方便用户:这种共享方式允许用户按自己的方式将共享文件组织到某个子目录下;并赋予它新的文件名,从而使用户可更方便地管理和使用共享文件。
(2)防止共享文件被删除。每次链接时,系统将对索引结点中的链接计数字段i-_nlink
进行加1操作,而删除时,必须先对它进行减1操作,只有当i_nlink的值为0时,共享文件才被真正删除,因此可避免用户仍要共享的文件被删除的现象。
(3)加快检索速度。为了加快检索文件的速度,一般系统都引入了当前目录的概念。用户在设置了工作目录后,若共享文件已被链接到该工作目录下,则系统无需再去逐级检索树形目录,从而可加快检索速度。
9.答:文件存取控制方式一般有存取控制矩阵、存取控制表、口令和密码术4种方式。
存取控制矩阵方式以一个二维矩阵来进行存取控制。而且矩阵的一维是所有的用户,另一维是所有的文件。对应的矩阵元素则是用户对文件存取控制权。存取控制矩阵的方法在概念上比较简单,但是当用户和文件较多时,存取控制矩阵将变得非常庞大,从而时间和空间的开销都很大。
存取控制表以文件为单位,把用户按某种关系划分为若干组,同时规定每组的存取限制。这样,所有用户组对文件权限的集合就形成了该文件的存取控制表。存取控制表方式占用空间较小,搜索效率也较高,但要对用户分组,引入了额外的开销。
口令方式有两种。一种是当用户进入系统,为建立终端进程时获得系统使用权的口令。另一种口令方式是,每个用户在创建文件时,为每一个创建的文件设置一个口令,且将其置于文件说明中。当任一用户想使用该文件时,都必须首先提供口令。口令方式比较简单,占用的内存单元以及验证口令所费时间都非常少。不过,相对来说,口令方式保密性能较差。
密码方式在用户创建源文件并写入存储设备时对文件进行编码加密,在读出文件时对其进行译码解密。加密方式具有保密性强的优点。但是,由于加密解密工作要耗费大量的处理时间,因此,加密技术是以牺牲系统开销为代价的。
10.答:(1)因磁带记录密度为每英寸800字符,则一个逻辑记录占据的磁带长度为:
160/800=0.2英寸
1500个逻辑记录要占据的磁带长度为:
(0.2+0.6〉×1500=1200英寸磁带利用率为,02/(0.2+0.6)=25%
(2)要使磁带利用率不少于50%,即磁带利用率大于或等于50%,则一组逻辑记录所占的磁带长度应与间隙长度相等,所以一组中的逻辑记录数至少为:
0.6/0.2=3
11.答：(1)由上述公式可得,逻辑磁盘块号x为:
x=k×m×a+k×b+c=10×20×185+10×12+5=37125
所以,柱面号为185,磁头号为12,磁道内块号为5的磁盘块的逻辑磁盘块号为37125。
(2)由上述公式可得
a =(x-1)DIV (k×m)=(1200-l) DIV (10×20)=1199 DIV 200=5
b =((x-1) MOD (k×m)) DIV K=((1200-1)MOD (10×20)) DIV 10=(1199 MOD 200) DIV lO
=199 DIV 10=19
c =((x-1) MOD (k×m)) MOD K+1=((1200-1) MOD (10×20)) MOD 10+1
=(1199 MOD 200〉MOD 10+1
=199 MOD 10+1
=9+1
=10
所以,逻辑磁盘块号为1200的盘块所对应的柱面号是5、磁头号是19、磁道内块号是10。
(3)对于磁盘组空间中的任一磁盘块,除了它的磁道内块号比原来小1以外,别的参数值均无变化,因此只要对转换公式中出现磁道内块号的公式作相应修改即可,x与a、b、c之间的转换公式如下:
x=k×m×a+k×b+c+1
a =(X-1) DIV (k×m)
b =（x-1）MOD (k×m)) DIV k
c =((x-1)MOD (k×m)) MOD K
12.分析：文件分配表FAT是一个数据结构,用在以链接方式存储文件的系统中记录磁盘分配和跟踪空白磁盘块。该表整个磁盘仅设一张,其结构如图7.7所示。表的序号是物理块号,从O开始直至N-1(N为盘块总数)。在每个表项中,存放下一个盘块号(即表项的内容为存放文件数据的下一个盘块号)。文件的首地址(第一个盘块号)存放在目录中。因此,从目录中找到文件的首地址后,就能找到文件在磁盘上的所有存放地址.例如图7.7中文件存放的盘块号依次为2、5、7。
物理块号
0 1 2 3 4 5 6 7 8 9
5
7
∧
某文件首块地址
图7.7 文件分配表答:由题目所给条件可知,硬盘大小为540M,磁盘块的大小为胀,所以该硬盘共有盘块:
540M/lk=540K(个)
又512K<540K<1024K故540K个盘块号要用20位二进制表示,即文件分配表的每个表目为2.5个字节。FAT要占用的存储空间总数为：25×540K=1350K
当硬盘大小为1.2G,硬盘共有盘块：1.2G/1K=1.2M〈个)
又
lM<1.2M<2M故1.2M个盘块号要用31位二进制表示。为方便文件分配表的存取,每个表目用32位二进制表示,即文件分配表的每个表目大小为4个字节。
FAT要占用的存储空间总数为:4×1.2M=4.8M
13.答:由题目所给条件可知,磁盘转速为每转27ms,每磁道存放9个记录,因此读出1个记录的时间是:27/9=3ms
(1)读出并处理记录A需要5ms,此时读写头己转到了记录B的中间,因此为了读出记录B,必须再转将近一圈〈从记录B的中间到记录B〉。后续8个记录的读取及处理与此相同,但最后一个记录的读取与处理只需5ms。于是,处理9个记录的总时间为:8×(27+3)+(3+2)=245ms
（2)由于读出并处理一个记录需要5ms,当读出并处理记录A时,不妨设记录A放在第1个盘块中,读写头已移到第2个盘块的中间,为了能顺序读到记录B,应将它放到第3个盘块中,即应将记录按如下顺序存放:
盘块
1
2
3
4
5
6
7
8
9
记录
A
F
B
G
C
H
D
I
E
这样,处理一个记录并将磁头移到下一个记录的时间是:
3(读出)+2(处理)+1(等待〉=6ms
所以,处理9个记录的总时间为:6×8+5=53ms
14.答:(1)为某文件分配两个盘块的过程如下:
①顺序检索位示图,从中找到第一个值为0的二进制位,得到其行号il=2,列号jl=2:第二个值为0的二进制位,得到其行号i2=3,列号j2=6。
②计算出找到的两个空闲块的盘块号分别为:
b1=i1×16十j1+1=2×16+2+1=35
b2=i2×16十j2+1=3×16+6+1=55
③修改位示图,令map[2,2]=map[3,6]=1,并将对应块35、55分配出去。
(2)释放磁盘的第300块时,应进行如下处理:
①计算出磁盘第300块所对应的二进制位的行号i和列号j:
i=(300-1)/16=18,j =(300-1)%16=11
②修改位示图,令map[18,11]=0,表示对应块为空闲块。
15.答:使用文件重命名功能时,用户必须提供两个参数:旧文件名,新文件名。实现该功能时,系统使用旧文件名查找文件目录,若找到旧文件名所对应的目录表目,则将目录表目中文件名字段对应的值改为新文件名值。从实现过程看,文件重命名功能完成的工作是修改目录表目中的文件名字段,除文件名外,文件的其他特性都未改变。
在后一种实现方法中,先进行文件复制并给复制文件起一个新名,此时系统完成了一次物理文件的复制工作,然后删除旧文件。虽然这样也能达到给文件重命名的目的,但其实现过程比前一种方式复杂,并且新文件与旧文件的物理存放地址肯定不同。
16.答:磁盘整理前,逻辑上相邻数据块的平均距离为13磁道,读一块数据需要的时间为:
13×6+100+25=203ms
因此,读取一个100块的文件需要时间:203×100=20300ms
磁盘整理后,逻辑上相邻数据块的平均距离为2磁道,读一块数据需要时间:
2×6+100+25=137ms
因此,读取一个100块的文件需要时间:137×100=13700ms
17.分析：在树形目录结构中,同一目录下的文件不可重名,不同目录下的文件可以重名。实现文件共享有多种方法,其中的一种方法是由系统实现对文件的共享,即当用户知道要共享文件的路径时,可以通过提供从根目录出发的路径名来共享访问这些文件;另一种方法是对需要共享的文件进行链接,即一个目录中的表目直接指向另一个目录的表目。所谓文件保护是指避免文件拥有者或其他用户因有意或无意的错误操作使文件受到破坏,对文件的保护可采用进行文件存取控制的任何一种方法。
答:在本题中,文件系统采用了多级目录组织方式。
(1)a.由于目录D中没有己命名为A的文件,因此在目录D中,可以建立一个取名为A的文件。
b.因为在文件系统的根目录下已存在一个取名为A的目录,所以根目录下的目录C不能改名为A。
(2)a.用户E欲共享文件Q,需要用户E有访问文件Q的权限。在访问权限许可的情况下,用户E可通过相应路径来访问文件Q,即用户E通过自己的主目录E找到其父目录C,再访问到目录C的父目录根目录,然后依次通过目录D、目录G、目录K和目录O访问到文件Q。若用户E当前目录为E，则访问路径为：../../D/G/K/O/Q,其中符号".."表示一个目录的父目录,符号"/"用于分隔路径中的各目录名。
b.用户G需要通过依次访问目录K和目录P,才能访问到文件S及文件T。为了提高访问速度,可以在目录G下建立两个链接文件,分别链接到文件s及文件T上.这样,用户G就可以直接访问这两个文件了。
c.用户E可以通过修改文件I的存取控制表来对文件I加以保护,不让别的用户使用。具体实现方法是,在文件I的存取控制表中,只留下用户E的访问权限,其他用户对该文件无操作权限,从而达到不让其他用户访问的目的。
18.分析：OPEN操作主要完成建立用户与文件联系的工作.为了避免用户在每次访问文件时从外存中查找文件目录,系统提供了OPEN命令。该命令的功能是将待访问文件的目录信息读入内存活动文件表中,建立起用户和文件的联系.一旦文件被打开就可以多次使用,直到文件被关闭为止。
CLOSE操作主要完成撤消用户与文件联系的工作.若文件暂时不用,应将其关闭。
CLOSE命令的功能是撤消主存中有关该文件的目录信息,切断用户与该文件的联系;若在文件打开期间,该文件作过某种修改,则应将其写回辅存。
答：(1)显式的OPEN操作完成文件的打开功能。它将待访问文件的目录信息读入内存活动文件表中,建立起用户进程与文件的联系。显式CLOSE操作完成文件的关闭操作。该命令撤消主存中有关该文件的目录信息,切断用户与该文件的联系;若在文件打开期间,该文件作过某种修改,还应将其写回辅存。
（2）可以取消显式的OPEN与CLOSE操作。如果取消了显式的OPEN与CLOSE操作,系统在进行文件操作之前需判断文件是否己打开,若文件未打开,则应自动完成文件的打开功能,以建立用户与文件间的联系。同时,在系统结束时,还应自动关闭所有打开文件。
(3)取消显式的OPEN与CLOSE操作使得文件的读写的系统开销增加。因为在每次读写前都需要判断文件是否已被打开。系统在结束时也要做一些额外的工作,以完成CLOSE命令的功能。当用户进程己使用完一个文件但尚未执行完时,因无显式的CLOSE命令也无法关闭文件,从而不利于系统资源的回收。
