第三章 进程管理(3)

1、1,第三章 进程管理,主讲：何中胜 计算机科学工程系,2020年7月15日星期三,2,3.7 进程的调度,2020年7月15日星期三,3,无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数，这将导致用户进程互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。本节介绍进程调度的功能、进程调度发生的时机以及由进程调度引起的进程上下文切换等。,2020年7月15日星期三,4,分级调度,作业调度：又称宏观调度，或高级调度。其主要任务是按一定的原则对外存输入井上的大量后备作业进行选择，给选出的作业分

2、配内存、输入输出设备等必要的资源，并建立相应的进程，以使该作业的进程获得竞争处理机的权利。另外，当该作业执行完毕时，还负责回收系统资源。 交换调度：又称中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或就绪等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。交换调度主要涉及到内存管理与扩充。,2020年7月15日星期三,5,分级调度(续),进程调度：又称微观调度或低级调度。其主要任务是按照某种策略和方法选取一个处于就绪状态的进程占用处理机。在确定了占用处理机的进程后，系统必须进行进程上下文切换以建立与占用处理机进程相适应的执行环境。 线程调

3、度。,2020年7月15日星期三,6,4级调度的关系,2020年7月15日星期三,7,在多道批处理系统中，存在着作业调度和进程调度。但是，在分时系统和实时系统中，一般不存在作业调度，而只有进程调度、交换调度和线程调度。这是因为在分时系统和实时系统中，为了缩短响应时间或为了满足用户需求的截止时间，作业不是建立在外存，而是直接建立在内存中。在这些系统中，一旦用户和系统的交互开始，用户马上要进行控制。因而，这些系统中没有作业提交状态和后备状态。它们的输入信息经过终端缓冲区为系统所接收，或者立即处理，或者经交换调度暂存外存中。,2020年7月15日星期三,8,进程调度方式,非抢占式(不可剥夺方式)：即

4、使就绪队列中的某个进程的优先级高于正在运行进程的优先级，也要等运行进程主动让出处理机后高优先级进程才能得到处理机。 抢占式(可剥夺方式)：是指当就绪队列中某一进程的优先级高于正在运行的进程优先级时，系统可剥夺正在运行进程的处理机的使用权(即使分配给它的时间片还没有用完)，而使高优先级的进程抢占处理机。,2020年7月15日星期三,9,引起进程调度的时机,(1) 正在执行的进程执行完毕。这时，如果不选择新的就绪进程执行，将浪费处理机资源。 (2) 执行中进程自己调用阻塞原语将自己阻塞起来进入睡眠等待状态。 (3) 执行中进程调用了P原语操作，从而因资源不足而被阻塞；或调用了V原语操作激活了等待资

5、源的进程队列。 (4) 执行中进程提出IO请求后被阻塞。 (5) 在分时系统中时间片已经用完。 (6) 在执行完系统调用，在系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。 以上都是在CPU执行不可剥夺方式下所引起进程调度的原因。在CPU执行方式是可剥夺时，还有： (7) 就绪队列中的某进程的优先级变得高于当前执行进程的优先级，从而也将引发进程调度。,2020年7月15日星期三,10,进程调度程序的功能,(1)记录系统中所有进程的有关信息。作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且，进程管理模式根据各进

6、程的状态特征和资源需求，将各进程的PCB表排成相应的队列并进行动态队列转接。进程调度模块通过PCB变化来掌握系统中所有进程的执行情况和状态特征，并在适当的时机从就绪队列中选择出一个进程占据处理机。 (2)确定处理机的分配原则。即按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。同时还确定将处理机分配给进程使用的时间片大小。根据不同的系统设计目的，有各种各样的选择策略，例如系统开销较少的静态优先数调度法，适合于分时系统的轮转法和多级反馈轮转法等。这些选择策略决定了调度算法的性能。,2020年7月15日星期三,11,进程调度程序的功能(续),(3)分配处理机。 (4)切换进程上下文。一

