操作系统教程第4章.ppt

《操作系统教程第4章.ppt》由会员分享，可在线阅读，更多相关《操作系统教程第4章.ppt（108页珍藏版）》请在三一办公上搜索。

1、第7章 实例分析：UNIX操作系统,1969年，美国贝尔实验室的汤普逊（K.Thompson）和里奇（D.M.Ritchie）免费发行了一个小型的实验性操作系统，由此宣布了UNIX操作系统的诞生。1978年以后，UNIX真正开始流行。时至今日，UNIX已经走过了30多个年头。在此期间，它发生了许多重大的变化，有欣欣向荣之日，也有曲折坎坷之时。但不管怎样，UNIX以其特有的简洁性和开放性，赢得了越来越多人的赞赏与青睐，已成为一个应用领域广泛、功能丰富实用的操作系统。现在已经有各种版本的、可以运行在不同平台上的UNIX。,退出,UNIX是一个通用、多用户的分时操作系统。本章主要从实现的角度出发，讲

2、述四个方面的内容：（1）UNIX的进程以及进程调度；（2）UNIX采用的存储管理策略；（3）UNIX目录结构的特点以及对磁盘存储空间的管理；（4）UNIX对块设备及字符设备的管理以及缓冲技术。,7.1 UNIX的处理机管理7.2 UNIX的存储管理7.3 UNIX的文件管理7.4 UNIX的设备管理,7.1 UNIX的处理机管理,7.1.1 UNIX的进程通常，一个进程由三个部分组成：进程控制块PCB、数据和程序。在UNIX中，一个进程也由三个部分组成：进程控制块、数据段和共享正文段，并有其自身的不同含义。1进程控制块,2数据段进程运行时用到的数据以及工作区，构成了一个进程的数据段。要注意的是

3、，如果进程执行的程序是不能被共享的，那么也把它归入到数据段中。这样，UNIX进程的数据段分成三个部分：系统数据区、用户数据区和用户栈区。如在基本控制块proc结构中所述，在进程的proc结构中，由p_addr指向该进程数据段的首地址，由p_size给出数据段的长度。其联系如图7-1所示。,3共享正文段为了管理好进程的共享正文段，UNIX在内存专门开辟了一个text结构区域，形成正文段表text。其中每一个text结构对应一个共享正文段，主要记录关于这个正文段的有关信息，比如共享正文段在磁盘对换区的地址（x_daddr），共享正文段在内存的地址（x_caddr），共享正文段的长度（x_size）

4、，共享本正文段的所有进程数目（x_count）等。综上所述，一个进程的基本控制块proc结构、数据段（包含扩充控制块user结构）以及共享正文段三者之间的关系，可以用图7-2勾画出来。,在那里一根虚线把图分成两个部分。标有的部分表示proc 表中进程的proc结构以及text 表中的text结构总是常驻内存。通过proc结构中的p_addr，就能够得到该进程的数据段；通过p_textp，就能够得到该进程共享正文段的text结构，再由这个text结构中的x_caddr或x_daddr就能够得到共享正文段在内存或在磁盘对换区的位置。标有的部分表示进程的数据段和共享正文段是非常驻内存部分，根据需要和

5、可能，数据段和共享正文段会在内存和磁盘对换区之间换进和换出。另外，通过user结构中的u_procp，可以得到该进程的proc结构的位置。,7.1.2 UNIX的进程状态UNIX进程在其生命期内，可以处于多种不同的状态，并记录在进程的proc结构中。图7-3给出了进程状态的变迁图。,当父进程执行系统调用fork创建一个子进程时，被创建进程处于“创建”状态。如果能够为该进程分配到足够的内存空间，则它变为“在内存就绪”状态；如果当前没有足够的内存空间，则它变为“换出并就绪”状态，被安置在磁盘的对换区。另外，原来已在内存的就绪进程，也可能因为内存紧张而被换出，同样成为“换出并就绪”状态。处于这两种状

