操作系统-课件xuos

第二章进程管理为什么要引入进程的概念程序顺序执行程序一般可分成三个部分：输入部分:以I表示;计算部分:以C表示;输出部分:以P表示。程序顺序执行的示意图为：I1C1P1I2C2P2InCnPn对于一个程序段中的多条语句来说，也有一个执行顺序问题。例：三条语句的程序段：S1：a:=x+yS2：b:=a-5S3：c:=b+1S2必须在a被赋值后才能执行;同样S3也只有在b程序被赋值后才能执行。程序顺序执行的特点：顺序性、封闭性、可再现性。封闭性指程序一旦开始执行其结果只取决于程序本身。2.1.2

程序并发执行程序的I、C、P三者之间存在Ii→Ci→Pi这样的前趋关系，对一个作业

的输入、计算、打印三个操作，必须顺序执行，但并不存在Pi→Ii+1关系，因而在对一批程序处理时，可使它们并发执行。程序并发执行的前趋图：I1

I2

I3

I4C1C2C3C4P4P1

P2

P3并发执行是指两个程序的执行在时间上是(输入设备)(CPU)(输出设备)的。例1：有两个循环程序A和B，共

个变量N。程序A每执行一次做：N:=N+1程序B每执行一次做：print(N)，然后置N:=0程序A和B独立地并行工作,可能出现三种情况(假定某时刻N的值为n)：N:=N+1在print(N)和N:=0之前,得到N的值分别为:n+1,n+1,0。N:=N+1在print(N)和N:=0之后,得到N的值分别为:n,0,1。N:=N+1在print(N)和N:=0之间,得到N的值分别为:n,n+1,0。并发程序已与程序的执行顺序有关，失去了封闭性和可再现性。程序是指令的有序集合,是静态的概念。机器执行程序的活动称为”计算”,”计算”是动态的概念。当一个并发程序可为多个用户作业调用,而使该程序处于多个“执行”中,从而形成多个“计算”。所以程序与“计算”不再一一对应。例2：有下述四条语句的程序段：S1：a:=x+2S2：b:=y+4S3：c:=a+bS4：d:=c+6可见，S3必须在a和b被赋值后才能执行；S4必须在S3之后执行，但S1和S2可以并发执行，因为它们彼此互不依赖。(相互制约性)S1S2S3S4并发执行的特点：相互制约性、失去封闭性、不可再现性。直接制约关系通常是在彼此之间有逻辑关系的两个并发执行的程序之间发生。间接方式发生制约关系是由竞争使用同一资源引起的,得到资源的程序可继续执行,得不到资源的程序只好暂停等待。程序或程序段并发执行的条件：若两个程序段p1、p2能满足下述条件，它们便能并发执行，具有可再现性。该条件称为Bernstein(伯恩斯坦)条件。R(p1)∩W(p2)∪R(p2)∩W(p1)∪W(p1)∩W(p2)={

}R(p1)——p1的读集、W(p2)——p2的写集、∩——“与”运算、∪——“和”运算

{

}——空集。例：S1：a:=x+yS2：b:=z+1S3：c:=a-bS4：w:=c+1R(S1)={x，y}，W(S1)={a}R(S2)={z}，W(S2)={b}R(S3)={a，b}，W(S3)={c}R(S4)={c}，W(S4)={w}S1和S2可以并发执行，S1和S3、S2和S3、S3和S4均不能并发执行。2.1.3

进程概念的引入一、引入进程的目的：在多道程序的环境下,程序的并发执行代替了程序的顺序执行,它破坏了程序的封闭性和再现性,使得程序和计算不再一一对应,而且由于资源共享和程序的并发执行导致在各个程序活动之间可能存在相互制约的关系。程序活动不再处于一个封闭系统中,出现了许多新的特征即独立性、并发性、动态性及相互制约性。在这种情况下，程序这个静态概念已经不能如实反映程序活动的这些特征，所以引入了进程这一概念。为了使程序在多道程序环境下能并发执行，并能对并发执行的程序进行控制和描述，而专门为之配置了一个称为“进程控制块”的数据结构。二、进程的定义：在操作系统中,进程有如下几种定义:进程是程序的一次执行过程。进程是可以和别的计算并行执行的计算。进程可定义为一个数据结构及能在其上进行操作的一个程序。进程是程序在一个数据集合上运行的过程，是系统进行资源分配和调度的一个独立单位。进程是一个具有独立功能的程序关于某个数据集合的一次运行活动。三、进程的特征：动态性：进程从产生到执行,再到消亡,是有生命的、动态的。并发性：程序没有并发特性。独立性：进程实体是一个能独立运行的单位,同时也是系统中能独立获得资源和独立调度的基本单位。异步性：进程按各自独立的不可预知的速度向前推进。四、进程和程序的区别进程是一个动态概念,程序是静态概念,程序是指令的有序集合,无执行含义,进程则强调执行的过程。进程具有并行特征(独立性、异步性:在不考虑资源共享的情况下，各进程的热执行是独立的，执行速度是异步的),程序则没有。不同的进程可以包含同一个程序，同一程序在执行中也可以产生多个进程。并发性独立性2.2

进程的表示和调度状态2.2.1

