第2章 进程管理

第2章进程管理王之仓青海师范大学2.12.32.22.42.52.6进程的基本概念目录进程控制进程同步管程机制线程进程互斥2.72.8经典同步问题进程通信010203进程特征、进程控制进程互斥与同步进程通信、管程机制、线程要点学要123456理解进程的特征及状态变化了解进程控制块的构成与作用掌握信号量机制及其应用掌握生产者－消费者问题理解管程的基本概念了解消息传递的直接方法与间接方法习求7了解微内核OS结构的基本特点运行程序还是运行进程？在传统的操作系统中，程序不能独立运行，作为资源分配和独立运行的单位是进程。操作系统所具有的四大特征也都是基于进程而形成的，并可从进程的观点来研究操作系统。显然，在操作系统中，进程是一个极其重要的概念。本章任务本章专门来描述进程。通过本章的学习，学习者可以明确进程为什么存在，什么是进程，进程有哪些状态，如何控制进程，进程互斥，进程同步以及几个典型的进程同步问题。同时，还会知道在现代操作系统中独立调度、独立运行的最小单位是线程(Thread)，而不是进程(Process)。2.1进程的基本概念

在早期的操作系统中，程序采用绝对装入方式(见第5章5.1节)，内存采用单一连续分配方式(见第5章5.2节)。在这个时期，每个正在运行的程序占用了系统所有资源，只有一个程序运行完毕后才考虑运行下一个程序。也就是，程序的执行是顺序执行，即必须在一个程序执行完成后，才允许另一个程序执行。2.1进程的基本概念随着支持多任务系统的固定分区内存分配技术(见第5章5.2节)的出现，系统允许多个程序并发执行。程序的这两种运行方式间有着显著不同。也正是程序并发执行时的特征，才在操作系统中引入进程的概念。2.1进程的基本概念1.程序的顺序执行程序是一个在时间上按严格次序前后相继的操作序列，是一个静态的概念。一个具有独立功能的程序独占处理机直至得到最终结果的过程称为程序的顺序执行。一个完整的程序应该包括输入、计算和输出3个部分。图2-1所示为程序顺序执行的过程。图中程序1和程序2分别包括I1、I2，C1、C2和P1、P2模块。只有程序1执行完毕后程序2才得以执行。2.1.1程序的顺序执行及特征2.1.1程序的顺序执行及特征图2-1

程序的顺序执行2.程序顺序执行时的特征(1)顺序性程序顺序执行时，其执行过程可看做一系列严格按程序规定的状态转移过程，也就是每执行一条指令，系统就从上一个执行状态转移到下一个执行状态，且上一条指令的执行结束是下一条指令执行开始的充分必要条件。2.1.1程序的顺序执行及特征2.程序顺序执行时的特征(2)封闭性程序是在封闭的环境下执行。即程序在运行时独占全部资源，资源的状况只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。(3)可再现性顺序执行的最终结果可再现是说它与执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。2.1.1程序的顺序执行及特征2.程序顺序执行时的特征(2)封闭性程序是在封闭的环境下执行。即程序在运行时独占全部资源，资源的状况只有本程序才能改变它。程序一旦开始执行，其执行结果不受外界因素影响。(3)可再现性顺序执行的最终结果可再现是说它与执行速度无关。只要输入的初始条件相同，则无论何时重复执行该程序都会得到相同的结果。2.1.1程序的顺序执行及特征

前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。结点间的有向边用于表示两个结点之间存在的偏序(PartialOrder)或前趋关系。前趋关系用→表示，如图2-1所示可看做前驱图，图中每个结点为1个进程。于是表示了I1制约C1、C1制约P1等信息。图2-2所示为多进程并发执行的前趋图。2.1.2前趋图2.1.2前趋图图2-2

