文件和设备管理示例(PPT 64页).ppt

1、1,第 9 章,文件和设备管理示例,2,9.1 UNIX文件系统的特点与文件类别,9.1.1 UNIX操作系统的特点 P227 UNIX采用树型目录结构。UNIX中一个文件的绝对路径名由斜杠“/”开头，随后是路径中所经过的所有目录名，中间用斜杠分隔而成，比如：/usr/bin/spell。由于UNIX允许用户设置“当前目录”，因此，从当前目录开始的文件路径名，是它的相对路径名。,3,图9.1是它的一个典型示例，其中，根目录下有8个子目录： /dev此目录下都是设备文件，比如键盘终端（con）、打印机（lp）等； /bin 此目录下是UNIX外壳（shell）中主要程序的二进制代码文件； /us

2、r 此目录下通常为已安装的各个子文件系统，如bin、tmp、lib、local、include以及用户的各种文件； /lib 此目录下存放的是一些库文件，比如C、PASCAL的函数库； /include 此目录下存放的是一些头文件； /etc 此目录下存放各种管理文件； /tmp此目录下存放临时性文件； /UNIX存放UNIX的核心程序。,4,9.1.2 UNIX文件的分类 按照文件的内容，UNIX把文件分成3类： 普通文件：这是通常意义下的磁盘文件，即存放用户和系统的有关数据和程序的那些文件。它们都被视为无结构、无记录概念的字符流，文件的长度可以动态增减。 目录文件：由文件的目录项组成的文件

3、称为目录文件。这种文件在形式上与普通文件相同，只是系统将其解释成目录。一般地，一个文件的目录项应该包含文件名称、文件长度、文件类型、文件在辅存的位置以及存取权限等信息。在UNIX中，为了加快对文件目录的搜索速度，便于文件共享，把这些内容划分成两个部分：一个称为该文件的索引节点（即文件控制块），简称为i节点，它的里面存放着这个文件的长度、文件类型、文件在辅存的位置、存取权限以及共享信息等内容；另一个仍称为文件目录项，但它的里面只包含文件名和这个文件的索引节点编号。,5,下图给出了UNIX文件目录项的格式，即用14个字节存放文件名，2个字节存放该文件的i节点号（id）。不难看出，在UNIX中，是由

4、文件名查文件目录，由文件目录得到该文件的i节点编号，由这个编号得到文件的i节点，从而得到该文件的有关信息。,6,设备文件：在UNIX中，把块存储设备（如磁盘）和字符设备（如键盘、打印机）都视为文件。不过它们只有文件目录和索引节点，并不占用实际的物理存储块，因此，有时也称它们为特殊文件。为了检查和处理方便，UNIX总是把所有的特殊文件放在名为“dev”的目录文件中。,7,9.2.1 UNIX文件系统的存储结构 UNIX中，无论是普通文件还是目录文件，都存储在磁盘上。另外，每个文件的i节点也存储在磁盘上。下面讲述这些信息在磁盘上如何分布，UINX怎样来对它们实行管理。 为了使整个文件系统易于扩充和

5、更改，UNIX把文件系统分成基本文件系统和可装卸的子文件系统(文件卷)两个部分。基本文件系统和子文件系统都有自己独立的目录结构，但是基本文件系统是整个UNIX文件系统的基础，是文件系统的“根”，它总是被固定在作为根存储设备的磁盘上。子文件系统是指存储在可装卸存储介质（如软盘）上的文件系统，因此，子文件系统具有可装卸的特性。当把它安装到基本文件系统上时，自身的独立性消失，与基本文件系统融为一体。比如，用户可以把自己的文件系统组织在软盘上成为子文件系统。,9.2 文件系统的数据结构及其关系,8,9,UNIX把文件的存储空间磁盘想象成是一个由连续物理块构成的文件卷（把每个磁盘或磁带看作是一个文件卷）

