第2章 进程管理

1、1,第二章,进程管理,2,本章讨论的主要问题,1、如何使程序并发执行？进程的引入2、如何进行进程控制？进程创建、阻塞、挂起、终止3、如何控制和协调并发进程异步执行的时序？进程的同步机制4、进程之间如何互相联系，传递信息？进程的通信5、如何提高程序并发执行的程度？线程的引入,3,2.1进程的基本概念,2.1.1程序的顺序执行及其特征2.1.2前趋图2.1.3程序的并发执行及其特征2.1.4进程的特征与状态2.1.5进程控制块,4,一.程序的顺序执行所谓程序的顺序执行，是指一个程序运行时独占整个系统资源,处理机严格按照程序所规定的顺序进行操作。在一个程序段中，只有前面的一个操作执行完，才能进行后面

2、一个操作。例如下述程序段:S1:a=x+y；S2:b=a-5；S3:c=b+1；,2.1.1程序的顺序执行及其特征,图2-1一个程序段中语句的顺序执行,5,在一个系统中，若要执行几个程序段，只有当一个程序段执行完后才能执行另一个程序段中的操作。例如：一个程序段若由输入(I)、计算(C)、输出(P)等操作组成，两个程序段的顺序执行则如图所示。,图2-2两个程序段的顺序执行,2.1.1程序的顺序执行及其特征,6,二.程序顺序执行的特征顺序性：处理机的操作严格按照程序所规定的操作顺序执行，时间上完全有序,即只有前一个操作执行完以后，才能进行后继操作。封闭性：程序执行时独占系统资源，系统内各种资源的状

3、态（初始状态除外）只能被本程序所改变，其执行结果不受外界因素干扰。结果可再现性：只要程序执行的环境与初始状态不变,当重复执行时,所获得的结果相同,与执行速度无关。,2.1.1程序的顺序执行及其特征,7,前趋图(ProcedenceGraph)前趋图是一个有向无循环图DAG(DirectedAcyclicGraph)。在前趋图中，每个结点代表一个事件。在操作系统中，可以将结点看作语句、程序段或进程等。结点间的有向边表示两个结点间的前趋关系，记为“”。若有S1S2，则表示只有当S1完成之后，S2才可以执行。称S1是S2的直接前趋，S2是S1的直接后继。,2.1.2前趋图,8,2.1.2前趋图,S,

4、S,S,S,S,S,S,S,2,S,S,S,S,S,(a),(b),(c),2,3,4,1,5,6,7,3,4,1,2,3,图2-3例图注意：前趋图中必须不存在循环！,9,并行操作指多个操作在计算机系统的各个硬件部件上同时进行。这是真正意义上的“同时”操作，称之为并行操作。并发执行是指在一个时间段内，多个程序段在计算机系统中“一起”执行。例如，在一个时间段内，一个CPU在为多道程序工作，而在某一个瞬间，一个CPU只能运行一道程序，它只是在多道程序中快速切换，给人以CPU“同时”运行几道程序的感觉。每个程序内部仍是按顺序执行，但是多个程序的执行过程是可以交叉的，这是一种伪并行，称之为并发执行。,

5、2.1.3程序的并发执行及其特征,10,一.并发执行若干程序段在执行时间上有重叠,即一个程序段的执行过程中插入了其它程序的操作，称为并发执行。,2.1.3程序的并发执行及其特征,11,二.程序并发执行的特征间断性：多个程序段并发执行时，由于共享资源或由于相互合作而形成执行时的相互制约关系，使得每个程序段执行时产生了间断性。将导致程序具有“执行暂停执行”这种间断的活动规律。,2.1.3程序的并发执行及其特征,12,2.非封闭性：多个程序段并发执行时，每个程序段不再独占系统资源,执行时受外界因素影响。例如，当一个用户的程序段执行中使用某个I/O设备时，其他用户的程序段申请使用该设备，就必须等待。3

6、.不可再现性：多个程序段并发执行时，产生了非封闭性，不再独占系统资源，此时，即使程序执行的环境与初始状态不变，重复执行时运算结果通常也不可再现。,2.1.3程序的并发执行及其特征,13,example,例如:两个并发执行的程序段A与B共享一个变量N，两个程序段推进速度发生变化时，可能导致程序运行结果不确定。假定N初始值为3。,程序的执行结果与相对执行速度有关，有时，程序的多次执行会有不同的结果。,程序执行结果,不一一对应,进程：程序的一次执行过程。,14,一.进程定义1961年，进程的概念首先由美国麻省理工学院在MULTICS系统中引入。随后，许多人都对进程下过定义，如：进程是可以并发执行的程

7、序在一个数据集合上的运行过程，它是系统进行资源分配和调度的一个独立单位。进程是程序的一次执行过程。进程是可参与并发执行的程序。,2.1.4进程的特征与状态,15,进程是一个程序及其数据在处理机上顺序执行时所发生的活动。进程是在给定初始状态和内存区域的条件下，可以并发执行的程序的一次执行过程。根据1978年在庐山召开的全国操作系统会议的讨论，认为“进程是一个具有一定独立功能的程序关于某个数据集合的一次运行活动”。传统OS中进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。,2.1.4进程的特征与状态,16,二.进程的特征结构特征动态性并发性独立性异步性,2.1.4进程的特征与状态

