第十章 UNIX系统内核结构 10.1 UNIX系统概述 10.2 进程的描述和控制 10.3 进程的同步与通信 10.4 存储器管理

Presentation on theme: "第十章 UNIX系统内核结构 10.1 UNIX系统概述 10.2 进程的描述和控制 10.3 进程的同步与通信 10.4 存储器管理"— Presentation transcript:

1 第十章 UNIX系统内核结构 10.1 UNIX系统概述 10.2 进程的描述和控制 10.3 进程的同步与通信 10.4 存储器管理
10.2　进程的描述和控制 10.3　进程的同步与通信 10.4　存储器管理 10.5　设备管理 10.6　文件管理

2 10.1 UNIX系统概述 10.1.1 UNIX系统的发展史 1．UNIX系统的发展
　　UNIX系统是美国电报电话公司(AT&T)Bell实验室的Ennis Ritchie和Ken Thompson合作设计和实现的。他们在设计时，充分地吸取了以往OS(其中包括著名的CTSS和MULTICS系统)设计和实践中的各种成功经验和教训。在DEC公司的小型机PDP7上实现并于1971年正式移植到PDP11计算机上。

3 　　最初的UNIX版本是用汇编语言编写的。不久，Thompson用一种较高级的B语言重写了该系统。1973年Ritchie又用C语言对UNIX进行了重写， 形成了最早的正式文件UNIX V5 版本。1976年正式公开发表了UNIX V6版本，还开始向美国各大学及研究机构颁发了使用UNIX的许可证，并提供了源代码，以鼓励他们对UNIX加以改进，因而又推动了UNIX 的迅速发展。

4 　　1978年发表了UNIX V7版本，它是在PDP 11/70上运行的，后来移植到DEC公司的VAX系列计算机上。1982至1983年期间，又先后宣布了UNIX System Ⅲ和UNIX System Ⅴ；1984年推出了UNIX System Ⅴ2.0；1987年发布了UNIX System Ⅴ3.0版本，分别称为UNIX SVR 2和UNIX SVR 3；1989年宣布了UNIX SVR 4；1992年又发表了UNIX SVR 4.2版本。

5 　　2．两大集团对峙 　　在UNIX系统的发展史上必须说明的是，由于UNIX的开放性、发展概念和商业利益等因素，使UNIX呈现出“百家争鸣”的盛况，后又进一步形成了两大阵营对峙的局面。 此即，由IBM和DEC等公司于1988年5月结成了开放软件基金会OSF集团，以及由AT&T、SUN和NCR等公司于同年12月结成了UI集团。他们分别推出了自己的UNIX系统产品。其中，UI推出的是“SVR 4”，而OSF推出的是“OSF/I”。虽然两者都是UNIX，但它们在系统构架、命令操作以及管理方式上，都有所不同。两者在市场上展开了激烈的竞争。

6 　　应当看到，虽然两种UNIX系统并存，但在他们之间并不相互兼容，这对用户非常不利。因而，这无疑会影响到UNIX对用户的吸引力，加之，随着Microsoft公司的迅速崛起， 并以惊人的速度由传统的PC机市场向工作站和网络市场扩张，迫使UI和OSF两大集团不得不相互让步、携手言和，从而共同制定了应用程序接口API(Application Program Interface)标准技术规范，并联合开发共同开放软件环境COSE(Common Open Software Enviroment)。

7 　　由于UNIX这一名字已被X/Open用作注册商标，因而其他公司所开发的UNIX产品不能再用UNIX这一名字，致使不同的UNIX系统在不同的公司，甚至是在不同的机器上，都各用自己的名字，如IBM RS/6000上的“AIX”(System Ⅴ)操作系统、Sun公司的“Sun OS”(4.3 BSD或SVR 4)和“Solarix”操作系统、HP公司的“HPUX”(System Ⅴ)以及SCO公司的“SCO UNIX”(SVR 3.2)操作系统等。

8 　　3．网络操作系统UNIX 　　UNIX凭借其“开放性”、“先进性”以及先入为主的优势，使20世纪70年代成为UNIX时代。70年代同时也是网络的萌芽时代，相应地，1976年人们便开发了一个UNIX网络应用程序。该程序随着UNIX V7版本一并发行。1980年9月Bell实验室等又为美国国防部在Berkeley的UNIX上开发了TCP/IP协议系统，于1983年8月对外发行，该协议得以很快发表和普及，从而成为后来的Internet上最重要的网络协议。到80年代中期，他们已在UNIX System Ⅴ上开发出多种基于TCP/IP的网络软件，并将它们构成一个TCP/IP协议软件包。

9 20世纪80年代是LAN快速发展的10年。1984年，Novell公司推出了以LAN为环境的Netware V1
　　20世纪80年代是LAN快速发展的10年。1984年，Novell公司推出了以LAN为环境的Netware V1.0，继之它经过了不断的改进并增强了其功能，相应的版本由V1.0经过V2.X到V3.X。 仅经历短短的3年，到1987年时，其销量已占居全球第一位，并由于此后它长期保持优势而使之成为网络工业界的标准。

10 　　进入90年代后，企业网络和Internet得到极其迅速的发展和广泛应用，致使计算机网络已经无所不在，也形成了巨大的网络软件市场。此时，一些主要的UNIX系统开发商也加强了在网络方面更深入的研究，于是也不断地推出用于企业网络的UNIX网络OS版本，如SCO公司的Unixware NOS和Sun公司的Solaris NOS等。 　

11 10.1.2　UNIX系统的特征 　　1．开放性 　　UNIX系统最本质的特征是开放性。所谓开放性，是指系统遵循国际标准规范；凡遵循国际标准所开发的硬件和软件，均能彼此兼容，并可方便地实现互连。开放性已成为20世纪90年代计算机技术的核心问题，也是一个新推出的系统或软件能否被广泛应用的重要因素。人们普遍认为: UNIX是目前开放性最好的OS，是目前惟一能稳定运行在从微型机到大、中型等各种机器上的OS，而且还能方便地将已配置了UNIX OS的机器互连成计算机网络。

12 　　2．多用户、多任务环境 　　UNIX系统是一个多用户、多任务OS，它既可以同时支持数十个乃至数百个用户通过各自的联机终端同时使用一台计算机，而且还允许每个用户同时执行多个任务。例如，在进行字符图形处理时，用户可建立多个任务，分别用于处理字符的输入、图形的制作和编辑等任务。

13 　　3．功能强大且高效 　　UNIX系统提供了精选的、丰富的系统功能，使用户可方便、快速地完成许多其它OS所难于实现的功能。UNIX已成为世界上功能最强大的操作系统之一，而且它在许多功能的实现上还有其独到之处，并且是高效的。例如，UNIX的目录结构、磁盘空间的管理方式、I/O重定向和管道功能等。其中，不少功能及其实现技术已被其它OS所借鉴。

14 　　4．丰富的网络功能 　　UNIX系统还提供了十分丰富的网络功能。作为Internet网络技术基础的TCP/IP协议， 便是在UNIX系统上开发出来的，并已成为UNIX系统不可分割的部分。UNIX系统还提供了许多最常用的网络通信协议软件，其中包括网络文件系统NFS软件、客户/服务器协议软件Lan Manager Client/Server及IPX/SPX软件等。通过这些产品可以实现在各UNIX 系统之间， UNIX与Novell的Netware，以及MS-Windows NT、IBM LAN Server等网络之间的互连和互操作。

15 　　5．支持多处理器功能 　　与Windows NT及Netware等OS相比较，UNIX是最早提供支持多处理器功能的OS，它所能支持的多处理器数目也一直处于领先水平。例如，1996年推出的NT 4.0只能支持1～4个处理器，而Windows 2000最多也只支持16个处理器，然而UNIX系统在20世纪90年代中期便已能支持32～64个处理器，而且拥有数百个乃至数千个处理器的超级并行机也普遍支持UNIX。

16 10.1.3　UNIX系统的内核结构 　　可以把整个UNIX系统分成四个层次。其最低层是硬件，作为整个系统的基础。次低层是OS核心，包括前面所介绍的进程管理、存储器管理、设备管理和文件管理四大资源管理功能。上面第二层是OS与用户的接口Shell以及编译程序等。最高层是应用程序。作为OS的核心，它应具有两方面的接口：一方面是核心与硬件的接口，它通常是由一组驱动程序和一些基本的例程所组成的；另一方面就是核心与Shell的接口，它由两组系统调用及命令解释程序等所组成。核心本身又可分成两大部分：一部分是进程控制子系统；另一部分则是文件子系统。 两组系统调用分别与这两大子系统交互。图10-1示出了UNIX核心的框图。

17 图10-1　UNIX核心的框图

18 　　1．进程控制子系统 　　进程控制子系统负责对四大资源中的两大资源——处理机和存储器进行管理。进程控制子系统的功能可分成以下几个方面： 　　(1) 进程控制。在UNIX系统中提供了一系列用于对进程进行控制的系统调用，例如，应用程序可利用系统调用fork创建一个新进程；用系统调用exit结束一个进程的执行。 　　(2) 进程通信。在UNIX系统中提供了许多进程间通信的手段，例如，用于实现进程之间通信的消息机制，用于在同一用户的各进程之间通信的“信号”通信工具以及性能优良的信号量机制等。

19 　　(3) 存储器管理。该功能用于为进程分配物理存储空间。为了提高内存利用率且方便用户，可采用段页式存储管理方式；可利用请求调页法实现虚拟存储器功能，以便从逻辑上扩充内存。此外，还实现了外存与内存间的对换功能。 　　(4) 进程调度。在UNIX系统中所采用的进程调度算法，是动态优先数轮转调度算法。系统按优先数最小者优先的策略，为选中的某一进程分配一个CPU时间片。当进程运行完一个时间片后，内核便把它送回就绪队列的末尾。

20 　　2．文件子系统 　　文件子系统用于有效地管理系统中的所有设备和文件。其功能可分成以下三个方面： 　　(1) 文件管理。该功能用于为文件分配存储空间、管理空闲磁盘块、控制对文件的存取以及为用户检索数据。用户可通过一组系统调用来实现对文件的各种操作。 　　(2) 高速缓冲机制。为使核心与外设之间的数据流在速率上相匹配，设置了多个缓冲区，每个缓冲区的大小与一个盘块的大小相当。这些缓冲区被分别链入各种链表中，如空闲缓冲区链表等。

21 　　(3) 设备驱动程序。UNIX系统把设备分成块设备(如磁盘、磁带等)和字符设备(如打印机)两类。相应地，也把驱动程序分成两类，文件子系统将在缓冲机制的支持下，与块设备的驱动程序之间交互作用。

22 10.2 进程的描述和控制 10.2.1 进程控制块 在UNIX系统Ⅴ中，把进程控制块(PCB)分为四部分：
10.2　进程的描述和控制 10.2.1　进程控制块 　　在UNIX系统Ⅴ中，把进程控制块(PCB)分为四部分： 　　(1) 进程表项，其中包括最常用的核心数据。 　　(2) U区，用于存放用户进程表项的一些扩充数据。 　　(3) 系统区表，存放各个区在物理存储器中的地址信息等。 　　(4) 进程区表，用于存放各区的起始虚地址及指向系统区表中对应区表项的指针。