7、个进程的上下文（context）包括进程的状态、有关变量和数据结构的值、硬件寄存器的值和PCB以及有关程序等。一个进程的执行是在进程的上下文中执行。当正在执行的进程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。当进行上下文切换时，系统要首先检查是否允许做上下文切换。然后，系统要保留有关被切换进程的足够信息，以便以后切换回该进程时，顺利恢复该进程的执行。在系统保留了CPU现场之后，调度程序选择一个新的处于就绪状态的进程，并装配该进程的上下文，使CPU的控制权转换到被选中进程中。 (5)回收处理机。,2020年7月15日星期三,12,调度算法,1. 先来先服务（FCF

8、S）调度算法 将就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。在没有特殊理由要优先调度进程时，从处理的角度来看，FCFS方式是一种最合适的方法，无论是追加还是取出一个队列元素在操作上都是最简单的。 直观看，该算法在一般意义下是公平的。即每个进程都按照它们在队列中等待时间长短来决定它们是否优先享受服务。不过对于那些执行时间较短的进程来说，如果它们在某些执行时间很长的进程之后到达，则它们将等待很长时间。在实际操作系统中，尽管很少单独使用FCFS算法，但和其他一些算法配合起来，FCFS算法还是使用得相当多的。例如基于优先级的调度算法就

9、是对具有同样优先级的进程采用的FCFS方式。,2020年7月15日星期三,13,调度算法(续),2. 轮转调度算法（round robin scheduling） 轮转法的基本思路是让每个进程在就绪队列中的等待时间与享受服务的时间成比例。轮转法的基本概念是将CPU的处理时间分成固定大小的时间片。如果一个进程在被调度选中之后用完了系统规定的时间片，但未完成要求的任务，则它自行释放自己所占有的CPU而排到就绪队列的末尾，等待下一次调度。同时，进程调度程序又去调度当前就绪队列中的第一个进程或作业。轮转法的原理见图。 显然，轮转法只能用来调度分配那些可以抢占的资源。将它们随时剥夺再分配给别的进程。CP

10、U是可抢占资源的一种。但如打印机等资源是不可抢占的。由于作业调度是对除了CPU之外的所有系统硬件资源的分配，其中包含有不可抢占资源，所以作业调度不使用轮转法。,2020年7月15日星期三,14,调度算法(续),在轮转法中，时间片长度的选取非常重要。首先，时间片长度的选择会直接影响系统开销和响应时间。如果时间片长度过短，则调度程序剥夺处理机的次数增多。这将使进程上下文切换次数也大大增加，从而加重系统开销。反过来，如果时间片长度选择过长，比方说一个时间片能保证就绪队列中所需执行时间最长的进程能执行完毕，则轮转法变成了先来先服务法。 此时间片值的设置可以是固定的(固定周期轮转)，也可以是可变的(可变

11、周期轮转)。 RR算法主要用于分时系统或事务处理系统，可保证对各终端用户的及时响应。但它对偏重CPU的进程和偏重I/O的进程有不同的处理结果，可以采用虚拟时间片轮转(VRR)策略来避免这个问题。新加入的特性是附加一个FCFS策略队列来收集从I/O等待中释放的进程。,2020年7月15日星期三,15,3. 多级反馈轮转法 在轮转法中，加入到就绪队列的进程有三种情况，一种是分给它的时间片用完，但进程还未完成，回到就绪队列的末尾等待下次调度去继续执行。另一种情况是分给该进程的时间片并未用完，只是因为请求IO或由于进程的互斥与同步关系而被阻塞。当阻塞解除之后再回到就绪队列。再有一种情况就是新创建进程进

12、入就绪队列。如果对这些进程区别对待，给予不同的优先级和时间片，从直观上看，可望进一步改善系统服务质量和效率。例如，可把就绪队列按照进程到达就绪队列的类型和进程被阻塞时的阻塞原因分成不同的就绪队列，每个队列按FCFS原则排列，各队列之间的进程享有不同的优先级，但同一队列内优先级相同。这样，当一个进程在执行完它的时间片之后，或从睡眠中被唤醒以及被创建之后，将进入不同的就绪队列。多级反馈轮转法与优先级法在原理上的区别是，一个进程在它执行结束之前，可能需要反复多次通过反馈循环执行，而不是优先级法中的一次执行。,调度算法(续),2020年7月15日星期三,16,2020年7月15日星期三,17,调度算法