进程的表示1.进程的组成进程通常由程序、数据集和进程控制块(Process

Control

Black,记为PCB)组成。进程的程序部分描述了进程所要完成的功能。数据集部分包括程序在执行时所需的数据和工作区。程序和数据集是进程存在的物质基础,即进程的实体。进程控制块包含进程的描述信息和控制信息，是进程的动态特性的集中反映。PCB程序数据（a)PCB程序共享程序段数据（b)2.进程控制块为描述进程的动态变化，便于系统对进程进行有效的控制和管理，系统中为每一进程设置一个进程控制块。进程控制块是进程存在的惟一标志。当系统创建一个进程时，系统为其创建一个PCB，当进程被撤消时，系统收回它的PCB，该进程就消亡了。不同的操作系统其PCB的格式和所含的信息不同。一般PCB含如下的信息：进程标识名或标识号:系统中每个进程有唯一的表示符,以便系统识别。位置信息:进程的程序和数据部分在内存或外存中的物理位置。状态信息:进程当前所处的状态(执行、就绪、阻塞等)。进程的优先级:相对于其他进程的优先级。进程现场保护区:当进程暂时不在CPU上运行时各状态保护起来，以便再次进入CPU时恢复现场。资源

:队列指针或资源需求、分配和控制信息。字:

用于将处于同一状态的进程 成一个队列,在该单元中存放下一进程的PCB首址。其它信息：视系统而定。2.2.2

进程的调度状态在多处理系统中,用进程调度来确定哪个进程将得到CPU的控制。调度分为3个阶段：长期、中期和短期(高级、中级和低级)。长期调度也叫做作业调度，确定哪些作业或进程可以竞争系统资源。通常一旦作业调度程序使某作业成为活动的，那么这个作业会一直保持活动状态直到作业完成为止。作业调度程序的主要目标是给中期调度程序提供适当数量的作业。如果作业数量太少，当所有作业都被阻塞时CPU会闲置。如果作业过多，管理系统可能过载从而降低系统效率。中期调度与交换有关，交换是进程在内存与外存之间的调度。支持多处理的

管理系统都可以使用交换机制，这样在内存中可以有超出物理容量的进程数以共享系统。页面调度这样的

管理系统甚至通过将整个进程换出内存限制竞争内存的进程数。短期调度也就是处理机调度，把CPU分配给已装入主存准备运行的进程。通常调度程序按固定的最大时间片分配CPU。进程用完分配给它的时间片后必须

CPU，回到进程池，调度程序从进程池中挑选执行的进程。在多线程系统中，短期调度有多种调度方式。短期调度程序用线程调度而不是进程

调度。然而短期调度也可以是两级调度，就是进程调度中还有线程调度。由

于一个进程中的线程共享内存和其他资源，所以进程中的线程切换

进

程”(或不同进程的线程)之间切换的开销要小得多。1.进程的基本调度状态⑴运行状态(running)。进程在CPU中运行时的状态。⑵就绪状态(ready)。进程在等待CPU的状态。⑶

阻塞状态(blocked)。正在CPU上运行的进程因某种原因而暂停运行并等待其他的资源被

时的状态。运行就绪阻塞I/O完成进程的基本调度状态及其转换就绪→执行:由进程调度程序调度。运行→阻塞:在CPU中的进程请求其他服务。一般由运行进程自己主动提出。例如:进程在运行过程中需要某一条件而不能满足时，就自己主动放弃CPU进入阻塞。运行→就绪:时间片到或另一个优先权高的进程来抢占。阻塞→就绪:I/O服务完成。总是由外界事件引起的,而不是由该事件自己引起的。阻塞→运行:必须经过“就绪”。因为该进程阻塞解除时,系统中可能有多个进程都处于逻辑上可执行状态。系统必须根据一定的算法选择一个就绪进程占用CPU。这种选择过程称为进程调度。2.细分进程的调度状态细分方法A就绪状态可细分为低优先级就绪、中优先级就绪和高优先级就绪。阻塞状态细分为因等待盘、带的I/O而阻塞，因等待终端的I/O而阻塞和因等待页面的I/O而阻塞。超过时限细分的进程状态转换图运行I/O完成因页面阻塞低优先级就绪中优先级就绪高优先级就绪因盘、带阻塞因I/O阻塞I/O完成I/O完成缺页运行500ms细分方法B将基本调度状态的就绪和阻塞细分为活跃的和的两部分。这是因为有时需要人为的把正在运行或没有运行的进程挂起(suspend),使其处于状态(正在运行的进程停止运行,没有运行的进程不再运行)。系统的三种基本调度状态演变为五种调度状态:运行、活跃就绪、活跃阻塞、

就绪和

阻塞。运行活跃就绪就绪活跃阻塞阻塞事件到达具有挂起操作的进程状态转换图事件到达创建激活激活挂起挂起活跃静止2.3

进程的控制2.3.1