23 　　1．进程表项(Process Table Entry)
　　用于描述和控制一个进程的信息通常都很多，其中有些是经常要被访问的，如进程标识符、进程状态等。为了提高对这些信息访问的效率，系统设计者将这些信息放在进程表项中，又称之为Proc表或Proc结构，使之常驻内存。在每个进程表项中，含有下述一些具体信息： 　　(1) 进程标识符(PID)，也称内部标识符，为方便用户使用，这里惟一地标识一个进程的某个整数。 　　(2) 用户标识符(UID)，标识拥有该进程的用户。 　

24 　　(3) 进程状态，表示该进程的当前状态。 　　(4) 事件描述符，记录使进程进入睡眠状态的事件。 　　(5) 进程和U区在内存或外存的地址，核心可利用这些信息做上、下文切换。 　　(6) 软中断信息，记录其它进程发来的软中断信号。 　　(7) 计时域，给出进程的执行时间和对资源的利用情况。 　　(8) 进程的大小，这是核心在为进程分配存储空间时的依据，包括正文段长度和栈段长度等。

25 　　(9) 偏置值nice，供计算该进程的优先数时使用，可由用户设置。
　　(10) P_Link指针，这是指向就绪队列中下一个PCB的指针。 　　(11) 指向U区进程正文、数据及栈在内存区域的指针。

26 　　2．U区(U Area) 　　为了存放用于描述和控制进程的另一部分信息，系统为每一个进程设置了一个私用的U区，又称之为User结构，这部分数据并非常驻内存，其中含有下述信息： 　　(1) 进程表项指针，指向当前(正在执行)进程的进程表项。 　　(2) 真正用户标识符u-ruid(real user ID)，这是由超级用户分配给用户的标识符，以后，每次用户在登录进入系统时，均须输入此标识符。

27 　　(3) 有效用户标识符u-euid(effective user ID)，在一般情况下，它与ruid相同，但在其他用户允许的情况下，可用系统调用setuid将它改变为其他用户标识符，以获得对该用户的文件进行操作的权力。 　　(4) 用户文件描述符表，其中记录了该进程已打开的所有文件。 　　(5) 当前目录和当前根，用于给出进程的文件系统环境。 　　(6) 计时器，记录该进程及其后代在用户态和核心态运行的时间。

28 　　(7) 内部I/O参数，给出要传输的数据量、源(或目标)数据的地址、文件的输入/输出偏移量。
　　(8) 限制字段，指对进程的大小及其能“写”的文件大小进行限制。 　　(9) 差错字段，记录系统调用执行期间所发生的错误。 　　(10) 返回值，指出系统调用的执行结果。 　　(11) 信号处理数组，用于指示在接收到每一种信号时的处理方式。

29 　　3．系统区表(System Region Table)
　　系统Ⅴ把一个进程的虚地址空间划分为若干个连续的区域：正文区、数据区、栈区等。 这些区是可被共享和保护的独立实体。多个进程可共享一个区，例如，多个进程共享一个正文区，即几个进程将执行同一个(子)程序。同样，多个进程也可共享一个数据区。为了对区进行管理，在核心中设置了一个系统区表(简称区表)，在各表项中记录了以下有关描述活动区的信息：

30 　　(1) 区的类型和大小。 　　(2) 区的状态。一个区有这样几种状态: 锁住、在请求中、在装入过程、有效(区已装入内存)。 　　(3) 区在物理存储器中的位置。 　　(4) 引用计数，即共享该区的进程数。 　　(5) 指向文件索引结点的指针。

31 　　4．进程区表(Process Region Table)
　　为了记录进程的每个区在进程中的虚地址，并通过它找到该区在物理存储器中的实地址，系统为每个进程配置了一张进程区表。表中的每一项记录一个区的起始虚地址及指向系统区表中对应的区表项的指针。这样，核心可通过查找进程区表和系统区表，将区的逻辑地址变换为物理地址。可见，进程区表和系统区表用于对区地址进行映像(射)。这里用两张区表实现地址映射，是为了便于实现对区的共享。

32 　　图10-2示出A和B两个进程的进程区表和系统区表。在A进程区表中的正文区、数据区和栈区中的指针，分别指向相应于a、b、c区的系统区表项。由于A和B进程共享正文区， 故它们都指向同一个正文区a。一个进程的数据结构是由上述的进程表项、U区、进程区表与系统区表项所组成的，它们之间的关系如图10-3所示。 　

33 图10-2　进程区表项、系统区表项和区的关系

34 图10-3　进程的数据结构

35 10.2.2　进程状态与进程映像 　　1．进程状态 　　在UNIX内核中，为进程设置了如图10-4所示的9种状态。

36 图10-4　进程的状态转换

37 　　(1) 执行状态。这表示进程已获得处理机而正在执行。UNIX系统把执行状态又进一步分为两种:一种是用户态执行，表示进程正处于用户状态中执行；另一种是核心态执行，表示一个应用进程执行系统调用后，或I/O中断、时钟中断后，进程便处于核心态执行。这两种状态的主要差别在于：处于用户态执行时，进程所能访问的内存空间和对象受到限制，其所占有的处理机是可被抢占的；而处于核心态执行中的进程，则能访问所有的内存空间和对象，且所占用的处理机是不允许被抢占的。

38 　　(2) 就绪状态。这是指进程处于一种只需再获得处理机便可执行的状态。由于UNIX内核提供了对换功能，因而又可把就绪状态分为“内存中就绪”和“就绪且换出”两种状态。当调度程序调度到“内存中就绪”状态的进程时，该进程便可立即执行；而调度到“就绪且换出”状态的进程时，则须先将该进程映像全部调入内存后，再使其执行。

39 　　(3) 睡眠状态。使一个进程由执行状态转换为睡眠状态的原因有许多，如因进程请求使用某系统资源而未能得到满足时；又如进程使用了系统调用wait( )后，便主动暂停自己的执行，以等待某事件的出现等。在UNIX中把睡眠原因分为64种，相应地，最多也可设置64个睡眠队列。同样，由于对换功能的原因又可将睡眠状态分为“内存睡眠”状态和“睡眠且换出”状态。当内存紧张时，在内存中睡眠的进程可被内核换出到外存上，相应地，此时进程的状态便由“内存睡眠”状态转换为“睡眠且换出”状态。

40 　　(4) “创建”与“僵死”状态。创建状态是指利用fork系统调用来创建子进程时，被创建的新进程所处的状态；僵死状态是在进程执行了exit系统调用后所处的状态，此时该进程实际上已不存在，但还留下一些信息供父进程搜集。 　　(5) “被抢占”状态，也称为“被剥夺状态”。当正在核心态执行的进程要从核心态返回到用户态执行时，如果此时已有一优先级更高的进程在等待处理机，则此时内核可以抢占(剥夺)已分配给正在执行进程的处理机，去调度该优先级更高的进程执行。这时，被抢占了处理机的进程便转换为“被抢占”状态。处于“被抢占”状态的进程与处于“内存中就绪”状态的进程是等效的，它们都被排列在同一就绪队列中等待再次被调度。 　

41 　　2．进程映像 　　1) 用户级上下文 　　用户级上下文的主要成分是用户程序。它在系统中可分为正文区和数据区两部分。正文区是只读的，它主要包括一些程序指令。进程在执行时，可利用用户栈区来保存过程调用时的传送参数和返回值。共享存储区是一个能与其它进程共享的数据区。存储区中的数据可由有权共享该存储区的进程所共享。

42 　　2) 寄存器上下文 　　寄存器上下文主要是由CPU中的一些寄存器的内容所组成的。主要的寄存器有下述几种。 　　(1) 程序寄存器。在其中存放的是CPU要执行的下一条指令的虚地址。 　　(2) 处理机状态寄存器(PSR)。其中包括运行方式(用户态或核心态)、处理机当前的运行级以及记录处理机与该进程有关的硬件状态信息，如产生进位和溢出等。 　　(3) 栈指针。该指针指向栈的下一个自由项或栈中最后使用的项(因机器而异)。 　　(4) 通用寄存器。该寄存器用于存放进程在运行过程中所产生的数据，通用寄存器的数目也因机器而异。

43 　　3) 系统级上下文 　　系统级上下文包括OS为管理该进程所用的信息，可分为静态和动态两部分： 　　(1) 静态部分。在进程的整个生命期中，系统级上下文的静态部分只有一个，其大小保持不变，又可再进一步把它分成三部分：进程表项、U区及进程区表项、系统区表项和页表。 　　(2) 动态部分。在整个进程的生命期中，系统级上下文动态部分的大小是可变的，它包括：① 核心栈，这是进程在核心态时使用的栈；② 若干层寄存器上下文，其中，每一层都保存了前一层的上下文。 　

44 10.2.3　进程控制 　　1．fork系统调用 　　在UNIX的内核中设置了一个0进程，它是惟一一个在系统引导时被创建的进程。在系统初启时，由0进程再创建1进程，以后0进程变为对换进程，1进程成为系统中的始祖进程。 UNIX利用fork为每个终端创建一个子进程为用户服务，如等待用户登录、执行shell命令解释程序等。每个终端进程又可利用fork来创建自己的子进程，如此下去可以形成一棵进程树。因此说，系统中除0进程外的所有进程都是用fork创建的。

45 　　fork系统调用如果执行成功，便可创建一个子进程，子进程继承父进程的许多特性，并具有与父进程完全相同的用户级上下文。核心需为fork完成下列操作：

46 　　(3) 拷贝进程表项中的数据。将父进程表项中的数据拷贝到子进程的进程表项中，并置进程的状态为“创建”状态。
　　(4) 子进程继承父进程的所有文件。对父进程的当前目录和所有已打开文件的文件表项中的引用计数f.count做加1操作，表示这些文件又增加了一个访问者，详见10.6节。

47 　　(5) 为子进程创建进程上下文。首先，由核心为子进程创建进程上下文的静态部分，并将其父进程上下文的静态部分拷贝到子进程的上下文中。然后，再为子进程创建进程上下文的动态部分。至此，进程的创建即告结束，再置子进程的状态为“内存中就绪”。最后，返回该子进程的标识符。 　　(6) 子进程执行。当子进程被调度执行时，将U区的计时字段初始化后返回0。

48 　　2．exec系统调用 　　在UNIX系统中，当利用fork系统调用创建一个新进程时，只是将父进程的用户级上下文拷贝到新建的子进程中。而UNIX系统又提供了一组系统调用exec，用于将一个可执行的二进制文件覆盖在新进程的用户级上下文的存储空间上，以更新新进程的用户级上下文。UNIX所提供的这一组exec系统调用，它们的基本功能相同，只是它们须各自以不同的方式提供参数，且参数各异。一种方式是直接给出指向参数的指针，另一种方式则是给出指向参数表的指针。

49 图10-5　exec Ⅴ的参数组织方式

50 　　(1) 对可执行文件进行检查。先调用检索目录的过程namei，以沿着目录树去获得指名可执行文件的索引结点。由于在索引结点中存放了相应文件的全部属性，因而可以从中得知该文件是否是可执行的，用户是否拥有执行的许可(权)。若可执行，便再将新的exec Ⅴ参数拷贝到一个临时缓冲区，以腾出参数占用的空间，然后将这些空间释放。 　　(2) 回收内存空间。对原来与进程连接的各个区，逐个断开其连接，并收回它们所占用的内存空间。