程序的并发执行前趋图1.程序的并发执行以程序为单位运行时，都是顺序执行的方式。因为程序会用到CPU和输入输出设备，使得其他程序没有资源可用。因此，程序的并发执行，本质上是以程序为基础，结合在该程序上处理的数据以及用于控制进程的数据结构PCB(见第2章2.1.3)而创建起来的进程的并发执行。2.1.3程序的并发执行及其特征2.程序并发执行时的特征(1)间断性程序在并发执行时，微观上是多个进程并发执行。由于它们共享系统资源，以及为完成同一任务而相互合作，致使在这些并发执行的程序之间形成了相互制约的关系。从而使得有些程序在执行中出现走走停停的情况。如上例中诸进程之间极易出现这种情况。2.1.3程序的并发执行及其特征2.程序并发执行时的特征(2)失去封闭性程序并发执行时，由多个程序(进程)共享资源，因而对资源的状态由多个程序来改变，从而失去了封闭性。(3)不可再现性各进程推进的顺序不可再现。2.1.3程序的并发执行及其特征3.程序并发执行引发的问题1)协调各程序的执行顺序。例如，当输入的数据还未全部输入内存时，计算必须等待。2)多个执行程序共享系统资源，程序之间可能会相互影响，甚至影响输出结果。3)选择哪些、多少个程序进入内存运行：根据资源等情况决定。4)内存中的执行程序哪个先执行：根据系统采用的调度算法。5)内存如何有效分配：内存资源非常宝贵2.1.3程序的并发执行及其特征进程和程序的对应关系：一个程序对应一个或多个进程，一个进程对应一个或一段程序。2.1.4进程的特征与状态1.进程的特征(1)进程的特征1)结构特征：程序段+相关数据段+PCB。2)动态性：进程是运行的程序。它由创建而产生、由调度而执行，由撤消而消亡。3)并发性：多个进程同时存在于内存，且能在一段时间内同时运行。如分时系统中按时间片运行。2.1.4进程的特征与状态1.进程的特征(1)进程的特征4)独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡未建立PCB的程序都不能作为一个独立的单位参与运行。5)异步性：各进程按照各自独立的、不可预知的速度向前推进，或者说进程按异步方式运行。进程最基本的两个特征是动态性和并发性。2.1.4进程的特征与状态1.进程的特征(2)引入进程产生的问题1)增加空间的开销：为进程建立数据结构(PCB)。2)增加时间开销：管理、协调、跟踪进程；填写和更新数据结构、切换进程、保护现场。3)更难控制：协调多个进程竞争和共享资源，如何预防并解决多个进程因为竞争资源而出现故障(如死锁、饥饿)。4)处理机的竞争尤为突出。2.1.4进程的特征与状态进程执行时的间断性，决定了进程可能具有多种状态。作业有四种状态，分为提交、后备、执行和完成。进程有三种状态，分为就绪(Ready)、运行(Run)和阻塞(Block)。在有些操作系统中，将进程状态分为5种，还有新状态、终止状态。图2-3示出了进程的三种基本状态以及各状态之间的转换关系。2.1.4进程的特征与状态2.1.4进程的特征与状态图2-3

进程状态转换1)就绪(Ready)状态已经分配到除CPU之外的所有资源，可谓“万事俱备，只欠CPU”。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。2)执行状态(Run)进程获得了包括CPU在内的所需的全部资源，程序正在执行。2.1.4进程的特征与状态3)阻塞状态(Block)正在执行的进程由于发生某事件而暂时无法继续执行时，便放弃处理机而处于暂停状态，即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，或称等待状态。通常把处于阻塞状态的进程排成一个队列，称为阻塞队列。2.1.4进程的特征与状态3.挂起状态(1)引起挂起状态的原因1)终端用户的请求：修改程序。2)父进程请求：对子进程的修改等。3)负荷调节的需要：资源不够用。4)操作系统的需要：检查资源利用情况。2.1.4进程的特征与状态(2)进程状态的转换在引入挂起状态后，又增加了挂起状态(静止状态)到非挂起状态(活动状态)的转换以及反转换。图2-4所示为具有挂起状态的进程状态图。1)活动就绪Readya→静止就绪Readys：Suspend原语2)活动阻塞Blockeda→静止阻塞Blockeds：Suspend原语3)静止就绪Readys→活动就绪Readya：Active原语4)静止阻塞Blockeds→活动阻塞Blockeda：Active原语2.1.4进程的特征与状态2.1.4进程的特征与状态图2-4

