运筹学第3章课件

§3.1进程的概念§3.2进程的描述§3.3进程状态及其转换§3.4进程控制§3.5进程互斥§3.6进程同步§3.7进程通信§3.8死锁问题§3.9线程本章小结本章内容进程管理第三章1进程的定义和特征进程的同步和互斥用信号量机制解决进程同步、互斥、前趋图问题

进程死锁本章重点和难点：2§3.1进程的概念问题：如何充分准确地反映现代操作系统程序并发性、资源共享性、用户随机性？需要：1、准确细致地描述计算机程序的执行过程2、更加精准贴切的资源分配的基本单位3前趋图概念：前趋图是一个有向无环图。要求每个结点可用于表示一条语句、一个程序段等结点间的有向边表示在两个结点之间存在的前趋关系如果(pi，pj)可写成pi—>pj，称pi是pj的前驱，而pj是pi的直接后继。51234567存在下面的前驱关系：P1->P2，P1->P3；P1->P4；P2->P5；P3->P5；P5->P7;P4->P6,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)}前趋图（续1）6注意：前驱图中不存在循环。如：S2S3

，

S3S2

显然这种前驱关系是不可能满足的，S3的执行要依赖于S2的执行结果，S2的执行结果又要依赖于S3的执行结果，这种程序是不可能执行下去的。

前趋图（续2）73.1.1程序的并发执行程序的顺序执行CPU是通过时序脉冲来控制顺序执行指令。其执行过程可以描述为：RepeatIR←M［pc］

pc←pc+1〈Execute(instructioninIR)〉UntilCPUhaltIR：指令寄存器，pc：程序计数器，M：存储器。82.多道程序系统中程序执行环境的变化现代OS均支持多个程序并发运行。须具有下述三个特点：(1)独立性-各程序逻辑上独立的，之间无逻辑上的制约关系。(2)随机性-在多道程序环境下，特别是在多用户环境下，程序和数据的输入与执行的开始时间都是随机的。(3)资源共享——资源共享将导致对进程执行速度的制约。硬件资源：CPU、输入输出设备，存储器软件资源：各种例行程序、各种共享的数据1、多道程序环境下执行程序的道数>计算机系统中CPU的个数2、单CPU中，则由N－1道程序处在等待CPU的状态；3、输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享

113.程序的并发执行

I1I2I4I3C1C2C3P1C4P4P3P2程序并发执行时的前驱图12(1)什么是程序的并发执行简单解释：交替操作技术。目的：增强计算机系统处理能力、提高资源利用率分为两种情形：第一，多道程序系统的程序执行环境变化所引起的多道程序的并发执行（宏观上是同时进行微观上仍是顺序执行）。第二，在某道程序的几个程序段中（例如几个程序），包含着一部分可以同时执行或顺序颠倒执行的代码。例如语句：read(a)；read(b)；同时执行不会改变顺序程序所具有的逻辑性质。14逻辑上互相独立的程序或程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序段的执行尚未结束，另一个程序段的执行已经开始。程序的并行执行：指一组程序按独立的、异步的速度执行。并行执行不等于时间上的重叠。并发执行过程描述为：程序的并发科学定义

S0 Cobegin P1；P2；...Pn CoendSnP1，P2，…，Pn也可由同一程序段中的不同语句组成15Bernstein提出两相邻语句S1，S2可并发执行条件：将程序中任一语句Si划分为两个变量的集合

R(Si)和W(Si)R(Si)={a1a2…am}，aj(j=1，…，m)是语句Si在执行期间必须对其进行参考的变量集合；W(Si)={b1b2…bn}，bj(j=1，…，n)是语句Si在执行期间必须对其进行修改、访问的变量集合；16如果对于语句S1和S2，须有①R(S1)∩W(S2)={φ}，②W(S1)∩R(S2)={φ}，③W(S1)∩W(S2)={φ}同时成立，则语句S1和S2是可以并发执行的。改写：若两个程序p1、p2能满足下述条件，他们便能并发执行，且具有可再现性。R(p1)∧W(p2)∨R(p2)∧W(p1)∨W(p1)∧W(p2)=φ17例：若有两条语句Ci＝a－b和Wi＝c＋1，判断它们是否可以并发执行？

解：它们的“读集”和“写集”分别为

R（C：=a－b）={a，b}；R（W：=c＋1）={c}W（C：=a－b）={c}；W（Wi：=c＋1）={w}R（C：=a－b）∩W（Wi:=

c＋1）={Φ}R（W：=c＋1）∩W（C：=a－b）={c}结论：两条语句不能并发执行18例：设有两个程序段。getaddr(top)：取内存数据块地址；reladdr(blk)：将内存数据块地址blk放入堆栈S中。分别描述为：proceduregetaddr(top)begin localr r←(top) top←top-1 return(r)end

procedurereladdr(blk)begin top←top+1 (top)←blkEnd结论：存在程序的并发执行使得其执行结果不再具有封闭性和可再现性，且可能造成程序出现错误。getaddr和reladdr程序段进行顺序执行，其执行结果具有封闭性和可再现性。

若采用并发执行，则在单CPU系统中，将有可能出现此种情况：reladdr执行未完，getaddr开始并抢占了处理机。导致getaddr的执行结果失败。20错误分析：两程序段共享堆栈S，使得执行结果受执行速度影响（程序员不希望的）。措施：采取适当的策略制约、控制各并发程序段的执行速度，就是控制和协调各程序段执行过程中的软、硬件资源的共享和竞争。为此，必须有一个描述各程序段执行过程和共享资源的基本单位。程序——顺序性、静态性以及孤立性，无法反映操作系统所应该具有的程序段执行的并发性、用户随机性，以及资源共享等特征。

