操作系统教程Linux实例分析孟庆昌第2章进程.ppt

《操作系统教程Linux实例分析孟庆昌第2章进程.ppt》由会员分享，可在线阅读，更多相关《操作系统教程Linux实例分析孟庆昌第2章进程.ppt（167页珍藏版）》请在三一办公上搜索。

1、第2章 进程管理,2.1 进程概念 2.2 线程 2.3 进程管理 2.4 进程间通信 2.5 经典进程同步问题 2.6 管程 2.7 进程通信 2.8 Linux进程管理 习题,2.1 进 程 概 念,2.1.1 程序的顺序执行 顺序程序活动有三个主要特点：(1)程序所规定的动作在机器上严格地按顺序执行。(2)只有程序本身的动作才能改变程序的运行环境。(3)程序的执行结果与程序运行的速度无关。,图2-1列出了几个典型的顺序程序的示意图。其中图(a)最简单，一条条指令顺次做下去；图(b）表示程序代码中出现循环的情况；图(c)表示A程序在执行过程中调用B程序，B运行完，返回A，继续执行A的情况。

2、,图2-1 顺序程序示意图,2.1.2 程序的并发执行和资源共享 多道程序 设计是指两个或更多个程序同时在系统中存在并且运行。这时的工作环境与单道程序（仅一个）的运行条件相比，大不相同。首先，每个用户程序都需要一定的资源，如内存、设备、CPU时间等，因此系统中的软、硬件资源不再是单个程序独占，而是由几道程序所共享。这样，共享资源的状态就由多道程序的活动共同决定，从而打破了单道程序“闭关自守”的局面。,图2-2 非多道技术下作业执行过程,采用多道程序技术来执行同样的作业A和B，就能大大改进系统性能，如图2-3所示。作业A先运行，它运行一秒后等待输入，此时让B运行；B运行一秒后等待输入，此时恰好A

3、输入完，可以运行了就这样在CPU上交替地运行A和B。在这种理想的情况下，CPU不空转，其使用率升至百分之百，并且吞吐量也随之增加了。,图2-3 多道技术下作业执行过程,2.1.3 程序并发执行的特性 资源共享和程序的并发执行使得系统的工作情况变得非常复杂，带来一系列新的问题，特别表现在各种程序活动的相互依赖和制约关系方面。我们分析一下图2-4中几个程序并发执行的情况。,图2-4 并发程序的执行(a)并发执行的程序；(b)并发程序的关系；(c)有制约关系的并发程序,通过上述三个例子的分析，可以得出并发程序的三个主要特征：（1)没有封闭性。有共享公共变量时，其执行结果不可再现，就是说，结果与相关的

4、并发程序的相对速度有关。(2)程序与计算不再一一对应。“程序”是指令的有序集合，是“静态”的概念。（3)并发程序在执行期间可以互相制约。,2.1.4 进程概念的引入和描述“进程”是操作系统的最基本、最重要的概念之一。引进这个概念对于理解、描述和设计操作系统都具有极其重要的意义。但是迄今为止，对这个概念还没有形成统一的定义，都是从不同的角度来描述它的各个基本特征。下面列举出比较能反映进程实质的几种定义：,(1)进程(或任务)是可以和别的计算并发执行的计算。(2)进程是程序的一次执行，是在给定内存区域中的一组指令序列的执行过程。(3)所谓进程，简单说来就是一个程序在给定活动空间和初始条件下，在一个

5、处理机上的执行过程。(4)进程可定义为一个数据结构和能在其上进行操作的一个程序。(5)进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。,进程和程序是两个不同的概念，但又有密切的联系。它们之间的主要区别是：(1)程序是静态概念，本身可以作为一种软件资源长期保存着；而进程则是程序的一次执行过程，它是动态概念，有一定的生命期，是动态地产生和消亡的。,(2)进程是一个能独立运行的单位，能与其他进程并发执行，进程是作为资源申请和调度单位存在的；而通常的程序段是不能作为一个独立运行的单位的。(3)程序和进程无一一对应关系。一个程序可由多个进程共用；另一方面，一个进程在其活动