具有挂起状态的进程状态图进程控制块是进程的“身份证”，唯一地标识着进程的存在。每个进程都和它的进程控制块一一对应。操作系统在内存专门划出一块区域——进程控制块区——存放进程控制块。2.1.5进程控制块1概念进程控制块(PCB，ProcessControlBlock)，为了描述和控制运行进程的运行，系统为每个进程定义了一个数据结构，成为进程控制块。(/include/linux/sched.h中structtask_struct)PCB中记录了操作系统所需的、用于描述进程的当前情况以及控制进程运行的全部信息。2.1.5进程控制块1概念进程控制块随着进程的创建而创建，即创建一个进程，就是创建一个PCB；进程控制块随着进程的撤消而撤消，即撤消一个进程，就是撤消进程PCB。因此，PCB是进程的存在的惟一标志。2.1.5进程控制块2进程控制块中的信息(1)进程标识符(processidentifier,PID)包括进程的标识符ID(系统指定)、该进程的父进程标识符FID(系统指定)和进程的用户标识符UID(如计算进程，由用户命名)。(2)处理机状态：处理机的各种寄存器中的内容(3)进程调度信息(4)进程控制信息2.1.5进程控制块3进程控制块的组织方式(1)链接方式Linux操作系统中PCB的组织形式采用链接方式。当操作系统的进程控制块采用链接方式时，操作系统将具有同一状态的PCB，组成PCB队列。分别是就绪队列、阻塞队列、空闲队列。2.1.5进程控制块3进程控制块的组织方式(2)索引方式系统根据所有进程的状态建立几张索引表。如为就绪进程的进程控制块索引表、等待进程的进程控制块索引表，多处理机中还会有运行态进程的进程控制块索引表，以及空闲的进程控制块索引表。各索引表在内存的首地址记录保存在PCB中。在每个索引表的表项中，记录具有相应状态的某个PCB在PCB区中的地址。2.1.5进程控制块【实例2-1】LinuxKernal2.6.8定义的PCB。见教材。2.1.5进程控制块2.2进程控制一般，把系统态下执行的某些具有特定功能的程序段称为原语。原语可分为机器指令级原语和功能级原语。前者是一条语句，后者是一段代码。机器指令级原语的特点是执行期间不允许中断，它是一个不可分割的基本单位。功能级原语的特点是作为原语的程序段不允许并发执行。2.2进程控制进程控制是进程和处理机管理的一个重要任务。进程控制是指系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。进程的控制是通过原语实现的。用于进程控制的原语有：创建原语、撤消原语、阻塞原语、唤醒原语、挂起原语和激活原语等。2.2进程控制1进程图进程图(ProcessGraph）是用于描述一个进程的家族关系的有向树。在进程Pi创建了进程Pj之后，称Pi是Pj的父进程，Pj是Pi的子进程。子进程可以继承父进程所拥有的所有资源。为了标识进程之间的家族关系，在PCB中设置了家族关系表项，以标明自己的父进程以及所有的子进程。2.2.1进程的创建2引起创建进程的事件/创建进程的原因1)用户登录：合法用户登录，创建用户进程。2)作业调度：在发生作业调度时，会为被调度作业分配内存，并为之创建进程，以待运行。3)提供服务：如打印进程。4)应用请求：如输入、计算、打印三进程。2.2.1进程的创建3进程的创建(1)引起创建进程的事件发生。(2)调用进程创建原语。(3)创建步骤：1)申请空白PCB；2)为新进程分配资源；3)初始化进程控制块；4）将新进程插入就绪队列。2.2.1进程的创建【实例2-2】创建一个子进程。子进程的创建通过调用fork()函数完成。本质上是从父进程派生出一个子进程。教材：p26提示：了解为什么调用fork()一次，会返回两次。2.2.1进程的创建1引起进程终止的事件(1)正常结束，即进程顺利的完成使命后终止，大多数进程终止都是这种情况。(2)异常结束，即在进程运行期间，由于出现某种错误和故障而迫使进程终止。(3)外界干预，即在进程运行的过程中，响应外界的请求而终止运行。可能的干预包括：1)操作员或操作系统干预；2)父进程请求；3)父进程终止。。2.2.2进程的终止2进程的终止过程(1)终止进程事件发生。(2)调用终止原语。(3)终止步骤：1)根据进程PID，得到进程PCB和进程的状态；2)若进程在执行，停止执行，置调度标志为真；3)终止子进程；4)归还资源给父进程或系统；5)移出队列。。2.2.2进程的终止1概念实现进程从执行状态到等待状态的转换的原语称为阻塞原语。实现进程从等待状态到就绪状态的转换的原语称为唤醒原语。2.2.3进程的阻塞与唤醒2阻塞原语阻塞原语在一个进程期待某一事件(例如IO操作、其他进程发来的数据等)发生，但发生条件尚不具备时，被该进程自己调用来阻塞自己。阻塞事件：1)请求系统服务；2)启动某种操作；3)新数据尚未到达；4)无新工作可做。2.2.3进程的阻塞与唤醒3阻塞过程阻塞原语在阻塞一个进程时，由于该进程正处于执行状态，故应先中断处理机和保存该进程的CPU现场。然后将被阻塞进程置“阻塞”状态后插入等待队列中，再转进程调度程序选择新的就绪进程投入运行。