6、态的进程，从原则上说都是“就绪”的，都可以参与处理机调度。只是处于“换出并就绪”状态的进程被调度到时，由于它的非常驻内存部分并不在内存，因此要先被换进，才能够真正占用处理机投入运行。,一个进程被调度到时，就成为“用户态运行”状态。进程在“用户态运行”状态下时，若程序中使用了系统调用或请求输入/输出，就会使进程从“用户态运行”状态改变为“核心态运行”状态。在“核心态运行”状态下的进程是不能被剥夺的。当系统调用执行完毕，就返回到“在内存就绪”状态。如果要等待输入/输出完成，则变成“在内存睡眠”状态；如果是调用了exit而进入“核心态运行”状态，则意味着进程运行结束，于是进入“僵死”状态，所占用的一

7、切资源被释放。如果在“用户态运行”状态下，由于时间片到等原因，就会直接变成“在内存就绪”状态。,一个进程处于“在内存睡眠”状态时，如果内存使用紧张，就会被从内存换出到磁盘的对换区。这时，该进程处于“睡眠并换出”状态。无论是处于“在内存睡眠”状态还是处于“睡眠并换出”状态，都表明这个进程在等待某个事件的发生。当处于“在内存睡眠”状态下等待的事件发生时，进程状态就变为“在内存就绪”；当处于“睡眠并换出”状态下等待的事件发生时，进程状态就变为“换出并就绪”。以上就是一个UNIX进程从被创建开始到被撤消为止的整个生命期内的变化过程。,7.1.3 UNIX的进程调度与换进换出为了把处理机分配给一个进程使

8、用，UNIX的进程调度程序总去查看系统proc 表中登记的所有进程。在处于就绪、且全部在内存的进程中，挑选一个优先数最小（即优先权最大）的进程作为分配对象。如果暂时没有这种进程存在，那么进程调度程序就处于“在内存睡眠”的等待状态。直到发生中断请求，被唤醒再次去搜索proc 表。UNIX赋予进程调度进程极高的优先权，以保证系统能以最快的速度找到可运行的进程，提高CPU的使用效率。,为了改变一个进程的优先数，在UNIX中采取设置和计算两种方法。设置方法用于当一个进程变为睡眠状态时，系统将根据不同的睡眠原因，赋予睡眠进程不同的优先数。这个优先数将在进程被唤醒后发挥作用。计算进程优先数的公式为：p_p

9、ri=min127，(p_cpu/16+PUSER+p_nice),此公式是在127和p_cpu/16+PUSER+p_nice两个数之间取最小值。其中PUSER是一个常数；p_nice是用户为自己的进程设定的优先权，它可以通过系统调用命令来加以设置。通常，由这个量反映用户进程工作任务的轻重缓急程度。一个进程的p_nice被设置后，若再要改变，则只能够让其增加；p_cpu是进程使用处理机的时间，它给出了一个进程使用处理机的情况。,这里最关键的是p_cpu，系统通过时钟中断来记录每个进程使用处理机的情况。时钟中断处理程序每20ms做一次。每做一次就将运行进程的p_cpu加1。到1s钟时，依次检查

10、系统中所有进程的p_cpu。如果这个进程的p_cpu10，表明该进程在此1s钟内占用处理机的时间超过200ms，于是在它原有p_cpu的基础上减10。图7-4给出了p_cpu的变化对进程优先数的影响，从而也就影响到了进程被调度到的可能性。,从左到右从上到下来观察图7-4。如果一个进程逐渐地占用了较多的处理机时间，那么它的proc结构中的p_cpu值就逐渐加大，呈上升的趋势（见图7-4）。由于p_cpu增加，根据公式（1）计算出来的进程优先数也呈上升的趋势（见图7-4）。进程优先数的上升，意味着它获得处理机的优先权下降（见图7-4），也就是被调度到的可能性减少（见图7-4）。由于调度到的可能性减

11、少了，使用处理机的机会就少了，于是p_cpu值下降（见图7-4）。P_cpu值下降，意味着由公式（1）计算出来的进程优先数也呈下降的趋势（见图7-4）。一个进程优先数减少，表示它的优先权上升（见图7-4），也就是这个进程获得处理机的机会增多（见图7-4）。可见，通过这样的处理，UNIX让每个进程都有较为合理的机会获得处理机的服务。,如上所述，UNIX一方面总是在“在内存就绪”状态的进程中挑选一个优先数最小（即优先权最大）的进程作为分配对象，因为它们不仅就绪，而且所有的信息全部在内存中。另一方面，为了缓解内存使用的紧张程度，UNIX又常把一些进程的非常驻内存部分换出到磁盘对换区上。它们或处于“换