13、(续),4. 优先级法 首先，系统或用户按某种原则为进程指定一个优先级来表示该进程所享有的调度优先权。该算法的核心是确定进程的优先级。这种算法可以是抢占式也可是非抢占式的。 确定优先级的方法：静态法和动态法。 静态法根据进程的静态特性在进程执行之前就确定它们的优先级，而且在执行过程中一直保持不变。动态法则是将进程的静态特性与动态特性结合起来确定进程的优先级而且随着进程的运行，其优先级不断变化。,2020年7月15日星期三,18,进程的静态优先级确定原则可以是： (1) 按进程的类型给予不同的优先级。例如，在有些系统中，进程被划分为系统进程和用户进程。系统进程享有比用户进程高的优先级。对于用户进

14、程来说，则可以分为： IO繁忙的进程， CPU繁忙的进程， IO与CPU均衡的进程， 其他进程。 对系统进程，也可以根据其所要完成的功能划分为不同的类型，例如，调度进程、IO进程、中断处理进程、存储管理进程等。这些进程还可进一步划分为不同类型和赋予不同的优先级。例如，在操作系统中，对于键盘中断的处理优先级和对于电源掉电中断的处理优先级是不相同的。 (2) 将作业的静态优先级作为它所属进程的优先级,2020年7月15日星期三,19,动态优先级 基于静态优先级的调度算法实现简单，系统开销小，但由于静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。现在的操作系统中

15、，如果使用优先级调度的话，则大多采用动态优先级的调度策略。 进程的动态优先级一般根据以下原则确定： (1) 根据进程占有CPU时间的长短来决定。一个进程占有处理机的时间愈长，则在被阻塞之后再次获得调度的优先级就越低，反之，其获得调度的可能性就会越大。 (2) 根据就绪进程等待CPU的时间长短来决定。一个就绪进程在就绪队列中等待的时间越长，则它获得调度选中的优先级就越高。 由于动态优先级随时间的推移而变化，系统要经常计算各进程的优先级，因此，系统要为此付出一定的开销。,2020年7月15日星期三,20,5. 最短进程优先法（shortest process first） 最短作业优先法（SPF）

16、就是从就绪队列中选择那些估计需要执行时间最短的进程将处理机分配给它。 6. 最高响应比优先法（highest responseratio next） 最高响应比优先法（HRN）是对FCFS方式和SJF 方式的一种综合平衡。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。,调度算法(续),2020年7月15日星期三,21,实时调度算法,实现实时调度的基本条件 提供必要的信息(就绪时间、截止时间、处理时间、资源优先级) 系统处理能力强 采用抢占式调度机制 具有快速切换机制 实时调度算法的分类 1)非抢占式调度算法 : 非抢占式轮转调度算法 非

17、抢占式优先调度算法 2)抢占式调度算法: 基于时钟中断的抢占优先调度算法 立即抢占优先权调度算法。,2020年7月15日星期三,22,2020年7月15日星期三,23,常用的几种实时调度算法,1）最早截止时间优先即EDF(Earliest Deadline First)算法 EDF算法用于非抢占调度方式,2020年7月15日星期三,24,2）最低松弛度优先(LLF)算法 该算法是根据任务紧急(或松弛)的程度，来确定任务的优先级。该算法主要用于可抢占调度方式中。 假如在一个实时系统中，有两个周期性实时任务A和B，任务A要求每 20 ms执行一次，执行时间为 10 ms；任务B只要求每50 ms执

18、行一次，执行时间为 25 ms。,A和B任务每次必须完成的时间,2020年7月15日星期三,25,在刚开始时(t1=0)，A1必须在20ms时完成，而它本身运行又需 10 ms，可算出A1的松弛度为10ms；B1必须在50ms时完成， 而它本身运行就需25 ms，可算出B1的松弛度为25 ms，故调度程序应先调度A1执行。在t2=10 ms时，A2的松弛度可按下式算出： A2的松弛度=必须完成时间-其本身的运行时间-当前时间 =40 ms-10 ms-10 ms=20 ms 类似地，可算出B1的松弛度为15ms，调度程序应选择B2运行。t3=30 ms时，A2的松弛度已减为0，B1的松弛度为1

