进程管理-课件

第二章进程管理1进程的基本概念2进程控制3进程同步4经典进程同步问题5管程机制6进程通信7线程第二章进程管理1进程的基本概念1进程的基本概念操作系统的特性之一是并发与共享，即在系统(内存)中同时存在几个相互独立的程序，这些程序在系统中既交叉地运行，又要共享系统中的资源，这就会引起一系列的问题，包括：对资源的竞争、运行程序之间的通信、程序之间的合作与协同等。要解决这些问题，用程序的概念已经不能描述程序在内存中运行的状态，必须引人新的概念－－进程。1进程的基本概念操作系统的特性之一是并发与共享，即在系统(前趋图(PrecedenceGraph)是一个有向无循环图，记为DAG(DirectedAcyclicGraph)，用于描述进程之间执行的前后关系。图中每个结点可用于描述一条语句、一个程序段或进程结点间的有向边则表示在两结点之间存在的偏序或前趋关系“→”，→={（Pi，Pj）|PimustcompletebeforePjmaystart}如果（Pi，Pj）∈→，可写成Pi→Pj；，称Pi是Pj的直接前趋，而Pj是Pi的直接后继。在前趋图中，没有前趋的结点称为初始结点(InitialNode)

，没有后继的结点称为终止结点(FinalNode)

。2.1.1前趋图S1→S2→S3前趋图(PrecedenceGraph)是一个有向无循环图

每个结点还可具有一个重量(Weight)，用于表示该结点所含有的程序量或结点的执行时间。前趋图P1P3P8P9P4P2P5P6P7S1S2S3(a)具有九个结点的前趋图(b)具有循环的有向图每个结点还可具有一个重量(Weight)，用于图2－l示出的前趋图，存在下面的前趋关系：P1→P2,P1→P3，P1→P4，P2→P5，P3→P5，P4→P6,P5→P7，P6→P7或表示为：P={P1,P2,P3,P4,P5,P6,P7}→={(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P5，P7)，(P6，P7)}注意：前趋图中必须不存在循环。2.1.1前趋图图2－l示出的前趋图，存在下面的前趋关系：注意：前趋图中必须一、概念一个程序由若干个程序段组成，在各程序段之间，必须按照某种先后次序顺序执行，仅当前一(程序段)执行完后，才能执行后继操作。这种程序执行的方式就称为程序的顺序执行。例如：2.1.2程序的顺序执行一、概念2.1.2程序的顺序执行1.顺序性 处理机严格按照程序所规定的顺序执行，即每个操作必须在下一个操作开始之前结束。2.封闭性 程序一旦开始执行，其执行结果不受外界的影响。3.可再现性 程序执行的结果与初始条件有关，而与执行时间无关。二、程序顺序执行的特点1.顺序性二、程序顺序执行的特点例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、处理、输出，即Ii,Ci,Pi(i=1,2,...,n)。这些作业在系统中执行时是对时间的偏序，有些操作必须在其它操作之前执行，这是有序的，但有些操作是可以同时执行的。例如:I1、C1、P1的执行必须严格按照I1，C1，P1的顺序，而P1与I2，C1与I2,I3与P1是可以同时执行的。图中存在下面的前趋关系：Ii→Ci,Ii→Ii＋1,Ci→Pi,Ci→Ci＋1,Pi→Pi＋1而Ii＋1和Ci及Pi－1是重迭的，它们可以并发执行。2.1.3程序的并发执行及其特征并发执行时的前趋图例：在系统中有n个作业，每个作业都有三个处理步骤，输入数据、例如:对于具有下列四条语句的程序段：S1:a:=x+2;S2:b:=y+4;S3:c:=a+b;S4:d:=c+8;其前趋图如右图。其中S1和S2可以并发执行。2.1.3程序的并发执行及其特征例如:2.1.3程序的并发执行及其特征程序并发执行（定义）若干个程序段同时在系统中运行，这些程序的执行在时间上是重迭的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重迭是很小的，也称这几个程序段是并发执行的。2.1.3程序的并发执行及其特征程序并发执行（定义）2.1.3程序的并发执行及其特征程序并发执行的描述：

parbeginS1;S2;S3;...;SNparend; Si(i=1,2,3,...,n)表示n个语句（程序段），这n个语句用parbegin和parend括起来表示这n个语句是可以并发执行的。这是Dijkstra提出的。2.1.3程序的并发执行及其特征程序并发执行的描述：2.1.3程序的并发执行及其特征假设有一个程序由S0～Sn+1个语句，其中S1～Sn语句是并发执行的，程序如下：

S0;parbeginS1;S2;S3;...;SNparend;Sn+1;2.1.3程序的并发执行及其特征假设有一个程序由2.1.3程序的并发执行及其特征程序并发执行时的特征1、间断性(执行—暂停—执行)2、失去了程序的封闭性3、不可再现性(失去封闭性引起)2.1.3程序的并发执行及其特征程序并发执行时的特征2.1.3程序的并发执行及其特征

例如，有两个循环程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N∶=N+1操作；程序B每执行一次时，都要执行Print(N)操作，然后再将N置成“0”。程序A和B以不同的速度运行。可能出现以下三种情形：

(1)N∶=N+1在Print(N)和N∶=0之前，此时得到的N值分别为n+1,n+1,0。

(2)N∶=N+1在Print(N)和N∶=0之后，此时得到的N值分别为n,0,1。

(3)N∶=N+1在Print(N)和N∶=0之间，此时得到的N值分别为n,n+1,0。结论：程序在并发执行时，由于失去了封闭性，其计算结果与并发程序的执行速度有关，使程序执行失去可再现性。例如，有两个循环程序A和B，它们共享一个变量N

进程的特征与状态在单道程序设计环境下，CPU被一道程序独占，CPU严格按程序的指令顺序来执行，程序具有顺序性、封闭性和可再现性特征。在多道程序设计的环境下，系统中有多个程序同时运行。此时的程序具有间断性、失去了程序的封闭性、不可再现性等特征。程序一旦运行起来，它不但与程序本身有关，而且与它运行时所处的运行环境有关，程序的活动不再是静态的、封闭的，而显现出并发性、动态性以及相互制约的关系。所以用程序的概念已经不能描述上述这些特征，于是引入进程的概念。进程的概念来自于麻省理工的MULTICS、IBM的TSS/360，在IBM的OS/360/370系统中也曾叫过任务(task)。进程的特征与状态在单道程序设计环境下，CPU被一道程序独占进程的特征（1）结构特征：从结构上看，进程实体是由程序段、相关的数据段和进程控制块(PCB，processcontrolblock)三部分组成。（2）动态性：进程的实质是进程实体的一次执行过程，它有着创建、活动、暂停、终止等过程，具有一定的生命期，是动态地产生、变化和消亡的。（3）并发性：多个进程实体同存于内存中，且能在一段时间内同时运行。（4）独立性：进程实体是一个能独立运行、独立分配资源和独立接受调度的基本单位。（5）异步性：各个并发进程按照各自独立的、不可预知的速度向前推进。2.1.4进程的特征与状态进程的特征2.1.4进程的特征与状态行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为进程（Dijkstra)。进程是这样的计算部分，它是可以和其它计算并行的一个计算。(Donovan)进程（有时称为任务）是一个程序与其数据一道通过处理机的执行所发生的活动。（Alan.C.Shaw)进程是执行中的程序。（KenThompsonandDennisRitchie)教材上给出的进程的定义：