8、,17,PCB中记录了进程在系统中的每一次活动和变化情况。操作系统根据PCB中各项的变化，掌握进程所处的状态，达到控制进程的目的。,1)结构特征,进程实体：,18,2)动态性,动态性是进程的最基本的特征。表现在：由创建而产生，由调度而执行，由撤消而消亡。进程在系统中有一定的生命周期。而程序仅是存放于某种介质的有序指令的集合。程序是静态的。,19,3)并发性、独立性、异步性,并发性引入进程的目的是为了程序的并发执行。没有创建进程的程序是不能并发执行的。独立性进程是系统进行资源分配和调度的独立单位。异步性进程按各自独立的、不可预知的速度向前推进。,20,三.进程的基本状态及其变迁进程有三个基本状态

9、：就绪状态、执行状态与阻塞状态。进程在运行过程中必处于这三个基本状态之一。,21,就绪状态：进程获得必要资源，例如内存等，已经具备了执行条件，只是没有空闲的CPU，处于等待CPU的状态。在系统中，将处于就绪状态的多个进程的PCB排成就绪队列。执行状态：进程已经获得必要的资源及CPU，它的程序正在执行中。在多处理机系统中，可以有多个进程处于执行状态。在单处理机系统中，只能有一个进程处于执行状态。,22,阻塞状态：进程因某等待事件发生（例如I/O请求、某些原语操作等）而处于暂停执行的状态，此时即使将CPU分配给它，也无法执行。在系统中，将处于阻塞状态的进程的PCB排成一个阻塞队列，或因阻塞原因不同

10、而排在不同队列中。,23,四.挂起状态的引入1.终端用户的需要：发现可疑问题2.父进程的需要：考查、修改子进程、协调子进程间活动3.负荷调节的需要：调整负荷，使系统正常运行。4.操作系统的需要：检查资源使用情况5.对换的需要：缓和内存紧张,24,挂起状态（Suspend）：对正在执行的进程，则停止执行。对就绪状态的进程，则停止调度，并回收资源。对阻塞状态的进程，则停止条件的发生。,25,活动阻塞,执行状态,活动就绪,静止就绪,静止阻塞,调度,释放,I/O请求,激活,激活,挂起,挂起,挂起,释放,五.进程状态的转换,26,活动就绪静止就绪：当进程处于未被挂起的就绪状态时，称活动就绪状态，此时进程

11、可接受调度。当它被挂起时，便转变为静止就绪状态，此时不再接受调度。通常，新建进程进入活动就绪状态，以便尽快得到调度。活动阻塞静止阻塞：当进程处于未被挂起的阻塞状态时，称活动阻塞状态，此时进程可因某等待事件的完成而转变为活动就绪状态。当处于活动阻塞状态的进程被挂起时，便转变为静止阻塞状态。,27,静止阻塞静止就绪：处于静止阻塞状态的进程在所期待的事件出现后，将转变为静止就绪状态，仍处于静止状态。静止就绪活动就绪：处于静止就绪状态的进程被激活后，转变为活动就绪状态，进程可重新接受调度。静止阻塞活动阻塞：处于静止阻塞状态的进程被激活后，转变为活动阻塞状态，当所期待的事件完成后，将转变为活动就绪状态。

12、执行静止就绪：处于执行状态的进程被挂起后处于静止就绪状态，暂停执行，不再接受调度。,28,调度,允许进入,超时，如时间片到了,事件等待如I/O操作,事件发生被唤醒,释放,六.创建状态和终止状态,注意：不存在以下状态转换阻塞执行就绪阻塞,29,1进程控制块的作用为描述进程动态变化过程以及对进程进行控制与管理而设的数据结构。进程与PCB一一对应，操作系统根据PCB了解进程的存在，是进程是否存在的唯一标志。PCB常驻内存，属于系统空间，只有操作系统程序才能访问，用户程序不得访问。,2.1.5进程控制块,30,2进程控制块中的信息进程标识符：外部标识符：创建者提供，字母、数字组成，便于记忆。内部标识符

13、：唯一数字标识符，一个进程的序号，方便系统使用。,2.1.5进程控制块,31,处理机状态：中断点现场信息通用寄存器：用户可视寄存器，可被用户程序访问，暂存信息。指令寄存器：存放要访问的下一条指令的地址。程序状态字：含状态信息，如条件码、执行方式、中断屏蔽标志等。用户栈指针：存放过程和系统调用参数及调用地址。,2.1.5进程控制块,32,进程调度信息：进程状态进程优先级进程调度所需的其它信息：进程已等待CPU的时间总和、进程已执行的时间总和等。事件：进程由执行状态转变为阻塞状态所等待发生的事件（阻塞原因）。,2.1.5进程控制块,33,进程控制信息：程序和数据的地址：该进程的程序和数据所在的内存