19、5 ms，于是调度程序应抢占B1的处理机而调度A2运行.,利用ELLF算法进行调度的情况,2020年7月15日星期三,26,其它算法,时限调度算法与频率单调调度算法。时限调度算法是一种以满足用户要求的时限为调度原则的算法。在实时系统中的用户要求时限有两种，即处理开始时限和处理结束时限。时限调度算法可以使用任一种时限。时限调度算法不可用于周期性调度与非周期性调度两种。 时限调度算法的基本思想是：按用户的时限要求顺序设置优先级，优先级高者占据处理机，也就是说，时限要求最近的任务优先占有处理机。时限调度是抢先式的。抢先式时限调度算法必须把新到达任务的时限要求和当前正在执行任务的时限要求进行比较，如果

20、新到达任务的时限要求更近，则应执行新到达的任务。 时限调度算法也可以用于非周期性任务调度。,2020年7月15日星期三,27,频率单调调度算法是一种被广泛用于多周期性实时处理的调度算法。 频率单调调度算法的基本原理是频率越低（周期越长）的任务的优先级越低。 另外，设任务周期问题，任务的执行时间为C，则使用频率单调调度算法的必要条件是C T。,2020年7月15日星期三,28,3.8 死锁,2020年7月15日星期三,29,死锁例子,一个由于申请不同类型资源而产生死锁的例子 设系统有一台打印机(R1)一台扫描仪(R2)，两进程共享这两台设备。 用信号量S1表示R1是否可用，用信号量S2表示R2是

21、否可用， S1、 S2初值为1。,这两个进程在并发执行过程中，可能会发生死锁。大家可以思考一下，如何修改，进程才不会发生死锁。,2020年7月15日星期三,30,死锁的概念,所谓死锁，是指各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成大家都想得到资源而又都得不到资源，各并发进程不能继续向前推进的状态。下图是两个进程发生死锁时的例子。,2020年7月15日星期三,31,关于死锁的一些结论,参与死锁的进程最少是两个 参与死锁的进程至少有两个已经占有资源 参与死锁的所有进程都在等待资源 参与死锁的进程是当前系统中所有进程的子集 注：如果死

22、锁发生，会浪费大量系统资源，甚至导致系统崩溃。,2020年7月15日星期三,32,永久性资源和临时性资源,永久性资源：可以被多个进程多次使用（可再用资源） 可抢占资源 不可抢占资源 临时性资源：只可使用一次的资源；如信号量,中断信号，同步信号等（可消耗性资源） “申请-分配-使用-释放”模式,2020年7月15日星期三,33,引起死锁的原因,有限资源的竞争 并发进程推进的顺序不当,2020年7月15日星期三,34,1. 竞争系统资源,若系统中只有一台打印机R1和一台读卡机R2，可供进程P1和P2共享。若形成环路，这样会产生死锁。,2020年7月15日星期三,35,2.进程的推进顺序不当,在进程

23、P1和P2并发执行时，按照下图曲线所示顺序推进时，两进程会顺利完成，我们称这种推进顺序是合法的。若按曲线的顺序推进时，进入不安全区D内，两进程再推进会产生死锁。,2020年7月15日星期三,36,系统资源类型,可剥夺资源：存储器 和不可剥夺资源：如打印机 死锁的起因是并发进程的资源竞争。产生死锁的根本原因在于系统提供的资源个数少于并发进程所要求的该类资源数。显然，由于资源的有限性，不可能为所有要求资源的进程无限制地提供资源。但是，可以采用适当的资源分配算法，以达到消除死锁的目的。为此，先看看产生死锁的必要条件。,2020年7月15日星期三,37,产生死锁的必要条件,(1) 互斥条件。并发进程所

