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

第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-1 顺序程序示意图,2.1.2 程序的并发执行和资源共享 多道程序 设计是指两个或更多个程序同时在系统中存在并且运行。 这时的工作环境与单道程序（仅一个）的运行条件相比， 大不相同。首先， 每个用户程序都需要一定的资源， 如内存、 设备、 CPU时间等， 因此系统中的软、 硬件资源不再是单个程序独占， 而是由几道程序所共享。 这样， 共享资源的状态就由多道程序的活动共同决定， 从而打破了单道程序“闭关自守”的局面。,图2-2 非多道技术下作业执行过程,采用多道程序技术来执行同样的作业A和B， 就能大大改进系统性能， 如图2-3所示。 作业A先运行， 它运行一秒后等待输入， 此时让B运行； B运行一秒后等待输入， 此时恰好A输入完， 可以运行了就这样在CPU上交替地运行A和B。 在这种理想的情况下， CPU不空转， 其使用率升至百分之百， 并且吞吐量也随之增加了。,图2-3 多道技术下作业执行过程,2.1.3 程序并发执行的特性 资源共享和程序的并发执行使得系统的工作情况变得非常复杂， 带来一系列新的问题， 特别表现在各种程序活动的相互依赖和制约关系方面。 我们分析一下图2-4中几个程序并发执行的情况。,图2-4 并发程序的执行 (a) 并发执行的程序； (b) 并发程序的关系； (c) 有制约关系的并发程序,通过上述三个例子的分析， 可以得出并发程序的三个主要特征： （1) 没有封闭性。 有共享公共变量时， 其执行结果不可再现， 就是说， 结果与相关的并发程序的相对速度有关。 (2) 程序与计算不再一一对应。 “程序”是指令的有序集合， 是“静态”的概念。 （3) 并发程序在执行期间可以互相制约。,2.1.4 进程概念的引入和描述 “进程”是操作系统的最基本、 最重要的概念之一。 引进这个概念对于理解、 描述和设计操作系统都具有极其重要的意义。 但是迄今为止， 对这个概念还没有形成统一的定义， 都是从不同的角度来描述它的各个基本特征。 下面列举出比较能反映进程实质的几种定义：,(1) 进程(或任务)是可以和别的计算并发执行的计算。 (2) 进程是程序的一次执行， 是在给定内存区域中的一组指令序列的执行过程。 (3) 所谓进程， 简单说来就是一个程序在给定活动空间和初始条件下， 在一个处理机上的执行过程。 (4) 进程可定义为一个数据结构和能在其上进行操作的一个程序。 (5) 进程是程序在一个数据集合上运行的过程， 它是系统进行资源分配和调度的一个独立单位。,进程和程序是两个不同的概念， 但又有密切的联系。 它们之间的主要区别是： (1) 程序是静态概念， 本身可以作为一种软件资源长期保存着； 而进程则是程序的一次执行过程， 它是动态概念， 有一定的生命期， 是动态地产生和消亡的。,(2) 进程是一个能独立运行的单位， 能与其他进程并发执行， 进程是作为资源申请和调度单位存在的； 而通常的程序段是不能作为一个独立运行的单位的。 (3) 程序和进程无一一对应关系。 一个程序可由多个进程共用； 另一方面， 一个进程在其活动中又可顺序地执行若干个程序。,(4) 各个进程在并发执行过程中会产生相互制约关系， 造成各自前进速度的不可预测性。 而程序本身是静态的， 不存在这种异步特征。 表2-1列出了进程和程序之间的主要区别。,表2-1 进程和程序的对比,2.1.5 进程的状态及其变迁 进程是一个程序的执行过程， 有着走走停停的活动规律。 进程的动态性质是由其状态变化决定的。 如果一个事物始终处于一种状态， 那么它就不再是活动的， 就没有生命力了。 通常在操作系统中， 进程至少要有三种基本状态， 这些状态是处理机挑选进程运行的主要因素， 所以又称之为进程控制状态。 这三种基本状态是： 运行态、 就绪态和阻塞态（或等待态）。 如图2-5所示。,图2-5 进程状态及其变化,在很多操作系统中， 又添加了两种基本状态： 创建态和终止态。 创建态是指新进程正被创建时的状态， 当创建工作完成后它就进入到就绪态。 终止态是指进程正常或非正常终止时所处的状态， 它的必然结局是从系统中消失。 上述五种进程状态及其变迁情况如图2-6所示。,图2-6 进程的五种基本状态,2.1.6 进程的组成 进程的活动是通过在CPU上执行一系列程序和对相应数据进行操作来体现的， 因此程序和它操作的数据是进程存在的实体。 但这二者仅是静态的文本， 没有反映出其动态特性。 为此， 还需要有一个数据结构， 用来描述进程当前的状态、 本身的特性等。 这种数据结构被称为进程控制块（PCB， Process Control Block)。,程序往往由一系列函数组成。 执行函数调用时要保存好调用者的现场信息， 以便被调函数完成后能恢复调用者的运行环境。 这一系列现场信息要保存在堆栈中， 按“后进先出”方式管理。 为此， 系统要为每个进程设立一个或多个栈。 所以进程通常都由程序、 栈、 数据集合和PCB这四部分组成。 图2-7示出进程的物理结构。,图2-7 进程组成,2.1.7 进程控制块 进程控制块有时也称为进程描述块（Process Descriptor）， 它是进程映像中最关键的部分， 其中含有进程的描述信息和控制信息， 是进程动态特性的集中反映， 它是系统对进程施行识别和控制的依据。 在不同的系统中， PCB的具体组成成分是不同的， 在简单操作系统中它较小； 而在大型操作系统中它很复杂， 设有很多信息项。 一般来说， 进程控制块应包括如下内容， 如图2-8所示。,图2-8 PCB构成,（1） 进程名。 它是惟一标志对应进程的一个标志符或数字。 (2) 特征信息。 它包括是系统进程还是用户进程， 进程映像是否常驻内存等。 (3) 进程状态信息。 它表明该进程的执行状态， 是运行态、 就绪态还是阻塞态。 (4) 调度优先权。 这表示进程获取CPU的优先级别。,(5) 通信信息。 它反映该进程与哪些进程有什么样的通信关系， 如等待哪个进程的信号等。 (6) 现场保护区。 当对应进程由于某个原因放弃使用CPU时， 需要把它的一部分与运行环境有关的信息保存起来， 以便在重新获得CPU后能恢复正常运行。,(7) 资源需求、 分配和控制方面的信息。 如进程所需要或占有的IO设备、 磁盘空间、 数据区等。 (8) 进程映像信息。 指出该进程的程序和数据的存储情况， 在内存或外存的地址、 大小等。 (9) 族系关系。 它反映父子进程的隶属关系。 (10) 其他信息。 如文件信息、 工作单元等。,2.1.8 PCB的组织方式 1. 线性表方式 如图2-9所示， 线性表的方式简单， 最容易实现。 操作系统预先确定整个系统中同时存在的进程最大数目， 比如是n， 静态分配空间， 把所有的PCB都放在这个表中。,图2-9 PCB线性表,2. 链接表方式 链接表方式是经常采用的方式。 其原理是： 按照进程的不同状态分别放在不同的队列中， 如图2-10所示。,图2-10 PCB链接表,3. 索引表方式 索引表方式是利用索引表记载各种状态进程的PCB地址， 如就绪索引表中的表项指向就绪进程PCB的指针， 而阻塞表中的表项指向阻塞进程PCB的指针。 各索引表的起始地址放在专用的指针单元中， 运行进程的PCB由一个专用的运行指针指向。 图2-11示出PCB索引表方式。,图2-11 PCB索引表,2.2 线 程,2.2.1 线程概念 1. 线程 线程 是进程中执行运算的最小单位， 亦即执行处理机调度的基本单位。 如果把进程理解为在逻辑上操作系统所完成的任务， 那么线程表示完成该任务的许多可能的子任务之一。,2. Thread结构 每个线程有一个Thread结构， 用于保存与线程有关的信息， 主要由以下几个基本部分组成： (1) 一个惟一的线程标识符。 （2） 描述处理器状态的一组状态寄存器的内容， 用于调度。 （3） 每个Thread结构有两个堆栈指针： 一个指向核心堆栈， 一个指向用户堆栈。 （4） 一个私有存储区， 存放现场保护信息及其他各种统计信息等。,图2-12 Thread结构,3. 带线程的进程模型 一个进程可以包含一个或者多个线程， 但至少要有一个线程。 在传统的进程中就只有一个线程。 当一个进程包含多个线程时， 各线程除自己有少量私有资源（如程序计数器、 寄存器和堆栈）外， 要共享所属进程的全部资源（如程序代码、 数据和文件等）。 图2-13示出单线程和多线程的进程模型。,图2-13 单线程式和多线程式的进程,4. 进程与线程的关系 从以上介绍中可以看出， 进程和它的线程有如下关系： （1） 一个进程可以有多个线程， 但至少要有一个线程。 （2） 进程是资源的拥有者， 是分配资源的独立单位； 而线程一般不拥有系统资源（仅有一点必不可少的资源）， 同一进程的所有线程共享该进程的全部资源。 （3） 在支持线程的操作系统中， 线程是调度和分派的基本单位。,（4） 进程可以并发执行。 （5） 线程在执行过程中往往需要协作同步。 （6） 在实施创建、 撤消和切换等操作时， 进程的开销远大于线程的开销。 （7） 线程和进程一样， 都是动态实体， 具有不同的状态， 如运行态、 就绪态、 阻塞态和终止态等。,2.2.2 线程的实现方式 1. 用户级线程 在这种方式下， 整个管理线程的线程库放在用户空间， 对线程从创建到撤消的全部管理工作都由应用程序完成。 核心对线程一无所知， 只对常规进程实施管理。 图2-14(a)示出用户级线程的实现方式。,图2-14 线程的实现方式,用户级线程实现方式具有以下三个优点： （1） 线程切换速度快。 （2） 调度算法可以是应用程序专用的， 不仅最适合自己的需求， 而且不干扰底层操作系统的进程调度。 （3） 用户级线程可运行在任何操作系统上， 包括不支持线程机制的操作系统。,用户级线程方式也存在两个主要缺点： （1） 系统调用的阻塞问题。 当一个线程执行系统调用时， 不仅它自己被阻塞， 而且在同一进程内的所 有线程都将被阻塞。 （2） 这种方式下的多线程应用程序不具有多处理的优点。 因为核心只为每个进程一次分配一台处理机。,2. 核心级线程 在这种方式下， 核心知道线程的存在， 并对它们实施管理。 如图2-14(b)所示。 在核心空间中不仅有一个进程表， 而且有一个线程表， 其中记载系统中所有线程的情况。 这样， 就由核心统一管理系统中所有的线程。 核心进行调度时以线程为基本单位。,核心级线程的优点是： （1） 在多处理器系统中， 核心可以同时调度同一进程的多个线程， 真正实现并行操作。 （2） 一个进程的某个线程阻塞了， 核心可以调度同一进程的另一个线程运行。 核心级线程方式也存在缺点， 主要是： （1） 线程切换速度慢， 控制转移开销大。 （2） 调度算法由核心确定， 应用进程无法影响线程的切换。,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) 若该进程还有子孙进程， 则还要终止其所有子孙进程， 回收它们所占用的全部资源。 (4) 释放被终止进程的PCB， 并从原来队列中摘走。,2.3.3 更换进程映像 改变进程映像的工作很复杂， 其主要过程是： （1） 释放子进程原来的程序和数据所占用的内存空间； （2） 从磁盘上找出子进程所要执行的程序和数据（通常以可执行文件的形式存放）； （3） 分配内存空间， 装入新的程序和数据； （4） 为子进程建立初始的运行环境主要是对各个寄存器初始化， 返回到用户态， 运行该进程的程序。,2.3.4 阻塞进程 进程阻塞的过程如下： （1） 立即停止当前进程的执行； （2） 将现行进程的CPU现场送到该进程的PCB现场保护区中保存起来， 以便将来重新运行时恢复此时的现场；,（3） 把该进程PCB中的现行状态由“运行”改为“阻塞”， 把它插入到具有相同事件的阻塞队列中； （4） 然后转到进程调度程序， 重新从就绪队列中挑选一个合适的进程投入运行。,2.3.5 唤醒进程 唤醒原语执行过程是： （1） 首先把被阻塞进程从相应的阻塞队列中摘下； （2） 将现行状态改为就绪态， 然后把该进程插入到就绪队列中； （3） 如果被唤醒进程比运行进程有更高的优先级， 则设置重新调度标志。,2.4 进 程 间 通 信,2.4.1 进程间的关系 1. 同步 同步是进程间共同完成一项任务时直接发生相互作用的关系， 也就是说， 这些具有伙伴关系的进程在执行的时间次序上必须遵循确定的规律。,2. 互斥 协同工作的进程之间存在同步关系， 但是进程之间更一般的关系是互斥关系， 这是由于诸进程共享某些资源而引起的。 3. 通信 进程经常需要与其他进程通信。,2.4.2 竞争条件和临界区 1. 竞争条件 在有些操作系统中， 并发进程在活动过程中可能共享一些彼此都能够读写的公用存储区。 它可能在内存中， 也可能是一个共享文件， 其所在位置并不影响问题的实质。 下面我们考虑两个进程对一个系统打印机分配表的操作情况。,假定进程Pa负责为用户进程分配打印机， 进程Pb负责释放打印机。 由于分配和释放可能同时发生， 因此两个进程必须共享一个打印机分配表， 如表2-2所示。,表2-2 打印机分配表,Pa进程分配打印机的过程是： (1) 逐项检查分配标志， 找出标志为0的打印机号码； （2） 把该机的分配标志置1； （3） 把用户名和设备名填入分配表中相应位置。,Pb进程释放打印机的过程是： （1） 逐项检查分配表的各项信息， 找出标志为1并且用户名和设备名与被释放的名字相同的机号； （2） 该机标志清0； （3） 清除该机用户名和设备名。,表2-3 打印机分配表（出错情况）,2. 临界区 为了使临界资源得到合理使用， 就必须禁止两个或两个以上的进程同时进入临界区内， 就是说欲进入临界区的若干个进程要满足如下关系： （1） 如果有若干进程要求进入临界区， 一次仅允许一个进程进入。,（2） 任何时候， 处于临界区内的进程不可多于一个。 （3） 进入临界区的进程要在有限时间内退出， 以便其他进程能及时进入自己的临界区。 （4） 如果进程不能进入自己的临界区， 则应让出CPU， 避免进程出现“忙等”现象。,2.4.3 用锁操作原语实现互斥 进程通信是实现进程间同步与互斥的一种机制。 这类似于人类社会生活中为表达意见、 交流思想、 交换信息等而采用多种通信方式， 例如， 人们打手势、 交谈、 打电话、 写信、 发E-mail等， 方式有简有繁， 当然其功能也有强弱之别。 下面分别介绍典型的实现进程同步与互斥的手段。,为解决进程互斥进入临界区的问题， 可为每类临界资源设置一把锁， 该锁有打开和关闭两种状态。 进程执行临界区程序的操作按下列步骤进行： (1) 关锁。 先检查锁的状态， 如为关闭状态， 则等待其打开； 如已打开了， 则将其关闭， 继续执行（2)的操作。 （2) 执行临界区程序。 (3) 开锁。 将锁打开， 退出临界区。,2.4.4 信号量上的P、 V操作原语 1. 信号量（Semaphore） 信号量及信号量上的P操作和V操作是E.W.Dijkstra在1965年提出的一种解决同步、 互斥问题的更通用的方法， 并在THE操作系统中得以实现。,结构型信号量一般是由两个成员组成的数据结构（亦称记录型信号量）， 其中一个成员是整型变量， 表示该信号量的值； 另一个是指向PCB的指针。 当多个进程都等待同一信号量时， 它们就排成一个先入先出的队列， 由信号量的指针项指出该队列的头， 而PCB队列是通过PCB本身所包含的指针项进行链接的。 最后一个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（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表示不空， 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 生产者消费者问题 为了使这两类进程协调工作， 防止盲目的生产和消费， 它们应满足如下同步条件： （1） 所有生产者当前存放产品的单元数不能超过缓冲区的总容量（N）； （2） 所有消费者取出产品的总量不能超过所有生产者生产产品的总量。,图2-18 生产者消费者问题,为了使两类进程实行同步操作， 应设置三个信号量： 两个计数信号量full和empty， 一个互斥信号量mutex。 full: 表示放有产品的缓冲区数， 其初值为0。 empty: 表示可供使用的缓冲区数， 其初值为N。 mutex: 互斥信号量， 初值为1， 表示互斥进入临界区， 即： 保证任何时候只有一个进程使用（读或写）缓冲区， 防止发生混乱。,下面是这个问题算法的描述。 生产者进程Pi： while(TRUE) 生产一个产品 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） 在每个程序中必须先做P（mutex)、 后做V(mutex)， 二者要成对出现。 （2） 对同步信号量full和empty的P、 V操作同样必须成对出现， 但它们分别位于不同进程的代码中。 （3） 无论在生产者进程中还是在消费者进程中， 两个P操作的次序不能颠倒。,读者可针对以下情况试分析上述方案中各进程的运行过程： （1） 只有生产者进程在运行， 各个消费者进程未被调度运行； （2） 消费者进程试图超前生产者进程运行； （3） 生产者进程和消费者进程被交替调度运行。,2.5 经典进程同步问题,2.5.1 读者写者问题 读者写者问题是一个著名的进程互斥访问有限资源的问题（1971年由Courtois等人解决）。 该问题可以表述为： 一个航班预订系统有一个大型数据库， 很多竞争进程要对它进行读、 写。,设置两个信号量： 读互斥信号量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(readcount=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); 进餐 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; /*互斥进入临界区*/,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)； /*如果拿不到筷子就阻塞*/ 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 困睡的理发师问题 理发师打盹问题。 理发店有一名理发师、 一个理发椅和几个坐椅， 等待理发的顾客可坐在上面。 如果没有顾客到来， 理发师坐在理发椅上打盹。 当顾客到来， 他唤醒理发师。 如果顾客到来时理发师正在理发， 则该顾客坐在椅子上排队； 如果满座了， 他就离开这个理发店到别处去理发。 为理发师和顾客各编写一段程序来描述他们的行为， 要求不能带有竞争条件。,设置三个信号量和一个计数变量： 信号量customers用来记录等待理发的顾客数（不包括正在理发的顾客）； barbers用来记录正在等候顾客的理发师数， 为0或1； mutex用于表示互斥。 计数变量waiting也用于记录等候的顾客数， 它实际上是customers的一份拷贝。 在程序中， 进入理发店的顾客必须先看坐椅上有无空位， 如果有空位， 他就留下来等； 否则他就离开。 由于无法直接读取信号量customers的当前值（信号量只能由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）; /*要求进程等候*/ waiting=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( ); /*坐在理发椅上等候服务*/ else V(mutex); /*店里人满了， 离开*/ ,2.6 管 程,一个管程由四部分组成， 它们是管程名称、 局部于管程的共享数据的说明、 对数据进行操作的一组过程和对该共享数据赋初值的语句。 图2-20示出了管程的结构， 它定义了一种共享数据结构。,图2-20 管程的结构,管程是一个程序设计语言的概念， 必须得到编译程序的支持。 编译程序必须能识别管程， 并用某种方式实现互斥访问。 管程构造已由多种语言实现， 如并发Pascal、 Pascal+、 Modula-2和Modula-3等。 最近它已作为程序库实现。,管程具有以下三个特性： （1） 管程内部的数据是局部变量， 只能被管程内部定义的过程所访问， 在管程外面声明过的过程不能直接访问它们。 （2） 进程要想进入管程， 必须调用管程内的某个过程。 （3） 一次只能有一个进程在管程内执行， 而其余调用该管程的进程都被挂起， 等待该管程成为可用的。,图2-21 带条件变量的管程,设进程P1调用signal(x)操作， 有一个被挂起的进程Q与条件x有关。 显然， 若被挂起的进程Q被允许恢复执行， 则发信号的进程P1一定要等待。 否则， P1和Q都将在管程内同时活动。 （当然， 从概念上讲， 这些进程都可以执行。） 下面是一个用管程解决生产者消费者问题的解法（用类Pascal语言）。,monitor ProducerConsumer condition full, empty; integer count; 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; procedure 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. 共享存储器方式 共享存储器方式是在内存中分配一片空间作为共享存储区。 需要进行通信的各个进程把共享存储区附加到自己的地址空间中， 然后就像正常操作一样对共享区中的数据进程读或写。,2. 管道文件 管道文件也称为管道线， 它是连接两个命令的个打开文件。 一个命令向该文件中写入数据， 称为写者； 另一个命令从该文件中读出数据， 称为读者。 例如在UNIX/Linux系统中， 下述命令行就实现两个命令间的通信： ls -lwc -l,3. 消息传递方式 消息传递方式以消息(Message)为单位在进程间进行数据交换。 它有两种实现方式： (1) 直接通信方式。 发送进程直接将消息挂在接收进程的消息缓冲队列上， 接收进程从消息缓冲队列中得到消息。 (2) 间接通信方式。 发送进程将消息送到被称为信箱的中间设施中， 接收进程从信箱中取得消息。 这种通信方式也称为信箱通信方式。,2.7.1 消息缓冲通信 消息缓冲区一般包含下列几种信息： name： 发送消息的进程名或标志号。 size： 消息长度。 text： 消息正文。 next： 下个缓冲区的地址。,在采用消息通信机构的系统中， 进程PCB中一般包含有下列项目： mutex： 消息队列操作互斥信号量。 消息队列是临界资源， 不允许两个或两个以上进程对它同时进行访问。 Sm： 表示接收消息计数和同步的信号量， 用于接收消息进程与发送消息进程进行同步， 其值表示消息队列中的消息数目。 Pm： 指向该进程的消息队列中第一个缓冲区的指针。 接收消息进程的PCB和它的消息缓冲链的关系如图2-22所示。,图2-22 PCB与消息缓冲链,两个进程进行消息传送的过程如图2-23所示， 发送进程在发送消息之前， 先要在自己的内存空间设置一发送区， 把准备发送的消息正文以及接收消息的进程名(或标志号)和消息长度填入其中， 完成上述准备工作之后， 调用发送消息的程序send(addr)， 其中参数addr是消息发送的起始地址。 send程序的流程如图2-24所示， 图中mutex是接收进程PCB中的互斥信号量， Sm是接收进程PCB中的同步信号量。,图2-23 消息发送与接收,图2-24 send程序流程图,图2-25 receive程序流程图,2.7.2 信箱通信 信箱是实现进程通信的中间实体， 可以存放一定数量的消息。 发送进程将消息送入信箱， 接收进程从信箱中取出发给自己的消息。 这有点类似于我们日常使用信箱的情况。 信箱是一种数据结构， 在逻辑上可分为两个部分： 信箱头包括信箱名字、 信箱属性(公用、 私用或者共享)、 信箱格状态等； 信箱体用来存放消息的多个信箱格。,当进程之间要通信时， 它们必须有共享信箱。 发送和接收消息的原语形式为： 1) send(mailbox， message) 其中， mailbox为信箱， message是要发送的消息。 2) receive(mailbox， message) 接收进程要接收一个消息时， 先判断信箱状态是否为满。,信箱可分为三类： (1) 公用信箱： 它由操作系统创建， 系统中所有核准进程都可使用它既可把消息放在该信箱中， 又可从中取出发给自己的消息。 （2） 共享信箱： 它由某个进程创建， 对它要指明共享属性以及共享进程的名字。 （3） 私有信箱： 用户进程为自己创建的信箱。,2.8 Linux进程管理,2.8.1 进程和线程的概念 1. 进程及其状态 简单来说， 进程就是程序的一次执行过程。 在Linux系统中， “进程”和“任务”是同一个意思。 所以， 在内核的代码中这两个词常常混用。,在Linux系统中， 进程有下述五种状态。 （1） 可运行态（TASK_RUNNING）： 进程处于就绪状态， 可以被调度运行。 （2） “可中断”睡眠态（TASK_INTERRUPTIBLE）: 进程处于“浅度”睡眠状态信号到来时可被唤醒。 （3） “不可中断”睡眠态（TASK_UNINTERRUPTIBLE）: 进程处于“深度”睡眠状态不受信号的干扰。,（4） 停止态（TASK_STOPPED): 主要用于程序调试。 当被调试进程收到一个信号（SIGSTOP）后就由运行态改为停止态， 以后收到一个激活信号（SIGCONT）时又恢复继续运行。 （5） 僵死态（TASK_ZOMBIE）: 由于某些原因运行进程被终止， 但该进程的控制结构(task_struct)仍保留着。 图2-26示出Linux系统中进程状态的变化关系。,图2-26 Linux进程状态的变化,2. 进程的模式和类型 在Linux系统中， 进程的执行模式划分为用户模式和内核模式。,图2-27 用户进程的两种运行模式,3. Liunx线程 线程是和进程紧密相关的概念。 一般来说， Linux系统中的进程应具有一段可执行的程序、 专用的系统堆栈空间、 私有的“进程控制块”(即task_struct数据结构)和独立的存储空间。 然而， Linux系统中的线程只具备前三个组成部分而缺少自己的存储空间。,2.8.2 进程的结构 1. task_struct结构 Linux系统中每一个进程都包括一个名为task_struct的数据结构， 它相当于“进程控制块”。每一个task_struct结构都有一个指针指向它， 所有的这种指针组成系统中的一个进程向量数组task， 该数组的大小默认值是512。,task_struct结构包含下列信息： (1) 进程状态。 (2) 调度信息。 调度算法利用这个信息来决定系统中的哪一个进程需要执行。 (3) 标识符。 系统中每个进程都有惟一的一个进程标识符(PID）。 (4) 内部进程通信。 Linux系统支持信号、 管道、 信号量等内部进程通信机制。 (5) 链接信息。 在Linux系统中， 每个进程都与其他进程存在联系。,(6) 时间和计时器。 内核要记录进程的创建时间和进程运行所占用CPU的时间。 (7) 文件系统。 进程在运行时可以打开和关闭文件。 (8) 虚拟内存。 大多数进程都使用虚拟内存空间。 (9) 处理器信息。 每个进程运行时都要使用处理器的寄存器以及堆栈等资源。,2. 进程系统堆栈 在Linux系统中， 每个进程都有一个系统堆栈， 用来保存中断现场信息和进程进入内核模式后执行子程序(函数)嵌套调用的返回现场信息。 每个进程的系统堆栈和task_struct数据结构之间存在紧密联系， 因而二者在物理存储空间中也连在一起， 如图2-28所示。,图2-28 进程的系统堆栈和task_struct结构,3. 进程的映像 Linux系统中进程映像由以下几个部分组成： 进程控制块（task_struct）、 系统栈、 用户栈、 程序代码段和数据段。 如图2-29所示。,图2-29 Linux进程映像,4. 进程的运行环境 进程在系统中存在以及活动需要一定的环境。 进程环境由它的（用户）地址空间内容、 硬件寄存器内容和与该进程有关的核心数据结构组成。 Linux系统中进程环境是其用户级环境、 寄存器环境和系统级环境的组合。,2.8.3 对进程的操作 进程是有“生命期”的动态过程， 核心能对它们实施操作， 这主要包括创建进程， 撤消进程， 挂起进程， 恢复进程， 改变进程优先级， 封锁进程， 唤醒进程， 调度进程等。 1. 进程的创建 与UNIX操作系统对进程的管理相似， Linux系统中各个进程构成了树形的进程族系。,2. 进程的等待 父进程创建子进程往往让子进程替自己完成某项工作。 因此， 父进程创建子进程之后， 通常等待子进程运行终止。 父进程用系统调用wait4()等待它的一个子进程终止。,wait4()算法如下： (1) 如果父进程没有子进程， 则出错返回。 (2) 如果发现有一个终止的子进程， 则取出子进程的进程号， 把子进程的CPU使用时间等加到父进程上， 释放子进程占用的task_struct和系统堆栈， 以供新进程使用。 (3) 如果发现有子进程， 但都不处于终止态， 则父进程睡眠等待， 以后由相应信号唤醒。,3. 进程的终止 在Linux系统中， 进程主要是作为执行命令的单位运行的， 这些命令的代码都以系统文件形式存放。 当命令执行完， 希望终止自己时， 可在其程序末尾使用系统调用exit()。,用户进程也可使用exit来终止自己。 其实现算法如下： (1) 撤消所有的信号量。 (2) 释放其所有的资源， 包括存储空间、 已打开的文件、 工作目录、 信号处理表等。 (3) 置进程状态为“终止态”(TASK_ ZOMBIE)。 (4) 向它的父进程发送子进程终止的信号。 (5) 执行进程调度。,4. 进程映像的更换 子进程被创建后， 通常处于“就绪态”， 以后被调度选中才可运行。 由于创建子进程过程中， 是把父进程的映像复制给子进程， 因此子进程开始执行的入口地址就是父进程调用fork()系统调用建立子进程映像时的返回地址， 此时二者的映像基本相同。,图2-30 ELF可执行文件格式示意图,execve（ ）系统调用的基本算法如下： (1) 验证文件的可执行性， 即用户有权执行它。 (2) 读文件头， 检查它是一个可装入模块。 (3) 释放原有的内存空间。 (4) 按照可执行文件的要求分配新的内存空间， 并装入内存。,2.8.4 进程同步和通信 1. 信号量 Linux系统中的信号量与上面所讲的信号量机制相似， 利用它可实现进程对共享资源的互斥访问。 信号量是一种数据结构， 其定义如下所示：,struct semaphore atomic_t count; int sleepers; wait_q