6、，每个物理块含512个字节。在一个磁盘上，存放着普通文件的信息，存放着目录文件的信息，存放着文件的i节点，还要存放对磁盘存储区的管理信息（比如哪些块是空闲的，哪些块是已分配的等等）。整个磁盘存储区的组织结构如下图示。,10,块0用来存放引导程序，它与文件管理关系不大。文件存储器全部资源的管理信息（即filsys表）存放在块1，它是磁盘的管理区。从第2块K+1块，存放磁盘上文件的i节点内容，这个区域称为索引节点表（区）。索引节点表的后面是一般数据存储区，在那里存放普通文件和目录文件的信息。显然，在磁盘上，一般数据存储区所占用的磁盘空间为最大。下面对管理区中的资源管理信息表filsys、索引节点区

7、中的i节点以及文件的目录分别加以介绍。,11,9.2.2 几种常用的数据结构,资源管理结构filsys: 用来进行文件空闲块和i节点项的分配与回收, 包含文件系统空闲块分配用堆栈及i节点分配用数据结构。原理见P229 i节点（索引节点）:存放文件说明信息和相应标识符的BFD.包括：磁盘i节点（dinode, 以静态形式存放文件说明信息）、内存活动 i节点（inode, 为减少设备启动次数、提高文件的操作速度而把磁盘i节复制到内存的特定区域）。每个文件都应有一个唯一的磁盘索引节点，文件被打开后，还应有内存索引节点。,12,目录项: 由文件名和磁盘i节点标识符id组成。 系统打开文件表、用户打开文

8、件表: 记录和控制打开文件的用户进程以及记录和控制那些共享同一文件的用户进程。其中： 用户打开文件表：存放打开文件的描述符fd; 系统打开文件表：记录打开同一文件的不同进 程和不同进程所使用的不同打开路径，及其对应的读写指针。,13,资源管理的任务： 空闲磁盘块的分配 i节点的分配 系统打开文件表的分配 空闲磁盘块的回收 i节点的回收 系统打开文件表的回收,9.3 资源管理和地址映射,14,空闲磁盘块的管理,UNIX对文件存储空间的管理在磁盘上，UNIX总是把文件安排在一般数据存储区。因此，UNIX对文件存储空间的管理，即是对磁盘上一般数据存储区的管理。前面第7章介绍使用“空闲块链”管理磁盘上

9、的空闲块时，曾提及“成组链接”法，并说UNIX操作系统就是采用这种方法来管理磁盘上的空闲块的。这种方法是将若干个（如100)空闲盘块划归为一个组，将每组在中的所有盘块号存放在其前一组的第一个空闲盘块中，而仅把第一组中的所有空闲块号放入超级块（filsys结构）中。 下面简单介绍它的实现过程。,15,在磁盘管理区filsys结构中，有两个内容涉及到磁盘空闲块的管理，一个是由数组s_free100构成的一个空闲磁盘块索引表。当一个文件要申请磁盘块时，就到这个索引表中去获得需要的空闲块；当一个磁盘块被释放时，就把它还回到这个索引表中。所以，这个索引表中记录的是当前系统可以直接分配的空闲磁盘块。另一个

10、是s_nfree，它记录了s_free 中现有的可分配的空闲磁盘块数。 从形式上看，利用数组s_free100直接管理100个空闲的磁盘块，与利用数组s_inode100直接管理100个空闲的i节点相类似，但实际上相差很远。因为除这100个直接管理的空闲块外，UNIX对其余的空闲块并没有放置不管，而是将它们分组进行链接。具体做法如下图所示。,16,17,UNIX把磁盘上一般数据存储区中的所有空闲块依次分组。为了下面讲述方便，对每一组的块都进行分别编号。具体的办法是：第1组为99块，编号为199（为什么第1组只有99块，后面会给出解释）。从第2组起，每组都是100块，剩下的块归并成为最后一组。它

11、们都按099的顺序进行编号。在图中，从右至左反映了这种分组的结构。在图中，假定最后一组中只有52个空闲块，各块的编号为051。 分好组以后，总是在后一组的第0块中开辟101个位置，依次存放前一组的总块数以及前一组中每一块的地址。也就是说，相当于总是在后一组中，开辟s_nfree和s_free100所需要的位置，用于存放前一组的分组信息。,18,在此，有两组的情况要做特殊处理。一个是第1组。在第1组中，实际只有99个空闲块。为了管理的需要，把它的总块数仍记为100，见图中第2组里的s_nfree=100。另外，第一组磁盘块编号是从1开始的，因此在相当于第0号磁盘块的位置存放一个0，而不是某一个磁