12、出并就绪”状态，或处于“睡眠并换出”状态。调度时，如果没有“在内存就绪”状态的进程存在，那么就需要把磁盘对换区中的“换出并就绪”状态的进程换进内存参与调度，因为它们处于就绪状态，只是有一部分信息在磁盘对换区，把这些信息调入内存后，它们就能够投入运行。但如果在换进进程时，内存没有足够的存储空间，那么就需要把当前在内存的一些进程换出到磁盘对换区。所以，在UNIX中，经常要遇到进程的换出和换进问题。,进程的换进换出，涉及到三个方面的问题：磁盘对换区中进程的换进、内存中进程的换出以及磁盘对换区的管理。最后一个问题将放在UNIX存储管理的“对换技术”一节中讨论，这里只介绍进程的换进和换出问题。在UNIX

13、中，进程的换进换出是由sched程序完成的。该进程有两个睡眠标志：runout和runin。当磁盘对换区中没有可换进的进程时，就把runout设置为1，sched进入“睡眠”，直到对换区中有要换进的进程时被唤醒；当磁盘对换区有就绪进程要换进，但内存没有足够的空间容纳、也没有可换出的进程时，就把runin设置为1，sched进入“睡眠”，直到内存中有可以换出的进程时被唤醒。Sched的工作流程如图7-5所示。,图7-5上有（*1）标志的地方，是在磁盘对换区寻找换进对象的地方。UNIX是根据这样的条件来选择调入者的：首先它应该处于“换出并就绪”；其次，它在磁盘对换区至少停留了2秒钟以上，这个信息在

14、该进程proc结构的p_time中记录着；最后，在满足前两个条件的进程中，p_time最小的那个进程即是第1个被换进的对象。Sched不断地把进程换进内存，直到没有可以换进的进程时，就把runout置为1，进入睡眠等待叫醒。,图7-5上有（*2）标志的地方，是在内存寻找换出对象的地方。只有当磁盘对换区中有可以换进的进程、但没有内存空闲空间时，UNIX才进行换出工作。sched是根据这样的条件来选择调出者的：首先考虑处于“在内存睡眠”状态的进程，把它的非常驻内存部分换出；其次是在处于“在内存就绪”状态的进程中，把其proc结构中p_time最大者的非常驻内存部分调出。只要内存中还有可以换出者，s

15、ched就不断地工作，直到不可能时，把标志runin设置为1，进入睡眠等待叫醒。,7.2 UNIX的存储管理,7.2.1 对换技术采用对换技术的UNIX，是在磁盘上开辟一个特定的对换区，把它作为内存的扩充：在内存紧张时，可以把内存中的某些进程换出到对换区；在需要时，又可以将对换区上的进程换进内存。这时UNIX的存储管理对象既包含内存的有关部分，也包含磁盘的对换区，并用相同的方法管理着它们。,首先要明确，在采用“对换”技术管理存储空间时，要把整个内存储器划分成两部分：操作系统使用部分和用户程序使用部分。前者所占用的内存空间称为系统空间，后者占用的内存空间称为进程空间。很清楚，系统空间的内容是不参

16、与对换的，换进换出的都是在进程空间中的内容。下面谈及内存空间时，就专指能够进行对换的进程空间。UNIX对内存空间和磁盘对换区都是采用可变式分区管理的办法。当提出存储请求时，都是采用最先适应算法来进行存储分配。关于内存管理的问题，在第3章已经介绍，这里只讲对磁盘对换区的管理。,为了管理磁盘对换区，UNIX设置了一张可用存储区表swapmap，每个表目由两部分内容组成：m_size，记录一个连续空闲磁盘空间里包含的磁盘块数；m_addr，记录一个空闲磁盘空间的起始地址。所以，每个表目反映了磁盘对换区中一个可用区域的信息。初启时，整个磁盘对换空间都是空闲的，因此swapmap 中只有第1个表目有效，

