1、第第2 2章章 进程管理进程管理 第第2章章 进程管理进程管理 2.1 进程概念进程概念 2.2 线程线程 2.3 进程管理进程管理 2.4 进程间通信进程间通信 2.5 经典进程同步问题经典进程同步问题 2.6 管程管程 2.7 进程通信进程通信 2.8 Linux进程管理进程管理 习题习题 第第2 2章章 进程管理进程管理 2.1 进进 程程 概概 念念 2.1.1 程序的顺序执行 顺序程序活动有三个主要特点：(1)程序所规定的动作在机器上严格地按顺序执行。(2)只有程序本身的动作才能改变程序的运行环境。(3)程序的执行结果与程序运行的速度无关。第第2 2章章 进程管理进程管理 图2-1列
2、出了几个典型的顺序程序的示意图。其中图(a)最简单，一条条指令顺次做下去；图(b）表示程序代码中出现循环的情况；图(c)表示A程序在执行过程中调用B程序，B运行完，返回A，继续执行A的情况。第第2 2章章 进程管理进程管理 图2-1 顺序程序示意图 N：(a)(b)(c)ABjmp：NM：第第2 2章章 进程管理进程管理 2.1.2 程序的并发执行和资源共享 多道程序 设计是指两个或更多个程序同时在系统中存在并且运行。这时的工作环境与单道程序（仅一个）的运行条件相比，大不相同。首先，每个用户程序都需要一定的资源，如内存、设备、CPU时间等，因此系统中的软、硬件资源不再是单个程序独占，而是由几道
3、程序所共享。这样，共享资源的状态就由多道程序的活动共同决定，从而打破了单道程序“闭关自守”的局面。第第2 2章章 进程管理进程管理 图2-2 非多道技术下作业执行过程 A开始空转输入运行空转输入A停止作业AB开始作业B等 待空转输入运行空转输入B停止第第2 2章章 进程管理进程管理 采用多道程序技术来执行同样的作业A和B，就能大大改进系统性能，如图2-3所示。作业A先运行，它运行一秒后等待输入，此时让B运行；B运行一秒后等待输入，此时恰好A输入完，可以运行了就这样在CPU上交替地运行A和B。在这种理想的情况下，CPU不空转，其使用率升至百分之百，并且吞吐量也随之增加了。第第2 2章章 进程管理
4、进程管理 图2-3 多道技术下作业执行过程开始空转输入空转输入停止作业A作业B开始空转输入空转输入停止第第2 2章章 进程管理进程管理 2.1.3 程序并发执行的特性 资源共享和程序的并发执行使得系统的工作情况变得非常复杂，带来一系列新的问题，特别表现在各种程序活动的相互依赖和制约关系方面。我们分析一下图2-4中几个程序并发执行的情况。第第2 2章章 进程管理进程管理 图2-4 并发程序的执行(a)并发执行的程序；(b)并发程序的关系；(c)有制约关系的并发程序程序An:0;K1n:n1;K2程序B打印n12(a)程序Acall C程序Bcall C程序C(b)程序Mcall S程序Ncall
5、 S5程序S172394810C1C3C2(c)S36第第2 2章章 进程管理进程管理 通过上述三个例子的分析，可以得出并发程序的三个主要特征：（1)没有封闭性。有共享公共变量时，其执行结果不可再现，就是说，结果与相关的并发程序的相对速度有关。(2)程序与计算不再一一对应。“程序”是指令的有序集合，是“静态”的概念。（3)并发程序在执行期间可以互相制约。第第2 2章章 进程管理进程管理 2.1.4 进程概念的引入和描述 “进程”是操作系统的最基本、最重要的概念之一。引进这个概念对于理解、描述和设计操作系统都具有极其重要的意义。但是迄今为止，对这个概念还没有形成统一的定义，都是从不同的角度来描述
6、它的各个基本特征。下面列举出比较能反映进程实质的几种定义：第第2 2章章 进程管理进程管理 (1)进程(或任务)是可以和别的计算并发执行的计算。(2)进程是程序的一次执行，是在给定内存区域中的一组指令序列的执行过程。(3)所谓进程，简单说来就是一个程序在给定活动空间和初始条件下，在一个处理机上的执行过程。(4)进程可定义为一个数据结构和能在其上进行操作的一个程序。(5)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。第第2 2章章 进程管理进程管理 进程和程序是两个不同的概念，但又有密切的联系。它们之间的主要区别是：(1)程序是静态概念，本身可以作为一种软件资源
7、长期保存着；而进程则是程序的一次执行过程，它是动态概念，有一定的生命期，是动态地产生和消亡的。第第2 2章章 进程管理进程管理 (2)进程是一个能独立运行的单位，能与其他进程并发执行，进程是作为资源申请和调度单位存在的；而通常的程序段是不能作为一个独立运行的单位的。(3)程序和进程无一一对应关系。一个程序可由多个进程共用；另一方面，一个进程在其活动中又可顺序地执行若干个程序。第第2 2章章 进程管理进程管理 (4)各个进程在并发执行过程中会产生相互制约关系，造成各自前进速度的不可预测性。而程序本身是静态的，不存在这种异步特征。表2-1列出了进程和程序之间的主要区别。第第2 2章章 进程管理进程
8、管理 表2-1 进程和程序的对比 第第2 2章章 进程管理进程管理 2.1.5 进程的状态及其变迁 进程是一个程序的执行过程，有着走走停停的活动规律。进程的动态性质是由其状态变化决定的。如果一个事物始终处于一种状态，那么它就不再是活动的，就没有生命力了。通常在操作系统中，进程至少要有三种基本状态，这些状态是处理机挑选进程运行的主要因素，所以又称之为进程控制状态。这三种基本状态是：运行态、就绪态和阻塞态（或等待态）。如图2-5所示。第第2 2章章 进程管理进程管理 图2-5 进程状态及其变化 运行状态就绪状态阻塞状态时间片到分到CPU等待某事件发生(如等待I/O)所等待事件发生(如I/O完成)第
9、第2 2章章 进程管理进程管理 在很多操作系统中，又添加了两种基本状态：创建态和终止态。创建态是指新进程正被创建时的状态，当创建工作完成后它就进入到就绪态。终止态是指进程正常或非正常终止时所处的状态，它的必然结局是从系统中消失。上述五种进程状态及其变迁情况如图2-6所示。第第2 2章章 进程管理进程管理 图2-6 进程的五种基本状态 创建状态运行状态就绪状态阻塞状态时间片用完分到CPU等待某事件发生(如等待I/O)所等待事件发生(如I/O完成)完成创建工作终止状态终止第第2 2章章 进程管理进程管理 2.1.6 进程的组成 进程的活动是通过在CPU上执行一系列程序和对相应数据进行操作来体现的，
10、因此程序和它操作的数据是进程存在的实体。但这二者仅是静态的文本，没有反映出其动态特性。为此，还需要有一个数据结构，用来描述进程当前的状态、本身的特性等。这种数据结构被称为进程控制块（PCB，Process Control Block)。第第2 2章章 进程管理进程管理 程序往往由一系列函数组成。执行函数调用时要保存好调用者的现场信息，以便被调函数完成后能恢复调用者的运行环境。这一系列现场信息要保存在堆栈中，按“后进先出”方式管理。为此，系统要为每个进程设立一个或多个栈。所以进程通常都由程序、栈、数据集合和PCB这四部分组成。图2-7示出进程的物理结构。第第2 2章章 进程管理进程管理 图2-7
11、 进程组成 PCB栈程序数据第第2 2章章 进程管理进程管理 2.1.7 进程控制块 进程控制块有时也称为进程描述块（Process Descriptor），它是进程映像中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，它是系统对进程施行识别和控制的依据。在不同的系统中，PCB的具体组成成分是不同的，在简单操作系统中它较小；而在大型操作系统中它很复杂，设有很多信息项。一般来说，进程控制块应包括如下内容，如图2-8所示。第第2 2章章 进程管理进程管理 图2-8 PCB构成 第第2 2章章 进程管理进程管理 （1）进程名。它是惟一标志对应进程的一个标志符或数字。(2)特
12、征信息。它包括是系统进程还是用户进程，进程映像是否常驻内存等。(3)进程状态信息。它表明该进程的执行状态，是运行态、就绪态还是阻塞态。(4)调度优先权。这表示进程获取CPU的优先级别。第第2 2章章 进程管理进程管理 (5)通信信息。它反映该进程与哪些进程有什么样的通信关系，如等待哪个进程的信号等。(6)现场保护区。当对应进程由于某个原因放弃使用CPU时，需要把它的一部分与运行环境有关的信息保存起来，以便在重新获得CPU后能恢复正常运行。第第2 2章章 进程管理进程管理 (7)资源需求、分配和控制方面的信息。如进程所需要或占有的IO设备、磁盘空间、数据区等。(8)进程映像信息。指出该进程的程序
13、和数据的存储情况，在内存或外存的地址、大小等。(9)族系关系。它反映父子进程的隶属关系。(10)其他信息。如文件信息、工作单元等。第第2 2章章 进程管理进程管理 2.1.8 PCB的组织方式 1.线性表方式 如图2-9所示，线性表的方式简单，最容易实现。操作系统预先确定整个系统中同时存在的进程最大数目，比如是n，静态分配空间，把所有的PCB都放在这个表中。第第2 2章章 进程管理进程管理 图2-9 PCB线性表 第第2 2章章 进程管理进程管理 2.链接表方式 链接表方式是经常采用的方式。其原理是：按照进程的不同状态分别放在不同的队列中，如图2-10所示。第第2 2章章 进程管理进程管理 图
14、2-10 PCB链接表PCBPCBPCB0就绪队列指针运行队列指针PCBPCBPCB0阻塞队列1指针PCBPCB0阻塞队列2指针PCB0第第2 2章章 进程管理进程管理 3.索引表方式 索引表方式是利用索引表记载各种状态进程的PCB地址，如就绪索引表中的表项指向就绪进程PCB的指针，而阻塞表中的表项指向阻塞进程PCB的指针。各索引表的起始地址放在专用的指针单元中，运行进程的PCB由一个专用的运行指针指向。图2-11示出PCB索引表方式。第第2 2章章 进程管理进程管理 图2-11 PCB索引表 PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB9就绪索引表阻塞索引表i运行指
15、针就绪表指针阻塞表i指针PCB表第第2 2章章 进程管理进程管理 2.2 线线 程程 2.2.1 线程概念 1.线程 线程 是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。如果把进程理解为在逻辑上操作系统所完成的任务，那么线程表示完成该任务的许多可能的子任务之一。第第2 2章章 进程管理进程管理 2.Thread结构 每个线程有一个Thread结构，用于保存与线程有关的信息，主要由以下几个基本部分组成：(1)一个惟一的线程标识符。（2）描述处理器状态的一组状态寄存器的内容，用于调度。（3）每个Thread结构有两个堆栈指针：一个指向核心堆栈，一个指向用户堆栈。（4）一个私有存储区，存
16、放现场保护信息及其他各种统计信息等。第第2 2章章 进程管理进程管理 图2-12 Thread结构 线程标识符调度状态信息核心堆栈指针用户堆栈指针私有存储区核心堆栈用户堆栈第第2 2章章 进程管理进程管理 3.带线程的进程模型 一个进程可以包含一个或者多个线程，但至少要有一个线程。在传统的进程中就只有一个线程。当一个进程包含多个线程时，各线程除自己有少量私有资源（如程序计数器、寄存器和堆栈）外，要共享所属进程的全部资源（如程序代码、数据和文件等）。图2-13示出单线程和多线程的进程模型。第第2 2章章 进程管理进程管理 图2-13 单线程式和多线程式的进程代码数据文件寄存器栈寄存器栈寄存器栈线
17、程代码数据文件寄存器栈线程(a)(b)第第2 2章章 进程管理进程管理 4.进程与线程的关系 从以上介绍中可以看出，进程和它的线程有如下关系：（1）一个进程可以有多个线程，但至少要有一个线程。（2）进程是资源的拥有者，是分配资源的独立单位；而线程一般不拥有系统资源（仅有一点必不可少的资源），同一进程的所有线程共享该进程的全部资源。（3）在支持线程的操作系统中，线程是调度和分派的基本单位。第第2 2章章 进程管理进程管理 （4）进程可以并发执行。（5）线程在执行过程中往往需要协作同步。（6）在实施创建、撤消和切换等操作时，进程的开销远大于线程的开销。（7）线程和进程一样，都是动态实体，具有不同的
18、状态，如运行态、就绪态、阻塞态和终止态等。第第2 2章章 进程管理进程管理 2.2.2 线程的实现方式 1.用户级线程 在这种方式下，整个管理线程的线程库放在用户空间，对线程从创建到撤消的全部管理工作都由应用程序完成。核心对线程一无所知，只对常规进程实施管理。图2-14(a)示出用户级线程的实现方式。第第2 2章章 进程管理进程管理 图2-14 线程的实现方式 核心运行时系统 线程表进程表进程线程(a)核心进程表进程线程(b)线程表用户空间核心空间第第2 2章章 进程管理进程管理 用户级线程实现方式具有以下三个优点：（1）线程切换速度快。（2）调度算法可以是应用程序专用的，不仅最适合自己的需求
19、，而且不干扰底层操作系统的进程调度。（3）用户级线程可运行在任何操作系统上，包括不支持线程机制的操作系统。第第2 2章章 进程管理进程管理 用户级线程方式也存在两个主要缺点：（1）系统调用的阻塞问题。当一个线程执行系统调用时，不仅它自己被阻塞，而且在同一进程内的所 有线程都将被阻塞。（2）这种方式下的多线程应用程序不具有多处理的优点。因为核心只为每个进程一次分配一台处理机。第第2 2章章 进程管理进程管理 2.核心级线程 在这种方式下，核心知道线程的存在，并对它们实施管理。如图2-14(b)所示。在核心空间中不仅有一个进程表，而且有一个线程表，其中记载系统中所有线程的情况。这样，就由核心统一管
20、理系统中所有的线程。核心进行调度时以线程为基本单位。第第2 2章章 进程管理进程管理 核心级线程的优点是：（1）在多处理器系统中，核心可以同时调度同一进程的多个线程，真正实现并行操作。（2）一个进程的某个线程阻塞了，核心可以调度同一进程的另一个线程运行。核心级线程方式也存在缺点，主要是：（1）线程切换速度慢，控制转移开销大。（2）调度算法由核心确定，应用进程无法影响线程的切换。第第2 2章章 进程管理进程管理 2.3 进进 程程 管管 理理 2.3.1 创建进程 1.进程图(Process Graph)与多数操作系统对进程的管理相似，UNIX系统中各个进程构成了树型的进程族系，如图2-15所示
21、。第第2 2章章 进程管理进程管理 图2-15 各个进程构成了树型的进程族系0#1#P_sP2iP2oP2nP31P3jP4mP4kshell进程执行shell命令第第2 2章章 进程管理进程管理 2.进程创建过程 父进程利用系统调用（如UNIX/Linux系统中的fork）来创建子进程，其主要过程如下：（1）申请一个空闲的PCB。（2）为新进程分配资源。（3）将新进程的PCB初始化。（4）将新进程加到就绪队列中。第第2 2章章 进程管理进程管理 2.3.2 终止进程 终止进程的主要操作过程是：(1)从系统的PCB表中找到指定进程的PCB。(2)回收该进程所占用的全部资源。(3)若该进程还有子
22、孙进程，则还要终止其所有子孙进程，回收它们所占用的全部资源。(4)释放被终止进程的PCB，并从原来队列中摘走。第第2 2章章 进程管理进程管理 2.3.3 更换进程映像 改变进程映像的工作很复杂，其主要过程是：（1）释放子进程原来的程序和数据所占用的内存空间；（2）从磁盘上找出子进程所要执行的程序和数据（通常以可执行文件的形式存放）；（3）分配内存空间，装入新的程序和数据；（4）为子进程建立初始的运行环境主要是对各个寄存器初始化，返回到用户态，运行该进程的程序。第第2 2章章 进程管理进程管理 2.3.4 阻塞进程 进程阻塞的过程如下：（1）立即停止当前进程的执行；（2）将现行进程的CPU现场
23、送到该进程的PCB现场保护区中保存起来，以便将来重新运行时恢复此时的现场；第第2 2章章 进程管理进程管理 （3）把该进程PCB中的现行状态由“运行”改为“阻塞”，把它插入到具有相同事件的阻塞队列中；（4）然后转到进程调度程序，重新从就绪队列中挑选一个合适的进程投入运行。第第2 2章章 进程管理进程管理 2.3.5 唤醒进程 唤醒原语执行过程是：（1）首先把被阻塞进程从相应的阻塞队列中摘下；（2）将现行状态改为就绪态，然后把该进程插入到就绪队列中；（3）如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标志。第第2 2章章 进程管理进程管理 2.4 进进 程程 间间 通通 信信 2.4.1
24、 进程间的关系 1.同步 同步是进程间共同完成一项任务时直接发生相互作用的关系，也就是说，这些具有伙伴关系的进程在执行的时间次序上必须遵循确定的规律。第第2 2章章 进程管理进程管理 2.互斥 协同工作的进程之间存在同步关系，但是进程之间更一般的关系是互斥关系，这是由于诸进程共享某些资源而引起的。3.通信 进程经常需要与其他进程通信。第第2 2章章 进程管理进程管理 2.4.2 竞争条件和临界区 1.竞争条件 在有些操作系统中，并发进程在活动过程中可能共享一些彼此都能够读写的公用存储区。它可能在内存中，也可能是一个共享文件，其所在位置并不影响问题的实质。下面我们考虑两个进程对一个系统打印机分配
25、表的操作情况。第第2 2章章 进程管理进程管理 假定进程Pa负责为用户进程分配打印机，进程Pb负责释放打印机。由于分配和释放可能同时发生，因此两个进程必须共享一个打印机分配表，如表2-2所示。第第2 2章章 进程管理进程管理 表2-2 打印机分配表 第第2 2章章 进程管理进程管理 Pa进程分配打印机的过程是：(1)逐项检查分配标志，找出标志为0的打印机号码；（2）把该机的分配标志置1；（3）把用户名和设备名填入分配表中相应位置。第第2 2章章 进程管理进程管理 Pb进程释放打印机的过程是：（1）逐项检查分配表的各项信息，找出标志为1并且用户名和设备名与被释放的名字相同的机号；（2）该机标志清
26、0；（3）清除该机用户名和设备名。第第2 2章章 进程管理进程管理 表2-3 打印机分配表（出错情况）第第2 2章章 进程管理进程管理 2.临界区 为了使临界资源得到合理使用，就必须禁止两个或两个以上的进程同时进入临界区内，就是说欲进入临界区的若干个进程要满足如下关系：（1）如果有若干进程要求进入临界区，一次仅允许一个进程进入。第第2 2章章 进程管理进程管理 （2）任何时候，处于临界区内的进程不可多于一个。（3）进入临界区的进程要在有限时间内退出，以便其他进程能及时进入自己的临界区。（4）如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。第第2 2章章 进程管理进程管理
27、 2.4.3 用锁操作原语实现互斥 进程通信是实现进程间同步与互斥的一种机制。这类似于人类社会生活中为表达意见、交流思想、交换信息等而采用多种通信方式，例如，人们打手势、交谈、打电话、写信、发E-mail等，方式有简有繁，当然其功能也有强弱之别。下面分别介绍典型的实现进程同步与互斥的手段。第第2 2章章 进程管理进程管理 为解决进程互斥进入临界区的问题，可为每类临界资源设置一把锁，该锁有打开和关闭两种状态。进程执行临界区程序的操作按下列步骤进行：(1)关锁。先检查锁的状态，如为关闭状态，则等待其打开；如已打开了，则将其关闭，继续执行（2)的操作。（2)执行临界区程序。(3)开锁。将锁打开，退出
28、临界区。第第2 2章章 进程管理进程管理 2.4.4 信号量上的P、V操作原语 1.信号量（Semaphore）信号量及信号量上的P操作和V操作是E.W.Dijkstra在1965年提出的一种解决同步、互斥问题的更通用的方法，并在THE操作系统中得以实现。第第2 2章章 进程管理进程管理 结构型信号量一般是由两个成员组成的数据结构（亦称记录型信号量），其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个先入先出的队列，由信号量的指针项指出该队列的头，而PCB队列是通过PCB本身所包含的指针项进行链接的。最后一个PCB（即队尾）的链接指
29、针为0。第第2 2章章 进程管理进程管理 信号量的值是与相应资源的使用情况有关的。当它的值大于0时，则表示当前可用资源的数量；当它的值小于0时，则其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的PCB的个数。图2-16表示信号量的一般结构以及信号量上PCB队列的情况。第第2 2章章 进程管理进程管理 图2-16 信号量的一般结构及PCB队列 PCB1PCB20PCB3指针数值(3)信号量第第2 2章章 进程管理进程管理 2.P、V操作原语 信号量的初值可以由系统根据资源情况和使用需要来确定。在初始条件下信号量的指针项可以置为0，表示队列为空。信号量在使用过程中它的值是可变的，但仅
30、能由P、V操作来改变。设信号量为S，对S的P操作记为P（S），对它的V操作记为V（S）。以下为它们各自的含义表述。第第2 2章章 进程管理进程管理 P（S）：顺序执行下述两个动作：信号量的值减1，即S=S-1。如果S0，则该进程继续执行；第第2 2章章 进程管理进程管理 2.4.5 用P、V原语实现互斥 利用P、V原语和信号量实现进程通信是很方便的，它的使用方式基本上可分成三种：第一种用法是用于实现进入临界区的互斥，这时信号量的初值往往是1；第二种用法是用于实现进程间的简单同步，信号量初值可以是0；第三种用法是用于实现进程间的计数同步，信号量初值通常是大于0的整数。第第2 2章章 进程管理进程
31、管理 2.4.6 用P、V原语实现简单同步 考虑2.4.1节中对缓冲区的同步使用问题。供者和用者对缓冲区的使用关系如图2-17所示。第第2 2章章 进程管理进程管理 图2-17 简单供者与用者的关系 缓冲区供者000000信息(buf空)用者(buf满)磁盘第第2 2章章 进程管理进程管理 设置两个信号量：S1表示缓冲区是否空(0表示不空，1表示空)；S2表示缓冲区是否满（0表示不满，1表示满)。规定S1和S2的初值分别为1和0，则对缓冲区的供者进程和用者进程的同步关系用下述方式实现：第第2 2章章 进程管理进程管理 供者进程 用者进程 L1：P（S1）L2：启动读卡机 P(S2);收到输入结
32、束中断 从缓冲区取出信息 V(S2);V(S1);goto L1;加工并存盘 goto L2；第第2 2章章 进程管理进程管理 用P、V操作实现同步时应注意：首先应分析进程间的制约关系，确定信号量个数和相应功能。信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。同一信号量的P、V操作要“成对”出现，但它们分别在不同的进程代码中。第第2 2章章 进程管理进程管理 2.4.7 生产者消费者问题 为了使这两类进程协调工作，防止盲目的生产和消费，它们应满足如下同步条件：（1）所有生产者当前存放产品的单元数不能超过缓冲区的总容量（N）；（2）所有消费者取出产品的总量不能超过所有
33、生产者生产产品的总量。第第2 2章章 进程管理进程管理 图2-18 生产者消费者问题 N2N10123供应方向in使用方向out第第2 2章章 进程管理进程管理 为了使两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。full:表示放有产品的缓冲区数，其初值为0。empty:表示可供使用的缓冲区数，其初值为N。mutex:互斥信号量，初值为1，表示互斥进入临界区，即：保证任何时候只有一个进程使用（读或写）缓冲区，防止发生混乱。第第2 2章章 进程管理进程管理 下面是这个问题算法的描述。生产者进程Pi：while(TRUE)生产一个产品P(em
34、pty);/*申请空缓冲区*/P(mutex);/*申请进入临界区*/产品送往buffer(in);in=(in+1)mod N;/*以N为模*/V（mutex);/*离开临界区*/V(full);/*满缓冲区个数增1*/第第2 2章章 进程管理进程管理 消费者进程Cj：while(TRUE)P(full);/*申请满缓冲区*/P(mutex);/*申请进入临界区*/从buffer(out)中取出产品out=(out+1)mod N;/*以N为模*/V（mutex);/*离开临界区*/V(empty);/*空缓冲区个数增1*/对取出的产品进行处理 第第2 2章章 进程管理进程管理 在生产者消费
35、者问题中应注意：（1）在每个程序中必须先做P（mutex)、后做V(mutex)，二者要成对出现。（2）对同步信号量full和empty的P、V操作同样必须成对出现，但它们分别位于不同进程的代码中。（3）无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。第第2 2章章 进程管理进程管理 读者可针对以下情况试分析上述方案中各进程的运行过程：（1）只有生产者进程在运行，各个消费者进程未被调度运行；（2）消费者进程试图超前生产者进程运行；（3）生产者进程和消费者进程被交替调度运行。第第2 2章章 进程管理进程管理 2.5 经典进程同步问题经典进程同步问题 2.5.1 读者写者问题 读者
36、写者问题是一个著名的进程互斥访问有限资源的问题（1971年由Courtois等人解决）。该问题可以表述为：一个航班预订系统有一个大型数据库，很多竞争进程要对它进行读、写。第第2 2章章 进程管理进程管理 设置两个信号量：读互斥信号量rmutex和写互斥信号量wmutex。另外设立一个读者计数器readcount，它是一个整型变量，初值为0。rmutex:用于读者互斥地访问readcount，初值为1。wmutex:用于控制对数据库的访问，保证一个写者与其他读者或写者互斥地访问共享资源，初值为1。第第2 2章章 进程管理进程管理 读者Ri：while(TRUE)P(rmutex);readcou
37、nt=readcount+1;if(readcount=1)P(wmutex);V(rmutex);执行读操作P(rmutex);readcount=readcount-1;if(readcount=0)V(wmutex);第第2 2章章 进程管理进程管理 V(rmutex);使用读取的数据 写者Wj：while(TRUE)准备更新数据P(wmutex);执行写操作V(wmutex);第第2 2章章 进程管理进程管理 2.5.2 哲学家进餐问题 Dijkstra在1965年提出并解决了名为哲学家进餐问题(The Dining Philosophers Problem)的同步问题。如图2-19所
38、示。简单的解决方案是，用一个信号量表示一根筷子，五个信号量构成信号量数组chopstick5，所有信号量初值为1。第i个哲学家的进餐过程可描述为：第第2 2章章 进程管理进程管理 while(TRUE)思考问题P(chopsticki);P(chopstick(i+1)mod5);进餐V(chopsticki);V(chopstick(i+1)mod 5);第第2 2章章 进程管理进程管理 图2-19 哲学家进餐问题 第第2 2章章 进程管理进程管理#define N 5 /*哲学家数目*/#define LEFT(i-1)%N/*i的左邻号码*/#define RIGHT（i+1）%N/*i
39、的右邻号码*/#define THINKING 0/*哲学家正在思考*/#define HUNGRY 1/*哲学家感到饿，想拿筷子*/#define EATING 2/*哲学家吃饭*/typedef int semaphore;/*定义信号量为特殊int量*/int stateN;/*记录每个人状态的数组*/semaphore mutex=1;/*互斥进入临界区*/第第2 2章章 进程管理进程管理 semaphore sN;/*每位哲学家一个信号量*/void philosopher(int i)/*参数i为哲学家号码*/while(TRUE)think();/*哲学家在思考问题*/take_
40、chopstick(i);/*拿到两根筷子或者阻塞*/eat();/*进餐*/put_chopstick(i);/*把筷子放回原处*/第第2 2章章 进程管理进程管理 void take_chopstick(int i)P(mutex);/*进入临界区*/statei=HUNGRY;/*第i位哲学家感到饥饿*/test(i);/*试图拿取两根筷子*/V(mutex);/*退出临界区*/P(si)；/*如果拿不到筷子就阻塞*/void put_chopstick(int i)P(mutex);/*进入临界区*/第第2 2章章 进程管理进程管理 statei=THINKING;/*进餐结束哲学家思
41、考*/test(LEFT);/*查看左邻现在能否进餐*/test(RIGHT);/*查看右邻现在能否进餐*/V(mutex);/*退出临界区*/void test(int i)/*第i位哲学家感到饥饿，且左右邻都不在进餐*/第第2 2章章 进程管理进程管理 if(statei=HUNGRY&stateLEFT!=EATING&stateRIGHT!=EATING)statei=EATING;/*第i位哲学家进餐*/V(si);/*释放第i位哲学家*/第第2 2章章 进程管理进程管理 2.5.3 困睡的理发师问题 理发师打盹问题。理发店有一名理发师、一个理发椅和几个坐椅，等待理发的顾客可坐在上面
42、。如果没有顾客到来，理发师坐在理发椅上打盹。当顾客到来，他唤醒理发师。如果顾客到来时理发师正在理发，则该顾客坐在椅子上排队；如果满座了，他就离开这个理发店到别处去理发。为理发师和顾客各编写一段程序来描述他们的行为，要求不能带有竞争条件。第第2 2章章 进程管理进程管理 设置三个信号量和一个计数变量：信号量customers用来记录等待理发的顾客数（不包括正在理发的顾客）；barbers用来记录正在等候顾客的理发师数，为0或1；mutex用于表示互斥。计数变量waiting也用于记录等候的顾客数，它实际上是customers的一份拷贝。在程序中，进入理发店的顾客必须先看坐椅上有无空位，如果有空位
43、，他就留下来等；否则他就离开。由于无法直接读取信号量customers的当前值（信号量只能由P、V进行操作），因此必须另设一个变量来记录等候的顾客数。第第2 2章章 进程管理进程管理 理发师问题的一种解法如下：#define CHAIRS 5 /*为等待理发的顾客准备的坐椅数*/typedef int semaphore;semaphore cutomers=0;/*等候服务的顾客数*/semaphore barbers=0;/*等候顾客的理发师数*/semaphore mutex=1;/*用于互斥*/int waiting=0;/*等候理发的顾客数*/void barber(void)第第2
44、 2章章 进程管理进程管理 while(TRUE)P(customers);/*若无等候的顾客，则睡觉*/P（mutex）;/*要求进程等候*/waiting=waiting-1;/*等候顾客数减1*/V(barbers);/*一个理发师现在开始理发了*/V(mutex);/*释放等候*/cut_hair();/*理发（非临界区操作）*/void customer(void)第第2 2章章 进程管理进程管理 P(mutex);/*进入临界区*/if(waitingCHAIRS)/*如果有空坐椅，则等待*/waiting=waiting+1;/*等候顾客数加1*/V(customers);/*如
45、果理发师在睡觉，则唤醒他*/V(mutex);/*释放访问等候*/P(barbers);/*如果理发师正忙，则等候*/get_haircut();/*坐在理发椅上等候服务*/else V(mutex);/*店里人满了，离开*/第第2 2章章 进程管理进程管理 2.6 管管 程程 一个管程由四部分组成，它们是管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句。图2-20示出了管程的结构，它定义了一种共享数据结构。第第2 2章章 进程管理进程管理 图2-20 管程的结构 操作共享数据初始化代码进入队列第第2 2章章 进程管理进程管理 管程是一个程序设计语言的概
46、念，必须得到编译程序的支持。编译程序必须能识别管程，并用某种方式实现互斥访问。管程构造已由多种语言实现，如并发Pascal、Pascal+、Modula-2和Modula-3等。最近它已作为程序库实现。第第2 2章章 进程管理进程管理 管程具有以下三个特性：（1）管程内部的数据是局部变量，只能被管程内部定义的过程所访问，在管程外面声明过的过程不能直接访问它们。（2）进程要想进入管程，必须调用管程内的某个过程。（3）一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。第第2 2章章 进程管理进程管理 图2-21 带条件变量的管程 条件队列XYNext操作共享数据
47、初始化代码进入队列第第2 2章章 进程管理进程管理 设进程P1调用signal(x)操作，有一个被挂起的进程Q与条件x有关。显然，若被挂起的进程Q被允许恢复执行，则发信号的进程P1一定要等待。否则，P1和Q都将在管程内同时活动。（当然，从概念上讲，这些进程都可以执行。）下面是一个用管程解决生产者消费者问题的解法（用类Pascal语言）。第第2 2章章 进程管理进程管理 monitor ProducerConsumer condition full,empty;integer count;procedure insert(item:integer);begin if count=N then w
48、ait (full);insert_item(item);/*加入一项*/count:=count+1;if count=1 then signal (empty)end;第第2 2章章 进程管理进程管理 function remove:integer;begin if count=0 then wait (empty);remove=remove_item;/*移走一项*/count:=count-1;if count=N-1 then signal (full)end;count:=0;end monitor;procedure producer;第第2 2章章 进程管理进程管理 begi
49、n while true do begin item=produce_item;/*生产一项*/ProducerConsumer.insert(item)end end;procedure consumer;begin while true do 第第2 2章章 进程管理进程管理 begin item=ProducerConsumer.remove;consume_item(item)/*消费一项*/end end ;第第2 2章章 进程管理进程管理 2.7 进进 程程 通通 信信 1.共享存储器方式 共享存储器方式是在内存中分配一片空间作为共享存储区。需要进行通信的各个进程把共享存储区附加到
50、自己的地址空间中，然后就像正常操作一样对共享区中的数据进程读或写。第第2 2章章 进程管理进程管理 2.管道文件 管道文件也称为管道线，它是连接两个命令的个打开文件。一个命令向该文件中写入数据，称为写者；另一个命令从该文件中读出数据，称为读者。例如在UNIX/Linux系统中，下述命令行就实现两个命令间的通信：ls-lwc-l第第2 2章章 进程管理进程管理 3.消息传递方式 消息传递方式以消息(Message)为单位在进程间进行数据交换。它有两种实现方式：(1)直接通信方式。发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。(2)间接通信方式。发送进程将消息送