12、盘块的地址，见图中第2组中的s_free0=0。,19,另一个要特殊处理的是最后一组。因为在最后一组的后面已经没有下一组了，所以UNIX就把它的所有信息存放在管理块的filsys中，即存放在filsys的s_nfree和s_free100中。由于现在最后一组只有52个空闲块，因此在filsys中的s_nfree取值为52，并且只用到数组s_free100的前52个元素，即用s_free0到s_free51存放最后一组的52个空闲块的地址。 至此，成组链接的格局已经完成：在filsys的s_free 中，记录了当前直接可以分配的52个空闲块。在这52个空闲块的第0块中，记录了下一组100个空闲的

13、磁盘块地址，下一组100个空闲的第0块中，记录了再下一组100个空闲的磁盘块地址，如此等等。,20,在采用“成组链接”法后，如何分配空闲块，如何回收空闲块？下面来讨论这两个问题。无论是磁盘空闲块的分配还是回收，都是在filsys中的空闲磁盘块索引表s_free 中进行，并把它视为一个栈。分配时，做出栈操作；回收时，做进栈操作。 s_nfree中记录的值，是s_free 中当前实际有的空闲块数，正好也是空闲磁盘块索引表s_free 中下一个可以使用的索引表目的下标。,21,因此，总是先在s_nfree上做减1操作，然后把s_frees_nfree中记录的磁盘块分配出去。这里要注意的是，如果在s_

14、nfree上做减1操作后，其值等于0了，那么就是要把s_free0所指向的那一个磁盘空闲块分配出去。由于它是这一组的第0个磁盘块（按照分配顺序，它总是在一组中最后被分配出去），里面包含有它前一组空闲块的信息在内。因此在把这一块分配出去之前，应该先把它记录的101个信息拷贝到filsys结构的s_nfree和s_free 里面去，然后才能将它分配出去。,22,分配时还要注意的一个问题是如果分配一直进行，现在要把第2组的第0块分配出去。根据前面所说，先把这块中记录的101个信息拷贝到filsys结构的s_nfree和s_free 里面去，然后才将它分配出去。这意味着系统现在只有最后99块能够分配了

15、。如果分配仍然继续，直到把这99块全部分配出去。此时，filsys中的s_nfree=1，s_free0=0。若再申请空闲块，s_nfree减1后成为0，即要把s_free0所指的块分配出去。此时发现s_free0=0，而不是一个磁盘块的地址，表明所有的磁盘空闲块都分配出去了，提出请求的进程只能阻塞等待。所以，这就是前面分组时把第1组只分99个空闲块，但仍然算这组有100个块，并将第0块指针处安放一个0的原因。,23,进行空闲块的回收时，就是将该块的地址登记在空闲磁盘块索引表的s_frees_nfree表目中,然后让s_nfree加1。不过要注意，在把释放块的地址存入索引表s_free 的表之

16、前，必须检查s_nfree的取值。如果发现s_nfree等于100，那么表明这时空闲磁盘块索引表在此之前已经收集满了100个空闲的磁盘块，它们应该形成一个新的链组。现在要释放的一块，是下一组空闲块的第0块。于是，就把filsys中的s_nfree和s_free0s_free99共101个值存入新释放块中，然后将此块的地址填入s_free0中，将s_nfree置为1。,24,9.3.1 磁盘i节点的管理,基本思想：在给新建文件分配磁盘存储区之前，为其分配磁盘i节点，以将文件的有关信息记入其中，并将用户提供的文件名和磁盘i节点号一并组成一个新目录项，记入其父目录文件中; 删除文件时，回收所分配的磁

17、盘i节点项。 分配算法：借助于i节点线性表利用ialloc算法（UNIX System V）进行的，具体分配过程见 P232 回收算法：利用ifee算法,25,9.3.2 内存i节点的管理,基本思想：系统打开文件进行搜索或读写等操作时，为其分配内存i节点，以存放从磁盘i节点拷贝过来的信息，方便用户或系统对文件的访问; 删除文件时，回收所分配的磁盘i节点项。 分配：利用过程iget实现 回收：利用过程iput实现,26,9.3.3 系统打开文件表的管理,系统打开文件表：记录打开同一文件的不同进程和不同进程所使用的不同打开路径，及其对应的读写指针。 分配：利用getf过程实现 回收：利用close