14、或外存地址。进程同步和通信机制：消息队列指针、信号量。资源清单：除CPU外，所需和已经分配到的资源。链接指针：本进程所在队列中的下一个进程的PCB的首地址。,2.1.5进程控制块,34,3进程控制块的组织方式链接方式：用PCB中的链接指针项将具有相同状态进程的PCB链接起来，形成就绪队列、若干个空闲队列和阻塞队列等。系统中的某些固定单元分别指向各队列队首地址及执行状态进程PCB的首地址。,2.1.5进程控制块,35,2.1.5进程控制块,36,索引方式：根据进程的状态，在内存中建立相应的索引表，系统中的某些固定单元保存各索引表的首地址。各索引表的表目中记录相应状态的某个PCB在PCB表中的地址

15、。,2.1.5进程控制块,37,2.1.5进程控制块,38,2.2.1进程的创建2.2.2进程的终止2.2.3进程的阻塞与唤醒2.2.4进程的挂起与激活,2.2进程控制,39,一.进程图：进程家族制：下图表示进程家族制中的一棵进程树。根结点为祖先进程，创建进程者为父进程，被创建者为子进程。进程家族制的特点是层次清晰、进程控制灵活、资源分配严格。进程家族制中，子进程由父进程创建与撤消，它的活动完全由父进程控制，子进程只能使用父进程的资源。,2.2.1进程的创建,40,2.2.1进程的创建,41,二.引起创建进程的事件：用户登录：当终端用户登录时，由系统创建用户进程；作业调度：批处理系统中，作业调

16、度程序为选出的作业创建进程；提供服务：系统为合法用户建立服务进程；应用请求：进程运行时可以创建子进程来协同完成任务。,2.2.1进程的创建,42,三.进程的创建：,2.2.1进程的创建,43,一.引起进程终止的事件：正常结束：进程完成任务，正常结束时被撤消；异常结束：进程运行出现故障及错误时，被迫终止运行而被撤消；外界干预：进程运行时因外界干预而撤消，如系统发生死锁时需要撤消一些进程、父进程撤消子进程等。二.进程的终止过程：,2.2.2进程的终止,44,45,一.引起进程阻塞和唤醒的事件：请求系统服务：进程请求某服务，若不能立即获得服务，通常要使其阻塞；启动某种操作：进程启动某操作后，必须在该

17、操作完成后才能继续执行，应使该进程阻塞；新数据尚未到达：一进程需要先获得另一进程提供的数据才能运行；无新工作可做：某些系统进程工作时占用CPU，无事可做时，则调用阻塞原语将自己阻塞。,2.2.3进程的阻塞与唤醒,46,二.进程阻塞过程：,2.2.3进程的阻塞与唤醒,47,三.进程唤醒过程：,2.2.3进程的阻塞与唤醒,48,一.进程的挂起：1.功能：根据进程所处状态，挂起原语可以有三种处理：完成进程从活动就绪状态到静止就绪状态的转变;完成进程从活动阻塞状态到静止阻塞状态的转变;若进程是执行状态，则转变为静止就绪状态。,2.2.4进程的挂起与激活,49,2.挂起对象与挂起方式：挂起对象：进程请求

18、挂起自身；父进程挂起子进程。挂起方式如下：挂起一个具有指定标识符的进程；挂起某个进程及其所有子孙进程：采用这种挂起方式可以避免进程被挂起而其子孙进程仍在活动而带来的问题。,2.2.4进程的挂起与激活,50,3.实现过程：,2.2.4进程的挂起与激活,51,二.进程的激活：实现过程：,2.2.4进程的挂起与激活,52,53,2.3.1进程同步的基本概念2.3.2信号量机制2.3.3信号量的应用2.3.4管程机制,2.3进程同步,54,并发执行的进程之间，通常有两种关系：同步关系进程进程时间次序上受到某种限制相互清楚对方的存在及其作用，交换信息往往指有几个进程共同完成一个任务进程之间通过在执行时序

19、上的某种限制而达到相互合作的这种约束关系称为进程的同步直接相互制约关系,一、并发进程间的约束关系,55,同步问题举例：,缓冲区,键盘,计算,A进程只有当缓冲区为空时，才能将数据输入缓冲区，B进程只有当缓冲区有数据时，才能从缓冲区取数进行计算。,B进程,A进程,56,又如，有用户作业程序，其形式是：Z=func1(x)*func2(y)其中func1(x)，func2(y)均是一个复杂函数，为了加快本题的计算速度，可用两个进程P1、P2各计算一个函数。进程P2计算func2(y)，进程P1在计算完func1(x)之后，与进程P2的计算结果相乘，以获得最终结果Z。,57,58,互斥关系进程资源进程

