六章节处理机调度

《六章节处理机调度》由会员分享，可在线阅读，更多相关《六章节处理机调度（38页珍藏版）》请在装配图网上搜索。

1、第六章第六章 处理机调度处理机调度（一）（一）处理机的多级调度处理机的多级调度（二）（二）作业调度作业调度（三）（三）进程调度进程调度（一）（一）处理机的多级调度处理机的多级调度一一.处理机调度的功能处理机调度的功能n 确定数据结构n 制定调度策略（调度原则）n 给出调度算法n 具体的实施处理机分派不同类型的操作系统往往采用不同的处理机分配方法。二二.处理机调度的分层实现处理机调度的分层实现只有内存的程序才能在CPU上运行。因此，处理机的调度通常分为两层：n 宏观上：作业调度 对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。n 微观上

2、：进程调度 对进入注册的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。三三.批处理系统中的处理机调度批处理系统中的处理机调度四四.多任务操作系统中的处理机调度多任务操作系统中的处理机调度在分时系统或支持多任务并发执行的个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。进程调度的任务任务是：当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。另外，由于分时系统中的作业调度功能很弱（甚至没有），因此有些分时系统会将进程在内、外存之间进行交换。由于进程仍然存在，也与处理机的分配无关，故称为中级调度。五五.多线程

3、操作系统中的处理机调度多线程操作系统中的处理机调度在支持多线程运行的系统中，每个进程都创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配的对象则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。（二）（二）作业调度作业调度一一.作业的状态作业的状态 作业在整个活动期间一共有四种状态：提交状态提交状态：用户将自己的程序和数据提交给系统，等待输入。后备状态后备状态：作业已存放在磁盘上，等待掉进主存。执行状态执行状态：作业在主存中运行。完成状态完成状态：作业计算完成开始，退出主存。作业调度的主要任务是完成作业从后备状

4、态到执行状态和从执行状态到完成状态的转变。二二.作业调度的功能作业调度的功能n确定数据结构建立作业控制块（JCB，Job Control Block），记录已进入系统的各作业的情况（类型、状态、资源请求与分配等）；n确定调度策略与调度算法n分配资源为被选中的作业创建进程，并且为其申请系统资源；n善后处理收回作业占用的全部资源，撤销作业控制块以及与该作业有关的全部进程。三三.作业控制块（作业控制块（JCBJCB，Job Control BlockJob Control Block）n每个作业进入系统时由系统为其建立一个作业控 制 块 J C B（J o b Control Block)，它是存放

5、作业控制和管理信息的数据结构，是作业存在的标志，主要信息见右图。四四.作业调度算法性能的衡量作业调度算法性能的衡量作业调度算法规定了从后备作业中选择作业进入系统内存的原则。1.1.确定调度算法时应考虑的因素确定调度算法时应考虑的因素(1)应与系统的整体设计目标一致(2)考虑系统中各种资源的负载均匀(3)保证作业的执行(4)对一些专用资源的使用特性的考虑2.2.调度性能的衡量调度性能的衡量通常采用平均周转时间和带权平均周转时间来衡量作业调度算法性能的好坏。(1)周转时间周转时间：一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。n定义定义：ti=tci-tsi ti：作业周转时间tc

6、i：作业完成时间 tsi:作业提交时间n意义意义：说明作业i在系统中停留的时间长短n平均周转时间平均周转时间：n定义定义：一个作业的周转时间与其运行时间的比值比值n意义意义：说明作业i在系统中的相对相对等待时间。(3)平均带权周转时间平均带权周转时间：n精确度精确度：高于周转时间和平均周转时间另外，还可以用CPU的利用率和吞吐量来衡量。五五.作业调度算法作业调度算法1.1.先来先服务调度算法先来先服务调度算法(FCFS)(FCFS)：n策略策略：作业来到的先后次序来到的先后次序进行调度n特点特点：每次选择的作业是等待时间最久的，而不管作业运行时间的长短。这种调度算法突出的优点是实现简单实现简单

7、，效率较低效率较低，在一些实际的系统和一般应用程序中采用这种算法的较多。2.2.短作业优先调度算法短作业优先调度算法n策略策略：考虑作业的运行时间，每次总是选择一个请求运行时间最小运行时间最小的作业调入内存（系统）。n特点特点：易实现，系统吞吐量高。只考虑短作业，而没有考虑长作业的利益。相对先来先服务调度算法实现要困难些，如果作业的到来顺序及运行时间不合适，会出现饿死饿死现象。3.3.响应比高者优先调度算法响应比高者优先调度算法响应比高者优先调度算法是介于这两种算法之间的一种折衷的算法。响应比 响应时间/执行时间 1 等待时间/执行时间一个作业时，计算后备作业表中每个作业的响应比，挑选响应比高