51 　　(3) 分配存储空间。根据可执行文件头中的信息(包括文件中的所有正文段和数据段的大小、进程执行时的起始地址等)，为每个段分配新区，并将它们连接到进程上。若有足够的内存空间，可将这些新区装入内存。
　　(4) 参数拷贝。将exec参数由临时缓冲区拷贝到新的用户栈区，并设置用户态寄存器上下文，如用户栈指针、程序计数器等。

52 　　3．exit系统调用 　　为了及时回收进程所占用的资源，对于一般的用户进程，在其任务完成后应尽快撤消该进程。UNIX内核利用exit来实现进程的自我终止。通常，父进程在创建子进程时，应在子进程的末尾安排一条exit，使子进程能自我终止。内核需为exit完成以下操作： 　　(1) 关闭软中断。由于进程即将终止而不再处理任何软中断信号，故应将软中断处理函数关闭。如果终止的进程是与某一终端相联系的进程组组长，则还须向本组中的各进程发送“挂起”软中断信号，并将它们交给进程1处理。

53 　　(2) 回收资源。关闭所有已打开的文件，释放进程所有的区及相应的内存，释放当前目录及修改根目录的索引结点。
　　(3) 写记账信息。将进程在运行过程中所产生的记账数据(其中含有进程运行时的各种统计数据)记录到一个全局记账文件中。 　　(4) 置进程为“僵死”状态。在做完上述处理后，便可将进程置为“僵死”状态，执行exit系统调用的子进程还应向父进程发送“子进程死”的软中断信号，最后由内核进行上下文切换，调度另一进程执行。

54 　　4．wait系统调用 　　wait系统调用用于将调用进程挂起，直至其子进程因暂停或终止而发来软中断信号为止。如果在wait调用前已有子进程暂停或终止，则调用进程做适当处理后便返回。核心对wait调用做以下处理：核心查找调用进程是否还有子进程，若无，便返回出错码；如果找到一个处于“僵死”状态的子进程，便将子进程的执行时间加到其父进程的执行时间上，并释放该子进程的进程表项；如果未找到处于“僵死”状态的子进程，则调用进程便在可被中断的优先级上睡眠，等待其子进程发来软中断信号时被唤醒。

55 10.2.4　进程调度与切换 　　1．引起进程调度的原因 　　首先，由于UNIX系统是分时系统，因而其时钟中断处理程序须每隔一定时间便对要求进程调度程序进行调度的标志runrun予以置位，以引起调度程序重新调度。其次，当进程执行了wait、exit及sleep等系统调用后要放弃处理机时，也会引起调度程序重新进行调度。此外，当进程执行完系统调用功能而从核心态返回到用户态时，如果系统中又出现了更高优先级的进程在等待处理机时，内核应抢占当前进程的处理机，这也会引起调度。

56 　　2．调度算法　 　　采用动态优先数轮转调度算法进行进程调度。调度程序在进行调度时，首先从处于“内存就绪”或“被抢占”状态的进程中选择一个其优先数最小(优先级最高)的进程。若此时系统中(同时)有多个进程都具有相同的最高优先级，则内核将选择其中处于就绪状态或被抢占状态最久的进程，将它从其所在队列中移出，并进行进程上下文的切换，恢复其运行。

57 　　3．进程优先级的分类 　　UNIX系统把进程的优先级分成两类，第一类是核心优先级，又可进一步把它分为可中断和不可中断两种。当一个软中断信号到达时，若有进程正在可中断优先级上睡眠，该进程将立即被唤醒；若有进程处于不可中断优先级上，则该进程继续睡眠。诸如“对换”、“等待磁盘I/O”、“等待缓冲区”等几个优先级，都属于不可中断优先级；而“等待输入”、“等待终端输出”、“等待子进程退出”几个优先级，都是可中断优先级。另一类是用户优先级， 它又被分成n+1级，其中第0级为最高优先级，第n级的优先级最低。

58 　　4．进程优先数的计算 　　在进程调度算法中，非常重要的部分是如何计算进程的优先数。在系统Ⅴ中，进程优先数的计算公式可表示如下： 其中，基本用户优先数即proc结构中的偏移值nice，可由用户将它设置成0～40中的任一个数。一旦设定后，用户仅能使其值增加，特权用户才有权减小nice的值。而最近使用CPU的时间，则是指当前占有处理机的进程本次使用CPU的时间。内核每隔 ms便对该时间做加1操作， 这样，占有CPU的进程其优先数将会随着它占有CPU时间的增加而加大，相应地，其优先级便随之降低。

59 　　5．进程切换 　　在OS中，凡要进行中断处理和执行系统调用时，都将涉及到进程上下文的保存和恢复问题，此时系统所保存或恢复的上下文都是属于同一个进程的。而在进程调度之后，内核所应执行的是进程上下文的切换，即内核是把当前进程的上下文保存起来，而所恢复的则是进程调度程序所选中的进程的上下文，以使该进程能恢复执行。

60 10.3 进程的同步与通信 10.3.1 sleep与wakeup同步机制 1．sleep过程
10.3　进程的同步与通信 10.3.1　sleep与wakeup同步机制 　　1．sleep过程 　　进入sleep过程后，核心首先保存进入睡眠时的处理机运行级，再提高处理机的运行优先级来屏蔽所有的中断，接着将该进程置为“睡眠”状态，将睡眠地址(对应着某个睡眠事件)保存在进程表项中，并将该进程放入睡眠队列中。如果进程的睡眠是不可中断的，做了进程上下文的切换后，进程便可安稳地睡眠。当进程被唤醒并被调度执行时，将恢复处理机的运行级为进入睡眠时的值，此时允许中断处理机。

61 　　如果进程的睡眠可被中断，但该进程并未收到软中断信号，则在做了进程上下文的切换后也进入睡眠状态。当它被唤醒并被调度执行时，应再次检查是否有待处理的软中断信号； 若仍无，则恢复处理机的运行级为进入睡眠时的值，最后返回0。 　　如果在进入睡眠前检测到有软中断信号，那么进程是否还要进入睡眠状态将取决于该进程的优先级。如果它是不可中断的优先级，进程仍进入睡眠，直至被wakeup唤醒；否则， 即若进程的优先级为可中断的，则进程便不再进入睡眠，而是响应软中断。

62 　　2．wakeup过程 　　该过程的主要功能是唤醒在指定事件队列上睡眠的所有进程，并将它们放入可被调度的进程队列中。如果进程尚未被装入内存，应唤醒对换进程；如果被唤醒进程的优先级高于当前进程的优先级，则应重置调度标志。最后，在恢复处理机的运行级后返回。

63 10.3.2　信号机制 　　1．信号机制的基本概念 　　信号机制主要是作为在同一用户的诸进程之间通信的简单工具。信号本身是一个1～19中的某个整数，用来代表某一种事先约定好的简单消息。每个进程在执行时，都要通过信号机制来检查是否有信号到达。若有信号到达，表示某进程已发生了某种异常事件，便立即中断正在执行的进程，转向由该信号(某整数)所指示的处理程序，去完成对所发生的事件(事先约定)的处理。处理完毕，再返回到此前的断点处继续执行。可见，信号机制是对硬中断的一种模拟，故在早期的UNIX版本中又称其为软中断。

64 　　信号机制与中断机制之间的相似之处表现为：信号和中断都同样采用异步通信方式，在检测出有信号或有中断请求时，两者都是暂停正在执行的程序而转去执行相应的处理程序，处理完后都再返回到原来的断点；再有就是两者对信号或中断都可加以屏蔽。 　　信号与中断两机制之间的差异是：中断有优先级，而信号机制则没有，即所有的信号都是平等的；再者是信号处理程序是在用户态下运行的，而中断处理程序则是在核心态下运行；还有，中断响应是及时的，而对信号的响应通常都有较长的时间延迟。 　　

65 　　2．信号机制的功能 　　1) 发送信号 　　这是指由发送进程把信号送至指定目标进程的proc结构中信号域的某一位上。如果目标进程正在一个可被中断的优先级上睡眠，核心便将目标进程唤醒，发送过程就此结束。一个进程可能在其信号域中有多个位被置位， 代表已有多种类型的信号到达， 但对于一类信号， 进程却只能记住其中的某一个。进程可利用系统调用kill向另一进程或一组进程发送一个信号。

66 　　2) 设置对信号的处理方式 　　在UNIX系统中，可利用系统调用signal(sig，func)来预置对信号的处理方式。其中， 参数sig为信号名，func用于预置处理方式，可分成三种情况： 　　(1) func=1时，进程对sig类信号不予理睬，亦即屏蔽了该信号。 　　(2) func=0，即为缺省值时，进程在收到sig信号后应自我终止。 　　(3) func为非0、非1类整数时，就把func的值作为指向某信号处理程序的指针。

67 　　3) 对信号的处理 　　当一个进程要进入或退出一个低优先级睡眠状态时，或一个进程即将从核心态返回到用户态时，核心都要检查该进程是否已收到信号。当进程处于核心态时，即使收到信号也不予理睬；仅当进程返回到用户态时，才处理信号。对信号的处理分三种情况进行：当func=1时，进程不做任何处理便返回；当func=0时，进程自我终止；当其值为非0、非1的整数时，系统从核心态转为用户态后，便转向相应信号的处理程序(因为该程序是用户程序，故应运行在用户态)，处理完后，再返回到用户程序的断点。

68 10.3.3　管道机制 　　1．管道的类型 　　1) 无名管道(Unnamed Pipes) 　　在早期的UNIX版本中，只提供了无名管道。这是一个临时文件，是利用系统调用pipe( )建立起来的无名文件(指无路径名)。 只用该系统调用所返回的文件描述符来标识该文件， 因而，只有调用pipe的进程及其子孙进程才能识别此文件描述符，从而才能利用该文件(管道)进行通信。当这些进程不再需要此管道时，由核心收回其索引结点。 　

69 　　2) 有名管道(Named Pipes) 　　为了克服无名管道在使用上的局限性，以便让更多的进程能够利用管道进行通信，在UNIX系统中又增加了有名管道。有名管道是利用mknod系统调用建立的、可以在文件系统中长期存在的、具有路径名的文件，因而其它进程可以感知它的存在，并能利用该路径名来访问该文件。对有名管道的访问方式像访问其它文件一样，都需先用Open系统调用将它打开。不论是有名管道、还是无名管道，对它们的读写方式是相同的。

70 　　2．对无名管道的读写 　　1) 对pipe文件大小的限制 　　为了提高进程的运行效率，pipe文件只使用索引结点中的直接地址i-addr(0)～i-addr(9)。如果每个盘块的大小为4 KB， 则pipe文件的最大长度被限制在40 KB之内。 核心将索引结点中的直接地址项作为一个循环队列来管理，为它设置一个读指针和一个写指针， 按先进先出顺序读写。

71 　　2) 进程互斥 　　为使读、写进程互斥地访问pipe文件，只须使诸进程互斥地访问pipe文件索引结点中的直接地址项。因此，每逢进程在访问pipe文件前，都须先检查该索引结点是否已经上锁。 若已锁住，进程便睡眠等待；否则，将索引结点上锁，然后再执行读、写操作。操作结束后又将该索引结点解锁，并唤醒因该索引结点上锁而睡眠的进程。