20、竞争到某一物理资源时不允许其它进程工作相互之间不一定清楚其它进程情况往往指多个任务多个进程间通讯制约故更广泛进程之间彼此无关，但是由于竞争使用同一共享资源而产生了相互约束的关系。这种因共享资源而产生的制约关系称为进程的互斥间接相互制约关系,59,互斥问题举例：,60,计算机的许多硬件资源都被处理成临界资源，如打印机、磁带机等。例如，若打印机允许若干用户同时打印，则打印结果会混在一起，不易分辨，给用户带来许多不便。系统中还有许多软资源，如共享变量、表格、队列、栈等也被处理成临界资源，以避免多个进程对它们访问时出现问题。,二、临界资源（criticalsource）,1.什么是临界资源凡是以互斥方

21、式使用的共享资源都称为临界资源。临界资源具有一次只允许一个进程使用的属性。,61,设有两个进程P1、P2，它们共享同一变量count,P1、P2的主要操作如下：P1：R1=count;P2:R2=count;R1=R1+1;R2=R2-1;count=R1;count=R2;其中，R1和R2是处理机的两个通用寄存器。,举例：,62,它们按各自独立的速度前进，运行的顺序可能是：P1:R1=count;R1=R1+1;count=R1;P2:R2=count;R2=R2-1;count=R2;若count的初值为5，则经过上面的顺序执行后结果为5；运行顺序还可能是：P1:R1=count;P2:R

22、2=count;P1:R1=R1+1;count=R1;P2:R2=R2-1;count=R2;若count的初值为5，则经过上面的顺序执行后结果为4；,63,进程并发执行的相对执行速度是不可预测的。,字符回显voidecho()chin=getchar();chout=chin;putchar(chout);,在内存中只需echo的一个副本，节省内存空间。echo共享进程,x,y,输出结果为yy,y,example：程序A和B都要调用echo函数,64,启发,example中问题的根本是访问共享的全局变量造成的，有何启发？既然对echo的交替执行会引发执行结果的不同，由此想到对访问该变量的代

23、码要进行控制。解决方法：一次只允许一个进程进入echo，并且只有在echo过程运行结束后，另外一个进程才能进入执行。,65,example：程序A和B都要调用echo函数,字符回显voidecho()chin=getchar();chout=chin;putchar(chout);,在内存中只需echo的一个副本，节省内存空间。echo共享进程,x,x,y,y,输出结果为xy,66,每个进程中，访问临界资源的那段代码称为临界区。临界区是一段代码。,临界区,这些程序段分散在不同的进程中。临界区可按不同的共享资源划分成不同的集合。如：print1,print2同属一个集合中的临界区不允许并发执行，

24、必须互斥。,2.临界区（criticalsection）,67,如何保证同一集合的临界区不会并发执行呢？在进入临界区之前先检测是否能够进入。如果有其它进程已进入临界区使用临界资源，则必须等待。否则，允许进入，同时设置标志表明有进程正在临界区内。进入区entercritical退出临界区后，要修改标志为无进程使用该临界资源。退出区exitcritical互斥机制entercritical、exitcritical有多种实现方法：加锁、信号量、管程等。,68,临界区的代码构成,voidP1while(true)/precedingcode/criticalsection/followingcode

25、,69,小结,受到制约的这些进程，不管是受到直接制约还是受到间接制约，执行时都要依次执行。或者说并发执行的同时在受到制约的语句部分要顺序执行。所不同的是，受到直接制约的要求有明确的执行次序。同步Synchronization受到间接制约的进程，谁先执行都可以，但一旦一个先执行，其余需要等待。互斥MutualExclusion同步的概念比互斥要强一些。,70,空闲让进无进程处于临界区内时，可让一个申请进入该临界区的进程进入。忙则等待临界区内有进程时，申请进入临界区的进程必须等待。有限等待进程进入临界区的请求，必须在有限的时间内满足。让权等待等待进入临界区的进程，必须立即释放CPU。,三、进程的同

26、步机制,1、同步机制应遵循的准则,进程的同步机制就是在进程异步运行时，在执行时序上施加某些限制，使其对共享资源的操作与时间无关。,71,互斥的实现软件方法：忙等待，浪费资源。硬件方法。信号量、管程等。BusyWaiting忙等待进程一直在检测是否能进入临界区，在没有进入之前，一直在做一些检测工作。,72,2.3.2信号量机制,并发进程间的相互制约关系从本质上说是由于争夺和共享资源而产生的。将资源抽象为信号量（Semaphore），在信号量基础上引入同步操作原语：P操作、V操作。,一.什么是信号量,73,1.整型信号量最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标

27、准的原子操作(AtomicOperation)wait(S)和signal(S)来访问。这两个操作被分别称为P、V操作。wait和signal操作可描述为：定义：Semaphore:S；wait(S):whileS=0dono-opS=S-1;signal(S):S=S+1;,2.3.2信号量机制,二.信号量机制,74,2.3.2信号量机制,定义：structsemaphoreint：value；信号量值queue：*L；信号量等待队列指针；,2.记录型信号量,其中：信号量值表示某种资源的数量。等待队列指针当信号量值为负时，表示该类资源已分配完，等待该类资源的进程排在等待队列中。L为指向该信号