引入的对象——必须能描述程序的执行过程且能作为共享资源的基本单位——进程。21(1)进程,动态概念，程序，静态概念。程序是指令的有序集合，没有任何执行的含义。而进程则强调执行过程，它动态地被创建，并被调度执行后消亡。(2)进程具有并发特征，而程序没有。由进程的定义可知，进程具有并发特征的两个方面，即独立性和异步性。即在不考虑资源共享的情况下，各进程的执行是独立的，执行速度是异步的。程序不反映执行过程，不具有并发特征。(3)进程是竞争计算机系统资源的基本单位，其并发性受到系统自己的制约。制约即对进程独立性和异步性的限制。(4)不同的进程可以包含同一程序，只要该程序所对应的数据集不同。（

1个程序可以对应多个进程，但1个进程只能对应1个程序）进程与程序的区别233.1.3作业和进程的关系(1)作业是用户向计算机提交任务的任务实体。在用户向计算机提交作业之后，系统将它放入外存中的作业等待队列中等待执行。而进程则是完成用户任务的执行实体，是向系统申请分配资源的基本单位。任一进程，只要它被创建，总有相应的部分存在于内存中。(2)一个作业可由多个进程组成。且必须至少由一个进程组成，但反过来不成立。(3)作业的概念主要用在批处理系统中。而进程的概念则用在几乎所有的多道系统中。243.2.1进程控制块PCB创建一个进程时，应首先创建其PCB：反映各并发进程间的制约关系和资源共享关系。当一个进程完成其功能之后，系统则释放PCB，进程也随之消亡。进程的PCB所包含的内容基本内容：(1)描述信息①进程名或进程标识号②用户名或用户标识号③家族关系26(2)控制信息①进程当前状态就绪态、执行态和等待状态。②进程优先级选取进程占有处理机的重要依据。与进程优先级有关的PCB表项有：a.占有CPU时间；b.进程优先级偏移；c.占据内存时间。③程序开始地址④各种计时信息给出进程占有和利用资源的有关情况。⑤通信信息通信信息用来说明该进程在执行过程中与别的进程所发生的信息交换情况。27(3)资源管理信息①占用内存大小及其管理用数据结构指针（进程页表指针）。②复杂系统中，还有对换或覆盖用的有关信息，如对换程序段长度，对换外存地址等。这些信息在进程申请、释放内存中使用。③共享程序段大小及起始地址。④输入输出设备的设备号，所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。这些信息在进程申请释放设备进行数据传输中使用。⑤指向文件系统的指针及有关标识等。进程可使用这些信息对文件系统进行操作。283.2.2进程上下文进程上下文：进程执行活动全过程的静态描述。包括计算机系统中与执行该进程有关的各种寄存器的值、程序段在经过编译之后形成的机器指令代码集（或称正文段）、数据集及各种堆栈值和PCB结构(图3.2)。这里，有关寄存器和栈区的内容是重要的。例如，没有程序计数器PC和程序状态寄存器PS，CPU将无法知道下条待执行指令的地址和控制有关操作。30图3.2进程上下文结构31进程切换：新老进程的上下文发生转换。在UNIXSystemⅤ中，进程上下文由用户级、寄存器级、系统级上下文组成。用户级：用户正文段、用户数据、用户栈等组成。寄存器级：由程序寄存器PC、处理机状态字寄存器PS、栈指针和通用寄存器的值组成。系统级：静态部分与动态部分。动态：进程进入和退出不同的上下文层次时，系统为各层上下文中相关联的寄存器值所保存和恢复的记录。静态：包括PCB结构、虚地址空间映射到物理空间用的有关表格和核心栈32图3.3UNIXSystemⅤ进程上下文组成系统级上下文的动态部分是与寄存器上下文相关联的333.2.3进程空间进程空间的大小只与处理机的位数有关。16位：空间大小为216，32：进程空间大小为232。用户程序、进程的各种控制表格等都按一定的结构排列在进程空间中。另外，在UNIX以及Linux等操作系统中，进程空间还被划分为用户空间和系统空间两大部分。

图3.4进程空间34§3.3进程状态及其转换3.3.1进程状态就绪状态、执行状态、等待状态。就绪状态：拥有除CPU之外的其他资源；分配到处

理机后，便可立即投入运行；执行状态：进程正在处理机上运行的状态。该进程已

获得必要的资源和处理机注：只有处于就绪状态的进程经调度选中之后才可进入执行状态。等待状态：（阻塞状态）进程等待某种事件完成（例如，等待输入/输出操作的完成）而暂时不能运行的状态。处于该状态的进程不能参加竞争处理机，此时，即使分配给它处理机，它也不能运行。35进程调度程序把处理机分配给进程状态变化：（1）就绪状态变化到运行状态。（2）运行状态变化到就绪状态。

（3）运行状态变化到等待状态。

（4）等待状态变化到就绪状态3.3.2进程状态转换图3.5进程状态转换36进程状态转换运行就绪等待图2－4进程的状态及其转换371)活动就绪→静止就绪2)活动阻塞→静止阻塞3)静止就绪→活动就绪4)静止阻塞→活动阻塞5)执行→静止就绪。6)静止阻塞→静止就绪状态转换细分进程的挂起挂起：暂时被淘汰出内存（资源不足）。当条件允许时，再次调回内存，重新进入就绪态。

引起挂起状态的原因有如下几方面：

（1）终端用户的请求。当终端用户在自己的程序运行期间发现有可疑问题时，希望暂停使自己的程序静止下来。亦即，使正在执行的进程暂停执行；若此时用户进程正处于就绪状态而未执行，则该进程暂不接受调度，以便用户研究其执行情况或对程序进行修改。我们把这种静止状态成为“挂起状态”。

（2）父进程的请求。有时父进程希望挂起自己的某个子进程，以便考察和修改子进程，或者协调各子进程间的活动。

（3）负荷调节的需要。当实时系统中的工作负荷较重，已可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能正常运行。

（4）操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账38§3.4进程控制进程控制——系统使用一些具有特定功能的程序段来创建、撤消进程以及完成进程各状态间的转换，从而达到多进程高效率并发执行和协调、实现资源共享的目的。

一般地，把系统态下执行的某些具有特定功能的程序段称为原语——分为两类机器指令级：执行期间不允许中断，它是一个