24、要求和占有的资源是不能同时被两个以上进程使用或操作的，进程对它所需要的资源进行排他性控制。 (2) 不剥夺条件。进程所获得的资源在未使用完毕之前，不能被其他进程强行剥夺，而只能由获得该资源的进程自己释放。 (3) 部分分配。进程每次申请它所需要的一部分资源，在等待新资源的同时继续占用已分配到的资源。 (4) 环路条件。存在一种进程循环链，链中每一个进程已获得的资源同时被下一个进程所请求。 显然，只要使上述4个必要条件中的某一个不满足，则死锁就可以排除。,2020年7月15日星期三,38,饥饿(starvation),是指系统资源分配不合理 与死锁区别：处于饥饿态的进程可能 是一个，也可能 是多

25、个。而处于死锁状态的进程至少是两个；饥饿不是对资源的循环等待，而是单向等待。处于饥饿态的进程所等待的事件不是永远不发生，而是在发生时总是被别的进程先响应。“饥饿”现象是可以避免的,2020年7月15日星期三,39,死锁的排除方法,解决死锁的方法一般可分为预防、避免、检测与恢复等三种。预防是采用某种策略，限制并发进程对资源的请求，从而使得死锁的必要条件在系统执行的任何时间都不满足。避免是指系统在分配资源时，根据资源的使用情况提前做出预测，从而避免死锁的发生。死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，并能通过外力破坏死锁发生的必要条件，从而使得并发进

26、程从死锁状态中恢复出来。 通过预防和避免的手段达到排除死锁的目的是一件十分困难的事。死锁的检测和恢复则不必花费多少执行时间就能发现死锁和从死锁中恢复出来。因此，在实际操作系统中大都使用检测与恢复法排除死锁,2020年7月15日星期三,40,死锁预防,一种方法是打破资源的互斥和不可剥夺这两个条件，例如允许进程同时访问某些资源等。这种方法不能解决访问那些不允许被同时访问的资源时所带来的死锁问题。另一种方法则是打破资源的部分分配这个死锁产生的必要条件。即预先分配各并发进程所需要的全部资源。如某个进程的资源得不到满足时，则安排一定的等待次序让其他进程释放资源。但是，这种方法也有如下缺点： (1) 在许

27、多情况下，一个进程在执行之前不可能提出它所需要的全部资源。 (2) 无论所需资源何时用到，一个进程只有在所有要求资源都得到满足之后才开始执行。 (3) 对于那些不经常使用的资源，进程在生存过程期间一直占用它们是一种极大的浪费。 (4) 降低了进程的并发性。,2020年7月15日星期三,41,另外一种死锁的预防方法是打破死锁的环路条件。即把资源分类按顺序排列，使进程在申请、保持资源时不形成环路。如有m种资源，则列出R1R2Rm。若进程Pi保持了资源Ri，则它只能申请比Ri级别更高的资源Rj（Ri Rj ）。释放资源时必须是Rj先于Ri被释放，从而避免环路的产生。这种方法的缺点是限制了进程对资源的

28、请求，而且对资源的分类编序也耗去一定的系统开销。,2020年7月15日星期三,42,死锁避免,死锁避免定义:在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配。 死锁避免可被称为动态预防，因为系统采用动态分配资源，在分配过程中预测出死锁发生的可能性并加以避免的方法。 预防死锁的几种策略，会严重地损害了系统性能。因此要施加较弱的限制，从而获得较满意得系统性能来避免死锁。 由于在避免死锁的策略中，允许进程动态地申请资源。因而，系统在进行资源分配之前预先计算资源分配的安全性。若此次分配不会导致系统

29、进入不安全状态，则将资源分配给进程；否则，进程等待。其中最具有代表性的避免死锁算法是银行家算法。,2020年7月15日星期三,43,安全状态与不安全状态,安全状态指系统能按某种进程顺序来为每个进程分配其所需资源，直至最大需求，使每个进程都可顺序完成。若系统不存在这样一个序列，则称系统处于不安全状态。,2020年7月15日星期三,44,1)安全序列,一个进程序列P1，Pn是安全的，如果对于每一个进程Pi(1in），它以后尚需要的资源量不超过系统当前剩余资源量与所有进程Pj (j i )当前占有资源量之和，系统处于安全状态。 (安全状态一定是没有死锁发生的),2020年7月15日星期三,45,2)

