操作系统第二章-课件_第1页
操作系统第二章-课件_第2页
操作系统第二章-课件_第3页
操作系统第二章-课件_第4页
操作系统第二章-课件_第5页
已阅读5页,还剩236页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第二章进程管理2.1进程的基本概念2.2进程控制2.3进程同步2.4经典进程的同步问题2.52.6进程通信2.7

线程7/23/20231第二章进程管理2.1进程的基本概念

2.1.1前趋图

2.1.2程序的顺序执行及其特征

2.1.3程序的并发执行及其特征

2.1.4

进程的特征与状态

2.1.5进程控制块7/23/20232第二章进程管理前驱图(PrecedenceGraph)前驱图是一个有向无循环图,图中的每个结点可用于表示一条语句,一个程序段或进程;结点间的有向边则表示在两结点之间存在的偏序或前驱关系。P1P2P3P4P5P6P7P8P9结点、有向边、直接前驱、直接后继、初始结点、终止结点无循环关系,可实现顺序执行7/23/20233第二章进程管理程序的顺序执行程序是一个静态的概念,是严格按次序执行的计算机操作序列的集合,体现了编程人员要求计算机完成相应功能时所应采取的顺序步骤。一个较大的程序通常都是由若干个程序段组成。在程序执行时,必须按照某种先后次序逐个执行,仅当前一操作执行完后,才能执行后继操作。例如:在进行计算时,总是先输入用户的程序和数据,然后才能计算,计算完成后再将结果打印出来。7/23/20234第二章进程管理程序的顺序执行如图I1P1O1I2P2O2作业1作业2在计算机系统中只有一个程序在运行,这个程序独占系统中所有资源,其执行不受外界影响。一道程序执行完后另一道才能开始。程序的顺序执行7/23/20235第二章进程管理程序的顺序执行一个程序的多条语句的顺序执行:S1:a:=x+yS2:b:=a-5S3:c:=b+1S1S2S37/23/20236第二章进程管理程序顺序执行的特点顺序性:一个程序开始执行必须要等到前一个程序已执行完成。封闭性:程序一旦开始执行,其计算结果不受外界因素影响。可再现性:程序的结果与它的执行速度无关(即与时间无关),只要给定相同的输入,一定会得到相同的结果。7/23/20237第二章进程管理多道程序系统中程序执行环境的变化计算机能够同时处理多个具有独立功能的程序(批处理系统,分时系统、实时系统、网络与分布式系统)。这样的执行环境具有三个特点:

独立性:每道程序都是逻辑上独立的,之间不存在制约关系。

随机性:程序和数据的输入与开始执行时间都是随机的。这种随机性形成了操作系统必须同时处理多道程序的客观要求。

资源共享硬件资源:CPU、输入输出设备,存储器软件资源:各种例行程序、各种共享的数据多道程序环境下执行程序的道数>计算机系统中CPU的个数单CPU中,则有N-1道程序处在等待CPU的状态输入输出设备有限将导致这些设备被共享、内存有限将导致内存被共享7/23/20238第二章进程管理程序的并发执行I1P1O1I2P2O2I3P3O3所谓程序的并发执行是指:若干个程序同时在系统中执行,这些程序的执行在时间上是重叠的,一个程序的执行尚未结束,另一个程序的执行已经开始。

7/23/20239第二章进程管理程序的并发执行一个程序的多条语句的并发执行:S1:a:=x+2S2:b:=y+5S3:c:=a+bS4:d:=c+6S1S3S4S27/23/202310第二章进程管理程序并发执行的特点

间断性

“走走停停”,一个程序可能走到中途停下来,失去原有的时序关系

失去程序的封闭性

多个程序共享系统中的资源,这些资源的状态将由多个程序来改变。如:一个程序写到存储器中的数据可能被另一个程序修改,失去原有的不变特征。

不可再现性失去封闭性→失去可再现性;外界环境在程序的两次执行期间发生变化,失去原有的可重复特征。7/23/202311第二章进程管理abefabeftopabeftop例:设有堆栈S,栈指针top,栈中存放内存中相应数据块地址,设有两个程序段getaddr(top)和reladdr(blk),其中getaddr(top)从给定的top所指栈中取出相应的内存数据块地址,而reladdr(blk)则将内存数据块地址blk放入堆栈S中。Getaddr接着执行Reladdr先执行top执行top=top+1后中断7/23/202312第二章进程管理程序并发执行的特点例:程序A、B,共享变量N,程序A,只有一个语句N:=N+1;程序B由两个语句Print(N),N=0组成。两个程序以不同速度运行,可能出现三种情况:N:=N+1在Print(N)和N=0之前,此时N值分为N+1,N+1,0N:=N+1在Print(N)和N=0之后,此时N值分为N,0,1N:=N+1在Print(N)和N=0之间,此时N值分为N,N+1,0问题:并发与并行的区别是什么?7/23/202313第二章进程管理并行与并发的概念差别

并行(Parallel)同一时刻,两个事物均处于活动状态并发(Concurrency)宏观上存在并行特征,微观上存在顺序性同一时刻,只有一个事物处于活动状态7/23/202314第二章进程管理并发所带来的效率提升7/23/202315第二章进程管理并发所带来的效率提升顺序执行模式下的系统工作效率系统总运行时间:80CPU使用效率:CPU占用时间/总时间=40/80=50%DEV1使用效率:15/80=18.75%DEV2使用效率:25/80=31.25%并发执行模式下的系统工作效率系统总运行时间:45CPU使用效率:40/45=89%DEV1使用效率:15/45=33%DEV2使用效率:25/45=55.6%7/23/202316第二章进程管理进程的引入并发执行的各程序段由于同时存在于主存中,共享软硬件资源,造成其执行结果受执行速度影响的局面。在多道程序系统所带来的复杂环境中,程序段具有了并发、制约、动态的特性,原来的程序概念,难以刻画系统中的情况。