72 　　3) 进程写管道 　　当进程向管道写数据时，可能有以下两种情况：如果管道中有足够的空间能存放要写的数据，在每写完一(盘)块后，核心便自动增加地址项的大小。当写完i-addr(9)地址项中所指示的盘块时，便又向i-addr(0)地址项所指示的盘块中写数据，全部写完后，核心修改索引结点中的写指针，并唤醒因该管道空而睡眠等待的进程。如果管道中无足够的空间来存放要写入的数据，核心将对该索引结点做出标志，然后让写进程睡眠等待，直到读进程将数据从管道中读出后，才唤醒等待写进程

73 　　4) 进程读管道 　　当进程从管道中读数据时，也同样会有两种可能：如果管道中已有足够的数据供进程读，读进程便根据读指针的初始值去读数据。每读出一块后，便增加地址项的大小。读完时，核心修改索引结点中的读指针，并唤醒所有等待的写进程。如果进程所要读的数据比管道中的数据多，则可令读进程把管道中已有数据读完后，暂时进入睡眠状态等待，直至写进程又将数据写入管道后，再将读进程唤醒。

74 10.3.4　消息机制 　　1．消息和消息队列 　　1) 消息(message) 　　消息是一个格式化的、可变长度的信息单元。消息机制允许进程发送一个消息给任何其它进程。由于消息的长度是可变的，因而为便于管理而把消息分为消息首部和消息数据区两部分。在消息首部中，记录了消息的类型和大小且指向消息数据区的指针以及消息队列的链接指针等是定长的。在图10-6 中示出了消息队列i中的三个消息首部msgh0、msgh3和msgh2。它们分别利用一个指向缓冲区(数据区)的指针指出消息的位置。

75 图10-6　消息机制中的数据结构

76 　　2) 消息队列 　　当一个进程收到由其它多个进程发来的消息时，可将这些消息排成一个消息队列，每个消息队列有一个称为关键字key的名称，它是由用户指定的。每个消息队列还有一个消息队列描述符，其作用与用户文件描述符一样，以方便用户和系统对消息队列的访问。在一个系统中可能有若干个消息队列，由所有的消息队列的头标组成一个头标数组。图10-6示出了消息和消息队列的数据结构。

77 　　2．消息队列的建立与操作 　　1) 消息队列的建立 　　在一个进程要利用消息机制与其它进程通信之前，应利用系统调用msgget( )先建立一个指名的消息队列。对于该系统调用，核心将搜索消息队列头标表，确定是否有指定名字的消息队列。若无，核心将分配一个新的消息队列头标，并对它进行初始化，然后给用户返回一个消息队列描述符；否则，它只是检查该消息队列的许可权后便返回。

78 　　2) 消息队列的操纵 　　用户可利用msgctl( )系统调用对指定的消息队列进行操纵。在该系统调用中包括三个参数，其中，msgid为消息队列描述符；cmd是规定的命令；buf是用户缓冲区地址，用户可在此缓冲区中存放控制参数和查询结果。命令可分为三类:　(1) 用于查询有关消息队列的情况的命令，如查询队列中的消息数目、队列中的最大字节数、最后一个发送消息的进程的标识符、发送时间等。 　　(2) 用于设置和改变有关消息队列的属性的命令，如改变消息队列的用户标识符、用户组标识符、消息队列的许可权等。 　　(3) 消除消息队列的标识符。

79 　　3．消息的发送和接收 　　1) 消息的发送 　　当进程要与其它进程通信时，可利用msgsnd( )系统调用来发送消息。对于msgsnd( )系统调用，核心检查消息队列描述符和许可权是否合法，消息长度是否超过系统规定的长度。 通过检查后，核心为消息分配消息数据区，并将消息从用户消息缓冲区拷贝到消息数据区。分配消息首部，将它链入消息队列的末尾；在消息首部中填写消息的类型、大小以及指向消息数据区的指针等；还要修改消息队列头标中的数据(如消息队列中的消息数、字节数等)。然后，唤醒在等待消息到来的睡眠进程。

80 　　2) 消息的接收 　　进程可利用msgrcv( )系统调用，从指定消息队列中读一个消息。对于msgrcv( )系统调用，先由核心检查消息队列标识符和许可权，继而根据用户指定的消息类型做相应的处理。消息类型msgtyp的参数可能有三种情况：当msgtyp=0时，核心寻找消息队列中的第一个消息，并将它返回给调用进程；当msgtyp为正整数时，核心返回指定类型的第一个消息；当msgtyp为负整数时，核心应在其类型值小于或等于msgtyp绝对值的所有消息中，选出类型值最低的第一个消息返回。如果所返回消息的大小等于或小于用户的请求，核心便将消息正文拷贝到用户区，再从队列中删除该消息，并唤醒睡眠的发送进程；如果消息长度比用户要求的大，则系统返回出错信息。用户也可忽略对消息大小的限制，此时，核心无需理会消息的大小而一概把消息内容拷贝到用户区。

81 10.3.5　共享存储区机制 　　1．共享存储区 　　共享存储区(Shared Memory)机制是UNIX系统中通信速度最高的一种通信机制。该机制一方面可使若干进程共享主存中的某个区域，且使该区域出现在多个进程的虚地址空间中。另一方面，在一个进程的虚地址空间中又可连接多个共享存储区，每个共享存储区都有自己的名字。当进程间欲利用共享存储区进行通信时，须首先在主存中建立一个共享存储区，然后将该区附接到自己的虚地址空间上。此后，进程之间便可通过对共享存储区中数据的读和写来实现直接通信。图 10-7 中示出了两个进程通过共享一个存储区进行通信的例子。其中，进程A将建立的共享存储区附到自己的AA′区域，进程B则将它附接到自己的BB' 区域。

82 图10-7 利用共享存储区进行通信

83 　　2．共享存储区的建立与操纵 　　1) 共享存储区的建立 　　当进程要利用共享存储区与另一进程进行通信时，须先利用系统调用shmget( )建立一块共享存储区，并提供该共享存储区的名字key和共享存储区以字节为单位的长度size等参数。若系统中已经建立了指名的共享存储区，则该系统调用将返回该共享存储区的描述符shmid；若尚未建立，便为进程建立一个指定大小的共享存储区。

84 　　2) 共享存储区的操纵 　　如同消息机制一样，可以用shmctl( )系统调用对共享存储区的状态信息进行查询，如其长度、所连接的进程数、创建者标识符等；也可设置或修改其属性，如共享存储区的许可权、当前连接的进程计数等；还可用来对共享存储区加锁或解锁，以及修改共享存储区标识符等。

85 　　3．共享存储区的附接与断开 　　在进程已经建立了共享存储区或已获得了其描述符后，还须利用系统调用shmat( )将该共享存储区附接到用户给定的某个进程的虚地址shmaddr上，并指定该存储区的访问属性，即指明该区是只读，还是可读可写。此后，该共享存储区便成为该进程虚地址空间的一部分。进程可采取与对其它虚地址空间一样的存取方法来访问。当进程不再需要该共享存储区时，再利用系统调用shmdt( )把该区与进程断开。

86 10.3.6　信号量集机制 　　1．信号量与信号量集 　　1) 信号量 　　在UNIX系统中规定，每个信号量有一个可用来表示某类资源数目的信号量值和一个操作值，该操作值可为正整数、零或负整数三种情况之一。传统的信号量机构是对信号量施加wait及signal操作。而在UNIX系统中则并未采用wait及signal，而是利用semop( )系统调用对指定的信号量施加操作。此外，还可利用semget( )来建立信号量及利用semctl( )系统调用对信号量进行操纵。

87 　　2) 信号量集 　　在一个信号量集中，通常都包含有若干个信号量。对这组信号量的操作方式应当是原子操作方式，此即，把对这组信号量视为一个整体，要么全做，要么全不做。如果核心不能完成对这组所有信号量的操作，则核心应将已经操作过的信号量恢复到操作前的状态，这样便可实现要么全做、要么全不做的原子操作方式。

88 　　2．信号量集的数据结构 　　1) 信号量表 　　信号量表是信号量的结构数组。在系统Ⅴ中，每个信号量用一个信号量结构表示。其中，包括信号量值semval及最近一次对信号量进行操作的进程标识符sempid、等待该信号量值增加的进程数等。

89 　　2) 信号量集表 　　信号量集表是信号量集的索引结构数组，其中的每一个元素都对应于一个信号量集，其内容有：访问权限、指向信号量集中第一个信号量的指针、信号量集中信号量的数目、最近对信号量执行操作的时间。信号量表与信号量集表间的关系示于图10-8中。

90 图10-8　信号量集表与信号量表

91 　　3．系统调用 　　在信号量机制中，同样也提供了若干条系统调用，分别用于对信号量执行各种操作。 　　1) semget( )系统调用 　　用户可利用该系统调用来建立信号量集。用户应提供信号量的名字、信号量集中信号量的数目等。若信号量集的建立成功，将返回信号量集的描述符semid。

92 　　2) semop( )系统调用 　　该系统调用可用来对信号量集进行操作。用户需提供信号量集的描述符、信号量的编号，即信号量在信号量集中的序号，以及所要施加操作的操作数semop。内核根据semop来改变信号量的值。当semop为正值时，便将该正值加到信号量的值上。当semop为负值时， 若信号量的值大于semop的绝对值，应将该负值加到信号量值上；否则，操作失败，内核将已经操作过的信号量恢复到该系统调用开始执行时的值。

93 10.4 存 储 器 管 理 10.4.1 请求调页管理的数据结构 1．页表和磁盘描述表 1) 页表
10.4　存 储 器 管 理 10.4.1　请求调页管理的数据结构 　　1．页表和磁盘描述表 　　1) 页表 　　为了实现请求调页策略，UNIX系统Ⅴ将进程的每个区分为若干个虚页，可把这些虚页分配到不相邻接的页框中，为此而设置了一张页表。在其每个表项中，记录了每个虚页和页框间的对照关系。为了支持请求调页，在页表项中需包含下述若干字段(见图10-9(a)所示)：

94 　　·页框号：此即第五章中所介绍的、在内存中的物理块号；
　　·年龄位：用于指示该页在内存中最近已有多少时间未被访问； 　　·访问位：指示该页最近是否被访问过； 　　·修改位：指示该页内容是否被修改过，修改位在该页第一次被装入时置为0； 　　·有效位：指示该页内容是否有效； 　　·写时拷贝(copy on write)字段: 当有多个进程共享一页时，须设置此字段，用于指示在某共享该页的进程要修改该页时，系统是否已为该页建立了拷贝； 　　·保护位: 指示此页所允许的访问方式，是只读还是读/写。

95 　　2) 磁盘块描述表 　　在请求调页机制中，若发现缺页，系统应将所缺页调入内存。但应从何处将其调入内存呢? 对于同一个虚页，在不同情况下应从不同的地方调入内存。例如，对于进程中从未执行过的虚页，在第一次调入内存时，应从可执行文件中取出。对于那些已经执行过的虚页，则应从对换区中将之调入内存。为此而引入了磁盘块描述表，用它来记录进程在不同时候的每个虚页在硬盘中的盘块号。这样，当进程在运行中发现缺页时，可通过查找该页表的方法来找到所需调入页面的位置。