6、中又可顺序地执行若干个程序。,(4)各个进程在并发执行过程中会产生相互制约关系，造成各自前进速度的不可预测性。而程序本身是静态的，不存在这种异步特征。表2-1列出了进程和程序之间的主要区别。,表2-1 进程和程序的对比,2.1.5 进程的状态及其变迁 进程是一个程序的执行过程，有着走走停停的活动规律。进程的动态性质是由其状态变化决定的。如果一个事物始终处于一种状态，那么它就不再是活动的，就没有生命力了。通常在操作系统中，进程至少要有三种基本状态，这些状态是处理机挑选进程运行的主要因素，所以又称之为进程控制状态。这三种基本状态是：运行态、就绪态和阻塞态（或等待态）。如图2-5所示。,图2-5 进

7、程状态及其变化,在很多操作系统中，又添加了两种基本状态：创建态和终止态。创建态是指新进程正被创建时的状态，当创建工作完成后它就进入到就绪态。终止态是指进程正常或非正常终止时所处的状态，它的必然结局是从系统中消失。上述五种进程状态及其变迁情况如图2-6所示。,图2-6 进程的五种基本状态,2.1.6 进程的组成 进程的活动是通过在CPU上执行一系列程序和对相应数据进行操作来体现的，因此程序和它操作的数据是进程存在的实体。但这二者仅是静态的文本，没有反映出其动态特性。为此，还需要有一个数据结构，用来描述进程当前的状态、本身的特性等。这种数据结构被称为进程控制块（PCB，Process Contro

8、l Block)。,程序往往由一系列函数组成。执行函数调用时要保存好调用者的现场信息，以便被调函数完成后能恢复调用者的运行环境。这一系列现场信息要保存在堆栈中，按“后进先出”方式管理。为此，系统要为每个进程设立一个或多个栈。所以进程通常都由程序、栈、数据集合和PCB这四部分组成。图2-7示出进程的物理结构。,图2-7 进程组成,2.1.7 进程控制块 进程控制块有时也称为进程描述块（Process Descriptor），它是进程映像中最关键的部分，其中含有进程的描述信息和控制信息，是进程动态特性的集中反映，它是系统对进程施行识别和控制的依据。在不同的系统中，PCB的具体组成成分是不同的，在简

9、单操作系统中它较小；而在大型操作系统中它很复杂，设有很多信息项。一般来说，进程控制块应包括如下内容，如图2-8所示。,图2-8 PCB构成,（1）进程名。它是惟一标志对应进程的一个标志符或数字。(2)特征信息。它包括是系统进程还是用户进程，进程映像是否常驻内存等。(3)进程状态信息。它表明该进程的执行状态，是运行态、就绪态还是阻塞态。(4)调度优先权。这表示进程获取CPU的优先级别。,(5)通信信息。它反映该进程与哪些进程有什么样的通信关系，如等待哪个进程的信号等。(6)现场保护区。当对应进程由于某个原因放弃使用CPU时，需要把它的一部分与运行环境有关的信息保存起来，以便在重新获得CPU后能恢

10、复正常运行。,(7)资源需求、分配和控制方面的信息。如进程所需要或占有的IO设备、磁盘空间、数据区等。(8)进程映像信息。指出该进程的程序和数据的存储情况，在内存或外存的地址、大小等。(9)族系关系。它反映父子进程的隶属关系。(10)其他信息。如文件信息、工作单元等。,2.1.8 PCB的组织方式 1.线性表方式 如图2-9所示，线性表的方式简单，最容易实现。操作系统预先确定整个系统中同时存在的进程最大数目，比如是n，静态分配空间，把所有的PCB都放在这个表中。,图2-9 PCB线性表,2.链接表方式 链接表方式是经常采用的方式。其原理是：按照进程的不同状态分别放在不同的队列中，如图2-10所

11、示。,图2-10 PCB链接表,3.索引表方式 索引表方式是利用索引表记载各种状态进程的PCB地址，如就绪索引表中的表项指向就绪进程PCB的指针，而阻塞表中的表项指向阻塞进程PCB的指针。各索引表的起始地址放在专用的指针单元中，运行进程的PCB由一个专用的运行指针指向。图2-11示出PCB索引表方式。,图2-11 PCB索引表,2.2 线 程,2.2.1 线程概念 1.线程 线程 是进程中执行运算的最小单位，亦即执行处理机调度的基本单位。如果把进程理解为在逻辑上操作系统所完成的任务，那么线程表示完成该任务的许多可能的子任务之一。,2.Thread结构 每个线程有一个Thread结构，用于保存与