程序本身完全是静态的概念

程序概念也反映不了系统中的并发特性为了控制和协调各程序段执行过程中的软硬件资源共享和竞争,必须有一个描述各程序执行过程和共享资源的基本单位。(这个单位被称为进程,或任务task)

7/23/202317第二章进程管理

进程的定义

进程的概念是60年代初首先由MIT的MULTICS系统和IBM公司的TSS/360系统引入的。进程有很多各式各样的定义,如:

(1)进程是可以并发执行的计算部分(2)进程是一个独立的可以调度的活动(3)进程是一个抽象的实体,当它执行某个任务时,将要分配和释放各种资源(4)行为的规则叫程序,程序在处理机上执行的活动称为进程。(5)一个进程是一系列逐一执行的操作,而操作的确切含义则有赖于以何种详尽程度来描述进程。7/23/202318第二章进程管理

进程的定义进程是可并发执行的程序在一个数据集合上的运行过程。或是指进程实体的运行过程。7/23/202319第二章进程管理阅读菜谱准备原料烹制菜肴饭菜阅读洗衣机手册准备衣服、洗衣粉设定参数,洗衣服干净衣服程序输入运行输出程序输入运行输出分时切换洗衣进程做饭进程进程同程序的比较7/23/202320第二章进程管理进程同程序的比较程序是指令的有序集合,其本身没有任何运行的含义,是一个静态的概念。而进程是程序在处理机上的一次执行过程,它是一个动态的概念;程序可以作为一种软件资料长期存在,而进程是有一定生命期的。程序是永久的,进程是暂时的;7/23/202321第二章进程管理进程同程序的比较进程更能真实地描述并发,而程序不能;进程是由程序和数据、进程控制块三部分组成的;进程具有创建其他进程的功能,而程序没有同一程序同时运行于若干个数据集合上,它将属于若干个不同的进程。也就是说同一程序可以对应多个进程7/23/202322第二章进程管理

进程的特征结构特征:由程序段、数据段、进程控制块三部分组成;动态性:进程是程序的执行;并发性:多个进程可同存于内存中,能在一段时间内同时运行;7/23/202323第二章进程管理

进程的特征独立性:独立运行的基本单位,独立获得资源和调度的基本单位;异步性:各进程按各自独立的不可预知的速度向前推进。7/23/202324第二章进程管理进程的状态及其转换不同系统设置的进程状态数目不同进程有三种基本状态: 进程在生命期内,至少具有三种基本状态:执行状态、等待状态和就绪状态。7/23/202325第二章进程管理进程的三种基本状态就绪状态(Ready):已经得到除CPU之外的其他资源的那些进程,它们已经准备就绪,一旦得到CPU,就立即可以运行。这些进程所处的状态为就绪状态。就绪队列:常按照进程优先权的大小排列,把优先权高的进程的PCB排在队列前面。7/23/202326第二章进程管理进程的三种基本状态运行状态(Running):正在运行的进程所处的状态为运行状态。单处理机系统,任一时刻只有一个进程处于运行状态多处理机系统有多个进程处于运行状态只有处于就绪状态的进程经调度选中之后才可进入执行状态7/23/202327第二章进程管理进程的三种基本状态等待状态(Wait/Blocked):若一进程正在等待某一事件发生(如等待输入输出工作完成),这时,即使给它CPU,它也无法运行,称该进程处于等待状态、阻塞、睡眠、封锁状态。阻塞队列根据阻塞原因可以设置多个队列。7/23/202328第二章进程管理进程的状态变迁图7/23/202329第二章进程管理进程的状态转换①就绪→执行:调度②执行→等待:等待某个事件发生而睡眠③等待→就绪:因等待的事件发生而唤醒④执行→就绪:时间片用完问题1:为什么不能从等待态变为运行态呢?问题2:为什么不能从就绪态变为等待态呢?答案:阻塞进程即使被给予CPU,也无法运行。理论上这种状态转换是可行的,只是没有实际价值而被操作系统禁止对于就绪状态的进程,因没有执行,自然无法进入到阻塞状态。这种状态转换理论上不可行7/23/202330第二章进程管理五状态进程模型增加了“创建”、“终止”两种状态创建状态(New):创建一个进程要通过两个步骤:首先,为一个新进程创建PCB,并填写必要的管理信息;其次,把该进程转入就绪状态并插入就绪队列中。当一个新进程被创建时,系统已为其分配了PCB,填写了进程标识等信息,但由于该进程所必需的资源或其他信息没有获得,进程自身还未进入主存,即创建工作尚未完成,进程还不能被调度运行。引入创建状态,是为了保证进程的调度必须在创建工作完成后进行,以确保对PCB操作的完整性。同时,也增加了管理的灵活性,操作系统可以根据系统性能或主存容量的限制,推迟创建状态进程的提交。对于处于创建状态的进程,获得了其所必需的资源,以及对其PCB初始化工作完成后,进程状态便可由创建状态转入就绪状态了。

