第三章进程管理-.ppt

《第三章进程管理-.ppt》由会员分享，可在线阅读，更多相关《第三章进程管理-.ppt（98页珍藏版）》请在三一文库上搜索。

1、2019/7/13,1,第三章 进程管理-1,3.1 进程的基本概念 3.2 进程的基本状态 3.3 进程的描述与管理 3.4 进程控制,重点:本章为本书的重点,难点,2019/7/13,2,3.1 进程的基本概念,3.1.1 进程概念的引入,C编译程序,C,C,程序A,程序B,时间片用完,中断,可再入程序,2019/7/13,3,进程：一段功能完整的程序在处理机上的执行过程。,3.1.2 进程与程序的区别,进程是动态的，程序是静态的 进程是暂时的概念，程序是永久的概念 进程有自己的数据结构PCB 进程和程序不是一一对应的。,2019/7/13,4,3.1.3 进程的定义,进程:是一个具有独立

2、功能的程序对某个数据集在处理 机上的执行过程和分配资源的基本单位.,程序:指一组操作序列.,数据集:接受程序规定操作的一组存储单元的内容.,进程的特征,动态性,并行性,独立性,异步性,2019/7/13,5,进程的结构特征:PCB,程序代码段,数据段,程序,数据,PCB,进程的结构特征,2019/7/13,6,进程与程序的区别与联系,2019/7/13,7,3.2 进程的基本状态,为了描述和控制进程的运行,系统为每个进程定义了一个数据 结构,即进程控制块PCB (Process Control Block),系统根据 PCB,感知该进程的存在,故亦称PCB是进程存在的标志.,PCB的作用:,感

3、知进程的存在 记录进程的状态或有关信息,通常在一个实际系统中,PCB的总数是固定的,该数目规定了系统所允许拥有的进程数目,同时将所有的PCB形成一个结构数组(或称PCB表),存放在系统的数据区中.,一个进程的PCB机构全部或部分常驻内存.,2019/7/13,8,3.2.1 进程的基本状态,1. 进程状态,就绪态:等待系统分配处理机以便执行时 所处的状态. 即获得了除处理机之外的所以资源,一旦由调度 程序选中得到处理机就可以立即执行的状态. 运行态:正在处理机上执行时所处的状态. 在单CPU情况下,处于该状态的进程数只有一个. 等待态:等待某个事件的完成时进程所处的状态.除了 CPU之外其他的

4、资源也没有得到满足,2019/7/13,9,运行,就绪,等待,进程调度策略,时间片用完,等待某一事件发生,等待事件结束,剥夺处理机,创建,撤销,进程的三种基本状态及其转换,2019/7/13,10,进程控制块,3.3 进程的描述与管理,1.OS感知进程存在的唯一标识-PCB,2.记录了OS所需的用于描述进程及控制进程全部信息. 在PCB中主要包括下面信息: 1) 进程描述信息 2) 进程控制信息 3) 资源信息 4) 现场保护信息,1) 进程描述信息:进程名或进程标识符. 家族关系.,2019/7/13,11,2) 进程控制信息,进程的当前信息:指明进程的当前状态,作为进程调度和对换的依据.

5、进程优先级:调度依据,是进程占有处理机的重要依据. 程序开始地址:便于执行这段程序. 各种计时信息:记录资源占用的信息. 通信信息:保证进程之间相应的联系.,3) 资源管理信息,占用内存大小及其管理用数据结构指针. 对换或覆盖用的有关信息. 共享程序的大小及起始地址. I/O设备号,传送的数据长度,缓冲区地址,缓冲区长度及所有设备的有关数据结构指针. 指向文件系统的指针及有关标识符.,2019/7/13,12,4) CPU现场保护信息(进程上下文),通用寄存器的用户 PC PSW :含状态信息（条件码的执行方式,中断屏蔽标识)。 用户栈指针：为每个用户进程有一个或若干隔与之相关的系统栈，用于存