17、在它的里面登记着对换区的起始地址和整个对换区包含的块数。随着进程的换出、换进，对换区空间不断被分配和释放，可用存储区表的表目也就随之增加和减少。无论怎样变化，每个有效表目总是按照其m_addr的值由小到大进行排列。,UNIX设置有malloc和mfree来管理存储区域的分配和释放。在接到一个存储请求时，malloc采用最先适应算法来分配对换区的可用空间。它从可用存储区表swapmap 的第1个表目出发，用申请的尺寸与表目中的m_size比较，第1个大于或等于申请尺寸的m_size就为所求。在按照分配单位（块）分配后，对可用存储区表swapmap 的表目进行调整。如果申请尺寸与m_size相等，

18、则将该表目删除，后面的表目上移填补。在释放一个存储区时，mfree开始工作。它先根据释放存储区的起始地址，在可用存储区表swapmap 中找到它的插入位置。然后由插入位置以及前一个表目中的m_addr、m_size信息，判断被释放的存储区能否与它们合并成为一个大的空闲存储区。随之对可用存储区表swapmap 的表目进行不同的调整，从而完成释放处理。图7-6描述了对磁盘对换区管理的过程。,假定该磁盘对换区起始地址为0，共1000块。那么初启时，可用存储区表swapmap 只有一个有效的表目，如图7-6(a)所示。若现在要申请100块的存储区，那么就把该对换区最前面的100块分配出去，这时可用存储

19、区表的情形如图7-6(b)所示。再申请50块时，就变成为图7-6(c)所示。此时可用存储区表中仍然只有一个有效的表目，它记录了当前对换区中仅有的一个空闲区。,若这时前面分配出去的那100块被释放，于是情形就成为图7-6(d)所示，这时可用存储区表中出现两个表目，记录了两个不连续的空闲存储区域的信息。如果此时提出60块的存储请求，根据最先适应算法，将把第1个空闲区中的前60块分配出去，剩下的40块仍为空闲，所以图7-6(e)中仍然有两个有效的表目。若这时分配出去的50块被释放，那么它能够与其前、后的空闲区合并成为一个大的空闲区，于是可用存储区表就如图7-6(f)所示。,7.2.2 请求页式存储管

20、理技术在请求页式存储管理中，仍把操作系统占用的内存空间称为系统空间，用户程序占用的内存空间称为进程空间。由于UNIX进程既可以执行操作系统程序，也可以执行用户程序，因此，一个进程的虚拟地址空间在逻辑上被划分成三个区段：系统区段、进程控制区段和进程程序区段，如图7-7所示。系统区段在系统空间里，其程序和数据常驻内存；另外两个区段在进程空间里，是进程中的非常驻内存部分。每个区中的箭头是它动态扩展的方向。,UNIX进程的每个区段都有自己的虚拟地址空间。也就是说，UNIX的每个进程都有三个虚拟空间。通过虚拟地址结构的最高两位，来区分属于哪一个空间，如图7-8所示。比如，一个虚拟地址的最高两位为00，则

21、表示这是P0区段中的某一页；如果一个虚拟地址的最高两位为10，则表示这是系统区段中的某一页。从虚拟地址结构可以看出，一个区段的虚拟地址空间最多可以有4096页，每页为个512字节。内存也分成与页一样大小的物理块，其编号称为物理块号。,UNIX通过页表进行虚拟地址到物理地址的地址变换。页表表目的形式如图7-9所示。页表以页号为索引进行排列，每个表项中除了记录该页号所对应的物理块号外，还有该页的有关信息。其中：“V”代表有效位，也就是“缺页中断位”。该位为1，表示此页已经在内存，所在位置就是表项中给出的物理块号；该位为0，表示此页不在内存。进程访问这页时，硬件就产生“页面错”（即缺页）中断，并要求

22、操作系统将此页调入内存。,“M”代表修改位，指出该页是否被修改过。该位为1，表示给修改过。如果在运行过程中要把一个修改过的页淘汰出去，就必须先进行回写操作，然后再实行淘汰；该位为0，则被淘汰时，不必进行回写操作。“PROT”四位指明此页的访问权限。如果一个进程无权访问此页，则硬件会产生“非法访问”中断。,由于UNIX进程的每个区段都有自己的虚拟地址空间，因此也就有自己相应的页表。为了保证页面映象的正确性，硬件为每个区段设置一对寄存器：由“基址寄存器”给出该区段页表的起始地址，由“长度寄存器”给出页表中表项的数目（也就是该区段虚拟地址空间中的页面数）。整个地址映象过程缤7-10所示。,总体上说，