7/23/202331第二章进程管理结束状态(Exit):进程的结束也要通过两个步骤:首先等待操作系统进行善后处理,然后将其PCB清零,并将PCB空间返还系统。当一个进程到达了自然结束点,或是出现了无法克服的错误,或是被操作系统所终结,或是被其他有终止权的进程所终结,它将进入结束状态。进入结束状态的进程以后不能再执行,但在操作系统中依然保留一个纪录,其中保存状态码和一些计时统计数据,供其他进程收集。一旦其他进程完成了对结束状态进程的信息提取之后,操作系统将删除该进程。对于一个进程来说“创建状态”和“结束状态”只有一次。五状态进程模型7/23/202332第二章进程管理五状态进程模型7/23/202333第二章进程管理五状态进程模型创建新进程:创建一个新进程,以运行一个程序。可能的原因为:用户登录、OS创建以提供某项服务、批处理作业。收容(Admit,也称为提交):收容一个新进程,进入就绪状态。由于性能、内存、进程总数等原因,系统会限制并发进程总数。释放(Release):由于进程完成或失败而终止进程运行,进入结束状态;运行到结束:分为正常退出Exit和异常退出abort(执行超时或内存不够,非法指令或地址,I/O失败,被其他进程所终止)7/23/202334第二章进程管理五状态进程模型注:对于五状态进程模型,一个重要的问题是当一个事件出现时如何检查阻塞进程表中的进程状态。当进程多时,对系统性能影响很大。一种可能的作法是按等待事件类型,排成多个队列。7/23/202335第二章进程管理五状态进程模型(单队列结构)7/23/202336第二章进程管理五状态进程模型(多队列结构)7/23/202337第二章进程管理七状态进程模型针对进程的存在位置(内存或者外存),进一步增加“阻塞挂起”和“就绪挂起”两种状态这个问题的出现是由于进程优先级的引入,一些低优先级进程可能等待较长时间,从而被对换至外存。这样做的目的是:提高处理机效率:就绪进程表为空时,要提交新进程,以提高处理机效率;为运行进程提供足够内存:资源紧张时,暂停某些进程,如:CPU繁忙(或实时任务执行),内存紧张用于调试:在调试时,挂起被调试进程(从而对其地址空间进行读写)7/23/202338第二章进程管理七状态进程模型活动挂起事件发生事件发生等待事件挂起调度超时释放活动挂起7/23/202339第二章进程管理就绪状态(Ready):进程在内存且可立即进入运行状态;阻塞状态(Blocked):进程在内存并等待某事件的出现;阻塞挂起状态(Blocked,suspend):进程在外存并等待某事件的出现;就绪挂起状态(Ready,suspend):进程在外存,但只要进入内存,即可运行;注:这里只列出了意义有变化或新的状态。七状态进程模型——状态7/23/202340第二章进程管理七状态进程模型——转换挂起(Suspend):把一个进程从内存转到外存;可能有以下几种情况:阻塞到阻塞挂起:没有进程处于就绪状态或就绪进程要求更多内存资源时,会进行这种转换,以提交新进程或运行就绪进程;就绪到就绪挂起:当有高优先级阻塞(系统认为会很快就绪的)进程和低优先级就绪进程时,系统会选择挂起低优先级就绪进程;运行到就绪挂起:对抢先式分时系统,当有高优先级阻塞挂起进程因事件出现而进入就绪挂起时,系统可能会把运行进程转到就绪挂起状态;收容(Admit):收容一个新进程,进入就绪状态或就绪挂起状态。进入就绪挂起的原因是系统希望保持一个大的就绪进程表(挂起和非挂起);7/23/202341第二章进程管理七状态进程模型——转换

激活(Activate):把一个进程从外存转到内存;可能有以下几种情况:就绪挂起到就绪:没有就绪进程或就绪挂起进程优先级高于就绪进程时,会进行这种转换;阻塞挂起到阻塞:当一个进程释放足够内存时,系统会把一个高优先级阻塞挂起(系统认为会很快出现所等待的事件)进程转换为阻塞进程;事件出现(EventOccurs):进程等待的事件出现;如:操作完成、申请成功等;可能的情况有:阻塞到就绪:针对内存进程的事件出现;阻塞挂起到就绪挂起:针对外存进程的事件出现;7/23/202342第二章进程管理【思考题】1.如果系统中有N个进程,运行的进程最多几个,最少几个;就绪进程最多几个,最少几个;等待进程最多几个,最少几个?答案:运行进程最多1个,最少1个就绪进程最多N-1个,最少0个等待进程最多N-1个,最少0个7/23/202343第二章进程管理进程的描述

进程的静态描述:由三部分组成进程控制块、有关程序段和该程序段对其进行操作的数据集。1进程控制块:包含了有关进程的描述信息、控制信息以及资源信息,是进程动态特征的集中反映。

2程序段:是进程中能被进程调度程序选中,并在CPU上执行的程序代码段。3数据段:一个进程的数据段,可以是进程对应的程序加工处理的原始数据,也可以是程序执行后产生的中间或最终数据。7/23/202344第二章进程管理进程控制块(ProcessControlBlock)为了描述一个进程与其它进程以及系统资源的关系,为了刻画一个进程在各个不同时期所处的状态,人们采用了一个与进程相联系的数据结构,称为进程控制块(PCB)。7/23/202345第二章进程管理其作用是将一个不能独立运行的程序变成一个可以独立运行的基本单位,一个能与其他进程并发执行的进程。OS利用PCB来对并发执行的进程进行控制和管理的,PCB是OS感知进程存在的唯一标志。进程与PCB是一一对应的。PCB应常驻内存。进程控制块(ProcessControlBlock)7/23/202346第二章进程管理1、PCB的内容进程描述信息:进程标识符(processID),唯一,通常是一个整数进程名,通常基于可执行文件名(不唯一)用户标识符(userID):指示该进程由哪个用户拥有进程组(家族)关系:父进程标识符以及子进程标识符7/23/202347第二章进程管理1、PCB的内容进程控制信息:当前状态优先级(priority)程序的外存地址运行统计信息(执行时间、页面调度)进程间同步和通信;阻塞原因进程的队列指针进程的消息队列指针7/23/202348第二章进程管理1、PCB的内容资源管理信息1、占用内存大小及其管理用数据结构指针。2、共享程序段大小及其起始地址。3、输入、输出设备的设备号,所要传送的数据长度、缓冲区地址、缓冲区长度及所用设备的有关数据结构指针等。4、指向文件系统的指针及有关标识。CPU现场保护结构当前进程因等待某个事件而进入等待状态或因某种事件发生被终止在处理机上的执行时,为了以后该进程能在被中断处恢复执行,需要保护当前进程的CPU现场。CPU中设有专门的CPU现场保护结构,以存储退出执行时的进程现场数据。7/23/202349第二章进程管理2、PCB表组织方式PCB表:

系统把所有PCB组织在一起,并把它们放在内存的固定区域,就构成了PCB表。PCB表的大小决定了系统中最多可同时存在的进程个数,称为系统的并发度。

7/23/202350第二章进程管理链接结构相同状态的进程其PCB组成一个链表,多个状态对应多个不同的链表。就绪链表、阻塞链表7/23/202351第二章进程管理7/23/202352第二章进程管理索引结构对具有相同状态的进程,分别设置各自的PCB索引表,表明PCB在PCB表中的地址(由index指向PCB)。多个状态对应多个不同的index表:就绪索引表、阻塞索引表索引表在内存的首地址记录在内存中的一些专用单元中。7/23/202353第二章进程管理索引表就绪队列等待队列1等待队列2PCB1PCB2PCB3PCB4PCB5PCB6PCB7…PCBnPCB表7/23/202354第二章进程管理3.进程的上下文进程是在操作系统的支持下运行的,进程运行时操作系统需要为其设置相应的运行环境,如系统栈、地址映射寄存器、打开文件表、PSW与PC、通用寄存器等。在UNIXSystemⅴ中,将进程的物理实体与支持进程运行的物理环境合称为进程上下文。进程切换过程就是进程上下文切换的过程。由于进程上下文涉及的内容较多,进程切换一般需要一定的时间才能完成,这是系统为实现并发而付出的额外代价,属于系统开销的一部分。7/23/202355第二章进程管理2.2进程控制

进程控制就是对系统中的所有进程实施管理(创建一个新进程、终止一个已完成的进程,或终止一个因出现某事件而使其无法运行下去的进程,还负责进程运行中状态的转换),进程控制一般由OS的内核来实现。7/23/202356第二章进程管理原语

所谓原语是指系统态下执行的某些具有特定功能的程序段。分为两类:

机器指令级的:执行期间不允许中断功能级的:作为原语的程序段不允许并发执行常用的进程控制原语:

创建原语Create

终止原语Destroy

阻塞原语Block、唤醒原语Wakeup

挂起原语Suspend、激活原语Active

7/23/202357第二章进程管理进程图用来描述进程家族关系的有向树。ABCDMEIJHGFLK

子进程可以继承父进程的所有资源,当子进程被撤消时,应将从父进程那里获得的资源归还给父进程。撤消父进程时也必须同时撤消其所有的子进程。UNIX称进程树里的所有进程为一个进程组,进程组中的进程分布在不同的层次上,从而形成一个层次架构。Windows没有进程组的概念,所有进程均地位平等。7/23/202358第二章进程管理引起创建进程的事件1用户登录:在分时系统中,用户在终端键入登录命令后,若是合法用户,系统建立一个进程,并插入就绪队列。2作业调度:批处理系统中,作业调度程序调度到某个作业以后,就把这个作业装入内存,并分配必要的资源,创建进程,插入就绪队列。3提供服务:运行中的用户向系统提出请求后,系统专门建立一个进程为用户服务。(打印请求)由操作系统核心(系统程序模块)创建4应用请求:应用进程的需要,由它自己创建一个新进程,使新进程以并发运行方式完成特定任务。(输入数据并将处理结果输出到表格上)由父进程创建

进程创建7/23/202359第二章进程管理进程创建申请空白PCB为新进程分配资源如内存初始化进程控制块将新进程插入就绪队列

7/23/202360第二章进程管理入口查PCB链表有空PCB?PCB(i)入进程家族或进程链PCB(i)入就绪队列将有关参数填入PCB(i)相应项取空表PCB(i)返回创建失败无有创建原语流程图7/23/202361第二章进程管理进程撤消(终止)引起进程终止的事件1正常结束:计算机系统中,都有一个表示进程已经运行完成的指示。2异常结束

越界错误、保护错、特权指令错、非法指令错、运行超时、等待超时算术运算错、I/O故障3外界干预操作员或操作系统干预父进程请求父进程终止7/23/202362第二章进程管理进程撤消过程根据被终止进程的标识符,从PCB集合中检索出该进程的PCB,从中读出该进程的状态若被终止进程处于执行状态,应立即终止执行,并置调度标志为真(用于指示该进程被终止时应重新调度其它进程),然后再选择一个进程,分配处理机给它。如果该进程还有子孙进程,则结束该进程所有子孙进程的执行,以防它们成不可控进程;将进程所拥有的资源交给父进程或系统进程;将被终止进程(PCB)从所在队列中移出,等待其他进程来收集信息。7/23/202363第二章进程管理查进程链表或进程家族入口返回有此PCB吗?该PCB有子进程吗?释放该进程所占有的资源释放该PCB结构本身出错处理有无有撤消原语流程图7/23/202364第二章进程管理阻塞:当一个进程所期待的某一事件尚未出现时,该进程调用阻塞原语将自己阻塞。进程阻塞是进程的自身的一种主动行为。唤醒:处于阻塞状态的进程是绝不可能叫醒它自己的,它必须由它的合作进程用唤醒原语唤醒它。进程的阻塞与唤醒7/23/202365第二章进程管理进程的阻塞与唤醒引起进程阻塞和唤醒的事件1请求系统服务正在执行的程序请求操作系统服务,但是由于某种原因操作系统没有立即满足该进程的要求,该进程只能转变为阻塞状态来等待。2启动某操作当进程启动某种操作后,如果该进程必须在该操作完成之后才能继续执行,所以必须先使进程阻塞。3新数据尚未到达4无新工作可做系统往往设置一些具有某特定功能的系统进程,每当这种进程完成任务以后便把自己阻塞起来等待新任务的到来。(发送进程)7/23/202366第二章进程管理阻塞过程:停止运行转变状态插入相应事件队列重新调度唤醒过程:移出阻塞队列转变状态插入就绪队列可能重新调度进程的阻塞与唤醒7/23/202367第二章进程管理入口保存当前进程的CPU现场置该进程的状态被阻塞进程入等待队列转进程调度入口从等待队列中摘下被唤醒进程将被唤醒进程置为就绪状态将被唤醒进程送入就绪队列转进程调度或返回阻塞原语唤醒原语阻塞原语和唤醒原语7/23/202368第二章进程管理进程的挂起与激活挂起:当出现了引起进程挂起的事件时,系统利用挂起原语将指定进程或处于阻塞状态的进程挂起。