不可分割的基本单位。功能级：作为原语的程序段不允许并发执行。39进程控制的原语：创建原语、撤消原语、阻塞原语、唤醒原语等。为何用原语？1、保证封闭性和可再现性；2、减少系统开销，降低系统复杂度。用程序段做成原语。403.4.1进程创建与撤消1.进程创建(1)由系统程序模块统一创建。例如在批处理系统中，由操作系统的作业调度程序为用户作业创建相应的进程以完成用户作业所要求的功能。进程之间的关系是平等(2)由父进程创建。如在层次结构的系统中；进程之间有隶属关系，构成树型结构。属于某个家族的一个进程可以继承其父进程所拥有的资源。（3）系统资源分配和管理工作的系统进程，须由操作系统创建。（4）实现：创建原语—>扫描PCB链表调用者提供的有关参数填入空PCB表—>PCB结构。进程名\进程优先级\进程正文段起始地址\资源清单

其实现过程如图3.6。4142图3.6创建原语流图2.进程撤消导致进程被撤消的情形：(1)进程完成任务正常终止。(2)由于某种错误导致非正常终止。(3)祖先进程要求撤消某子进程。实现：撤消原语—>检查PCB进程链—>找进程的PCB结构—>释放资源、

从PCB进程链摘下PCB结构—>归还PCB空队列；

注：先考虑子进程的撤销（原理同）。创建原语和撤消原语：完成进程从无到有，从存在到消亡的变化。43图3.7撤消原语流图443.4.2进程的阻塞与唤醒1、被创建后的进程最初处于2、经调度程序选中后进入3、阻塞原语：a\进程期待某事件发生，被该进程自己调用阻塞自己。b\阻塞进程过程：首先，中断处理机和保存CPU现场；其次，将被阻塞进程置“阻塞”状态后插入等待队列；然后，调度程序选择新的就绪进程投入运行（避免处

理机空闲）。45就绪状态；执行状态；执行状态；等待状态；图3.8阻塞原语图464、唤醒原语1）事件发生进程被唤醒；2）唤醒进程的两种方法：a系统进程唤醒：系统进程统一控制事件的发生，将消息通知等待进程进入就绪队列。b事件发生进程唤醒;3)过程：首先，唤醒原语将被唤醒进程从等待队列中摘下；其次，被唤醒进程置为就绪状态之后，送入就绪队列；然后，返回原调用程序，或转向进程调度.47等待状态；就绪状态；图3.9唤醒原语48§3.5进程互斥3.5.1资源共享所引起的制约分析进程的并发执行的原因：1）用户程序的执行开始时间的随机性；2）提高资源利用率的需要3）资源有限性导致资源的竞争、共享对进程的执行过程的制约。临界区分析赋值语句： X=X+1；汇编语言书写：LOADA，XADDIA，1STOREA，X三语句执行期间，发生中断？原因：执行速度和对资源竞争失控。结果：错49设有两个计算进程ＰA，ＰB共享内存ＭS。其中ＭS分为三个领域，即系统区、进程工作区和数据区（如图3.10）。图3.10多进程共享内存栈区示例50分析：1、ＰA或ＰB

取空（getspace）数据块时：从栈取数据块位置；2、ＰA或ＰB释放（release(ad)）数据块时：将释放数据块地址入栈顶；这里，ad为待释放数据块的地址。3、若栈Ｓ非空，ＰA或ＰB可以用任意顺序释放和获取数据块。4、下面的描述，在进程并发执行时，getspace或release(ad)将有可能完不成所要求的功能。getspace和release(ad)可进一步描述为：51 getspace: begin local g g←stack［top］

top←top-1 end release(ad): begin top←top+1 stack［top］←ad end设时刻t0时，top=h0，则getspace和release(ad)可能按以下顺序执行：首先：

release(ad)的第一句执行，

t0：top←top+1 → top=h0+1；其次：getspace执行，得：52t1：g←stack［top］→g=stack［h0+1］；t2：top←top-1 → top=h0；然后：release(ad)的第二句执行，得：t3：stack［top］←ad→stack［h0］←ad；分析结果：1、调用getspace进程，取到一个未定义值；2、调用release(ad)进程把所释放的空块地址ad放入了h0中，覆盖了h0中的内容。如何保证执行结果的正确性？把getspace和release(ad)：两个各以一个动作完成的顺序执行单位。临界区（criticalregion）定义：不允许多个并发进程交叉执行的一段程序。由于它由属于不同并发进程的程序段共享公用数据或公用数据变量而引起的。故也被称为访问公用数据的那段程序。532.间接制约令不允许交叉执行的临界区按不同的公用数据划分为不同的类（class）。如：以公用数据栈Ｓ划分的临界区集合是{getspace,release}。对类给定一个唯一的标识名，系统容易区分。在程序的描述中，可用下列标准形式来描述临界区：

when〈类名〉do〈临界区〉od设类{getspace，release}的类名为sp，则getspace和release(ad)可重新描述为：

getspace: whenspdogetspce←stack［top］

top←top-1od release(ad):whenspdotop←top+1 stack［top］←adod54间接制约含义：

1、由于共享某一公有资源而引起的在临界区内不允许并发进程交叉执行的现象，称为由共享公有资源而造成的对并发进程执行速度的间接制约，简称间接制约。2、“间接”二字主要是指各并发进程的速度受公有资源制约，非进程间直接制约。3、受间接制约的类中各程序段在执行顺序上是任意的。

对于每一类，系统都有相应的分配和释放相应公有资源的管理办法，以制约并发进程。这就是互斥。553.什么是互斥1、定义：一组并发进程中的一个或多个程序段，因共享某一公有资源而导致它们必须以一个不允许交叉执行的单位。2、不允许两个以上的共享该资源的并发进程同时进入临界区称为互斥。一般情况下，作为程序段的一个过程不允许多个进程共同访问它（纯过程除外）。纯过程：1）在执行过程中不改变过程自身代码的一类过程。2）便于多个进程共享。但编制纯过程要对有关变量和工作区作相应的处理，使得执行效率受到影响。56一组并发进程互斥执行时必须满足如下准则：(1)