2.2.3进程的阻塞与唤醒4唤醒问题当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都可能被唤醒。显然，一个处于阻塞状态的进程不可能自己唤醒自己。5唤醒进程的方法唤醒进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。2.2.3进程的阻塞与唤醒4唤醒问题当等待队列中的进程所等待的事件发生时，等待该事件的所有进程都可能被唤醒。显然，一个处于阻塞状态的进程不可能自己唤醒自己。5唤醒进程的方法唤醒进程有两种方法：一种是由系统进程唤醒。另一种是由事件发生进程唤醒。2.2.3进程的阻塞与唤醒6唤醒过程唤醒原语首先将被唤醒进程从相应的等待队列中取出，将被唤醒进程置为就绪状态之后，送入就绪队列。在把被唤醒进程送入就绪队列之后，唤醒原语既可以返回原调用程序，也可以转向进程调度，以便让调度程序有机会选择一个合适的进程执行。2.2.3进程的阻塞与唤醒1进程的挂起(1)概念挂起进程在操作系统中可以定义为暂时被淘汰出内存的进程系统的资源是有限的，在资源不足的情况下，操作系统会对在内存中的进程进行合理的安排，其中有的进程被暂时调离出内存。2.2.4进程的挂起和激活1进程的挂起(2)引起挂起状态的原因1)终端用户的请求。2)父进程的请求。3)负荷调节的需要。4)操作系统的需要。5)对换的需要。2.2.4进程的挂起和激活2进程的激活(1)概念处于挂起状态的进程，当有存放其的内存空间时，会被操作系统再次调回内存，重新进入等待被执行的状态（即就绪态）或阻塞状态。(2)引起激活状态的原因当发生激活进程的事件，如父进程或用户进程请求激活指定进程时，会发生激活。2.2.4进程的挂起和激活2进程的激活(3)激活原语active()激活过程1)激活原语将进程从外存调入内存。2)检查该进程的现行状态并进行相应操作(静止就绪→活动就绪；静止阻塞→活动阻塞)。3)假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，检查是否要进行重新调度，即比较被激活进程与当前进程的优先级，决定处理机归属。2.2.4进程的挂起和激活2.3进程互斥一组并发进程之间可能是交往的也可能是无关的。无关的并发进程是指它们分别在不同的变量集合或资源上操作，所以一个进程的执行与其他进程的进展无关，即一个并发进程不会改变另一个并发进程的变量值。