激活:当发生激活进程的事件时,系统利用激活原语将指定进程激活。7/23/202369第二章进程管理进程的挂起与激活挂起过程:检查/转换状态复制PCB到指定内存挂起运行时,重新调度激活过程:检查/转换状态变活动就绪时,可能重新调度7/23/202370第二章进程管理2.3进程同步进程同步的主要任务是使并发执行的诸进程之间能有效的共享资源和相互合作,从而使程序的执行具有可再现性。2.3.1进程同步的基本概念2.3.2信号量机制2.3.3信号量的应用7/23/202371第二章进程管理并发系统中诸进程由于资源共享、进程合作,而产生进程之间的相互制约;又因共享资源的方式不同,而导致两种不同的制约关系:间接制约关系(进程互斥)由于共享公有资源而造成的对并发进程执行速度的间接制约。(系统资源:如A、B两进程竞争打印机)

间接:指各并发进程的速度受公有资源制约。直接制约关系(进程同步)由于并发进程互相共享对方的私有资源所引起的直接制约。(进程间合作:如输入进程、计算进程和打印进程)2.3.1进程同步的基本概念7/23/202372第二章进程管理

相似处:进程的互斥实际上是进程同步的一种特殊情况;进程的互斥和同步统称为进程同步。

差别:进程互斥是进程间竞争共享资源的使用权,这种竞争没有固定的必然联系,哪个进程竞争到使用权就归那个进程使用,直到不需要使用时再归还;而进程同步则是涉及共享资源的并发进程间有一种必然的联系,当进程必须同步时,即使无进程在使用共享资源时,那么尚未得到同步消息的进程也不能去使用这个资源。进程同步和互斥间的关系7/23/202373第二章进程管理

临界资源(criticalresource):一次仅允许一个进程访问的资源。如:进程AB共享一台打印机,若让它们交替使用则得到的结果肯定不是我们希望的。临界资源可能是硬件,也可能是软件:变量,数据,表格,队列等。并发进程对临界资源的访问必须作某种限制,否则就可能出与时间有关的错误,如:联网售票。

2.3.1进程同步的基本概念7/23/202374第二章进程管理与时间有关的错误:一飞机订票系统,两个终端,运行A1、A2进程

A1:A2:

......

Read(x);Read(x);

ifx>=mthenifx>=mthen

x:=x-m;x:=x-m;(售出m张机票)

write(x);write(x);

......7/23/202375第二章进程管理时间T1T2T3T4T5结果X的值10010010808080A1Sell(90)Read(x)x=x-90购票成功A2Sell(20)Read(x)x=x-20购票成功7/23/202376第二章进程管理实例:生产者-消费者问题一种同步问题的抽象描述计算机系统中的每个进程都可以消费(使用)或生产(释放)某类资源。这些资源可以是硬件资源,也可以是软件资源。当某一进程使用某一资源时,可以看作是消费,称该进程为消费者。而当某一进程释放某一资源时,它就相当于生产者。7/23/202377第二章进程管理实例:生产者-消费者问题一种同步问题的抽象描述生产者-消费者之间设置一个具有n个缓冲区的缓冲池,生产者进程将它所生产的产品放入一个缓冲区;消费者进程可从一个缓冲区中取走产品去消费。不允许消费者进程到一个空缓冲区去取产品;不允许生产者进程向一个已装满产品且尚未取走的缓冲区投放产品。7/23/202378第二章进程管理实例:生产者-消费者问题问题分析利用一个数组表示具有n个缓冲区的循环缓冲池;用输入指针in指示下一个可投放产品的缓冲区,每当生产者进程生产并投放一个产品,输入指针加1(in:=(in+1)modn);用指针out指示下一个可从中获取产品的缓冲区,每当消费者进程取出一个产品,输出指针加1(out:=(out+1)modn);7/23/202379第二章进程管理实例:生产者-消费者问题……1234n-1ninout7/23/202380第二章进程管理实例:生产者-消费者问题问题分析(in+1)modn=out缓冲池满;in=out缓冲池空;counter表示缓冲池内产品的数量。在生产者进程中使用一局部变量nextp,用于暂时存放每次刚生产出来的产品;使用一个局部变量nextc用于存放每次要消费的产品。7/23/202381第二章进程管理实例:生产者-消费者问题producer:repeat…produceaniteminnextp;…whilecounter=ndono-op;buffer[in]:=nextp;in:=(in+1)modn;

counter:=counter+1;untilfalse;consumer:repeatwhilecounter=0dono-opnextc:=buffer[out];out:=(out+1)modn;

counter:=counter-1;consumertheiteminnextc;untilfalse;两者并发执行会出现错误!7/23/202382第二章进程管理实例:生产者-消费者问题register1:=counterregister1:=register1+1counter:=register1register2:=counterregister2:=register2-1counter:=register21

32

45

6应把counter作为临界资源处理!假设counter=5,则按上述次序执行结果是4—程序的执行失去了可再现性7/23/202383第二章进程管理2.3.1进程同步的基本概念临界区(criticalsection):在每个程序中,访问临界资源的那段程序。若在一组并发进程的各自临界区中都使用了相同的共享变量,则称这组临界区为相关临界区。若能保证诸进程互斥地进入自己的临界区,便可实现诸进程对临界资源的互斥访问.