28、量等待队列的指针。,75,S.value=S.Value+1；若S.Value0则进程继续执行。若S.Value0则唤醒S等待队列中的一个进程，使之转为就绪状态。,定义：Semaphore:S；P操作（wait原语）每执行一次P操作，申请分配一个单位的资源。P(S)对信号量S进行P操作。,V操作（Signal原语）V(S)对信号量S进行V操作，释放一个单位的资源。,S.value=S.Value-1；若S.Value0则进程继续执行。若S.Value0则进程阻塞，并进入等待队列(L)。,76,P操作：P（s）semaphore：s；s.value=s.value-1；ifs.value0blo

29、ck（s.L）；,V操作：V（s）semaphore：s；s.value=s.Value+1；ifs.value=0wakeup（s.L）；,P、V操作的算法描述,77,说明：S.Value0时，其值表示某类资源可用数量。S.Value0时，其绝对值表示在信号量队列中等待该资源的进程数。PV操作有严格不可分割性；执行过程不允许中断；P、V操作成对出现。,78,（根据同步机制的原则，分析P、V操作的特点）,？问题？,如何使用P、V操作实现同步机制？,考虑：如何控制互斥地使用临界资源？如何控制进程并发执行的时序？,实现同步机制基本思想是：加锁、解锁,79,设mutex公共互斥信号量,利用P、V操作

30、实现互斥的模型,1、实现进程互斥,初值：mutex.Value=1,V（mutex）；.,值0,V（mutex）；.,进程P1,进程P2,.,P（mutex）；,进入P1临界区；,P（mutex）；,进入P2临界区；,值-1,.,值0,设先执行进程P1,2.3.3信号量的应用,值1,80,利用信号量实现进程互斥的进程描述为：定义公共的互斥信号量：mutex初值：mutex.Value=1执行过程中mutex.Value的值，在1，0，-1之间变化。,semaphoremutex=1;process1:doP(mutex);criticalsection;V(mutex);remainderse

31、ction;while1；,process2:doP(mutex);criticalsection;V(mutex);remaindersection;while1；,为了实现进程互斥地进入临界区，只须把临界区CS置于P(mutex)和V(mutex)之间。,2.3.3信号量的应用,81,分析：打印进程与计算进程之间有两个约束：1）计算进程只有当缓冲区为空时，才能放入计算结果。2）打印进程只有当缓冲区有结果时，才能从缓冲区取计算结果打印。,2、实现进程同步实例：打印进程与计算进程的同步问题。,缓冲区,计算,打印机,缓冲区,缓冲区,打印进程,计算进程,full,empty,2.3.3信号量的应用

32、,每个进程互给对方进程发送执行条件已满足的信号。设信号量empty表示缓冲区为空，初值为1。信号量full表示缓冲区为满，初值为0。,82,L1:P（empty）；计算结果放入缓冲区；T2:V（full）；,显然，进程CP与进程IOP相互制约：只有CP执行到T2，IOP才能执行T1。（T2T1）只有IOP执行到L2，CP才能执行L1。（L2L1）,计算进程与打印进程同步的模型,计算进程CP,打印进程IOP,T1:P（full）；从缓冲区取结果；L2:V（empty）；,empty初值为1,full初值为0,2.3.3信号量的应用,83,利用信号量实现进程同步：以打印进程与计算进程的同步问题为例

33、，count总计算量（初值为n）empty和full同步信号量，初值分别为1和0。,T2T1L2L1,semaphoreempty=1,full=0;CP:docomputernextnumber;L1:P(empty);addtobuffer;count=count-1;T2:V(full);ifcount=0destroy(CP)；while1；,IOP:doT1:P(full);takefrombuffer;L2:V(empty);printlastnumber;ifcount=0destroy(IOP);while1；,2.3.3信号量的应用,84,3、利用信号量来描述前趋关系,前趋关

34、系：并发执行的进程P1和P2中，分别有代码C1和C2，要求C1在C2开始前完成；为每个前趋关系设置一个互斥信号量S12，其初值为0。,2.3.3信号量的应用,85,有三个进程，进程get从输入设备上不断读数据，并存入buffer1；进程copy不断将buffer1的内容复制到缓冲区buffer2，进程put则不断将buffer2的内容在打印机上输出。三个进程并发执行，协调工作。写出该三个进程并发执行的同步模型。,讨论题,buffer1,buffer2,get,copy,put,86,同步与互斥的解题思路,分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。对互斥

35、问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但可分别出现在不同的进程中。,87,利用信号量的P、V操作解决较复杂的并发性问题：一个进程需要获得多个资源，才可能运行。效率低多个进程同时需要获得相同的多个资源，容易产生“死锁”。例如：两个进程A、B争夺资源D

