《进程管理》PPT课件.ppt

《《进程管理》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《进程管理》PPT课件.ppt（93页珍藏版）》请在三一办公上搜索。

1、第二章进程管理(2),第二章进程管理(2),2.4 进程同步2.5 管程机制2.6 进程通信,2.4 进程的同步,在多道程序系统中，由于资源共享或进程合作，使进程间形成间接相互制约和直接相互制约关系，这需要用进程互斥与同步机制来协调两种制约关系。进程同步的主要任务是使并发执行的进程间有效的共享资源和相互合作，进程的同步机制信号量及P.V操作（解决进程同步互斥问题）,直接作用(相互合作）：进程间的相互联系是有意识的安排的，直接作用只发生在相交进程间间接作用（资源共享）：进程间要通过某种中介发生联系，是无意识安排的，可发生在相交进程之间，也可发生在无关进程之间,1.进程间的关系,2.进程的同步（直

2、接作用）,指系统中多个进程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。具体说，一个进程运行到某一点时要求另一伙伴进程为它提供消息，在未获得消息之前，该进程处于等待状态，获得消息后被唤醒进入就绪状态,由于各进程要求共享资源，而有些资源需要互斥使用，因此各进程间竞争使用这些资源，进程的这种关系为进程的互斥。临界资源：系统中某些资源一次只允许一个进程使用，称这样的资源为临界资源或互斥资源或共享变量,3.进程的互斥（间接作用）,4.基本概念,进程互斥：指在多道程序环境下，每次只允许一个进程对临界资源进行访问。进程同步：指多个相关进程在执行次序上的协调。临界资源:一次仅供一个进程使用的

3、资源。在进程中涉及到临界资源的程序段叫临界区多个进程的临界区称为相关临界区,5.使用互斥区的原则,空闲让进：当无进程在互斥区时，任何有权使用互斥区的进程可进入忙则等待：不允许两个以上的进程同时进入互斥区有限等待：任何进入互斥区的要求应在有限的时间内得到满足让权等待：处于等待状态的进程应放弃占用CPU，以使其他进程有机会得到CPU的使用权,使用互斥区的原则：前提：任何进程无权停止其它进程的运行 进程之间相对运行速度无硬性规定进程互斥的解决有两种做法:由竞争各方平等协商引入进程管理者，由管理者来协调竞争各方对互斥资源的使用具体方法：硬件（当一个进程进入临界区,就屏蔽所有中断，但成本高）软件（用编程

4、解决，但常常忙等待）,6.进程互斥的软件方法,通过平等协商方式实现进程互斥的最初方法是软件方法 其基本思路是在进入区检查和设置一些标志，如果已有进程在临界区，则在进入区通过循环检查进行等待；在退出区修改标志 其中的主要问题是设置什么标志和如何检查标志软件解法的缺点：1.忙等待 2.实现过于复杂 3.需要高的编程技巧,软件解法(1),free:表示临界区标志 true:有进程在临界区 false:无进程在临界区(初值).while(free);free=false;临界区 free=true;,软件解法(2),turn:true P进入临界区 false Q进入临界区.P:while(not t

5、urn);临界区 turn=false;Q:while(turn);临界区 turn=true;,软件解法(3),pturn,qturn:初值为falseP进入临界区的条件:pturn not qturnQ进入临界区的条件:not pturn qturn P.Q.pturn=true;pturn=true;while(qturn);while(pturn);临界区 临界区 pturn=false;qturn=false;.,硬件解法(1)“测试并设置”指令,boolean TS(boolean*lock)boolean old;old=*lock;*lock=true;,while TS(,硬

6、件解法(2)“交换”指令,void SWAP(int*a,int*b)int temp;temp=*a;*a=*b;*b=temp;,key=true;do SWAP(,硬件解法(3)“开关中断”指令,进入临界区前执行：执行“关中断”指令离开临界区后执行：执行“开中断”指令,7 进程的同步机制信号量及P.V操作（解决进程同步）,同步机制：信号量及P、V操作；管程；条件临界域；路径表达式等（用于集中式系统中）会合；通信顺序进程；分布进程；远程过程调用等（适用于分布式系统中）,描述能力可以实现效 率 高 使用方便,1)同步机制应满足的基本要求,2)解决互斥的锁机制,实现互斥的一种软件方法是采用锁机

7、制，即提供一对上锁(Lock)和开锁(UnLock)原语，以及一个锁变量W。进程进入临界区前，通过锁变量来判断临界资源是否被占用。,3)信号量机制,信号量机制是一种卓有成效的进程同步工具，被广泛应用于单处理机和多处理机系统，以及计算机网络中。锁机制仅能表示“开”与“关”两种状态；开、关锁原语必须作为原子操作来进行；关锁原语言中反复测试状态，浪费了处理机的时间；锁机制只能解决互斥，不能用于同步。信号量同步机制能完满地解决上述问题。,信号量：semaphore,是一个数据结构定义如下：struc semaphore int value;pointer_PCB queue;信号量说明：semapho