进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。进程的定义行为的一个规则叫做程序，程序在处理机上执行时所发生的活动称为1、程序是指令的集合，是静态的概念。进程是程序在处理机上的一次执行过程，是动态的概念。程序可以作为软件资料长期保存。进程是有生命周期的。2、进程是一个独立的运行单位，能与其它进程并发活动。而程序则不是。3、进程是竞争计算机系统有限资源的基本单位，也是进行处理机调度的基本单位。4、一个程序可以作为多个进程的运行程序，一个进程也可以运行多个程序。进程与程序的区别与联系1、程序是指令的集合，是静态的概念。进程是程序在处理机上的例子：光盘（CD、VCD）光盘（程序）放光盘的活动（进程）进程与程序的区别与联系例子：光盘（CD、VCD）进程与程序的区别与联系进程在系统中的活动规律是：执行暂停执行(间断性)进程的三种基本状态：

就绪状态

执行状态

阻塞状态（又称等待，睡眠）进程的三种基本状态进程在系统中的活动规律是：进程的三种基本状态就绪状态(Ready)若进程已具备了运行条件，只因CPU被别的进程占用而不能被CPU执行，则称此时进程处于就绪状态。一旦把CPU分配给它，该进程就可以运行。从宏观上讲，它是一种逻辑上的可运行状态。系统中处于就绪状态的进程可能有多个，通常将它们按某种策略（优先级）排成一个队列，称为就绪队列。进程的三种基本状态就绪状态(Ready)进程的三种基本状态执行状态(Running）当一个进程已分配到CPU，它的程序正在被CPU执行时进程所处的状态称执行状态，也称为运行状态。对于单CPU系统而言，处于执行状态的进程只可能有一个，多处理机系统中则有多个。进程的三种基本状态执行状态(Running）进程的三种基本状态阻塞状态(Wait)正在执行的进程因等待某种事件的发生而暂时不能运行便放弃CPU的状态称阻塞状态(等待状态)，例如，等待输入/输出、等待进程间的同步/互斥等。一旦引起等待的原因消失，进程便转为就绪状态。以便在适当的时候占用CPU。系统中处于等待状态的进程可能有多个，通常也将它们排成一个队列。有的系统按照进程不同的等待原因，把处于等待状态的进程排成多个队列。进程的三种基本状态阻塞状态(Wait)进程的三种基本状态1．就绪状态→执行状态2．执行状态→阻塞状态3．执行状态→就绪状态4.阻塞状态→就绪状态时间片完进程状态的转换：进程的三种基本状态的转换进程的动态性决定了它不会固定处于某个状态，系统中的进程由于各种不同的原因在以上各个状态之间变化。其状态变化及原因如图所示。1．就绪状态→执行状态时间片完进程状态的转换：进程的三种基本创建（新）状态和终止状态（1）创建（新）状态：一个进程刚刚建立，但还未将它插入就绪队列时的状态。（2）终止状态：一个进程已经正常结束或异常结束，OS已将它从就绪队列中移出，但尚未将它撤消时的状态。创建（新）状态和终止状态（1）创建（新）状态：一个进程刚刚进程状态的转换1．创建(新)状态→就绪状态2．就绪状态→执行状态3．执行状态→阻塞状态4．执行状态→就绪状态5．执行状态→终止状态6．阻塞状态→就绪状态

时间片完进程状态变迁图进程状态的转换时间片完进程状态变迁图进程的挂起状态

使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，我们把这种静止状态称为挂起状态(静止状态)。

引入挂起状态的原因有：

1．终端用户的需要终端用户在自己的程序运行期间发现有可疑问题，希望暂时使自己的程序静止下来。

2．父进程请求父进程希望挂起自己的子进程，以便考查和修改子进程，或协调子进程的活动。

3．负荷调节的需要当实时系统中的负载较重，影响到实时任务的执行，可挂起不重要进程，保证系统正常运行。

4．操作系统的需要操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记帐。进程的挂起状态使正在执行的进程暂停执行；若此时用户进程带有挂起状态时的进程状态转换

所谓原语就是计算机机器指令的延伸，它是由若干条机器指令构成，并完成一种特定功能的程序段。原语操作由操作系统内核提供。为保证原语操作的正确性，还规定原语在执行期间必须一次执行完，中间不允许被中断。也就是说，原语具有原子性，即原语操作中的所有指令（动作）要么全做，要么全不做，不允许被分割。在单CPU系统中，在执行原语的过程中一般要关中断。带有挂起状态时的进程状态转换所谓原语就是计算机机器指令的延1．活动就绪→静止就绪：当进程处于未被挂起的就绪状态时，称此为活动就绪状态，表示为Readya，此时进程可被调度。当用挂起原语Suspend将该进程挂起后，该进程便转变为静止就绪状态，表示为Readys。 处于Readys状态的进程，不再被调度执行。2．活动阻塞→静止阻塞：当进程处于未被挂起的阻塞状态时，称为它处于活动阻塞状态，表示为Blockeda。当用Suspend原语将它挂起后，进程便转变为静止阻塞状态，表示为Blockeds。 处于该状态的进程，在其所期待的事件出现后，它将从静止阻塞变为静止就绪。带有挂起状态时的进程状态转换

1．活动就绪→静止就绪：带有挂起状态时的进程状态转换3．静止就绪→活动就绪：处于Readys状态的进程，若用激活原语Active激活后，该进程将转变为Readya状态。4．静止阻塞→活动阻塞：处于Blockcds状态的进程，若用激活原语Active激活后，进程将转变为Blockeda状态。带有挂起状态时的进程状态转换

3．静止就绪→活动就绪：带有挂起状态时的进程状态转换具有挂起状态的进程状态图带有挂起状态时的进程状态转换

时间片完调度具有挂起状态的进程状态图带有挂起状态时的进程状态转换时间具有创建、终止和挂起状态的进程状态图带有挂起状态时的进程状态转换

创建许可许可终止释放时间片完调度具有创建、终止和挂起状态的进程状态图带有挂起状态时的进程状在系统中一个进程存在：

进程控制块PCB(ProcessControlBlock)(记录型数据结构)

进程的执行程序(一个可执行文件)进程执行时所需的数据进程总是位于某个队列(就绪、阻塞某事件队列)

处于某种状态（执行、就绪、阻塞）占用某些系统资源（内存，打开某些文件、处理机、外设）进程控制块在系统中一个进程存在：进程控制块PCB中记录了操作系统所需的、用于描述进程的当前情况及控制进程运行所需的全部信息。进程标识符用于惟一标识一个进程。内部标识符操作系统为每一个进程赋予一个惟一的数字标识符(进程的序号)外部标识符由创建者提供，由字母、数字组成。为了描述进程的家族关系，还应设置父进程标识及子进程标识。还可设置用户标识。处理机状态信息由处理机的各种寄存器(通用寄存器、指令计数器、程序状态字PSW、用户栈指针)中的内容组成。进程控制块中的信息PCB中记录了操作系统所需的、用于描述进程的当前情况及控制进3.进程调度信息包括进程状态、进程优先级、进程调度所需的其它信息(与所采用的进程调度算法有关，如进程已等待CPU的时间总和、进程已执行的时间总和等)、事件(进程由执行状态转变为阻塞状态所等待发生的事件)。4.进程控制信息包括程序和数据的地址(进程的程序和数据所在的内存或外存地址)、进程同步和通信机制、资源清单(除CPU以外的、进程所需的全部资源及已经分配到该进程的资源的清单)、链接指针等。进程控制块中的信息3.进程调度信息包括进程状态、进程优先级、进程调度所需的其进程控制块PCB的作用是使一个多道环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个与其它进程并发执行的进程。操作系统是根据PCB来对并发执行的进程进行控制和管理的。可以说PCB是进程存在的惟一标志。当进程被创建时，系统要为其建立一个PCB，在进程的整个生命期内系统利用该PCB对其进行控制，进程运行结束后要回收其PCB。(户口)由于PCB经常被系统访问，故PCB应常驻内存。系统将所有的PCB组织成若干个链表(或队列)，存放在操作系统中专门开辟的PCB区内。进程控制块的作用进程控制块PCB的作用是使一个多道环境下不能独立运行的程序(进程控制块的组织方式1)线性方式 即将系统中所有的PCB都组织在一张线性表中，将该表的首地址存放在内存的一个专用区域中。该方式实现简单、开销小，但每次查找时都需要扫描整张表，因此适合进程数量不多的系统。PCB1PCB2PCB3…PCBn进程控制块的组织方式1)线性方式PCB1PCB2PCB3…P进程控制块的组织方式2)链接方式 系统把所有进程的PCB按其状态实行分类管理，每一类用一个队列来管理。一般来说，系统中的进程队列可分为三类，即就绪队列、若干个阻塞队列(根据阻塞原因的不同把处于阻塞状态的进程的PCB排成不同的队列)和空白队列。进程控制块的组织方式2)链接方式进程控制块的组织方式3)索引方式系统根据所有进程的状态建立几张索引表(就绪索引表、阻塞索引表等)，并把各索引表在内存的首地址记录在内存的一些专用单元中。在每个索引表的表目中，记录具有相应状态的某个PCB在PCB区中的地址。进程控制块的组织方式3)索引方式进程控制用于创建一个新进程，终止一个已完成的进程，或去终止一个因出现某事件而使其无法运行下去的进程，还可负责进程运行中的状态转换。进程控制一般由操作系统内核来实现。在操作系统内核中，有一组程序专门用于完成对进程的控制。进程控制包括：