不能假设各并发进程的相对执行速度。(2)某个进程不在临界区时，它不阻止其他进程进入临界区。(3)若干个进程申请进入临界区时，只能允许一个进程进入。(4)进程应在有限时间内得以进入临界区。

准则(1)，(2)，(3)：保证各并发进程享有平等的、独立的竞争和使用公有资源的权利，且保证每一时刻至多只有一个进程在临界区；准则(4)：并发进程不发生死锁的重要保证。竞争公有资源间接制约进程互斥共享私有资源直接制约进程同步。573.5.2互斥的加锁实现推想：把临界区中的各个过程按不同时间排列调用。须做到：每个进程事先知道其他并发进程与系统的动作。不可能：用户程序执行的随机性决定的。办法：对临界区加锁。58设Ｓ:临界区类名,

key［Ｓ］:锁定位。加锁后的临界区程序描述如下：

lock(key［Ｓ］) 〈临界区〉 unlock(key［Ｓ］)key［Ｓ］=1：临界区可用key［Ｓ］=0：不可用。unlock(key［Ｓ］)只用一条语句即可实现。即：

key［Ｓ］←1lock(key［Ｓ］)须满足key［Ｓ］=0时，不允许任何进程进入临界区，而key［Ｓ］=1时仅允许一个进程进入临界区的准则，实现起来较为困难。59一种简便的实现方法是：

lock(x)beginlocalv repeat v←x untilv=1 x←0 end缺点：不能保证并发进程互斥执行所要求的准则(3)。因为：同时有几个进程调用lock(key［Ｓ］)时，在x←0语句执行之前，可能已有两个以上进程由于key［Ｓ］=1而进入临界区。解决：硬件设置“测试与设置指令”，保证第一步和第二步执行不可分离。注意：在系统实现时锁定位key［Ｓ］总是设置在公有资源所对应的数据结构中的。603.5.3信号量和Ｐ，Ｖ原语信号量（semaphore）分析加锁实现进程之间互斥？缺点：1）循环测试锁定位，

牺牲CPU时间；进程多，开销大；存在一些影响系统可靠性和执行效率的问题。2）会导致不公平现象；举例：进程PA和PB反复使用临界区

PA A：lock(key［Ｓ］) 〈Ｓ〉61 unlock(key［Ｓ］) GotoA PB B：lock(key［Ｓ］)

＜Ｓ＞

unlock(key［Ｓ］) GotoB分析：只有PA执行完unlock(key［Ｓ］)之后、执行GotoA语句之前的瞬间发生进程调度，使PA

让出处理机给PB，PB才有可能得到执行。这显然不太可能。所以，PB

将永远处于饥饿（starvation）原因：能否进入临界区是依靠自己的测试判断决定。举例：学生使用教室解决：引入信号量机制（教室管理员：信号量）62信号量的含义1、荷兰科学家E.W.Dijkstra提出来的；2、信号量sem是一整数（初值>0）

a、sem>=0,资源实体数b、sem<0,正在等待使用临界区的进程数;

3、建立一个信号量须做到a、说明所建信号量所代表的意义b、赋初值c、建立相应的数据结构（指向等待使用临界区的进程）。632.Ｐ，Ｖ原语1）含义：信号量的数值仅能由Ｐ，Ｖ原语操作改变Ｐ|Ｖ分别是荷兰语Passeren和Verhoog的头字母;相当于英文的pass和increment的意思2）过程：采用Ｐ，Ｖ原语，可以把类名为Ｓ的临界区描述为WhenＳdoＰ(sem)临界区Ｖ(sem)od。A、一次Ｐ原语操作：sem减1；B、一次Ｖ原语操作：sem加1。C、若某进程正在临界区内执行时，其他进程如果执行了Ｐ操作，则该进程将在等待队列中等待（不同于加锁），直到其他进程做Ｖ操作后，进入临界区（可能继续等待），Ｐ原语的执行真正结束。643）Ｐ原语的主要动作：(1)sem减1；(2)若sem减1后仍大于或等于零，则进程继续执行；若sem减1后小于零，则该进程被阻塞后入该信号相对应的队列中等待，然后转进程调度。4）Ｖ原语的操作主要动作：(1)sem加1；(2)若相加结果大于零，进程继续执行；(3)若相加结果小于或等于零，则从该信号的等待队列中唤醒一等待进程，然后再返回原进程继续执行或转进程调度。65图3.11Ｐ原语操作流程3.12Ｖ原语操作流程分析：PV过程若不用原语实现，怎样？多进程同时调用Ｐ或Ｖ操作，有可能在Ｐ操作刚把sem-1而未把对应进程送入等待队列时，Ｖ操作开始执行。从而，Ｖ操作将无法发现等待进程而返回。结论：Ｐ，Ｖ操作都必须以原语实现，且在Ｐ，Ｖ原语执行期间不允许中断发生。66?!使用加锁法的P、V原语软件实现方法: Ｐ（sem）：

begin

封锁中断；

lock(lockbit) val［sem］=val［sem］-1 ifval［sem］<0

保护当前进程CPU现场 当前进程状态置为″等待″

将当前进程插入信号sem等待队列 转进程调度

fi unlock(lockbit)；开放中断

end67Ｖ（sem）：

begin

封锁中断；

lock(lockbit) va［sem］=val［sem］+1 ifval［sem］≤0 localk

从sem等待队列中选取一等待进程，将

其指针置入k中 将k插入就绪队列 进程状态置“就绪”

fi unlock(lockbit)；开放中断end使用加锁法的P、V原语软件实现方法(续):683.5.4用Ｐ，Ｖ原语实现进程互斥用信号量实现两并发进程PA，PB互斥的描述如下：sem：互斥信号量，值范围为(1,0,-1)。A、sem=1表示进程PA和PB都未进入类名为Ｓ的临界区B、sem=0表示进程PA或PB已进入类名为Ｓ的临界区C、sem=-1表示进程PA和PB中，一个进程已进入临界区，而另一个进程等待进入临界区。2)描述：