96 　　一个进程的每一页对应一个磁盘描述表项，如图10-9(b)所示。它描述了每一个虚页的磁盘拷贝。其中，包括对换设备号、设备块号和存储器类型。当一个虚页的拷贝在可执行文件的盘块中时，此时在盘块描述表中的存储器类型为File，设备块号是文件的逻辑块号。若虚页的内容已经拷贝到对换设备上，则此时的存储器类型应为Disk。对换设备号和设备块号则用于指示该虚页的拷贝所驻留的逻辑对换设备和相应的盘块号。

97 图10-9　页表项和磁盘描述表项

98 　　2．页框数据表和对换使用表 　　1) 页框数据表 　　每个页框数据表项描述了内存的一个物理页。每个表项包括有下列各项： 　　·页状态：指示该页的拷贝是在对换设备上，还是在可执行文件中。 　　·内存引用计数：指出引用该页面的进程数目。 　　·逻辑设备：指含有此拷贝的逻辑设备，它可以是对换设备，也可以是文件系统。

99 　　·块号：当逻辑设备为对换设备时，这是盘块号；而当逻辑设备为文件系统时，这是指文件的逻辑块号。
　　·指针1：指向空闲页链表中的下一个页框数据表的指针。 　　·指针2：指向散列队列中下一个页框数据表的指针。 　　系统初启时，核心将所有的页框数据表项链接为一个空闲页链表，形成空闲页缓冲池。 为给一个区分配一个物理页，核心从空闲页链表之首摘下一个空闲页表项，修改其对换设备号和块号后，将它放到相应的散列队列中。图10-10示出了页框数据表项的若干散列队列。

100 图10-10　页框数据表项及其散列队列

101 　　2) 对换使用表 　　对换设备上的每一页都占有对换使用表的一个表项，表项中含有一个引用计数，其数值表示有多少页表项指向该页。图10-11示出了页表项、磁盘块描述项、页面数据表项和对换使用表项四者间的关系。例如，一个进程的虚地址为1493 K，由页表项可得知其物理页号为794，其拷贝在对换设备1的2743号盘块上。物理页794有一对应的页面数据表项，在该表项中同样指出该页在对换设备1上的2743号盘块中有一拷贝，其引用数为1。

102 图10-11　四种数据结构之间的关系

103 10.4.2　换页进程 　　1．增加有效页的年龄 　　一个页可计数的最大年龄，取决于它的硬件设施。对于只设置两位作为年龄域的页，其有效页的年龄只能取值为0、1、2和3。当该页的年龄为0、1、2时，该页处于不可换出状态；而当其年龄达到3时，该页便为换出状态。每当内存中的空闲页面数低于某规定的低限时，核心便唤醒换页进程，由换页进程去检查内存中的每一个活动的、非上锁的区，对所有有效页的年龄字段加1。对于那些其年龄已增至3的页，便不再加1，而是将它们换出。如果这种页已被进程访问过，便将其年龄域中的年龄降为0。

104 　　2．对换出页的几种处理方式 　　当换出进程从内存的有效页中找到可换出的页后，可采取以下三种方式之一进行处理： 　　(1) 若在对换设备上已有被换出页的拷贝，且该页的内容未被修改，此时，核心只需将该页页表项中的有效位清零，并将页框数据表项中的引用计数减1，最后将该页框数据表项放入空闲页链表中。

105 　　(2) 若在对换设备上没有被换出页的拷贝，则换出进程应将该页写到对换设备上。但为了提高对换效率，对换进程并不是随有随换，而是先将所有要换出的页链入到一个要换出的页面链上。当换出页面链上的页面数达到某一规定值时，比如64个页，核心才真正将这些页面写到对换区中。 　　(3) 虽然在对换设备上已有换出页的副本，但该页的内容已被修改过，此时核心应将该页在对换设备上原来占有的空间释放，再重新将该页拷贝到对换设备上，使在对换设备上的拷贝内容总是最新的。

106 　　3．将换出页面写到对换设备上 　　当在换出页面链表中的页面数已达到规定值时，核心应将它们换出。为此，应首先为它们分配一个连续的对换空间，以便一起将它们换出；但如果在对换设备上没有足够大的连续空间，而其空闲存储空间的总和又大于64 KB时，核心可采取每次换出一页的方式将它们换出。每当核心向对换设备上写一个页时，须首先清除该页页表项的有效位，并将页框数据表项中的引用计数减1。若引用计数为0，表明已无其它进程再引用该页，核心便将其页框数据表项链入空闲页链表的尾部。若虽引用计数不为0，表明仍有进程共享该页，但如果该页已长期未被访问过，则也须将该页换出。最后，核心将分配给该页的对换空间的地址填入相应的磁盘描述表项中，并将对换使用表中的计数加1。

107 10.4.3　请求调页 　　当一个运行进程试图访问一个其有效位为0的页面时，将产生一个有效性错误。这时由核心调用有效性出错处理程序进行处理，可能有下述两种情况：一种情况是，由于在将可执行文件调入内存时，该文件的所有页所在的磁盘块号已记入磁盘块描述表项中，因此，如果在磁盘块描述表项中又找不到所需(缺)的页，则表明此次内存访问非法，核心将向违例进程发送一个“段违例”软中断信号。

108 　　另一种情况是，若在磁盘块描述表项中找到所需的页，表示内存访问合法；但若该页尚未调入内存，则核心为之分配一个页面的内存，将所缺的页调入。至于如何将所缺之页调入内存，这将与所缺页面应从何处调入有关，这又可分成以下三种情况: 　　(1) 缺页在可执行文件上。如果欲访问虚页对应的磁盘块描述表项中的类型项是File，表示该缺页尚未运行过，其拷贝在可执行文件中，于是核心应从可执行文件中将该页调入内存。其调入的具体过程是：根据该文件所对应的系统区表项中的索引结点指针，找到该文件的索引结点，即可把从磁盘块描述表项中得到的该页的逻辑块号作为偏移量，查找索引结点中的磁盘块号表，便可找到该页的磁盘块号，再将该页调入内存。

109 　　(2) 缺页在对换设备上。如果要访问的虚页对应的磁盘块描述表项中的类型是Disk，表示该缺页的拷贝是在对换设备上，因此，核心应从对换设备上将该页调入内存。其调入过程是：核心先为该缺页分配一个内存页，修改该页页表，使之指向内存页，并将页框数据表项放入相应的散列队列中，然后把该页从对换设备上调入内存。当I/O完成时，核心把请求调入该页的进程唤醒。

110 　　(3) 缺页在内存页面缓冲区中。 在进程运行过程中， 当一个页被调出后又被要求访问时，须重新将之调入。但并非每次都要从对换设备上调入，因为被换出的页可能又被其它进程(指共享页)调入另一个物理页上，这时就可在页面缓冲池中找到该页。此时，只需适当地修改页面表项等数据结构中的信息。

111 10.5　设 备 管 理 10.5.1　字符设备缓冲区管理 　　为了缓和CPU和I/O设备速度不匹配的矛盾并提高CPU和I/O设备操作的并行程度， 在现代OS中，都设置了缓冲管理功能。在UNIX系统中，分别为字符设备和块设备设置了缓冲池。字符缓冲区的大小是以字节为单位计量的，而块缓冲则是以盘块大小为单位的。系统同时为每一种缓冲池提供了一组相应的操作，以便从缓冲池中获取或释放一个缓冲区。

112 　　1．空闲字符缓冲区队列 　　在系统中设置了一组公用的字符缓冲区，并形成了一个公用字符缓冲池，提供给各种字符设备使用。每个缓冲区的大小为70个字节，可用cblock结构来描述。在该结构中包括四项：第一个字符的位置、最后一个字符的位置、指向下一个缓冲区的指针和用于存放64个字符的缓冲区。 所有的空闲字符缓冲区都通过各自的链接指针C-next链接成一个空闲字符缓冲区队列，由队列头标中的队首指针cfreelist指向其第一个缓冲区。图10-12示出了空闲字符缓冲区队列。

113 图10-12　空闲字符缓冲区队列

114 　　2．空闲字符缓冲区的分配与回收 　　在字符设备进行I/O时， 内核可利用getcf过程从空闲字符缓冲区队列中取得一个空闲缓冲区，若队列空，表明已无空闲缓冲区可提供，便返回；否则，从队首取得一个空闲缓冲区，并把指向该缓冲区的指针bp返回给调用者。由于空闲缓冲区队列属于临界资源，故还须采取互斥访问措施，即在过程开始处，将处理机的优先级提升为6，在取得空缓冲区之后，再恢复处理机的优先级。

115 　　当缓冲区中数据已被提取完而不再被需要时，可调用putcf过程释放缓冲区。该过程的输入参数是指向已不再需要的缓冲区的指针bp的，以便把该缓冲区送回到由空闲缓冲区队列的队首指针cfreelist指向的头部。若此时已有因申请空缓冲区而阻塞的进程，则将它唤醒。 同样，对空闲缓冲区队列的访问应该互斥地进行。

116 　　3．设备的字符缓冲区队列 　　所有的字符设备在进行I/O操作时，都采用了字符缓冲区。当字符设备工作时，通常都拥有一个至几个不同的字符缓冲区队列，所有的队列都由一个称为clist结构的信息块加以控制。在该结构中包括：该队列的可用字符计数、指向该队列的队首指针和队尾指针。内核提供了getc和putc等多个过程，以对该队列进行各种操作。 　　(1) getc过程。该过程用于从一个clist结构的队首指针所指示的字符缓冲队列中取出为首的字符，然后修改该队列的可用字符计数和队首指针。当取完一个缓冲区中的所有字符时，将释放该缓冲区。该过程的返回值是取出的字符。

117 　　(2) putc过程。该过程用于将一个字符C放入设备的指定字符缓冲区队列的末尾。若此时该队列空，或队列的最后一个缓冲区已满，且空闲字符缓冲区队列也空，该过程无法将字符放入队列中，则返回“ -1 ”。
　　(3) getcb过程。该过程用于从指定的设备字符缓冲区队列中取出第一个缓冲区，并将该队列的可用字符计数减去第一个缓冲区中的字符数，然后返回指向该缓冲区的指针bp。 若该缓冲区已是该队列中惟一的缓冲区，则置队尾指针为空。 　　(4) putcb过程。该过程用于将由bp所指向的缓冲区放入指定的设备字符缓冲区队列的末尾，然后将该队列的可用字符计数加上bp缓冲区中的字符数后返回。

118 10.5.2　块设备缓冲区管理 　　1．盘块缓冲区及其首部 　　在UNIX系统中，每一个盘块缓冲区均由两部分组成：一部分用于存放数据本身，即数据缓冲区；另一部分是缓冲控制块，也称缓冲首部，用于存放对应缓冲区的管理信息。以上两者一一对应，但缓冲首部与缓冲区在物理上并不相连，只是在缓冲首部中用一个指向对应缓冲区的指针把两者联系起来，如图10-13所示。

119 图10-13　缓冲首部

120 　　2．盘块缓冲池结构 　　(1) 空闲链表。为了对缓冲区进行管理，在核心中设置了一个双向链接的空闲链表。当需要一个空闲缓冲区时，可利用getblk过程从空闲链的首部摘下一个缓冲区；在释放缓冲区时，利用brelse过程，将缓冲区挂在空闲链的末尾。