进程创建、

进程终止、

进程阻塞、

进程唤醒、进程挂起、进程激活2.3进程控制这些操作都要对应地执行一个特殊的程序段（操作系统核心程序），同时系统也通过系统调用(称为原语，一种特殊的系统调用)给用户提供进程控制的功能。进程控制用于创建一个新进程，终止一个已完成的进程，或去终止一进程图(ProcessGraph)是用于描述一个进程的家族关系的有向树。一个进程可以通过创建原语产生一个新进程在进程Pi创建了进程Pj之后，称Pi是Pj的父进程(ParentProcess),Pj

是Pi的子进程(ProgenyProcess)。用一条由进程Pi指向进程Pj的有向边来描述它们的父子关系。创建父进程的进程称为祖先进程。这样便形成了一棵进程树，树的根结点作为进程家族的祖先(Ancestor)。进程树的特点：资源分配严格，子进程可以继承父进程所拥有的资源；当子进程被撤消时，应将其从父进程那里获得的资源归还给父进程；在撤消父进程时，也必须同时撤消其所有的子进程，便于管理；系统可根据需要赋予进程不同的控制权，并可以把一个任务分解成若干个进程来完成，具有较好的灵活性；树形结构层次清晰，关系明确。进程的创建ABCDIJEKGLMHNF图2-9进程树祖先父进程子进程进程图(ProcessGraph)是用于描述一个进程的家族引起创建进程的事件