repeatentrysectioncriticalsectionexitsectionremaindersectionUntilfalse7/23/202384第二章进程管理2.3.1进程同步的基本概念注意:临界区是对某一临界资源而言的,对于不同临界资源的临界区,它们之间不存在互斥。

如程序段A、B有关于变量X的临界区,而C、D有关于变量Y的临界区,那么,A、B之间需要互斥执行,C、D之间也要互斥执行,而A与C、B与D之间不用互斥执行。

。7/23/202385第二章进程管理“金鱼问题”zuo和you两人合住一套公寓,共同养了一条金鱼,该金鱼每天进食一顿。两人想把金鱼养活,一天只能喂一次,如果一天内两人都喂了鱼,鱼就胀死。如果一天内两人都没有喂鱼,鱼就饿死。7/23/202386第二章进程管理Solution#0没有同步zuo:you:if(nofeed){if(nofeed){feedfishfeedfish}}7/23/202387第二章进程管理Problemwithsolution#0zuo:you:13:00观察鱼(没有喂)13:05观察鱼(没有喂)13:10喂鱼13:25喂鱼

鱼胀死了!7/23/202388第二章进程管理临界区Solution0#中临界区为:if(nofeed),feedfish要防止鱼胀死,zuo和you就不能同时进入临界区。要达到这点,就需要某种协调手段。协调的目的就是在任何时刻只能有一个人在临界区里——互斥。7/23/202389第二章进程管理正确互斥需要满足四个条件(1)空闲让进:当无进程处于临界区时,应允许一个请求进入临界区的进程立即进入自己的临界区,以有效利用临界资源。(2)忙则等待:当已有进程进入临界区时,其他试图进入临界区的进程必须等待,以保证对临界资源的互斥访问。(3)让权等待:当进程不能进入自己的临界区时,应立即释放处理机,以免进程陷入“忙等”状态。(4)有限等待:对要求访问临界资源的进程,应保证在有限时间内能进入自己的临界区,以免陷入“死等”状态。7/23/202390第二章进程管理Solution#1思想:zuo和you商定,每个人在察看鱼的状态之前留下字条,告诉对方自己将检查鱼缸并在需要时喂鱼。zuo:you:if(nonote){if(nonote){leavenoteleavenoteif(nofeed){if(nofeed){feedfishfeedfish}}removenoteremovenote}}7/23/202391第二章进程管理Problemwithsolution#1zuo:you:13:00检查发现没有字条13:05检查发现没有字条13:10留字条13:25留字条13:50观察鱼(没有喂)14:05观察鱼(没有喂)14:10喂鱼14:25喂鱼

鱼胀死了!但鱼胀死的概率降低了!(zuo和you严格交叉执行时,才可能发生鱼胀死现象)7/23/202392第二章进程管理Solution#2思想:上述程序不解决问题的原因是因为先检查有没有字条,然后留字条。这使得检查字条和留字条之间存在空挡。为此修改一下顺序,先留字条,再检查有没有对方字条,若没有,就喂鱼,喂完把字条拿掉。但要区分条子是谁的。zuo:you:leavenotezuoleavenoteyouif(nonoteyou){if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}}}removenotezuoremovenoteyou鱼不会胀死:因无论按怎样顺序穿插,总有一个人的留条子在另一人的检查字条前执行,从而防止两人同时进入临界区。7/23/202393第二章进程管理Problemwithsolution#2zuo:you:13:10留字条you13:25留字条zuo13:50检查字条you(存在)14:05检查字条zuo(存在)14:10拿掉字条you14:25拿掉字条zuo

没人喂鱼,鱼饿死了!7/23/202394第二章进程管理Solution#3思想:鱼饿死是因为没人进入临界区。解决的方法是让某个人等着,直到确认有人喂了鱼才离去。zuo:you:leavenotezuoleavenoteyouwhile(noteyou){donothing}if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}}removenotezuoremovenoteyou7/23/202395第二章进程管理Solution#3鱼不会胀死,因为使用的方法包括了solution#2的同步方式;上述程序在两个人都留字条的情况下,zuo不会离开,而是一直循环等待直到对方删除字条后,再检查鱼有没有喂,并在没有喂鱼的情况下喂鱼,因此鱼也不会饿死。存在的问题:程序不对称,造成程序编写困难。浪费。Zuo的循环等待是一种很大的浪费。循环等待还可能造成cpu调度的优先级倒挂,即高优先级的进程等待低优先级的进程。7/23/202396第二章进程管理进一步改进问题:对哪个方案进行改进,solution#3?solution#2?还是solution#1?Solution#1不满足条件是因为检查字条和留字条中间存在空挡,造成字条作用的丧失,能否将这两步骤并为一个步骤,或者变成原子操作,使其中间不留空挡?解决的办法是提高抽象层次从保护鱼和鱼缸的层次提高到保护放置鱼缸的房间的层次。即设计一种同步措施,使得在任何时候只能有一个人进入放置鱼缸的房间。7/23/202397第二章进程管理锁zuo:you:lock()lock()if(nofeed){if(nofeed){feedfishfeedfish}}unlock()unlock()问题:若zuo正在喂鱼,you只能等待(等待锁变为打开状态)。若zuo喂鱼的动作很慢,you等待的时间就会很长,而这种繁忙等待将造成浪费,也降低系统效率。7/23/202398第二章进程管理减少锁的繁忙等待时间zuo:you:lock()lock()if(nonoteyou)if(nonotezuo)leavenotezuoleavenoteyouunlock()unlock()if(nonoteyou){if(nonotezuo){if(nofeed){if(nofeed){feedfishfeedfish}}removenoteremovenote}}在锁上的繁忙等待时间已经很少,但还是有等待7/23/202399第二章进程管理睡觉与叫醒思想:如果锁被对方持有,不用等待锁变为打开状态,而是睡觉去,锁打开后再来把你叫醒。producer:repeatproduceaniteminnextp;ifcounter=nsleep();buffer[in]:=nextp;in:=(in+1)modn;counter:=counter+1;ifcounter=1wakeup(consumer)untilfalse;consumer:repeatifcounter=0sleep();nextc:=buffer[out];out:=(out+1)modn;