PA： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)： ：

69PB： Ｐ(sem) 〈Ｓ〉

Ｖ(sem)：

：举例9：生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：

（1）进程A专门拣黑子，进程B专门拣白子；

（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子；分析：

第一步：确定进程间的关系。由功能（2）可知进程之间是互斥的关系。

第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设为1。

70实现：begin

s:semaphore;s:=1;

cobegin

processA

begin

L1:P(s);

拣黑子；

V(s);

gotoL1;

end;

processB

begin

L2:P(s);

拣白子；

V(s);

gotoL2;

end;coend;

end;

提示：判断进程间是否互斥，关键是看进程间是否共享某一公有资源，一个公有资源与一个信号量相对应。确定信号量的值是一个关键点，它代表了可用资源实体数。71问题：使用P、V原语和加锁法在实现并发进程间的互斥时有何异同?加锁法是对临界区加锁以实现互斥。当某个进程进入临界区后，就锁定临界区直到它退出临界区，其他进程要进入时，须要不断测试临界区是否被用着，直到临界区空才能进入。可靠性、执行效率不高。P，V原语操作能改变信号量的数值，信号量（sem）可代表管理相应临界区公共资源的实体。当sem>=0时，表示可供并发进程使用的资源实体数，当sem<0是时，表示正在等待使用临界区的进程数。而一次P操作使得sem减1，一次V操作使得sem加1。

P，V操作中进程不需象加锁时要不断的测试，而是在队列里等待其他进程执行V操作时，就可以进入临界区了。这样P，V操作比加锁更简单，且表达能力强，但P，V相对来说不安全，会出现死锁，遇复杂同步互斥问题时会更复杂。72§3.6进程同步3.6.1同步的概念已知：间接制约——影响进程执行速度问题：是否存在着其他制约关系影响执行速度？看下面的例子。计算进程和打印进程共同使用同一缓冲区Buf。计算进程反复地把每次计算结果放入Buf中，而打印进程则把计算进程每次放入Buf中的数据通过打印机打印输出。如果不采取任何制约措施，这两个进程的执行起始时间和执行速度都是彼此独立的，其相应的控制段可以描述为：73PC

: A: localBuf Repeat Buf←Buf Until Buf=空 计算 得到计算结果

Buf←计算结果

Goto APP: : B: localPri Repeat Pri←Buf Until Pri≠空 打印Buf中的数据 清除Buf中的数据

Goto B分析：1、假设：两进程对buf已经采取互斥措施；2、存在两处测试；

导致CPU时间的极大浪费；3、PC、PP

互相制约；互为条件和结果；结论：一组在异步环境下的并发进程，各自的执行结果互为对方的执行条件，从而限制各进程的执行速度的过程称为并发进程间的直接制约。执行起始时间的随机性和执行速度的独立性解决：采用消息机制。同步进程间通过消息的传递决定进程的运行。74同步的定义：

把异步环境下的一组并发进程，因直接制约而互相发送消息而进行互相合作、互相等待，使得各进程按一定的速度执行的过程称为进程间的同步。

具有同步关系的一组并发进程称为合作进程，合作进程间互相发送的信号称为消息或事件。过程1：wait(消息名)——等待合作进程发来的消息过程2：signal(消息名)——向合作进程发送消息利用过程wait和signal，可以简单地描述上面例子中的计算进程PC和打印进程PP的同步关系如下：75(1)设消息名Bufempty表示Buf空，消息名Buffull表示Buf中装满了数据。(2)初始化Bufempty=true，Buffull=false。(3)描述：

PC

：

A: wait(Bufempty)

计算

Buf←计算结果

Bufempty←false signal(Buffull) Goto A等待到消息名为true的进程继续执行向合作进程发送所需要的消息名，并将其值置为true76 PP ：

B: wait(Buffull)

打印Buf中的数据 清除Buf中的数据

Buffull←false

signal(Bufempty) Goto B

等待到消息名为true的进程继续执行向合作进程发送所需要的消息名，并将其值置为true773.6.2私用信号量进程间的同步的另一实现方法：信号量原理：把各进程之间发送的消息作为信号量；私用信号量（

PrivateSemaphvre）：仅与制约进程及被制约进程有关的。是从制约进程发送来的进程Pi的执行条件所需要的消息。公用信号量：互斥时使用的信号量。783.6.3用Ｐ，Ｖ原语操作实现同步Ｐ，Ｖ原语+私用信号量实现进程同步1、首先，设置私用信号量；2、其次，私用信号量赋初值；3、然后，利用Ｐ，Ｖ原语和私用信号量规定各进程