12、线程有关的信息，主要由以下几个基本部分组成：(1)一个惟一的线程标识符。（2）描述处理器状态的一组状态寄存器的内容，用于调度。（3）每个Thread结构有两个堆栈指针：一个指向核心堆栈，一个指向用户堆栈。（4）一个私有存储区，存放现场保护信息及其他各种统计信息等。,图2-12 Thread结构,3.带线程的进程模型 一个进程可以包含一个或者多个线程，但至少要有一个线程。在传统的进程中就只有一个线程。当一个进程包含多个线程时，各线程除自己有少量私有资源（如程序计数器、寄存器和堆栈）外，要共享所属进程的全部资源（如程序代码、数据和文件等）。图2-13示出单线程和多线程的进程模型。,图2-13 单线

13、程式和多线程式的进程,4.进程与线程的关系 从以上介绍中可以看出，进程和它的线程有如下关系：（1）一个进程可以有多个线程，但至少要有一个线程。（2）进程是资源的拥有者，是分配资源的独立单位；而线程一般不拥有系统资源（仅有一点必不可少的资源），同一进程的所有线程共享该进程的全部资源。（3）在支持线程的操作系统中，线程是调度和分派的基本单位。,（4）进程可以并发执行。（5）线程在执行过程中往往需要协作同步。（6）在实施创建、撤消和切换等操作时，进程的开销远大于线程的开销。（7）线程和进程一样，都是动态实体，具有不同的状态，如运行态、就绪态、阻塞态和终止态等。,2.2.2 线程的实现方式 1.用户级

14、线程 在这种方式下，整个管理线程的线程库放在用户空间，对线程从创建到撤消的全部管理工作都由应用程序完成。核心对线程一无所知，只对常规进程实施管理。图2-14(a)示出用户级线程的实现方式。,图2-14 线程的实现方式,用户级线程实现方式具有以下三个优点：（1）线程切换速度快。（2）调度算法可以是应用程序专用的，不仅最适合自己的需求，而且不干扰底层操作系统的进程调度。（3）用户级线程可运行在任何操作系统上，包括不支持线程机制的操作系统。,用户级线程方式也存在两个主要缺点：（1）系统调用的阻塞问题。当一个线程执行系统调用时，不仅它自己被阻塞，而且在同一进程内的所 有线程都将被阻塞。（2）这种方式下

15、的多线程应用程序不具有多处理的优点。因为核心只为每个进程一次分配一台处理机。,2.核心级线程 在这种方式下，核心知道线程的存在，并对它们实施管理。如图2-14(b)所示。在核心空间中不仅有一个进程表，而且有一个线程表，其中记载系统中所有线程的情况。这样，就由核心统一管理系统中所有的线程。核心进行调度时以线程为基本单位。,核心级线程的优点是：（1）在多处理器系统中，核心可以同时调度同一进程的多个线程，真正实现并行操作。（2）一个进程的某个线程阻塞了，核心可以调度同一进程的另一个线程运行。核心级线程方式也存在缺点，主要是：（1）线程切换速度慢，控制转移开销大。（2）调度算法由核心确定，应用进程无法

16、影响线程的切换。,2.3 进 程 管 理,2.3.1 创建进程 1.进程图(Process Graph)与多数操作系统对进程的管理相似，UNIX系统中各个进程构成了树型的进程族系，如图2-15所示。,图2-15 各个进程构成了树型的进程族系,2.进程创建过程 父进程利用系统调用（如UNIX/Linux系统中的fork）来创建子进程，其主要过程如下：（1）申请一个空闲的PCB。（2）为新进程分配资源。（3）将新进程的PCB初始化。（4）将新进程加到就绪队列中。,2.3.2 终止进程 终止进程的主要操作过程是：(1)从系统的PCB表中找到指定进程的PCB。(2)回收该进程所占用的全部资源。(3)若

17、该进程还有子孙进程，则还要终止其所有子孙进程，回收它们所占用的全部资源。(4)释放被终止进程的PCB，并从原来队列中摘走。,2.3.3 更换进程映像 改变进程映像的工作很复杂，其主要过程是：（1）释放子进程原来的程序和数据所占用的内存空间；（2）从磁盘上找出子进程所要执行的程序和数据（通常以可执行文件的形式存放）；（3）分配内存空间，装入新的程序和数据；（4）为子进程建立初始的运行环境主要是对各个寄存器初始化，返回到用户态，运行该进程的程序。,2.3.4 阻塞进程 进程阻塞的过程如下：（1）立即停止当前进程的执行；（2）将现行进程的CPU现场送到该进程的PCB现场保护区中保存起来，以便将来重新