121 　　(2) 散列队列。为了加速对缓冲区的查找，系统把所有的缓冲区逐个设备地、按其块号所计算的散列值的不同，组织成多个队列，每个散列队列仍是一个双向链，其中缓冲区的数目不断地变化， 各块的散列值用散列函数计算。图10-14示出了某一设备的若干散列队列。在“block 0 mod 4”散列队列上，有磁盘块号为28、4和64等的缓冲区；由于每一个缓冲区都在一个散列队列中，而空闲缓冲区又应链入空闲链中，因此，一个空闲缓冲区可同时链入两个队列，并使对某一空闲缓冲区的查找可用两种方法之一来进行，即如果要求获得任一空闲缓冲区，便到空闲链上去摘取第一个缓冲区，这是最方便的；但如果是要求寻找某一特定的空闲缓冲区，则搜索散列队列更方便。

122 图10-14　空闲队列(链)及散列队列

123 　　3．盘块缓冲区的分配 　　由于在系统中有两种块缓冲队列，相应地，也就有两个获得块缓冲区的过程：getblk( )过程和getblk(dev，blkno)过程。 　　(1) getblk( )过程。该过程用于从空闲缓冲区队列中获得任一空闲缓冲区。该过程首先检查空闲块缓冲队列是否为空，若空，便调用sleep过程睡眠等待，直至在空闲块缓冲队列中出现空闲缓冲区为止；否则，从空闲块缓冲队列中摘下第一个缓冲区。若在其缓冲首部中还有延迟写标志，则还须调用bdwrite过程，将此缓冲区中的数据写回到磁盘中，再从空闲队列中取得一个空缓冲区；否则，便将b-flag中的b-busy标志置为1，并返回指向该缓冲区的指针bp。

124 　　(2) getblk(dev，blkno)过程。该过程用于为指定设备dev和盘块号为blkno的盘块申请一个缓冲区。核心首先检查要读入的盘块内容是否已在某个缓冲区中，若发现已在某缓冲区中，便不再从磁盘上读入；否则，核心须从磁盘上将数据读入，这时才需为其分配一个空缓冲区。类似地，当要把数据写入一特定盘块时，核心先检查该盘块的内容是否已在某缓冲区，仅当该块的内容尚不在缓冲区中时，才需调用getblk( )过程，分配一个空缓冲区。

125 　　4．盘块缓冲区的回收 　　当核心用完某缓冲区时，可调用brelse过程将之收回。此前，可能有些进程因等待使用该缓冲区而睡眠，此时，释放者进程应将睡眠队列的队首进程唤醒。此外，还有可能有进程因空闲链表空而处于等待状态，同样也应将之唤醒。如果在所释放的缓冲区中的数据是有效的，为使以后在某进程需要它时也能直接从缓冲区中读出而不必启动磁盘的I/O操作，可将该缓冲区链入空闲链表的末尾；否则(缓冲区中数据无效)，应将它链入空闲队列的头部。 空闲链表属于临界资源，为了保证对其操作的互斥性，UNIX系统通过提高处理机的运行级对中断加以屏蔽的方法来实现。

126 10.5.3　内核与驱动程序接口 　　1．设备开关表的作用 　　通常，任何一个驱动程序都包括用于执行不同操作的多个函数，如打开、关闭、读或写等。为了能方便地找到各函数的入口地址，使系统控制能方便地转向各函数，系统为每类设备提供了一个设备开关，其中含有各函数的入口地址。由多种类型的设备开关构成一张设备开关表，表中的每一行是一类设备驱动程序的各函数的入口地址；表的每一列是执行相同操作的不同(设备类型)函数。图10-15示出了字符和块设备开关表与系统调用和驱动函数的关系。由图可以看出，设备开关表是核心与驱动程序间的接口，系统调用通过设备开关表转向相应驱动程序的函数。由于块设备与字符设备的驱动程序有所不同，故系统为它们分别设置了设备开关表。

127 图10-15　设备开关表及系统调用和驱动程序间的接口

128 　　2．块设备开关表 　　图10-16 示出了块设备开关表，其中，第一行为0号设备的开关，它包括三个表项，其中gdopen是0号设备专用的打开函数的入口地址，该函数用于打开指定的磁盘驱动器； gdclose是0号设备专用的关闭函数的入口地址，该函数用于关闭指定的磁盘驱动器； gdstrategy是策略函数的入口地址，该函数用于在数据缓冲区与块设备之间传输数据。块设备开关表的第二行是1号块设备的开关。

129 图10-16　块设备开关表

130 　　3．字符设备开关表 　　图10-17示出了字符设备开关表。表中共有三行，表明共有三类字符设备驱动程序。每个驱动程序含有下述五个函数的入口地址： 　　(1) 打开特定字符设备的函数open。 　　(2) 关闭特定字符设备的函数close。 　　(3) 读特定字符设备的函数read。 　　(4) 写特定字符设备的函数write。 　　(5) 预置该设备参数的函数及读取该设备预置参数的函数等的入口地址。

131 图10-17　字符设备开关表

132 10.5.4　磁盘驱动程序 　　1．打开磁盘驱动器的过程gdopen 　　在UNIX系统中，设备被看做是一种特殊类型的文件，因而在使用该文件之前，也须先将它打开。gdopen便是用于打开磁盘驱动器的过程，该过程的输入参数是设备号，无输出参数。进入该过程后，首先检查系统中是否有由输入参数dev所指定类型的磁盘驱动器。若有，再检查它是否已被打开，如果尚未打开，便将此驱动器打开，亦即，将该磁盘控制器表中的标志b-flag设置为B-ONCE；再调用gdtimer过程启动对应的控制器和设备短期时钟闹钟，用于控制磁盘驱动器的执行时间。若系统中无指定类型的磁盘驱动器，则置相应的出错信息后返回。

133 　　2．启动磁盘控制器的过程gdstart 　　在进行磁盘的读、写之前，应首先装配磁盘控制器中的各个寄存器，然后再启动磁盘控制器。这些功能是由gdstart过程完成的。该过程的输入参数是控制器号ctl，无输出参数。 进入该过程后，先从磁盘设备控制表中找到I/O队列的队首指针，若它为0，表示I/O队列空，无I/O缓冲区可取，于是返回；否则，将控制器表中的忙闲标志b-active置“1”。设置磁盘控制器中的各寄存器，如磁盘地址寄存器、内存总线地址寄存器、控制状态寄存器、字计数器等，最后启动磁盘控制器读(或写)后返回。

134 　　而gdstartegy过程的主要功能则是把指定的缓冲首部排在磁盘控制器I/O队列的末尾，并启动磁盘控制器。输入参数是指向缓冲首部的指针bp，无输出参数。进入该过程后，先检查磁盘控制器队列是否空，若空，使把缓冲首部的始址赋予I/O队列的队首指针；否则，便将该缓冲首部放在I/O队列的末尾。再判别磁盘设备是否忙，若不忙，便调用gdstart过程启动磁盘控制器，以传输I/O队列中第一个缓冲区中的数据；否则返回。

135 　　3．磁盘中断处理过程gdintr 　　当磁盘I/O传送完成并发出中断请求信号时，CPU响应后将通过中断总控程序进入磁盘中断处理过程gdintr。该过程的输入参数是控制器号ctl。进入该过程后，先检查磁盘是否已经启动，若尚未启动，程序便不予理睬即返回；若已启动，则还须先通过对状态寄存器的检查，来了解本次传送是否出错。若已出错，便在控制终端上显示出错信息。由于磁盘的出错率较高，因而并不采取一旦出错便停止传送的策略，而是做好重新执行的准备，然后再传送。仅当重试多次都失败且超过规定的执行时间时，才设置出错标志。如未出错，则继续传送下一个缓冲区中的数据。

136 10.5.5　磁盘读/写程序 　　1．磁盘的读/写方式 　　1) 读方式 　　在UNIX系统中有两种读方式：一般读方式: 只把盘块中的信息读入缓冲区，由bread过程完成。 　　提前读方式: 当一个进程要顺序地读一个文件所在的各个盘块时，会预见到所要读的下一个盘块，因而在读出指定盘块(作为当前块)的同时，可要求提前将下一个盘块(提前块)中的信息读入缓冲区。这样，当以后需要该盘块的数据时，由于它已在内存，故而可缩短读这块数据的时间，从而改善了系统性能。提前读功能由breada过程完成。

137 　　2) 写方式 　　UNIX系统有三种写方式: 　　一般写方式：这种方式是真正地把缓冲区中的数据写到磁盘上，且进程须等待写操作完成，由bwrite过程完成。 　　异步写方式: 进程无需等待写操作完成便可返回，异步写过程是bawrite。

138 　　延迟写方式: 该方式并不真正启动磁盘，而只是在缓冲首部设置延迟写标志，然后便释放该缓冲区，并将之链入空闲链表的末尾。以后，当有进程申请到该缓冲区时，才将其内容写入磁盘。引入延迟写的目的是为了减少不必要的磁盘I/O，因为只要没有进程申请到此缓冲区，其中的数据便不会被写入磁盘，倘若再有进程需要访问其中的数据时，便可直接从空闲链表中摘下该缓冲区，而不必从磁盘读入。延迟写方式由过程bdwrite完成。

139 　　2．读过程bread和breada 　　1) 一般读过程bread 　　该过程的输入参数是文件系统号(即逻辑设备号)及块号。进入该过程后，先调用getblk过程申请一缓冲区，若缓冲首部标明该缓冲区中数据是有效的，便无需再从磁盘读入，直接返回；若所需数据尚未读入，则应先填写缓冲首部，如设置读标志，以表明本次是读操作。其次是设置块的初始字符计数值(如1024)，再通过块设备开关表转入相应的gdstartegy过程，启动磁盘传送。由于一般读方式下进程要等待读操作完成，故须调用sleep过程使自己睡眠，直至读操作完成时再由中断处理程序将该进程唤醒，最后将缓冲区首部的指针bp作为输出参数，返回给调用进程。

140 　　2) 提前读过程breada 　　该过程的输入参数是当前读的文件系统号(设备号)、盘块号，以及提前读的文件系统号和盘块号。进入该过程后，先判别当前块是否在缓冲池中。若当前块不在缓冲池，须调用getblk过程为其分配一缓冲区。若缓冲区中的数据无效，则应填写缓冲区首部，通过设备开关表转入策略过程，启动磁盘读入。若当前块已在缓冲池中，或所分配的缓冲区中数据有效，都将转去读提前块。

141 　　若提前块的数据缓冲区不在缓冲池中，同样要调用getblk过程为读提前块而分配一缓冲区。若所得数据缓冲区中的数据有效，则调用brelse过程将该缓冲区释放，以便其他进程能对该缓冲区进行访问；否则，填写缓冲区首部后启动磁盘。最后，若当前块缓冲区在缓冲池中，则调用bread过程去读当前块；否则，调用sleep过程使自己睡眠，以等待读操作完成。在读操作完成而被唤醒后，将该缓冲区首部的指针返回。