6、放过程和系统调用参数和调用地址。,当处理机被中断时,各种寄存器的内容都必须保存在被中断进程的PCB中,以便在该进程重新执行时,能从断点继续执行.,由于PCB中包含较多的信息（占几百几千BYTE),在有的系统中只含PCB中最常用部分（CPU现场保护部分，进程描述信息，控制信息）常驻内存，其他部分则放在外存中，待该进程将要执行时与其他数据一起装入内存。,2019/7/13,13,*进程上下文,是对进程动态活动的静态描述,进程的上下文是其相应的程序地址空间的内容，硬件寄存器的内容以及与该进程有关的核心数据结构（系统堆栈，用户堆栈）构成的。,包括：计算机系统中与执行该进程有关的各种寄存器值；程序段经过

7、编译连接后形成的机器指令代码段（text);数据段以及各种堆栈的值和PCB块）。,例：UNIX进程上下文,用户级上下文,系统级上下文,寄存器上下文,*进程上下文,2019/7/13,14,*进程的组成,进程PCB程序（代码和数据）,进程的表记,PCB,程序,PCB,程序,代码,2019/7/13,15,*PCB的组成方式,在一个系统中，通常可以拥有数十个以及若干个PCB,为了能对他们进行有效的管理，应当用适当的方式将他们组织起来。,PCB目前常用的组织方式：链接方式；索引方式,系统中进程队列分类：就绪队列，等待队列，运行队列。 就绪队列：整个系统一个 等待队列：每一个等待事件一个。 运行队列：

8、单机系统中整个系统一个。,2019/7/13,16,链接方式,PCB链接队列示意图,把具有相同状态的PCB,用其中的链接字链接成一个队列.,线性表,2019/7/13,17,按索引方式组织PCB,2. 索引方式,系统根据所有进程的状态,建立几张索引表,如就绪索引表,阻塞索引 表,并把各索引表在内存的首地址记录于内存中的一些专用库文件中.,2019/7/13,18,3.4 进程控制,为了防止OS及关键数据如PCB等,受到用户程序有意或无意的破坏,通 常将处理机的执行状态分为:系统态和用户态.,系统态(核心态):具有较高的特权,能执行一切指令,访问所有的寄存器和存储区. 用户态:具有较低特权的执行

9、状态,只能执行规定的指令,访问指定的寄存器和存储区.,进程控制: 就是系统使用一些具有特定功能的程序段来创建、撤销进程以及完成进程状态间的转换，从而达到多进程高效率并发执行和协调实现资源共享的目的。,原语（Atomic Operation): 系统态下执行的某些具有特定功能的程序段。,2019/7/13,19,. 创建原语,为此进程分配进程控制块,为此进程分配资源,把此进程插入到就绪队列中,等待CPU的调度,. 引起创建进程的事件,用户登陆 作业调度 提供服务 应用请求,3.4.1. 进程的创建,2019/7/13,20,1. 引起进程终止的事件,正常结束 异常结束 外界干预,3.4.2 .

10、进程的终止,Procedure Destroy(n) begin sched=false; i=获取n进程内部名 kill(i); if (sched) schedure else continue(当前正在执行的进程); end,2019/7/13,21,.进程创建原语的描述形式,create(n,So,Po,Mo,Ro,acc) Begin i=get internal name(n);/* 获得内部名*/ i.id=n; /* 填外部名 */ i.priority=Po; /* 设优先级 */ i.Cpustate=So; /* 填CPU初始状态 */ i.mainstore=Mo; /

11、* 填写主存区域 */ i.resource=Ro; /* 填写资源清单 */ i.status=readys; /* 填写进程状态 */ j=EP; /* 获取调用者内部标识 */ i.parent=j; /* 填写i进程的父进程j */ j.progency=; /* 置i的家族指针为空 */ i.progency=i; /* 把i填入其父进程PCB的家族指针处 */ i.state=RQ; /* 置i所在状态队列首指针 */ insert(RQ,i); /* 把i进程插入到RQ对尾 */ End,i,2019/7/13,22,Procedure kill(i) begin if i-st