8、re s;,P操作,P(s)s.value=s.value-;if(s.value 0)该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue;,操作,意味着请求分配一个单位资源,V操作,V(s)s.value=s.value+;if(s.value=0)唤醒相应等待队列s.queue中等待的一个进程 改变其状态为就绪态 并将其插入就绪队列,操作,意味着释放一个单位资源,P、V操作为原语操作 原语：是由若干多机器指令构成的完成某种特定功能的一段程序，具有不可分割性。即原语的执行必须是连续的，在执行过程中不允许被中断 实现：开关中断,信号量的使用：必须置一次且只能置一次初值

9、 初值不能为负数 只能执行P、V操作,用P、V操作解决进程间互斥问题,互斥例子,三个进程共用两个I/O缓冲区。解：设用信号量S表示共享资源，S初始值为2,同步例子,有A、B两进程，A进程从卡片机读信息入缓冲区，B进程负责加工读进缓冲区的卡片解：设信号量S1：缓冲区中有否可供加工的信息，初始值为0；信号量S2：缓冲区是否为空，初始值为1。,同步例子（续）,在输入进程A中，可以把P(S2)调到V(S1)后面，而把信号量S2的初始值设为0。,用P-V操作描述前趋关系的例子,信号量还可以描述程序或语句之间的前趋关系。,用P-V操作描述前趋关系（续）,描述如下：Var a，b，c，d，e，f，g：sem

10、aphore：=0，0，0，0，0，0，0；begin parbegin beginS1；V(a)；V(b)；end；beginP(a)；S2；V(c)；V(d)；end；beginP(b)；S3；V(e)；end；beginP(c)；S4；V(f)；end；beginP(d)；S5；V(g)；end；beginP(e)；P(f)；P(g)；S6；end；parend end,经典的生产者消费者问题,消费者,生产者,经典的生产者消费者问题,同步问题：P进程不能往“满”的缓冲区中放产品，设置信号量为S1 Q进程不能从“空”的缓冲区中取产品，设置信号量S2,S1初值为1，S2初值为0,P：Q：wh

11、ile(true)while(true)生产一个产品;P(s2);P(s1);从缓冲区取产品;送产品到缓冲区;V(s1);V(s2);消费产品;,生产者-消费者问题,生产者消费者(Producer-Consumer)问题是著名的进程同步问题。它描述一组生产者向一组消费者提供消息，它们共享一个有界缓冲池，生产者向其中投放消息，消费者从中取得消息。以下用信号量解决生产者消费者问题。假设缓冲池中有n个缓冲区，每个缓冲区存放一个消息，可利用互斥信号量mutex使诸进程对缓冲池实现互斥访问；利用empty和full计数信号量分别表示空缓冲及满缓冲的数量。又假定这些生产者和消费者互相等效，只要缓冲池未满，