36、、E；进程A进程B。P（Dmutex）；P（Emutex）；P（Emutex）；P（Dmutex）；如果按照以下次序并发执行：进程A：P（Dmutex）；Dmutex值：0进程B：P（Emutex）；Emutex值：0进程A：P（Emutex）；Emutex值：-1进程B：P（Dmutex）；Dmutex值：-1,僵死！,定义初值：Dmutex=1Emutex=1,2.3.3信号量的应用,88,基本思想：一个进程必须同时分配其所需要的资源，或者同时释放所有资源。在分配资源的过程中，只要尚有一个资源无法获得，就必须释放已占有的其它资源。,“AND型信号量”机制：AND型信号量用于同时需要多种资源

37、且每种占用一个时的信号量操作；,AND型信号量机制,89,AND型信号量,定义：Swait（S1，S2，Sn）ifS1=1,P72-P73,90,基本思想：信号量集是对AND信号量的扩充，每个并发进程应该同时获得所需数量的各类资源，当某类资源的数量低于某一下限时，不予分配。定义三组参数：Si信号量（资源种类）ti某类资源的最小限额（下限）di每次SP或SV操作的资源分配或释放数量。其中：i=1n,信号量集机制,91,信号量集机制定义,Swait(S1,t1,d1,Sn,tn,dn)ifS1=t1andandSn=tnfor(i=1;i=n;i+)Si=Si-di;elsePlacetheexe

38、cutingprocessinthewaitingqueueofthefirstSiwithSitiandsetitsprogramcountertothebeginningoftheSwaitOperation.Ssignal(S1,d1,Sn,dn)for(i=1;i=n;i+)Si=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.,92,信号量集机制的几种特殊情况,(1)Swait(S,d,d)。此时在信号量集中只有一个信号量S，但允许它每次申请d个资源，当现有资源数少于d时，不予分配

39、。(2)Swait(S,1,1)。此时的信号量集已蜕化为一般的记录型信号量(S1时)或互斥信号量(S=1时)。(3)Swait(S,1,0)。这是一种很特殊且很有用的信号量操作。当S1时，允许多个进程进入某特定区；当S变为0后，将阻止任何进程进入特定区。即相当于一个可控开关。,93,管程的基本思想：加围墙,统管,2.3.4管程机制,将分散的各同类临界区集中起来，为每一类共享资源设置一个“管程”，统一控制和管理各进程对该资源的访问，即任何一个进程要访问共享资源，必须通过管程。,Dijkstra(1971)：“秘书”进程Hansan和Hoare(1973)：管程,94,2.5管程机制,采用PV同步

40、机制来编写并发程序，对临界区的执行分散在各个进程中，缺点：1.易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，就必须通读整个系统或者并发程序。2.不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响大局。正确性难以保证，因为操作系统或并发程序通常很大，要保证这样一个复杂的系统没有逻辑错误是很难的。,管程(monitor)是更高级的同步机制，能够进一步实现复杂的并发性问题。一.为什么引入管程,95,2.3.4管程机制,1.管程的组成,二.什么是管程(monitor),系统资源,局部共享数据结构,实施操作的若干过程,管程名局部于管程的共享变量说明对该数据结构

41、实施操作的若干函数对局部于管程的数据设置初始值的语句,抽象,建立,管程,调用,进程,96,2.3.4管程机制,图管程的示意图,97,（一）模块化。一个管程是一个基本程序单位，可以单独编译。（二）抽象数据类型。管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码。（三）信息掩蔽。管程是半透明的，管程中的过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的。,2.3.4管程机制,2.管程的3个主要特性：,98,2.3.4管程机制,管程中的局部变量只能由该管程的函数来访问，不允许进程直接访问，也不允许其他管程访问。任何一个进程要访问共享资源必须通过管程（管程入口

42、）。管程每次只允许一个进程进入。当某进程通过管程请求临界资源而未能满足时，管程便调用wait原语使该进程等待，并将它排在等待队列上。,3.实现管程的基本原则,为区别不同的等待原因，引入条件变量（condition）；将申请资源（wait原语）和释放资源（signal原语）的原语修改为：条件变量名.wait条件变量名.signal,可以实现互斥,99,在管程中执行的某进程发现条件未能满足时，发送wait使该进程阻塞。X.wait：等待操作，用来将执行进程挂到与条件变量X相应的等待队列上。当管程中执行的另一进程发现条件X满足了，则发送signal通知X条件队列，条件已改变。X.signal：发信号

43、操作，用来恢复与X相应的等待队列上的一个进程。若没有等待进程，则X.signal不起任何作用，什么都不做。,100,如果有进程Q处于阻塞状态，当进程P执行了X.signal操作后，怎样决定由哪个进程执行，哪个等待，可采用下述两种方式之一进行处理：(1)P等待，直至Q离开管程或等待另一条件。（Hoare,进程切换过于频繁）(2)Q等待，直至P离开管程或等待另一条件。（效率高，但它导致逻辑关系不清晰）(3)规定唤醒为管程中的最后一个可执行的操作。（Hansan,是(1)的特例）,2.3.4管程机制,101,2.3.4管程机制,步骤：为进程建立管程，其格式为：typedefmonitormonito