counter:=counter-1;ifcounter=n-1wakeup(profucer)consumertheiteminnextc;untilfalse;7/23/2023100第二章进程管理睡觉与叫醒问题一:生产者和消费者共用变量counter,两进程并发执行时可能发生与时间有关的错误。解决办法:在对counter操作的前后加上lock和unlock即可防止生产者和消费者同时访问counter的情况出现。7/23/2023101第二章进程管理睡觉与叫醒问题二:可能出现生产者和消费者同时睡觉,从而无法相互叫醒继续往前推进。(假定消费者先来,counter=0,于是去睡觉,但在执行sleep语句前cpu发生切换,生产者开始运行,它生产一件产品后,给counter加1,发现counter结果为1,因此发出叫醒消费者的信号,但这时消费者还没睡,所以信号没有任何效果。生产者一直运行直到缓冲区满后也去睡觉。这时cpu切换到消费者,而消费者执行的第一个操作就是sleep,至此生产者与消费者都进入睡眠状态)解决办法:不让二者同时睡觉。造成二者同时睡觉的原因是生产者发出的叫醒信号丢失(因消费者此时还未睡)。若用某种方法将发出的信号累积起来,而不是丢掉,问题就会得到解决。即在消费者获得cpu执行sleep语句后,生产者在这之前发送的叫醒信号还保留着,因此消费者将马上获得这个信号而醒过来。----能够将信号累积起来的操作系统原语就是信号量。7/23/2023102第二章进程管理1965年,由荷兰学者Dijkstra提出(所以P、V分别是荷兰语的test(proberen)和increment(verhogen))。一种卓有成效的进程同步机制。经历整型信号量、记录型信号量,发展为“信号量集”机制。P、V操作是原语。2.3.2信号量机制7/23/2023103第二章进程管理1、整型信号量把整型信号量定义为一个表示资源数目的整型量,仅由两个标准原子操作wait(S)(P操作)和signal(S)(V操作)来访问。wait(S):whileS≤0dono-op;S:=S-1;signal(S):S:=S+1;注意:两种操作皆为原语操作。7/23/2023104第二章进程管理2、记录型信号量记录型信号量机制采取“让权等待”策略,避免了整型信号量出现的“忙等”现象。实现时需要一个用于代表资源数目的整型变量value,一个用于链接所有等待进程的进程链表queue。7/23/2023105第二章进程管理2、记录型信号量信号量是一个数据结构,定义如下:

structsemaphore{ intvalue; pointer_PCBqueue;//进程链表}信号量说明:semaphores;7/23/2023106第二章进程管理P操作(wait(s))—申请资源P(s){s.value=s.value-1;if(s.value<0){

该进程状态置为等待状态将该进程的PCB插入相应的等待队列末尾s.queue;}}S.value初值表示系统中某类资源的数目;当S.value<0时,表示该资源已分配完毕,其绝对值表示在该信号量链表中已阻塞进程的数目7/23/2023107第二章进程管理V操作(signal(s))—释放资源V(s){s.value=s.value+1;if(s.value<=0){唤醒相应等待队列s.queue中等待的一个进程改变其状态为就绪状态并将其插入就绪队列}}7/23/2023108第二章进程管理3、AND型信号量例如:两个进程A、B要求访问共享数据D、E。

为D、E分别设置用于互斥的信号量Dmutex、Emutex,初值为1。

processA:processB:wait(Dmutex);wait(Emutex);wait(Emutex);wait(Dmutex);可能出现死等现象7/23/2023109第二章进程管理3、AND型信号量AND同步机制的基本思想是:将进程在整个运行过程中需要的所有资源,一次性全部地分配给进程,待进程使用完后再一起释放。只要尚有一个资源未分配给进程,其它所有可能为之分配的资源,也不分配给他。实现时在wait操作中,增加一个“AND”条件,故称AND同步,或同时wait操作(Swait)。7/23/2023110第二章进程管理3、AND型信号量Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si-1;endforelse当发现有Si<1时,该进程状态置为等待状态endifSsignal(S1,S2,…,Sn)fori:=1tondoSi:=Si+1;

将与Si相关的所有 等待进程移出到就 绪队列endfor7/23/2023111第二章进程管理Swait(S1,S2,…,Sn) //P原语;{if(S1>=1&&S2>=1&&…&&Sn>=1){ //满足资源要求时的处理;for(i=1;i<=n;++i)--Si;}else{ //某些资源不够时的处理;

调用进程进入第一个小于1信号量的等待队列Sj.queue;

阻塞调用进程;}}7/23/2023112第二章进程管理Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //释放占用的资源;for(在Si.queue中等待的每一个进程P){从等待队列Si.queue中取出进程P;if(判断进程P是否通过Swait中的测试)//重新判断{进程P进入就绪队列;break;}else进程P进入某等待队列;

}}}7/23/2023113第二章进程管理4、信号量集一次需要N个某类临界资源时,就要进行N次P操作——低效又可能死锁。信号量集是指同时需要多种资源、每种占用的数目不同、且可分配的资源还存在一个临界值时的信号量处理。一般信号量集的基本思路就是在AND型信号量的基础上进行扩充,在一次原语操作中完成所有的资源申请。7/23/2023114第二章进程管理进程对信号量Si的测试值为ti(表示信号量的判断条件,要求Si>=ti;即当资源数量低于ti时,便不予分配)占用值为di(表示资源的申请量,即Si=Si-di)对应的P、V原语格式为:Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);4、信号量集7/23/2023115第二章进程管理4、信号量集Swait(S1,t1,d1,…,Sn,tn,dn)ifS1≥t1and…andSn≥tnthenfori:=1tondoSi:=Si-di;endforelse