30、 安全状态之例,我们通过一个例子来说明安全性。假定系统中有三个进程P1、 P2和P3，共有12台磁带机。进程P1总共要求10台磁带机，P2和P3分别要求4台和9台。假设在T0时刻，进程P1、P2和P3已分别获得5台、2台和2台磁带机，尚有3台空闲未分配，如下表所示：,2020年7月15日星期三,46,3) 由安全状态向不安全状态的转换,如果不按照安全序分配资源，则系统可能会由安全状态进入不安全状态。例如，在T0时刻以后，P3又请求1台磁带机，若此时系统把剩余3台中的1台分配给P3，则系统便进入不安全状态。 因为，此时也无法再找到一个安全序列， 例如，把其余的2台分配给P2，这样，在P2完成后只

31、能释放出4台，既不能满足P1尚需5台的要求，也不能满足P3尚需6台的要求，致使它们都无法推进到完成，彼此都在等待对方释放资源，即陷入僵局，结果导致死锁。 不安全状态:不存在一个安全序列，不安全状态可能进而导致死锁,2020年7月15日星期三,47,利用银行家算法避免死锁,银行家算法中的数据结构 (1) 可利用资源向量Available。这是一个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目，其初始值是系统中所配置的该类全部可用资源的数目，其数值随该类资源的分配和回收而动态地改变。如果Availablej=K，则表示系统中现有Rj类资源K个。 (2) 最大需求矩阵Max。这是一个n

32、m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。,2020年7月15日星期三,48,银行家算法(续),(3) 分配矩阵Allocation。这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 (4) 需求矩阵Need。这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 显然有：Needi,j=Maxi,j-Allocation

33、i,j,2020年7月15日星期三,49,银行家算法具体步骤,设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查： (1) 如果RequestijNeedi,j，便转向步骤2；否则认为出错，因为它所需要的资源数已超过它所宣布的最大值。 (2) 如果RequestijAvailablej，便转向步骤(3)；否则， 表示尚无足够资源，Pi须等待。,2020年7月15日星期三,50,银行家算法具体步骤,(3) 系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值： Availablej=Avail

34、ablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) 系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。若安全，才正式将资源分配给进程Pi，以完成本次分配；否则， 将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。,2020年7月15日星期三,51,安全性 判断算法,(1) 设置两个向量： 工作向量Work: 它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available; Finish: 它表示系

35、统是否有足够的资源分配给进程，使之运行完成。开始时先做Finishi=false; 当有足够资源分配给进程时， 再令Finishi=true。 (2) 从进程集合中找到一个能满足下述条件的进程： Finishi=false; Needi,jWorkj； 若找到， 执行步骤(3)， 否则，执行步骤(4)。,2020年7月15日星期三,52,安全性 判断算法(续),(3) 当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行： Workj=Worki+Allocationi,j; Finishi=true; go to step 2; (4) 如果所有进程的Finishi=

36、true都满足， 则表示系统处于安全状态；否则，系统处于不安全状态。,2020年7月15日星期三,53,银行家算法之例,假定系统中有五个进程P0, P1, P2, P3, P4和三类资源A, B, C，各种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图 所示。,T0时刻的资源分配表,2020年7月15日星期三,54,(1) T0时刻的安全性：,T0时刻的安全序列,2020年7月15日星期三,55,(2) P1请求资源：P1发出请求向量Request1(1，0，2)，系统按银行家算法进行检查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0

37、, 2)Available1(3, 3, 2) 系统先假定可为P1分配资源，并修改Available, Allocation1和Need1向量，由此形成的资源变化情况如图 中的圆括号所示。 再利用安全性算法检查此时系统是否安全。,2020年7月15日星期三,56,P1申请资源时的安全性检查,2020年7月15日星期三,57,(3) P4请求资源：P4发出请求向量Request4(3，3，0)，系统按银行家算法进行检查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，让P4等待。(4) P0请求资源：P