18、f过程实现,27,9.3.4 地址映射,前面提及，UNIX文件的物理结构采用的是索引结构，这种索引结构是通过每个文件i节点中的数组di_addr 来形成文件存储索引表的。该数组总共有13个元素，每个元素为一个索引项。前10个索引项直接指向文件数据存放的磁盘块号，后3个索引项分别构成一次间接索引、二次间接索引和三次间接索引的多级索引结构。这样，UNIX可以根据文件的大小，通过使用这张存储索引表，形成小型、中型、大型和巨型等不同规模的文件。,28,小型文件的索引结构：通常，每个磁盘块为512个字节。当一个文件的长度在110个磁盘块之间时，就称为小型文件。这时，用文件i节点中数组di_addr 的前

19、10个表目，直接指向文件数据存放的磁盘块号。因此，在UNIX中，小型文件是通过i节点中的数组di_addr 构成一级索引表而获得文件在磁盘上的存储位置的。如下图所示。,29,30,中型文件的索引结构:当一个文件的长度在10138磁盘块内时，就成为一个UNIX的中型文件。这时除了用到di_addr0di_addr9外，还要用到di_addr10，如下图所示。 在图中，di_addr0di_addr9仍然直接指向文件数据存放的10个磁盘块号，然后又利用di_addr10指向一个磁盘块。这块并不存放文件的数据，而是利用它形成又一级的索引。在UNIX中，用4个字节放一个磁盘块号，因此在这个盘块中，可以

20、放128个磁盘块号。这样一来，通过di_addr10提供的索引，一个文件就可以达到138个磁盘存储块这么大。,31,32,大型和巨型文件的索引结构: 当一个文件的长度在13816522磁盘块内时，就成为一个UNIX的大型文件。这时除了用到di_addr0 di_addr9外，要用到di_addr10，还要用到di_addr11。 在图中，di_addr0di_addr9直接指向文件数据存放的10个磁盘块号。然后如同前面那样，利用di_addr10指向一个磁盘块，由它提供128个磁盘块的索引，从而使文件总共达到138个磁盘存储块这么大。但这还不够，又利用di_addr11指向一个磁盘块，由它指向

21、128个磁盘块，每个都是一个索引。这样，通过这128个索引、每个指向128个磁盘块，就又可以得到16384个磁盘块。于是，UNIX的大型文件最多可以拥有16522个磁盘块（即10+128+16384）。,33,34,当一个文件所需的磁盘块大于16522个磁盘块时，就成为UNIX的巨型文件了。这时除了用到di_addr0di_addr9外，还要用到di_addr10、di_addr11和di_addr12。此时，文件的最大长度可以达到约11亿个字节，但是由于此时要经过多次间接索引，会使系统的查找速度大大降低。,35,9.4 目录与检索方法,目录的构造和删除 创建一新文件时，UNIX系统利用mak

22、enode过程在其父目录文件中为之构造一个目录项。 目录的检索 由namei过程利用散列搜索法完成，其根据用户给出的文件路径名，从高层到低层顺序地查找各级文件目录，寻找指定文件的内存i节点指针。,36,9.5 文件系统的系统调用,UNIX提供了一些系统调用命令，以便用户在程序一级完成对文件的操作。有关的系统调用是：creat、open、read、write、close、chdir、chown、chmod、link和unlink等。下面对它们各自的功能做粗略的描述。 creat（建立文件） open（打开文件） close（关闭文件） read（读） write（写）,37,link（链接） 系

23、统调用link可以为一个已经存在的文件开辟一条新的路径，也就是说，可以为一个文件再取一个新的名字。它的使用格式是： link(pathname1，pathname2)； 其中参数pathname1是原文件的路径名，参数pathname2为其新取的路径名。 link处理程序先按照参数pathname2的指点，将新的文件名登记到指定的路径目录中。然后根据pathname1，找到原文件所对应的i节点编号，将该号填入新文件的文件目录中。由于每个文件的i节点编号是惟一的，因此经过link之后，两个不同路径名的文件就与同一个文件相对应了。,38,unlink（去链接）,39,比如考虑上图的情形。zong和