进程的控制结构OS采用层次化的模块结构，一般将与硬件紧密相关的模块安排在同一个层次中，并使它们常驻内存(以便提高OS的运行效率，并对它们加以特殊的保护),通常把这一部分称为OS的内核。内核不是进程。中断处理支撑部分时钟管理原语操作OS内核进程管理管理设备管理资源管理部分原语：一段紧凑不可分割(不可被中断)的指令组。内核中包含的原语主要有进程控制原语、进程通信原语、资源管理原语和其它方面的原语。属于进程控制方面的原语有进程创建原语、进程撤消原语、进程挂起原语、进程激活原语、进程阻塞原语和进程唤醒原语。2.3.2

进程控制原语1.

进程的建立建立进程的两种方法：⑴在系统生成时建立起一些系统进程。⑵利用创建原语来创建一个新进程。一个进程必须由其父进程来创建，而父进祖先进程创建。即父进程创建子进程，子进程创建孙进程。形成进程树。树型结构系统的主要优点是:⑴资源分配严格。子进程仅能分配到父进程所拥有的资源,用完立即归还。⑵进程控制灵活。给进程不同的控制权。进程可建立子进程分担子任务，且可并发地执行。⑶进程层次清晰，关系明确。进程创建原语(CREAT())步骤：A0B1B2C1

C2

