第6章-进程管理与作业管理2.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二层,*,*,*,进程的安全性,1,死锁概述,操作系统中的死锁基于如下假定：,任意一个进程要求资源的最大数量不超过系统能提供的最大量；,如果一个进程在执行中提出的资源要求能够得到满足，那么它一定能在有限时间内结束；,一个资源在任何时刻最多只为一个进程所占有；,一个进程申请资源，只在资源得不到满足时才处于等待状态；,一个进程结束时释放它所占有的全部资源；,系统具有有限个进程和资源。,2,死锁,在多道程序系统中，若干个进程彼此相互等待对方拥有且不会释放的资源，从而形成各进程都想得到资源而又都得不到资源，因而不能继续向前推进的,僵局,状态，就叫死锁。,3,例,1,：进程推进顺序不当产生死锁,设系统有打印机、读卡机各一台，被进程,P,和,Q,共享。两个进程并发执行，按下列次序请求和释放资源：,进程,P,进程,Q,请求读卡机请求打印机,请求打印机 请求读卡机,释放读卡机 释放读卡机,释放打印机 释放打印机,4,例,2 PV,操作使用不当产生死锁,进程,Q1,进程,Q2,P(S1);P(s2);,P(s2);P(s1);,使用,r1,和,r2;,使用,r1,和,r2,V(S1);V(s2);,V(S2);V(S1);,5,资源的概念,资源的分类,a,、,可再用资源,/,消耗性资源,可再用资源：可供进程重复使用,如：硬件资源、软件资源,消耗性资源：由某个进程所产生，只为另一个进程使用一次，或经短暂时间后便不再使用的资源。,如：时钟中断、同步信号、消息等,b,、,共享,/,独享资源：例如,CPU,、,主存,/,打印机,c,、,可剥夺,/,不可剥夺资源,6,产生死锁的必要条件,互斥：,对于独占资源，每个资源每次只能给一个进程使用，进程申请到了资源后占为己有，则排斥其他进程享受该资源,非剥夺：,正在使用的资源不可剥夺，进程获得的资源尚未使用完毕之前，只能由占有者自己释放，不能被其他进程强行占用,占有且等待：,进程因未分配到新的资源而受阻，但对已占有的资源又“死抱住不放”,循环等待：,存在进程的循环等待链，前一进程占有的资源是后一进程所需求的资源，结果就形成了循环等待的僵持局面,说明：发生死锁，则四个条件一定同时成立；破坏其中一个，死锁就可以阻止。,7,资源分配图,约定,PiRj,为请求边，表示进程,Pi,申请资源类,Rj,中的一个资源得不到满足而处于等待,Rj,类资源的状态，该有向边从进程开始指到方框的边缘，表示进程,Pi,申请,Rj,类中的一个资源。,RjPi,为分配边，表示,Rj,类中的一个资源已被进程,Pi,占用，由于已把一个具体的资源分给了进程,Pi,，,故该有向边从方框内的某个圆点出发指向进程。,8,资源分配图的一个例子,R1,R2,P1,P2,P3,R3,9,资源分配图的另一个例子,R1,R2,P1,P2,P3,P4,10,资源分配图死锁状态,(1),如果进程,-,资源分配图中无环路，则此时系统没有发生死锁。,(2),如果进程,-,资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进程便为死锁进程。,(3),如果进程,-,资源分配图中有环路，且涉及的资源类中有多个资源，则环路的存在只是产生死锁的必要条件而不是充分条件。,11,处理死锁的基本方法,死锁的预防,死锁的避免,死锁的检测,死锁的解除（）,12,死锁的预防,死锁预防策略是试图设计一种系统，在这样的系统中排除发生死锁的可能性。,可以把死锁预防方法看作两类,间接的死锁预防方法,：,即防止前三个必要条件中任何一个的发生,直接的死锁预防方法,：,即防止循环等待的发生,13,死锁的预防,(1),破坏互斥条件,使资源可同时访问而不是互斥使用，是个简单的办法，磁盘可用这种办法管理,但有许多资源往往是不能同时访问，所以这种做法许多场合行不通。,所以一般来说，,4,个条件中的互斥条件不可能禁止。,如果访问资源要求互斥，操作系统必须支持。某些资源，如文件，可能允许多个读访问，但只允许互斥的写访问。即使在这种情况下，如果有多个进程要求写权限，也可能发生死锁。,14,死锁的预防,(2),剥夺式分配,采用剥夺式调度方法可破坏第二个条件，但只适用于对主存资源和处理器资源的分配；,如果占有某些资源的一个进程，其进一步的资源请求被拒绝，则该进程必须释放它最初的资源；,如果一个进程请求当前被另一个进程占有的一个资源，操作系统可以剥夺第二个进程，要求它释放资源；,只有当应用于资源的状态可以很容易地保存并在以后恢复的情况下,(,像处理器一样,),，这种方法才是实用的,15,死锁的预防,(3),按序分配,采用资源顺序使用法，,破坏环路条件,;,循环等待条件可以通过定义资源类型线性顺序来预防。如果一个进程已经分配到了,R,类型资源，它接下来请求的资源只能是那些排在,R,类型之后的资源类型。,和占有等待预防一样，循环等待预防可能是低效的，它使进程执行速度变慢，并且可能没有必要地拒绝资源访问。,16,死锁的预防,(4),系统分配,静态预分配,破坏部分分配条件,：一个进程必须在执行前就申请它所要的全部资源，并且直到它所要的资源都得到满足后才开始执行。,缺点：,a,、,资源浪费,b,、,作业延迟,17,死锁的避免,解决死锁问题的另一种方法是死锁避免。,在死锁预防中，约束资源请求，至少防止,4,个死锁条件中的一个发生。这可以通过防止发生三个必要策略条件中的一个直接完成，也可以通过防止循环等待间接完成，但这都会导致低效的资源使用和低效的进程执行。,死锁避免则相反，它允许三个必要条件，但通过明智的选择，确保永远不会到达死锁点，因此避免比预防允许更多的并发。,18,预防和避免的比较,19,死锁的避免,死锁避免的优点是它不需要死锁预防中的剥夺和重新运行进程，并且比死锁预防的限制少，但在使用中也有许多限制。,必须事先声明每个进程请求的最大资源；,考虑的进程必须是无关的，也就是说，它们执行的顺序必须没有任何同步要求的限制；,分配的资源数目必须是固定的；,在占有资源时，进程不能退出。,20,避免死锁的算法,银行家算法,银行家算法,银行家拥有一笔周转资金。,客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款。,银行家应谨慎的贷款，防止出现坏帐。,用银行家算法避免死锁,操作系统,(,银行家,),操作系统管理的资源,(,周转资金,),进程,(,要求贷款的客户,),21,银行家算法的,数据结构,Available:,可利用的资源量；,Need,i,：,进程,P,i,尚需要的各类资源数；,Allocation,：,已经分配给某进程的资源数；,Request,i,：,进程,P,i,的请求量。,(1),若,Request,i,Need,i,，,转向步骤,(2),，否则出错；,(2),若,Request,i,Available,，,转向步骤,(3),，否则表示系统没有足够的资源，进程,P,i,必须等待；,(3),系统试探分配资源，修改以下数据：,Available=Available,Request,i,Allocation=Allocation+,Request,i,Need,i,=,Need,i,-,Request,i,(4),执行安全检查：系统是否处于安全状态。,若系统处于安全状态，才正式将资源分配给进程,P,i,；,若系统不安全，试探分配作废，恢复资源原态，进程,P,i,等待。,22,银行家算法的,安全检查算法,(1),设置两个向量,Work:,系统可提供进程继续运行所需要的各类资源数；,初始值：,work=available;,Finish:,系统能否有足够的资源分配给进程完成,初始值：,Finishi=false;,得到资源后为,True,(2),从进程集合中找到一个能满足下列条件的进程：,Finishi=,false;Need,i,available,若找到这样的进程，执行步骤,(3),，否则执行步骤,(4),；,(3),进程获得资源后，可以顺利执行，直到完成，释放所有资源：,work=work+Allocation,；,Finishei,=false;,回到步骤,(2);,(4),如果所有进程的,Finishi=True,；,表示系统安全；否则系统表示不安全状态；,23,银行家算法,银行家算法的特点,允许互斥、部分分配和不可抢占，可提高资源利用率；,要求事先说明最大资源要求，在现实中很困难；,银行家算法的缺点：,要求被分配的各类资源数量固定；,要求用户也要保持不变；,算法只保证用户在有限时间内得到满足，难以满足更高响应的要求；,需要花费很多时间用于不断的测试。,24,银行家算法,示例,现在有,12,个资源供三个进程共享，,进程,1,共需要,4,个资源，但第一次先申请一个资源；,进程,2,总共需要,6,个资源，第一次要求,4,个资源；,进程,3,总共需要,8,个资源，第一次需要,5,个资源。现在的分配情况如下：,进程,已占资源数,最大需求量,P1,P2,P3,1,4,5,4,6,8,剩余资源数,2,系统安全,25,银行家算法,示例,系统不安全,银行家算法就是不断测试各个进程占用和申请资源的情况，在保证至少一个进程能得到所需的全部资源的前提下进行资源的分配。,进程,已占资源数,最大需求量,P1,P2,P3,2,4,5,4,6,8,剩余资源数,1,26,银行家算法,示例,对每个请求进行检查，是否会导致不安全状态。若是，则不满足该请求；否则便满足。,检查状态是否安全的方法是看他是否有足够的资源满足一个距最大需求最近的客户，如此反复下去。如果所有投资最终都被收回，则该状态是安全的，最初的请求可以批准。,系统拥有某类资源,10,个,进程,已有资源数,还要申请资源数,P,4,4,Q,2,2,R,2,7,27,银行家算法,示例,存在一个状态序列能够使所有的客户均得到其所有的贷款，则称该状态是安全的。,28,银行家算法,示例,图示状态是安全的，以使,Marvin,运行结束，释放所有的,4,个单位资金。这样下去便可满足,Suzanne,或,Barbara,的请求。,考虑给,Barbara,另一个她申请的资源，则得到的状态是不安全的。,如果忽然所有的客户都申请，希望得到最大贷款额，而银行家无法满足其中任何一个的要求，则发生死锁。,29,死锁的检测,死锁检测算法与死锁避免算法是类似的，不同在于前者考虑了检查每个进程还需要的所有资源能否满足要求；而后者则仅要根据进程的当前申请资源量来判断系统是否进入了不安全状态。,死锁检测,算法的,策略,是查找一个进程，使得可用资源可以满足该进程的资源请求，然后假设同意这些资源，让进程运行直到完成，再释放它的所有资源，然后算法寻找另一个可以满足资源请求的进程。,30,死锁的检测,用表格来记录进程使用和等待资源的情况。,进程,依次申请,已占,等待资源,P1,P2,P3,r1、r5、r3,r3、r4、r2,r2、r5,r5、r1,r3,r2,r3,r2、r4,r5,出现死锁,31,解除死锁,资源剥夺法,撤消进程法,32,解除死锁,立即结束所有进程的执行，并重新启动操作系统。方法简单,但以前工作全部作废,损失可能很大。,撤销陷于死锁的所有进程,解除死锁继续运行。,逐个撤销陷于死锁的进程,回收其资源,直至死锁解除。,剥夺陷于死锁的进程占用的资源，但并不撤销它,直至死锁解除。,根据系统保存的,checkpoint,让所有进程回退,直到足以解除死锁。,当检测到死锁时，如果存在某些未卷入死锁的进程，而这些进程随着建立一些新的抑制进程能执行到结束，则它们可能释放足够的资源来解除死锁。,33,小结和示例,例,:,假定希望顺序执行,s,1,s,2,s,3,但,s,2,需互斥执行。请利用信号量机制和,P/V,操作实现这一要求。,解,:,设,S=1(,初值,),，程序段为：,s,1,;P(s);s,2,;V(s),；,s,3,34,线程,35,线程的基本概念,研究可否将进程的属性分开，由操作系统分别进行处理。即把处理机调度和其他资源的分配针对不同的活动实体进行；而对拥有资源的基本单位，不进行频繁切换。正是这样，产生了线程概念。,在引入线程的操作系统中，线程是进程中的一个实体，是被系统独立调度和分配的基本单位。,线程基本上不拥有系统资源，只拥有一些在运行中必不可少的资源,(,如程序计数器、一组寄存器和栈,),，但它可与同属一个进程的其他线程共享进程所拥有的全部资源。,一个线程可以创建和撤消另一个线程；同一进程中的多个线程之间可以并发执行。,由于线程之间的相互制约，致使线程在运行中也呈现出间断性、相应地，线程也同样有就绪、阻塞和执行三种基本状态，有的系统中线程还有终止状态。,36,线程与进程的比较,调度：,在传统的操作系统中，拥有资源的基本单位和独立调度、分派的基本单位都是进程。,并发性：,在引入线程的操作系统中，不仅进程之间可以并发执行，而且在一个进程中的,多个线程之间亦可并发执行,，因而使操作系统具有更好的并发性，从而能更有效地使用系统资源和提高系统吞吐量。,拥有资源：,不论是传统的操作系统，还是设有线程的操作系统，,进程都是拥有资源的一个独立单位,，它可以拥有自己的资源。,系统开销：,由于在创建或撤消进程时，系统都要为之分配或回收资源，如内存空间、,I/O,设备等。因此，操作系统所付出的开销将明显地大于在创建或撤消线程时的开销。,37,作业管理,38,作业管理概述,(1),作业由程序、数据和作业说明书三部分组成。,作业说明书,包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。,39,作业管理概述,(2),作业,进入系统和作业建立,启动,SPOOLing,系统的“预输入”程序实现作业的装入。,(p208),作业建立：接收作业信息，组织文件，建立,JCB,。,作业控制块,JCB(p166),JCB,是记录类型的数据结构；,包含对作业进行管理的必要信息；,比如：用户名、作业名；优先级、地址、长度、类型说明、作业状态等,JCB,是作业调度的基本依据，是,作业存在的唯一标志,。,40,作业管理概述,(3),作业管理的任务,作业调度：又称高级调度。,主要功能是根据一定的算法，从一批作业中选取若干作业进入内存，并做好运行前的准备和作业完成后的善后工作。,作业控制：,指程序员或操作员对作业运行的全过程进行控制，从作业输入系统直到作业运行结束。,分为联机作业控制和脱机作业控制。,41,作业状态,四种状态,进入状态,（提交状态）：在输入设备上预输入,后备状态,：在输入井中，已建,JCB,，,挂在队列中,运行状态,：调入内存，参与对,CPU,的竞争；,先到,就绪,，经调度,运行,，有,I/O,请求,等待,，,I/O,完成到,就绪,完成状态,：运行完毕或非正常终止，回收全部资源，释放,PCB,和,JCB,。,42,作业状态变迁,43,处理机调度的层次,三级调度层次,高级调度,(High Level Scheduling),低级调度,(Low Level Scheduling),中级调度,(Intermediate Level Scheduling),44,高级调度,作业调度,/,长程调度,用于决定把外存上处于后备队列的哪些作业,调入内存,，并为它们创建进程，分配必要的资源，然后再将新创建的进程排在就绪队列上。,两个决定：,接纳多少作业；,接纳哪些作业。,45,低级调度,进程调度,/,短程调度,它决定就绪队列中的哪个进程将,获得处理机,，然后由分派程序执行把处理机分配给进程的操作。,短程调度程序是操作系统最为核心的部分，短程调度策略的优劣直接影响到整个系统的性能。,两种调度方式,：,非剥夺方式,剥夺方式：时间片原则、优先权原则、短作业优先原则,46,中级调度,平衡负载调度，中程调度。,引入目的：为了提高内存的利用率和系统的吞吐量,决定主存储器中所能容纳的进程数，这些进程将允许参与竞争处理器资源。,中级调度根据存储资源量和进程的当前状态来决定,辅存和主存中进程的对换,。,47,中级调度,中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过,把一些进程换出主存，使之进入“挂起”状态,，不参与进程调度，起到平滑和调整系统负荷的作用。,使那些暂时不能运行的进程不再占用宝贵的内存空间，而将它们调至外存上去等待；当这些进程重又具备运行条件，且内存又稍有空闲时由中级调度决定将哪些进程重新调入内存。,48,处理器调度的层次,中级调度,新建态,挂起就绪态,挂起等待态,高级调度,低级调度,运行态,就绪态,等待态,终止态,49,调度的模型,中级调度,处理器,低级调度,高级调度,完成,超时,挂起就绪队列,挂起等待队列,等待队列,就绪队列,等待事件,交互式用户,事件,出现,后备作业队列,中级调度,50,作业调度及调度算法,检查系统是否满足作业的资源要求，并按一定算法选取作业。作业调度也称为高级调度。,功能：,选取作业；,分配资源，建立进程；,构造有关信息；,运行结束回收资源，输出必要信息，撤消该作业的全部进程和,JCB,。,51,常见调度算法,先来先服务,(FCFS),：,按照作业进入系统的,先后次序,进行调度，先进入系统者先调度；即启动等待时间最长的作业。,优点,：实现,简单,、,公平,缺点,：没考虑资源利用率和作业的特殊性,短作业优先,（,SJF,）：,以要求,运行时间长短,进行调度，即启动要求运行时间最短的作业。,优点,：易于实现，强调了资源的充分利用，保证了系统的最大吞吐量,(,单位时间里处理作业的个数,),。,缺点,：不公平，会造成长作业长期等待。,结论：假设系统中所有作业,同时到达,，可以证明采用,SJF,能得到最短的作业平均周转时间。,52,常见调度算法,高响应比优先,(HRF),：,响应比最高的作业优先启动。,响应比,=(,等待时间,+,估计运行时间,)/,估计运行时间,该算法是,FCFS,和,SJF,的结合，克服了两种算法的缺点,优点,:,公平，吞吐率大,缺点,:,增加了计算，增加了开销,高优先级优先,：由用户指定作业优先级，优先级高的作业先启动。,资源均衡型调度,：把作业分类，作业调度从不同类型作业中去调度作业,根据作业对资源要求分类：,I/O,型、,CPU,型和均衡型,实际的算法可能会是,多种算法的综合,。,53,常见调度算法,时间片轮转调度算法,调度程序每次把,CPU,分配给就绪队列首进程使用一个时间片，例如,100ms,，,就绪队列中的每个进程轮流地运行一个时间片。当这个时间片结束时，强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。,轮转策略可防止那些很少使用外围设备的进程过长的占用处理器而使得要使用外围设备的那些进程没有机会去启动外围设备。,54,时间片取选,轮转法调度是一种剥夺式调度,，系统耗费在进程切换上的开销比较大，这个开销与时间片的大小很有关系。,时间片取值太小,，多数进程不能在一个时间片内运行完毕，,切换就会频繁,，开销显著增大，从系统效率来看，时间片取大一点好。,时间片取值较大,，随就绪队列里进程数目增加，轮转一次的总时间增大，对,进程的响应速度放慢,了。为满足响应时间要求，要么限制就绪队列中进程数量，要么采用动态时间片法，根据负载状况，及时调整时间片的大小。,55,