的执行顺序。79例10：设进程PA和PB通过缓冲区队列传递数据（如图3.13）。PA为发送进程，PB为接收进程。PA发送数据时调用发送过程deposit(data)，PB接收数据时调用过程remove(data)。且数据的发送和接收过程满足如下条件：(1)在PA至少送一块数据入一个缓冲区之前，PB不可能从缓冲区中取出数据（假定数据块长等于缓冲区长度）；(2)PA往缓冲队列发送数据时，至少有一个缓冲区是空的；(3)由PA发送的数据块在缓冲队列中按先进先出（FIFO）方式排列。描述发送过程deposit(data)和接收过程remove(data)。图3.13缓冲区队列80分析：1、PA调用的过程deposit(data)和PB调用的过程remove(data)必须同步执行（？）2、分三步描述过程deposit(data)和remove(data)：（1)设Bufempty为进程PA的私用信号量，Buffull为进程PB的私用信号量；（2)令Bufempty的初始值为n（n为缓冲队列的缓冲区个数），Buffull的初始值为0；（3)描述：81PA:deposit(data):beginlocalx/*x:缓冲区的区号 P(Bufempty)； 按FIFO方式选择一个空缓冲区Buf(x)；

Buf(x)←data Buf(x)置满标记/*便于区别和搜索空缓冲区及

非空缓冲区 Ｖ（Buffull）/*

Buffull置为1，并将消息传给PB

endPB:remove(data):Beginlocalx

Ｐ（Buffull）； 按FIFO方式选择一个装满数据的缓冲区Buf(x) data←Buf(x) Buf(x)置空标记 Ｖ(Bufempty)end82思考1：在该题中需要考虑互斥吗？为什么？如果每次只允许一个进程对缓冲队列进行操作时怎么办？思考2：在例9中，若增加以下条件（3）：（3）当一个进程拣了一个棋子（黑子或白子）以后，必让另一个进程拣一个棋子（黑子或白子）

请用P、V原语实现进程操作。833.6.4生产者-消费者问题（producer-consumerproblems）概念的产生：同步和互斥问题模型化。生产者：释放资源的进程，如计算进程PC消费者：使用同类资源的进程，如打印进程PP外部设备、内存及缓冲区、临界区、数据等84例11把一个长度为ｎ的有界缓冲区（n>0)与一群生产者进程Ｐ1，Ｐ2，…，Ｐm和一群消费者进程Ｃ1，Ｃ2，…，Ｃk联系起来（如图3.14所示）。设生产者进程和消费者进程是互相等效的，其中，各生产者进程使用的过程deposit(data)和各消费者使用的过程remove(data)可描述如下：生产者和消费者之间满足如下条件：(1)消费者想接收数据时，有界缓冲区中至少有一个单元是满的；(2)生产者想发送数据时，有界缓冲区中至少有一个单元是空的。

(3)由于有界缓冲区是临界资源，因此，各生产者进程和各消费者进程之间必须互斥执行。85图3.14生产者-消费者问题86具有n个缓冲区的缓冲池生产者——消费者问题871）mutex：公用信号量；初值1，可用有界缓冲区个数avail：为生产者进程私用信号量，初值为nfull：消费者进程私用信号量。初值为0；deposit(data):begin

Ｐ（avail） Ｐ（mutex） 送数据入缓冲区某单元 Ｖ（mutex） Ｖ（full）end88remove(data):beginＰ（full）Ｐ（mutex） 取缓冲区中某单元数据Ｖ（mutex）Ｖ（avail）

end

注：Ｐ、Ｖ原语的操作次序。1、Ｖ原语是以任意次序。2、但Ｐ原语则不然，如果次序混乱，

将会造成进程之间的死锁。问题：为什么？89P操作顺序不当会产生死锁

例：有执行顺序如下：Producer:Consumer:P(empty);P(mutex);P(mutex);P(full);Oneunit->buf;Oneunitbuf;V(mutex);V(mutex);V(full);V(full);分析：当full=0,mutex=1时，执行顺序有：Consumer.P(mutex);Consumer.P(full);//显然，Consumer阻塞，等待Producer发出的full信号；Producer.P(empty);Producer.P(mutex);//显然，Producer阻塞，等待Consumer发出的empty信号；结果：发生死锁！问：还有其他的执行序列可以产生死锁吗？90P、V小结1、信号量的物理含义：

1)S>0表示有S个资源可用

2)S=0表示无资源可用

3)S<0则|S|表示S等待队列中的进程个数

4)P(S):表示申请一个资源

5)V(S)表示释放一个资源。信号量的初值应该大于等于02、P.V操作必须成对出现，有一个P操作就一定有一个V操作

1)当为互斥操作时，它们同处于同一进程

2)当为同步操作时，则不在同一进程中出现

3)如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至

关重要,一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前.而两个V操作无关紧要91

1、必须置一次且只能置一次初值

2、初值不能为负数

3、只能执行P、V操作信号量的使用92§3.7进程通信（communication）含义：进程间信息交换（传送数据）。分类：根据通信内容可以划分为二种。A、低级通信：进程间控制信息的交换（传送一两个

字节，控制进程执行速度）信号量机制作为同步工具是卓有成效的，但作为通信工具则不够理想？

（效率低。通信对用户不透明。）B、高级通信：大批量数据传送（为了交换信息）。用户可以直接利用操作系统所提供的一组通信命令933.7.1进程的通信方式在单机系统中，进程间通信可分为4种形式：(1)主从式；(2)会话式；(3)消息或邮箱机制；(4)共享存储区方式。主从式特点：①主进程可自由地使用从进程的资源或数据；②从进程的动作受主进程的控制；③主进程和从进程的关系是固定的。例：终端控制进程和终端进程。94会话方式特点：①使用进程在使用服务进程所提供的服务之前，必须得到服务进程的许可；②服务进程根据使用进程的要求提供服务，但对所提供服务的控制由服务进程自身完成。③使用进程和服务进程在通信时有固定连接关系。例：用户进程与磁盘管理进程之间的通信。95消息或邮箱机制的特点：①只要存在空缓冲区或邮箱，发送进程就可以发送消息。②与会话系统不同，发送进程和接收进程之间无直接连接关系，接收进程可能在收到某个发送进程发来的消息之后，又转去接收另一个发送进程发来的消息③发送和接收进程间存在缓冲区或邮箱来存放被传送消息。消息的组成缓冲区或邮箱通信结构96共享存储区方式：1、不要求数据移动；2、共享数据区属于互相通信进程的一个组成部分；3、两个需要互相交换信息的进程通过对同一共享数据区（sharedmemory）的操作来达到互相通信的目的。973.7.2消息缓冲机制原理图：两通信进程必须满足下列条件1在发送进程把消息写入缓冲区和把缓冲区挂入消息队列时，应禁止其他进程对缓冲区消息队列的访问。同理，接收进程取消息时也禁止其他进程访问缓冲区消息队列2当缓冲区中没有信息存在时，接收进程不能接收到任何消息3发送进程是否可以发送消息，则由发送进程是否申请到缓冲区决定。发送进程在自己的内存空间设置一个把要发送的消息填入发送区发送区接收区接收进程在自己的内存空间设置一个公用缓冲区需要互斥访问98分析：1)mutex:控制对缓冲区访问的互斥信号量，SM:接收进程的私用信号量;2)赋初值。Mutex=1，SM=0（等待接收的消息个数）3)过程功能：send(m)：消息m送往缓冲区；Receive(m)：消息m从缓冲区读往自己的数据区，Send(m)和Receive(n)可分别描述为：99Send(m): begin

向系统申请一个消息缓冲区 Ｐ（mutex）/*使用公用缓冲区 将发送区消息m送入新申请的消息缓冲区

把消息缓冲区挂入接收进程的消息队列 Ｖ（mutex）/*释放缓冲区 Ｖ（SM）/*向接收进程发送消息

endReceive(n): begin

Ｐ（SM）/*等待接收的消息的个数 Ｐ（mutex）/*使用公用缓冲区 摘下消息队列中的消息n

将消息n从缓冲区复制到接收区 释放缓冲区 Ｖ（mutex）/*释放公用缓冲区

end100特别注意：

虽然缓冲区总数已知，但消息队列是按接收进程排列，故同一时间内，系统中存在着多个消息队列；且这些队列长度不固定。结论：发送进程无法在Send过程用Ｐ操作判断信号量SM1013.7.3邮箱通信邮箱含义：由发送进程申请建立一与接收进程链接的大小固定的私有数据结构。构成：逻辑上分成两部分：信箱头和由若干格子组成的信箱体信箱中每个格子存放一封信，信箱中格子的数目和每格的大小在创建信箱时确定。优点：发送与接收的随机性。条件：

进程间的通信要满足

a.发送进程发送消息时，邮箱中至少要有一个空格存放该消息

b.接收进程接收消息时，邮箱中至少要有一个消息存在。102发送进程A

邮箱头

…邮箱体接收进程BDeposite(m)Remove(m)

邮箱通信结构邮箱头：邮箱名称、邮箱大小、拥有该邮箱的进程名邮箱体：存放消息103算法设计：1、定义：fromnum：发送进程的私用信号量；mesnum：接收进程的私用信号量；2、赋初值：fromnum=n，信箱的空格数，

mesnum=0。消息个数3、描述：

Deposit(m);BeginlocalxP(fromnum)空格数减1

选择空格x

将消息m放入空格x中置格x的标志为满V(mesnum)向接收进程发送消息end

消息个数＋1Remove(m)beinglocalxP(mesnum)消息个数减1

选择满格x

把满格x中的消息取出放m中置格x标志为空

V(mesnum)空格个数加1end1043.7.4进程通信的实例——和控制台的通信1、定义：KCP：键盘控制进程；DCP：显示控制进程；CCP：会话控制进程，完成用户进程和控制台终端的通信2、通信过程如图3.18。进程死锁1261051、控制台键盘的输入放入缓冲队列inbuf中2、CCP从inbuf中取出消息(来自控制台的指示)3、CCP的提问，以消息形式放入outbuf中；4、DCP从outbuf中取出消息送至显示器，以供操作员判断106KCP和DCP的动作1）KCP和键盘KP发生通信；2）DCP和显示器动作DP的通信；107KCP可描述如下：设T-Ready：键盘KP私用信号量；初值为0T-Busy：控制进程KCP的私用信号量，初值1。 初始化｛清除所有inbuf和echobuf} beginlocalx

Ｐ（T-Ready） 从键盘数据传输缓冲x中取出字符m记为x.m Send(x.m)

将x.m送入echonuf

Ｖ（T-Busy）

end

repeatlocalx

Ｐ（T-Busy）把键入字符放入数据传输缓冲x

Ｖ（T-Ready）Until终端关闭键盘动作KP：108初始化{清除输出缓冲outbuf，echo模式置false}beginifoutbuf满then receive(k)/*CCPk*/