当发现有Si<ti时,该进程状态置为等待状态endif7/23/2023116第二章进程管理4、信号量集Ssignal(S1,d1,…,Sn,dn)fori:=1tondoSi:=Si+di;将与Si相关的所有等待进程移出 到就绪队列

endfor7/23/2023117第二章进程管理一般“信号量集”可以用于各种情况的资源分配和释放,几种特殊情况:Swait(S,d,d)表示每次申请d个资源,当少于d个时,便不分配Swait(S,1,1)表示记录型信号量或互斥信号量Swait(S,1,0)可作为一个可控开关(当S1时,允许多个进程进入特定区域;当S=0时,禁止任何进程进入该特定区域)一般“信号量集”未必成对使用。如:一起申请,但不一起释放!7/23/2023118第二章进程管理1、利用信号量实现进程互斥2、利用信号量实现前趋关系2.3.3信号量的应用7/23/2023119第二章进程管理只须为临界资源设置一互斥信号量mutex,设其初始值为1,然后将各进程访问该资源的临界区CS置于wait(mutex)和signal(mutex)操作之间即可。1、利用信号量实现进程互斥7/23/2023120第二章进程管理用P、V操作解决进程间互斥问题P(mutex)V(mutex)P1P2P3临界区P(mutex)P(mutex)V(mutex)V(mutex)7/23/2023121第二章进程管理Varmutex:semaphore:=1beginparbeginprocess1:beginrepeat

wait(mutex);criticalsection

signal(mutex);remaindersectionuntilfalse;endProcess2:begin

repeat

wait(mutex);criticalsection

signal(mutex);remaindersectionuntilfalse;endparend

7/23/2023122第二章进程管理若干个进程为了完成一个共同任务而并发执行,在这些进程中,有些进程之间有次序的要求,有些进程之间没有次序的要求,为了描述方便,可以用一个图来表示进程集合的执行次序。2、利用信号量实现前趋关系7/23/2023123第二章进程管理2、利用信号量实现前趋关系7/23/2023124第二章进程管理方法1:在需要顺序执行的进程(P1→P2)间设置一个两个进程的共有信号量S,供两个进程共享,并赋初值为0。在进程P1中,运行完成,signal(S)在进程P2中,wait(S),运行2、利用信号量实现前趋关系7/23/2023125第二章进程管理方法2:在需要顺序执行的进程(P1→P2)间设置一个同步信号量f,将用来标识前面进程是否执行完成,该信号量如果没有遇到同步则一直沿用下去,赋初值为0。在进程P1中,运行完成,signal(f)在进程P2中,wait(f),运行2、利用信号量实现前趋关系7/23/2023126第二章进程管理不同之处方法1在图中存在n个进程,则需要设置n-x个公用信号量,x表示起始进程个数;方法2在图中存在n个进程,则需要设置n-x个同步信号量,x取决于终点进程的数目。2、利用信号量实现前趋关系7/23/2023127第二章进程管理例:试用信号量实现这三个进程的同步。方法1:设有两个共用信号量SB、SC,初值均为0。Pa:Pb:Pc:…P(SB);P(SC)

V(SB);……V(SC);2、利用信号量实现前趋关系7/23/2023128第二章进程管理方法2:设有一个同步信号量SA,初值均为0。Pa:Pb:Pc:…P(SA);P(SA)

V(SA);……V(SA);2、利用信号量实现前趋关系7/23/2023129第二章进程管理【思考题1】试用信号量实现这三个进程的同步。7/23/2023130第二章进程管理解设有一个信号量S3,初值均为0。P1:P2:P3:……P(S3)

V(S3);V(S3);P(S3)…7/23/2023131第二章进程管理【思考题2】试用信号量实现这6个进程的同步。7/23/2023132第二章进程管理解设有5个信号量S2、S3、S4、S5、S6,初值均为0P1:P2:P3:…P(S2);P(S3)

V(S2);……V(S3);V(S4);V(S6);V(S5)P4:P5:P6:P(S4);P(S5);P(S6);…P(S5);P(S6);……V(S5);V(S6);7/23/2023133第二章进程管理2.4经典的进程同步问题2.4.1生产者/消费者问题2.4.2哲学家进餐问题2.4.3读者/写者问题2.4.4理发师问题7/23/2023134第二章进程管理2.4.1生产者/消费者问题生产者消费者问题是一种同步问题的抽象描述。计算机系统中的每个进程都可以消费(使用)或生产(释放)某类资源。这些资源可以是硬件资源,也可以是软件资源。当某一进程使用某一资源时,可以看作是消费,称该进程为消费者。而当某一进程释放某一资源时,它就相当于生产者。7/23/2023135第二章进程管理问题描述通过一个有界缓冲区可以把一群生产者p1,p2…,pm,和一群消费者Q1,Q2,…,Qn联系起来。如图只要缓冲区未满,生产者就可以把产品送入缓冲区;只要缓冲区未空,消费者就可以从缓冲区中取走物品。7/23/2023136第二章进程管理图7/23/2023137第二章进程管理问题分析由于在此问题中有M个生产者和N个消费者,它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源,必须互斥使用,所以还需要设置一个互斥信号量mutex,其初值为1。7/23/2023138第二章进程管理问题分析为解决生产者消费者问题,可以设两个同步(资源)信号量:一个代表空缓冲区的数目,用empty表示,初值为有界缓冲区的大小n;一个代表已用缓冲区的数目,用full表示,初值为0。7/23/20

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论