进程与存储管理示例.ppt

6.1 UNIX进程和存储管理简介 6.2 UNIX进程结构 6.3 进程控制 6.4 UNIX进程调度与交换 6.5 进程通信 6.6 UNIX存储管理 本章小结 习题 第6章 进程与存储管理示例 本章以Linux 2.4 为主，介绍Linux的进程和存储管理方法。 6.1 Linux进程和存储管理简介 UNIX系统的核心部分从整体上说可以分为两大部分， 即“静”的文件系统和“动”的进程控制系统。 文件系统主要用来存放、管理那些暂时不被处理机执 行的程序和数据，它为程序和数据文件分配空间，控制文 件存取和为用户检索信息。 进程控制系统则负责为将要执行的程序和数据文件分 配内存空间，并负责进程调度、控制并发进程的执行速度 和分配必要的资源，以及负责进程通信和内存管理等。 UNIX的进程控制系统与文件系统之间通过系统调用来互相 作用。先介绍UNIX的进程控制系统部分。 第6章 进程与存储管理示例 Linux系统把一个程序看作是一个可执行文件，而把一 个进程看作是程序的执行或执行中的程序实例。但是，从 静态的观点看，CPU把进程解释为由一组机器指令、数据和 堆栈结构组成的集合，及其上下文。 系统核心调度进程占据CPU。由于调度并不一定是在每 个进程执行完毕时发生，因此，系统内同时有多个进程在 执行。而且，若干个进程可以同时调用一个子程序。 和其他所有操作系统一样，UNIX操作系统只有在其内 核装入内存后才能开始运行。 6.1 Linux进程与存储管理简介 为了使操作系统内核能在每次开机时顺利地装入内存 ，用户必须事先把 Linux 操作系统的执行代码以文件方式 存储在计算机硬盘设备中，并对计算机系统中的相应资源 ，例如高速缓存、交换区等进行初始化。 这一过程被称为操作系统的安装过程。 一个商用的操作系统都有自己的自动安装程序。用户 在购买了操作系统之后，只要按照操作系统程序的提示和 说明，一般都能进行系统安装。因此，本章的进程运行和 存储管理都是假定在一个已完全安装完毕的操作系统基础 上进行的。 6.1 Linux进程与存储管理简介 在一个已安装好UNIX系统的操作系统中，启动电源意 味着系统引导程序开始系统自举，引导在外存硬盘中的操 作系统进入内存。 这一过程是一个启动 Linux 系统、设置和初始化各种 数据结构与表格、建立控制 Linux 系统内核运行的控制进 程（在 Linux 系统中，把核心进程称为 0#进程 ），和建 立控制终端进程与 Shell 进程（用户交互进程）运行的1# 进程。最后，系统在建立了 0#进程 和 1#进程 等之后， 将出现相应的提示符，以等待用户输入命令来执行和处理 用户应用程序。 6.1 Linux进程与存储管理简介 Shell 程序将为用户提供解释执行用户命令的交互工具 。随着用户命令，例如“cp”等的输入，系统将为该命令建 立一个执行该命令的用户进程。 如果这个用户进程抢不到处理器，则Shell进程会自动 退出处理器，进入等待队列，以便用户进程执行。 在用户进程执行结束后，Shell进程又恢复执行，并显 示提示符和等待用户的下一条命令输入。 Linux系统的所有进程都是在上述执行过程中产生和消 亡。 6.1 Linux进程与存储管理简介 由图6.1可以看到，在 Linux 系统中还未创建出其他新 用户进程之前，只有 0#进程、1#进程以及终端管理进程与 Shell进程存在。 其中，终端管理进程与 Shell 进程是 1#进程 的子进程 ，这是因为在 Linux 系统中，除了 0#进程 和 1#进程 之外 ，其他进程都是由父进程创建的。 人们也称 1#进程 是所有用户进程的祖先。 6.1 Linux进程与存储管理简介 Linux操作系统的 0#进程 在核心态下运行，而1#进程以 及由1#进程衍生的其他进程都可在用户态和核心态两种执行 模式下执行。 两态之间的主要区别是：用户态下的进程能存取它们 自己的指令与数据，但不能存取核心指令和数据。然而， 核心态下的进程能存取核心和用户地址。另外，某些机器 的指令是特权指令，在用户态下执行会引起错误，只能在 核心态下执行。 6.1 Linux进程与存储管理简介 Linux进程的核心态和用户态之间的转换靠中断以及硬 件设置等方法完成，当用户进程由用户态转向核心态执行 时，需要依靠中断或后述的陷阱来实现。在核心态执行的 进程只有通过设置程序状态寄存器 PSW 才能回到用户态。 6.1 Linux进程与存储管理简介 Linux的进程控制系统在逻辑上由四个模块组成。即与文件系 统的接口部分，进程本身的控制部分，包括进程的创建、 进程调度和进程的撤消等，第三部分是进程间控制部分， 包括进程间的互斥、同步和通信等，第四部分是存储管理 部分。进程控制系统模块结构如图6.3 所示。 6.1 Linux进程与存储管理简介 图6.3 进程控制系统 进程控制系统与文件系统的接口有两个，一个是在系统内部 与文件系统直接发生联系的有关表格和数据结构。另一个 则是通过系统调用界面，也就是中断和陷阱（Interrupt Trap）总控部分与文件系统发生联系。以便把待执行的文 件读入内存，或把已经执行完毕的程序和结果写入文件系 统长期保存。 调度模块的作用是分配CPU。显然，在进行资源分配、特别 是CPU 分配时要按照一种既公平合理又有很高效率的分配 原则。在UNIX系统中，这个调度原则就是按照进程的优先 级，每次调度具有最高优先级的进程去占有处理机。每一 个进程，从它被创建的那一时刻起，就具有了一个随时间 动态变化的优先级。在UNIX System 中，系统有两个时 机计算各进程的优先级。这两个时机是： (1) 每秒钟一次的时间片结束发生时钟中断时，对那些优先级 大于某个常数的进程进行重新计算。 (2) 当前执行进程请求系统调用后，从中断和陷阱总控程序返 回当前执行的用户态时，重新计算当前执行进程的优先级 。 这里要指出的一点是，系统计算各进程优先级的时间并不总 是发生进程调度的时间。 UNIX System 中引起进程调度的情况有五种： (1) 当前执行进程申请内存等系统资源未得到满足，从而自己 调用sleep 过程,放弃处理机进入睡眠状态。 (2) 为了与其他并发进程保持同步，调用了wait或stop过程等 ，从而主动放弃了处理机而进入睡眠状态。 (3) 当系统发现系统中某进程的优先级已高于当前执行进程的 优先级时，系统设置一个名叫runrun的调度标志。但是， 系统并不在runrun标志刚被设置时就开始调度。它要等待 到系统在核心态下的程序执行完毕，由核心态转入用户态 时，也就是在中断陷入总控处理程序结束之前的瞬间，检 查runrun标志并进行调度。 (4) 时间片用完，且当前进程的优先级低于其他就绪进程。 (5) 当前进程调用exit，自我终止时。 进程通信是UNIX System 的一个重要组成部分。进程通信 既包括用来控制各并发进程执行速度和资源共享与竞争的 低级通信，也包括进程之间大量传递信息的高级通信。 UNIX系统在核心态下执行时，系统进程只能借助sleep 原语 和wakeup（或set-run）原语实现同步。sleep 原语使当前执 行进程以指定原因和优先数睡眠，而wakeup则唤醒在指定 原因上睡眠的所有进程。用户进程不能使用sleep 原语和 wake-up原语。用户进程之间要实现同步通信的话，一种办 法是利用系统核心提供的软中断信号进行通信。UNIX System 为用户使用软中断通信提供了相应的系统调用。 另一种办法是调用系统调用wait或sleep使得当前执行进程进 入等待状态，直到所等待事件发生时由核心唤醒或睡眠到 一定时间后自动唤醒。用户进程之间实现同步的高级办法 是使用System 提供的信号量方法。System 中的IPC模 块为进程间的大量信息传送提供了众多的系统调用。 除了上述通信手段之外，UNIX还提供了一种称之为管道（ pipe）的信息传送手段。它以临时文件的方式，实现同一主 机内的进程之间批量数据的单向、先进先出方式的无格式 字符流传送。 存储管理模块控制存储分配。任何一个待执行进程，如果它 不能在内存中占据必需的容量，它是不能执行的。换句话 说，CPU 绝对不会执行一个全部内容都在外存的进程。然 而，内存是一种有限而又昂贵的资源，它不可能容纳系统 中全部活动进程。存储管理系统必须决定把哪一个进程的 哪一部分留在内存中，而把哪一部分放在外存。也就是说 ，存储管理部分管理进程在内存和外存之间的信息转移， 以便所有进程都得到公平执行的机会。 下面先介绍UNIX系统的进程结构。 6.2 UNIX进程结构 本节将进一步介绍UNIX System 进程的静态构成，定义进 程上下文及其状态转换等。 6.2.1 进程的概念 在UNIX系统中，进程被赋予了下述特定的含义和特性： (1) 一个进程是对一个程序的执行。 (2) 一个进程的存在意味着在所谓的“proc”数组（PCB 的常驻 内存部分）中有一个非零的结构存在，它包含着相应的进 程控制信息。 (3) 对于每一个进程有一个被称为U 区或user结构的数据结构 。这个数据结构放置该进程的私用控制信息，且在进程被 创建时才会由系统分配相应的域。 (4) 一个进程可以生成或消灭其子进程。 (5) 一个进程是获得和释放各种系统资源的基本单位。 上述第(1)点是反映进程动态特性的，而第(2)点与第(3)点又反 映了进程的静态特性。第(4)点与第(5)点反映了UNIX系统的 进程之间的关系以及UNIX没有作业概念的特性。事实上， 由第3章可知，一个进程的静态描述是由三部分组成的，即 进程状态控制块PCB（栈段），进程的程序文本（正文） 段以及进程的数据段。在第3章中，把这三部分统称为进程 上下文，而进程的动态特性则定义为在进程上下文中的执 行。 首先介绍UNIX System 进程的虚拟地址结构。 由于UNIX System 进程的虚拟地址结构是依赖于硬件，因 此，如果不作特别说明，本文默认那些与硬件有关的部分 都是依赖于VAX11的。 6.2.2 进程的虚拟地址结构 如上所述，UNIX System 的进程由三个逻辑段组成：即存 放状态控制块的栈段、存放CPU 执行指令集合的正文段以 及被执行指令所访问的数据段。UNIX System 中，一个 进程的虚拟地址空间被分成若干个逻辑区（logical region） 来存放上述三个逻辑段。区是进程虚拟地址空间上的一段 连续区域，它是被共享、保护以及进行内存分配和地址变 换的独立实体。正文、数据和栈分别存放于各自的区中。 这里，要强调的一点是进程的虚拟地址在各区之内是连续的 。 为了管理每个进程中的区，系统设有一个称为区表的数据结 构，每个在系统中存在的区都在该表中占有一个表项。区 表包括下列内容： (1) 区的类型，指明该区存放正文段、数据段或私有数据及栈 段。 (2) 区的长度。 (3) 区所对应页表的内存始址。 (4) 区的状态，包括是否已被调入内存，是否正在调入内存过 程中，是否被锁住，以及是否正在被请求调入内存等。 (5) 共享位，给出共享该区的进程数。 (6) 文件系统指针，指向外存中与该区对应的数据文件。 区表如图6.4所示。 图6.4 系统区表 在系统创建新进程时，核心将从区表中分配相应的表项给所 创建的进程。 为了把区表和进程联系起来，当进程中的某个逻辑段在区表 中分得表项并填写了相关栏目之后，将把该表项的内存地 址返回到进程的proc结构中。proc结构中与区表项有关的还 有该段在虚存空间的起始地址，内存中的页表地址及页表 长度等。关于proc结构，将在后面讲述。 把区表和进程proc结构分开的原因之一是便于共享，因为每 个逻辑区（段）在不同的进程中对应的虚拟地址是不同的 ，但它们却可以通过区表而对应变换到同一物理内存空间 。区表和进程proc结构的关系如图6.5所示。 图6.5 区表与进程proc结构 在系统创建一个进程或让一个进程共享其他进程的某个段时 ，在分配区表项后或在改变有关区表项共享计数位后，把 这些区表项与有关进程连接起来。对新进程的连接是在创 建proc结构时填写区表项地址，该区表项对应逻辑段的虚拟 地址、所需页表的内存始址、逻辑段长度等。对共享段的 连接只要填写区表项地址、页表内存始址和长度即可。但 是，共享段的虚拟地址在不同的进程中是不一样的。 在区表的讨论中，大家也可能注意到一点，即UNIX System 中的区和段页式管理中的段非常相像。所不同的是，段 页式管理中的虚拟地址空间是二维的，而UNIX System 的各个进程的分区虚拟地址仍是一维的。另外，UNIX System 的分区并不是由用户按照段的逻辑功能独立定义 ，而是由系统设计人员预先设置好的。 6.2.3 进程上下文 UNIX System 的进程上下文是由正文段，也就是CPU 执行 指令的集合、核心数据结构、和有关寄存器的内容与数据 段组成。 1. 进程上下文的基本结构 进程上下文的各个部分按照一定的规则分布在进程虚拟空间 的不同位置上。对于不同的机器和硬件结构，进程上下文 的分布规则不同。例如，在VAX-11型机上，其虚拟地址空 间划分为进程空间和系统空间两大部分。其寻址范围为 232 个单元，即4096M 位。其中，虚拟空间的低位地址的半部 分（0 231-1）是进程虚拟空间，其余为所有进程共享的系 统空间，操作系统核心程序占据这个区。 进程虚拟空间又分为程序区P0和控制区P1，其中P0区用来放 用户程序，也就是进程上下文中的正文段代码。这个段的 起始虚址为0 ，且可以动态地向高地址方向增长。P1区容纳 各种方式的栈以及存放受保护的进程专用代码和数据，P1区 从231-1 单元开始向低地址方向增长。进程空间基本结构如 图6.6。 在图6.6中，核心态栈（kernal stack）是该进程执行核心程序 时，保留的核心栈副本。该栈中装有进程调用核心函数时 用到的有关参数等，另外，还包括系统调用的调用序列。 设置核心栈的目的是使进程在执行了不同调用顺序的核心 函数之后，仍能返回到原来的用户态下执行。核心栈具有 多个层次，其中每层可保留一次调用或中断处理后，返回 被中断程序处继续执行所必需的有关寄存器的值。 图6.6 进程空间结构 用户栈含有在用户态下执行时函数调用的参数、局部变量及 其他数据。图6.7给出了执行copy程序时用户栈和核心栈的 变化例。图6.7的左侧描述了当由 main (argc,argv) 过程调用 copy (old,new),过程copy (old,new) 更进一步调用库函数 write () 来调用 write 的内部结构。系统调用使用专门的陷 阱指令trap，执行trap指令将产生一个中断，使得进程的执 行模式由用户态转换为核心态。 然后，用户态执行转变为核心程序执行,并使用核心栈。 由于内核保护的原因，用户栈和核心栈之间不能互相传递参 数。因此，如果要把用户程序中的参数传递给核心函数， 必须通过通用寄存器和进程的PCB 结构。 图6.7 执行copy程序时用户栈和核心栈的变化 进程空间的用户进程正文段、数据段、用户栈、核心栈以及 有关的专用代码和数据是以进程为单位独立的。它们根据 需要换进换出内存。 在系统虚拟空间部分存放的进程上下文部分是：系统程序用 页表、进程页表、proc结构、核心正文段和数据段等。系统 虚拟空间的内容常驻内存，不因内存的大小或执行情况而 换进换出。另外，由于核心正文段和与它们有关的数据结 构、系统页表是被所有进程共享的，在UNIX系统中，不把 它们看作进程上下文的一部分。 2. 进程上下文的组成部分 进程上下文由proc结构、user结构、用户栈和核心栈的内容、 用户地址空间的正文段、数据段、硬件寄存器的内容以及 区表和页表等组成。 proc 结构 UNIX的proc结构和user结构相当于在第3章中介绍的进程控制 块PCB 。之所以把进程控制块分成两部分的原因是user结 构中主要包含那些只有进程执行时才被使用的控制信息， 从而，这些信息可以不必常驻内存而节省内存空间。 UNIX System 的proc结构主要包括以下各项： (1) 标识进程的状态用的状态位。UNIX System 共有9 个状 态编码。 (2) 若干用户标识号，简称UID 或用户ID。这些用户标识号指 出该进程属于哪一组用户，具有何种特权，例如是否可以 互相发送软中断等等。 (3) 若干进程标识号，简称PID 或进程ID，说明进程相互间的 关系。 (4) 存储区位置和长度，指明进程在内存或在外存中的位置及 大小。这些信息在进程换入换出，以及状态转换等时用到 。 (5) 调度参数，包括优先数等。核心用它们决定进程转换到核 心态和用户态的次序以及占有处理机的次序。 (6) 软中断信号项，记录发向一个进程的所有未处理的软中断 信号。 (7) 各种计时项，给出进程执行时间和系统资源的利用情况。 这些信息用来为进程计账、计算调度优先权，以及发送计 时信号等。 (8) user结构的起始地址项。 (9) 进程页表指针，用于CPU 访问内存时的地址变换。 user 结构 user结构则主要包括以下各项 (1) 指向proc结构的指针，标识出对应于该user结构的proc结构 。 (2) 一个含有系统调用结果的返回值项，当系统调用执行结束 之后，所得结果存放该项中以便用户程序可以使用。 (3) 与用户标识有关的若干项，它们决定进程的各种权限，如 存取权限等。 (4) 与文件结构有关的若干项，它们描述文件的当前目录和当 前根，以及进程的文件系统环境。 (5) 与文件读写有关的若干项，描述所要传送的数据量，在用 户空间的源(或目的）数据的数组地址、读写的文件字节数、 读写方式、缓冲区长度与地址等。 (6) 用户文件描述符表，记录该进程已打开的文件。 (7) 中断及软中断处理的有关参数，依靠这些参数，进程对所 收到的软中断信号作出不同的反应。 (8) 出错管理项，记录系统调用过程中遇到的错误，以便系统 或进程做相应的处理。 (9) 对该进程创建的所有文件设置许可权方式字段的屏蔽模式 项。 (10) 与上下文切换、现场保护有关的各项，它们保存通用寄 存器的用户区地址，保存各种寄存器的当前值，进程的核 心栈和用户栈指针，程序计数器和处理机状态字等当前值 。 (11) 各种计时项，记录进程及其后代在用户态和核心态下执 行时各自所用的时间。 (12) 进程数据段、正文段、栈段长度。 由以上proc结构与user结构的组成可知，proc结构中存放的是 系统感知进程存在所必需的数据和信息，而user结构中存放 的是进程执行时所必需的各种控制数据和信息。因此，系 统在内存中开辟有专用的proc结构区域，使proc结构常驻内 存且系统可存取访问任一proc结构。而user结构则不常驻内 存，且只有当一个进程被创建成功时，系统才为其分配user 结构空间。user结构的各项只能由其执行中的进程自己访问 存取。关于用户栈和核心栈已在上一小节中作了说明，这 里不再重复。 寄存器内容 进程上下文所包含的寄存器内容有： (1) 程序计数器PC的内容，指出CPU 将要执行的下条指令的 虚拟地址。 (2) 处理机状态寄存器的内容，称为处理机状态字PSW ， PSW 给出机器与该进程相关联的硬件状态。 PSW 包含当前执行进程的访问方式，即是在核心态下还是在 用户态下执行。另外，还包含中断优先级，以及中断或陷 入之前的访问方式等。 (3) 栈指针，指向栈中下一项的当前地址。至于指针是指向核 心栈还是用户栈，则由CPU 执行方式确定。 (4) 通用寄存器，用来存放进程在执行期间所产生的中间结果 或参数。例如，通用寄存器R0和R1就是在用户进程与系统 进程之间传递参数和返回值时用的。 区表和页表 区表和页表也是进程上下文的内容之一。它们定义了进程各 部分从虚拟地址到物理地址的映射。如果存在多个进程共 享某个公用区（正文区或数据区），那么这个公用区将是 每个进程上下文的一部分（注意，这对系统程序是不成立 的）。 进程正文段、数据段 进程正文段、数据段和用户栈等一起占据进程的虚拟地址空 间（0 231-1）部分，由区表和页表等组成的地址变换机构 将其虚拟地址变换为内存物理地址。由于 UNIX System 采用交换操作和请求页式虚存，因此，进程虚拟地址空 间的许多部分不是总驻留在内存中，但它们仍是进程上下 文的一部分。这一点与UNIX的早期版本有区别。 6.2.4 进程的状态和状态转换 一个进程的生命期是由一组状态来刻画的。这些状态是进程 proc结构的一部分。 UNIX System 中进程共有9 个状态，它们是： (1) 进程在用户态下的执行态SRUN。 (2) 进程在核心态下的执行态SRUN。 进程是在用户态下还是在核心态下执行主要由处理机状态字 PSW 来区别。 (3) 进程处于就绪态SRUN，只要核心程序调度到它，就可投 入执行。 (4) 进程处于就绪态SRUN，但交换程序已将其换出内存。只 有等待交换程序把它换入内存之后，核心才能调度它去执 行。 (5) 进程正在睡眠，且驻留在内存中的状态SSLEEP。 (6) 进程正在睡眠，但交换程序已将其换出内存的状态 SSLEEP。 (7) 进程正从核心态返回用户态。但核心抢先于它作了进程上 下文切换，以调度别的进程执行。最后，当该进程再次被 调度到时返回用户态。 (8) 进程刚被创建时，由于正在进行资源分配，因此，既不是 就绪态，也不是睡眠态。这个状态可被认为是进程的初始 状态。 (9) 进程执行了系统调用exit后，进入僵死状态。 图6.8给出了UNIX System 的进程状态转换图。 图6.8 进程状态转换图 图6.8反映了一个进程从被创建到被释放的整个生命周期内的 变化过程。状态之间的转换有些是通过系统原语或核心函 数完成（例如唤醒或调度等）。有些则由外部事件的发生 而导致状态转换（例如陷阱或中断）。 首先，当父进程执行系统调用fork时，被创建进程进入图中状 态8 ，即创建状态。在该状态时，核心为该进程分配user结 构区以及必要的内存工作集。内存管理分配程序如果能为 该进程分配足够的内存，则进程状态发生变化，由状态8 进 入内存就绪状态3 。此时，由于该进程已分得存放user结构 ，各种页表、堆栈、部分正文段和数据段所用的内存空间 ，因此，该进程可以经调度选中后占有CPU。 如果内存分配程序不能为该进程分配足够的内存，则该进程 的进程上下文被放入外存交换系统中，进程由状态8 进入外 存就绪状态5 。如果进程处于状态5 ，则只有在交换程序将 进程上下文换入内存成为状态3 之后，才有可能被调度执行 。 当进程进入状态3 后，进程调度程序将会在适当时机选择该进 程去执行。这时，该进程在核心态下执行，以装配该进程 的进程上下文。在这个状态下，该进程完成有关fork部分的 工作。 当该进程完成fork系统调用后，它可能返回用户态下执行用户 程序，这时进入状态1。 另外，在进程完成系统调用后返回用户态之前，根据UNIX System 的调度时机规定，此时若有优先级高于当前进程 的进程存在，则系统将调度优先级高的进程去占据处理机 ，从而进入状态7 。 进程进入状态7 之后，所处的地位与状态3 相同，即要等到再 一次进程调度时，才能返回用户态。 当进程处于状态1 时，用户程序中由于使用系统调用或由于输 入输出数据等而发生陷阱与中断。这样，进程又进入状态2 而变为在核心态执行。 进程在核心态执行时，因为等待某事件发生，例如等待输入 输出完成时，调用sleep 原语进入睡眠状态。处于睡眠状态 的进程因为内存的限制，将在睡眠一段时间后被交换程序 换出内存而进入外存睡眠状态6 ，直到事件发生后被唤醒原 语唤醒而进入状态5。 在进程完成它所要求任务之后，将使用系统调用exit，从而使 得进程进入僵死状态9 而释放资源。 6.2.5 小结 在本节中，讨论了UNIX System 中进程的虚拟地址空间， 并介绍了进程的上下文和进程的状态及转换。进程的虚拟 地址空间是进程管理和内存管理的基础，UNIX System 采用了分区连续虚拟地址空间的方法。这使得进程之间程 序或数据段的共享更加容易。 进程上下文是进程的静态描述。proc是系统感知进程存在的 唯一实体。proc结构中的各项是系统调度、控制进程必需的 ，因此，必须常驻内存。反过来，user结构是进程执行时才 要用到的控制信息，因此，如果一个进程不在执行过程中 ，其user结构是不必调入内存且不能被系统或其他进程所访 问的。进程上下文中的正文段和数据段是进程完成所要求 任务的关键部分，通用寄存器、程序计数器以及处理机状 态寄存器和页表、区表等都是为了正文段的顺利执行而用 来存放中间结果、传递参数，或存放下条指令的虚拟地址 ，或区别控制CPU 的访问模式和完成地址变换等功能的。 进程上下文各部分构成十分巧妙，缺一不可。 另外，进程可以在用户级对某些状态的转换加以控制。例如 ，用户可以创建进程，可以利用系统调用从用户态进入系 统态。但是，有些状态转换是由系统控制的。例如，被创 建进程是转换到内存就绪态还是外存就绪态取决于内存管 理程序。有些状态转换则要依靠外部事件和系统的共同控 制。例如，一个处于睡眠态的进程何时能转换成就绪态则 依赖于事件的发生和唤醒原语。 总之，进程的上下文和状态转换刻画了UNIX进程的静、动两 种特性，它们是进程的完整反映。 6.3 进 程 控 制 6.3.1 UNIX启动及进程树的形成 系统管理员首先通过自举把操作系统装入内存，并开始执行 它。自举过程是由系统管理员按动某个特殊的按钮来指示 机器从它的微代码装入启动程序的。UNIX系统的自举过程 是读一个磁盘的引导块（文件系统的第0 块），并将其装入 内存，在核心装入内存后，系统开始执行启动过程start 。 启动过程start 首先初始化系统内部数据结构。例如，构造 空闲缓冲区、初始化区结构、页表项等。然后，系统将根 文件系统安装到根“”下，并建立系统调度进程的proc结构 proc0 ，并使根“”成为进程0 的当前目录。 在创建和设置好进程0 的环境之后，系统就作为进程0 执行并 调用fork过程创建新进程1（这里的fork不是系统调用）， 也就是设置proc1 的有关表项。进程1 在系统中被称为 init进程。它是一个既可在核心态，又可在用户态运行的进 程，它的正文代码由调用系统调用exec执行程序“etc init ”的代码组成，进程1 负责初始化所有新的用户进程。 进程1 调用exec执行“etcinit”程序后，为每个终端生成一 个子进程，然后等待用户在终端上注册。 用户在终端上输入命令，每个命令都对应于一个可执行文件 。shell 命令解释程序解释此命令，找到相应的可执行命令 文件，用系统调用fork()创建子进程，并由此子进程调用系 统调用exec()执行此命令文件；父进程也就是终端进程则处 于等待状态，子进程执行文件结束后调用系统调用exit()自 我终止。唤醒父进程做善后处理并转而显示提示符，准备 接受下一条命令执行。 进程启动及进程树的形成过程如图6.9所示。 图6.9 进程树的形成 6.3.2 进程控制 1. 进程的创建 该节主要讨论用户进程的创建、执行和自我终止问题，与此 相对应，UNIX系统提供有相应的系统调用fork( )，exec( ) 和exit( ),以便在用户级上实现上述功能。 fork的功能是创建一个子进程。调用fork的进程称为父进程。 系统调用fork的语法格式是： pid fork ( ) ; 从系统调用fork返回时，父进程和子进程除了返回值pid 与 proc结构中某些特性参数不同之外，其他完全相同。CPU 在父进程中时，pid 值为所创建子进程的进程号，若在子进 程中时，pid 的值为零。 为了便于理解UNIX系统进程的并发性，下面介绍一下fork的 功能与实现过程。 系统调用fork通过执行核心程序fork过程完成的功能是： (1) 为子进程在proc结构表中分配一个空项。 (2) 为子进程赋一个唯一的进程标识号pid 。 (3) 复制一个父进程上下文的逻辑副本。这里的逻辑副本是指 不把父进程中那些可被共享的部分复制到新的内存区中， 而只改变共享区的引用数。但是，对于父进程的非共享区 部分则复制到新的内存区中。 (4) 增加与父进程相关联的有关文件系统的进程引用计数。 (5) 对父进程返回子进程的进程标识号，对子进程返回零。 下面介绍fork算法。其算法流程图如图6.10所示。 在图6.10中，系统首先检查有无足够的内存或外存交换空间存 放子进程的上下文。在资源满足的条件下，系统在proc结构 中为子进程分配一空表项，并开始构造子进程的上 下文。 系统在分配给用户proc结构表时，对用户同时拥有的进程个 数有一定的限制，以免妨碍其他用户创建进程。另外，普 通用户不能占用proc结构表中的最后一个表项，以防系统发 生死锁而无法正常退出。再者，系统为新创建进程所分配 的标识号按比最近一次分配的进程标识号大1 的顺序递增。 当标识号达到所规定的最大值之后，则从0 开始重新循环。 图6.10 fork流程图 紧接着，系统从父进程proc结构中，把除了pid 等之外的大部 分项复制到子进程proc结构中。然后，系统设置子进程的各 种调度参数，并把子进程状态置为SIDI（创建态）。 然后，系统调整进程与文件的接口，使得子进程自动共享父 进程所打开的文件，以及确定子进程在文件系统中所处的 目录位置（有关文件系统，将在后面的章节中讲述）。 下一步，系统将把进程的上下文中的寄存器内容保存在父进 程的fork专用保存区（fork的核心栈）中。系统在保存的寄 存器内容中，包括程序计数器和处理机状态字等内容。这 些内容将在后述各步中复制给子进程，以便子进程执行时 能识别出自己是子进程，并从这里开始执行。 接着，系统开始把父进程的上下文复制到子进程中去。这包 括为子进程的user结构区及页表等分配内存和进行复制。另 外，如果父进程的正文段和数据段不允许共享的话，则也 要将这些非共享部分复制到子进程的内存区或外存区中。 对于那些允许共享的部分，则只要增加相应的共享计数值 就行。子进程的user结构除了指向proc结构表项的指针与父 进程的不同之外，其他部分与父进程的user结构完全相同。 以上复制的上下文部分是进程的静态部分，除了复制父进程 的静态上下文之外，系统也将保存有寄存器内容的核心栈 内容复制到子进程的核心栈上去。以利于进程能从系处开 始执行。注意在有的计算机中，核心栈是作为user结构的一 部分实现的，因此不必再另外需要内存和进行专门的复制 。但有些计算机中，核心栈不是user结构的一部分，此时， 则需把核心栈复制到子进程的一个私有存储区上。 由于复制子进程的上下文需要足够大的内存，有时，内存空 闲区是不能满足这个要求的。这时，上述复制只好在虚空 间完成，也就是说，所创建的子进程上下文将被换出内存 空间。否则，父进程将子进程的状态改为“内存就绪”之后 ，从核心态准备返回到用户态。如果此时不发生进程调度 和不调度到子进程执行，则父进程将子进程的pid 返回给用 户后回到用户态执行。否则，调度算法调度到子进程执行 ，子进程返回零值给用户后，完成fork调用返回用户态执行 。 2. 执行一个文件的调用 当父进程使用fork创建了子进程之后，子进程继承了父进程的 正文段和数据段，从而限制了子进程可以执行的程序规模 。那么，子进程用什么办法来执行那些不属于父进程正文 段和数据段的呢？这就是利用系统调用exec( )或exece( )。系 统调用exec引出另一个程序，它用一个可执行文件的副本覆 盖调用进程的正文段和数据段，并以调用进程提供的参数 转去执行这个新的正文段程序。 系统调用exec( )包含六种不同的调用格式，但它们都完成同一 工作，即把文件系统中的可执行文件调入并覆盖调用进程 的正文段和数据段之后执行。有关exec的各种系统调用的区 别主要在参数处理方法上。这些系统调用使用不同的输入 参数、环境变量和路径变量。 这里，系统调用execvp()和execlp()在程序中经常用到，其调用 格式是： execvp (filename ，argp)， 或 execlp (filename ，arg0 ，arg1，.，(char *)0); 其中，filename是要执行的文件名指针，argp是输入参数序列 的指针，而0则是参数序列的结束标志。 例：用execlp 调用实现一个shell 的基本处理过程。 利用fork-exec 可实现一个shell 的基本功能。用户输入命令后 ，按以下步骤执行用户命令（图6.11）。 (1) 利用fork，创建子进程。 (2) 利用exec，启动命令程序。 (3) 利用wait，父进程和子进程同步。 图6.11 shell执行过程 用C语言实现的程序例如下。 #include stdio.h main ( ) char command32 ; char * prompt = “ $ ” ; while (printf (“%s” ，prompt) ,gets (command) != NULL) if (fork () = 0) execlp (command ，command ，(char *)0) ; else wait (0) ; 上面实现的shell 中，不包含路径检索功能（即执行有关命令 时，必须把从根开始至命令名为止的路径名全部输入）， 也没有包括参数处理功能。此例只是为了说明exec调用的应 用以及fork与exec的关系。 3. 进程的终止 系统调用exit(rv)自我终止当前进程，使其进入SZOMB 僵死 状态，等待父进程进行善后处理。 exit调用将导致释放除proc结构之外的所有资源，并清除进程 上下文。父进程在收到子进程的信息rv和有关子进程的时间 信息之后，将释放子进程的proc结构和将有关时间信息加到 自己的proc结构的有关项中去。 6.4 UNIX进程调度与交换 UNIX系统的调度与交换都是进程0 的两个部分。它们分别由 swtch () 过程和sched ()过程实现。事实上，用于交换的 sched 过程是把处于外存就绪态的进程换入内存，相当于三 级调度中的中级调度（UNIX系统中没有高级调度）。因此 ，有时也把进程0 称为调度进程。下面分别介绍进程的调度 与交换。 6.4.1 进程调度 1. 调度原理 UNIX系统的进程调度采用多级反馈轮转调度法（Round Robin with Multiple Feedback）。即系统给进程分一个 时间片，当时间片结束时，动态计算该进程的优先级，若 有优先级高于当前进程的内存就绪态进程时，系统设置调 度标识，在由核心态转换到用户态前由swtch 过程调度优先 级高的进程执行，并把被抢先的进程反馈到相应的优先级 队列中。一个进程在它结束之前，可能要经过多次反馈循 环。 UNIX的进程调度按时间片计算优先级,并按优先级的高低来调 度进程,抢占处理机。因此，UNIX系统的进程调度是基于时 间片加优先级的。 UNIX的进程调度涉及的主要问题是： (1) 调度的时机。 (2) 调度标志设置。 (3) 调度策略与优先数的计算。 (4) 调度的实现。 下面，分别说明这几个问题。 2. 调度的时机 在UNIX系统中，为了减少操作系统设计的复杂性和提高系统 执行效率，对操作系统程序采用了伪异步执行方式。也就 是说，设计人员认为在系统程序执行期间不会发生调度或 发生调度的时间是可预知的。然而，由于调度程序swtch 又 是进程0 的一部分，也就是说是系统程序，这又要求调度必 须在核心态下完成。怎样把这二者统一起来呢？显然，采 用系统调用的方式向用户开放进程调度是不可取的，这一 是导致系统无法控制，二是可能造成系统瘫痪和很多意想 不到的问题出现。UNIX的设计者们采用了当处理机在执行 完核心程序之后向用户态转换之前的瞬间,检查各就绪进程 的优先级进行调度的方法。由用户态转而执行核心程序的 可能性很多。例如中断处理和陷阱处理，系统调用等。 另一种可以切换处理机的时机是：当进程因申请系统资源而 未得到满足，从而调用过程sleep 放弃处理机；或者是进程 为了与其他进程保持同步而调用 wait 或stop程序放弃了处 理机；或由于执行了exit调用，终止了当前进程。这几种情 况下，由于发生调度的时机是可以预见的，因此，在这些 程序执行结束之前，都自动调用switch 过程调度其他优先 级高的进程执行。 综上所述，UNIX System 中，发生进程调度的时机实质上 只有两个：一个是进程自动放弃处理机时自动转入调度进 程，另一个则是在由核心态转入用户态时，系统设置了高 优先级就绪进程的强迫调度标识。 3. 调度标识的设置 UNIX System 中有三个关于调度和交换用的调度标识。它 们是runrun、runin和runout。 runrun标识是要求处理机调度程序进行调度的标识，由唤醒 原语wakeup、setrun及优先级设置过程setpri在发现某进程 的优先级高于当前进程的优先级时，设置runrun标识。另 外，每隔一秒一次的时钟中断处理中也将检查各就绪态进 程的优先级而设置runrun标识。只要设置了该标识，在中 断陷阱程序结束之前，系统就会调用swtch 过程调度具有最 高优先级的进程执行。 runin 和runout标识是用于就绪进程换入换出内存的。runin 表示内存无足够空间换入一个外存就绪态进程，设置runin 标识也意味着内存中无适当的进程可以换出。runout标识与 runin 相反，它表示外存交换区中无适当的进程可以调入内 存。 4. 调度策略与优先数的计算 UNIX System 采用动态优先数调度策略。在UNIX系统中 ，优先数越大优先级越低。调度策略从内存就绪队列中选 取优先数最小的进程投入执行。 System 采用下式计算各进程的优先数： P-pri P-CPU2 PUSER P-nice NZERO 其中，PUSER 和NZERO 是称为基本用户优先数的阈值。在 System 中，这两个数是常数，分别为25和20。P-CPU 为 每个进程的最近一次CPU 使用时间。当进程使用CPU时， 系统每个时钟周期对该进程的P-CPU 加1 ，最多时该值可 达80。另外，系统按每秒钟的时间间隔对P-CPU 执行除以2 的衰减操作。这样，如果系统的时钟周期为16.667ms的话 ，则系统进行每秒时钟中断处理时，P-CPU 的值将由60变 为30。P-nice是系统允许用户设置的一个进程优先数偏移值 。System 中，P-nice可以被设置成0 40间的一个数。但 一旦设置之后，除了超级用户可以将其减小之外，普通用 户仅能作增加的改变。 显然，由于新创建的进程未使用CPU ，其P-CPU 值为0 ，因 而具有较高的优先级。但随着被调度执行，其P-CPU 的值 将会不断增加，从而在每秒1 次的时钟中断处理时，将被其 他P-CPU 值小的进程所抢先。然后，随着其他进程的执行 以及每秒1 次的P-CPU 值的衰减，当其优先数小于当前进 程和其他进程之后，又会重新抢占处理机。 5. 调度的实现 进程调度是由swtch 过程实现的。这里主要讲述swtch 的执行 过程。 swtch 过程实质上是完成一个进程之间的上下文切换过程。它 的执行分为三个阶段，涉及三个进程。 第一阶段检查决定是否做上下文切换和系统是否允许做上下 文切换。如果允许做上下文切换的话，则保存当前进程的 上下文。 在UNIX System 中，系统通过禁止任意的上下文切换来保 证内部数据结构的完整性和一致性。在做上下文切换之前 ，系统必须保证各种正在更新的内部数据结构都已完成， 各种队列都已正确链接，各种数据结构的加锁、解锁都已 完成等。 在保存了当前进程的上下文之后，紧接着swtch 过程要先恢复 进程0 的进程上下文，以提高优先级和为第二阶段的调度选 择高优先级进程提供执行环境。在UNIX System 中，当前 进程上下文的保存工作主要涉及各种寄存器内容（寄存器 上下文）和栈指针的保存。因为进程上下文的其他部分都 在内存或外存中，不会因其他进程抢占处理机而受到影响 ，只有寄存器只存放当前进程的内容，因此，当一个进程 被抢先时，必须保存各种寄存器的内容以及指向它们的指 针,以便该进程被再次调度执行时能恢复其执行环境。 当前进程的有关寄存器内容及栈指针的保存是由过程save(u.u- rsav)完成的。该过程把有关寄存器内容保存在核心栈中或 user结构中的u-rsav和u-pcb 中（此时核心栈在user结构中 ）。而进程执行环境的恢复则是由过程resume完成的。 第二阶段属于进程0 部分。第二阶段使用本节前面所述的调度 算法，从内存就绪队列中寻找一优先级最高进程。若内存 就绪队列中没有这样的进程存在，则调出idle过程循环等待 某进程变为就绪状态。若就绪队列中有符合条件的进程存 在，则选取该进程占据处理机。 第三阶段属于被选中进程。该进程已成为当前进程，因此， 它调用resume，从它的核心栈或user结构中的u.u-rsav及u.u -pcb 等中恢复该进程的有关寄存器内容和栈指针，从而使 得新进程开始正常执行。 6.4.2 交换 UNIX的早期版本（BSD 4.0 以前）在内存和外存之间传送整 个进程，从而给交换赋予了特殊的含义。即将内存中的整 个进程上下文换出内存后将驻留在外存的整个进程上下文 换入内存。 交换功能由进程0完成。在系统初始化结束时，进程0 就进入 无限循环，先试图从外存交换区换入进程（因为初始化结 束时内存总不会是满的），内存不够时再换出进程。如果 没有进程要换入换出时，则该进程进入睡眠状态。 系统通过时钟中断定期唤醒进程0 完成交换功能。在进程0 执 行之前，时钟中断处理程序计算出每个就绪进程在内存或 外存中驻留的时间。 交换算法实际上涉及三个部分：外存交换设备的空间管理、 交换区中的进程换入、内存中进程的换出。sched 过程完成 进程的换入与换出。至于外存交换设备的空间管理，将在 本章后面部分简单介绍。 sched 过程的流程图如图6.13所示。 图6.13 sched过程流程图 在图6.13中sched 程序首先检查proc结构表，寻找一个不在内 存且驻留时间最长的就绪态进程。如果该进程在外存交换 区的驻留时间小于2 秒，则表示没有适当的进程可以换入， 从而设置runout标识后进入睡眠状态。反之，如果sched 过 程找到了一个适当的就绪态进程，则启动输入输出设备， 将其写入内存。如果内存中没有足够的内存空间（这可由 存储