12、生产者可将消息送入缓冲池；只要缓冲池未空，消费者可从缓冲池取走一个消息。,生产者-消费者问题（续）,其中，mutex，empty，full的初始值分别为1，n，0；,P操作的顺序可换吗？,P.V操作讨论,1)信号量的物理含义：S0表示有S个资源可用 S=0表示无资源可用 S0则|S|表示S等待队列中的进程个数 P(S):表示申请一个资源 V(S)表示释放一个资源。信号量的初值应该大于等于02)P.V操作必须成对出现，有一个P操作就一定有一个V操作 当为互斥操作时，它们同处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至 关重要,一个

13、同步P操作与一个互斥P操作在一起时同步P操作在互斥P操作前 而两个V操作无关紧要,P.V操作的优缺点,P.V操作优点：简单，而且表达能力强（用P.V操作可解决任何同步互斥问题）缺点：“不够安全；P.V操作使用不当会出现死锁；遇到复杂同步互斥问题时实现复杂,8.信号量集AND型信号量集,AND型信号量集是指同时需要多种资源且每种占用一个时的信号量操作 AND型信号量集的基本思想：在一个原语中申请整段代码需要的多个临界资源，要么全部分配给它，要么一个都不分配AND型信号量集P原语为SwaitAND型信号量集V原语为Ssignal,Swait(S1,S2,Sn)/P原语；while(TRUE)if(

14、S1=1,Ssignal(S1,S2,Sn)for(i=1;i=n;+i)+Si;/释放占用的资源；for(在Si.queue中等待的每一个进程P)/检查每种资源的等待队列的所有进程；从等待队列Si.queue中取出进程P;,if(判断进程P是否通过Swait中的测试)/注：与signal不同，这里要进行重新判断；/通过检查（资源够用）时的处理；进程P进入就绪队列;else/未通过检查（资源不够用）时的处理；进程P进入某等待队列；,9.一般“信号量集”,一般信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理 一般信号量集的基本思路就是在AND型信号量

15、集的基础上进行扩充，在一次原语操作中完成所有的资源申请。,进程对信号量Si的测试值为ti（表示信号量的判断条件，要求Si=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：Swait(S1,t1,d1;.;Sn,tn,dn);Ssignal(S1,d1;.;Sn,dn);,一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：,Swait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配Swait(S,1,1)表示互斥信号量Swait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入临界区；当S=0

16、时，禁止任何进程进入临界区）,【思考题】,1.用P.V操作解决下图之同步问题:,get,copy,put,f,s,t,g,用P.V操作解决司机与售票员的问题,10.经典问题,1)读者写者问题 有两组并发进程:读者和写者,共享一组数据区 要求：允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作,第一类：读者优先,如果读者来：1）无读者、写者，新读者可以读2）有写者等，但有其它读者正在读，则新读者也可以读3）有写者写，新读者等如果写者来：1）无读者，新写者可以写2）有读者，新写者等待3）有其它写者，新写者等待,第一类读者写者问题的解法,读者：while(true)P(mu

17、tex);readcount+;if(readcount=1)P(w);V(mutex);读 P(mutex);readcount-;if(readcount=0)V(w);V(mutex);,写者：while(true)P(w);写 V(w);,第一类读者写者问题的解法（一般信号量集）,读者：swait(wmutex,1,1;rcount,R,0);写；ssignal(wmutex,1);,写者：swait(rcount,1,1;wmutex,1,0);写；ssignal(rcount,1);,2)哲学家就餐问题,有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每人面前有一只空盘子，每两人之

18、间放一只筷子 每个哲学家的行为是思考，感到饥饿，然后吃通心粉 为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子,#define N 5 void philosopher(int i)while(true)思考；取forki;取fork(i+1)%5；进食；放forki;放fork(i+1)%5；,为防止死锁发生可采取的措施：最多允许4个哲学家同时坐在桌子周围仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 为了避免死锁，把哲学家分为三种状态，思考，饥饿，进食，并且一次拿到两只

