第4章进程及管理

第4章进程及进程管理进程及进程管理进程的引入进程概念进程控制进程之间的制约关系进程互斥与同步的实现进程间通信线程的概念和特点进程及进程管理——主要内容进程引入进程及进程管理——进程的引入程序进程及进程管理——进程的引入用来表示人们思维对象的抽象概念的物理表现叫做数据。数据处理的规则叫做操作（指令）。对某一有限数据的集合所施行的、目的在于解决某一问题的一组有限的操作的集合，称为一个计算。计算机就是用指令来处理数据。程序是数据和指令的集合（数据结构+算法）。一个程序的执行过程就是一次计算。程序的顺序执行和并发执行

进程及进程管理——进程的引入程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式；现在的操作系统多为并发执行，具有许多新的特征。引入并发执行的目的是提高资源利用率。顺序程序的特点进程及进程管理——进程的引入1.什么是程序的顺序执行一个程序由若干个子程序段组成，每个程序段由若干条操作指令组成。子程序段的执行必须严格按照先后次序顺序执行。子程序段中的指令也必须是顺序执行的。系统中存在的若干个程序也是一个一个按顺序运行，同时只能运行一个程序，一个程序运行完毕后才能运行下一个程序。

顺序程序的特点①单道系统的工作情况对用户作业的处理——

首先输入用户的程序和数据；然后进行计算；最后打印计算结果，即有三个顺序执行的操作。

I：输入操作

C：计算操作

P：输出操作单用户系统中操作的先后次序图进程及进程管理——进程的引入P2C2I2P1C1I1P3C3

I3②

顺序程序的特点顺序性

——处理机的操作严格按照程序所规定的顺序执行。封闭性

——程序一旦开始执行，其计算结果不受外界因素的影响。可再现性

——程序执行的结果与它的执行速度无关(即与时间无关)，而只与初始条件有关。

时间无关性-->可再现性

时间无关性的先决条件是：程序的封闭性缺点是计算机系统效率不高。

进程及进程管理——进程的引入进程及进程管理——进程的引入78输入处理器打印130150228280300378430450时间处理器利用率：52/(78+52+20)≈35%2.并发执行

(1)多道系统的工作情况

I1

I2

I3

I4C1C3C2P1P2

哪些程序段的执行必须是顺序的？为什么？哪些程序段的执行可以是并行的？为什么？多道系统中操作的先后次序图对n个用户作业的处理——

作业1：I1C1P1

作业2：I2C2P2......

......

作业n：InCnPn进程及进程管理——进程的引入进程及进程管理——进程的引入78输入处理器打印130150156234312384时间处理器利用率：52/78≈67%(2)为什么程序可以并发执行由程序运行时需要占用的资源决定的：一个资源本来就可以同时被多个程序使用；一个资源同时只能被一个程序使用，但是可以分时使用；一个程序在不同的时刻可能占用不同的资源，它释放的资源可以让其他程序使用；存在多个同类资源；并发执行的优点：发挥了硬件的并行能力，以提高资源利用率进程及进程管理——进程的引入(3)什么是程序的并发执行①

定义

若干个程序段同时在系统中运行，这些程序段的执行在时间上是重叠的，一个程序段的执行尚未结束，另一个程序段的执行已经开始，即使这种重叠是很小的一部分，也称这几个程序段是并发执行的。②三个并发执行的程序段PQR三个并发进程进程及进程管理——进程的引入(4)并发程序的描述进程及进程管理——进程的引入把一个程序设计成若干个可同时执行的程序模块，用下面语句表示并发执行这些程序段：

cobegin S1；S2；…；Sn coend

表示程序段（函数）S1，S2，…，Sn可以并发执行。并发执行意味着各个程序段以不可预知的次序运行。甚至也可能是串行。并发程序的描述示例进程及进程管理——进程的引入一个程序设计成若干个程序模块Si，用下面语句表示执行这些程序段：{

S0

cobegin S1；S2；…；Sn coend Sn+1}s0sns2s1sn+1…并发程序的例子(1)誊抄——用卡片输入机将一个文本复写到行式打印机。

(1)循环顺序执行

