《《操作系统原理及应用（Linux）（第二版）》-王红-电子教案 第3章 处理机调度与死锁》由会员分享，可在线阅读，更多相关《《操作系统原理及应用（Linux）（第二版）》-王红-电子教案 第3章 处理机调度与死锁（93页珍藏版）》请在金锄头文库上搜索。
1、第3章 处理机调度与死锁,本章学习目标 掌握处理机的三级调度 掌握作业调度及进程调度的概念 理解调度算法的评价准则 掌握并灵活运用常用的几种作业调度、进程调度算法 掌握死锁的概念、产生的原因及死锁的必要条件 掌握死锁的预防方法及利用银行家算法避免死锁的方法 掌握死锁的检测与恢复的方法，并能灵活运用,第 3章 处理机调度与死锁,1,教学内容,3.1 作业管理 3.2分级调度 3.3作业调度 3.4 进程调度 3.5 调度算法 3.6 LINUX系统的调度算法 3.7 死锁问题 3.8 死锁的预防 3.9 死锁的避免 3.10 利用银行家算法避免死锁 3.11 死锁的检测与解除,3.1.1 作业的
2、概念 1作业,3.1 作业管理,作业是用户在一次解题或一个事务处理过程中要求计算机系统所做工作的集合。也可以说，把一次应用业务处理过程 ，从输入开始到输出结束，用户要求计算机所做的相关该次业务处理的全部工作，称为一个作业。,2作业步 通常，一个作业可以划分成若干个相对独立的步骤，每个步骤称为一个作业步。 3作业流 作业流是由若干个作业组成的。在批处理系统中，通常把一批作业或按用户提交次序，或按某种算法次序依次安放到相应的输入装置上，在系统的控制下，依次输入到后援存储器中等待运行，从而形成一个作业流。 4作业的分类 依据计算机系统的作业处理方式不同，可把作业分成两大类：脱机作业和联机作业。,5作
3、业管理的功能 作业管理的功能包括作业调度和作业控制。所谓作业调度，就是按照某种作业调度算法从后备作业队列中选择作业进入内存并运行。作业控制就是按照作业控制语言的解释程序读取用户作业说明书，具体控制作业的执行，并按照规定的步骤对作业进行处理。,3.2 分级调度,一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历以下三级调度：即作业调度、对换和进程调度。,第 3章 处理机调度与死锁,6,1作业调度 作业调度又称为高级调度或长调度，用于选择把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源。然后，再将新创建的进程排在就绪队列上，准备执行。在
4、批处理系统中，需要有作业调度的过程，以便将它们分批地装入内存。无须再配置作业调度机制。在分时系统和实时系统中，通常也不需要作业调度。,第 3章 处理机调度与死锁,7,2对换,又称交换调度或中级调度。其主要任务是按照给定的原则和策略，将处于外存交换区中的就绪状态或等待状态的进程调入内存，或把处于内存就绪状态或内存等待状态的进程交换到外存交换区。,第 3章 处理机调度与死锁,8,3进程调度,进程调度又称为低级调度或微观调度。其主要任务是按照某种策略和算法，将处理机分配给一个处于就绪状态的进程。进程调度可分为下列两种方式： （1） 非抢占方式：非抢占方式不允许进程抢占已经分配出去的处理机。 （2）
5、抢占方式 ：抢占调度方式允许调度程序根据某种原则，暂停某个正在执行的进程，将处理机收回，重新分配给另一个进程。,第 3章 处理机调度与死锁,9,第 3章 处理机调度与死锁,3.3 作业调度,作业调度主要是完成作业从后备状态到执行状态的转换，以及从执行状态到完成状态的转换。,第 3章 处理机调度与死锁,11,3.3.1 作业调度的功能,1记录系统中各作业的状态 2从后备队列中挑选出一部分作业投入执行。作业调度程序根据选定的调度算法，从后备作业队列中挑选出若干作业去投入执行。 3为被选中作业做好执行前的准备工作。作业调度程序为选中的作业建立相应的进程，并为这些进程分配它们所需要的系统资源，如分配给
6、它们内存、外存、外设等。 4在作业执行结束时做好善后处理工作。包括输出作业管理信息；回收该作业所占用的资源；撤销与该作业有关的全部进程和该作业的作业控制块等等。,第 3章 处理机调度与死锁,12,按调度算法，从后备 作业中选出一作业,调用存储管理、设备管理程序，审核资源要求,分配资源,调用进程管理 程序建立进程,进程调度,放弃该 作业,调用存储管理， 设备管理回收 分配给该作业 的全部资源,调用会计程序，计算 该作业的执行费用,撤销该作业的所有 进程及作业的JCB,调度下一个作业,后备作业 队列空,资源要求 能满足？,是,出口,否,否,图3-3 (a) 作业从后备状态到执行状态 (b)作业从执
7、行状态到完成状态,是,第 3章 处理机调度与死锁,13,3.3.2 调度算法的评价及准则,1面向用户的准则 2面向系统的准则,14,1面向用户的准则 （1）周转时间短 周转时间：是指作业被提交给系统开始，到作业终止为止的这段时间间隔，也称为作业周转时间。它包括四部分时间： a作业在外存后备队列上等待调度的时间。 b进程在就绪队列上等待进程调度的时间。 c进程占用CPU执行的时间。 d进程等待I/O操作完成的时间。,第 3章 处理机调度与死锁,15,作业i的周转时间Ti可定义为： Ti=TeiTsi 其中，Tei为作业i的完成时间，Tsi为作业i的提交时间。 平均周转时间为： T= 作业的周转时
8、间T与系统为它提供服务的时间（即作业要求运行时间）Ts之比，称为带权周转时间，即：,第 3章 处理机调度与死锁,16,带权周转时间 WTs 因为周转时间 T=等待时间+运行时间Ts， 因此，W也可表示为： W1+等待时间运行时间 从公式可以看出，W1，即W的最小值为1。可以看出，带权周转时间越接近1，则该作业相对等待时间越短，系统性能越高。 而平均带权周转时间可表示为： W=,第 3章 处理机调度与死锁,17,（）响应时间快,所谓响应时间，是指从用户提交一个作业请求开始，直至系统首次产生响应为止的时间。它包括三部分时间： 从键盘输入的请求信息传送到处理机的时间。 处理机执行响应处理的时间。 将
9、所形成的响应信息在终端显示器上显示出来的时间。 （）截止时间的保证。所谓截止时间，是指某任务必须开始执行的最晚时间，或必须完成的最晚时间。 （）优先权准则。调度程序根据任务的优先权确定先选中哪个作业。,第 3章 处理机调度与死锁,18,2面向系统的准则,（）系统的吞吐量。 （）处理机的利用率。 （）各类资源的平衡利用。,第 3章 处理机调度与死锁,19,3.4 进程调度,3.4.1 进程调度的功能 进程调度的功能可总结为如下几个方面： 1记录系统中所有进程的执行情况 2从就绪态队列中选择一个进程 3进行进程上下文的切换,第 3章 处理机调度与死锁,20,3.4.2 进程调度的时机,在并发执行的
10、环境下，引起进程调度的事件有： 1完成任务 2等待资源 3运行时间到 4进入睡眠状态 5发现标志 6优先级变化,第 3章 处理机调度与死锁,21,3.4.3 进程上下文的切换,进程的上下文由正文段、数据段、硬件寄存器的内容以及有关的数据结构组成。进程上下文的切换主要包括以下四个方面： 1决定是否要做及是否允许做上下文切换 2保存当前执行进程的上下文 3选择一个处于就绪态的进程 4使被选中的进程执行,第 3章 处理机调度与死锁,22,3.4.4 Linux系统中进程调度发生的时机,通常，Linux系统中的进程调度发生的时机有以下几种： 1用户创建一个新的进程时。 2正在执行的进程在申请资源或者等
11、待某个事件的发生，得不到满足时。 3分时系统中，进程执行完一定的时间片之后，释放CPU资源。 4Linux系统提供了两级保护，当进程从核心态返回到用户态时，将会调用调度函数，发生调度。,第 3章 处理机调度与死锁,23,3.5 调度算法,3.4.1 单道批处理系统的调度算法 3.5.1 先来先服务（FCFS）调度算法 先来先服务（FCFS）调度算法既可用于作业调度，也适用于进程调度。该算法是按照作业或进程到达的先后次序来进行调度。 3.5.2 短作业（进程）优先调度算法 短作业调度算法（SJF）或短进程调度算法（SPF），是指对短作业或短进程优先调度的算法。 短作业优先调度算法对短作业带来明显
12、的改善，同时降低了作业的平均周转时间，提高了整个系统的性能。,第 3章 处理机调度与死锁,24,SJ(P)F调度算法也存在一些不容忽视的缺点： （1）该算法对长作业不利。 （2）该算法未考虑作业的紧迫度，因而不能保证紧迫作业的及时处理。 （3）致使不一定保证做到真正意义上的短作业优先调度。,第 3章 处理机调度与死锁,25,3.5.3 高响应比优先调度算法,高响应比优先调度算法又称为HRN调度算法。响应比R可定义如下： R（已等待时间要求服务时间）要求服务时间 即：R1已等待时间要求服务时间 对于同样长度的作业，其R值可以从其等待调度的时间长短来区分；同样等待时间的作业，要求执行时间少的作业R
13、值高。因此，它既照顾了短作业，又考虑了作业的等待时间。当然，在利用该算法时，每次在进行调度之前，都要先计算相应比，因此增加了系统的开销,第 3章 处理机调度与死锁,26,3.5.4 优先级调度算法,优先级调度算法也叫做优先权调度算法，可做为作业调度或进程调度策略。这种算法可用于批处理系统，也可用于实时系统中 。 1. 优先级的类型 在优先级调度算法中，优先级用来表示作业或进程所享有的调度优先权。该算法的关键是确定进程或作业的优先级。确定优先级的方法有两类： 1） 静态优先级 静态优先级是在创建进程时确定的，且在进程的整个运行期间保持不变。 （2）动态优先级 动态优先级是指，在创建进程时所赋予的
14、优先级，是随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。,第 3章 处理机调度与死锁,27,2优先级调度算法的类型 （1）非抢占式优先级调度算法 （2）抢占式优先级调度算法,第 3章 处理机调度与死锁,28,例3：有一个具有两道作业的批处理系统，作业调度采用短作业优先的调度算法，进程调度采用以优先数为基础的抢占式调度算法，假设优先数小的优先级别高。如下表所示的作业序列。 （1）列出所有作业进入内存的时间及作业结束时间。 （2）计算平均周转时间。,第 3章 处理机调度与死锁,29,解： （1）各作业进入时间和结束时间如下：,第 3章 处理机调度与死锁,30,（2）根据周转时间
15、=完成时间提交时间，可得各作业的周转时间为： TA=11：1010：00=70（分钟） TB=10：5010：20=30（分钟） TC=12：0010：30=90（分钟） TD=12：2010：50=90（分钟） 平均周转时间（TA + TB + TC + TD ）/4=70（分钟）,第 3章 处理机调度与死锁,31,3.5.5 时间片轮转法,时间片轮转法（RR算法）主要用于分时系统中的进程调度。系统把所有就绪进程按先入先出的原则排成一个队列。新来的进程加到就绪队列末尾。每当执行进程调度时，就绪队列的队首进程总是先被调度程序选中，让它在CPU上运行一个时间片的时间。,第 3章 处理机调度与死锁
16、,32,例4：考虑下述四个进程A、B、C和D的执行情况。设它们依次进入就绪队列，但前后时间忽略不计。四个进程分别需要运行12，5，3和6个时间单位。如下表所示。 计算当时间片分别为q=1、q=4时各进程的开始运行时间、完成时间、周转时间及带权周转时间。,第 3章 处理机调度与死锁,33,例4表,第 3章 处理机调度与死锁,34,解：通过分析及计算，我们可以得到下表：,平均周转时间T=18.5 平均带权周转时间,平均周转时间T=19.75 平均带权周转时间,当q=1、q=4时，RR调度算法的比较,第 3章 处理机调度与死锁,35,3.5.6 多级队列调度算法,多级队列轮轮调度算法（multiple-level Queue,MLQ）是先来先服务调度算法、时间片轮转算法和优先级算法的综合。