19、筷子，否则不拿,3)第二类读者写者问题：写者优先条件：1）多个读者可以同时进行读2）写者必须互斥（只允许一个写者写，也不能读者写者同时进行）3）写者优先于读者（一旦有写者，则后续读者必须等待，唤醒时优先考虑写者）,第二章进程管理 2.5 管程机制,1.管程的提出,采用P-V同步机制来编写并发程序，对于共享变量及信号量变量的操作将被分散于各个进程中 缺点：（）易读性差，因为要了解对于一组共享变量及信号量的操作是否正确，则必须通读整个系统或者并发程序（）不利于修改和维护，因为程序的局部性很差，所以任一组变量或一段代码的修改都可能影响全局（）正确性难以保证，因为操作系统或并发程序通常很大，要保证这样

20、一个复杂的系统没有逻辑错误是很难的,2.管程概念,概念：指关于共享资源的数据及在其上操作的一组过程或共享数据结构及其规定的所有操作。系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性。,3.管程的组成,管程的四个组成部分：名称数据结构说明对该数据结构进行操作的一组过程/函数初始化语句 局部于管程的数据结构，仅被局部于管程的过程访问。局部于管程的过程，也仅能访问管程内的数据结构。管程（相当于围墙）把共享变量和对它进行操作的若干过程围起来。,管程：一种同步机制

21、系统按资源管理的观点分解成若干模块，用数据表示抽象系统资源，同时分析了共享资源和专用资源在管理上的差别，按不同的管理方式定义模块的类型和结构，使同步操作相对集中，从而增加了模块的相对独立性,管程的形式TYPE monitor_name=MONITOR;共享变量说明define 本管程内所定义、本管程外可调用的过程（函数）名字表use 本管程外所定义、本管程内将调用的过程（函数）名字表PROCEDURE 过程名（形参表）；过程局部变量说明；BEGIN语句序列；END;.,FUNCTION 函数名（形参表）：值类型；函数局部变量说明；BEGIN语句序列；END;.BEGIN共享变量初始化语句序列；

22、END;,模块化:一个管程是一个基本程序单位，可以单独编译 抽象数据类型:管程是一种特殊的数据类型，其中不仅有数据，而且有对数据进行操作的代码 信息掩蔽:管程是半透明的，管程中的外部过程（函数）实现了某些功能，管程中的外部过程（函数）实现了某些功能，至于这些功能是怎样实现的，在其外部则是不可见的,4.管程的三个主要的特性,管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接地访问管程中的共享变量 为了保证管程共享变量的数据完整性，规定管程互斥进入 管程通常是用来管理资源的，因而在管程中应当设有进程等待队以及相应的等待及唤醒操作,5.管程的要素,问题：多个进

23、程出现在管程中 当一个进入管程的进程执行等待操作时，它应当释放管程的互斥权；当一个进入管程的进程执行唤醒操作时（如唤醒），管程中便存在两个同时处于活动状态的进程处理方法有三种：等待继续，直到退出或等待 等待继续，直到等待或退出 规定唤醒为管程中最后一个可执行的操作,因为管程是互斥进入的，所以当一个进程试图进入一个巳被占用的管程时它应当在管程的入口处等待，因而在管程的入口处应当有一个进程等待队列，称作入口等待队列 如果进程唤醒进程，则等待继续，如果进程在执行又唤醒进程，则等待继续，如此，在管程内部，由于执行唤醒操作，可能会出现多个等待进程，因而还需要有一个进程等待队列，这个等待队列被称为紧急等待

