《第2章处理器管理课件》由会员分享,可在线阅读,更多相关《第2章处理器管理课件(54页珍藏版)》请在金锄头文库上搜索。
1、第2章 处理器管理,主讲:周文强 课程:操作系统,本章内容,2.7 进程死锁 2.8 处理器管理新技术 2.9 Windows操作系统的进程管理,2.7 进程死锁,死锁问题是Dijkstra于1965年在研究银行家算法(该问题原来是为了研究银行家如何将一定的资金安全地借给若干顾客的问题)时首先提出来的,后来Havender等人又进一步认识这一现象并将其发展。实际上,死锁是一个具有普遍性的现象,在各个领域乃至日常生活中也屡见不鲜。研究死锁问题是保证操作系统正确、可靠运行必须考虑的课题。,并行进程的执行虽然改善了系统资源的利用率,提高了系统的处理能力,但并行执行的风险增大了,因为并发进程执行的结果
2、与时间有关,且对临界资源的管理或操作不当(如在生产者与消费者问题中的P操作的次序颠倒时等)就会产生死锁。,1. 死锁的概念,死锁(Deadlock),是指在多道程序系统中的两个或多个进程,当某个进程提出资源请求后,使得若干进程在无外力作用下,永远不能再继续前进,称这种情况为系统发生了死锁或僵局(Deadly Embrace)。或当两个或多个进程因竞争系统资源而无休止地相互等待时,称这些进程是死锁的,或处于死锁状态。,2. 死锁的原因,1竞争临界资源 当系统中供多个进程共享的临界资源(如输入设备、打印机、公用队列等)的数目不能满足各个进程的需要时,会引起各个进程对资源的竞争而产生死锁。可以说,资
3、源不足是产生死锁的最主要的原因,但是这个问题在多道程序系统中是无法解决的。,2进程推进顺序不当,进程在运行过程中,请求和释放资源的顺序不当,也同样会导致死锁的产生。,案例,条件: 1、进程A和进程B均需要申请得到资源R1和资源R2方可运行。 2、进程A先申请得到R1,然后进程B申请也得到R2。 执行: 1、随后进程A又申请R2,但R2因为B进程正占用该资源而阻塞,等待B释放R2。 2、进程B又申请R1,但R1因为A进程正占用该资源而阻塞。 结论:A、B两个进程都因为申请不到所需的资源而处于阻塞状态,都不能继续运行,就形成了死锁。,3. 产生死锁的必要条件,系统中资源有限,而且进程各自按照自己的
4、顺序向前推进。因此会产生死锁,但并非一定会产生死锁。 (1)互斥条件。在同一段时间内,每一资源只能被一个进程使用,若有别的进程也请求该资源,则必须等待该资源被释放。 (2)占有并请求条件。允许进程不释放已经分配到了一些资源,并可以请求并等待分配新的资源。,(3)不可剥夺条件。已分配给某进程的资源不可被剥夺,只能由占有它的进程使用完后主动释放。 (4)循环等待条件。系统必然存在一条由两个或两个以上的进程组成的循环链,链中的每一个进程都在等待相邻进程所占用的资源。这反映在资源分配图(一种有向图:含进程与资源两类结点,由进程结点指向资源结点的边表示资源请求,由资源结点指向进程结点的边表示资源分配)中
5、就是存在有向封闭环路。,2.7.2 死锁的预防和避免,了解产生死锁的必要条件后,下一步就是如何预防和避免死锁的问题。,1死锁的预防,死锁的预防就是通过破坏产生死锁的必要条件之一,使系统中不发生死锁的一种操作系统用来对付死锁的办法。 这种办法是在系统运行之前就采取措施,即在系统设计时确定资源分配算法,消除发生死锁的任何可能性。,该方法虽然比较保守、资源利用率低,但因简单明了并且安全可靠,仍被广泛采用。 产生死锁的四个必要条件中,互斥条件和不可剥夺条件几乎都是由共享资源本身的使用特性所决定的,因此不好破坏。那么,实用的死锁预防办法就是通过破坏占有并请求条件和循环等待条件来实现的。,(1)静态资源分
6、配法,采用这种方法时,系统规定每个进程在开始运行前,都必须次性地申请其在整个运行过程中所需的全部资源。此时,若系统有足够的资源,便把进程想要的全部资源一次性地分配给它;若不能全部满足进程的资源请求,则一个资源也不分给它。这样,进程在运行过程中就不会再提出资源请求,从而破坏了占有与请求条件。 该方法的优点是简单、安全、易实现,缺点是资源被严重浪费。,(2)有序资源使用法,在采用这种方法时,系统中的所有资源按类都被赋予一个唯一的编号,每个进程只能按编号的升序申请资源。即对同一个进程而言,它一旦申请了一个编号为n的资源,就不允许再申请编号比n小的资源了,因此,破坏了循环等待条件。 该方法的优点是安全
7、且资源利用率比静态资源分配法有所提高,因为它实际是一种半动态的资源分配法。缺点是实现较困难,因为难给出合适的资源编号,不便于系统增添新设备,不便于用户编程,且仍有一定的资源浪费现象。,2.7.3 死锁的避免,在死锁的预防中我们采用限制死锁的必要条件的方法虽然简单,但严重损害了系统的性能。 如果将限制条件弱化,既能获得满意的系统性能,也能够有效地避免死锁。,安全状态与不安全状态,安全状态是指系统能够按照某种进程顺序,即一种进程推进序列(称为安全序列),来为每个进程分配其所需资源,使每个进程都可以顺利完成。如果系统不存在这种安全序列,系统处于不安全状态。 不安全状态并非都是死锁状态,但系统一旦进入
8、不安全状态,则有可能继而进入死锁状态。而系统如果处于安全状态,则可避免进入死锁状态。,安全状态与不安全状态,避免死锁要使系统不进入不安全状态。系统允许进程动态申请资源,但系统在分配资源之前,先计算资源分配的安全性。若此次分配不会导致系统进入不安全状态,则将资源分配给该进程,否则,让该进程等待。,案例分析,条件: 1、系统中现有3个进程P1,P2,P3,可供进程使用的总资源数有12 2、各进程需求资源数及已得到资源数情况如下:进程P1需求资源数为9,已分配到的资源数3;进程P2需求资源数为5,已分配到的资源数3;进程P3需求资源数为10,已分配到的资源数2, 系统资源剩余数是4。按照以下两种方法
9、安排进程序列:,计算安全序列,1、剩余资源4中分配2给进程P2,分配1给进程P1,分配1给进程P3; 2、进程P2完成后释放资源5,全部给进程P1; 3、进程P1完成后,释放资源9,在分配7给进程P3。 这样,进程按照序列P2,P1,P3推进,该序列是安全序列,采用它,系统处于安全状态,各个进程都能顺利完成,不会产生死锁。,不安全序列,剩余资源4中分配2给进程P2,分配1给进程P1,分配1给进程P3;进程P2完成后释放资源5,如果全部给进程P3,P3和P1都不能满足而相互等待对方释放资源,造成死锁。也就是说,进程按照序列P2,P3,P1推进,该序列是不安全序列,会产生死锁。,2.7.4 死锁的
10、检测与解除,这种对付死锁的办法适用于那些对死锁的产生不采取任何预防或避免的对策,即允许死锁发生的系统中,其功能是由以下两部分实现的。 1、定时触发执行的死锁检测程序 2、可能在死锁检测程序中被调用执行的死锁解除程序,1死锁的检测,死锁检测程序的任务就是实际确定系统中是否存在死锁,并试图找出陷入死锁的进程和资源。 通常采用的检测算法主要是通过对资源分配图的化简来确定资源分配时是否有循环等待事件。,死锁定理,化简资源分配图,是指依次把所有资源请求都能满足的进程结点变成孤立结点的过程(即消去其请求边和分配边,回收资源)。当且仅当某时刻系统的资源分配图是不可完全化简的(即至少有一个进程结点不会变成孤立
11、结点),则称此时系统处于死锁状态,这是死锁产生的充分条件,称为死锁定理。,2死锁的解除,当死锁检测程序检测到系统中出现死锁时,应该立即把系统从死锁状态中解脱出来。 常见的死锁解除方法有以下两种: 1)资源剥夺法 1.还原算法。即恢复计算结果和状态。 2.建立检查点主要是用来恢复分配前的状态。 2)撤消进程法 1.程序的优先数,即被撤消进程的优先数。 2.作业类的外部代价 3.运行代价,即重新启动它并运行到当前撤消点所需要的代价。,(1)撤销进程法,最简单的做法是撤销全部死锁进程,但被撤销进程前面所做的一切工作都白费了,这种代价也太大了,因此这种做法已经没有用的。更常用的解除死锁的方法叫最小代价
12、撤销法。该方法首先计算死锁进程的撤销代价,然后依次选择撤销代价最小的进程,逐个地撤销死锁进程,回收资源给其他进程,直至死锁不复存在。进程的撤销代价往往与进程的优先级、占用处理器的时间等成正比。,(2)剥夺进程法,该方法使用系统的挂起与激活机构挂起一些死锁进程,暂时剥夺它们占有的资源,以解除死锁,待以后系统中可利用的资源增多了,再激活被挂起的进程,使之继续运行。这种方法因实现代价大而很少被使用。,2.8 处理器管理新技术,从20世纪60年代提出进程概念后,操作系统中一直都是以进程作为资源分配与独立运行的基本单位。 到了20世纪80年代中期,人们又提出了比进程更小的能独立运行的基本单位:线程,用它
13、来进一步提高系统的并发程度和吞吐量。进入21世纪,又提出了超线程技术和双核技术。本节主要介绍这些技术的基本知识。,2.8.1 线程技术,1.线程的引入 在操作系统中引入进程后,使得多个程序可以实现并发运行,改善了资源利用效率,提高了系统吞吐量。此时进程作为系统中的一个基本单位,具有两个属性: 一是,进程是资源分配和拥有的基本单位。二是,进程是一个可以独立调度和运行的基本单位。,由于进程的这两个基本属性,构成了进程并发运行的基础,系统要不断地进行资源的分配与回收、现场的保存与恢复等工作。系统要为此付出较大的时间与空间的开销。 在系统中所设置的进程数目不能过多,进程切换的频率也不能过高,这就限制了
14、系统并发程度的进一步提高。 如何能使进程更好地并发运行,同时又能尽量减少系统开销呢? 引入线程,2、线程的概念,线程是进程中的一个实体,是被系统独立调度和运行的基本单位。 1、线程自己基本上不拥有系统资源,只拥有一点在运行中必不可少的资源(如程序计数器、一组寄存器和栈)但是它可以与同属于一个进程的其他线程共享进程所拥有的全部资源。 2、一个线程可以创建和撤销另一个线程,同一进程中的多个线程之间可以并发运行。 3、线程之间也会相互制约,使其在运行中呈现异步性。 因此,线程同样具有就绪、运行、等待三种基本状态。,3、线程与进程的比较,线程具有许多传统进程的特征,所以又称为轻型进程。传统的进程称为重
15、型进程,相当于只有一个线程的任务。 在引入线程的操作系统中,通常一个进程拥有若干个线程,至少也有一个线程。 线程与进程有如下4个方面不同:,(1)调度,在原有的系统中,进程既是资源分配和拥有的基本单位,又是独立调度和运行的基位。 在引入线程后,把线程作为是独立调度和运行的基本单位,而进程只作为资源分配和拥有的基本单位,把传统进程的两个属性分开,线程便能轻装前进,从而显著提高系统的并发程度。 此时,在同一进程中,线程的切换不会引起进程的切换,而由一个进程中的线程到另一个进程中的线程时,将会同时引起进程的切换。,(2)并发,在引入线程的系统中,不仅进程之间可以并发运行,而且在一个进程中的多个线程之
16、间,也可以并发运行,使系统真有更好的并发性,从而能更有效地使用系统资源和提高吞吐量。,(3)拥有资源,不论是传统的操作系统,还是引入线程的操作系统,进程都是资源分配和拥有的基本单位,而线程基本上不拥有系统资源(只有一些运行时必不可少的资源),但是,线程可以访问所属进程的所有资源。,(4)系统开销,系统在创建(或撤销)进程时,都要为之分配(或回收)大量的资源,如主存空间、I/O设备等。所以,在进程切换时,要进行复杂的现场保护和新环境的设置。 因而,不管是进程的创建、撤销,还是是切换,对于进程的操作所付出的系统开销都远大于对于线程操作所付出的系统开销。,4. 线程的类型,(1)系统级线程 系统级线程是依赖于系统控制的,即无论是用户进程中的线程,还是系统进程中的线程,它们的创建、撤销与切换都是由系统控制实现的。 在系统中保留了一张线程控制块,系统根据该线程控制块来感知线程的存在,并对线程进行控制。,(2)用户级线程 用户级线程是由用户控制的,对于用户级线程的创建、撤销与切换,都与系统控制无关,完全由用户自己管理。 简单来说就