142 　　3．写过程bwrite、bawrite和bdwrite
　　该过程的输入参数是缓冲区指针bp。进入该过程后，根据bp指针找到缓冲区首部，设置缓冲区首部的初值，通过设备开关表转入策略过程，启动磁盘。如是一般写，应等待I/O完成，为此，须调用sleep过程使自己睡眠。I/O完成后才被唤醒，再调用brelse过程释放该缓冲区。如是异步写，且有延迟写标志，则在给缓冲区打上标志后，将之放入空闲链表的首部。

143 　　2) 异步写过程bawrite 　　它与一般写过程很相似，但不需等待I/O完成即可返回。进入bawrite过程后，设置异步写标志，再调用bwrite过程实现之。 　　3) 延迟写过程bdwrite 　　延迟写过程也很简单。这里只需设置延迟写标志及数据有效标志，再调用brelse过程将该缓冲区释放，并链入空闲链表的尾部。以后，当某进程调用getblk获得该缓冲区时，再用异步写方式将缓冲区内容写入磁盘。

144 10.6 文 件 管 理 10.6.1 UNIX文件系统概述 1．UNIX文件系统的特点
10.6　文 件 管 理 10.6.1　UNIX文件系统概述 　　1．UNIX文件系统的特点 　　(1) 文件系统的组织是分级树形结构形式。UNIX文件系统的结构基本上是一棵倒向的树，这棵树的根是根目录，树上的每个结点都是一个目录，而树的叶则是信息文件。每个用户都可建立自己的文件系统，并把它安装到UNIX文件系统上，从而形成一棵更大的树。 当然，也可以把安装上去的文件系统完整地拆卸下来，因而，整个文件系统显得十分灵活、方便。

145 　　(2) 文件的物理结构为混合索引式文件结构。所谓混合索引文件结构，是指文件的物理结构可能包括多种索引文件结构形式，如单级索引文件结构、两级索引文件结构和多级索引文件结构形式。这种物理结构既可提高对文件的查询速度，又能节省存放文件地址所需的空间。 　　(3) 采用了成组链接法管理空闲盘块。这种方法实际上是空闲表法和空闲链法相结合的产物，它兼备了这两种方法的优点而克服了这两种方法都有的表(链)太长的缺点，这样，既可提高查找空闲盘块的速度，又可节省存放盘块号的存储空间。

146 　　(4) 引入了索引结点的概念。在UNIX系统中，把文件名和文件的说明部分分开，分别作为目录文件和索引结点表中的一个表项，这不仅可加速对文件的检索过程，减轻通道的I/O压力，而且还可给文件的联接和共享带来极大的方便。

147 　　2．文件系统的结构 　　由于在UNIX系统中，文件名和文件属性(说明)分开存放，由文件属性构成文件的索引结点，这使UNIX的目录项与一般文件系统的目录项不同，故UNIX文件系统的结构也与一般文件有所差异。图10-18示出了引入索引结点后所形成的UNIX文件系统结构。其中，根目录中的bin是二进制系统文件的根目录；usr为用户文件的根目录；dev为特殊文件的根目录。

148 图10-18　UNIX文件系统的结构

149 　　3．文件系统的资源管理 　　为了在系统中保存一份文件，必须花费一定的资源，当文件处于“未打开”状态时，文件需占用三种资源： 　　(1) 一个目录项，用以记录文件的名称和对应索引结点的编号。 　　(2) 一个磁盘索引结点项，用以记录文件的属性和说明信息，这些都驻留在磁盘上。 　　(3) 若干个盘块，用以保存文件本身。

150 当文件被引用或“打开”时，须再增加三种资源：
(1) 一个内存索引结点项，该项驻留在内存中。 (2) 文件表中的一个登记项。 (3) 用户文件描述符表中的一个登记项。

151 　　由于对文件的读写管理必须涉及到上述各种资源，因而对文件的读写管理又在很大程度上依赖于对这些资源的管理，故可从资源管理的观点来介绍文件系统。这样，对文件的管理就必然包括：① 对索引结点的管理；② 对空闲盘块的管理；③ 对目录文件的管理；④ 对文件表和描述符表的管理；⑤ 对文件的使用。下面我们先介绍文件的物理结构。

152 10.6.2　文件的物理结构 　　1．寻址方式 　　1) 直接寻址 　　在UNIX系统中的作业，是以中、小型的作业为主的。根据对大量文件调查的结果得知，文件长度字节数在10 KB以下的占大多数。为了提高对中、小型作业的检索速度，宜采用直接寻址方式。为此，在索引结点中建立了10个地址项i-addr(0)～i-addr(9)，在每个地址项中直接置入该文件占用盘块的编号，如图10-19所示。这相当于第六章所述的单级索引文件的寻址方式。如果盘块的大小为 1 KB，则当文件长度不大于10 KB时，可直接从索引结点中找出该文件的所有盘块号。

153 图10-19　直接寻址和间接寻址

154 　　2) 一次间接寻址方式 　　采用间接寻址方式是基于这样的事实：有不少文件，其长度可能达到几十千字节、几十兆字节甚至更长。如果全部采用直接寻址方式，就必须在索引结点中设置几百个或更多的地址项，这显然是不现实的。为了节省存放文件盘块号所占用的存储空间，在UNIX系统中又提供了所谓的“一次间接”寻址方式，即在i-addr(10)地址项中，存放的不再是存放文件的一个物理盘块号，而是将存放了直接地址的1～256个物理盘块号的盘块的编号放于其中，这相当于第6章所述的两级索引文件中的寻址方式。假定一个盘块仍为1 KB， 一个盘块号占用32位，这样，i-addr(10)的寻址范围可达256 KB。

155 　　3) 多次间接寻址 　　为了进一步扩大寻址范围，又采用了二次间接和三次间接寻址方式，使用的地址项分别为索引结点中的i-addr(11)和i-addr(12)。二次间址相当于三级索引文件中的寻址方式，若盘块大小仍为1 KB，则可将寻址范围扩大到64 MB+256 KB；三次间址则可将寻址范围扩大到16 GB。

156 　　2．地址转换 　　1) 将字节偏移量转换为文件逻辑块号 　　在UNIX文件系统中，文件被视为流式文件，每个文件有一个读、写指针，用来指示下一次要读或写的字符的偏移量。该偏移量是从文件的头一个字符的位置开始计算的。在每次读、写时，都要先把字节偏移量转换为文件的逻辑块号和块内位移量。其转换方法是：将字节偏移量除以盘块大小的字节数，其商即为文件的逻辑块号，余数为块内位(偏)移量。

157 　　2) 把文件逻辑块号转换为物理盘块号 　　(1) 直接寻址。当文件的逻辑块号小于或等于10时，索引结点中所存放的是直接地址。将逻辑块号转换为物理块号的方法是：首先，将文件的逻辑块号转换为索引结点中地址项的下标；其次，从该下标所指的地址项中，即可获得物理盘块号。 　　例如，某进程要访问其字节偏移量为9000处的数据，为此，核心须先将9000转换成文件逻辑块号8，块内偏移量为808。由于逻辑块号小于10，故可直接从相应的地址项i-addr(8)中找到物理盘块号为367的块(见图10-20)，在该块中的第808字节处即为文件的第9000字节处。

158 　　(2) 一次间址。当文件系统中的逻辑块号大于10而小于或等于256+10时，为一次间址寻址方式。其地址转换过程分为两步：
　　第一步，由于一次间址的地址项下标为10，所以可以从i-addr(10)中得到一次间址盘块号，由bread过程读间址块。 　　第二步，计算一次间址中文件的逻辑块号，即将文件的逻辑块号减10，根据一次间址中的逻辑块号得到间址块号中地址项的下标，再从相应下标的地址项中得到物理盘块号。

159 　　例如，进程要访问偏移量为14 000字节处的数据。核心先将14 000转换为逻辑块号13及块内偏移量688。由于10<13<266，故应属于一次间址。这样，再从i-addr(10)中得到一次间址的盘块号为428，调用bread过程读该盘块，计算一次间址块中的文件逻辑块号为3，从中可得到盘块号为952。于是，该块中的第688字节处便是要访问的文件的第14 000字节处，见图10-20所示。

160 　　(3) 多次间址。当文件的逻辑块号大于266，又小于或等于64 266时，应采用二次间址；逻辑块号大于64 266时应采用三次间址。多次间址的转换方法和一次间址时相似，但要多次循环，这里不再赘述。 　

161 图10-20　文件的地址映射示例

162 10.6.3　索引结点的管理 　　1．超级块(Superblock) 　　在UNIX系统中，通常把每个磁盘或磁带看做是一个文件卷，在每个文件卷上可存放一个文件系统。文件卷可占用许多物理盘块，其中0#盘块一般用于系统引导；1#块为超级块。磁盘块和索引结点的分配与回收，将涉及到超级块。超级块是专门用于记录文件系统中盘块和磁盘索引结点使用情况的一个盘块，其中含有以下各字段： 　　(1) 文件系统的盘块数目。 　　(2) 空闲盘块号栈，即用于记录当前可用的空闲盘块编号的栈。

163 　　(3) 当前空闲盘块号数目，即在空闲盘块号栈中保存的空闲盘块号的数目。它也可被视为空闲盘块编号栈的指针。
　　(4) 空闲磁盘i结点编号栈，即记录了当前可用的所有空闲i结点编号的栈。 　　(5) 空闲磁盘i结点数目，指在磁盘i结点栈中保存的空闲i结点编号的数目，也可视为当前空闲i结点栈顶的指针。 　　(6) 空闲盘块编号栈的锁字段，是对空闲盘块进行分配与回收时的互斥标志。

164 　　(7) 空闲磁盘i结点栈的锁字段，是对空闲磁盘i结点进行分配与回收时的互斥标志。
　　(8) 超级块修改标志，用于标志超级块是否被修改，若已被修改，则在定期转储时，应将超级块内容从内存复制到文件系统中。 　　(9) 修改时间，指记录超级块最近一次被修改的时间。

165 　　2．磁盘索引结点的分配与回收 　　1) 分配过程ialloc 　　该过程的主要功能是每当核心创建一个新文件时，都要为之分配一个空闲磁盘i结点。若分配成功，便再分配一内存i结点。其分配过程如下： 　　(1) 检查超级块上锁否。超级块是临界资源，诸进程必须互斥地对它进行访问。因此在进入ialloc过程后，要首先检查它是否已被上锁，若已被锁住，进程便睡眠等待。 　　(2) 检索i结点栈空否。若发现i结点栈中已无空闲i结点编号，则应从盘中再调入一批结点号进栈。若盘中也已无空闲i结点，便做出错处理后返回。

166 　　(3) 从空闲i结点编号栈中分配一个i结点，并且加以初始化，填写有关文件的属性。
　　(4) 分配内存i结点。在UNIX系统中，每当创建一个新文件后，便随之把它打开。因此在分配了磁盘i结点后，便调用iget过程再为之分配一个内存i结点，并对它进行初始化， 然后把磁盘i结点的内容复制到内存i结点中。 　　(5) 将磁盘i结点总数减1，并在置超级块的修改标志后返回。

167 　　2) 回收过程ifree 　　当一个文件已不再被任何进程需要时，应将该文件从磁盘上删除，并回收其所占用的盘块及相应的磁盘i结点。过程ifree便是用于回收磁盘i结点的。其所包括的操作有： 　　(1) 检查超级块上锁否。若已上锁便直接返回，即不能把本次回收的i结点号记入空闲i结点编号栈中。 　　(2) 检查i结点编号栈满否。若栈中的i结点编号的个数已等于100，则表示栈已满，无法再装入新的i结点号，也须立即返回。 　　(3) 若i结点编号栈未满，便使回收的i结点的编号进栈，并使当前空闲i结点数加1。 　　(4) 置超级块修改标志后返回。