然而交往的并发进程它们共享某些变量或资源，所以一个进程的执行可能影响其他进程的结果，因此这种交往必须是有控制的，否则会出现不正确的结果。叫作与时间有关的错误。2.3.1与时间有关的错误为了保证共享资源的并发进程正确地操作，引进互斥技术来保证并发进程不同时进入这个特别的区域，或者说不让他们同时访问共享变量或资源。这个涉及到共享变量或资源的区域称为临界区。一次只能供一个进程使用的资源被称为临界资源，访问临界资源的那段程序被称为临界区。多个进程访问公共变量时，当一个进程正在进行访问时，就不允许其他进程对该临界资源访问，它们必须互斥地使用这个临界资源，这种约束关系叫做互斥。2.3.2互斥的概念互斥访问应遵循准则：1)不能假设各并发进程的相对执行速度。即各并发进程享有平等的、独立的竞争共有资源的权利，且在不采取任何措施的条件下，在临界区内任一指令结束时，其他并发进程可以进入临界区。2)某一时间，只能有一个进程在临界区内执行。3)并发进程中的某个进程不在临界区时，它不阻止其他进程进入临界区。4)并发进程中的若干个进程申请进入临界区时，只能允许一个进程进入。5)并发进程中的某个进程申请进入临界区时开始，应在有限时间内得以进入临界区。2.3.2互斥的概念临界区？临界资源？直接制约？间接制约？互斥？同步？2.3.2互斥的概念临界区？临界资源？直接制约？间接制约？互斥？同步？要实现互斥，一种可能的办法是对临界区加锁以实现互斥。当某个进程进入临界区之后锁上临界区，直到它退出临界区时再开锁。并发进程在申请进入临界区时，首先测试该临界区是否是上锁的。单CPU环境下，可能会陷入循环测试（忙等）。2.3.3互斥的加锁实现2.4进程同步异步环境：相互合作的一组并发进程，其中每一个进程都以各自独立的、不可预知的速度向前推进；但它们又需要密切合作，以实现共同的任务。直接制约：一组在异步环境下的并发进程，当各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。同步：把因直接制约而互相发送消息、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。2.4.1同步切菜机和洗菜机之间的相互制约、相互等待的合作关系就是典型的同步关系。同步机制应遵循的规则：空闲让进；忙则等待；有限等待；让权等待。2.4.2同步的例子：流水作业互斥和同步的区别前面的互斥算法都存在问题，需要一个地位高于进程的管理者来解决公有资源的使用问题。操作系统可从进程管理者的角度来处理互斥的问题，信号量就是操作系统提供的管理公有资源的有效手段。十字路口带计时器的信号灯就是典型的信号量。在操作系统中，信号量sem是一整数。2.4.3信号量机制1整型信号量机制最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作wait(S)和signal(S)来访问。这两个操作一直被分别称为P、V操作。wait和signal操作可描述为：Voidwait(S){ whileS≤0dono-op; S=S-1;} 2.4.3信号量机制Voidsignal(S){S:=S+1;} 2记录型信号量机制(1)记录型信号量的出现尽管整型信号能够实现进程之间的同步，但是，代价是巨大的，缺陷是进程出现了“忙等”的现象，原因是该机制不能完全遵循同步机制应遵循的规则。以此为思路，提出记录型信号量机制，解决进程“忙等”问题，从而使得该机制能够完全遵循同步机制应遵循的规则。 2.4.3信号量机制(2)记录型信号量的P、V操作1)P原语操作的主要动作是：sem减1；若sem减1后仍大于或等于零，则进程继续执行；若sem减1后小于零，则该进程被阻塞到与该信号相对应的阻塞队列中，然后转向进程调度。2.4.3信号量机制(2)记录型信号量的P、V操作2)V原语操作的主要动作是：sem加1；若相加结果大于零，则进程继续执行；若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转向进程调度。2.4.3信号量机制2记录型信号量机制(3)记录型信号量的实现在记录型信号量机制中，1）需要一个用于代表资源数目的整型变量value(资源信号量)。2）需要一个用于链接上述的所有等待进程的进程链表L。记录型信号量是由于它采用了记录型的数据结构而得名的。 2.4.3信号量机制Pascal语言描述Typesemaphore=recordvalue:integer;L:listofprocess;End C语言描述Structsemaphore{intvalue;semaphoreL;};2.4.3信号量机制Procedurewait(S)varS:semaphore;begin S.value:=S.value-1;ifS.value＜0thenblock(S,L);end

Proceduresignal(S)varS:semaphore;beginS.value:=S.value+1;ifS.value≤0thenwakeup(S,L);end2.4.3信号量机制(4)记录型信号量机制的wait()和signal()操作put（s）{wait（empty）；wait（mutex）；put‘s’intotheemptyplace;signal（mutex）；signal（full）;get（s）{wait（full）；wait（mutex）；get‘s’fromthefullplace;signal（mutex）；signal（empty）;【实例】在笼子上互斥地执行放入/拿出操作intempty=1;intmutex=1;intfull=0;items;3AND型信号量机制(1)信号量机制存在的问题上述的进程互斥问题，是针对并发进程之间共享一个临界资源而言的。在有些应用场合，一个进程需要获得两个或两个以上的资源才能执行。判定：继续采用记录型信号量，是否可能会出现死锁。回答：是。（why？？？） 2.4.3信号量机制3AND型信号量机制(2)AND同步机制的基本思想将进程在整个运行过程中需要的所有资源，一次性全部地分配给进程，待进程使用完后再一起释放。只要有一个资源未分配给进程，其他所有可能为之分配的资源，也不分配给他。亦即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。由死锁理论可知，这样就可避免上述死锁情况的发生。 2.4.3信号量机制3AND型信号量机制(3)AND同步机制的实现基于以上分析，在wait操作中，增加了一个“AND”条件，故称为AND同步，或称为同时wait操作，即Swait(Simultaneouswait)。教材：p34 2.4.3信号量机制4信号量集(1)信号量集的必要性在记录型信号量机制中wait(s)或signal(s)操作仅能对信号量实施加1或减1操作，意味着每次只能获得或释放一个单位的临界资源。而当一次需要N个某类临界资源时，需要进行N次wait(s)操作。显然这很低效。此外，在有些情况下当资源数量低于某一阈值时，不予分配，因此在每次分配时要测试该资源的数量，是否大于阈值。基于上述两点，对AND信号量加以扩展，形成一般化的“信号量集”机制。 2.4.3信号量机制4信号量集(2)信号量集机制的形式化描述swait(Si,ti,di)变量描述：Si：可用资源数；ti：阈值；di：申请资源数。教材：p35 2.4.3信号量机制2.4.3信号量机制表2-1信号量机制比较

整型记录型AND型信号量集备注种类数11NN1)记录型是AND的特殊情况;2)AND型是信号量集的特殊情况数量111M特点整型信号量循环测试不支持让权等待2.5经典进程的同步问题1问题描述生产者-消费者模型(Producer-ConsumerModel，PCM)是6大并行算法模型之一，常用来讨论并发程序和并发控制问题。生产者-消费者描述的是有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。在生产者-消费者模型中，既有生产者或消费者自身进程的并发，又有生产者和消费者之间的并发，具备并发程序的典型特征。 2.5.1生产者-消费者问题