18、运行时恢复此时的现场；,（3）把该进程PCB中的现行状态由“运行”改为“阻塞”，把它插入到具有相同事件的阻塞队列中；（4）然后转到进程调度程序，重新从就绪队列中挑选一个合适的进程投入运行。,2.3.5 唤醒进程 唤醒原语执行过程是：（1）首先把被阻塞进程从相应的阻塞队列中摘下；（2）将现行状态改为就绪态，然后把该进程插入到就绪队列中；（3）如果被唤醒进程比运行进程有更高的优先级，则设置重新调度标志。,2.4 进 程 间 通 信,2.4.1 进程间的关系 1.同步 同步是进程间共同完成一项任务时直接发生相互作用的关系，也就是说，这些具有伙伴关系的进程在执行的时间次序上必须遵循确定的规律。,2.互

19、斥 协同工作的进程之间存在同步关系，但是进程之间更一般的关系是互斥关系，这是由于诸进程共享某些资源而引起的。3.通信 进程经常需要与其他进程通信。,2.4.2 竞争条件和临界区 1.竞争条件 在有些操作系统中，并发进程在活动过程中可能共享一些彼此都能够读写的公用存储区。它可能在内存中，也可能是一个共享文件，其所在位置并不影响问题的实质。下面我们考虑两个进程对一个系统打印机分配表的操作情况。,假定进程Pa负责为用户进程分配打印机，进程Pb负责释放打印机。由于分配和释放可能同时发生，因此两个进程必须共享一个打印机分配表，如表2-2所示。,表2-2 打印机分配表,Pa进程分配打印机的过程是：(1)逐

20、项检查分配标志，找出标志为0的打印机号码；（2）把该机的分配标志置1；（3）把用户名和设备名填入分配表中相应位置。,Pb进程释放打印机的过程是：（1）逐项检查分配表的各项信息，找出标志为1并且用户名和设备名与被释放的名字相同的机号；（2）该机标志清0；（3）清除该机用户名和设备名。,表2-3 打印机分配表（出错情况）,2.临界区 为了使临界资源得到合理使用，就必须禁止两个或两个以上的进程同时进入临界区内，就是说欲进入临界区的若干个进程要满足如下关系：（1）如果有若干进程要求进入临界区，一次仅允许一个进程进入。,（2）任何时候，处于临界区内的进程不可多于一个。（3）进入临界区的进程要在有限时间内

21、退出，以便其他进程能及时进入自己的临界区。（4）如果进程不能进入自己的临界区，则应让出CPU，避免进程出现“忙等”现象。,2.4.3 用锁操作原语实现互斥 进程通信是实现进程间同步与互斥的一种机制。这类似于人类社会生活中为表达意见、交流思想、交换信息等而采用多种通信方式，例如，人们打手势、交谈、打电话、写信、发E-mail等，方式有简有繁，当然其功能也有强弱之别。下面分别介绍典型的实现进程同步与互斥的手段。,为解决进程互斥进入临界区的问题，可为每类临界资源设置一把锁，该锁有打开和关闭两种状态。进程执行临界区程序的操作按下列步骤进行：(1)关锁。先检查锁的状态，如为关闭状态，则等待其打开；如已打

22、开了，则将其关闭，继续执行（2)的操作。（2)执行临界区程序。(3)开锁。将锁打开，退出临界区。,2.4.4 信号量上的P、V操作原语 1.信号量（Semaphore）信号量及信号量上的P操作和V操作是E.W.Dijkstra在1965年提出的一种解决同步、互斥问题的更通用的方法，并在THE操作系统中得以实现。,结构型信号量一般是由两个成员组成的数据结构（亦称记录型信号量），其中一个成员是整型变量，表示该信号量的值；另一个是指向PCB的指针。当多个进程都等待同一信号量时，它们就排成一个先入先出的队列，由信号量的指针项指出该队列的头，而PCB队列是通过PCB本身所包含的指针项进行链接的。最后一个

23、PCB（即队尾）的链接指针为0。,信号量的值是与相应资源的使用情况有关的。当它的值大于0时，则表示当前可用资源的数量；当它的值小于0时，则其绝对值表示等待使用该资源的进程个数，即在该信号量队列上排队的PCB的个数。图2-16表示信号量的一般结构以及信号量上PCB队列的情况。,图2-16 信号量的一般结构及PCB队列,2.P、V操作原语 信号量的初值可以由系统根据资源情况和使用需要来确定。在初始条件下信号量的指针项可以置为0，表示队列为空。信号量在使用过程中它的值是可变的，但仅能由P、V操作来改变。设信号量为S，对S的P操作记为P（S），对它的V操作记为V（S）。以下为它们各自的含义表述。,P（