23、UNIX的地址映象过程可分为如下三步。（1）根据虚拟空间地址的最高两位，判定该地址所在区段，以便确定使用哪一对寄存器，在图7-10中，用3个问号表示这一过程。（2）由所决定的寄存器对，得到相应的页表，用虚拟地址中的页号去查页表，图7-10中用长虚线表示。（3）从页表中得到该页所对应的物理块号，用它与页内位移进行拼装，得到所需要的物理地址。这种地址变换过程的基本思想，与存储管理中所述的是一致的，只是具体实现稍有差别。,在UNIX的请求页式存储管理中，是采用位示图的办法来管理内存空间的。位示图中的每一位对应于内存的一个物理块，位为1，表示所对应的内存块已经分配；位为0，表示所对应的内存块空闲可用。

24、当提出存储申请时，就在位示图中寻找为0的块加以分配，并把0改为1；当释放存储块时，就把该块所对应的位示图中的位，由1改为0。当在图7-10中用虚拟地址中的页号去查页表，而该页所对应的页表表目里的“V”位是0时，表示这一页当前不在内存块中，因此会引起“页面错”中断。UNIX必须通过中断处理，将这一页从辅存调入内存。当然，这样做有时会导致页面淘汰。,7.3 UNIX的文件管理,7.3.1 UNIX文件管理综述按照文件的内容，UNIX把文件分成3类：（1）普通文件：这是通常意义下的磁盘文件，即存放用户和系统的有关数据和程序的那些文件。它们都被视为无结构、无记录概念的字符流，文件的长度可以动态增减。,

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

26、点号。不难看出，在UNIX中，是由文件名查文件目录，由文件目录得到该文件的i节点编号，由这个编号得到文件的i节点，从而得到该文件的有关信息。,（3）特殊文件：在UNIX中，把块存储设备（如磁盘）和字符设备（如键盘、打印机）都视为文件。不过它们只有文件目录和索引节点，并不占用实际的物理存储块，因此，有时也称它们为设备文件。为了检查和处理方便，UNIX总是把所有的特殊文件放在名为“dev”的目录文件中。,为了使整个文件系统易于扩充和更改，UNIX把文件系统分成基本文件系统和可装卸的子文件系统（又称文件卷）两个部分。基本文件系统和子文件系统都有自己独立的目录结构，但是基本文件系统是整个UNIX文件系

27、统的基础，是文件系统的“根”，它总是被固定在作为根存储设备的磁盘上。子文件系统是指存储在可装卸存储介质（如软盘）上的文件系统，因此，子文件系统具有可装卸的特性。当把它安装到基本文件系统上时，自身的独立性消失，与基本文件系统融为一体。比如，用户可以把自己的文件系统组织在软盘上成为子文件系统。,使用时，把软盘插入软盘驱动器，然后通过系统调用命令将它与基本文件系统挂接在一起。于是，用户就可以像访问基本文件系统中的文件那样去访问子文件系统中的文件。也就是说，整个系统统一地只有一个“根”，没有从这个文件系统的“根”切换到那个文件系统的“根”的问题。使用完毕后，可以用系统调用命令把它与基本文件系统脱钩，取

28、出软盘。这样既安全又灵活。在把子文件系统安装到基本文件系统上时，总是把子文件系统的根目录与基本文件低车哪骋患赌录连接起来。图7-12给出了一个挂接的示例过程。,假定图7-12(a)是UNIX的基本文件系统，它就是根文件系统。现在要把如图7-12(b)所示的子文件系统挂接到根文件系统的“/usr”目录下。图7-12(c)是挂接完毕后的情形。为了访问原来子文件系统中的文件“/ast/f1”，现在只需用文件名“/usr/ast/f1”即可达到目的。UNIX采用树型目录结构，图7-13是它的一个典型示例。其中，根目录下有8个子目录：/vmunix存放UNIX的二进制引导文件；/dev 此目录下都是特殊