PCM为使生产者进程和消费者进程并发进行，在它们之间设置了一个具有多个缓冲区的缓冲池，生产者进程可以将其所生产的产品放入一个缓冲区中，消费者进程可以从一个缓冲区中取得产品去消费。尽管所有的生产者进程和消费者进程都是以异步方式运行的，但它们之间必须保持同步，即不允许消费者进程从空缓冲区中取产品；也不允许生产者进程向满缓冲区中放产品。由于生产者—消费者问题是相互合作的进程关系的一种抽象，因此，该问题有很大的代表性及实用价值。生产者—消费者问题即theProducer-ConsumerProblem，简称PC问题。 1问题描述我们可利用一个数组来表示上述的具有n个(0，1，…，n-1)缓冲单元的缓冲区。用输入指针in作写指针，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out作读指针，每当消费者进程取走一个产品后，输出指针加1。由于缓冲区通常被组织成循环队列，故应把写指针加1表示成in：=(in+1)modn；读指针加1表示成out：=(out+1)modn。当(in+1)modn=out时表示缓冲区满；而in=out则表示缓冲区空。此外，还引入了一个整型变量counter,其初始值为0。每当生产者进程向缓冲区中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。 2问题分析生产者和消费者两进程共享下面的变量：intn,buffer[n];intin,out;//in∈[0,n-1],out∈[0,n-1]intcount;//count∈[0,n] 3利用整型信号量解决PC问题

voidproducer() {produceaniteminnextp;while(counter)=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;}; voidconsumer(){whilecounter=0dono-op;nextc:=buffer[out];out:=(out+1)modn;counter:=counter-1;consumertheiteminnextc;};3利用整型信号量解决PC问题设生产者和消费者之间的公用缓冲区有n个缓冲单元。利用互斥信号量mutex实现诸进程对缓冲区的互斥访问；信号量empty表示缓冲区中空缓冲单元的个数，Full表示满缓冲区中产品的个数。这些生产者和消费者之间存在同步关系，只要缓冲区未满，生产者便可将数据写入缓冲区；只要缓冲区未空，消费者便可从缓冲区中取走一个数据。 4利用记录型信号量解决PC问题

intmutex=0,empty=n,full=0;intbuffer[n];intin=0,out=0;Voidproducer(){ Produceranitem,nextp;wait(empty); wait(mutex); Buffer(in)=nextp;In=(in+1)modn;Ssignal(mutex); Ssignal(full);}

Voidconsumer(){wait(full);wait(mutex);nextc=buffer(out);out=(out+1)modn;signal(mutex);signal(empty);consumenextc;}4利用记录型信号量解决PC问题首先，在每个程序中用于实现互斥的wait(mutex)和signal(mutex)必须成对地出现；其次，对资源信号量empty和full的wait和signal操作，同样需要成对地出现，但它们分别处于不同的程序中。例如，wait(empty)在生产者进程中，而signal(empty)则在消费者进程中，生产者进程若因执行wait(empty)而阻塞，以后将由消费者进程通过执行Signal(empty)将它唤醒；最后，在每个程序中的多个wait操作顺序不能颠倒。应先执行对资源信号量的wait操作，然后再执行对互斥信号量的wait操作，否则可能引起进程死锁。 PC问题注意事项