8、者投入运行。这种算法从理论上讲是比较完备的，但作业调度程序要统计作业的等待时间，使用用户的估计的运行时间，并要作浮点运算（这是系统程序最忌讳的）浪费大量的计算时间，这是系统程序所不允许的。4.4.优先数调度算法优先数调度算法优先数调度算法综合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何终合考虑，这些因素之间的关系怎样处理。5.5.均衡调度算法均衡调度算法均衡调度算法是一种更为理想化的调度算法，如何实现更困难，并且算法本身的开销有时会远远大于先来先服务和

9、小作业优先调度算法的不足，这也是这两种算法被众多系统采用的最根本的原因。UnixUnix调度算法调度算法nUNIX系统采用优先数调度算法优先数调度算法n进程有一个进程优先数p_prip_prinp_pri取值范围是127127，其值越小，进程的优先级越高1.1.优先数的确定优先数的确定n进入睡眠状态设置优先数0进程（100优先数）；资源请求得不到满足的进程，磁盘（80），打印机（20），；等待块设备I/O完成的进程(50)；等待字符设备I/O完成的进程(020）；所有处于用户态运行进程同步（一般情况下为大于100）。目的目的 充分利用系统资源，即提高系统资源的使用效率2.2.优先数的计算优先数

10、的计算（1）计算公式：p_pri=min127,(p_cpu/16+p_nice+PUSER)其中：p_cpu 进程占用CPU的程度R1:R1=Tu/(Tu+Tnu)Tu:进程创建后占用CPU的累计值Tnu：进程生成后没有占用CPU的累计值p_nice 用户通过系统调用nice(priority)设置的进程优先数。PUSER 常数，其值为100大量的统计工作，并且要做浮点运算UINXUINX系统中对系统中对p_cpup_cpu的处理：的处理：每个时钟中断当前占用处理机的进程的 p_cpu+;每秒钟（时钟中断）（对所有进程）：if(p_cpu-SCHMAG 0处理机调度处理机调度switch（）

11、（）保护现场、形成调用中断处理程序的参数调具体中断处理程序中断返回NNY YNNY Y防止优先级反转，强迫调度runrun标志大于0是说明系统中处于就绪状态的进程的优先级高于现运行进程的优先级，这时要进行强迫调度。两种可能（调度时机）：睡眠进程唤醒后；重新计算进程的优先数后(包括当一个进程占用一段时间的CPU后，它的优先级要降低)。四四.调度用的进程状态变迁图调度用的进程状态变迁图右图中新创建的进程进入低优就绪状态，一个运行进程因时间片到（实际上是计算量大的进程）而转换成低优就绪；进程因等待I/O完成而转换高优就绪.通过进程调度变迁图，可反映系统的进程调度的各种特征。1.1.队列结构队列结构n

12、I/O等待对列一个进程如果请求I/O，则进入I/O等待队列；n低优先就绪队列一个进程如果在运行中超过了分配给它的时间片，就进入低优先就绪n高优先就绪队列当进程从等待状态变为就绪状态时，则进入高优先就绪队列。2.2.进程调度算法进程调度算法n当CPU空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为100ms。n当CPU空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为500ms。优先调度与时间片调度相结合的调度策略优先调度与时间片调度相结合的调度策略3.3.调度效果调度效果优先照顾了I/O量大的进程；适当照顾了计算量大的进程。五五.进

13、程调度算法进程调度算法1.进程优先数调度算法进程优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。n静态：n进程的优先数在进程创建时确定后就不再变化n确定进程优先数：系统确定系统确定：（运行时间、使用资源，进程的类型）用户确定用户确定：（紧迫程度，计费与进程优先数有关）系

14、统与用户结合（用户可以为本用户的进程设置优先数，但不是作调度用，系统还要根据系统情况把用户设置的进程优先数作为确定进程优先数的一个参数）n动态动态：系统在运行的过程中，根据系统的设计目标，不断地调整进程的优先数，这种方法的优点是能比较客观地反映进程的实际情况和保证达到系统设计目标2.循环轮转调度算法循环轮转调度算法循环轮转调度实际上是一种先来先服务算法的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程让出CPU，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。简单循环轮转调度n 实现简单、系统开销小

15、。n 不灵活，当系统中进程较多时，系统开销变大。n 可变时间片轮转调度n时间片的大小可变，系统可根据系统中当前的进程数来确定时间片的大小。例：Q=T/NnT：系统响应时间，一般为1秒，具体大小由系统设计时根据系统设计目标确定。nN：系统中进程的个数，也由系统设计时确定，或者通过系统配置文件，由系统管理员确定。第六章第六章 小结小结一一.处理机的二级调度处理机的二级调度二二.作业调度作业调度 1.作业的状态 2.作业控制块 3.作业调度的功能 4.周转时间、带权周转时间：定义、物理意义 5.常用的作业调度算法先来先服务 短作业优先第六章第六章 小结小结三三.进程调度进程调度1.进程调度的功能2.调度方式：非剥夺方式剥夺方式3.常用的进程调度算法：优先数调度循环轮转调度 4.调度用的进程状态变迁图（多种进程状态及变迁）