29、文件，比如键盘终端（con）、打印机（lp）等；,/bin 此目录下是UNIX外壳（shell）中主要程序的二进制代码文件；/usr 此目录下通常为已安装的各个子文件系统，如bin、tmp、lib、local、include以及用户的各种文件；/lib 此目录下存放的是一些库文件，比如C、PASCAL的函数库；/user 此目录下存放的都是用户自己的文件；/etc 此目录下存放各种管理文件；/tmp 此目录下存放临时性文件。,UNIX中一个文件的绝对路径名由斜杠“/”开头，随后是路径中所经过的所有目录名，中间用斜杠分隔而成，比如：/usr/bin/spell。由于UNIX允许用户设置“当前目录

30、”，因此，从当前目录开始的文件路径名，是它的相对路径名。,7.3.2 UNIX对磁盘的组织UNIX中，无论是普通文件还是目录文件，都存储在磁盘上。另外，每个文件的i节点也存储在磁盘上。下面讲述这些信息在磁盘上如何分布，UINX怎样来对它们实行管理。UNIX把文件的存储空间磁盘想象成是一个由连续物理块构成的文件卷，每个物理块含512个字节。在一个磁盘上，存放着普通文件的信息，存放着目录文件的信息，存放着文件的i节点，还要存放对磁盘存储区的管理信息（比如哪些块是空闲的，哪些块是已分配的等等）。图7-14给出了整个磁盘存储区的组织结构。,块0用来存放引导程序，它与文件管理关系不大。文件存储器全部资源

31、的管理信息（即filsys表）存放在块1，它是磁盘的管理区。从第2块起，存放磁盘上文件的i节点内容，这个区域称为索引节点区。索引节点区的后面是一般数据存储区，在那里存放普通文件和目录文件的信息。显然，在磁盘上，一般数据存储区所占用的磁盘空间为最大。下面对管理区中的资源管理信息表filsys、索引节点区中的i节点以及文件的目录分别加以介绍。1资源管理信息表filsys2目录和目录文件3i节点,7.3.3 UNIX文件的物理结构前面提及，UNIX文件的物理结构采用的是索引结构，这种索引结构是通过每个文件i节点中的数组di_addr 来形成文件存储索引表的。该数组总共有13个元素，每个元素为一个索引

32、项。前10个索引项直接指向文件数据存放的磁盘块号，后3个索引项分别构成一次间接索引、二次间接索引和三次间接索引的多级索引结构。这样，UNIX可以根据文件的大小，通过使用这张存储索引表，形成小型、中型、大型和巨型等不同规模的文件。,1小型文件的索引结构通常，每个磁盘块为512个字节。当一个文件的长度在110个磁盘块之间时，就称为小型文件。这时，用文件i节点中数组di_addr 的前10个表目，直接指向文件数据存放的磁盘块号。因此，在UNIX中，小型文件是通过i节点中的数组di_addr 构成一级索引表而获得文件在磁盘上的存储位置的。如图7-16所示。,2中型文件的索引结构当一个文件的长度在101

33、38磁盘块内时，就成为一个UNIX的中型文件。这时除了用到di_addr0di_addr9外，还要用到di_addr10，如图7-17所示。在图7-17中，di_addr0di_addr9仍然直接指向文件数据存放的10个磁盘块号，然后又利用di_addr10指向一个磁盘块。这块并不存放文件的数据，而是利用它形成又一级的索引。在UNIX中，用4个字节放一个磁盘块号，因此在这个盘块中，可以放128个磁盘块号。这样一来，通过di_addr10提供的索引，一个文件就可以达到138个磁盘存储块这么大。,3大型和巨型文件的索引结构当一个文件的长度在13816522磁盘块内时，就成为一个UNIX的大型文件。

34、这时除了用到di_addr0di_addr9外，要用到di_addr10，还要用到di_addr11，如图7-18所示。在图7-18中，di_addr0di_addr9直接指向文件数据存放的10个磁盘块号。然后如同图7-17那样，利用di_addr10指向一个磁盘块，由它提供128个磁盘块的索引，从而使文件总共达到138个磁盘存储块这么大。但这还不够，又利用di_addr11指向一个磁盘块，由它指向128个磁盘块，每个都是一个索引。这样，通过这128个索引、每个指向128个磁盘块，就又可以得到16384个磁盘块。于是，UNIX的大型文件最多可以拥有16522个磁盘块（即10+128+16384