1．用户登录

2．作业调度

3．提供服务

4．应用请求由系统内核创建由应用进程自已创建进程的创建引起创建进程的事件由系统内核创建由应用进程自已创建进程的创建创建进程的主要工作是申请一个进程控制块PCB，并向其中填入进程名、优先级等有关的参数。创建进程的基本过程是：

(进程创建原语Creat())(1)申请空白PCB。从空闲的PCB集合中申请一个新的PCB，同时获得该进程的内部标识；(2)为新进程的程序和数据分配所需资源（内存、文件、I/O和CPU时间片）；(3)初始化进程控制块PCB。向该PCB中填写各种参数；(4)将新进程插入到就绪队列。把该进程的状态设置成就绪状态，并将该PCB插入到就绪队列中。进程的创建创建进程的主要工作是申请一个进程控制块PCB，并向其中填入进引起进程终止的事件

1．正常结束 进程任务已完成，退出运行。

2．异常结束在进程运行期间，由于出现异常事件而迫使进程终止。如：越界错误、保护错、非法指令、特权指令错、运行超时、等待超时、算术运算错、I/O故障等。

3．外界干预进程应外界的请求而终止运行。包括：操作员或操作系统干预、父进程请求、父进程终止。进程的终止引起进程终止的事件进程的终止进程的终止过程是：

(进程终止原语Holt())(1)根据被终止进程的标识符，从PCB集合中检索出该进程的PCB，从中读出该进程的状态。(2)若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。(3)若该进程还有子孙进程，还应将其子孙进程予以终止，以防它们成为不可控的进程。(4)将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。(5)将被终止进程(其PCB)从所在队列中移出，等待其他程序来搜集信息。进程的终止进程的终止过程是：(进程终止原语Holt())进程的终止引起进程阻塞和唤醒的事件

1．请求系统提供服务正在执行的进程请求操作系统提供服务，由于某种原因，操作系统并不立即满足该进程的要求。

2．启动某种操作进程启动某种操作后，必须在该操作完成之后才能继续执行。

3．新数据尚未到达对于相互合作的进程，如果其中一个进程需要先获得另一进程提供的数据才能运行，则只要其所需的数据尚未到达，该进程只有阻塞。

4．无新工作可做系统往往设置一些具有特定功能的系统进程，每当这种进程完成任务后，便把自己阻塞起来以等待新任务到来。正在执行的进程，当发生上述事件时，由于无法继续执行，于是进程便通过调用阻塞（等待）原语block把自己阻塞。可见，进程阻塞是进程自身的一种主动行为。进程的阻塞和唤醒引起进程阻塞和唤醒的事件进程的阻塞和唤醒进程的阻塞(等待)过程

阻塞(等待)原语block(1)进程立即停止执行，把其PCB中的现行状态由“执行”变为阻塞；

(2)将其PCB插入到相应的阻塞队列中去；

(3)转调度程序进行重新调度，将处理机重新分配给另一就绪进程，并进行切换。进程的阻塞和唤醒进程的阻塞(等待)过程阻塞(等待)原语block进程的阻塞当被阻塞进程所期待的事件出现时，如I/O完成或所期待的数据已经到达，则由有关进程(如，用完并释放了该I/O设备的进程)调用唤醒原语，将等待该事件的进程唤醒。进程的唤醒过程唤醒原语wakeup()

(1)把被阻塞进程从等待该事件的阻塞队列中移出;(2)将其PCB中的现行状态由“阻塞”变为就绪;(3)该PCB插入到就绪队列中。注意：如果在某进程中调用了阻塞原语，则必须在与之相合作的另一进程中或其他相关进程中安排唤醒原语，以能唤醒阻塞进程；否则，被进程将会因不能被唤醒而长久地处于阻塞状态。进程的阻塞和唤醒当被阻塞进程所期待的事件出现时，如I/O完成或所期待的数据已当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或者父进程请求将自己的某个子进程挂起时，系统将利用挂起原语suspend（）将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是:(1)检查被挂起进程的状态：若正处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将其改为静止阻塞。(2)为了方便用户或父进程考查该进程的运行情况，而把该进程的PCB复制到某指定的内存区域。(3)最后，如被挂起的进程正在执行，则转调度程序重新调度。进程的挂起与激活当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，当发生激活过程的事件时，如用户进程或父进程请求激活指定进程，若进程驻留在外存而内存中已有足够的空间，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active()将指定进程激活。激活原语的执行过程是：先将进程从外存调入内存，检查该进程的现行状态：若是静止就绪，便将其改为活动就绪；若为静止阻塞，便将其改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。进程的挂起与激活当发生激活过程的事件时，如用户进程或父进程请求激活指定进程，2.4进程同步

进程同步的基本概念

两种形式的制约关系在多道程序的环境中，系统中的多个进程可能存在着以下两种形式的制约关系：直接相互制约关系并发进程在一些关键点上可能需要相互等待与互通消息，比如，当某进程运行到某点时要求另一伙伴进程为它提供消息，在未得到对方的消息时，该进程必须处于等待状态，直到收到消息后被唤醒，这种进程之间的协同工作关系就是进程之间的直接相互制约关系，也称为进程同步关系。例如：输入进程A通过单缓冲向计算进程B提供数据间接相互制约关系也称为进程互斥关系，是由各进程排它性使用共享资源(如共享CPU、I/O设备等)引起的。当某进程正在访问某临界资源时，就不允许其它进程进入，否则就会发生无法估计的错误，这种关系就是进程之间的互斥关系。例如：A、B两个进程共享一台打印机2.4进程同步

进程同步的基本概念