24、S）：顺序执行下述两个动作：信号量的值减1，即S=S-1。如果S0，则该进程继续执行；,2.4.5 用P、V原语实现互斥 利用P、V原语和信号量实现进程通信是很方便的，它的使用方式基本上可分成三种：第一种用法是用于实现进入临界区的互斥，这时信号量的初值往往是1；第二种用法是用于实现进程间的简单同步，信号量初值可以是0；第三种用法是用于实现进程间的计数同步，信号量初值通常是大于0的整数。,2.4.6 用P、V原语实现简单同步 考虑2.4.1节中对缓冲区的同步使用问题。供者和用者对缓冲区的使用关系如图2-17所示。,图2-17 简单供者与用者的关系,设置两个信号量：S1表示缓冲区是否空(0表示不空

25、，1表示空)；S2表示缓冲区是否满（0表示不满，1表示满)。规定S1和S2的初值分别为1和0，则对缓冲区的供者进程和用者进程的同步关系用下述方式实现：,供者进程 用者进程 L1：P（S1）L2：启动读卡机 P(S2);收到输入结束中断 从缓冲区取出信息 V(S2);V(S1);goto L1;加工并存盘 goto L2；,用P、V操作实现同步时应注意：首先应分析进程间的制约关系，确定信号量个数和相应功能。信号量的初值与相应资源的数量有关，也与P、V操作在程序代码中出现的位置有关。同一信号量的P、V操作要“成对”出现，但它们分别在不同的进程代码中。,2.4.7 生产者消费者问题 为了使这两类进程

26、协调工作，防止盲目的生产和消费，它们应满足如下同步条件：（1）所有生产者当前存放产品的单元数不能超过缓冲区的总容量（N）；（2）所有消费者取出产品的总量不能超过所有生产者生产产品的总量。,图2-18 生产者消费者问题,为了使两类进程实行同步操作，应设置三个信号量：两个计数信号量full和empty，一个互斥信号量mutex。full:表示放有产品的缓冲区数，其初值为0。empty:表示可供使用的缓冲区数，其初值为N。mutex:互斥信号量，初值为1，表示互斥进入临界区，即：保证任何时候只有一个进程使用（读或写）缓冲区，防止发生混乱。,下面是这个问题算法的描述。生产者进程Pi：while(TRU

27、E)生产一个产品P(empty);/*申请空缓冲区*/P(mutex);/*申请进入临界区*/产品送往buffer(in);in=(in+1)mod N;/*以N为模*/V（mutex);/*离开临界区*/V(full);/*满缓冲区个数增1*/,消费者进程Cj：while(TRUE)P(full);/*申请满缓冲区*/P(mutex);/*申请进入临界区*/从buffer(out)中取出产品out=(out+1)mod N;/*以N为模*/V（mutex);/*离开临界区*/V(empty);/*空缓冲区个数增1*/对取出的产品进行处理,在生产者消费者问题中应注意：（1）在每个程序中必须先做

28、P（mutex)、后做V(mutex)，二者要成对出现。（2）对同步信号量full和empty的P、V操作同样必须成对出现，但它们分别位于不同进程的代码中。（3）无论在生产者进程中还是在消费者进程中，两个P操作的次序不能颠倒。,读者可针对以下情况试分析上述方案中各进程的运行过程：（1）只有生产者进程在运行，各个消费者进程未被调度运行；（2）消费者进程试图超前生产者进程运行；（3）生产者进程和消费者进程被交替调度运行。,2.5 经典进程同步问题,2.5.1 读者写者问题 读者写者问题是一个著名的进程互斥访问有限资源的问题（1971年由Courtois等人解决）。该问题可以表述为：一个航班预订系统

29、有一个大型数据库，很多竞争进程要对它进行读、写。,设置两个信号量：读互斥信号量rmutex和写互斥信号量wmutex。另外设立一个读者计数器readcount，它是一个整型变量，初值为0。rmutex:用于读者互斥地访问readcount，初值为1。wmutex:用于控制对数据库的访问，保证一个写者与其他读者或写者互斥地访问共享资源，初值为1。,读者Ri：while(TRUE)P(rmutex);readcount=readcount+1;if(readcount=1)P(wmutex);V(rmutex);执行读操作P(rmutex);readcount=readcount-1;if(rea

30、dcount=0)V(wmutex);,V(rmutex);使用读取的数据 写者Wj：while(TRUE)准备更新数据P(wmutex);执行写操作V(wmutex);,2.5.2 哲学家进餐问题 Dijkstra在1965年提出并解决了名为哲学家进餐问题(The Dining Philosophers Problem)的同步问题。如图2-19所示。简单的解决方案是，用一个信号量表示一根筷子，五个信号量构成信号量数组chopstick5，所有信号量初值为1。第i个哲学家的进餐过程可描述为：,while(TRUE)思考问题P(chopsticki);P(chopstick(i+1)mod5);