35、）。,当一个文件所需的磁盘块大于16522个磁盘块时，就成为UNIX的巨型文件了。这时除了用到di_addr0di_addr9外，还要用到di_addr10、di_addr11和di_addr12。此时，文件的最大长度可以达到约11亿个字节，但是由于此时要经过多次间接索引，会使系统的查找速度大大降低。有关巨型文件的索引结构和它拥有的规模，留作一个习题去思考，这里就不具体解释了。,7.3.4 UNIX对文件存储空间的管理在磁盘上，UNIX总是把文件安排在一般数据存储区（见图7-14）。因此，UNIX对文件存储空间的管理，即是对磁盘上一般数据存储区的管理。在5.2.3节介绍使用“空闲块链”管理磁盘

36、上的空闲块时，曾提及“成组链接”法，并说UNIX操作系统就是采用这种方法来管理磁盘上的空闲块的。下面详细介绍它的实现过程。,在磁盘管理区filsys结构中，有两个内容涉及到磁盘空闲块的管理，一个是由数组s_free100构成的一个空闲磁盘块索引表。当一个文件要申请磁盘块时，就到这个索引表中去获得需要的空闲块；当一个磁盘块被释放时，就把它还回到这个索引表中。所以，这个索引表中记录的是当前系统可以直接分配的空闲磁盘块。另一个是s_nfree，它记录了s_free 中现有的可分配的空闲磁盘块数。,从形式上看，利用数组s_free100直接管理100个空闲的磁盘块，与利用数组s_inode100直接管

37、理100个空闲的i节点相类似，但实际上相差很远。因为除这100个直接管理的空闲块外，UNIX对其余的空闲块并没有放置不管，而是将它们分组进行链接。具体做法如图7-19所示。,UNIX把磁盘上一般数据存储区中的所有空闲块依次分组。为了下面讲述方便，对每一组的块都进行分别编号。具体的办法是：第1组为99块，编号为199（为什么第1组只有99块，后面会给出解释）。从第2组起，每组都是100块，剩下的块归并成为最后一组。它们都按099的顺序进行编号。在图7-19中，从右至左反映了这种分组的结构。在图中，假定最后一组中只有52个空闲块，各块的编号为051。分好组以后，总是在后一组的第0块中开辟101个位

38、置，依次存放前一组的总块数以及前一组中每一块的地址。也就是说，相当于总是在后一组中，开辟s_nfree和s_free100所需要的位置，用于存放前一组的分组信息。,在此，有两组的情况要做特殊处理。一个是第1组。在第1组中，实际只有99个空闲块。为了管理的需要，把它的总块数仍记为100，见图7-19中第2组里的s_nfree=100。另外，第一组磁盘块编号是从1开始的，因此在相当于第0号磁盘块的位置存放一个0，而不是某一个磁盘块的地址，见图7-19中第2组中的s_free0=0。,另一个要特殊处理的是最后一组。因为在最后一组的后面已经没有下一组了，所以UNIX就把它的所有信息存放在管理块的fil

39、sys中，即存放在filsys的s_nfree和s_free100中。由于现在最后一组只有52个空闲块，因此在filsys中的s_nfree取值为52，并且只用到数组s_free100的前52个元素，即用s_ferr0到s_free51存放最后一组的52个空闲块的地址。至此，成组链接的格局已经完成：在filsys的s_free 中，记录了当前直接可以分配的52个空闲块。在这52个空闲块的第0块中，记录了下一组100个空闲的磁盘块地址，下一组100个空闲的第0块中，记录了再下一组100个空闲的磁盘块地址，如此等等。,在采用“成组链接”法后，如何分配空闲块，如何回收空闲块？下面来讨论这两个问题。无

40、论是磁盘空闲块的分配还是回收，都是在filsys中的空闲磁盘块索引表s_free 中进行，并把它视为一个栈。分配时，做出栈操作；回收时，做进栈操作。s_nfree中记录的值，是s_free 中当前实际有的空闲块数，正好也是空闲磁盘块索引表s_free 中下一个可以使用的索引表目的下标。,因此，总是先在s_nfree上做减1操作，然后把s_frees_nfree中记录的磁盘块分配出去。这里要注意的是，如果在s_nfree上做减1操作后，其值等于0了，那么就是要把s_free0所指向的那一个磁盘空闲块分配出去。由于它是这一组的第0个磁盘块（按照分配顺序，它总是在一组中最后被分配出去），里面包含有它