C3进程的树型结构申请一张空白PCB，并获得 标识号为新进程分配资源初始化进程控制块(初始化标识符信息、初始化处理机状态信息、初始化处理机控制信息

）将新进程 就绪队

列2.状态转换原语⑴挂起原语。当需要把某个进程挂起时调用此原语。对于树型结构系统，被挂起的进程只能是它的子孙或其自身。若进程状态为：“运行”：把CPU状态保存在PCB中，停止运行该进程,并把其状态改为

就绪。并从活跃就绪进程队列中选一进程投入运行。“活跃阻塞”：改为“活跃就绪”：改为阻塞。就绪。阻塞改为活跃阻塞。激⑵激活原语。把 就绪改为活跃就绪或活原语只能激活某进程自己的子孙。⑶阻塞原语和唤醒原语。由“运行”→“活跃阻塞”→“活跃就绪”通常是在资源管理原语“请求”和“

”的作用下完成。但有的系统使用阻塞原语和唤醒原语完成上述转换。当一进程所期待的某一事件尚未出现时，该进程调用阻塞原语把自己阻塞起来。当某进程所期待的事件出现时，由“发现者”进程调用唤醒原语。发现者进程可能与被唤醒进程不直接相干，但通常与唤醒进程是合作的并发进程。阻塞原语(BLACK())步骤：提出者：进程自己唤醒原语(WAKEUP())步骤：执行者：其它进程(“发现者”进程)一个在阻塞队列中的进程在所等待的事件发生后，由另外一个相关进程通过调用唤醒原语将其唤醒。(发现者和被唤醒者是合作的并发进程)停止运行将PCB

的“运行态”改为“阻塞态”阻塞队列转调度程序进行重新调度移出阻塞队列将PCB

的“阻塞态”改为“就绪态”就绪队列3.进程的撤消当一个进程完成其任务后，应予以撤消，以便及时它所占用的资源。撤消原语(KILL())步骤：按调用者提供的进程名检索出该进程的PCB若该进程还有子进程，将其所有子孙进程予以撤消，以防它们成为不可控的将该进程所拥有的全部资源，或者归还给其父进程，或者归还给系统将被撤消的进程的PCB从所在队列中移出PCB结构2.4

进程调度2.4.1

交通控制程序和进程调度程序交通控制程序在操作系统

通控制程序的主要职能是管理进程状态之间的转变和协调进程间的通讯。进程调度程序该程序实现进程从就绪→运行状态的转变。进程调度程序所要完成的是把一台物理的CPU转变为多台虚拟的CPU或多台逻辑的CPU。进程调度程序的功能⑴记住系统中所有进程的状态、优先数和资源需求情况。⑵确定调度算法，决定把处理机分配给哪个进程和分配多长时间。⑶分配处理机给进程。进程调度程序是操作系统的真正

。2.4.2

进程调度算法的设计引起进程调度的时机⑴现运行进程运行结束或因任务完成而正常结束,或因出错而异常结束。⑵现运行进程因某种原因从运行进入阻塞状态。⑶当进程从阻塞状态转换到就绪状态时。(例：I/O完成时)⑷一个具有更高优先级的进程要求使用处理机。⑸分配给该进程运行的时间片已用完。进程调度方式⑴非 方式(非抢占式)。原来运行的进程继续运行直至该进程完成或发出某事件而进入完成或阻塞状态时才主动放弃自己的处理机。⑵

方式(抢占式)。现运行进程在运行过程中，

更高优先级的进程到达，则现运行进程被迫放弃处理机，处理机立即分配给新进程。进程调度算法的选择进程调度算法基本分为两大类：优先级法和时间片轮转法。4.进程队列的组织表或进程队列方式可使PCB的数目不受限制，可动态申请或

。由于各队列分开，因此管理方便。缺点是动态分配PCB所占内存的算法比较复杂，指针占用额外 空间，费时。运行队列PCB0就绪队列PCBPCBPCB0阻塞队列PCBPCBPCB02.4.3

常用的进程调度算法1.静态优先级法如果在进程创建时就确定了优先级，且在运行过程中不再动态改变，这种优先级法称为静态优先级法。优先级的确定方法:⑴按进程类型确定。系统类型(优先级高)、用户类型。⑵按作业的资源要求确定。如要求CPU时间和内存空间少的进程优先(短进程优先算法SPF–Shortest

Process

)。⑶按作业到达的时间确定。先来先服务算法(FCFS–e-Served

)⑷按用户类型和要求确定。用户可

作业优先权数，以高代价取得系统照顾。作业情况调度算法进程名ABCDE平均到达时间01234服务(执行)时间43524FCFS完成时间471214周转时间带权周转时间1225.53.52.8SPF完成时间4①9③⑤②④周转时间8带权周转时间12.673.21.52.252.1周转时间T:指进程提交给系统开始,到进程完成为止的时间间隔。T＝进程等待时间+进程执行时间＝完成时间－提交(到达)时间。带权周转时间W:W=进程周转时间/进程执行时间。W越小越好进程等待时间P:P=进程周转时间-进程执行时间。SPF平均周转时间<FCFS平均周转时间平均带权周转时间平均带权周转时间SPF优点：有效地降低作业平均等待时间，提高系统的吞吐量。SPF缺点：对长作业不利，不考虑作业的紧迫程度。动态优先级法各进程使用CPU的程度是动态变化的。时间片轮转法在分时系统中常采用时间片轮转法。时间片轮转法将就绪进程按先来先服务原则排队，每个进程使用CPU的时间片q秒，若未完成，必须

CPU，并排到最后，等下一次。系统的响应时间T=N*q。N为就绪队列中的进程数。q的大小对进程调度有很大影响。时间片的长短由以下因素确定：⑴系统的响应时间;⑵就绪队列中的进程数;⑶进程的轮转时间;⑷计算机的处理能力，计算机的速度越高，时间片就可越短。优点：简单，易实现。缺点：采用固定时间片和一个就绪队列，服务质量不够理想。改进：固定时间片改为可变时间片;单就绪队列改为多就绪队列。4.

多队列轮转法采用多个时间片不等的队列，一队列时间片内末完成的进程放入下一队列，直至放入最后一个队列。在此法中只有前一队列没有进程可调度时才选择下一队列中的进程占用处理机。这样短作业能较快地占用处理机，而长作业一旦占用处理机可使用较长时间，避免因频繁调度增加系统开销。就绪队列1(8ms)就绪队列2(16ms)就绪队列3(32ms)就绪队列m(FCFS)CPU完成……2.5

进程通讯进程制约关系的基本形式:进程—进程，称为直接制约关系。进程—资源—进程，称为间接制约关系。进程之间相互依赖又相互制约、相互合作又相互竞争的关系意味着进程之间需要某种形式的通讯，这主要表现为同步和互斥两个方面。2.5.1

进程间的同步和互斥1.

进程间的同步某种进程未获得合作进程发来消息之前，该进程等待，消息到来之后方可继续执行的进程合作关系，称为进程的同步。例：计算Z=func1(x)*

func2(y),P1进程计算func1()和Z的结果,P2进程计算func2()。计算func1(x)进程P2计算完func2(y)?取用P2计算结果P1进程YNP2进程计算func2(x)置计算完标志终止进程P1和进程P2的同步例：P1:R1:=count;

R1:=R1+1;

count:=R1;//

count++;P2:R2:=count;

R2:=R2+1;

count:=R2;//

count++;2.

进程间的互斥一个进程的执行引起另一个或另一批进程不能执行的现象称为互斥。这是由于进程在运行过程中争夺资源引起的。一次仅允许一个进程使用的资源称为临界资源(Critical

Resource)。临界资源既可能是外设，也可能是内存变量。R1,R2为通用寄存器并发运行可能会出现的运行顺序：P1:

R1:=count;P2:

R2:=count;P1: R1:=R1+1;

count:=R1;P2:

R2:=R2+1;

count:=R2;程序的本意是两进程各自对count进行加1操作，可效果可能只增加了1。原因是两个进程使用了临界资源。因此各进程对临界资源操作的程序段的执行应该是互斥的。互斥执行的程序段称为临界区(Critical

Section)或互斥段。3.实现临界区互斥的锁操作法多个进程同时进入临界区的方法之一是可通过加锁和开锁实现。使用一个物理实体称为锁,用W表示,W=0表示锁已打开,W=1表示锁被关闭。加锁原语用LOCK(W)表示，其操作为：L: if

(

W=1

)

then

goto

L;else

W:=1;开锁原语用UNLOCK(W)表示，其操作为：W:=

0;实施进程互斥后的实例：P1:

LOCK(W);S1;P2:

LOCK(W);S2;//

S1,S2分别为P1和P2的临界区UNLOCK(W);

UNLOCK(W);用加锁和开锁的方法实现临界区互斥其效率很低。因为若一个进程在临界区,当其它进程欲进入临界区时,反复检测是否可以进入,即忙于等待临界区中的进程离开。E.W.Dijkstra

提出了用信号量(Semaphore)以及有关的P、V操作解决同步、互斥问题。Test

and

Set指令enter_region:mov

Rx,

1xchg

Rx,LOCKcmp Rx,

0jne

enter_regionretleave_region:mov

LOCK,

0ret2.5.2

信号量和P、V操作1.

信号量及P、V操作在操作系统中，信号量是表示资源的实体，是一个与队列有关的整型变量，其值仅能由P、V操作来改变。公用信号量：通常用于实现进程间互斥，初值为1。私有信号量：用于实现进间的同步,初值为0或正整数n。仅允许拥有它的进程实施P操作。信号量S大于等于零时表示可供并发进程使用的资源实体数，但S小于零时表示正在等待使用临界区的进程数。P原语的操作功能

V原语的操作功能S=S

-

1S

>=

0?返回调用进程入等待队列转进程调度YNS=S

+

1S

<=

0?返回唤醒等待队列中的一个进程返回或转进程调度NYDijkstra于1965年提出使用信号量抽象数据类型来控制同步。在操作系统中很临界区的通用解决方法。容易实现信号量，而且信号量提供了控制struct

semaphore{int

count;ProcessQueue

queue;};void

P(semaphore

s){if(

s.count

>

0)s.count=s.count-1;elses.queue.Insert(

);

//

Block

this

process}void V(semaphore

s

){if

(

s.queue.empty()

)s.count

=

s.count

+

1;elses.queue.Remove(

);//

Schedule

a

process,if

any,

blocked

on

‘s’}信号量是非负的整数变量。信号量操作有时也称为Down和Up,或Wait和Signal。2.

利用信号量实现进程的互斥设S为两进程互斥的公用信号量,初值为1,表明该临界资源末被占用。只需把临界区的程序段置于P(S)和V(S)之间,即可实现两进程互斥。进程P1P(S)S1

//(临界区)V(S)进程P2P(S)S2

//(临界区)V(S)例：有一单向行驶的公路桥,每次只允许一辆汽车通过。当汽车到达桥头时,若桥上无车便可上桥;否则,需等待,直到桥上的汽车下桥为止。若每一辆汽车为一个进程,请用P,V操作编程实现。解：公路桥是1个临界资源,由于它每次只允许一辆汽车通过,故可为它设置一个初值为1的临界资源mutex。汽车过公路桥的动作可描述为：Semaphore

mutex=1;CrossBridge()begin行驶到桥头;P(mutex);上桥行驶,从另一头下桥;V(mutex);end;例:

设一

航班售票系统有n个售票处,每个售票处通过终端系统的公共数据区,假定公共数据区中一些单元Xｊ(j＝1,2,3…)分别存放×月×日×次航班的现存票数。用P1,P2,…Pn表示各售票处为旅 务时的处理进程,R1,R2…Rn为各进程执行时所用到的工作单元(变量)。当售票处有旅客买票时，进程如下工作：beginS:semaphore；S:=1;cobeginPROCESS

Pi

//(i=1,2,…,n)begin{按旅客要求找到Xj};P(S);Ri

:=

Xj；If

Ri>=１

thenbeginRi

:=Ri

–

1;Xj

:=Ri；V(S);{输出一张票};endelsebeginV(S);{输出“票已售完”};end；end；coend；end

;3.利用信号量实现进程间的同步设S为两进程的信号量,初值为0。进程P1受进程P2制约。进程P1L1:

P(S)进程P2L2:

V(S)例:

用信号量实现

和售票员的同步。设S1和S2分别为 和售票员的私用信号量，初值均为0。进程售票员进程正常行车到站停车V(S2)P(S1)离站开车售票P(S2)开车门关车门V(S1)合作进程的执行次序：例：PA、PB、PC为一组合作进程，其前驱图如右：要求PA执行结束后，PB、PC才能执行。设两个信号量SB、SC分别表示进程PB、PC能否开始执行，初值为SB=0、SC=0。PA：PB：PC：……P（SB）P（SC）V（SB）V（SC）…………PaPbPc共享单缓冲区的两个进程的同步问题：例：设一计算进程IC和一打印进程OP共用一个单缓冲，

。IC进程负责不断地计算数据并输入缓冲区T中，OP进程负责从缓冲区T中取出数据去打印。ICOPBUF:

T同步约束：OP进程只有在IC进程将数据输入缓冲区后，才能取出打印。IC进程只有在OP进程将数据取出打印后，才能送入下一个计算数据。SA=0；//SA信号量表示缓冲区中有无信息（初始无数据）SB=1；//SB信号量表示缓冲区中有无空位（初始有空位）IC:

OP:生产一个数据P(SB)送入缓冲区中V(SA)P(SA)从缓冲区中取一数据V(SB)输出数据4.生产者—消费者问题生产者—消费者问题是很多并发进程间存在的内在关系的一种抽象。假定这些生产者和消费者是互相等效的,只要缓冲区未满,生产者就可把产品送入缓冲;类似地,只要缓冲区未空,消费者便可从缓冲区取走产品并消耗它。仅当缓冲区满时生产者被阻塞;类似地,缓冲区空时消费者被阻塞。问题：生产者、消费者—同步问题生产者之间(或消费者之间)都会选中同一共享资源:缓冲单元—互斥问题。设：公用信号量S初值为1,表示没有进程进入临界区,用于实现进程互斥。私有信号量S0,表示产品数量,初值为0。私有信号量Sn,表示可用缓冲区数,初值为n。beginB:array[0..n-1]

of

integer;//

int

B[n];p,r:integer;//存、取产品的位置

S,Sn,S0:semaphore;p:=r:=0;S:=1;

Sn:=n;

S0:=0;cobeginprocess

produceri(i=1,2,…,m)beginL1: produce

a

product;P(Sn);

P(S);B[p]

:=

product;p

:=

(p+1)

mod

n;V(S0);

V(S);gotoL1;endprocess

consumerj(j=1,2,…,k)beginL2: P(S0);

P(S);take

a

product

from

B[r];r:=

(

r+1

)

modn;V(Sn);

V(S);consume;gotoL2;endcoend;End;生产者进程生产一种产品P(Sn)//有空缓冲吗P(S)//临界区可用吗产品送入缓冲区V(S0)//产品数加1V(S)//临界区可用消费者进程P(S0)//有产品吗P(S)//临界区可用吗从缓冲区取一产品V(Sn)//缓冲区数加1V(S)//临界区可用消费该产品semaphore

S=1,Sn=n,S0=0;producer

(){ while

(

true

)

{生产一个产品;P(Sn);P(S);将一个产品送入缓冲区;V(S);V(S0);}}consumer(){ while

(

true

)

{P(S0);P(S);从缓冲区中取一个产品;V(S);V(Sn);消费一个产品;}}main(){

cobeginproducer();consumer();coend;}生产者进程生产一种产品P(Sn)//有空缓冲吗P(S)//临界区可用吗产品送入缓冲区V(S0)//产品数加1V(S)//临界区可用消费者进程P(S0)//有产品吗P(S)//临界区可用吗从缓冲区取一产品V(Sn)//缓冲区数加1V(S)//临界区可用消费该产品int

rc=0;

//在读文件的人数计数器,是共享变量void

Reader

(

){while(

true){P(Sr);rc

=

rc

+1;if (rc

==１)P(S);//第一个读者对写加锁V(Sr);read

file

F;P(Sr);rc

=

rc-

1;if

(rc==0)V(S);//最后一个读者对写V(Sr);}}5.

读者与写者问题一个文件F供多个进程读写,要求:写时需独占;读时可共享。semaphore

S=1;//对共享资源file信号量semaphore

Sr=1;//对共享资源rc的信号量void

Writer(){while

(

true

){

P(S);write

file

F；V(S);}；}说明:该程序的问题:当有进程在读而使一个写进程阻塞时,如果仍有进程不断地请求读,则写进程将被长期地推迟运行。而实际情况是希望写者优先。即有进程在读时，么新的读者被读写进程为进程请求写，那。(实际上是置地位。)semaphore S=1,Sr=1,Sw=1;//S控制对文件,Sr对rc的信号量,Sw提高写进程优先级int rc

=

0;void

Reader(

){ while

(

true

){

P(Sw);

//在无写进程请求时进入P(Sr);

//互斥对rc的rc=rc+1;//增加一个读进程数if(rc==1)

P(S);

//当第一个读进程读数据时写进程写V(Sr); //恢复对rc的V(Sw); //

恢复对数据read

file

F;P(Sr);rc=rc-1;if(rc==0) V(S);//当最后一个读进程完后,允许写进程写V(Sr);}}void

Writer(

)main(

){cobegin//两个进程并发执行{ while

(

true

){P(Sw);//在无写进程请求时进入P(S); //

排斥

数据write

file

F；Reader(

);Writer(

);coendV(S); //

恢复

数据}V(Sw);//恢复对数据}};写者优先，且对读者数

：semaphore

Sx=1,Sy=1;//Sx,Sy用于控制readcount和writecount

的更新semaphore

Sr=1,Sw=1;//Sr用于

所有读进程，Sw用于

所有写进程semaphore

Sz=1;int

readcount=0,writecount=0;void

Reader

(

){P(Sz);P(Sr);P(Sx);readcount=readcount+1;if

(

readcount

==

1)P(Sw);V(Sx);V(Sr);V(Sz)read

file

F;P(Sx);readcount:=readcount-1;if

(

readcount

==

0

)V(Sw);V(Sx);}void

Writer(

){P(Sy);writecount=writecount+1;if

(

writecount

==

1

)P(Sr);V(Sy);P(Sw);write

file

F；V(Sw);P(Sy);writecount=writecount-1;if

(

writecount

==

0

)V(Sr);V(Sy)}对于读进程,需要一个额外的信号量,防止在

Sr上建造长队列,否则写进程将不能跳过这个队列,因此只允许一个读进程在Sr上排队,而所有其他读进程在等待Sr之前在信号量Sz上排队。2.5.3

高级通讯原语低级通讯：交换的数据量少(P,V操作)。目的是控制进程执行速度。高级通讯：交换的数据量大。目的是交换信息。消息缓冲方式和信箱通讯方式。1.消息缓冲通讯发送进程直接将消息挂在接受进程的消息队列上。(1)message数据结构（缓冲区的几个域）：sender;size;text;next;发送消息的进程标识：消息的长度：消息正文：指向下一消息缓冲区的指针：(2)PCB中相应的数据项：消息队列队首指针：

消息队列互斥信号量：消息队列资源信号量：mq;mutex;//进入临界区时P(mutex)操作,离开时V(mutex)操作sm;//放消息时V(sm)操作，取消息时P(sm)操作发送原语send

(receiver,addr);receiver:

接收进程的标识符,addr:发送区始址。发送区包括:发送进程标识，消息长度和消息正文。接收原语receive(addr);addr:接收区始址。接收区包括:发送进程标识，消息长度和消息正文。Send(B,a)sender:

Asize:

5text:

oreceive(b)sender:

Asize:

5text:

o进程A进程B发送区接收区abmqmutexsmsender:Asize:5text:

onext:

0PCB(B)消息缓冲通讯若消息队列容量N，发送进程申请不到缓冲区，发送进程阻塞。若消息队列的消息为0，接收进程接收不到消息，接收进程阻塞。2.信箱通讯信箱用于存放信件，而信件是一进程发送给另一进程的消息。信箱通讯过程发送进程将消息发到一中间实体(称为信箱)，接收进程从中获取。发信的进程主要把预处理的信笺投入信箱，而不必过问是 接收及处理。同样，接收进程只关心取信笺处理，也不必知道是谁发来的。每个信箱有一个唯一的标识符。信箱的数据结构信箱由信箱头和信箱体组成。信箱的拥有者为接收进程，信箱名、信箱大小在创建信箱时确定。mesnum是接收进程的私有信号量，初值为0。fromnum是发送进程的私有信号量，初值为boxsize。mutex是该邮箱的互斥信号量,初值为1。发送原语和接收原语send(boxname,

msg);receive(boxname,

msg);原语的实现信箱名：boxname信箱大小：boxsize已存信件数：mesnum空格子数：fromnum满信件满信件满信件空格子……空格子send(

boxname,

msg)beginlocal

X;根据boxname找到信箱;P(fromnum);P(

mutex

);选择标志为空的格子;把消息msg放入空的格子X中;置格子X为满标志;V(

mutex

);V(

mesnum

);endreceive(

boxname,

msg

)beginlocal

X;根据boxname找到信箱;P(mesnum

);P(

mutex

);选择标志为满的格子X;将格子X中的信件取出放入msg中;置格子X的标志空;V(

mutex

);

V(

fromnum

);end2.6

死锁当某一进程提出资源的使用要求后,使得系统中一些进程处于无休止的阻塞也不能继续前进,这种现象称死锁。状态,在无外力的作用下,这些进程2.6.1

死锁的起因和产生死锁的必要条件1.死锁的起因临界资源：Y1,Y2进程Pa进程Pb进程Pa进程Pb…………P(SY1)占用Y1P(SY2)占用Y2P(SY1)占用Y1P(SY1)占用Y1…………P(SY2)要用Y2P(SY1)要用Y1P(SY2)要用Y2P(SY2)要用Y2…………V(SY2)V(SY1)V(SY2)V(SY2)V(SY1)V(SY2)V(SY1)V(SY1)…………进程Pa,Pb无法继续前进,出现死锁。当进程争夺资源时,有可能产生死锁,但不一定就会死锁,这取决于各进程推进的速度和对资源请求的顺序,因此,死锁是一种与时间有关的错误。2.产生死锁的必要条件1971年Coffman提出了可逐次再使用资源产生死锁的必要条件是：⑴互斥控制进程对其所要求的资源进行排它控制，一个资源仅能被一个进程独占。⑵非

控制进程所获得的资源在未

之前,不能被其它进程强行

,只能有该进程自己

。⑶逐次请求(占用和等待)进程以随意的零星方式逐次取得资源,而不是集中性的一次请求,这有利于提高资源的利用率。⑷环路条件(循环等待)在发生死锁时，其有向图必构成环路，即前一进程保持着后一进程所要求的资源。R1R2B进程进程A占用只要破坏上述四个条件之一，即可预防死锁的发生。R1资源A进程进程B占用R2资源进程A请求R2资源进程B请求R1资源2.6.2

死锁举例⑴P、V操作引起的死锁进程A进程B启动读卡机卡片送入缓冲区P(S2)V(S1)P(S1)从缓冲区取卡片信息V(S2)加工卡片信息初始时S1=0;S2=0;⑵ 器共享的死锁假定系统中有m个单位的

器，它为n个进程所共享。若每个进程都要求i个单位，当m<n*i

时就可能发生死锁。⑶加锁法引起的死锁进程P1进程P2LOCK(W)LOCK(W)若P1,P2优先级不同，S1S2也可能发生死锁。UNLOCK(W)UNLOCK(W)⑷哲学家吃通心面问题(Dining

Philosophers

Problem)有五个哲学家围坐在一圆桌旁,桌 有一盘通心面,每人面前有一只空盘子,每两人之间放一根筷子。每个哲学家思考、饥饿,然后吃通心面。但是每个哲学家必须获得两根筷子(只能从自己左边和右边取筷子)才能吃到通心面。P[0..4]对应五个哲学家，r0-r4对应五根筷子，S[0]–S[4]对应取五根筷子的互斥信号量，初值为1。对于第i个哲学家可取左边(i)和右边(i+1)的筷子。设i+1的操作为i=(i+1)mod

5;

semaphore

S[5];S[0]:=S[1]:=S[2]:=S[3]:=S[4]:=1;void Philosopher(int

i){ while(

true

)P2P3P4{

thinking;hungry;P(S[i]);pickup

riP(S[i+1]);pickup

ri+1eating;putdown

riputdown

ri+1;V(S[i]);V(S[i+1]);};}此算法采用先取左边的筷子,再取右边的筷子,可能会出现每人都取到左边的筷子而取不到右边的,从而形成死锁。2.6.3

死锁的预防只要打破互斥控制、非 控制、逐次请求和环路条件之一，即可预防死锁。对于后两种条件可采用如下两种方法解决：⑴资源静态分配法进程在运行之前一次申请它所需的全部资源。优点：简单、安全。 缺点：资源利用率低。⑵资源顺序分配法对系统的全部资源加以全局 。使用时，所有进程对资源的申请必须严格按资源的序号递增的次序提出。例如：在哲学家吃通心面问题中，五根筷子 为r0,r1,r2,r3,r4。对于P0-P3必须先申请ri,然后申请ri+1,对于P4必须先申请r0,然后申请r4,就可防止死锁。2.6.4

死锁的避免如果一个进程的请求会导致死锁,则不启动此进程。如果一个进程增加的资源请求会导致死锁,则不允许此分配。只要系统在分配资源时自始至终地作出正确的选择就能避免死锁。银行家算法(资源分配银行家占有有限策略)：，不可能满足所有借款人的最大需求量的总和，但可以满足一部分借款人的借款要求。待这些人的借款归还后又可把这笔借给他人。当有人提出借款要求时，银行家就要计算，以决定是否借给他，看是否会造成银行家的被借光而使无法周转。例程客户已贷款额最大贷款额A06B05C04D07客户已贷款额最大贷款额A16B25C24D47客户已贷款额最大贷款额A16B15C24D47设银行家有金额为10。 余额为2,

安全 余额为1,

不安全n检查状态是否安全:看是否有足够的资源满足一个距最大需求最近的客户。考虑一个有n个进程和m种不同类型的资源的系统分配问题。银行家算法中的数据结构:各资源总数W[1..m]:每一个元素表示一类可分配资源总数。最大需求数Max[1..n][1..m]:n个进程中的每一个进程对m类资源的最大需求。已分配资源R[1..n][1..m]:每一类资源当前已分配给每一进程的资源数。可用资源S[1..m]:表示系统可供进程继续分配的各类资源数目。尚需资源Q[1..n][1..m]:每一个进程尚需的各类资源数。(Q[][]=Max[][]-R[][])进程运行标志Finish[1..n]:表示系统是否有足够的资源分配给进程。有足够的资源时:Finish[i]=1。算法开始时：Finish[i]=0S[

j]

W[

j]

R[i][

j]i1:Req[]进程i的资源请求Finish[1..n]

:=

0计算可用资源:for

j:=1

to

mS[j]:=W[j]-sum(R[j])试探性分配修改：For

j:=

1

to

mR[i][j]:=R[i][j]+Req[j];S[j]:=S[j]-Req[j];Q[i][j]:=Q[i][j]-Req[j];安全性检查：(在K=1..n时有满足下面条件的情况吗)Finish[k]=0

ANDQ[k][1..m]

<=

S[1..m]Finish[k]:=1;For

j:=

1

to

mS[j]:=S[j]+R[k][j];是所有的Finisk[]=1系统安全，可实际分配资源系统不安全，不可分配资源,撤销分配。否是结束注：sum(R[j])根据资源类型汇总，fork:=1

to

na

:=

a

+

R[k][j]return

a;假设可给第i进程分配所需资源判剩余资源能否满足一个距最大需求的进程需要。例：假设系统中有五个进程{P0，P1，P2，P3，P4}和三种资源{A，B，C}，每一种资源的数量分别为W(10，5，7)。在T0时刻的资源分配情况如下：MaxA,

B,

CA,RB,CQA,

B,CS(

3,

3,

2

)Finish(

)P0753010743P1322200122P2902302600P3222211011P4433002431①判断T0时刻是否安全？SA,

B,

CA,RB,CQA,

B,CS+RA,

B,CFinish()P321P35322110117431P07430107437531P275330260010551P4105500243110571系统在T0时刻安全，有一个可能的安全序列{P1，P3，P0，P2，P4}②此时假如P1提出请求向量Req[]=(1,0,2),系统能分配给它吗？MaxA,

B,

CA,RB,CQA,

B,CS(

2,

3,

0)Finish(

)P0753010743P1322302020P2902302600P3222211011P4433002431判断此时刻是否安全？A,SB,CRA,

B,CA,QB,CS+RA,

B,

CFinish(

)P12303020205321P35322110117431P07430107437531P275330260010551P4105500243110571系统在此时刻安全，有一个可能的安全序列{P1，P3，P0，P2，P4}③此时假如P0提出请求向量Req[]=(0,2,0),系统能分配给它吗?MaxA,

B,

CA,RB,CQA,

B,CS(

2,

1,

0)Finish()P0753030723P1322302020P2902302600P3222211011P4433002431判断此时刻是否安全?因为此时系统可用资源数S(2,1,0)已不能满足任何进程的需求,故可得知系统