两种形式的制约关系在多操作系统中一次仅允许一个进程访问的资源称为临界资源。例：软件临界资源有内存变量、指针、数组等等硬件临界资源有打印机、磁带机等不论是硬件临界资源，还是软件临界资源，多个进程互斥地对它进行访问。临界资源

操作系统中一次仅允许一个进程访问的资源称为临界资源。临界资源问题的描述：有一群生产者进程在生产产品，并将这些产品提供给消费者进程去消费。为使生产者与消费者进程能并发执行，在两者之间设置了一个具有n个缓冲区(每个缓冲区只能放一件产品)的缓冲池。生产者进程将它所生产的产品放入一个缓冲区中；消费者进程可从一个缓冲区中取走产品消费。分析：同步关系：生产者进程和消费者进程之间必须保持同步，即：不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。生产者进程的处理过程：生产一个产品，当要送入缓冲区时，要检查缓冲区是否已满。若未满，则可将产品送入缓冲区；否则，等待。消费者进程的处理过程：当它去取产品时，要检查缓冲区是否有产品。若有，则取走一个产品；否则，等待。例生产者－消费者问题

著名的进程同步问题临界资源

问题的描述：有一群生产者进程在生产产品，并将这些产品提供给消分析：用一个数组buffer来表示上述的具有n个(0，1，…，n-1)缓冲区的缓冲池。这里的缓冲池是组织成循环缓冲的。用输入指针in来指示下一个可投放产品的缓冲区，每当生产者进程生产并投放一个产品后，输入指针加1；用一个输出指针out来指示下一个可从中获取产品的缓冲区，每当消费者进程取走一个产品后，输出指针加1。当(in+1)modn=out时表示缓冲池满；而in=out则表示缓冲池空。引入了一个整型变量counter,其初始值为0。每当生产者进程向缓冲池中投放一个产品后，使counter加1；反之，每当消费者进程从中取走一个产品时，使counter减1。生产者和消费者两进程共享下面的变量：

intin=0,out=0,count=0; itembuffer[n];分析：Voidproducer()

//生产者程序

Repeat

produceaniteminnextp;

//nextp用于暂时存放每次刚生产出来的产品

…

whilecounter==ndono-op;

//表示重复地测试条件,no-op是一条空操作指令

bufferin[in]=nextp;

in=(in+1)%n;

counter++;

Voidconsumer()

//消费者程序

Repeatwhilecounter==0dono-op;

nextc=buffer［out］;

out=(out+1)%n;

counter--;

consumertheiteminnextc;

//nextc用于存放每次要消费的产品两者在顺序执行时其结果会是正确的，但若并发执行时，就会出现差错，问题就在于这两个进程共享变量counter。生产者对它做加1操作，消费者对它做减1操作，这两个操作在用机器语言实现时，常可用下面的形式描述：register1:=counter;register2:=counter;

register1:=register1+1;register2:=register2-1;counter:=register1;counter:=register2;假设counter的当前值是5。如果按下述顺序执行：

register1∶=

counter;(register1=5)

register1∶=

register1+1;(register1=6)

register2∶=

counter;(register2=5)

register2∶=

register2-1;(register2=4)

counter

∶=

register1;(counter=6)

counter

∶=

register2;(counter=4)

结论：变量count应作为临界资源，生产者和消费者进程互斥访问。不论是硬件临界资源，还是软件临界资源，并发进程必须互斥地对它进行访问。Voidproducer()//生产者程序两者在顺序执每个进程中访问临界资源的那段程序段称为临界区(临界段)临界区同一临界资源在多个共享它的进程中将对应多个临界区。

如果能保证诸进程互斥地进入自己的临界区，便可保证诸进程对临界资源的互斥访问。或者说：要临界资源互斥地被使用，就要保证临界区互斥地被执行。每个进程中访问临界资源的那段程序段称为临界区(临界段)临界区临界区为了保证诸进程的临界区互斥地被执行，我们把一个访问临界资源的循环进程分成以下几部分：进入区

每个进程在进入临界区之前，应先对欲访问的临界资源进行检查，看它是否正被访问，因此必须在临界区之前增加一段用于上述检查的代码，把这段代码称为进入区。临界区访问临界资源的那段程序段。退出区在临界区后面增加一段用于将临界区正被访问的标志恢复为未被访问的标志的代码，把这段代码称为退出区。剩余区进程除上述进入区、临界区、退出区之外的其它部分代码称为剩余区。临界区为了保证诸进程的临界区互斥地被执行，我们把一个访问临界可把一个访问临界资源的循环进程描述如下：While(TURE)