41、前一组空闲块的信息在内。因此在把这一块分配出去之前，应该先把它记录的101个信息拷贝到filsys结构的s_nfree和s_free 里面去，然后才能将它分配出去。,分配时还要注意的一个问题是如果分配一直进行，现在要把第2组的第0块分配出去。根据前面所说，先把这块中记录的101个信息拷贝到filsys结构的s_nfree和s_free 里面去，然后才将它分配出去。这意味着系统现在只有最后99块能够分配了。如果分配仍然继续，直到把这99块全部分配出去。此时，filsys中的s_nfree=1，s_free0=0。若再申请空闲块，s_nfree减1后成为0，即要把s_free0所指的块分配出去。此

42、时发现s_free0=0，而不是一个磁盘块的地址，表明所有的磁盘空闲块都分配出去了，提出请求的进程只能阻塞等待。所以，这就是前面分组时把第1组只分99个空闲块，但仍然算这组有100个块，并将第0块指针处安放一个0的原因。,进行空闲块的回收时，就是将该块的地址登记在空闲磁盘块索引表的s_frees_nfree表目中,然后让s_nfree加1。不过要注意，在把释放块的地址存入索引表s_free 的表之前，必须检查s_nfree的取值。如果发现s_nfree等于100，那么表明这时空闲磁盘块索引表在此之前已经收集满了100个空闲的磁盘块，它们应该形成一个新的链组。现在要释放的一块，是下一组空闲块的第

43、0块。于是，就把filsys中的s_nfree和s_free0s_free99共101个值存入新释放块中，然后将此块的地址填入s_free0中，将s_nfree置为1。,7.3.5 UNIX的文件操作UNIX提供了一些系统调用命令，以便用户在程序一级完成对文件的操作。有关的系统调用是：creat、open、read、write、close、link和unlink等。下面对它们各自的功能做粗略的描述。1creat（建立文件）2open（打开文件）3close（关闭文件）4read（读）5write（写）,6link（链接）系统调用link可以为一个已经存在的文件开辟一条新的路径，也就是说，可以为

44、一个文件再取一个新的名字。它的使用格式是：link(pathname1，pathname2)；其中参数pathname1是原文件的路径名，参数pathname2为其新取的路径名。link处理程序先按照参数pathname2的指点，将新的文件名登记到指定的路径目录中。然后根据pathname1，找到原文件所对应的i节点编号，将该号填入新文件的文件目录中。由于每个文件的i节点编号是惟一的，因此经过link之后，两个不同路径名的文件就与同一个文件相对应了。,比如考虑图7-20(a)的情形。zong和wang要共同完成一项工作。zong为了访问对方的文件x，只能通过“/usr/wang/x”才能达到目

45、的。但如果通过命令：link（/usr/wang/x，/usr/zong/k）；那么，若当前目录为zong，则zong直接通过k就能够访问wang的文件x了，这是因为link命令在zong的文件k和wang的文件x之间建立了链接的缘故。如图7-20(b)所示。,7unlink（去链接）,7.4 UNIX的设备管理,7.4.1 UNIX设备管理概述UNIX是根据设备与内存之间信息交换的单位来对设备进行分类的，因此在整个系统中，归到设备管理的有两类设备：块设备和字符设备。前者与内存之间以成组信息为单位进行信息交换，比如硬盘、软盘、磁带都属于块设备。由于这些设备是用来存储信息的，因此有时把它们称为存

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

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

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

49、贝到指定的内存用户区。,块设备的每一个缓冲区长度为512个字节或1024个字节，这要由文件系统来确定。由一个个缓冲区，组成了供块设备输入/输出使用的缓冲池。为了便于管理，UNIX把缓冲池中的每个缓冲区分成两个部分：一个是真正用于存放数据的部分，一个是用于管理的部分。前者仍称为“缓冲区”，后者称为“缓冲区控制块”，并在缓冲区和缓冲区控制块之间保持一一对应的关系。图7-22给出了缓冲区控制块的内容和它与缓冲区的对应关系。,1空闲缓冲区队列为了构成系统中空闲缓冲区队列，UNIX设置了一个名为bfreelist的控制块，它的结构与缓冲区控制块相同，里面的av_forw和av_back就是块设备空闲缓冲

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