Ｐ（D-Busy） 把k送入显示器数据缓冲区 Ｖ（D-Ready）else echo模式置true echobuf中字符置入显示器数据缓冲区

fi设D-Ready：0(DP);D-Busy:1(DCP)。

repeatif echo模式

then打印显示器数据缓冲区

中字符

else

Ｐ（D-Ready）打印显示器数据缓冲区中消息Ｖ（D-Busy）

Until 显示器关机DCP动作：显示器动作DP：109(2)CCP和KCP及DCP的接口CCP从inbuf中读出消息消息写入outbuf?Read(x):BeginP（inbuf-full）

Copy(inbufintox)/*把inbuf中的所有字符读到用户进程数据区x处

Ｖ（inbuf-empty）

endWrite(y):begin

Ｐ（outbuf-empty）

Copy(outbuffromy)/*把用户进程y处的消息写到outbuf中

Ｖ（outbuf-full）

end110这里，inbuf-full和inbuf-empty分别是CCP和KCP的私用信号量，在过程Send(m)和Read(x)中使用，其初值分别为0和1。由于在KCP中，Send(m)被用来将字符一个个地送入inbuf中，Send(m)过程必须要作一定的改动，也就是要加入缓冲计数功能和把inbuf的长度看作是固定的。另外，outbuf-full和outbuf-empty则是DCP和CCP的私用信号量，在过程receive(k)和write(y)中使用。其初值分别为0和1。由于outbuf的长度是固定的，所以receive(k)过程也应作相应的修改。111(3)CCP与用户进程的接口除了和KCP及DCP的通信之外，CCP还要从各用户进程那里得到提问和向提问的用户进程转达从控制台来的指示。因此，CCP和用户进程之间也存在着通信关系。设各用户进程向CCP发出的提问，用消息组成队列RQ。各用户进程把消息送入RQ时，必须互斥操作，否则将引起RQ队列混乱。因此，设互斥用信号量rq，初值为1。另外，CCP只有在用户进程提问之后才负责向控制台转发提问和向用户进程转达控制台的指示。因此，还必须为CCP设置一私用信号量question以计算用户进程所提出的问题数目。信号量question的初值为0。112另外，由于各用户进程在CCP发出回答消息之后，不一定马上就能处理CCP所发出的回答消息，因而，需设置相应的消息接收队列SQi。SQi和RQ的关系如图3.19。图3.19CCP和用户进程接口113与对RQ队列的操作时相同，对SQi队列的操作也必须是互斥的，因而，设互斥信号量sqi，其初值为1。除此之外，为了保证CCP和各用户进程之间在获得回答的同步，还需设一私用信号量answeri以计算SQi中的消息个数。CCP和用户进程的接口可描述如下：

U-receive(m): begin

Ｐ（question）

whenrqdo从RQ中取出mod return(m) end114这里，采用了互斥变量rq作为临界区名。U-receive(m)描述从RQ取出一个消息的过程。

S-answer(a，i): begin whensqido把a插入SQi中od

Ｖ（answeri）

end115(4)CCP的动作作为实现用户进程与控制台通信的方法之一，利用上面所述的各种接口，可以描述实现严格的顺序会话CCP进程。会话控制进程CCP：

local k，m，x repeat U-receive(m)

将消息m的进程标号置入k中 将消息m解码变换到x Write(x) Read(x)

将x编码到m S-answer(m，k) untilCCP结束1163.7.5进程通信的实例——管道1.管道pipe1）含义：管道（pipe）通讯由UNIX首创的一种借助文件和文件系统形成的一种通信方式。指用于连接一个读进程和一个写进程，以实现它们之间通信的共享方式，又称pipe文件。

2）管道通信：

向管道（共享文件）提供输入的发送进程（即写进程），以字符流形式将大量的数据送入管道；而接收管道输出的接收进程（即读进程），可从管道接收数据，由于发送和接收都是利用管道进行通信的，故称为管道通信。1173）

Pipe的建立和使用方式A、pipe文件在使用之前，必须先由使用者建立并打开；B、建立pipe的主要工作是在系统打开文件表中建立该pipe的两个表目；C、表目作用：分别用于控制该pipe的写操作（写入端）和读操作（读出端）。此时，pipe本身还是个空白文件。

系统文件write(Fd[1],buf,size)

功能：把buf中的长度为size字符的消息送入管道入口fd[1]fd[1]—pipe入口

buf:存放消息的空间

size:要写入的字符长度系统文件read(fd[0],buf,size)fd[0]――Pipe的出口功能：从pipe出口fd[0]读出size字符的消息置入buf中。注：pipe只允许建立者及其子进程使用。一进程及其所有‘子孙’构成一个进程族，同族中的多个进程可共享一个pipe，为了避免混乱，通常一个pipe为两个进程专用，且一个进程只用其写入端，另一进程只用其读出端。118

图3.20管道通信示意图4）Pipe文件的读写操作的同步与互斥

如同消息缓冲一样，在对pipe文件进行读写操作过程中要对发送进程和接送进程实施正确的同步与互斥以确保通信的正确性.接收进程：当接收进程读pipe时，若发现pipe为空，则进入等待状态。一旦有发送进程对该pipe执行写操作是唤醒等待进程.发送进程：当发送进程在写pipe时，总是先按pipe文件的当前长度设置，如果pipe文件长度已经到4096字节，但仍有一部分信息没有写入，则系统使要求写pipe的进程进入睡眠状态，当读pipe进程收走了全部信息时，此时，系统再唤醒待写的进程。它将余下部分信息继续送入pipe中。注：管道按先进现出方式FIFO传送消息，

且只能单向传送消息1192.示例例1：用C语言编写一个程序，建立一个pipe，同时父进程生成一个子进程，子进程向pipe中写入一字符串，父进程从pipe中读出该字符串。解：程序如下：

#include〈stdio.h〉 main() { intx，fd［2］；

charbuf［30］，s［30］；

pipe(fd)；/*创建管道*/ while((x=fork())==-1)；/*创建子进程失败时，循环*/ if(x==0)120 { sprintf(buf，″Thisisanexample＼n″)；

write(fd［1］，buf，30)；/*把buf中字符写入管道*/ exit(0)；

} else/*父进程返回*/ { wait(0)；

read(fd［0］，s，30)；/*父进程读管道中字符*/ printf(″%s″，s)；

} }121例2：编写一程序，建立一个管道。同时，父进程生成子进程P1，P2，这两个子进程分别向管道中写入各自的字符串，父进程读出它们（如图3.21）。图3.21父进程和子进程P1，P2通信例子解：程序框图如图3.22所示，源程序如下：122图3.22例2程序流图123#include〈stdio.h〉main(){inti，r，p1，p2，fd［2］；charbuf［50］，s［50］；pipe(fd)；/*父进程建立管道*/while((p1=fork())==-1)；/*创建子进程P1，失败时循环*/if(p1==0)