31、进餐V(chopsticki);V(chopstick(i+1)mod 5);,图2-19 哲学家进餐问题,#define N 5/*哲学家数目*/#define LEFT(i-1)%N/*i的左邻号码*/#define RIGHT（i+1）%N/*i的右邻号码*/#define THINKING 0/*哲学家正在思考*/#define HUNGRY 1/*哲学家感到饿，想拿筷子*/#define EATING 2/*哲学家吃饭*/typedef int semaphore;/*定义信号量为特殊int量*/int stateN;/*记录每个人状态的数组*/semaphore mutex=1;/

32、*互斥进入临界区*/,semaphore sN;/*每位哲学家一个信号量*/void philosopher(int i)/*参数i为哲学家号码*/while(TRUE)think();/*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者阻塞*/eat();/*进餐*/put_chopstick(i);/*把筷子放回原处*/,void take_chopstick(int i)P(mutex);/*进入临界区*/statei=HUNGRY;/*第i位哲学家感到饥饿*/test(i);/*试图拿取两根筷子*/V(mutex);/*退出临界区*/P(si)；/*如果拿不

33、到筷子就阻塞*/void put_chopstick(int i)P(mutex);/*进入临界区*/,statei=THINKING;/*进餐结束哲学家思考*/test(LEFT);/*查看左邻现在能否进餐*/test(RIGHT);/*查看右邻现在能否进餐*/V(mutex);/*退出临界区*/void test(int i)/*第i位哲学家感到饥饿，且左右邻都不在进餐*/,if(statei=HUNGRY/*释放第i位哲学家*/,2.5.3 困睡的理发师问题 理发师打盹问题。理发店有一名理发师、一个理发椅和几个坐椅，等待理发的顾客可坐在上面。如果没有顾客到来，理发师坐在理发椅上打盹。当顾

34、客到来，他唤醒理发师。如果顾客到来时理发师正在理发，则该顾客坐在椅子上排队；如果满座了，他就离开这个理发店到别处去理发。为理发师和顾客各编写一段程序来描述他们的行为，要求不能带有竞争条件。,设置三个信号量和一个计数变量：信号量customers用来记录等待理发的顾客数（不包括正在理发的顾客）；barbers用来记录正在等候顾客的理发师数，为0或1；mutex用于表示互斥。计数变量waiting也用于记录等候的顾客数，它实际上是customers的一份拷贝。在程序中，进入理发店的顾客必须先看坐椅上有无空位，如果有空位，他就留下来等；否则他就离开。由于无法直接读取信号量customers的当前值（

35、信号量只能由P、V进行操作），因此必须另设一个变量来记录等候的顾客数。,理发师问题的一种解法如下：#define CHAIRS 5/*为等待理发的顾客准备的坐椅数*/typedef int semaphore;semaphore cutomers=0;/*等候服务的顾客数*/semaphore barbers=0;/*等候顾客的理发师数*/semaphore mutex=1;/*用于互斥*/int waiting=0;/*等候理发的顾客数*/void barber(void),while(TRUE)P(customers);/*若无等候的顾客，则睡觉*/P（mutex）;/*要求进程等候*/w

36、aiting=waiting-1;/*等候顾客数减1*/V(barbers);/*一个理发师现在开始理发了*/V(mutex);/*释放等候*/cut_hair();/*理发（非临界区操作）*/void customer(void),P(mutex);/*进入临界区*/if(waitingCHAIRS)/*如果有空坐椅，则等待*/waiting=waiting+1;/*等候顾客数加1*/V(customers);/*如果理发师在睡觉，则唤醒他*/V(mutex);/*释放访问等候*/P(barbers);/*如果理发师正忙，则等候*/get_haircut();/*坐在理发椅上等候服务*/el

37、se V(mutex);/*店里人满了，离开*/,2.6 管 程,一个管程由四部分组成，它们是管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句。图2-20示出了管程的结构，它定义了一种共享数据结构。,图2-20 管程的结构,管程是一个程序设计语言的概念，必须得到编译程序的支持。编译程序必须能识别管程，并用某种方式实现互斥访问。管程构造已由多种语言实现，如并发Pascal、Pascal+、Modula-2和Modula-3等。最近它已作为程序库实现。,管程具有以下三个特性：（1）管程内部的数据是局部变量，只能被管程内部定义的过程所访问，在管程外面声明过的过

38、程不能直接访问它们。（2）进程要想进入管程，必须调用管程内的某个过程。（3）一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。,图2-21 带条件变量的管程,设进程P1调用signal(x)操作，有一个被挂起的进程Q与条件x有关。显然，若被挂起的进程Q被允许恢复执行，则发信号的进程P1一定要等待。否则，P1和Q都将在管程内同时活动。（当然，从概念上讲，这些进程都可以执行。）下面是一个用管程解决生产者消费者问题的解法（用类Pascal语言）。,monitor ProducerConsumer condition full,empty;integer count

39、;procedure insert(item:integer);begin if count=N then wait(full);insert_item(item);/*加入一项*/count:=count+1;if count=1 then signal(empty)end;,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;proce

40、dure producer;,begin while true do begin item=produce_item;/*生产一项*/ProducerConsumer.insert(item)end end;procedure consumer;begin while true do,begin item=ProducerConsumer.remove;consume_item(item)/*消费一项*/end end;,2.7 进 程 通 信,1.共享存储器方式 共享存储器方式是在内存中分配一片空间作为共享存储区。需要进行通信的各个进程把共享存储区附加到自己的地址空间中，然后就像正常操作一样

41、对共享区中的数据进程读或写。,2.管道文件 管道文件也称为管道线，它是连接两个命令的个打开文件。一个命令向该文件中写入数据，称为写者；另一个命令从该文件中读出数据，称为读者。例如在UNIX/Linux系统中，下述命令行就实现两个命令间的通信：ls-lwc-l,3.消息传递方式 消息传递方式以消息(Message)为单位在进程间进行数据交换。它有两种实现方式：(1)直接通信方式。发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。(2)间接通信方式。发送进程将消息送到被称为信箱的中间设施中，接收进程从信箱中取得消息。这种通信方式也称为信箱通信方式。,2.7.1 消息

42、缓冲通信 消息缓冲区一般包含下列几种信息：name：发送消息的进程名或标志号。size：消息长度。text：消息正文。next：下个缓冲区的地址。,在采用消息通信机构的系统中，进程PCB中一般包含有下列项目：mutex：消息队列操作互斥信号量。消息队列是临界资源，不允许两个或两个以上进程对它同时进行访问。Sm：表示接收消息计数和同步的信号量，用于接收消息进程与发送消息进程进行同步，其值表示消息队列中的消息数目。Pm：指向该进程的消息队列中第一个缓冲区的指针。接收消息进程的PCB和它的消息缓冲链的关系如图2-22所示。,图2-22 PCB与消息缓冲链,两个进程进行消息传送的过程如图2-23所示，

43、发送进程在发送消息之前，先要在自己的内存空间设置一发送区，把准备发送的消息正文以及接收消息的进程名(或标志号)和消息长度填入其中，完成上述准备工作之后，调用发送消息的程序send(addr)，其中参数addr是消息发送的起始地址。send程序的流程如图2-24所示，图中mutex是接收进程PCB中的互斥信号量，Sm是接收进程PCB中的同步信号量。,图2-23 消息发送与接收,图2-24 send程序流程图,图2-25 receive程序流程图,2.7.2 信箱通信 信箱是实现进程通信的中间实体，可以存放一定数量的消息。发送进程将消息送入信箱，接收进程从信箱中取出发给自己的消息。这有点类似于我们

44、日常使用信箱的情况。信箱是一种数据结构，在逻辑上可分为两个部分：信箱头包括信箱名字、信箱属性(公用、私用或者共享)、信箱格状态等；信箱体用来存放消息的多个信箱格。,当进程之间要通信时，它们必须有共享信箱。发送和接收消息的原语形式为：1)send(mailbox，message)其中，mailbox为信箱，message是要发送的消息。2)receive(mailbox，message)接收进程要接收一个消息时，先判断信箱状态是否为满。,信箱可分为三类：(1)公用信箱：它由操作系统创建，系统中所有核准进程都可使用它既可把消息放在该信箱中，又可从中取出发给自己的消息。（2）共享信箱：它由某个进程创