24、wang要共同完成一项工作。zong为了访问对方的文件x，只能通过“/usr/wang/x”才能达到目的。但如果通过命令： link（/usr/wang/x，/usr/zong/k）； 那么，若当前目录为zong，则zong直接通过k就能够访问wang的文件x了，这是因为link命令在zong的文件k和wang的文件x之间建立了链接的缘故。如图(b)所示。,40,9.6 UNIX的设备管理,UNIX设备管理概述 UNIX是根据设备与内存之间信息交换的单位来对设备进行分类的，因此在整个系统中，归到设备管理的有两类设备：块设备和字符设备。前者与内存之间以成组信息为单位进行信息交换，比如硬盘、软盘、

25、磁带都属于块设备。由于这些设备是用来存储信息的，因此有时把它们称为存储设备；后者与内存之间以字节为单位进行信息交换，比如键盘输入、显示器和打印机等都属于字符设备之列。由于这些设备主要供计算机接收外部信息，或把加工完毕的信息传递给外部世界，因此也被称为输入/输出设备。,41,为了识别每一个具体的设备，UNIX是这样做的：每一类设备附有一个编号，称为“主设备号”，同类设备中的不同设备也给予一个编号，称为“次设备号”。在请求设备进行输入输出时，必须指定主设备号和次设备号。这样，由主设备号判定由哪个驱动程序工作；驱动程序根据次设备号确定控制哪台设备去完成所需要的I/O。 从前面对UNIX文件管理的讲述

26、可知，UNIX把块设备和字符设备都视为特殊文件来对待，它们的文件目录都在子目录dev下。由于它们是文件，因此有自己的i节点。为了与其他文件加以区分，在它们的索引节点中，把“文件类型”栏置为“块”或“字符”。由此表明它们不是普通文件，也不是目录文件，而是设备文件，并且由此也能区分是块设备文件还是字符设备文件。,42,在UNIX中，是通过系统调用creat来建立新文件的。但设备文件不能用普通的方法来创建，并且也不是谁都有权来创建。如果要创建一个新的设备文件，则应该由系统管理员通过系统调用mknod来完成。它的使用格式是（ P250）： mknod（pathname，mode，dev）； 其中，参数

27、pathname是文件的路径名，mode指出文件的类型（B表示块设备，C表示字符设备），dev是主设备号和次设备号的组合。比如有如下命令： mknod（/dev/abc，C，2 12）； 表示要在根目录的子目录dev下，创建一个名为abc的文件（由于它建立在子目录dev下，因此它是一个设备文件），由于mode=“C”，因此是一个字符设备文件，该设备的主设备号是2，次设备号是12。,43,9.6.1 块设备的管理,UNIX在块设备和内存之间安放了缓冲区，通过它使块设备与内存间的数据流动在速度上能够匹配，从而达到减少内、外存传输次数的目的。如图所示。对于写操作，先是把内存用户区中的数据拷贝到缓冲区

28、，再从缓冲区输出到设备；对于读操作，先从设备接收数据到缓冲区，再将缓冲区中的数据拷贝到指定的内存用户区。,44,块设备的每一个缓冲区长度为512个字节或1024个字节，这要由文件系统来确定。由一个个缓冲区，组成了供块设备输入/输出使用的缓冲池。为了便于管理，UNIX把缓冲池中的每个缓冲区分成两个部分：一个是真正用于存放数据的部分，一个是用于管理的部分。前者仍称为“缓冲区”，后者称为“缓冲区控制块”，并在缓冲区和缓冲区控制块之间保持一一对应的关系。图9.10给出了缓冲区控制块的内容和它与缓冲区的对应关系。,45,46,1空闲缓冲区队列（av队列） 为了构成系统中空闲缓冲区队列，UNIX设置了一个

29、名为bfreelist的控制块，它的结构与缓冲区控制块相同，里面的av_forw和av_back就是块设备空闲缓冲区队列的首指针和尾指针，如图9.11所示。,47,48,对于空闲缓冲区队列，有两点要说明：第一，这个由缓冲区控制块构成的队列是一个双向链表，它们通过各自的前向指针av_forw和后向指针av_back链接在一起，形成队列。第二，UNIX对这个队列采用先进先出（FIFO）的管理算法。即当释放一个缓冲区时，与之对应的缓冲区控制块就被链入到空闲缓冲区队列之尾；当申请一个缓冲区时，就把空闲缓冲区队列之首的那个缓冲区控制块摘下分配出去，这也就意味着是把这个缓冲区控制块所对应的缓冲区分配出去。