/*由子进程P1返回，执行子进程P1*/{lockf(fd［1］，1，0)；/*加锁锁定写入端*/sprintf(buf，″childprocessP1issendingmessages!＼n″)；

printf(″childprocessP1!＼n″)；write(fd［1］，buf，50)；/*把buf中的50个字符写入管道*/sleep(5)；/*睡眠5秒，让父进程读*/lockf(fd［1］，0，0)；/*释放管道写入端*/exit(0)；/*关闭P1*/}else/*从父进程返回，执行父进程*/{while((p2=fork())==-1)；/*创建子进程P2，失败时循环*/if(p2==0)/*从子进程P2返回，执行P2*/{124lockf(fd［1］，1，0)；/*锁定写入端*/sprintf(buf，″childprocessP2issendingmessages＼n″)；

printf(″childprocessP2!＼n″)；

write(fd［1］，buf，50)；/*把buf中字符写入管道*/sleep(5)；/*睡眠等待*/lockf(fd［1］，0，0)；/*释放管道写入端*/exit(0)；/*关闭P2*/}wait(0)；if(r=read(fd［0］，s，50)==-1)printf(″can′treadpipe＼n″)；elseprintf(″%s＼n″,s)；wait(0)；if(r=read(fd［0］，s，50)==-1)printf(″can′treadpipe＼n″)；elseprintf(″%s＼n″,s)；exit(0)；

}}lockf为保证进程互斥使用管道的系统调用，sleep为保证当前进程睡眠，转让处理机的系统调用。125§3.8死锁问题3.8.1死锁的概念死锁的定义死锁——各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。 图3.22死锁的概念126举例：生产