{

进入区临界区退出区剩余区｝临界区可把一个访问临界资源的循环进程描述如下：临界区进程互斥进入临界区的过程：临界区(1)在“进入区”判断是否可进入临界区。若可以进入，则必须设置临界区使用标志，阻止其它进程进入临界区。(2)后来的进程通过查看临界区使用标志，知道自己不能进入，就进入阻塞队列，将自己阻塞。(3)当临界区的进程退出区时，即在“退出区”修改临界区使用标志，并负责唤醒一个进程，让其进入临界区。进程互斥进入临界区的过程：临界区(1)在“进入区”判断是否可进入临界区的准则：临界区(1)每次至多有一个进程处于临界区；(2)当有若干个进程欲进入临界区时，应在有限的时间内使其进入；(3)进程在临界区内仅逗留有限的时间。进入临界区的准则：临界区(1)每次至多有一个进程处于临界区；同步机制同步机制用来协调诸进程间的运行，以实现进程互斥地进入自己的临界区。同步机制可以用软件方法，也可以用硬件方法。同步机制应遵循的规则：（1）空闲让进：无进程处于临界区内时，允许一个进程进入临界区；（2）忙则等待：已有进程进入临界区时，其他欲进入进程必须等待；（3）有限等待：对要求访问临界区的进程，应保证在有限的时间内使其进入，以免陷入“死等”状态。那么，当一进程离开临界区时，若发现有进程正在等待进入临界区，则要唤醒这些进程。（4）让权等待：当进程不能进入临界区时，应立即释放CPU，以免进程陷入“忙等”状态。同步机制同步机制用来协调诸进程间的运行，以实现进程互斥地进入信号量机制

1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制经历了四种形式：

整型信号量

记录型信号量

AND型信号量信号量集信号量机制1965年，荷兰学者Dijkstra提出的信整型信号量(互斥信号量)最初信号量S是一个整型变量，表示资源数目，除初始化外，对信号量仅能通过两个标准的原子操作(即原语)wait(s)和signal(s)来访问。这两个原子操作一直被分别称为P（s）和V(s)操作。

wait(s)和signal(s)描述为：

wait(s)：whiles<=0dono-op

s--;

signal(s)：s++;

存在的问题：在wait操作中，只要是信号量S<=0，就会不断地测试，这将使进程处于“忙等”状态。这种机制就没有遵循“让权等待”的原则。整型信号量(互斥信号量)最初信号量S是一个整型变量，表记录型信号量

记录型信号量机制，是一种不存在“忙等”现象的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的情况。为此，在信号量机制中，除了需要一个用于代表资源数目的整型变量value外，还应增加一个进程链表list，用于链接上述的所有等待进程。 记录型信号量是由于它采用了记录型的数据结构而得名的。它所包含的上述两个数据项可描述为：

typedefstruct{ intvalue;//表示系统中某类资源的数目，也称为资源信号量

structprocess_control_block*list//进程链表，用于链接等待访问同一临界资源的所有等待进程

}semaphore记录型信号量 记录型信号量机制，是一种不存在“忙等”现象wait(semaphore*s){s->value--;//表示进程请求一个单位的资源

if(s->value<0)block(s->list);

//若资源分配完毕，就调用block原语自我阻塞，放弃处理机，并插入到信号量链表s->list中}//遵循“让权等待”准则，此时s->value的绝对值表示在该信号量链表中已阻塞进程的数目。signal(semaphore*s)s->value++;//表示执行进程释放一个单位的资源

if(s->value<=0)wakeup(s->list);//若还有等待资源的进程被阻塞，则调用wakeup原语，将s->list链表中的第一个等待进程唤醒。}//若s->value的初值为1，表明只允许一个进程访问临界资源，此时的信号量转化为互斥信号量，用于进程互斥。记录型信号量wait(semaphore*s){记录型信号量在有些场合下，各进程之间要共享两个或多个共享资源(各进程一次请求两种或多种共享资源)后，方能执行其任务。假定现有进程A和B，都要访问共享数据D和E(临界资源)。因此，为D和E分别设置用于互斥的信号量Dmutex和Emutex，并令它们的初值为1。进程A和B中都包含两个对Dmutex和Emutex的操作，即：

ProcessAProcessBwait(Dmutex);wait(Emutex);

wait(Emutex);

wait(Dmutex);

若进程A和B按下述次序交替执行wait操作：

ProcessA：wait(Dmutex); Dmutex＝0

ProcessB：wait(Emutex); Emutex＝0

ProcessA：wait(Emutex); Emutex＝-1

A阻塞

ProcessB：wait(Dmutex); Dmutex＝-1

B阻塞进程A和B处于僵持状态。在无外界干预的情况下，两者都无法从此状态中解脱出来。称此时的进程A和B已进入死锁状态。显然，当进程同时要求的共享资源越多，发生死锁的可能性越大。AND型信号量机制可以解决诸进程一次请求两个或多个共享资源的问题。AND型信号量在有些场合下，各进程之间要共享两个或多个共享资源(各进程AND型信号量AND同步机制的基本思想：将进程在整个运行过程中需要的所有资源，一次性全部分配给进程，待进程使用完后再一起释放。只要尚有一个资源未能分配给进程，其它所有可能为之分配的资源，也不分配给它。也即，对若干个临界资源的分配，采取原子操作方式：要么全部分配到进程，要么一个也不分配。AND同步机制的做法：在wait操作中，增加一个“AND”条件，故称为AND同步，或称为同时wait操作(Simultaneouswait,Swait)。AND型信号量AND同步机制的基本思想：将进程在整个运行过程Swait(S1,S2,…,Sn)

ifSi≥1and

…

andSn≥1then

for(i=1;i<=n;i++)

Si--;

//表示进程请求n种资源，每种资源一个

break;

else

placetheprocessinthewaitingqueueassociatedwiththefirstSi

foundwithSi＜1,andsettheprogramcountofthisprocessto thebeginningofSwaitoperation

endif

Ssignal(S1,S2,…,Sn)

for(i=1;i<=n;i++)

Si++;

RemovealltheprocesswaitinginthequeueassociatedwithSiinto thereadyqueue.

Swait(S1,S2,…,Sn)信号量集在有些情况下，进程一次需要N个某类临界资源；当资源数量低于某一下限值时，系统不予以分配，因此，在每次分配之前，都必须测试该资源的数量，看其是否大于其下限值。基于上述两点，对AND信号量机制加以扩充，形成一般化的“信号量集机制”。信号量集在有些情况下，进程一次需要N个某类临界资源；当信号量集Swait(S1,t1,d1,…,Sn,tn,dn)

ifSi≥t1and…andSn≥tnthen

for(i=1;i<=n;i++)

Si=Si-di;

//表示进程请求n种资源，每种资源di个

endfor

else

PlacetheexecutingprocessinthewaitingqueueofthefirstSiwith

Si＜tiandsetitsprogramcountertothebeginningoftheSwaitOperation

endif

Ssignal(S1,d1,…,Sn,dn)

for(i=1;i<=n;i++)

Si=Si+di;

RemovealltheprocesswaitinginthequeueassociatedwithSiinto

thereadyqueue

endfor;信号量集Swait(S1,t1,d1,…,Sn,一般“信号量集”的几种特殊情况：

(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配。

(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S＞1时)或互斥信号量(S=1时)。

(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S≥1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。换言之，它相当于一个可控开关。一般“信号量集”的几种特殊情况：

进程P0

进程P1

进程P2 ┊

┊

┊ wait（mutex）

wait（mutex）

wait（mutex） 临界区 临界区 临界区

signal（mutex）signal（mutex）

signal（mutex） 剩余区 剩余区

剩余区 设置互斥信号量mutex的初值为1。在互斥模型中，每个进程在进入临界区时对信号量执行wait操作，待临界区执行完后执行signal操作。注：wait（mutex）和signal（mutex）必须成对出现。用wait、signal操作实现进程互斥 进程P0 进程P1 进程P2用wait、sig

进程Pa 进程Pb

┊

┊L1：wait（pro）L2：signal（Pro）

┊

┊信号量pro的初值为0。

当进程Pa执行到某点L1时，如果进程Pb没有执行过L2点，则Pa必须等待，直到Pb执行过L2点。用wait、signal操作实现同步的模型进程Pa 进程Pb用wait、signal操作实现p1(){s1；signal(a)；signal(b);}p2(){wait(a)；s2；signal(c)；signal(d);}P3(){wait(b)；s3；signal(e);}P4(){wait(c)；s4；signal(f);}P5(){wait(d)；s5；signal(g);}P6(){wait(e)；wait(f)；wait(g)；s6;}Main(){semaphorea,b,c,d,e,f,g;a.value=b.value=c.value=0;d.value=e.value=0;f.value=g.value=0;cobeginp1();p2();p3();p4();p5();p6();coend}S1S2S3S5S4S6利用信号量来描述前驱关系p1(){s1；signal(a)；signal(b);}用信号量可以很好地实现进程间的同步和互斥，但是，每个要使用临界资源的用户进程都显式的使用Wait(S)和Signal(S)同步操作来实现进程间的同步和互斥，这就使大量的Wait(S)和Signal(S)同步操作分散在各个进程中，即信号量的控制分布在整个系统中，这给系统的管理带来了麻烦。

管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可以函数库的形式实现。相比之下，管程比信号量好控制。2.4.5管程(monitor)机制用信号量可以很好地实现进程间的同步和互斥，但是管程的引入1971年，Dijkstra提出，把所有进程对某一临界资源的同步操作集中起来，构成一个所谓的“秘书”进程。凡是要访问临界资源的进程，都必须先向“秘书”报告，并由“秘书”实现诸进程的同步。1973年，Hoare和Hanson又把“秘书”的思想发展为管程的概念，把并发进程之间的同步操作分别集中于相应的管程中。其基本思想是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程是一种在程序设计级控制进程互斥与同步的机制，具有信号量的功能，且更容易使用和控制。2.4.5管程(monitor)机制(自学)管程的引入1971年，Dijkstra提出，把所有进程对某一系统中的各种硬件资源和软件资源均可用数据结构加以抽象的描述，即用少量信息和对该资源所执行的操作来表征该资源，而忽略它们的内部结构和实现细节。例如：一台打印机，可用与分配该资源有关的状态(busy和free)和对它执行请求和释放的操作，以及等待该资源的进程队列来描述。一个FIFO队列，可用其队长、队首和队尾以及在该队列上执行的一组操作来描述。2.4.5管程(monitor)机制

管程的基本概念系统中的各种硬件资源和软件资源均可用数据结构加以抽象的描述，当共享资源用共享数据结构表示时，资源管理程序可用对该数据结构进行操作的一组过程来表示。把这样一组相关的数据结构和过程一并称为管程。Hansan为管程所下的定义：一个管程定义了一个数据结构和能为并发进程所执行(在该数据结构上)的一组操作，这组操作能同步进程和改变管程中的数据。管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。2.4.5管程(monitor)机制

管程的基本概念当共享资源用共享数据结构表示时，资源管理程序可用对该数据结构管程由四部分组成：管程的名称对局部于管程的共享数据结构的说明对该数据结构进行操作的一组过程对局部于管程的共享数据设置初始值的语句2.4.5管程(monitor)机制

管程的基本概念管程由四部分组成：管程的名称2.4.5管程(monitor图2-11管程的示意图管程的结构图2-11管程的示意图管程的结构Monitormonitor_name={//管程名

sharevariabledeclarations;//共享变量说明

conddeclarations;//条件变量说明

public://能被进程调用的过程

voidP1(……)//对数据结构操作的过程

{……}voidP2(……){……}……void(……){……}……{//管程主体

initializationcode;//初始化代码

……}}

管程的语法格式Monitormonitor_name={//管程

模块化：一个管程是一个基本程序单位，可以单独编译；抽象数据类型：管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码；信息掩蔽：管程中的数据结构只能被管程中的过程访问，这些过程也是在管程内部定义的，供管程外的进程调用，而管程中的数据结构以及过程(函数)的具体实现外部不可见。为了保证管程中共享变量的数据完整性，把管程本身作为一种临界区，规定管程互斥进入；一个进程通过调用管程的一个过程进入管程。管程通常是用来管理资源的，因而在管程中应当设有进程等待队列以及相应的等待及唤醒操作。任何时侯，只能有一个进程在管程中执行，调用管程的任何其他进程都被阻塞，以等待管程变为可用。管程的主要特征模块化：一个管程是一个基本程序单位，可以单独编译；管程的主由于管程通常是用于管理资源的，为了实现进程对资源的共享，管程必须包含同步工具。因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量----条件变量。每个条件变量表示一种等待原因，并且不取具体数值－－相当于每个原因对应一个队列。条件变量(condition)由于管程通常是用于管理资源的，为了实现进程对资源的共享，管程管程使用条件变量condition和同步操作原语wait和signal提供对同步的支持。等待的原因可有多个，条件变量相应的可有多个。管程中对每个条件变量都要进行说明，形式为：

conditionx,y;

且条件变量应置于wait和signal之前，即表示为x.wait和x.signal。条件变量(condition)管程使用条件变量condition和同步操作原语wait和s同步操作原语wait和signal

：针对条件变量x，x.wait将自己阻塞在x队列中，x.signal将x队列中的一个进程唤醒。x.wait：正在调用管程的进程因x条件需要被阻塞或挂起，则调用x.wait将自己插入到x条件的等待队列上，并释放管程，直到x条件变化。此时其它进程可以使用该管程。x.signal：正在调用管程的进程发现x条件发生了变化，则调用x.signal，重新启动一个因x条件而阻塞的进程。如果存在多个这样的进程，则选择其中的一个，如果没有，则继续执行原进程，而不产生任何结果。条件变量(condition)同步操作原语wait和signal：针对条件变量x，x.w如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执行了x.signal操作后，进程Q被重新启动，此时两个进程P和Q，如何确定哪个执行，哪个等待，可采用下述方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件Q等待，直至P离开管程或等待另一条件两者的折衷，规定管程中的过程所执行的signal操作是过程体的最后一个操作条件变量(condition)如果有进程Q因x条件处于阻塞状态，当正在调用管程的进程P执2.5经典的进程同步问题

2.5.1生产者－消费者问题(Theproceducer-consumerproblem)一．利用记录型信号量解决生产者/消费者问题情形一：问题的描述：有一个生产者进程在生产产品，并将这些产品提供给一个消费者进程去消费。为使生产者与消费者进程能并发执行，在两者之间设置了一个缓冲区(只能放一件产品)。生产者进程将它所生产的产品放入缓冲区中；消费者进程可从缓冲区中取走产品消费。分析：同步关系：生产者进程和消费者进程之间必须保持同步，即：不允许消费者进程到一个空缓冲区去取产品；也不允许生产者进程向一个已装满产品且尚未被取走的缓冲区中投放产品。生产者进程的处理过程：生产一个产品，当要送入缓冲区时，要检查是否可把产品存入缓冲区（即缓冲区是否为空，消费者是否把产品取走）。若空，则可将产品送入缓冲区；否则，等待。消费者进程的处理过程：当它去取产品时，要检查缓冲区是否有产品。若有，则取走一个产品；否则，等待。2.5经典的进程同步问题

2.5.1生产者－消费者问题(T一．利用记录型信号量

解决生产者/消费者问题定义如下信号量：empty表示缓冲池中空缓冲区的数量(物品是否可以存入缓冲区)。full表示满缓冲区的数量。mutex表示互斥信息量，对缓冲池的互斥使用。又假定这些生产者进程和消费者进程相互等效，只要缓冲池未满，生产者进程便可将产品（消息）投放到缓冲池；只要缓冲池未空，消费者进程便可从缓冲池中取走一个产品。一．利用记录型信号量

解决生产者/消费者问题定义如下信号量：程序段如下：intin=0,out=0;itembuffer[n];semaphoremutex=1,empty=n,full=0;voidproceduer(){do{ produceanitemnextp;…

wait(empty);

wait(mutex); buffer[in]=nextp; in=(in+1)%n;

signal(mutex);

signal(full);}while(TRUE);}Voidconsumer(){do{

wait(full);wait(mutex);nextc=buffer[out];out=(out+1)%n; signal(mutex);signal(empty);

consumetheiteminnextc; …}while(TRUE);}一．利用记录型信号量

解决生产者/消费者问题1.wait(mutex)和signal(mutex)必须成对出现；2.对资源信号量empty和full的wait和signal操作也要成对出现，但分别处于不同进程中。e.g.:wait(empty)在生产者进程中，signal(empty)在消费者进程中，生产者进程因执行wait(empty)而阻塞，之后将由消费者进程对它唤醒。

程序段如下：Voidconsumer(){一．利用记录型一．利用记录型信号量解决生产者/消费者问题情形二：问题的描述：有m个生产者进程在生产产品，并将这些产品提供给r个消费者进程去消费。为使生产者与消费者进程能并发执行，在两者之间设置了n个缓冲区(可以存放n件产品)。生产者进程将它所生产的产品放入缓冲区中；消费者进程可从缓冲区中取走产品消费。分析：同步关系：生产者进程和消费者进程之间必须保持同步，即：当n个缓冲区都为空时，不允许消费者进程到空缓冲区去取产品；当n个缓冲区都为满时，也不允许生产者进程向已装满产品且尚未被取走的缓冲区中投放产品。

互斥关系：缓冲池是个临界资源，因此，诸进程对缓冲池的操作程序是一个共享临界区，因此，需要互斥的访问。m个生产者往缓冲区存放物品时应互斥，r个消费者从缓冲区中取物品也互斥,同时也要求生产者和消费者互斥存取物品。一．利用记录型信号量解决生产者/消费者问题情形二：一．利用记录型信号量

解决生产者/消费者问题定义如下信号量：empty表示缓冲池中空缓冲区的数量(物品是否可以存入缓冲区)，初值为n，即系统初始化时允许存入n件物品。full表示缓冲池中满缓冲区的数量(缓冲区中是否存有物品)，初值为0，即系统初始化时缓冲区无物品。Mutex：互斥信号量，表示诸进程对缓冲池的互斥使用，初值为1定义两个指针：in：指示生产者往缓冲区存放产品的相对位置。out：指示消费者从缓冲区取出产品的相对位置。一．利用记录型信号量

解决生产者/消费者问题定义如下信号量：程序段如下：Varempty,full,mutex

:semaphore:=n,0,1;Buffer:array[0..n-1]ofitemitem;in,out:integer:=0,0;beginparbeginproceduer:begin repeat… procedueanitemnextp;…wait(empty);wait(mutex);Buffer(in):=nextp;in:=(in+1)modn; signal(mutex);

signal(full); untillfalse;endConsumer:begin

repeatwait(full);wait(mutex);nextc:=Buffer(out); out:=(out+1)modn;signal(mutex);signal(empty);

consumetheiteminnextc; untillfalse;end

parend;end；一．利用记录型信号量

解决生产者/消费者问题注意:wait操作不能颠倒，必须先执行对共享资源信号量的wait操作，然后执行互斥信号量的wait操作，否则可能引起进程死锁。

程序段如下：Consumer:一．利用记录型信号量

解决Varmutex,empty,full:semaphore:=1,n,0;Buffer:array[0..n-1]ofi