38、0发出请求向量Requst0(0，2，0)，系统按银行家算法进行检查： Request0(0, 2, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系统暂时先假定可为P0分配资源，并修改有关数据，如图 所示。,2020年7月15日星期三,58,为P0分配资源后的有关资源数据,2020年7月15日星期三,59,死锁的检测和恢复(一般系统使用),它是死锁发生后的事后处理技术。它是指系统设有专门的机构，当死锁发生时该机构能够检测到死锁发生的位置和原因，并通过外力破坏死锁发生的必要条件，使得并发进程从死锁状态中恢复出来。 允许死锁发生，操

39、作系统不断监视系统进展情况，判断死锁是否发生。一旦死锁发生则采取专门的措施，解除死锁并以最小的代价恢复操作系统运行 当进程进行资源请求时，死锁检测算法检查并发进程组是否构成资源的请求和保持环路。有限状态转移图和petriNet等技术都可用来有效地判断死锁发生。 死锁的恢复办法较多。最简单的办法是终止各锁住进程，或按一定的顺序中止进程序列，直至已释放到有足够的资源来完成剩下的进程时为止。另外，也可以从被锁住进程强迫剥夺资源以解除死锁。,60,3.9 线程,2020年7月15日星期三,61,线程的概念,进程是程序的一次执行过程和资源分配的基本单位。由此可知，即使是同一段程序，在不同的执行时间，应属

40、于不同的进程。那么，什么是线程（Thread）以及为什么在操作系统中要引入线程的概念呢？ 事实上，引入线程主要是为了提高系统的执行效率，减少处理机的空转时间和调度切换（保护现场信息）的时间，以及便于系统管理。 一个进程内的基本调度单位称为线程或称为轻权进程（Light weight process），这个调度单位既可以由操作系统内核控制，也可以由用户程序控制。,2020年7月15日星期三,62,线程与进程的异同,可以从比较中进一步理解线程的概念。 (1)进程是资源分配的基本单位。所有与该进程有关的资源，例如打印机，输入缓冲队列等，都被记录在进程控制块PCB中。以表示该进程拥有这些资源或正在使用

41、它们。有时，为了对进程的上述两个特性进行区分，规定线程为操作系统的基本调度单位，而进程则为系统资源的者。 (2)当发生进程调度时，它拥有一个完整的虚拟地址空间，但不同的进程拥有不同的虚拟地址空间存同时同一进程内的不同线程共享其所属进程的同一地址空间。 (3)线程只由相关堆栈、寄存器和线程控制块(TCB)组成，寄存器用来存储线程内的局部变量，但不能存储其它线程的相关变量，线程控制块则用于记录线程的有关信息，起到与PCB相对应的一些功能。,2020年7月15日星期三,63,线程与进程的异同,(4)进程切换时涉及到有关资源指针的保存以及地址空间的变化等问题，线程切换时，由于同一进程内的线程共享资源和

42、地址空间，将不涉及资源信息的保存和地址变化问题，从而减少了操作系统的开销时间。 (5)进程的调度与切换都是由操作系统内核完成，而线程则既可由操作系统内核完成，也可由用户程序进行。 (6)在多线程操作系统中，线程是系统内的执行褓，而进程不是。 (7)一个进程内的各个线程以及不同进程内的各个线程均可并发执行，在多处理机系统中，它们可以被分派到不同的CPU上并行运行。,2020年7月15日星期三,64,多线程系统中进程与线程的关系,2020年7月15日星期三,65,并不是在所有的计算机系统中线程都是适用的。事实上在那些很少做进程调度和切换的实时系统、个人数字助理系统中，由于任务的单一性，设置线程相反

43、会占用更多的内存空间和寄存器。 使用线程的最大好处是在有多个任务需要处理机处理时，减少处理机的切换时间；而且，线程的创建和结束所需要的系统开销也比进程的创建和结束要小得多。由此，可以推出最适合使用线程的系统是多处理机系统。在多处理机系统中，同一用户程序可以根据不同的功能划分为不同的线程，放在不同的处理机上执行。 在用户程序可以按功能划分为不同的小段时，单处理机系统也可因使用线程而简化程序的结构和提高执行效率。,线程的适用范围,2020年7月15日星期三,66,线程的分类,线程的两个基本类型是：用户级线程和系统级线程(核心级线型)。在同一个操作系统中，有的使用纯用户级线程，有的使用纯核心级线程，

44、例如Windows NT和Os/2；有的则混合使用用户及线程和核心级线程，例如Solaris 。 用户级线程（user level threads）的管理过程全部由用户程序完成，操作系统内核只对进程进行管理。 为了对用户级线程进行管理，操作系统提供一个在用户空间执行的线程库。该线程库提供创建、调度、撤销线程功能。同时该线程库也提供线程间的通信，线程的执行以及存储线程上下文的功能。用户级线程只使用户堆栈和分配给所属进程的用户寄存器。 线程的调度算法和调度过程完全由用户自行选择和确定。线程调度过程中仅进行线程上下文的切换而不切换处理机，而且切换仅在用户本、用户寄存器间进行，与操作系统内核无关，所以

45、开销相当小。,2020年7月15日星期三,67,线程的分类,核心级线程（Kernel-level Threads）由操作系统内核进行管理，操作系统负责维护核心级线程的各种管理表格，负责线程在处理机上的调度和切换，并给应用程序提供相应的系统调用和应用程序接口API，以使用户程序可以创建、执行、撤消线程。 与用户线程不同，核心级线程既可以被调度到一个处理机上并发执行，也可以被调度到不同的处理机上并行执行。操作系统内核既负责进程的调度，也负责进程内不同线程的调度工作。因此，核心级线程不会出现进程处于阻塞或等待状态，而线程处于执行状态的情况。 另外，核心级线程技术也可用于内核程序自身，从而提高操作系统

46、内核程序的执行效率。 与用户级线程相比，核心级线程的上下文切换时间要大于用户级线程的上下文切换时间。,2020年7月15日星期三,68,线程的状态及转换,线程在执行时也有它的相关特性。线程的状态和同步用来反映线程的这些特性。 线程有3个基本状态，即执行、就绪和阻塞。但是线程没有进程中的挂起状态。也就是说，线程是一个只与内存和寄存器相关的概念，它的内容不会因交换而进入外存。 针对线程的3种基本状态，存在5种基本操作来转换线程的状态。这5种基本操作是： (1) 派生（spawn）：线程在进程内派生出来，它即可由进程派生，也可由线程派生。用户一般用系统调用（或相应的库函数）派生自己的线程。,2020

47、年7月15日星期三,69,线程的状态及转换,一个新派生出来的线程具有相应的数据结构指针和变量，这些指针和变量作为寄存器上下文放在相应的寄存器和堆栈中。 新派生线程被放入就绪队列。 (2) 阻塞（Block）：如果一个线程在执行过程中需要等待某个事件发生，则被阻塞。阻塞时，寄存器上下文、程序计数器以及堆栈指针都会得到保证。 (3) 激活（unblock）：如果阻塞线程的事件发生，则该线程被激活并进入就绪队列。 (4) 调度（schedule）：选择一个就绪线程进入执行状态。 (5) 结束（Finish）：如果一个线程执行结束，它的寄存器上下文以及堆栈内容等将被释放。,2020年7月15日星期三,

48、70,线程的状态和操作关系,需要注意的一点是，在某些情况下，某个线程被阻塞也可能导致该线程所属的进程被阻塞。,2020年7月15日星期三,71,线程的应用,几种典型的应用是 (1) 服务器中的文件管理或通信控制。在局域网的文件服务器中，对文件的访问要求可被服务器进程派生出的线程进行处理。由于服务器同时可能接受许多个文件访问要求，则系统可以同时生成多个线程来进行处理。如果计算机系统是多处理机的，这些线程还可以安排到不同的处理机上执行。 (2) 前后台处理。许多用户都有过前后台处理经验，即把一个计算量较大的程序或实时性要求不高的程序安排在处理机空闲时执行，即后台方式。对于同一个进程中的上述程序来说，线程可被用来减少处理机切换时间和提高执行速度。 (3)异步处理。若程序中的两部分在执行上无顺序规定，则这两