44、r_namevariabledeclarationsp1();.pn();initializationcode,在并发进程中调用管程,定义管程名、局部变量,一组操作,设置变量初值,4.利用管程实现进程同步,102,管程与信号量的对比,X.wait/X.signal与Wait/Signal的区别：使用X.wait会挂起当前进程。而执行Wait未必阻塞。如果没有挂起进程，X.signal什么都不做。解决同步互斥问题时：使用信号量：实现同步和互斥都是程序员的责任。使用管程：管程本身的互斥机制使得生产者、消费者不能同时访问缓冲区。但实现同步需要程序员使用X.wait、X.signal实现。与信号量相比

45、，管程的优势在于所有的同步机制都限制在管程内部，因此不仅易于验证同步的正确性，而且易于检测错误。,103,一个生产者，一个消费者，一个缓冲区，生产者生产消息，并将此消息提供给消费者进程去消费。,一.生产者消费者问题（producerconsumerproblems）,2.4经典的进程同步问题,生产者关心？,消费者关心？,信号量empty，full,单一资源,104,empty的初值为1，full的初值为0,2.4经典的进程同步问题,生产者进程：生产一个产品；P（empty）；将产品放入缓冲区；V（full）；,消费者进程：P（full）；从缓冲区取产品；V（empty）；消费产品；,105,2

46、.4经典的进程同步问题,一个生产者，一个消费者，n个缓冲区。,生产者进程：in=0；生产一个产品；P（empty）；往bufferin放产品；in=（in+1）%n；V（full）；,有限资源,消费者进程：out=0；P（full）；从bufferout取产品；out=（out+1）%n；V（empty）；消费产品；,empty的初值为n，full的初值为0,106,2.4经典的进程同步问题,一个生产者，一个消费者，缓冲区。,无限资源,full的初值为0,生产者进程：in=0；生产一个产品；往bufferin放产品；in=in+1；V（full）；,消费者进程：out=0；P（full）；从b

47、ufferout取产品；out=out+1；消费产品；,107,2.4经典的进程同步问题,问题？,一组生产者进程Pi（P1，P2，Pk）一组消费者进程Ci（C1，C2，Cm）,互斥使用由n个缓冲区组成的缓冲池。,in,out,Ci,Pi,1.同步关系：当缓冲池放满产品时生产者必须等待。定义生产者进程同步信号量：empty表示空闲缓冲区数。0emptynempty初值为；当缓冲池空时，消费者进程必须等待。定义消费者进程同步信号量：full表示有产品的缓冲区数。0fullnfull初值为；,分析,n,0,2.互斥关系：两组进程中的每个进程必须互斥的使用缓冲区。定义公共互斥信号量：mutex初值为1

48、,3.定义：in，out分别表示首空缓冲区序号及首满缓冲区序号。,一般的生产者消费者问题（producerconsumerproblems）,108,生产者消费者问题算法：,生产者进程：生产一个产品m；.P（empty）；P（mutex）；将产品m放入缓冲区；in=（in+1）%n；V（mutex）；V（full）；,semaphoremutex，empty，full=1,n,0messagebuffern;in,out=0,0,消费者进程：P（full）；P（mutex）；从缓冲区取产品m；out=（out+1）%n；V（mutex）；V（empty）；,检查有否空缓冲区,检查缓冲区中有无进