24、队列。它的优先级应当高于入口等待队列的优先级,由于管程通常是用于管理资源的，因而在管程内部，应当存在某种等待机制。当进入管程的进程因资源被占用等原因不能继续运行时使其等待。为此在管程内部可以说明和使用一种特殊类型的变量，称作条件变量：VAR C:condition;对于条件型变量，可以执行wait和signal操作：wait（c）：如果紧急等待队列非空，则唤醒第一个等待者；否则释放管程的互斥权，执行此操作的进程的PCB入c链尾部signal（c）：如果c链为空，则相当于空操作，执行此操作的进程继续；否则唤醒第一个等待者，执行此操作的进程的PCB入紧急等待队列的尾部,两个主要途径：直接构造(效率

25、高)间接构造，即用某种已经实现的同步机制去构造例子：用P-V操作构造管程,6.管程的实现,(1）设置进程和管程的目的不同（2）系统管理数据结构 进程：PCB 管程：等待队列（3）管程被进程调用（4）管程是操作系统的固有成分，无创建和撤消,7.管程和进程的异同点,第二章进程管理 2.6 进程通信,1.进程通信概述,P.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）,2.实现进程通信的方式,共享存储器方式：相互通信的进程通过共享某些数据结构或存储区来进行通信，可分为共

26、享数据结构方式、共享存储区方式；消息通信方式：进程间的消息交换以消息或报文为单位，程序员利用一组通信命令(原语)来实现通信，可分为直接、间接通信方式；共享文件方式：利用共享文件来实现进程间的通信。,3.管道通信,在UNIX系统中，利用一个打开的共享文件来连接两个相互通信的进程，该共享文件称为管道(Pipe)，因而该方式又称为管道通信。为了协调双方通信，管道通信必须提供三方面的协调能力：互斥、同步、对方是否存在。,4.消息传递模式,系统为进程提供了两个高级通讯原语send和receive。要进行消息传递时执行send,当接收者要接收消息时执行receive消息缓冲：在内存中开设缓冲区，发送进程将

27、消息送入缓冲区，接收进程接收传递来的缓冲区信箱通信,5.直接方式,共享文件模式：管道通信发送进程发消息时要指定接收进程的名字，反过来，接收时要指明发送进程的名字 Send(receiver,message)Receiver(sender,message)对称形式：一对一非对称形式：多对一（顾客/服务员）有缓冲（有界，无界），无缓冲,直接通信方式,直接通信方式模型,6.消息缓冲（有界缓冲区）,在操作系统空间设置一组缓冲区，当发送进程需要发送消息时，执行send系统调用，产生自愿性中断，进入操作系统，操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息

28、的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。发送进程返回到用户态继续执行。在以后某个时刻，当接收进程执行到receive接收原语时，也产生自愿性中断进入操作系统，由操作系统将载有消息的缓冲区从消息链中取出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行。,直接通信方式实例消息缓冲通信,消息缓冲数据结构（下图）此外，进程的PCB块中增加一些数据项以支持消息缓冲区的通信机制实现；如：mq，消息链首指针；mutex，消息链互斥信号量；Sm，消息链同步计数信号量。,两个进程利用消息缓冲区通信过程,发送原语,接收原语,7.间接方式,

29、发送进程发消息时不指定接收进程的名字，而是指定一个中间媒介，即信箱。进程间通过信箱实现通信 发送原语：send(MB,Message)接收原语：receive(MB,Message),信箱通信,信箱组成 信箱说明 与 信箱体 可存放信件数，已存放信件数，指针信箱使用规则 1）若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被释放 2）若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被释放send（N，M）：把信件M送到指定的信箱N中receive（N，X）：从指定信箱N中取出一封信，存放到指定的地址X中,8.管道通信方式 Pipe 也称共享文件方式，基

30、于文件系统，利用一个打开的共享文件连接两个相互通信的进程，文件作为缓冲传输介质,综合实例,设某台机挂有两个I/O通道：分别挂一台输入机和一台打印机。卡片机上有一叠数据卡片，现在要把这些数据逐一输入到缓冲区B1，然后再复制到缓冲区B2，并在打印机上打印出来。问：系统可设哪些进程来完成这个任务？用P-V原语写这些进程的同步算法。,综合实例（续）,解：由上图可见，系统可设3个进程：输入进程、复制进程、打印进程；分别用进程R、进程C、进程P来表示。这些进程之间的相互制约关系：R受C的约束；C受R、P的约束；P受C的约束。设4个信号量：S1=1，S2=0，S3=1，S4=0 同步算法如下：,The End,