12、atus=“running” begin stop(i); sched=true; end remove(i-state,i);将被撤销进程i从i.state所指示的队列中去掉. for all s(i.progency) do kill(s); for all r(i.mainstoreUi.resoure) do if owner (r) insert(r.semaphore,r.data); 归还属于父进程资源且插入父资源清单. for all Rcreated resoure(i) do remove descriptor(R) ; 撤销自己的资源清单并归还系统 remove proc

13、ess control block(i); END,2019/7/13,23,根据被终止进程的标识符，从PCB链表中检索出该进程的PCB，从中读出该进程的状态。 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真，用于指示该进程被终止后应重新进行调度。 若该进程还有子孙进程，还应将其所有子孙进程予以终止，以防他们成为不可控的进程。 将被终止进程所拥有的全部资源，或者归还给其父进程， 或者归还给系统。 将被终止进程(它的PCB)从所在队列(或链表)中移出， 等待其他程序来搜集信息。,2.进程的终止过程,2019/7/13,24,3.4.3 进程的挂起和激活,挂起:让进程暂时不参

14、与资源的竞争,1. 挂起原语的方式,把挂起原语调用者本身挂起,即自己挂起自己 挂起某个标识符的进程 将某个指定标识符的进程及其全部或部分子孙挂起. 挂起用以保存N进程的PCB副本的内存区,以备参考.,Procedure suspend(n,a) Begin i=get internal name(n); s=i.status; if i.status=“running” stop(i); a=copy pcb(i); /* 相应的PCB保留起来以便查看是属于哪一种挂起. if s=blocka i.status=Blocks else i.status=readys; if s=running

15、 schedule else continue; End,2019/7/13,25, 当出现了引起进程挂起的事件时，比如，用户进程请求将自己挂起，或父进程请求将自己的某个子进程挂起， 系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。挂起原语的执行过程是：首先检查被挂起进程的状态，若处于活动就绪状态，便将其改为静止就绪；对于活动阻塞状态的进程，则将之改为静止阻塞。 为了方便用户或父进程考查该进程的运行情况而把该进程的PCB复制到某指定的内存区域。最后，若被挂起的进程正在执行，则转向调度程序重新调度。,2. 进程的挂起,2019/7/13,26,. 激活原语的激活方式,激

16、活指定标识符的进程 激活某进程及其子孙,Procedure active(n) Begin i=get internal name(n); if i.status=“readys” i.status=readya else i.status=blocka; if i.status=“readya” scheduler; else continue; End,2019/7/13,27, 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，若该进程驻留在外存而内存中已有足够的空间时，则可将在外存上处于静止就绪状态的进程换入内存。这时，系统将利用激活原语active( )将指定进程激活。

17、 激活原语先将进程从外存调入内存，检查该进程的现行状态，若是静止就绪，便将之改为活动就绪；若为静止阻塞便将之改为活动阻塞。假如采用的是抢占调度策略，则每当有新进程进入就绪队列时，应检查是否要进行重新调度，即由调度程序将被激活进程与当前进程进行优先级的比较，如果被激活进程的优先级更低，就不必重新调度；否则，立即剥夺当前进程的运行，把处理机分配给刚被激活的进程。,. 进程的激活,2019/7/13,28,.挂起引起的原因,协调负载过重 某些设备故障 调试程序,具有挂起状态的进程状态图,2019/7/13,29,1. 引起阻塞和唤醒的事件,请求系统服务 启动某种操作 新数据尚未到达 无新工作可作.,

18、3.4.4 进程的阻塞与唤醒,Procedure Block(n) Begin i=EP; 从执行进程的指针EP获得调用者内部标识符 stop(i); i.status=blocka; 修改该进程的状态 i.state=WQ(r); 找到相应的插入队列 insert(WQ(r),i); 把i插入到WQ队尾 scheduler; 转调度程序 End,. 阻塞原语,2019/7/13,30,正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，由于此时该进程还处于执行状态，所以应先立即停

19、止执行，把进程控制块中的现行状态由“执行”改为阻塞，并将PCB插入阻塞队列。如果系统中设置了因不同事件而阻塞的多个阻塞队列，则应将本进程插入到具有相同事件的阻塞(等待)队列。 最后，转调度程序进行重新调度，将处理机分配给另一就绪进程，并进行切换，亦即，保留被阻塞进程的处理机状态(在PCB中)，再按新进程的PCB中的处理机状态设置CPU的环境。,2. 进程阻塞的过程,2019/7/13,31,唤醒原语:由于资源的释放才能利用此资源把某些因等待 此资源而被阻塞的进程唤醒,Procedure Wakeup(n) Begin i=get internal name(n);找到相应的给定资源进程N并获取

20、N进程的内部名 remove(WQ(r),i); 把i进程从等待队列r中去除. i.status=readys; 置i进程为就绪状态 i.state=RQ; 把i进程插入到就绪队列 insert(RQ,i); 把i插入到RQ队尾 continue; End,2019/7/13,32,当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒。唤醒原语执行的过程是：首先把被阻塞的进程从等待该事件的阻塞队列中移出，将其PCB中的现行状态由阻塞改为就绪，然后再将该PCB插入到就绪队列

21、中。,3. 进程唤醒过程,2019/7/13,33,相交进程:多个并发进程在逻辑上存在着相互关系,无关进程(不相交进程):在逻辑上无任何联系的进程,. 进程间的作用,直接作用:进程间的相互联系是有意识的安排的.,间接作用:进程间要通过某种中介发生联系,是无意识的.,3.5 进程间的相互作用,. 进程间的联系,相交进程:多个并发进程在逻辑上存在着相互关系,无关进程(不相交进程):在逻辑上无任何联系的进程,进程间的联系,进程的同步机制-信号量及P.V操作(解决进程同步互斥问题),2019/7/13,34,进程间的相互联系,2019/7/13,35,3.5.1 进程的互斥,由于各进程要求共享资源,而

22、有些资源需要互斥使用,因此各进程间竞争使用这些资源,进程的这种关系未进程的互斥.反映在资源的使用本身时排它的,从而引起进程间资源的竞争.,临界资源(critical resource):,一次只允许一个进程使用的资源(或者排它性使用的资源),2019/7/13,36,与时间有关的错误,. 顺序程序特征,. 程序的顺序执行 一条指令执行结束之后,下一条指令才开始.或者说一条指令的执行应该在它前一条指令的执行结果的基础之上才能进行。,顺序性,允许环境的封闭性,运行结果的确定性,运行结果的可再现,2019/7/13,37,例:,同学甲,同学乙,if 有空椅子 then 坐下,if 有空椅子 then

23、 搬走,造成的结果,运行结果的不确定性 不能保证运行环境的封闭性 不能保证顺序性 运行结果的不可再现性,2019/7/13,38,.并行程序的特征,共享性 并发性 随机性,主机,A,B,C,D,时间片到,A进程,B进程,if (x0 ) x=x-1; . . .,if (x0 ) x=x-1; . . .,.例1:民航售票,2019/7/13,39,.临界区(互斥区):Critical Section,把程序当中具有共享资源并且对共享资源进行操作的这段程序,或者说在进程中涉及到临界资源的程序段叫做临界区.,a=a+1 print(a),a=a-1 print(a),P1,P2,P3,If a0

24、 a=a+1; Else a=a-1;,2019/7/13,40,程序段1,程序段2,程序段3,共享变量,2019/7/13,41,使用临界区的原则,有空让进:当临界区中无进程时,任何有权使用临界区的进程可进入,无空等待:不允许两个以上的进程同时进入临界区.,多中选一:当没有进程在临界区,而同时有多个进程要求进入临界区, 只能让其中一个进入临界区,其他进程必须等待.,有限等待:任何进入临界区的进程要求在有限的时间内得到满足.,让权等待:处于等待状态的进程应该放弃占用CPU,以便使得其他进程 有机会得到CPU的使用权.,2019/7/13,42,3.5.2 进程互斥的两种解决方法,.由竞争各方平

25、等协商,.引人一进程管理者,由管理者来协调竞争各方对互斥资源的使用.,具体办法: 硬件(当一个进程进入临界区,就屏蔽所有中断) 软件(用编程解决,但常常忙等待),2019/7/13,43,进程互斥的软件方法,通过平等协商方式实现进程互斥的最初方法是软件方法.,软件方法1:,While(free) free=true;,free=false;,临界区,free:表示临界区标志 true:有进程在临界区 false:无进程在临界区(初值),其基本思路：是在进入临界区检查和设置一些标志，如果已有进程在临界 区，则在进入区通过循环检查进行等待；在退出区修改标志。,问题：设置什么标志和如何检查标志。,2

26、019/7/13,44,软件方法2:,While( not turn);,Turn=false,临界区,turn: true表示P进入临界区 false表示Q进程临界区,P:,While( turn);,Turn=true,临界区,Q:,2019/7/13,45,软件方法3:,Pturn=true; While( qturn);,Pturn=false,临界区,Pturn,qturn:初值为false P进入临界区的条件:pturn not qturn Q进入临界区的条件:not Pturn qturn,P:,Qturn=true; While (pturn),Qturn=false,临界区,

27、Q:,2019/7/13,46,例:,进行修改,. while (flag1); flag0=true; 临界区; flag0=false;,进程1,. while (flag0); flag1=true; 临界区; flag1=false;,falg0,flag1,. while (flag1); 临界区; flag0=false;,. while (flag0); 临界区; flag1=false;,再进行修改,flag1=true;,flag0=true;,2019/7/13,47,. flag0=true; while (flag1) begin flag0=false; wait(5

28、); flag0=true; end 临界区; flag0=false;,. flag1=true; while (flag0) begin flag1=false; wait(5); flag1=true; end 临界区; flag1=false;,2019/7/13,48,软件方法4:Dekker算法,Pturn,qturn:初值为false P进入临界区的条件:pturn not qturn Q进入临界区的条件:not Pturn qturn Turn:枚举类型,初值任意,2019/7/13,49,While (true) pturn=true; while( qturn) if (t

29、urn=2) pturn=false; while(turn=2); pturn=true; ,turn=2; pturn=false; ,临界区,P:,While (true) qturn=true; while( pturn) if (turn=2) qturn=false; while(turn=1); qturn=true; ,turn=1; qturn=false; ,临界区,Q:,2019/7/13,50,软件解决的缺点:,忙等待 实现过于复杂,需要高的编程技巧.,Peterson算法,pturn=true; turn=2; while( qturn,Pturn=false,临界区

30、,P:,Qturn=true; Turn=1; while (pturn,Qturn=false,临界区,Q:,2019/7/13,51,硬件办法1,boolean Ts(boolean *lock) boolean old; old=*lock; *lock=true; return(old); ,while Ts (*lock);,临界区,lock=false;,“测试并设置”指令,2019/7/13,52,硬件办法2,Void swap(int *a,int *b) int temp temp=*a; *a=*b; *b=temp; ,key=true; Do swap(*lock,ke

31、y); while(key);,临界区,lock=false;,“交换”指令,2019/7/13,53,硬件办法3,“开关中断”指令,进入临界区前执行：执行“关中断”指令,离开临界区后执行：执行“开中断”指令,2019/7/13,54,3.5.3 进程的同步机制-信号量及p.v操作,同步机制,信号量及P.V操作 管程 条件临界域 路径表达式等(用于集中式系统中),同步机制应满足的基本要求,描述能力必须能够详细描述出进程间这种相互配合以及相互矛盾的关系. 可以实现实现起来方便,这种机制在一定的机制或一定的语言上要能够实施. 效率高不然的话,它会降低系统的并行能力和并行程度. 使用方便,2019/

32、7/13,55,信号量(semaphore) 是一个数据结构;严格说来它是一个整型变量,能够刻画一定程序的状态.,.信号量(semaphore)的定义,struc semaphore int value; pointer_pcb queue; ,.信号量说明,Semaphore s;,2019/7/13,56,信号量,互斥的信号量:P.V操作一定在同一个进程中 同步的信号量:P.V操作在不同的进程当中,信号量的物理意义,S0:S表示可用资源的个数. S=0:S表示无资源使用,也无等待进程. S0: 表示等待队列中进程的个数,S,问题:信号量的初值不能为负,为什么?,2019/7/13,57,原

33、语:primitive or acomic action,是由若干机器指令构成的完成某种特定功能的一段程序,具有不可 分割性.即原语的执行必须是连续的,在执行过程中不允许被中断.,原语实现:开关中断,必须置一次且只能设一次初值 初值不能为负数 修改信号量的值只能由P.V进行操作.,信号量的使用原则:,2019/7/13,58,P.V操作/ *原语,P(s) s.value=s.value-1; if (s.value0) 该进程状态置为等待态 将该进程的PCB插入相应的等待队列未尾s.queue; ,V(s) s.value=s.value+1; if (s.value=0) 唤醒相应等待队列

34、s.queue中等待的一个进程 改变其状态为就绪态. 并将其插入就绪队列. ,2019/7/13,59,P(mutex) V(mutex),临界区,P(mutex) V(mutex),临界区,P(mutex) V(mutex),临界区,P1,P2,P3,用P.V操作解决进程间的互斥问题,2019/7/13,60,1.进程A和B共享一台打印机,A进程,B进程, 打印 ,互斥的例子:,P(s),V(s), 打印 ,P(s),V(s),S=1,2019/7/13,61,互斥的例子:,2. 4个进程A、B、C、D共享2台打印机,A进程,B进程,C进程,B进程,初值:,S=2,执行过程的S值：,2,1,

35、0,-1,-2,-1, 打印 ,P(s),V(s), 打印 ,P(s),V(s), 打印 ,P(s),V(s), 打印 ,P(s),V(s),等,等,2019/7/13,62,3.6 进程的同步, 指两个或多个进程相互配合进行工作,其中某一个进程在未得到它的伙伴进程发来消息的时候,它就应该处于等待状态,这种等待状态一直持续到它的伙伴发来的信息为止,靠这种方法来协调彼此之间的工作.这种情形称为同步, 指系统中多个进程间发生的事件存在某种时序关系,需要相互合作,共同完成一项任务.具体说,一个进程运行到某一点时要求另一伙伴进程为它提供消息,在未获得消息之前,该进程处于等待状态,获得消息后,被唤醒进入

36、就绪态.,2019/7/13,63,例:,司机(P1),售票员(P2),While(true) 启动车辆 正常运行 到站停车 ,While(true) 关门 售票 开门 ,2019/7/13,64,同步的例子:,1. 矩阵运算A+B,进程甲:负责输入A矩阵,进程乙:负责输入B矩阵,并计算A+B,S=0,输 入 A,输 入 B,P(s),V(s),慢,;等,计算A+B,S,S,第一种（甲快）:,第二种（乙快）：,执行过程：,输 入 B,输 入 A,输 入 B,快,2019/7/13,65,规定：一次只可放一个产品 生产者：生产一件产品，放入仓库，一次只能放一件产品 消费者：消费一件产品，从仓库中

37、取一件产品消费,2. 经典的生产者消费者问题,生产者,消费者,仓库,放产品,取产品,2019/7/13,66,同步问题,P进程不能往满的缓冲区中放产品，设置信号量为S1 Q进程不能从空的缓冲区中取产品，设置信号量为S2,问题：怎么知道设置2个信号量S1和S2,生产者进程,. 生产一件产品 P(S1) 放入仓库,消费者进程,. P(S2) 取一件产品 消费,S1:,表示仓库中的空位,S2:,表示仓库中的产品,2019/7/13,67,P:,S1=,1,Q:,S2=,0,While (true) 生产一个产品; P(S1); 送产品到缓冲区; V(S2); ,While (true) P(S2);

38、 从缓冲区中取产品; V(S1); 消费产品; ,2019/7/13,68,P,放消息,Q,取消息,i,j,此图说明的问题:,当缓冲区增大的时候,2019/7/13,69,3. 多个缓冲区的生产者消费者问题,P:,Q:,i=0; While (true) 生产产品; P(S1); 往Bufferi放产品 V(S2); i=(i+1)%n; ,j=0; While (true) P(S2); 从Bufferj中取产品; V(S1); 消费产品; j=(j+1)%n; ,此例所关注的问题,1. 生产的产品放在缓冲区的哪个位置上去.,S1,S2,=n,=0,2. 初值,2019/7/13,70,思考

39、题:要不要对缓冲区(临界资源)进程互斥操作?,生产者-消费者的归类, 单一资源的生产者-消费者,S1,S2,=1,=0,S1,S2,=n,=0,S2,=0, 有限资源的生产者-消费者, 无限资源的生产者-消费者,2019/7/13,71,4. 个缓冲区的生产者消费者问题,P:,Q:,i=0; While (true) 生产产品; P(S1); 往Bufferi放产品 V(S2); i=(i+1) % n; ,j=0; While (true) P(S2); 从Bufferj中取产品; V(S1); 消费产品; j=(j+1) % n; ,P:,S2,=0,上面情况所关注的问题:,一个生产者和一

40、个消费者的问题,2019/7/13,72,n个缓冲区,m个生产者和k个消费者问题,P:,Q:,i=0; While (true) 生产产品; P(S1); P(mutex) 往Bufferi放产品 V(mutex) V(S2); i=(i+1) % n; ,j=0; While (true) P(S2); P(mutex) 从Bufferj中取产品; V(mutex) V(S1); 消费产品; j=(j+1) % n; ,S2=,mutex=,S1=,n,0,1,2019/7/13,73,注意: 互斥信号量使用不当,会产生与时间有关的错误,P操作的顺序非常重要(如颠倒两个P操作的顺序) 对临界

41、区(仓库)使用不当,P:,Q:,i=0; While (true) 生产产品; P(S1); P(mutex) 往Bufferi放产品 V(mutex) V(S2); i=(i+1) % n; ,j=0; While (true) P(mutex); P(S2); 从Bufferj中取产品; V(mutex) V(S1); 消费产品; j=(j+1) % n; ,2019/7/13,74,解决办法: 引入两个互斥信号量:,mutex1,mutex2,=1,=1,P:,Q:,i=0; While (true) 生产产品; P(S1); P(mutex1); 往Bufferi放产品; i=(i+1

42、) % n; V(mutex1) V(S2); ,j=0; While (true) P(S2); P(mutex2) 从Bufferj中取产品; j=(j+1) % n; V(mutex2); V(S1); 消费产品; ,生产者所关心的,消费者所关心的,:,说明他们针对的临界资源是不一样的,完全可以把他们划分开来,2019/7/13,75,S0:S表示可用资源的个数. S=0:S表示无资源使用,也无等待进程. S0: 表示等待队列中进程的个数,S,P.V操作总结:,1. 信号量的物理意义,P(S):表示申请或使用一个资源.因此S=S-1;,V(S):表示释放一个资源.因此S=S+1;,信号量

43、的初值应该大于等于0,说明:,2. P.V操作必须成对出现,有一个P操作就一定有一个V操作,当为互斥操作时,它们处于同一进程. 当为同步操作时,则不在同一进程. 如果P(S1)和P(S2)两个操作在一起,那么P操作的顺序至关重要,一个同步P操作与一个互斥P操作在一起时,同步P操作在互斥P操作前,而两个V操作无关紧要.,2019/7/13,76,3. P.V操作的优缺点,优点:简单,而且表达能力强(用P.V操作可以解决任何同步互斥问题),不够安全. P.V操作使用不当会出现死锁. 遇到复杂同步互斥问题时实现复杂,缺点:,2019/7/13,77,例:,有一个充分大的池子,两个人分别向池子里扔球,

44、甲扔红球,乙扔兰球, 一次扔一个.开始时池子里有红、兰球各一个。要求池子里球满足条件,1,2,红球数,兰球数,用P.V描述两个进程,扔红球者,. P(r) 扔一个 V(b),扔兰球者,. P(b) 扔一个兰球 V(r) V(r),原来的条件,兰,红,2兰,r=,1,b=,0,2019/7/13,78,例:,有一个大池子,三个人分别向池子里扔球,甲扔兰球,乙扔红球,丙扔绿 球，一次扔一个。开始时池子里有红、兰、绿球各一个。,1,2,红,兰,用P.V描述三个进程用以解决这个问题,扔红球者,. P(r) 扔一个红 V(b1)； V(g),扔兰球者,. P(b1); P(b2); 扔一个兰球; V(r

45、) V(r) V(g),要求池子里球满足条件：,兰,红兰,绿,扔兰球者,. P(g) 扔一个绿球 V(b2),r=,b1=,g=,b2=,说明：b1表明兰球受到红球的制约，b2表明兰球受到绿球的制约,1,0,1,0,2019/7/13,79,例:,有一仓库，可以存放A和B两种产品。,用P.V描述三个进程用以解决这个问题,要求满足条件：,-N,B产品数量,A产品数量,-,每次只能存入一种产品（A或B）,M,int mutex=1; int a=M-1; int b=N-1; main() while(true) 取一个产品； if (A) P(a); p(mutex); 将产品入库； v(mut

46、ex); v(b); ,else P(b); p(mutex); 将产品入库； v(mutex); v(a); ,2019/7/13,80,第二类经典的同步问题,1.读者写者问题：有两组并发进程：读者和写着共享一组数据区。,要求：允许多个读者同时执行读操作 不允许读者、写着同时操作（读、写互斥） 不允许多个写者同时操作（只能一个写）,第一类：读者优先策略,如果读者来 无读者、写者，新读者可以读 有写者等，但有其他读者正在读，则新读者也可以读。 有写者写，新读者等。,如果写者来 无读者，新写者可以写。 有读者，新写者等待。 有其他写者，新写者等待。,2019/7/13,81,写进程,. P(Wr

47、t); 写； V(Wrt);,读进程,. P(Wrt)； 读； V(Wrt);,Wrt,=1,2019/7/13,82,读者,While (true) P(mutex); readcount+; if (readcount1） P(w); V(mutex); 读； P(mutex); readcount- -; if (readcount= =0) V(w); V(mutex); ,写者,While (true) P(w); 写； V(w); ,2019/7/13,83,2.哲学家就餐问题： 有五个哲学家，围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之间放一只筷子。每个哲学家的行为是思考，感到饥饿，然后吃通心粉。为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边取筷子。,为防止死锁发生可采取的措施：,最多允许4个哲学家同时坐在桌子周围 仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。 给所有哲学家编号，奇数号的必须先拿左边，偶数号的必须先拿右边的。,为了避免死锁，把哲学家分成三种状态：思考、饥饿、进 食。并且一次拿到两只筷子，否则不拿。,2019/7/13,84,哲学家就餐问题解法,#define N 5 #define THINKING 0 #define HUNGRY 1 #define EATING