49、程,释放缓冲区,通知消费者进程使用,检查缓冲区中是否有产品,检查缓冲区中有无进程,释放缓冲区,通知生产者进程使用,109,生产者消费者问题算法：,生产者进程：生产一个产品m；.P（empty）；P（mutex）；将产品m放入缓冲区；in=（in+1）%n；V（mutex）；V（full）；,消费者进程：P（full）；P（mutex）；从缓冲区取产品m；out=（out+1）%n；V（mutex）；V（empty）；,问题,1.能否交换两个P操作？能否交换两个V操作？为什么？2.如果缺少操作：P（empty）或P(full）,结果如何？,110,voidproducer()生产一个产品将产品放

50、入缓冲区；in=(in+1)%n;,voidconsumer()从缓冲区中取产品；out=(out+1)%n;消费该产品；,voidmain()parbegin(producer,consumer);,constintn=/*buffersize*/semaphoreempty=n;semaphorefull=0;,Wait(empty);,Signal(full);,Wait(full);,Signal(empty);,while(true),semaphoremutex=1；,Wait(mutex);,Signal(mutex);,Wait(mutex);,Signal(mutex);,思

51、考下面的情况：缓冲区全空，消费者先执行,1-1=0,0-1=-1,0-1=-1,while(true),111,结论,进程中若有多个Wait，要求同步信号量的Wait操作在前，互斥信号量的Wait操作在后，以免引起死锁。进程中若有多个Signal，其操作顺序无所谓。,112,同步与互斥的解题思路,分清哪些是互斥问题（互斥访问临界资源的），哪些是同步问题（具有前后执行顺序要求的）。对互斥问题要设置互斥信号量，不管有互斥关系的进程有几个或几类，通常只设置一个互斥信号量，且初值为1，代表一次只允许一个进程对临界资源访问。对同步问题要设置同步信号量，通常同步信号量的个数与参与同步的进程种类有关，即同步

52、关系涉及几类进程，就有几个同步信号量。同步信号量表示该进程是否可以开始或该进程是否已经结束。在每个进程中用于实现互斥的PV操作必须成对出现；用于实现同步的PV操作也必须成对出现，但可以分别出现在不同的进程中；在某个进程中如果同时存在互斥与同步的P操作，则其顺序不能颠倒，必须先执行对同步信号量的P操作，再执行对互斥信号量的P操作，但V操作的顺序没有严格要求。,113,生产者消费者问题算法：,生产者进程：生产一个产品m；.将产品m放入缓冲区；in=（in+1）modn；,消费者进程：从缓冲区取产品m；out=（out+1）modn；,用AND信号量解决：,P（empty）；P（mutex）；,SP

53、(empty，mutex）；,P（full）；P（mutex）；,SP(full,mutex);,V（mutex）V（full）；,SV(mutex,full);,V（mutex）；V（empty）；,SV（mutex,empty）；,114,生产者消费者问题算法：,用管程解决：,定义一个管程boundedbuffer，管理有界缓冲区。管程中有两个条件变量：notfull：由于缓冲区全满而使调用进程等待；notempty：由于缓冲区全空而使调用进程等待。为该管程定义两个过程：放产品put(item)取产品get(item),115,typedefmonitorproducer-consumer

54、intin,out,count;itembuffern;conditionnotfull,notempty;put(item)ifcountnnotfull.wait;bufferin=nextp;in=(in+1)n;count=count+1;ifnotempty.queuenotempty.signal;,生产者消费者问题算法：,用管程解决：,116,get(item)ifcount0notempty.wait;nextc=bufferout;out=(out+1)n;count=count-1;ifnotfull.quenenotfull.signal;in=out=0;count=0

55、,生产者消费者问题算法：,用管程解决：,117,Producer:doproduceaniteminnextp;PC.put(item);while(true);Consumer:doPC.get(item);consumetheiteminnextc;while(true);,在利用管程解决生产者-消费者问题时，其中的生产者和消费者可描述为：,生产者消费者问题算法：,用管程解决：,118,2.4经典的进程同步问题,分析：为每支筷子设置一个信号量，一个哲学家，通过在相应的信号量上执行P操作，抓起一支筷子，通过执行V操作放下一支筷子。5个信号量构成数组：semaphorechopstick5；,

56、二.哲学家进餐问题,第i个哲学家的活动可描述为：doP（chopsticki）；抓起左边筷子；P（chopstick（i+1）%5）；抓起右边筷子；.Eat;吃饭；V(chopsticki）；放下左边筷子；V(chopstick（i+1）%5）；放下左边筷子；.Think;思考；.while(true);,同时拿起筷子，出现死锁!,119,用AND信号量机制解决哲学家进餐问题,第i个哲学家的活动可描述为：doThink;Swait（chopstick（i+1）%5，chopsticki）；Eat;Ssignal(chopstick（i+1）%5，chopsticki）；while(true);

57、,120,解决办法,(1)规定奇数号哲学家先拿他左边的叉子，然后再去拿右边的叉子；而偶数号哲学家则相反。按此规定，0、1号哲学家竞争1号叉子；2、3号哲学家竞争3号叉子。(2)至多有4个哲学家同时拿叉子。,4,3,2,1,0,4,3,2,1,0,121,解决方法一,voidPhilosophers(inti)while(true)think();if(i%2=0)Wait(forki);Wait(fork(i+1)mod5);elseWait(fork(i+1)mod5);Wait(forki);eat();Signal(forki);Signal(fork(i+1)mod5);,122,/*

58、programdiningphilosophers*/semaphorefork5=1,1,1,1,1;inti;,voidPhilosophers(inti)while(true)think();eat();voidmain()parbegin(Philosophers(0),Philosophers(1),Philosopher(2),Philosopher(3),Philosopher(4);,4,3,2,1,0,4,3,2,1,0,Wait(forki);,Wait(fork(i+1)mod5);,Signal(forki);,Signal(fork(i+1)mod5);,semaphoreroom=4;,Wait(room);,Signal(room);,解决方法二,123,2.4经典的进程同步问题,有两组并发进程：读者进程（只读），写者进程（只写）共享一个文件（资源）对象。读、写规则如下：允许多个“读者”同时执行读操作。任一“写者”访问文件时，不允许其他“读者”或“写者”工作。,三.读者写者问题,问题,第一类：“读者优先”,若读者来:a.无读者、写者，新读者可以读。b.有写者等，但有其他读者正在读，则新读者也可以读。c.有写者写，新读者等。若写者来:a