45、建，对它要指明共享属性以及共享进程的名字。（3）私有信箱：用户进程为自己创建的信箱。,2.8 Linux进程管理,2.8.1 进程和线程的概念 1.进程及其状态 简单来说，进程就是程序的一次执行过程。在Linux系统中，“进程”和“任务”是同一个意思。所以，在内核的代码中这两个词常常混用。,在Linux系统中，进程有下述五种状态。（1）可运行态（TASK_RUNNING）：进程处于就绪状态，可以被调度运行。（2）“可中断”睡眠态（TASK_INTERRUPTIBLE）:进程处于“浅度”睡眠状态信号到来时可被唤醒。（3）“不可中断”睡眠态（TASK_UNINTERRUPTIBLE）:进程处于“深

46、度”睡眠状态不受信号的干扰。,（4）停止态（TASK_STOPPED):主要用于程序调试。当被调试进程收到一个信号（SIGSTOP）后就由运行态改为停止态，以后收到一个激活信号（SIGCONT）时又恢复继续运行。（5）僵死态（TASK_ZOMBIE）:由于某些原因运行进程被终止，但该进程的控制结构(task_struct)仍保留着。图2-26示出Linux系统中进程状态的变化关系。,图2-26 Linux进程状态的变化,2.进程的模式和类型 在Linux系统中，进程的执行模式划分为用户模式和内核模式。,图2-27 用户进程的两种运行模式,3.Liunx线程 线程是和进程紧密相关的概念。一般来说

