《第二进程管理.ppt》由会员分享，可在线阅读，更多相关《第二进程管理.ppt（148页珍藏版）》请在三一文库上搜索。
1、辽东学院信息技术学院,第二章 进程管理,2.1 进程的基本概念 2.2 进程控制 2.3 进程同步 2.4 经典进程的同步问题 2.5 进程通信 2.6 线程,辽东学院信息技术学院,2.1 进程的基本概念,2.1.1 程序的顺序执行及其特征,I:输入数据,C:处理数据,O:输出结果,数据处理程序,I,C,O,I1,C1,O1,前趋图,辽东学院信息技术学院,a:=x+y; b:=a*5; C:=a+6 D:=a/c,S1: S2: S3: S4:,S1,S2,S3,顺序性： (2) 封闭性： (3) 可再现性：,S4,程序运行时独占全机资源,环境和初始条件相同，运行多次获得相同的结果,辽东学院信
2、息技术学院,2. 1.3 程序的并发执行及其特征,I:输入数据,C:处理数据,O:输出结果,数据处理程序,I,C,O,I1,C1,O1,I2,C2,O2,辽东学院信息技术学院,a:=x+y; b:=a*5; C:=a+6; D:=a/c,S1: S2: S3: S4:,S1,S2,S4,S3,间断性：执行-暂停-执行 (2) 失去封闭性： 资源共享 (3) 不可再现性： 结果不同,辽东学院信息技术学院,不可再现性,例如，有两个程序A和B，它们共享一个变量N。程序A每执行一次时，都要做N=N+1操作；程序B每执行一次时， 都要执行Print(N)操作。程序A和B以不同的速度运行。,辽东学院信息技
3、术学院,某时刻， N=9：,程序A得到的N值为：10,程序B得到的N值为：10,辽东学院信息技术学院,某时刻， N=9：,程序B得到的N值为：9,辽东学院信息技术学院,2.1.4 进程的特征与状态,1. 进程的特征和定义,结构特征：进程控制块（PCB）+数据+程序段 2) 动态性 ：进程一次执行过程；产生、灭亡 3) 并发性 ：并发执行 4) 独立性：独立运行、独立分配资源、独立调度单位 5) 异步性 ：不可预知速度运行,进程引入原因：程序并发执行三大特性不能参与并发，并发+动态描述-进程,辽东学院信息技术学院,较典型的进程定义有： (1) 进程是程序的一次执行。 (2) 进程是一个程序及其数
4、据在处理机上顺序执行时所发生的活动。 (3) 进程是程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的一个独立单位。 在引入了进程实体的概念后，我们可以把传统OS中的进程定义为：“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位”。,辽东学院信息技术学院,进程与程序的区别 (1)程序是指令的有序集合，其本身没有任何运行的含义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。 (2)程序可以作为一种软件资料长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。 (3)进程更能真实地描述并发，而程序不能 (4)进程包括程序和数据+PCB
5、两部分 (5)进程具有创建其他进程的功能，而程序没有 (6)同一程序同时运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程,辽东学院信息技术学院,思考？,为什么引入进程的概念？,辽东学院信息技术学院,2. 进程的三种基本状态,(1)就绪(Ready)状态 (2)执行状态 (3) 阻塞状态,辽东学院信息技术学院,进程的三种基本状态及其转换,执 行,阻 塞,就 绪,时间片完,I/O请求,进程调度,I/O完成,辽东学院信息技术学院,3. 挂起状态 引入挂起状态的原因 终端用户的请求。 (2) 父进程请求。 (3) 负荷调节的需要。 (4) 操作系统的需要。,辽东学院信
6、息技术学院,2) 进程状态的转换,活动就绪静止就绪(挂起)。 (2) 活动阻塞静止阻塞。 (3) 静止就绪活动就绪。 (4) 静止阻塞活动阻塞。,辽东学院信息技术学院,具有挂起状态的进程状态图,请求I/O,静止阻塞,活动阻塞,静止就绪,活动就绪,执行,挂起,挂起,挂起,激活,激活,唤醒,唤醒,时间片到,CPU调度,辽东学院信息技术学院,4创建状态和终止状态,1) 创建状态 创建一个进程两步骤：为一个新进程创建PCB，并填写必要的管理信息；其次，把该进程转入就绪状态并插入就绪队列之中。 刚创建进程 还未进入主存，即创建工作尚未完成，进程还不能被调度运行，其所处的状态就是创建状态。 2) 终止状态
7、 进程自然结束点、出现了无法克服的错误、或是被操作系统所终结、或是被其他有终止权的进程所终结，它将进入终止状态。 进程的终止也要通过两个步骤：首先等待操作系统进行善后处理 ，然后将其PCB清零，并将PCB空间返还系统。,辽东学院信息技术学院,进程的五种基本状态及转换,辽东学院信息技术学院,请求I/O,静止阻塞,活动阻塞,静止就绪,活动就绪,执行,挂起,挂起,挂起,激活,激活,唤醒,唤醒,时间片到,CPU调度,终止,释放,创建,许可,许可,七状态转换图,辽东学院信息技术学院,思考？,1如果单CPU系统中有N个进程，运行的用户进程最多几个，最少几个；阻塞的用户进程最多几个，最少几个？ 2. 有没有
8、这样的状态转换，为什么？ 阻塞运行； 就绪阻塞,辽东学院信息技术学院,2.1.5 进程控制块,1. 进程控制块的作用,进程控制块的作用是使一个在多道程序环境下不能独立运行的程序(含数据)，成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。或者说，OS是根据PCB来对并发执行的进程进行控制和管理的。,为了描述一个进程和其它进程以及系统资源的关系，为了刻画一个进程在各个不同时期所处的状态，人们采用了一个与进程相联系的数据块，称为进程控制块（PCB）。 系统利用PCB来控制和管理进程，所以PCB是系统感知进程存在的唯一标志 进程与PCB是一一对应的,辽东学院信息技术学院,2. 进程控制块
9、中的信息,内部标识符 外部标识符,描述信息,现场信息,控制及资源管理信息,辽东学院信息技术学院,3. 进程控制块的组织方式,1) 链接方式,PCB链接队列示意图,辽东学院信息技术学院,2) 索引方式,按索引方式组织PCB,辽东学院信息技术学院,思考？,何时会发生进程切换？,进程切换指一个进程进处理器,另一个进程出处理器的过程。 若有一个进程从运行态变成阻塞态或就绪态（进程的状态发生改变）,或完成工作后就撤消,则必定会发生进程切换。,辽东学院信息技术学院,2.2 进 程 控 制,2.2.1 进程的创建,1. 进程图(Process Graph),图 2-9 进程树,进程控制就是对系统中的所有进程
10、实施管理，进程控制一般有原语来实现。 原语是由若干条指令组成，用于完成一定功能的一个过程。其特点是原语执行时不可被中断。 常用原语： 创建原语Creat() 终止原语Terminal() 阻塞原语Block()、唤醒原语Wakeup(),描述一个进程的家族关系的有向图。PCB,辽东学院信息技术学院,2. 引起创建进程的事件,用户登录。分时系统 ，系统 (2) 作业调度。 批处理系统，系统 (3) 提供服务。 打印进程，系统 (4) 应用请求。 应用进程自己创建,辽东学院信息技术学院,3. 进程的创建(Creation of Progress),OS调用Creat() 原语 申请一空闲PCB ，
11、获得数字标识符 分配必要的资源 初始化PCB:标识信息到PCB;处理机和进程状态； 插入就绪队列,辽东学院信息技术学院,2.2.2 进程的终止,1. 引起进程终止(Termination of Process)的事件 1) 正常结束：产生中断-OS 2) 异常结束 ：越界；保护错rw;非法指令；运行超时；程序错；I/O错 3) 外界干预 ：操作员或者OS终止；父进程请求；父进程终止,辽东学院信息技术学院,2. 进程的终止过程 OS调用终止原语，过程： (1) 从PCB集合中检索出该进程的PCB，从中读出该进程的状态。 (2) 若被终止进程正处于执行状态，应立即终止该进程的执行，并置调度标志为真
12、，用于指示该进程被终止后应重新进行调度。 (3) 若该进程还有子孙进程，还应将其所有子孙进程予以终止。 (4) 将被终止进程所拥有的全部资源，或者归还给其父进程，或者归还给系统。 (5) 将被终止进程(PCB)从所在队列(或链表)中移出，等待其他程序来搜集信息。,辽东学院信息技术学院,2.2.3 进程的阻塞与唤醒,1. 引起进程阻塞和唤醒的事件,请求系统服务 2) 启动某种操作：如果启动I/O必须等待完成 3) 新数据尚未到达：合作进程 4) 无新工作可做 ：对于某些服务系统进程,辽东学院信息技术学院,2. 进程阻塞过程 正在执行的进程，当发现上述某事件时，由于无法继续执行，于是进程便通过调用
13、阻塞原语block把自己阻塞。可见，进程的阻塞是进程自身的一种主动行为。进入block过程后，,辽东学院信息技术学院,3. 进程唤醒过程 当被阻塞进程所期待的事件出现时，如I/O完成或其所期待的数据已经到达，则由有关进程(比如，用完并释放了该I/O设备的进程)调用唤醒原语wakeup( )，将等待该事件的进程唤醒。唤醒原语执行的过程是：,阻塞-唤醒,辽东学院信息技术学院,2.2.4 进程的挂起与激活,1. 进程的挂起 当出现了引起进程挂起的事件时（用户进程请求；父进程请求；负荷调节；OS需要）， 系统将利用挂起原语suspend( )将指定进程或处于阻塞状态的进程挂起。 挂起原语的执行过程：活
14、动就绪状态-便将其改为静止就绪； 活动阻塞状态的进程- 静止阻塞。,辽东学院信息技术学院,2. 进程的激活过程 当发生激活进程的事件时，例如，父进程或用户进程请求激活指定进程，系统将利用激活原语active( )将指定进程激活。,激活原语： 静止就绪- 活动就绪； 静止阻塞-活动阻塞。,挂起-激活,对换 ：将进程从外存调入内存,辽东学院信息技术学院,思考？,为什么创建进程要用原语来实现？ 请设想一下进程在什么情况下会变为阻塞状态？ 阻塞进程在什么情况下会被唤醒？谁来唤醒它？,辽东学院信息技术学院,复习,程序顺序执行时的特征 程序并发执行时的特征 进程的特征和定义 进程与程序的区别 进程的三种基
15、本状态及转换图 什么是进程控制块?它的作用? OS何时会发生进程切换？,辽东学院信息技术学院,2.3.1 进程同步的基本概念 1两种形式的制约关系 (1) 间接相互制约关系。同处于一个系统中的进程，通常都共享着某种系统资源。 (2)直接相互制约关系。这种制约主要源于进程间的合作。,2.3 进 程 同 步,进程同步： 对多个相关进程在执行次序上进行协调，使系统中诸进程之间能有效地共享资源和相互合作，从而使程序的执行具有可再现性。 同步机制：用来实现同步的机制称作同步机制。,辽东学院信息技术学院,2 . 同步和互斥,同步是进程间共同完成一项任务时直接发生相互作用的关系 同步进程间具有合作关系 在执
16、行时间上必须按一定的顺序协调进行,互斥是并发执行的多个进程由于竞争同一资源而产生的相互排斥的关系 互斥进程彼此在逻辑上是完全无关的 它们的运行不具有时间次序的特征,辽东学院信息技术学院,3.临界资源,一次仅允许一个进程使用的共享资源 如：打印机、内存单元、表格 诸进程间应采取互斥访问方式,辽东学院信息技术学院,4.临界区,临界区：在每个进程中访问临界资源的那段程序。 repeat entry section /进入区 critical section； /临界区 exit section /退出区 remainder section；/剩余代码 until false；,辽东学院信息技术学院,
17、5同步机制应遵循的规则,(1) 空闲让进。当无进程处于临界区时，应允许一个请求进入临界区的进程立即进入自己的临界区。 (2) 忙则等待。当已有进程进入临界区时，其它试图进入临界区的进程必须等待，以保证对临界资源的互斥访问。 (3) 有限等待。对要求访问临界资源的进程，应保证在有限时间内能进入自己的临界区，以免陷入“死等”状态。 (4) 让权等待。当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。,辽东学院信息技术学院,2.3.2 信号量机制,一般说来，信号量s的值与相应资源的使用情况有关 信号量的值仅由P、V操作改变,辽东学院信息技术学院,记录型信号量定义,type s
18、emaphore=record value: integer； L: list of process； end Value-代表资源数目 一个进程链表指针L，用于链接上述的所有等待进程,辽东学院信息技术学院,P（wait)、V(signal)操作都是原语,P操作 (Wait操作)：申请一个单位资源 V操作 (Signal操作)：释放一个单位资源,P(s)操作,当S.value0时，表示该类资源已分配完毕，因此进程应调用block原语，进行自我阻塞，放弃处理机，并插入到信号量链表S.L中,V操作,对信号量的每次signal操作，表示执行进程释放一个单位资源 若加1后仍是S.value0，则表示在
19、该信号量链表中，仍有等待该资源的进程被阻塞， 故还应调用wakeup原语，将S.L链表中的第一个等待进程唤醒,辽东学院信息技术学院,一、用P、V原语实现互斥,例：1台打印机，A和B进程申请使用打印机，进程互斥，正确使用。,辽东学院信息技术学院,A进程： While(1) . 打印 ,B进程： While(1) . 打印 ,互斥信号量mutex（初值为1） Semphore:mutex=1,临界区,P(mutex),P(mutex),V(mutex),V(mutex),信号量及P、V操作讨论,对于两个并发进程争用同一个临界资源，互斥信号量的值仅取1、0和-1三个值 若UTEX1表示没有进程进入临
20、界区 若UTEX0表示有一个进程进入临界区 若UTEX-1表示一个进程进入临界区，另一个进程等待进入。,辽东学院信息技术学院,思考,对于N个并发进程争用同一个临界资源，互斥信号量的取值范围是什么，有什么含义。,辽东学院信息技术学院,二、用P、V原语实现简单同步,例：供者和用者对单缓冲区的同步 供者负责通过读卡机往缓冲区中输入数据 用者则负责从缓冲区中取出数据用于处理,辽东学院信息技术学院,供者进程 L1： 启动读卡机 收到输入结束中断 goto L1,用者进程 L2： 从缓冲区取出信息 goto L2,同步信号量： S1缓冲区资源（初值为1） S2数据资源（初值为0）,P(S1),P(S2),
21、V(S2),V(S1),1) 信号量的物理含义： S0表示有S个资源可用 S=0表示无资源可用 S0则| S |表示S等待队列中的进程个数 P(S)：表示申请一个资源 V(S)：表示释放一个资源。 信号量的初值应该大于等于0,信号量及P、V操作讨论（续1）,辽东学院信息技术学院,【思考题】,用P.V操作解决司机与售票员的问题,辽东学院信息技术学院,同步信号量： S1开车信号量（初值为0） S2开门信号量（初值为0）,P(S1),V(S1),V(S2),P(S2),2) P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出
22、现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要。 一个同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要,信号量及P、V操作讨论（续2）,3）P、V操作的优缺点 优点： 简单，而且表达能力强（用P、V操作可解决任何同步互斥问题） 缺点： 不够安全，P、V操作使用不当会出现死锁； 遇到复杂同步互斥问题时实现复杂,信号量及P、V操作讨论（续3）,辽东学院信息技术学院,三、利用P、V操作解决合作进程的执行次序,若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来
23、表示进程集合的执行次序。如图,辽东学院信息技术学院,例题1,如图，试用信号量实现这三个进程的同步。,Pa： V(SB); V(SC);,Pb： P(SB); ,Pc： P(SC); ,Pa,Pb,Pc,SB,SC,为进程Pa和Pb设置共享公用信号量SB，为进程Pa和Pc设置共享公用信号量SC，初值均为0,辽东学院信息技术学院,【思考题1】,如图，试用信号量实现这三个进程的同步。,Pa,Pb,Pc,SB,SC,【思考题2】,如图，试用信号量实现这6个进程的同步,S12,S13,S14,S45,S26,S35,S56,为进程P1和P2设置共享公用信号量S12， P1和P3设置共享公用信号量S13，
24、 P1和P4设置共享公用信号量S14， P2和P6设置共享公用信号量S26， P3和P5设置共享公用信号量S35， P4和P5设置共享公用信号量S45， P5和P6设置共享公用信号量S56，,P1进程 V(S12); V(S13)； V(S14); ,P2进程 P(S12); V(S26); ,P3进程 P(S13); V(S35）; ,P4进程 P(S14); V(S45)； ,P5进程 P(S35); P(S45); V(S56); ,初值均为0,辽东学院信息技术学院,P5进程 P(S35); P(S45); V(S56); ,P1进程 V(S12); V(S13)； V(S14); ,P
25、2进程 P(S12); V(S26); ,P3进程 P(S13) V(S35） ,P4进程 P(S14); V(S45)； ,P6进程 P(S26); P(S56); ,辽东学院信息技术学院,总结 进程互斥：在OS中，当某一进程正在访问cs时，就不允许其它进程来读写(访问)，否则就会发生后果无法估计的错误，进程之间的这种相互制约关系为进程互斥。,进程同步：并发进程在一些关键点上可能需要互相等待与互通消息，这种相互制约的等待与互通消息，称为进程同步。,辽东学院信息技术学院,进程同步与互斥关系：,都反映了在异步环境下并发进程间的相互制约关系。可归于同步范畴，但互斥是同步问题的一个特例，互斥解决临界
26、区的使用，同步是并发进程在一些关键点上需互相等待互发消息。,辽东学院信息技术学院,2.4经典的进程同步问题,生产者/消费者问题 读者/写者问题 哲学家进餐问题 管程机制,辽东学院信息技术学院,2.4.1生产者/消费者问题描述,通过一个有界缓冲池(包含N个缓冲区)可以把一群生产者p1, p2, pm，和一群消费者Q1, Q2, , Qn联系起来。如图 只要缓冲池未满，生产者就可以把消息送入缓冲池; 只要缓冲池未空，消费者就可以从缓冲区中取走消息。,辽东学院信息技术学院,同步信号量：S1空缓冲区数=n； S2满缓冲区数=0 互斥信号量 mutex=1,辽东学院信息技术学院,图, ,生产者(m)：P
27、,消费者(n)：Q,Buffer(n-1),n个缓冲区,(Buffer),Buffer(0),Buffer(i),生产消息； 申请空缓冲区； 放消息； 指针移动； 满缓冲区+1；,申请满缓冲区； 取消息； 指针移动； 释放空缓冲区； 消费消息；,Buffer(i),i:0，n-1 i=(i+1)%n,Buffer(j),j:0，n-1 j=(j+1)%n,同步信号量：S1空缓冲区数，n；S2满缓冲区数，0。互斥信号量：mutex，1,辽东学院信息技术学院,图,生产者(m)：P,消费者(n)：Q,生产消息； 申请空缓冲区； 放消息； 指针移动； 满缓冲区+1；,申请满缓冲区； 取消息； 指针移动
28、； 释放空缓冲区； 消费消息；,Buffer(i),i:0，n-1 i=(i+1)%n,Buffer(j),j:0，n-1 j=(j+1)%n,同步信号量：S1空缓冲区数，n；S2满缓冲区数，0;互斥信号量：mutex，1.,Message bufferm ; i,j=0;,生产者P： i=0; while (1) 生产消息; P(S1); P(mutex); 往Buffer i放消息; i = (i+1) % n; V(mutex); V(S2); ;,消费者Q： j=0; while (1) P(S2); P(mutex); 从Bufferj取消息; j = (j+1) % n; V(mu
29、tex); V(S1); 消费消息; ;,辽东学院信息技术学院,【思考题】,如果生产者消费者问题中的缓冲池是无界的，又该如何解呢？,辽东学院信息技术学院,生产者(m)：P,消费者(n)：Q,生产消息； 放消息； 指针移动； 满缓冲区+1；,申请满缓冲区； 取消息； 指针移动； 消费消息；,Buffer(i),i=i+1,Buffer(j),j=j+1,互斥信号量：mutex，1,同步信号量：S1满缓冲区，0。,辽东学院信息技术学院,Q： J=0; while (1) P(S1); P(mutex); 从Bufferj取消息; j = j+1; V(mutex); 消费消息; ;,互斥信号量：m
30、utex，1,同步信号量：S1满缓冲区，0。,P： i=0; while (1) 生产消息; P(mutex); 往Buffer i放消息; i = i+1; V(mutex); V(S1); ;,辽东学院信息技术学院,【练习题】,有一个仓库，可以存放A和B两种产品，但要求： （1） 每次只能存入一种产品（A或B） （2） NA产品数量B产品数量M。 其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。,分析：(1)互斥地使产品入库 (2)A-BM，B-AN，A产品的数量不能比B产品的数量少N个以上，A产品的数量不能比B产品的数量多M个以上,辽东学院信息技术学院,仓库,生产产品 申请
31、入库 A产品入库 允许B多放入一个,A产品入库,B产品入库,A-BM，B-AN,生产产品 申请入库 B产品入库 允许A多放入一个,互斥信号量：mutex，1,同步信号量： Sa：表示允许产品A比B多入库的数量，初值为M-1； Sb：表示允许产品B比A多入库的数量，初值为N-1,辽东学院信息技术学院,B产品入库进程： while (1) 生产产品 P(Sb); P(mutex); B产品入库 V(mutex); V(Sa); ;,A产品入库进程： while (1) 生产产品; P(Sa); P(mutex); A产品入库 V(mutex); V(Sb); ;,辽东学院信息技术学院,2.4.2读
32、者/写者问题,有两组并发进程: 读者和写者,共享一组数据区 要求： 允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,辽东学院信息技术学院,第一类：读者优先,如果读者来： 1）无读者、写者，新读者可以读 2）有写者等待写，但有其它读者正在读，则新读者也可以读 3）有写者写，新读者等,如果写者来： 1）无读者，新写者可以写 2）有读者，新写者等待 3）有其它写者，新写者等待,辽东学院信息技术学院,读者操作（Reader）： 判断读者数，为0则申请数据区； 读者数+1； 读数据； 读者数-1 判断读者数，为0则释放数据区；,写者操作（Reader）： 申请数据区； 写数
33、据； 释放数据区；,全局变量：readcount(读者数)，0 互斥信号量：mutex(临界资源数据区)，1 Rmutex(临界资源readcount)，1,辽东学院信息技术学院,读者操作（Reader）： 判断读者数，为0则申请数据区； 读者数+1； 读数据； 读者数-1 判断读者数，为0则释放数据区；,repeat P(Rmutex); if readcount=0 then P(mutex); readcount:=readcount+1; V(Rmutex); 读数据； P(Rmutex); readcount:=readcount-1; if readcount=0 then V(m
34、utex); V(Rmutex); until false;,全局变量：readcount(读者数)，0 互斥信号量：mutex(临界资源数据区)，1 Rmutex(临界资源readcount)，1,辽东学院信息技术学院,写者操作（Reader）： 申请数据区； 写数据； 释放数据区；,写者（Writer）： repeat P (mutex); 写； V(mutex); until false;,全局变量：readcount(读者数)，0 互斥信号量：mutex(临界资源数据区)，1 Rmutex(临界资源readcount)，1,辽东学院信息技术学院,【思考题】写优先,修改读者写者问题的算法
35、，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。,辽东学院信息技术学院,2.4.3哲学家就餐问题,思考,思考,思考,思考,思考,准备进餐,进餐,准备进餐,进餐,问题描述 五位哲学家围桌而坐 哲学家在思考问题时不需要任何资源，思考完问题后进入进餐态。 每人必须获得左右两支筷子才能进餐,辽东学院信息技术学院,哲学家i： 思考； 取左手筷子； 取右手筷子； 吃通心粉； 放左手筷子； 放右手筷子；,第i根筷子,第(i+1)%5根筷子,Philosopheri： repeat 思考； P(forki); P(fork(i+1) % 5)； 进食； V(forki); V(
36、fork(i+1) % 5)； Until false;,互斥信号量：筷子forki ， i取值0-4,辽东学院信息技术学院,哲学家进餐问题分析,死锁,思考,思考,思考,思考,思考,准备进餐,准备进餐,准备进餐,准备进餐,准备进餐,思考,P（left_stick）,P（right_stick),V（left_stick）,eat,V（right_stick),辽东学院信息技术学院,解决方法： 1、至多只允许有四位哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕后释放出他用过的两只筷子，从而使更多的哲学家能够进餐。-限制并发执行的进程数 2、仅当哲学家的左右两只筷子均可用时
37、，才允许他拿起筷子进餐。-采用信号量集 3、规定奇数号哲学家先拿他左边的筷子，然后再去拿右边的筷子；偶数号哲学家则相反。-保证总会有一个哲学家能同时获得两只筷子而进餐,辽东学院信息技术学院,Program diningphilosophers; var fork:array04 of semphore:=1; room:semphore:=4; i:int; Procedure philopher(i:integer); Begin repeat think; wait(room); wait(forki); wait(fork(i+1)mod 5); eat; signal(forki);
38、signal(fork(i+1)mod 5); signal(room); forever end; begin parbegin philopher(0); philopher(1); philopher(2); philopher(3); philopher(4); parend end,辽东学院信息技术学院,信号量： fork0fork4,初始值均为1.分别表示I号筷子可以拿起 Philosophers(i) Begin repeat if (i%2)=0 then P(forki); P(ci+1mod 5); eat; V(forki); V(forki+1mod 5); else
39、P(forki+1mod 5); P(forki); eat; V(forki+1mod 5); V(forki); until false,辽东学院信息技术学院,【思考题】 有一阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名。读者离开时要消掉登记信号，阅览室中共有100个座位，请问：,(1) 为描述读者的动作，应编写几个程序？设置几个进程？进程与程序间的对应关系如何？,(2) 用类Pascal语言和P, V操作写出这些进程间的同步算法。,辽东学院信息技术学院,答：(1) 应编写1个程序；设置2个进程； 进程与程序间的对应关系是：多对1。,进阅览室（
40、P1）： 申请空座位； 填写登记表; 读者+1； 就座，阅读；,出阅览室（P2）： 读者-1； 消掉登记表； 释放空座位； 离开阅览室;,同步信号量：S1座位数，100；S2读者，0 互斥信号量：mutex(临界资源登记表)，1,辽东学院信息技术学院,P1: repeat P(S1); P(mutex); 登记信息; V(mutex); V(S2) 就座，阅读； until false,P2: repeat P(S2) P(mutex); 消掉信息; V(mutex); V(S1); 离开阅览室; until false,(2) begin semphore S1:=100; (有100个座位
41、) semphore S2:=0; (阅读者) semphore mutex: =1; cobegin,coend end,辽东学院信息技术学院,辽东学院信息技术学院,设自行车生产线上有一个箱子，其中 N个位置（N=3)，每个位置可存放一个车架或一个车轮；有一组工人负责生产车架，另一组工人负责生产车轮，第三组工人负责组装自行车，用P,V描述三组工人操作过程。,工人1 Repeat 加工一个车架 车架放入箱中,工人2 Repeat 加工一个车轮 车轮放入箱中,工人3 Repeat 取一个车架; 取2个车轮; 组装一台自行车,信号量：s 箱子空位置=n；s1 车架=0；s2车轮=0；mutex=1
42、,P(s) P(mutex),V(mutex) V(s1),P(s) P(mutex),V(mutex) V(s2),P(s1);P(mutex),V(mutex) P(s2); P(s2);P(mutex),V(mutex) V(s);V(s);V(s),信号量： s 箱子空位置=n ; s1 车架=0； s2车轮=0； mutex=1 cj 车架最多位置=n-2; cl 车轮最多位置=n-1,P(cj),P(cl),V(cj);V(cl);V(cl),辽东学院信息技术学院,2.4.4 管程(monitor)机制,信号量同步的缺点：,同步操作分散：信号量机制中，同步操作分散在各个进程中，使用
43、不当就可能导致各进程死锁; 易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须通读整个系统或者并发程序； 不利于修改和维护：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局； 正确性难以保证：操作系统或并发程序通常很大，很难保证这样一个复杂的系统没有逻辑错误；,辽东学院信息技术学院,管程的基本概念,管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。 管程可增强模块的独立性： 引入管程可提高代码的可读性，便于修改和维护，正确性易于保证 管程被请求和释放资源的进程所调用,辽东学院信息技术学院,条件变量(condition),在管程内部可以说明和
44、使用一种特殊类型的变量-条件变量。每个条件变量表示一种阻塞原因，并不取具体数值相当于每个原因对应一个队列。,辽东学院信息技术学院,同步操作原语C.wait和C.signal：针对条件变量c，执行C.wait（c）的进程将自己阻塞在c队列中，C.signal(c)将c队列中的一个进程唤醒。,C.signal(c) 操作的作用，是重新启动一个被阻塞的进程，但如果没有进程被阻塞，则C.signal(c)操作不产生任何效果，这与信号量机制中的signal操作不同。,条件变量(condition),辽东学院信息技术学院,管程中的多个进程进入,当一个进入管程的进程执行唤醒操作时（如进程唤醒进程），管程结构
45、不允许被唤醒的进程重新执行（管程内只能有一个进程）。这种情况有三种可能的解决办法： P等待Q继续，直到Q等待或退出； Hoare采用。 Q等待P继续，直到P等待或退出； Lampson和Redell采用。 规定唤醒为管程中最后一个可执行的操作，这样被唤醒的进程可以立即执行。,辽东学院信息技术学院,管程示意图,urgent queue,辽东学院信息技术学院,5. 管程的组成,辽东学院信息技术学院,管程的组成,名称： 数据结构说明：一组局部于管程的共享变量 操作原语：对共享变量进行操作的一组原语过程（程序代码）， 初始化代码：对控制变量进行初始化的代码,辽东学院信息技术学院,2.5.2 利用管程解
46、决生产者-消费者问题,参见P60,辽东学院信息技术学院,管程机制(复习),引入原因 过多信号量的使用，容易造成死锁 管程的基本概念 把数据及其上的一组操作看作一个整体管程 管程组成 名称 局部于管程的局部变量 局部于管程的数据初值设置 在数据上的一组操作,辽东学院信息技术学院,2.5 进程的通信,进程之间的信息交换-进程通信 低级通信进程同步 进程的同步，简单的信号交换 如：锁、信号量 高级通信进程通信 高效、大量数据传递,辽东学院信息技术学院,2.5.1 高级进程通信的类型,共享存储器系统 消息传递系统 管道通信系统,辽东学院信息技术学院,基于共享数据结构的通信方式 在这种通信方式中，诸进程
47、公用某些数据结构，借以实现诸进程间的信息交换。 生产者-消费者 缓冲区 程 序 员： 提供对公用数据结构的设置 及对进程间同步的控制 操作系统：提供共享存储器 特 点：低效，只适合传递相对少量的数据。 基于共享存储区的通信方式 在存储器中划出了一块共享存储区，诸进程可通过对共享存储区中数据的读或写来实现通信。 特点：传输大量数据,1. 共享存储器系统,在共享存储器系统中，相互通信的进程共享某些数据结构或共享存储区，进程之间能够通过这些空间进行通信。,辽东学院信息技术学院,消息传递系统：进程间的数据交换，以格式化的消息为单位。 在计算机网络中消息称为报文。程序员直接利用系统提供的一组通信命令(原语)进行通信。,2. 消息传递系统,3. 管道通信,所谓“管道”，是指用于连接一个读进程和一个写进程以实现他们之间通信的一个共享文件，又名pipe文件。,辽东学院信息技术学院,在进程之间通信时，源进程可以直接或间接地将消息传送给目标进程。 1. 直接通信方式 通信原语： Send(Receiver, message);发送一个消息给接收进程 Receive(Send