30、,49,2.设备缓冲区队列（设备b链,散列队列） 这是由缓冲区控制块组成的第二种队列，是UNIX对缓冲区管理的一大特色。下面来说明这是一个什么队列，为什么要组成它。,50,缓冲池中的缓冲区资源是有限的，为了能够对它们充分地加以利用，以及对它们里面存放的数据信息最大限度地加以利用，UNIX提出了这样的设想：一个已经在空闲缓冲区队列中的缓冲区控制块，在它未被挪为它用之前，它对应的缓冲区中保存的仍然是磁盘上某块中的数据信息。如果这时根据需要又要对该磁盘块进行操作，那么大可不必去通过启动I/O获得盘块上的数据，这些数据还在原来的缓冲区中完好无损地保存着，只要拿来就可以使用。这样做的结果是减少了I/O次

31、数，大大提高了系统的工作效率。,51,出自于这些考虑，UNIX一方面仍然是让被释放缓冲区所对应的缓冲区控制块链入到空闲缓冲区队列之尾，以便能够它用。另一方面又设置了一个新的队列：设备缓冲区队列，即把为某个设备服务的缓冲区所对应的缓冲区控制块全都汇集在一起，形成了这个设备的设备缓冲区队列。一个设备的设备缓冲区队列由缓冲区控制块中的d_forw和d_back指针进行链接，前者为前向指针，后者为后向指针。该队列的首、尾指针是设备表中的d_forw和d_back。整个队列如下图所示。,52,53,几点说明： （1）这个由缓冲区控制块构成的队列是一个双向链表，它们通过各自的前向指针b_forw和后向指针

32、b_back链接在一起，形成队列。 （2）当一个缓冲区被分配给某个块设备做输入/输出用时，它所对应的缓冲区控制块就从队首插入到队列里。 （3）当一个缓冲区控制块插入到一个设备的设备缓冲区队列中之后，即便该缓冲区被释放，它也仍然在这个队列中排着。这就是说，在任何时刻，UNIX中的任何一个缓冲区控制块，总会在空闲缓冲区队列、设备缓冲区队列以及设备输入/输出队列这三个队列中的两个里排队，或是在空闲缓冲区队列、设备缓冲区队列里面排着，或是在设备缓冲区队列、设备输入/输出队列里面排着。 （4）只有当一个缓冲区的服务对象改变（比如原来被分配给磁盘1使用，现在被分配给磁盘2使用了）时，该缓冲区所对应的缓冲区

33、控制块才会从一个设备缓冲区队列上摘下，进入到另一个设备缓冲区队列中；否则即便缓冲区被释放，它仍然保持在原来的设备缓冲区队列中。,54,3输入/输出请求队列（块设备av链)） 当用户对块设备提出输入/输出请求时，首先要申请一个空闲的缓冲区控制块（注意：申请到空闲的缓冲区控制块，就意味着申请到了存放数据的缓冲区，因为它们是一一对应的），并把这次输入/输出请求具体要完成的任务填入到缓冲区控制块中（数据源的地址、目的地址、传输的个数等等）。因此，UNIX把向主设备号相同的设备提出的I/O请求所对应的缓冲区控制块链接在一起，形成对这个设备的输入/输出请求队列。该队列的首指针就是这个设备的设备表里的d_actf，尾指针是d_actl。如下图所示。,55,56,对于块设备的输入/输出请求队列有三点说明：第一，它是一个单链表，不像空闲缓冲区队列，那里给出的是一个双向链表。第二，由于一个缓冲区控制块不可能同时在空闲缓冲区队列和输入/输出请求队列，因此，在输入/输出请求队列中，就借用缓冲区控制块中的av_forw指针来构成单链表（这个指针在空闲缓冲区队列里是前向指针）。第三，UNIX对这个队列采用先进先出（FIFO）的管理算法。即后到的输入/输出请求所对应的缓冲区控制块被排在队尾，设备总是为排在队首的那个缓冲区控制块中所