47、，Linux系统中的进程应具有一段可执行的程序、专用的系统堆栈空间、私有的“进程控制块”(即task_struct数据结构)和独立的存储空间。然而，Linux系统中的线程只具备前三个组成部分而缺少自己的存储空间。,2.8.2 进程的结构 1.task_struct结构 Linux系统中每一个进程都包括一个名为task_struct的数据结构，它相当于“进程控制块”。每一个task_struct结构都有一个指针指向它，所有的这种指针组成系统中的一个进程向量数组task，该数组的大小默认值是512。,task_struct结构包含下列信息：(1)进程状态。(2)调度信息。调度算法利用这个信息来决定

48、系统中的哪一个进程需要执行。(3)标识符。系统中每个进程都有惟一的一个进程标识符(PID）。(4)内部进程通信。Linux系统支持信号、管道、信号量等内部进程通信机制。(5)链接信息。在Linux系统中，每个进程都与其他进程存在联系。,(6)时间和计时器。内核要记录进程的创建时间和进程运行所占用CPU的时间。(7)文件系统。进程在运行时可以打开和关闭文件。(8)虚拟内存。大多数进程都使用虚拟内存空间。(9)处理器信息。每个进程运行时都要使用处理器的寄存器以及堆栈等资源。,2.进程系统堆栈 在Linux系统中，每个进程都有一个系统堆栈，用来保存中断现场信息和进程进入内核模式后执行子程序(函数)嵌

49、套调用的返回现场信息。每个进程的系统堆栈和task_struct数据结构之间存在紧密联系，因而二者在物理存储空间中也连在一起，如图2-28所示。,图2-28 进程的系统堆栈和task_struct结构,3.进程的映像 Linux系统中进程映像由以下几个部分组成：进程控制块（task_struct）、系统栈、用户栈、程序代码段和数据段。如图2-29所示。,图2-29 Linux进程映像,4.进程的运行环境 进程在系统中存在以及活动需要一定的环境。进程环境由它的（用户）地址空间内容、硬件寄存器内容和与该进程有关的核心数据结构组成。Linux系统中进程环境是其用户级环境、寄存器环境和系统级环境的组合

50、。,2.8.3 对进程的操作 进程是有“生命期”的动态过程，核心能对它们实施操作，这主要包括创建进程，撤消进程，挂起进程，恢复进程，改变进程优先级，封锁进程，唤醒进程，调度进程等。1.进程的创建 与UNIX操作系统对进程的管理相似，Linux系统中各个进程构成了树形的进程族系。,2.进程的等待 父进程创建子进程往往让子进程替自己完成某项工作。因此，父进程创建子进程之后，通常等待子进程运行终止。父进程用系统调用wait4()等待它的一个子进程终止。,wait4()算法如下：(1)如果父进程没有子进程，则出错返回。(2)如果发现有一个终止的子进程，则取出子进程的进程号，把子进程的CPU使用时间等加