while(不空){INPUT;//卡片输入机读OUTPUT;//打印机打印}

缺点：未能利用卡片输入机与行式打印机的并行操作能力，造成系统效率低。进程及进程管理——进程的引入并发程序的例子(2)基于一个缓冲区的并发誊抄方案卡片输入机-->缓冲区-->行式打印机

输入程序I： 输出程序O：

while(不空){ while(未结束){INPUT; RECEIVE;SEND; OUTPUT; } }

问题：提高了誊抄效率，但是可能出现结果不正确（可能出现什么错误？请考虑）。进程及进程管理——进程的引入并发程序的例子(3)基于两个缓冲区的并发誊抄方案，卡片输入机-->缓冲区s-->缓冲区t->行式打印机进程及进程管理——进程的引入卡片输入-->缓冲区swhile(誊写未完成){

缓冲区s-->缓冲区t cobegin

缓冲区t-->行式打印机 卡片输入-->缓冲区s coend}并发程序的特点①失去程序的封闭性若一个程序(段)的执行可以改变另一个程序(段)的变量，那么后者的输出就可能有赖于各程序(段)执行的相对速度，即失去了程序的封闭性特点。

例子：

讨论共享公共变量的两个程序，执行时可能产生的不同结果。程序A执行时对n做加

1的操作；程序B打印出n值，并将它减1重新置为零。程序A...n:=n+1;......程序B...

print(n);

n:=n-1;

...共享变量的两个程序进程及进程管理——进程的引入与时间有关的错误程序A的n:=n+1与程序B的两个语句的关系n的初值打印的结果n的最终值

之前

10

11

0

之后

10

10

1

之间

10

10

0

程序A...n:=n+1;......程序B...

print(n);

n:=0;

...共享变量的两个程序进程及进程管理——进程的引入intX;//剩余的票数订票的函数（）{ if(X>=1){ X=X-1; 输出一张票 }else{ 输出票已售完 }}机票问题并发程序的特点失去封闭性，导致失去可再现性1即使输入相同的初始条件，也可能得到不同的结果。2结果不可再现，不可预测。3程序的执行结果与程序间的相对速度有关。

即：程序并发执行时会发生与时间有关的错误。与时间有关的错误进程及进程管理——进程的引入

程序并发执行时若共享了变量，其执行结果将与并发程序执行的相对速度有关，即使给定相同的初始条件，也可能会得到不同的结果，此为与时间有关的错误。并发执行不能保证程序的正确性，还有实用价值吗？ 1并发程序之间如果没有共享变量，那么他们之间还是封闭的，不会发生与时间有关的错误。 2如果有共享变量，必须慎重对待！！！ 怎样才能保证程序的正确性呢？对共享变量的互斥访问②程序与计算不再一一对应程序是静态的概念，是指令的有序集合。计算是指令序列在处理机上的执行过程，是动态的概念。程序顺序执行时，程序和计算有一一对应关系。并发执行时，程序的一次运行就可能是一次不同的计算。③程序并发执行的相互制约（为了保证结果正确）并发进程之间存在同步和互斥的约束。同步对应协作；互斥对应资源共享或公共变量；进程及进程管理——进程的引入进程概念进程及进程管理——进程概念

进程引入

a提高资源利用率-->程序并发执行 b程序段的并发执行可以有任意的组合情况，为了保证并发程序的正确性，避免时间有关的错误，并发程序之间有同步和互斥的约束，这些运行时的约束是通过阻塞/唤醒程序运行来实现，这样程序就不停的处于运行/暂停/运行....的状态。

c 一个程序可以同时多次运行，每次运行的情况可能都不一样

基于以上原因，程序的概念已经不够了。为了动态反应程序的活动和状态的变化，

运行----->暂停------>运行

引入了新的概念：进程进程及进程管理——进程概念

1.进程定义

1进程是这样的计算部分，它是可以和其他计算并行的一个计算。 2进程是一个程序与其数据一道通过处理机的执行所发生的行为 3进程是由一个程序以及与它相关的状态信息（包括寄存器内容，存储区域和链接表）所组成。 4所谓进程，就是一个程序在给定活动空间和初始环境下，在一个处理机上的执行过程。 5进程是指一个具有一定独立功能的程序关于某个数据集合的一次运行活动。进程及进程管理——进程概念进程是支持并发作业的操作系统中最基本、最重要的概念。现代操作系统的设计都是建立在进程的基础上。

1.进程定义

进程及进程管理——进程概念

(2)进程与程序的区别①程序是指令的有序集合，是静态的概念，进程是程序的一次执行过程，是动态的概念；②进程是一个独立运行的活动单位；③进程是竞争系统资源的基本单位；④一个程序可以对应多个进程；

一个进程一定包含一个程序；2.进程的状态②等待状态(wait)

进程正等待着某一事件的发生而暂时停止执行。这时，即使给它CPU控制权，它也无法执行。③就绪状态(ready)

进程已获得除CPU之外的运行所必需的资源，一旦得到CPU控制权，立即可以运行。(1)进程的基本状态（至少应该具备的状态）①运行状态(running)

该进程已获得运行所必需的资源，它的程序正在处理机上执行。进程及进程管理——进程概念(2)进程状态的变迁①基本状态的最少变迁图运行服务请求(请求I/O等)服务完成/事件来到进程调度等待就绪进程状态变迁图进程及进程管理——进程概念(2)进程状态的变迁②分时系统的进程变迁运行1234等待就绪进程状态变迁图进程及进程管理——进程概念(2)进程状态的变迁③进程状态可能的变迁运行服务请求(请求I/O等)服务完成/事件来到进程调度时间片到等待就绪×进程状态变迁图进程及进程管理——进程概念×3.进程描述

(1)进程的组成代码与数据进程控制块代码段：描述进程本身所应完成的功能；数据段：进程使用的数据堆：用于动态分配的数据栈：用于函数调用和参数传递PCB：进程控制块（ProcessControlBock）进程组成的示意图进程及进程管理——进程概念 (2)什么是进程控制块

描述进程的动态特征，进程与其他进程和系统资源的关系的数据结构。是操作系统标识一个进程以及进程存在的唯一标识。(一一对应)(3)进程控制块的主要内容

①

进程标识符

进程名或内部id号②

进程当前状态本进程目前处于何种状态大量的进程如何组织？wait_lpt_q_startPCB3PCB7next打印机等待队列结构runningPCB4next运行指针ready_q_startPCB1PCB2PCB9就绪队列结构next进程队列结构示例进程及进程管理——进程概念③

当前队列指针next

该项登记了处于同一状态的下一个进程的PCB地址。④

进程优先级反映了进程要求CPU的紧迫程度。⑤

CPU现场保护区当进程由于某种原因释放处理机时，CPU现场信息被保存在PCB的该区域中。⑥通信信息进程间进行通信时所记录的有关信息。⑦家族联系指明本进程与家族的联系⑧占有资源清单

进程及进程管理——进程概念进程控制进程及进程管理——进程控制1.进程控制的概念

(1)进程控制的职责

对系统中的进程实施有效的管理，实现进程状态的改变。

①

进程状态变化进程及进程管理——进程控制创建撤销无有消亡阻塞运行等待唤醒就绪等待

②常用的进程控制原语

创建原语、撤消原语、阻塞原语、唤醒原语(2)进程创建

进程及进程管理——进程控制进程创建的方式和时机：批处理系统中，提交一个作业；分时系统中，在一个终端登录，交互；启动时，操作系统创建服务进程；用户程序自己也可以创建新的进程；生成进程称父进程(ParentProcess)，被生成进程称子进程(ChildProcess)、即一个父进程可以创建子进程，从而形成树形结构。(2)进程创建①进程创建原语的形式

create(name，priority)name为被创建进程的标识符priority为进程优先级②进程创建原语的功能创建一个具有指定标识符的进程，建立进程的PCB结构。进程及进程管理——进程控制PCB池③进程创建原语的实现

ab-1...进程创建原语的实现框图入口查PCB总链有同名?向系统申请一个空的PCB

结构有空PCB?将入口信息填入PCB相应项将PCB入就绪队列将PCB入总链队列返回进程pid出错YN出错PCB池示意图进程创建原语流程图进程及进程管理——进程控制linux下创建进程的实现： pid_tfork(void)+exec(...)系列函数进程及进程管理——进程控制(3)进程撤销进程及进程管理——进程控制进程撤销的原因：进程正常运行结束进程运行中出错，如执行了非法指令、在常态下执行了特权指令、运行时间超越了分给的最大时间段、申请的内存超过了系统能提供最大量、越界错误等操作员或操作系统干预父进程撤销其子进程

父进程撤销操作系统终止(3)进程撤销①

进程撤销原语的形式

当进程完成任务后希望终止自己时使用进程撤消原语。

Kill(或exit)②进程撤销原语的功能

撤消当前运行的进程。将该进程的PCB结构归还到PCB资源池，所占用的资源归还给父进程，从总链队列中摘除它，然后转进程调度程序。进程及进程管理——进程控制③进程撤销原语的实现

入口由运行指针得当前进程的pid释放本进程所占用的资源该进程从总链队列中摘下释放PCB结构转进程调度进程撤销原语流程图进程及进程管理——进程控制linux下进程撤销的实现1.进程自己正常结束退出: main()函数返回 exit()2.其他进程撤销情况都是通过信号(signal)实现: kill进程及进程管理——进程控制(4)进程等待①进程等待原语的形式

当进程需要等待某一事件完成时，它可以调用等待原语挂起自己。

susp(chan)

入口参数chan：进程等待的原因②进程等待原语的功能

中止调用进程的执行，并加入到等待chan的等待队列中；最后使控制转向进程调度。进程及进程管理——进程控制③进程等待原语的实现

入口保护进程的CPU现场到PCB结构中置该进程为”等待”状态将该进程PCB结构插入到等待队列中转进程调度进程等待原语流程图进程及进程管理——进程控制(5)进程唤醒①进程唤醒原语的形式

当处于等待状态的进程所期待的事件来到时，由发现者进程使用唤醒原语叫唤醒它。

wakeup(chan)

入口参数chan：进程等待的原因。②

进程唤醒原语的功能当进程等待的事件发生时，唤醒等待该事件的进程。进程及进程管理——进程控制③进程唤醒原语的实现

入口找到该等待队列将队列首进程移出此等待队列将该进程置为”就绪”状态，并将PCB结构插入到就绪队列中返回进程唤醒原语流程图进程及进程管理——进程控制linux下进程等待/唤醒的情形比较多，每一种情况等待和唤醒的系统调用都不一样，有：锁，等待进程或线程退出，sleep，文件读，select，poll，epoll进程及进程管理——进程控制进程之间的相互制约关系进程及进程管理——进程之间的相互制约关系进程之间的相互制约关系进程及进程管理——进程之间的相互制约关系

并发执行的多个进程以各自的速度向前推进，但是相互协作的多个进程之间不是孤立的，存在相互制约的关系。

例子:

多个终端订票；

医院看病、化验；

输入、打印；

接力赛跑；

视频播放；

图像处理...进程之间的相互制约关系分为两种情况：进程及进程管理——进程之间的相互制约关系1、由于竞争系统资源引起的间接相互制约关系.

比如：处理器的共享(分时)，内存，其他硬件资源2、进程之间存在共享数据而引起的直接相互制约关系.

比如：共享文件，共享变量；相互协作 协调进程之间的直接相互制约关系就是要协调各进程前进的步伐，即实现进程的同步，而要实现进程的同步，必须支持进程之间的信息交换，这就是进程间的通信。进程及进程管理——进程之间的相互制约关系并发进程之间的直接相互制约关系分为两种：

进程互斥、进程同步 操作A必须在操作B之前执行； 操作C必须在操作A和B都完成之后才能执行； 操作D和操作E不能在同一时刻执行；1.进程互斥的概念

(1)临界资源

①例1：两个进程共享一个变量x

设：x代表某航班机座号，p1和p2两个售票进程，售票工作是对变量x加1。这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。

进程及进程管理——进程之间的相互制约关系两个进程共享一个变量x时，两种可能的执行次序p1：r1:=x;r1:=r1+1;x:=r1;p2：r2:=x;r2:=r2+1;x:=r2;设x的初值为10，两种情况下的执行结果：

情况A：

x=10+2情况B：x=10+1

特点：当两个进程公用一个变量时，它们必须顺序地使用，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。

p1：r1:=x;

r1:=r1+1;x:=r1;

p2：r2:=x;r2:=r2+1;x:=r2;进程及进程管理——进程之间的相互制约关系A：B：临界区是进程中对公共变量(或存储区)进行访问与修改的程序段，称为相对于该公共变量的临界区。

临界资源的定义一次仅允许一个进程使用的资源称为临界资源。

硬件：如输入机、打印机、磁带机等软件：如公用变量、数据、表格、队列等(2)临界区

x

:=x+1;csa{进程A进程B

x

:=x+1;csb{进程临界区示意图进程及进程管理——进程之间的相互制约关系临界区的调度原则一次至多允许一个进程进入临界区内一个进程不能无限地停留在临界区内一个进程不能无限地等待进入临界区无空等待、有空让进、择一而入、算法可行。(3)互斥

在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约关系（排它性控制）称为互斥。

x

:=x+1;csa{进程A进程B

x

:=x+1;csb{进程临界区示意图进程及进程管理——进程之间的相互制约关系注意：同一临界资源的临界区才需要互斥进入。进程A正在执行csa段时，进程B就不能进入csb段执行。2.进程同步的概念

(1)什么是进程同步并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息称为进程同步。(2)进程同步的例子

①

病员就诊

同步约束条件：？看病活动：看病

要病人去化验；

等化验结果；

继续诊病；化验活动：

有化验单?

进行化验；

开出化验结果；

进程同步活动示意图进程及进程管理——进程之间的相互制约关系②

共享缓冲区的计算进程与打印进程的同步计算进程cp和打印进程iop公用一个单缓冲

缓冲区bufiop

cp两个进程共享一个缓冲区示意图进程及进程管理——进程之间的相互制约关系同步约束条件？1：cp进程把数据送入buf后，iop进程才能取出数据去打印。2：iop进程把数据取出后，cp进程才能把下一个数据送入buf。进程同步机构进程及进程管理——进程同步机构

操作系统提供的，实现进程之间协作关系（同步和互斥）的措施和方法，称为同步机构:

1锁2信号灯(信号量)1.锁和上锁、开锁操作(1)什么是锁

用一个变量w代表某种资源的占用状态，w称为“锁”。(2)上锁操作和开锁操作

进程及进程管理——进程同步机构检测w的值(是0还是1)；如果w的值为1，继续检测；如果w的值为0，将锁位置1(表示占用资源)，进入临界区执行。

(此为上锁操作)临界资源使用完毕，将锁位置0。(此为开锁操作)

(3)上锁原语和开锁原语①

上锁原语算法lock输入：锁变量w输出：无{test：if(w==1)gototest;∕*测试锁位的值*∕

elsew=1;∕*上锁*∕}②

开锁原语算法unlock输入：锁变量w输出：无{w=0；∕*开锁*∕}进程及进程管理——进程同步机构（spinlock自旋锁）(4)用上锁原语和开锁原语实现互斥

上锁原语w

进入临界区csb

开锁原语w进程B

上锁原语w

进入临界区csa

开锁原语w进程Aspinlock中的锁变量w本身也是一个共享变量，怎么保证w自己的互斥访问？进程及进程管理——进程同步机构①

上锁原语算法lock输入：锁变量w输出：无{test：if(w==1)gototest;∕*测试锁位的值*∕

elsew=1;∕*上锁*∕}1:mov%0,[w];cmp%0,#1;beq1b;mov[w],#1;[w]:变量w的内存地址%0：表示某个寄存器#1：表示立即数1硬件可以保证的原子操作：1、单个硬件指令是原子操作，中断只会发生在指令边界。2、内存总线一次地址对齐的读或写操作（1到N个字节）是原子操作。spinlock中的锁变量w本身也是一个共享变量，怎么保证w自己的互斥访问？进程及进程管理——进程同步机构必须扩充新的指令，能同时完成内存的读写操作1、交换指令（arm:swpx86:xchg）虽然一个指令完成读写，但是内存操作不是原子性，如果有多核cpu，还是会打断。必须要lock锁住总线的功能。多核心处理器实现：加锁：

cli+禁止进程调度；

1:mov%0,#1;

lockxchg%0,[lock];

cmp%0,#1;判断是否已经加锁

beq1b;解锁：

mov[w],#0；

sti+恢复进程调度；单核心处理器实现：加锁：

cli+禁止进程调度；解锁：

sti+恢复进程调度；进程及进程管理——进程同步机构交换指令违背了arm精简指令机的宗旨，并且lock总线导致自旋时整个系统总线效率很低，在armv6指令级之后引入了新的机制:独占监测（Exclusivemonitors）机制ldrex/strex:多核心处理器实现：加锁1:ldrex%0,[lock];标记cpu0独占这个地址，并读lock值到%0寄存器cmp%0,#1;假定是否已经加锁beq1b;等于1表示已经加锁，自旋mov%0,#1;strex%1,%0,[lock];检查是否cpu0仍然独占这个地址，如果是就存储%0到lock(即lock为1),并赋值0-->%1寄存器，并清除独占标记;

如果不是就赋值1-->%1，不改变lock值;cmp%1,#0;bne1b;解锁mov%0,#0；str%0,[lock];(3)上锁原语和开锁原语2进程及进程管理——进程同步机构

上锁原语lock

输入：锁变量w输出：无{while(w==1){保护当前进程的cpu现场；

设置当前进程的状态为等待,并插入到w的等待队列；转进程调度；

}w=1;}（mutex普通锁）(3)上锁原语和开锁原语2进程及进程管理——进程同步机构开锁原语

unlock输入：锁变量w输出：无{

if(w的等待队列不为空)

{移出等待队列首元素，插入到就绪队列；置该进程为就绪状态；}

w=0;}(4)用上锁原语和开锁原语实现互斥

上锁原语w

进入临界区csb

开锁原语w进程B

上锁原语w

进入临界区csa

开锁原语w进程A2、信号灯和P、V操作1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increment(verhogen)），是一种卓有成效的进程同步机制。

72/130

(1)什么是信号灯信号灯是一个确定的二元组(s，q)，s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管理。

s是整型变量，代表可用资源实体的数量。

s>0时，表示有可用资源，进程执行(绿灯)；

s

<=

0时，表示没有可用资源，进程停止执行(红灯)；

注意：创建信号灯时，应准确说明信号灯s的意义和初值

(这个初值绝不能为负值)。进程及进程管理——进程同步机构(2)P操作①

P操作的定义

对信号灯s的p操作记为p(s)。p(s)是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用p(s)的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。②

P操作的实现

入口

S-1→S

S≥0?转进程调度返回入信号灯等待队列置“等待状态”≥0P操作原语流程图进程及进程管理——进程同步机构(3)V操作①

V操作的定义

对信号灯s的v操作记为v(s)。v(s)是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队列上的一个进程。②V操作的实现

入口

S+1→S从信号灯的等待队列中取出首元素入就绪队列置“就绪状态”返回

S≤0?>0V操作原语流程图进程及进程管理——进程同步机构进程互斥与同步的实现进程及进程管理——进程互斥与同步的实现1.用上锁原语和开锁原语实现进程互斥

(1)框图描述上锁原语进入临界区csa进程pa开锁原语上锁原语进入临界区csb进程pb开锁原语两个进程利用上锁、开锁原语实现互斥进程及进程管理——进程互斥与同步的实现(2)程序描述程序task1main()pa()pb(){{{

intw=0；∕*互斥锁,初值为0*∕

cobeginlock(w)；lock(w)；

pa()；csa

；csb

；

pb()；unlock(w)；unlock(w)；

coend

}}}

进程及进程管理——进程互斥与同步的实现2.用信号灯的P、V操作实现互斥

(1)框图描述设：mutex为互斥信号灯，初值为1。p(mutex)进入临界区csa进程pa

v(mutex)p(mutex)进入临界区csb进程pb

v(mutex)两个进程利用信号灯的P、V操作实现互斥进程及进程管理——进程互斥与同步的实现(2)程序描述main(){intmutex=1；∕*互斥信号灯*∕

cobeginpa()；

pb()；

coend}pa()pb(){{p(mutex)；p(mutex)；

csa

；csb

；

v(mutex)；v(mutex)；

}}

(3)信号灯可能的取值两个并发进程，互斥信号灯的值仅取1、0和－1三个值。mutex=1

表示没有进程进入临界区;mutex=0

表示有一个进程进入临界区;mutex=－1表示一个进程进入临界区，另一个进程等待进入。进程及进程管理——进程互斥与同步的实现习题4-12:n个并发进程共用一个公共变量，写出用信号灯实现n个进程互斥的程序描述，给出信号灯的取值范围，并说明取值含义main(){intmutex=1；∕*互斥信号灯*∕

cobegin

p1()；p2()；…pn()；

coend}pi(){p(mutex)；访问变量Q；

v(mutex)；

}n个并发进程，互斥信号灯的取值可能为 1,0,-1,…,-(n-1)进程及进程管理——进程互斥与同步的实现(4)推论推论1：若信号灯s为正值，则该值等于在挂起进程之前对信号灯s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数。推论2：若信号灯s为负值，则其绝对值等于登记排列在该信号灯s队列之中等待的进程个数，亦即恰好等于对信号灯s实施P操作而被挂起并进入信号灯s队列的进程数。推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作。82/130

(5)共享变量的例子（互斥）

x代表某航班机座号，pa和pb两个售票进程，售票工作是对变量x加1。试用信号灯的P、V操作实现这两个进程的互斥。

设：mutex为互斥信号灯，初值为1。main()pa()pb(){{{

x=0;mutex=1;

cobeginp(mutex)；p(mutex);

Pa()

x:=x+1；x:=x+1；

Pb()

v(mutex)；v(mutex)；

coend

}}}进程及进程管理——进程互斥与同步的实现

(6)看病化验的例子（同步）

医生的看病活动和化验室的化验活动的同步约束关系：

1、看病进程开出化验单，并发送给化验进程，化验进程才能开始工作，否则化验进程必须等待；

2、化验进程化验完毕后得到化验结果，并发送给看病进程，看病进程才能根据化验结果确定医疗方案，否则看病进程必须等待。进程及进程管理——进程互斥与同步的实现main(){ints1=0；∕*表示有无化验单，即化验单资源的个数*∕

ints2=0；∕*表示有无化验结果，即化验结果资源的个数*∕

cobegin

化验()；看病()；

coend}看病()化验(){{while(没下班){while(没下班){

看病

p(s1)；

v(s1)；化验；

p(s2)；

v(s2)

;诊断}

}}}

进程及进程管理——进程互斥与同步的实现3.两类同步问题的解法

(1)合作进程的执行次序①进程流图

p2p3p1

f

sp1p2p3

s

f进程流图示例进程及进程管理——进程互斥与同步的实现p3

s

fp5p1p2p4p6p7p8②

例：pa、pb、pc为一组合作进程，其进程流图如图所示，试用信号灯的p、v操作实现这三个进程的同步。pbpcpa

f

s

ⅰ分析任务的同步关系任务启动后pa先执行，当它结束后，pb、pc可以开始执行，pb、pc

都执行完毕后，任务终止。ⅱ信号灯设置设两个同步信号灯sb、sc分别表示进程pb和pc能否开始执行，其初值均为0。ⅲ同步描述

papbpcp(sb)；p(sc)；

v(sb)；

v(sc)；3个合作进程的进程流图进程及进程管理——进程互斥与同步的实现pbpcpa

f

s程序task4main(){intsb=0；∕*表示pb进程能否开始执行*∕

intsc=0；∕*表示pc进程能否开始执行*∕

cobeginpa()；

pb()；

pc()；

coend}pa()pb()pc(){{{

p(sb)；p(sc)；

v(sb)；

v(sc)；

}}}

3个合作进程的进程流图进程及进程管理——进程互斥与同步的实现习题4-13：用信号灯实现下面两组进程之间的同步，写出程序描述。进程及进程管理——进程互斥与同步的实现p2p3p1

f

sp4p1p3p2

f

s(a)(b)进程及进程管理——进程互斥与同步的实现p2p3p1

f

sp4(a)习题4-13(a)main(){ints2=0；∕*表示p2进程能否开始执行*∕

ints3=0；∕*表示p3进程能否开始执行*∕

ints4=0；∕*表示p4进程能否开始执行*∕

cobeginp1()；p2()；p3()；p4()；

coend}p1()p2()p3()p4(){{{{...

p(s2)；p(s3)；p(s4)；

v(s2)；...

...

...

v(s3)；}}}

v(s4)；}

进程及进程管理——进程互斥与同步的实现习题4-13(b)main(){ints1=0；∕*表示p1进程能否执行完*∕

ints2=0；∕*表示p2进程能否执行完*∕

cobeginp1()；p2()；p3()；

coend}p1()p2()p3(){{{......

p(s1);

v(s1);

v(s2);

p(s2);}

}...}p1p3p2

f

s(b)进程及进程管理——进程互斥与同步的实现作业：

习题4-14p1p5

f

sp2p3p4

fp1p2

sp3p4p5(2)共享缓冲区的合作进程的同步的解法

计算进程cp和打印进程iop公用一个单缓冲，为了完成正确的计算与打印，试用信号灯的p、v操作实现这两个进程的同步。

缓冲区bufiop

cp①两个进程的任务计算进程cp经过计算，将计算结果送入buf；打印进程iop把buf中的数据取出打印。共享缓冲区的合作进程的同步示意图进程及进程管理——进程互斥与同步的实现②分析任务的同步关系

当cp进程把计算结果送入buf后，iop进程才能从buf中取出结果去打印，否则必须等待。当iop进程把buf中的数据取出后，cp进程才能把下一个计算结果数据送入buf中，否则必须等待。

缓冲区bufiop

cp共享缓冲区的合作进程的同步示意图进程及进程管理——进程互斥与同步的实现③信号灯设置

sa：表示缓冲区中是否有可供打印的计算结果，其初值为0。

sb：表示缓冲区有无空位置存放新的信息，其初值为1。

缓冲区bufiop

cp共享缓冲区的合作进程的同步示意图进程及进程管理——进程互斥与同步的实现②分析任务的同步关系

当cp进程把计算结果送入buf后，iop进程才能从buf中取出结果去打印，否则必须等待。当iop进程把buf中的数据取出后，cp进程才能把下一个计算结果数据送入buf中，否则必须等待。程序描述main(){intsa=0；∕*表示buf中有无信息*∕

intsb=1；∕*表示buf中有无空位置*∕

cobegincp()；iop()；

coend}cp()iop(){{while(计算未完成)while(打印工作未完成){{

得到一个计算结果；p(sa)；

p(sb)；从缓冲区中取一数；将数送到缓冲区中；v(sb)；

v(sa)；从打印机上输出；

}}}}

缓冲区bufiop

cp共享缓冲区的合作进程的同步示意图进程及进程管理——进程互斥与同步的实现习题4-15：

get，copy，put三个进程共用两个缓冲区s，t（其大小为每次存放一个记录）。get进程负责不断的把输入记录送入缓冲区s中；copy进程负责从缓冲区s中取出记录复制到缓冲区t中；put进程负责把记录从缓冲区t中取出打印。试用P、V操作实现这三个进程之间的同步。进程及进程管理——进程互斥与同步的实现

缓冲区s

缓冲区tgetcopyput习题4-18：（1）3个进程并发活动的流程图如图所示，其同步算法描述如下：main(){ints=-1;cobeginp1();p2();p3();coend}p1()p2()p3(){{{......p(s);v(s);v(s);...}}}进程及进程管理——进程互斥与同步的实现p1p3p2

f

s(b)习题4-18：（2）设a，b两进程共用一缓冲区t，a向t写入信息，b从t读出信息，算法框图如下所示，判断是否有错，指出错误原因并改正。

a进程b进程

while(1)while(1){{......向t写入信息P(s)

......

V(s)从t读信息......}}

注：信号灯s的初值为0进程及进程管理——进程互斥与同步的实现习题4-18：（3）设a，b两进程为并发进程，它们共享一临界资源。其执行临界区的算法框图如下所示，判断是否有错，指出错误原因并改正。

a进程b进程

while(1)while(1){{......

CSa

P(s1)

V(s1)

CSb

P(s2)V(s2)......}}

注：信号灯s1，s2的初值为0进程及进程管理——进程互斥与同步的实现4.生产者——消费者问题

(1)生产者——消费者问题的例子

①

计算进程和打印进程 多个计算进程cp不断产生数据，是生产者；

多个打印进程iop不断打印数据，是消费者； 有多个缓冲区；

②通信问题发消息进程send不断产生消息，是生产者；收消息进程receive不断接收消息，是消费者。进程及进程管理——进程互斥与同步的实现(2)生产者——消费者问题的一般解答

①生产者——消费者问题图示

②生产者与消费者的同步关系生产者：当有界缓冲区中无空位置时，要等待；向有界缓冲区放入物品后，要发消息。消费者：当有界缓冲区中无物品时，要等待；从有界缓冲区取出物品后，要发消息。c1p1.........c2c3ck...p2p3pm生产者——消费者问题示意图进程及进程管理——进程互斥与同步的实现③信号灯设置

ⅰ两个同步信号灯——sb

：表示空缓冲区的数目，初值=nsa

：表示满缓冲区(即信息)的数目，初值=0

ⅱ一个互斥信号灯——

mutex：表示有界缓冲区是否被占用，初值=1c1p1.........c2c3ck...p2p3pm生产者——消费者问题示意图进程及进程管理——进程互斥与同步的实现④同步描述

生产者:消费者:生产；p(sa)；p(sb)；p(mutex)；p(mutex)；从有界缓冲区中取数据；将数据放入有界缓冲区；v(mutex)；v(mutex)；v(sb)；v(sa)；消费;进程及进程管理——进程互斥与同步的实现⑤程序描述main(){intsa=0；∕*满缓冲区的数目*∕

intsb=n；∕*空缓冲区的数目*∕

intmutex=1；∕*对有界缓冲区进行操作的互斥信号灯*∕

cobeginp1()；p2()；…pm(