168 　　3．内存索引结点的分配与回收 　　1) 分配过程iget 　　该过程的主要功能是在打开文件时，为之分配内存i结点。由于允许文件被共享，因此，如果一文件早已被其他用户打开并有了内存i结点，此时便只需将该i结点中的引用计数加1；如果文件尚未被其他用户打开，则由iget过程为该文件分配一个内存i结点，并调用bread过程将其磁盘i结点的内容拷贝到内存i结点中，同时进行初始化。

169 　　2) 回收过程iput 　　每当进程要关闭某文件时，须调用iput过程先对该文件的内存i结点中的引用计数做减1操作。若结果为0，便回收该内存i结点，再判断其磁盘的i结点的联接计数，若其结果也为0，便删除此文件，并回收分配给该文件的盘块和磁盘i结点。

170 10.6.4　空闲磁盘空间的管理 　　1．文件卷的组织 　　在UNIX系统中的文件存储介质，可采用磁盘或磁带。通常可把每个磁盘或磁带看做是一个文件卷，每个文件卷上可存放一个具有独立目录结构的文件系统。一个文件卷包括许多物理块，并按照块号排列成如图10-21所示的结构。

171 图10-21　文件卷的组织

172 　　在文件卷中，0#块一般用于系统引导或空闲；1#块为超级块(Superblock)，用于存放文件卷的资源管理信息，包括整个文件卷的盘块数、磁盘索引结点的盘块数、空闲盘块号栈和空闲盘块号栈指针、空闲盘块号栈锁、空闲索引结点栈和空闲索引结点栈指针，以及空闲索引结点栈锁等。从2#块起存放磁盘索引结点，直到K#块。每个索引结点为64个字节，当盘块大小为1 KB时，每个盘块中可存放16个索引结点；从(K+1) #块起及其以后各块都存放文件数据，直至文件卷的最后一块即(N-1)#块。

173 　　2．空闲盘块的组织  　　UNIX系统采用了第六章所介绍的成组链接法，对空闲盘块加以组织。该方法是将若干个(如100个)空闲盘块划归为一个组，将每一组中的所有盘块号存放在其前一组的第一个空闲盘块中，而仅把第一组中的所有空闲盘块号放入超级块的空闲盘块号栈中。例如，在图10-22所示的空闲盘块的组织中，将第四组的盘块号409、406、403等存入第三组的第一个即310号盘块中；又将第三组的盘块号310、307、304等放入第二组的第211号盘块中；而第一组的盘块号109、106、103等则放入超级块的空闲盘块号栈中。

174 图10-22　空闲盘块的组织

175 　　3．空闲盘块的分配与回收 　　1) 空闲盘块的分配 　　空闲盘块的分配是由alloc过程完成的，该过程的主要功能是从空闲盘块号栈中获得一空闲盘块号。当核心要从文件系统中分配一个盘块时，首先检查超级块中的盘块号栈是否已经上锁。若已锁上，便调用sleep过程睡眠；否则，将超级块的空闲盘块号栈顶的盘块号(如95号)分配出去。如果所分配的空闲盘块号是在栈底(如109号)，由于在该号盘块中又包含了第二组盘块的所有盘块号(如211、208等)，于是核心在给超级块上锁后，应先调用bread过程将该栈底盘块号对应盘块中的内容读出，作为新栈的内容进栈；然后，再将原有栈底所对应的盘块作为空闲盘块分配出去(即109号盘块)；最后，将超级块解锁，唤醒等待超级块解锁的进程。

176 　　2) 空闲盘块的回收 　　空闲盘块的回收是由free过程完成的。在回收空闲盘块时，首先检查超级块中的盘块号栈是否已经上锁，若已上锁，便调用sleep睡眠；否则，再检查空闲盘块号栈是否已满。如果空闲盘块号栈未满，可直接将回收盘块的编号记入空闲盘块号栈中；若栈已满，须调用betblk过程申请一个缓冲区，将栈中的所有空闲盘块号复制到新回收的盘块中，再将新回收盘块的编号作为新栈的栈底块号进栈。

177 10.6.5　文件表的管理 　　1．用户文件描述符表的管理 　　1) 用户文件描述符表 　　为了方便用户和简化系统的处理过程，在UNIX系统Ⅴ中，在每个进程的U区中都设置了一张用户文件描述符表。核心先对其打开请求做仔细检查后，便在该进程的用户文件描述符表中分配一个空项，取其在该表中的位移量作为文件描述符fd(file discriptor)返回给用户。以后，当用户再访问该文件时，只需提供该文件描述符fd，系统根据fd便可找到相应文件的内存索引结点。

178 　　2) ufalloc过程 　　用户文件描述符表项的分配是由ufalloc过程来完成的。该过程首先是从用户文件描述符表中查找一个空项，若找到，便将该表项的序号fd作为文件描述符写入进程的U区，然后返回；否则，置出错标志后返回“NULL”。

179 　　2．文件表的管理 　　1) 文件表 　　系统为了对文件进行读/写，设置了一个确定读/写位置偏移量的读/写指针。该读/写指针应放在何处，是否可放在用户文件描述符表中，我们对此做了简单的分析。用户在读写文件时，可采用三种方式： 　　第一种方式，多个用户读/写各自的文件，见图10-23中的上部； 　　第二种方式，多个用户共享一个文件，但彼此独立地对文件进行读/写，见图10-23的中部； 　　第三种方式，多个用户共享一个文件，且共享一个读/写指针，见图10-23的下部。

180 图10-23　对文件的三种读/写方式

181 　　这样，若将读/写指针设置在文件描述符表项中，对前面两种情况固然可行，但要实现对读/写指针的共享就很困难了。为解决此问题，在UNIX系统中引入了文件表，在其表项中存放各用户的读/写指针。这样，对上述三种读/写方式的读/写要求都能很好地满足。在文件表项中，除了读/写偏移量f-offset外，还设置了文件引用计数f-count，用于指示正在利用该文件表项的进程数目，以及用于指向对应内存索引结点的指针f-inode和读/写标志f-flag。

182 　　2) falloc过程 　　该过程的功能是分配文件表项。进入falloc过程后，调用ufalloc过程分配用户文件描述符表项。若未分配成功，便返回NULL；否则，继续从文件表中查找一个空闲文件表项。若找到空闲文件表项，便将该项的始址置入用户文件描述符表项中。在设置完文件描述符表项的初始值后便返回(fp)。若未找到空闲文件表表项，则返回NULL。

183 10.6.6　目录管理 　　1．构造目录项 　　每当某用户(进程)要创建一个新文件时，内核便应在其父目录文件中为之构造一个目录项；另外，当某进程需要共享另一用户的某文件时，内核也将为要共享该文件的用户建立一个目录项。因此，当一个共享文件与N个用户相联接时，该文件将有N个目录项。下面我们介绍在第一种情况下的目录构造过程。

184 　　在UNIX系统中，构造目录的任务是由过程makenode完成的。在创建一个新文件时，由系统调用creat过程来为文件构造一个目录项。makenode过程首先调用ialloc过程为新文件分配一个磁盘i结点及内存i结点。若分配失败便返回。当分配成功时，须先设内存i结点的初值(含拷贝)，然后又调写目录过程wdir，将用户提供的文件名与分配给该文件的磁盘i结点号一起，构成一个新目录项，再将它记入其父目录文件中。

185 　　2．删除目录项 　　对于一个只由某用户独享的文件，在该用户不再需要它时，应将它从文件系统中删除，以便及时腾出存储空间。 　　对于一个可供若干个用户(进程)共享的文件，为了表示有多个用户(进程)要共享此文件，内核将利用link系统调用为各用户分别建立一个与该文件的联接，并设置联接计数nlink，使之等于要共享该文件的进程数目。 如有6个进程要共享该文件，则应设置nlink为6。 对于共享文件，由于该文件在某时刻可能正在被若干个用户所访问，因而不允许任何一个用户(进程，包括文件主)将该文件删除，这也正是UNIX系统中不存在一条用于删除文件的系统调用的原因。

186 　　如果某时刻任何一个用户(进程)已不再需要某个共享文件，则只能利用去联接系统调用unlink，请求系统将本进程与该文件间的联接断开。此时， 系统须对该文件的联接计数nlink执行减1操作，并相应地删除该用户(进程)的一个指名的文件目录。仅当所有联接到该文件上的用户都不再需要该文件时，其nlink值必为0，系统才执行删除此共享文件的操作。相应地，将此文件的最后一个目录项从其文件目录中删除。

187 　　3．检索目录 　　在UNIX系统中，用户在第一次访问某文件时，须使用文件的路径名，系统按路径名去检索文件目录，得到该文件的磁盘索引结点，且返回给用户一个文件描述符。以后，用户便利用该文件描述符来访问该文件，这时系统不再去检索文件目录。 　　对文件目录的检索是由namei过程完成的。该过程可被许多不同的系统调用所调用， 如有creat、open、link、chdir、chmod等，但它们对namei的要求并不完全相同。可将这些系统调用分成三类，分别用flag=0、flag=1和flag=2来表示。

188 　　对于flag=0的类，是由chmod、chdir等调用namei；如果namei查找到指名文件，便返回其相应的内存索引结点指针。
　　对于flag=1的类，主要是由creat调用namei；如果namei未找到指名文件，便做正常返回。 　　对于flag=2的类，主要是由unlink调用；在正常情况下，应返回由路径名所指出的父目录文件的内存i结点指针。这样就使得namei过程变得非常复杂，成为UNIX系统中最复杂的过程。

189 　　检索目录的过程namei是根据用户给出的文件路径名，从高层到低层顺序地查找各级文件目录，寻找指定文件的索引结点号。在检索路径名时，对于以“/”开头的路径名，须从根目录开始检索；否则，应从当前目录开始检索，并把与它对应的i结点作为工作索引结点，然后用文件路径名中的第一分量名与根或当前目录文件中各目录项的文件名逐一进行比较。 由于一个目录文件可能占用多个盘块，因此，在检索完一个盘块中的所有目录项而又未找到匹配的文件分量名时，须调用bmap和bread过程，将下一个盘块中的所有目录项读出后，再逐一检索。若检索完该目录文件的所有盘块而仍未找到匹配的目录项时，才认为无此文件分量名。 　　

190 　　在未找到指定分量名的匹配目录项时，可分成以下几种情况处理:
　　第一种情况：对于最后一个路径分量名(要找的)，若flag≠1，做出错处理后返回；否则，属于正常情况。此时使namei过程继续执行，去检查其父目录文件是否允许写，父目录文件中是否有空目录项，若有，便分配一个空目录项，然后返回NULL。

191 　　第二种情况：若指定分量名不是最后一个路径分量名，也做出错处理后返回。
　　第三种情况：如果找到匹配项，便把该目录项中所指示的索引结点作为工作索引结点，并取出文件路径名的下一个分量名，继续重复上述过程，直至路径名中的所有分量名全部查找完毕，最后便可得到指名文件的索引结点。