Voidproducer(){produceranitem,nextp;swait(empty,mutex);buffer(in)=nextp;in=(in+1)modn;ssignal(mutex,full);}

Voidconsumer(){swait(full,mutex);nextc=buffer(out);out=(out+1)modn;ssignal(mutex,(empty);consumenextc;}5利用AND信号量解决PC问题一个数据文件或数据对象，可以被多个进程共享。其中有些进程要求读，这些进程叫做读进程；而另一些进程要求写或修改，这些进程叫写进程。

2.5.2读者-写者问题“读者—写者”问题是现代操作系统中经典的进程同步互斥问题，在以C/S模式为代表的多进(线)程通信系统都可以作为该模型的不同表现形式，有着广泛的应用。该问题首先在1971年由Courtois等人解决。该问题描述如下：一个数据文件或记录可被多个进程所共享，我们将其中只要求读该文件的进程称为读者，即“Reader进程”，其他进程称为写者，即“Writer进程”。多个Reader进程和多个Writer进程在某个时间段内对该文件资源进行异步操作，也就是说允许多个进程同时读一个共享对象，但绝不允许一个Writer进程和其他Reader进程或Writer进程同时访问共享对象。

1问题描述因此，所谓“读者—写者问题”就是指必须保证一个Writer进程和其他进程(Writer进程和Reader进程)互斥地访问共享对象的同步问题。两者的读写操作限制如下：写—写互斥，即不允许多个写者同时对文件进行写操作；读—写互斥，即不允许读者和写者同时对文件分别进行读写操作；读—读允许，即允许多个读者同时对文件进行读操作。

1问题描述intrmutex=1,wmutex=1，readcount=0；//初始化VoidReade(){dowhile(true){wait(rmutex);//各读者互斥地通过门禁，进入读书室//第1个读者进入读书室时需要开启禁止写者进入的信号ifreadcount=0thenwait(wmutex);Readcount=Readcount+1;signal(rmutex);performreadoperation;//读者阅读，此时进行的读操作无需互斥

2利用记录型信号量解决读者-写者问题//以下为离开读书室wait(rmutex);//互斥地通过门禁，离开读书室readcount=readcount-1;//最后1个读者离开读书室时需要关闭禁止写者进入的信号ifreadcount=0thensignal(wmutex);signal(rmutex);}} 2利用记录型信号量解决读者-写者问题intrmutex=-1,wmutex=1；intreadcount=0;VoidReader() { dowhile(true){ Swait(L,1,1，mx,1,0); performreadoperation;Ssignal(L,1);} } 3利用信号量集机制解决读者-写者问题Voidwriter(){dowhile(true){Swait(mx,1,1;0,L,0);performwriteoperation;Ssignal(mx,1);}}【实例2-5】

（a）b）图2-6

读者-写者问题在生活中的实例（a）大学校门的门禁系统（b）地铁入口的门禁系统

有五个哲学家，他们的生活方式是交替地进行思考和进餐。哲学家们共用一张圆桌，分别坐在周围的五张椅子上。在圆桌上有五个碗和五支筷子，平时哲学家进行思考，饥饿时便试图取用其左、右靠他最近的筷子，只有当他拿到两支筷子时才能进餐。进餐完毕，放下筷子又继续思考。哲学家问题的实现，请参照教材，自主学习。2.5.3哲学家进餐问题2.6管程机制信号量机制是一种方便而有效的进程同步机制，但每个要访问临界资源的进程须自备wait和signal操作。这样不仅给系统管理造成麻烦，而且还会因同步操作使用不当而导致死锁，甚至产生与时间有关的错误。2.6.1管程的引入可能出现的错误：1)颠倒wait和signal操作导致临界资源被同时访问；2)signal误写为wait操作，导致任何进程无法访问临界资源，发生死锁；3)遗漏wait操作会导致多个进程同时访问临界资源，遗漏signal则导致其他进程无法进入临界区。基于以上情况，1971年Dijkstra提出了秘书“进程”机制。1973年Hansan和Hoare又将“秘书”进程思想发展为“管程”概念，把并发进程间的同步操作分别集中在相应的管程中。2.6.1管程的引入1管程的定义需要为管程赋予一个名字。另外，形式上，管程的结构和面向对象程序设计技术中的类是类似的。管程和类的比较，如表2-2所示。表2-2管程和类的结构比较2.6.2管程的基本概念管程（Monitor）类（Class）共享数据（变量申明）成员变量的申明操作过程（过程的定义）成员函数的定义数据初始值的设定（初始化）成员变量的初始化1管程的定义(1)管程由三部分组成1)局部于管程的共享变量说明。2)对该数据进行操作的一组过程。3)对局部于管程的数据设置初始值的语句。2.6.2管程的基本概念(2)管程的定义typemonitor-name=monitor//第一部分变量申明variabledeclarations//第二部分过程定义procedureentryP1(…)begin…end;procedureentryP2(…)begin…end;…procedureentryPn(…)begin…end;//第三部分初始化代码begininitializationcode;end2.6.2管程的基本概念2条件变量在管程机制中，引起进程等待的原因可能很多，为了区别它们，有引入了条件变量condition。管程中对每个条件变量，都须予以说明，其形式为Varx,y:condition。该变量应置于wait和signal之前，即可表示为X.wait和X.signal。2.6.2管程的基本概念1基本思想利用管程方法来解决生产者-消费者问题时，首先便是为它们建立一个管程，并命名为Proclucer-Consumer，或简称为PC。其中包括两个过程：1)put(item)过程。生产者利用该过程将自己生产的产品投放到缓冲区中，并用整型变量count来表示在缓冲区中已有的产品数目，当count≥n时，表示缓冲区已满，生产者须等待。2)get(item)过程。消费者利用该过程从缓冲区中取出一个产品，当count≤0时，表示缓冲区中已无可取用的产品，消费者应等待。2.6.3利用管程解决PC问题2管程描述//管程producer-consumer的定义typeproducer-consumer=monitor//变量申明varin,out,count:integer;buffer:array[0..n-1]ofitem;notfull,notempty:condition;2.6.3利用管程解决PC问题//put()过程定义procedureentryput(item)beginifcount≥nthennotfull.wait;buffer(in):=nextp;in:=(in+1)modn;count:=count+1;ifnotempty.queuethennotempty.signal;end2.6.3利用管程解决PC问题//get()过程定义procedureentryget(item)beginifcount≤0thennotempty.wait;nextc:=buffer(out);out:=(out+1)modn;count:=count-1;ifnotfull.quenethennotfull.signal;end//变量初始化beginin:=out:=0;count:=0;end2.6.3利用管程解决PC问题3生产者和消费者进程描述在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;end2.6.3利用管程解决PC问题consumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end2.7进程通信进程通信，是指进程之间的信息交换，其所交换的信息量大小不一。一般来说，进程间的通信根据通信的内容可以划分为两种：控制信息的传送与大批量数据传送。低级进程通信：进程之间的互斥和同步，由于其所交换的信息量少而被归结为低级通信。信号量机制在通信方面的缺点：1)效率低；2)通信对用户不透明。2.7进程通信高级进程通信是指用户可直接利用操作系统所提供的一组通信命令，高效地传送大量数据的一种通信方式。操作系统隐藏了进程通信的细节。或者说，通信过程对用户是透明的。这样，就大大减少了通信程序编制上的复杂性。2.7进程通信1共享存储器系统在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。可分为两类。(1)基于共享数据结构的通信方式 在该方式下，要求诸进程公用某些数据结构，借以实现诸进程间的信息交换。如生产者—消费者问题中有使用有界缓冲区这种数据结构来实现通信的。(2)基于共享存储区的通信方式 2.7.1进程的通信类型1共享存储器系统在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。可分为两类。(1)基于共享数据结构的通信方式(2)基于共享存储区的通信方式 为了传输大量数据，在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。这种方式属于高级通信。2.7.1进程的通信类型2消息传递系统消息传递机制是使用最广泛的一种进程间通信的机制。程序员直接利用系统提供的一组通信命令(原语)进行通信。操作系统隐藏了通信的细节，简化了通信程序的编制。3管道通信管道是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。图2-7所示为管道示意图。2.7.1进程的通信类型3管道通信管道是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。图2-7所示为管道示意图。2.7.1进程的通信类型图2-7管道示意图在进程之间通信时，源进程可以直接或间接地将消息传送给目标进程，由此将进程通信分为直接通信和间接方式。1直接通信方式直接通信方式指发送进程利用OS所提供的发送命令，直接把消息发送给目标进程。此时，要求发送进程和接收进程都以显式方式提供对方的标识符。2.7.2消息传递系统的实现方法1直接通信方式通常，系统提供下述两条通信命令(原语)：1)发送原语：Send（Receiver,message)；发送一个消息给接收进程2)接收原语：Receiv