第6章处理机调度课件

(一一)处理机的多级调度处理机的多级调度(二二)作业调度作业调度(三三)进程调度进程调度第六章第六章 处理机调度处理机调度1 (一一一一)处理机的多级调度处理机的多级调度处理机的多级调度处理机的多级调度一一.处理机调度的功能处理机调度的功能 确定数据结构确定数据结构 制订调度策略制订调度策略(调度原则调度原则)给出调度算法给出调度算法 具体的实施处理机分派具体的实施处理机分派不同类型的操作系统往往采用不同的处理机分配方法。不同类型的操作系统往往采用不同的处理机分配方法。2 二二二二.批处理系统中的处理机调度批处理系统中的处理机调度批处理系统中的处理机调度批处理系统中的处理机调度处理机调度分为两级：作业调度和进程调度。处理机调度分为两级：作业调度和进程调度。处理机调度分为两级：作业调度和进程调度。处理机调度分为两级：作业调度和进程调度。1.1.作业调度作业调度作业调度作业调度作业调度又称为宏观调度。作业调度又称为宏观调度。作业调度又称为宏观调度。作业调度又称为宏观调度。任务任务任务任务对存放在辅存设备上的大量作业，以一定的策略对存放在辅存设备上的大量作业，以一定的策略对存放在辅存设备上的大量作业，以一定的策略对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，进行挑选，分配主存等必要的资源，建立作业对应的进程，进行挑选，分配主存等必要的资源，建立作业对应的进程，进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。使其投入运行。使其投入运行。使其投入运行。2.2.进程调度进程调度进程调度进程调度进程调度又称为微观调度进程调度又称为微观调度进程调度又称为微观调度进程调度又称为微观调度。任务任务任务任务对进入主存的所有进程，确定哪个进程在什么时对进入主存的所有进程，确定哪个进程在什么时对进入主存的所有进程，确定哪个进程在什么时对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。候获得处理机，使用多长时间。候获得处理机，使用多长时间。候获得处理机，使用多长时间。3 三三三三.多任务操作系统中的处理机调度多任务操作系统中的处理机调度多任务操作系统中的处理机调度多任务操作系统中的处理机调度在分时系统或支持多任务并发执行个人计算机操作系统在分时系统或支持多任务并发执行个人计算机操作系统在分时系统或支持多任务并发执行个人计算机操作系统在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以中，系统将用户提交的任务处理为进程，一个进程又可以中，系统将用户提交的任务处理为进程，一个进程又可以中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。创建多个子进程，形成可以并发执行的多进程。创建多个子进程，形成可以并发执行的多进程。创建多个子进程，形成可以并发执行的多进程。进程调度的任务是：当处理机空闲时，以某种策略选择进程调度的任务是：当处理机空闲时，以某种策略选择进程调度的任务是：当处理机空闲时，以某种策略选择进程调度的任务是：当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。一个就绪进程去运行，并分配处理机的时间。一个就绪进程去运行，并分配处理机的时间。一个就绪进程去运行，并分配处理机的时间。4四四四四.多线程操作系统中的处理机调度多线程操作系统中的处理机调度多线程操作系统中的处理机调度多线程操作系统中的处理机调度在支持多线程运行的系统中，一个进程可以创建一个线在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。程，也可以创建多个线程。系统为进程分配它所需要的资系统为进程分配它所需要的资源源，而，而处理机的分配单位则为线程处理机的分配单位则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。某种策略选择一个就绪线程去运行，并分配处理机时间。5 (二二二二)作业调度作业调度作业调度作业调度一一一一.作业的状态作业的状态作业的状态作业的状态作业在整个活动期间一共有四种状态，作业在整个活动期间一共有四种状态，作业在整个活动期间一共有四种状态，作业在整个活动期间一共有四种状态，提交状态：用户将自己的程序和数据提交给系统，等待提交状态：用户将自己的程序和数据提交给系统，等待提交状态：用户将自己的程序和数据提交给系统，等待提交状态：用户将自己的程序和数据提交给系统，等待输入。输入。输入。输入。后备状态：作业已存放在磁盘上，等待调度。后备状态：作业已存放在磁盘上，等待调度。后备状态：作业已存放在磁盘上，等待调度。后备状态：作业已存放在磁盘上，等待调度。执行状态：作业进入主存开始运行。执行状态：作业进入主存开始运行。执行状态：作业进入主存开始运行。执行状态：作业进入主存开始运行。完成状态：作业计算完成开始，退出系统。完成状态：作业计算完成开始，退出系统。完成状态：作业计算完成开始，退出系统。完成状态：作业计算完成开始，退出系统。6运行就绪完成等待后备提交作业调度作业调度作业录入执行运行运行就绪就绪完成完成等待等待后备后备提交提交作业作业调度调度作业作业调度调度作业作业录入录入执行执行运行运行就绪就绪完成完成等待等待后备后备提交提交作业作业调度调度作业作业调度调度作业作业录入录入执行执行7 二二二二.作业调度的功能作业调度的功能作业调度的功能作业调度的功能 1.确定数据结构确定数据结构建立作业控制块建立作业控制块jcb(jobcontrolblock)。作业控制块记录了每个作业类型、状态、资源请求及分作业控制块记录了每个作业类型、状态、资源请求及分配情况配情况。2.确定调度策略与调度算法确定调度策略与调度算法3.分配资源分配资源为选中的作业分配所需要的系统资源。为选中的作业分配所需要的系统资源。4.善后处理善后处理收回该作业所占用的全部资源，撤消作业控制块以及与收回该作业所占用的全部资源，撤消作业控制块以及与该作业有关的全部进程。该作业有关的全部进程。8 三三三三.作业控制块作业控制块作业控制块作业控制块作业控制块作业控制块jcb存在于系统的整个过程中，存在于系统的整个过程中，jcb是一个作业是一个作业存在的标志。存在的标志。jcb的主要内容如下：的主要内容如下：作作业业名名 资资源源要要求求（用户提供）（用户提供）资资源源使使用用情况情况估计执行时间估计执行时间进入系统时间进入系统时间 最迟完成时间最迟完成时间开始执行时间开始执行时间 要求的主存量要求的主存量已执行时间已执行时间 要求外设的类型及台数要求外设的类型及台数主存地址主存地址 要求文件量和输出量要求文件量和输出量外设台号外设台号 类类型型 优优先先级级 控制方式（联机控制方式（联机/脱机）脱机）状状态（后备态（后备/执行执行/完成）完成）作业类型（作业类型（CPU偏多，偏多，I/O偏多，均衡）偏多，均衡）9 四四四四.作业调度算法性能的衡量作业调度算法性能的衡量作业调度算法性能的衡量作业调度算法性能的衡量采用采用平均周转时间平均周转时间和和平均带权周转时间平均带权周转时间来衡量作业调度来衡量作业调度算法性能的好坏。算法性能的好坏。1.周转时间周转时间一个作业提交给计算机系统到该作业的结果返回给用户一个作业提交给计算机系统到该作业的结果返回给用户所需要的时间。所需要的时间。(1)定义定义ti=tci-tsiti作业作业i的周转时间的周转时间tsi作业作业i的提交时间的提交时间 tci作业作业i的完成时间的完成时间(2)意义意义说明作业说明作业i在系统中停留时间的长短。在系统中停留时间的长短。(3)平均周转时间平均周转时间t=n n为进入系统的作业个数为进入系统的作业个数10 2.2.带权周转时间带权周转时间带权周转时间带权周转时间(1)(1)定义定义定义定义 一个作业的周转时间与其运行时间的比值。一个作业的周转时间与其运行时间的比值。一个作业的周转时间与其运行时间的比值。一个作业的周转时间与其运行时间的比值。wiwi=(2)(2)意义意义意义意义 说明作业说明作业说明作业说明作业i i在系统中相对等待时间。在系统中相对等待时间。在系统中相对等待时间。在系统中相对等待时间。(3)(3)平均带权周转时间平均带权周转时间平均带权周转时间平均带权周转时间 t=t=tritri为作业的实际执行时间为作业的实际执行时间11 五五五五.作业调度算法作业调度算法作业调度算法作业调度算法1.1.先来先服务调度算法先来先服务调度算法先来先服务调度算法先来先服务调度算法(FCFS)(FCFS)(1)(1)策略：按作业来到的先后次序进行调度。策略：按作业来到的先后次序进行调度。策略：按作业来到的先后次序进行调度。策略：按作业来到的先后次序进行调度。(2)(2)特点：特点：特点：特点：简单，易实现。简单，易实现。简单，易实现。简单，易实现。(3)(3)讨论在先来先服调度算法下的周转时间与带权周转时间讨论在先来先服调度算法下的周转时间与带权周转时间讨论在先来先服调度算法下的周转时间与带权周转时间讨论在先来先服调度算法下的周转时间与带权周转时间 作业作业作业作业 提交时间提交时间提交时间提交时间执行时间执行时间执行时间执行时间 开始时间开始时间开始时间开始时间 完成时间完成时间完成时间完成时间 周转时间周转时间周转时间周转时间 带权周转时带权周转时带权周转时带权周转时间间间间18.0018.002.002.00 228.508.500.500.50339.009.000.100.1049.500.2049.500.20 8.00 10.00 2.00 1 10.00 10.50 2.00 4 10.50 10.60 1.60 16 10.60 10.80 1.30 6.5 平均周转时间平均周转时间t=平均带权周转时间平均带权周转时间w=1.7256.87512 五五五五.作业调度算法作业调度算法作业调度算法作业调度算法 2.2.短作业优先调度算法短作业优先调度算法短作业优先调度算法短作业优先调度算法(1)策略：按作业按作业请求运行的时间长短进行调度。策略：按作业按作业请求运行的时间长短进行调度。(2)特点：易实现，系统吞吐量高；只照顾短作业，而没有特点：易实现，系统吞吐量高；只照顾短作业，而没有考虑长作业的利益易实现。考虑长作业的利益易实现。(3)讨论短作业优先调度算法下的周转时间与带权周转时间讨论短作业优先调度算法下的周转时间与带权周转时间作业作业提交时间提交时间执行时间执行时间开始时间开始时间完成时间完成时间周转时间周转时间带权周转时带权周转时间间 1 8.001 8.00 2.00 2.00 2 28.508.50 0.50 0.50 3 39.00 9.00 0.10 0.10 4 9.50 0.20 4 9.50 0.20 平均周转时间平均周转时间t=平均带权周转时间平均带权周转时间w=1.555.15 8.00 10.00 2.00 1 10.30 10.80 2.30 4.6 10.00 10.10 1.10 11 10.10 10.30 0.80 4 13先来先服务调度算法和短作业优先调度算法（比较）先来先服务调度算法和短作业优先调度算法（比较）先来先服务调度算法和短作业优先调度算法（比较）先来先服务调度算法和短作业优先调度算法（比较）143.3.3.3.响应响应响应响应比高者优先调度算法：比高者优先调度算法：比高者优先调度算法：比高者优先调度算法：先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先算算算算法法法法都都都都有有有有其其其其片片片片面面面面性性性性，先先先先来来来来先先先先服服服服务务务务调调调调度度度度算算算算法法法法只只只只考考考考虑虑虑虑作作作作业业业业的的的的等等等等待待待待时时时时间间间间，而而而而忽忽忽忽视视视视了了了了作作作作业业业业的的的的运运运运行行行行时时时时间间间间，短短短短作作作作业业业业优优优优先先先先算算算算法法法法则则则则相相相相反反反反，只只只只考考考考虑虑虑虑了了了了作作作作业业业业的的的的运运运运行行行行时时时时间间间间，而而而而忽忽忽忽视视视视了了了了作作作作业业业业的的的的等等等等待待待待时时时时间间间间。响响响响应应应应比比比比高高高高者者者者优优优优先先先先调调调调度度度度算算算算法法法法是是是是介介介介于于于于这这这这两两两两种种种种算法之间的一种算法之间的一种算法之间的一种算法之间的一种折中折中折中折中的算法。的算法。的算法。的算法。15作业作业作业作业 提交时间提交时间提交时间提交时间执行时间执行时间执行时间执行时间 开始时间开始时间开始时间开始时间 完成时间完成时间完成时间完成时间 周转时间周转时间周转时间周转时间 带权周转时间带权周转时间带权周转时间带权周转时间18.0018.002.002.00 228.508.500.500.50339.009.000.100.1049.500.2049.500.20 8.00 10.00 2.00 1 10.00 10.10 1.10 11 作业作业作业作业1 1 1 1执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比响应比响应比响应比响应比2=1+2=1+2=1+2=1+（10.00 8.5010.00 8.5010.00 8.5010.00 8.50）/0.5=1+3=4/0.5=1+3=4/0.5=1+3=4/0.5=1+3=4响应比响应比响应比响应比3=1+3=1+3=1+3=1+（10.00 9.0010.00 9.0010.00 9.0010.00 9.00）/0.1=1+10/0.1=1+10/0.1=1+10/0.1=1+10 =11=11=11=11响应比响应比响应比响应比4=1+4=1+4=1+4=1+（10.00 9.5010.00 9.5010.00 9.5010.00 9.50）/0.2=1+2.5=3.5/0.2=1+2.5=3.5/0.2=1+2.5=3.5/0.2=1+2.5=3.5因为作业因为作业因为作业因为作业3 3 3 3的响应比最高，所以选择作业的响应比最高，所以选择作业的响应比最高，所以选择作业的响应比最高，所以选择作业3 3 3 3执行执行执行执行作业作业作业作业3 3 3 3执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比执行之后，计算其余作业的响应比响应比响应比响应比响应比2=1+2=1+2=1+2=1+（10.10 8.5010.10 8.5010.10 8.5010.10 8.50）/0.5=1+3.2=4.2/0.5=1+3.2=4.2/0.5=1+3.2=4.2/0.5=1+3.2=4.2响应比响应比响应比响应比4=1+4=1+4=1+4=1+（10.10 9.5010.10 9.5010.10 9.5010.10 9.50）/0.2=1+3=4/0.2=1+3=4/0.2=1+3=4/0.2=1+3=4因为作业因为作业因为作业因为作业2 2 2 2的响应比较高，所以选择作业的响应比较高，所以选择作业的响应比较高，所以选择作业的响应比较高，所以选择作业2 2 2 2执行执行执行执行 10.10 10.60 2.10 4.2 10.60 10.80 1.30 6.5 平均周转时间平均周转时间t=1.625平均带权周转时间平均带权周转时间w=5.67516 响应比高者优先调度算法的响应比高者优先调度算法的响应比高者优先调度算法的响应比高者优先调度算法的特点特点特点特点n n响响响响应应应应比比比比高高高高者者者者优优优优先先先先调调调调度度度度算算算算法法法法其其其其调调调调度度度度性性性性能能能能不不不不如如如如短短短短作作作作业业业业优优优优先先先先算算算算法法法法好好好好，但但但但它它它它及及及及照照照照顾顾顾顾到到到到用用用用户户户户到到到到来来来来先先先先后后后后，又又又又考考考考虑虑虑虑到到到到系系系系统统统统服服服服务务务务时间长短，从时间长短，从时间长短，从时间长短，从理论上讲是比较理论上讲是比较理论上讲是比较理论上讲是比较完备的调度算法。完备的调度算法。完备的调度算法。完备的调度算法。n n但但但但作作作作业业业业调调调调度度度度程程程程序序序序要要要要统统统统计计计计作作作作业业业业的的的的等等等等待待待待时时时时间间间间，使使使使用用用用用用用用户户户户的的的的估估估估计计计计的的的的运运运运行行行行时时时时间间间间，并并并并要要要要作作作作浮浮浮浮点点点点运运运运算算算算（这这这这是是是是系系系系统统统统程程程程序序序序最最最最忌忌忌忌讳讳讳讳的）浪费大量的计算时间，这是系统程序所不允许的）浪费大量的计算时间，这是系统程序所不允许的）浪费大量的计算时间，这是系统程序所不允许的）浪费大量的计算时间，这是系统程序所不允许的。的。的。的。174.4.4.4.优先数调度优先数调度优先数调度优先数调度算法算法算法算法 优优优优先先先先数数数数调调调调度度度度算算算算法法法法是是是是综综综综合合合合考考考考虑虑虑虑各各各各方方方方面面面面的的的的因因因因素素素素（作作作作业业业业等等等等待待待待时时时时间间间间、运运运运行行行行时时时时间间间间、缓缓缓缓急急急急程程程程度度度度，系系系系统统统统资资资资源源源源使使使使用用用用等等等等），给给给给每每每每个个个个作作作作业业业业设设设设置置置置一一一一个个个个优优优优先先先先数数数数，调调调调度度度度程程程程序序序序总总总总是是是是选选选选择择择择一一一一个个个个优优优优先先先先数数数数最最最最大大大大（或或或或者者者者最最最最小小小小）的的的的作作作作业业业业调调调调入入入入（系系系系统统统统）内内内内存存存存。这这这这种种种种算算算算法法法法实实实实现现现现的的的的困困困困难难难难在在在在于于于于如如如如何何何何综综综综合合合合考考考考虑虑虑虑，这这这这些些些些因因因因素素素素之之之之间间间间的的的的关关关关系系系系怎怎怎怎样样样样处理。处理。处理。处理。算法思想：算法思想：算法思想：算法思想：计算优先数，确定优先级，根据优先级大小挑选作业。计算优先数，确定优先级，根据优先级大小挑选作业。计算优先数，确定优先级，根据优先级大小挑选作业。计算优先数，确定优先级，根据优先级大小挑选作业。例如，例如，例如，例如，优先数优先数优先数优先数 =等待时间等待时间等待时间等待时间2 2 2 2 要求执行时间要求执行时间要求执行时间要求执行时间 16*16*16*16*输出量输出量输出量输出量特点：特点：特点：特点：迅迅迅迅速速速速地地地地执执执执行行行行一一一一个个个个短短短短作作作作业业业业，但但但但偶偶偶偶尔尔尔尔也也也也要要要要执执执执行行行行一一一一个个个个在在在在磁磁磁磁盘盘盘盘中中中中等等等等待待待待了了了了很很很很久久久久的作业。此时的作业。此时的作业。此时的作业。此时“等待时间等待时间等待时间等待时间”的值远远超过其他的值远远超过其他的值远远超过其他的值远远超过其他2 2 2 2项目的和项目的和项目的和项目的和185.5.5.5.均衡调度算法均衡调度算法均衡调度算法均衡调度算法 均均均均衡衡衡衡调调调调度度度度算算算算法法法法就就就就是是是是一一一一种种种种更更更更为为为为理理理理想想想想化化化化的的的的调调调调度度度度算算算算法法法法，如如如如何何何何实实实实现现现现就就就就更更更更困困困困难难难难，并并并并且且且且算算算算法法法法本本本本身身身身的的的的开开开开销销销销有有有有时时时时会会会会远远远远大大大大于于于于先先先先来先服务和短作业优先来先服务和短作业优先来先服务和短作业优先来先服务和短作业优先调度算法。调度算法。调度算法。调度算法。先先先先来来来来先先先先服服服服务务务务和和和和短短短短作作作作业业业业优优优优先先先先调调调调度度度度算算算算法法法法是是是是2 2 2 2种种种种开开开开销销销销较较较较小小小小的的的的算算算算法法法法，这这这这也也也也是是是是这这这这两两两两种种种种算算算算法法法法被被被被众众众众多多多多系系系系统统统统采采采采用用用用的的的的最最最最根根根根本本本本的的的的原因。原因。原因。原因。19 (三三三三)进程调度进程调度进程调度进程调度一一一一.调度调度调度调度/分派结构分派结构分派结构分派结构1.1.调度调度调度调度在众多处于就绪状态的进程中，按一定的原则选择一个进在众多处于就绪状态的进程中，按一定的原则选择一个进在众多处于就绪状态的进程中，按一定的原则选择一个进在众多处于就绪状态的进程中，按一定的原则选择一个进程。程。程。程。组织和维护就绪进程队列。包括确定调度算法、按调度算组织和维护就绪进程队列。包括确定调度算法、按调度算组织和维护就绪进程队列。包括确定调度算法、按调度算组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。法组织和维护就绪进程队列。法组织和维护就绪进程队列。法组织和维护就绪进程队列。2.2.分派分派分派分派当处理机空闲时，是移出就绪队列中第一个进程，并赋予当处理机空闲时，是移出就绪队列中第一个进程，并赋予当处理机空闲时，是移出就绪队列中第一个进程，并赋予当处理机空闲时，是移出就绪队列中第一个进程，并赋予它使用处理机的权利。它使用处理机的权利。它使用处理机的权利。它使用处理机的权利。n n 调调调调度度度度与与与与进进进进程程程程控控控控制制制制和和和和进进进进程程程程通通通通信信信信的的的的功功功功能能能能有有有有密密密密切切切切的的的的联联联联系系系系，当当当当一一一一个个个个进进进进程程程程阻阻阻阻塞塞塞塞时时时时，这这这这种种种种进进进进程程程程将将将将进进进进入入入入相相相相应应应应的的的的等等等等待待待待队队队队列列列列中中中中，并并并并让让让让出出出出CPUCPU，调调调调用用用用进进进进程程程程分分分分派派派派程程程程序序序序选选选选择择择择一一一一个个个个就就就就绪绪绪绪进进进进程程程程占占占占用用用用CPUCPU；当当当当一进程被唤醒时，这种进程将插入到就绪进程队列中。一进程被唤醒时，这种进程将插入到就绪进程队列中。一进程被唤醒时，这种进程将插入到就绪进程队列中。一进程被唤醒时，这种进程将插入到就绪进程队列中。n n在一般的操作系统教材中把上述功能称为进程调度。在一般的操作系统教材中把上述功能称为进程调度。在一般的操作系统教材中把上述功能称为进程调度。在一般的操作系统教材中把上述功能称为进程调度。20 3.3.调度调度调度调度 分派结构图分派结构图分派结构图分派结构图 ready_qschedulersuspwakeupreceive pcb6pcb4pcb3pcb2pcb1dispatcherCPU21 二二二二.进程调度的功能进程调度的功能进程调度的功能进程调度的功能1.1.记录和保持系统中所有进程的有关情况和状态特征记录和保持系统中所有进程的有关情况和状态特征记录和保持系统中所有进程的有关情况和状态特征记录和保持系统中所有进程的有关情况和状态特征 有有有有关关关关进进进进程程程程调调调调度度度度的的的的信信信信息息息息是是是是记记记记录录录录在在在在PCBPCB中中中中的的的的，在在在在进进进进程程程程调调调调度度度度中中中中用用用用到到到到的的的的主要是进程的状态、调度优先级（优先数）、就绪进程队列等。主要是进程的状态、调度优先级（优先数）、就绪进程队列等。主要是进程的状态、调度优先级（优先数）、就绪进程队列等。主要是进程的状态、调度优先级（优先数）、就绪进程队列等。2.2.决定分配（处理机）策略决定分配（处理机）策略决定分配（处理机）策略决定分配（处理机）策略确确确确定定定定进进进进程程程程调调调调度度度度的的的的策策策策略略略略，例例例例如如如如，先先先先来来来来先先先先服服服服务务务务、优优优优先先先先数数数数调调调调度度度度策策策策略略略略，调度策略的不同，组织就绪进程队列的方式也不同。调度策略的不同，组织就绪进程队列的方式也不同。调度策略的不同，组织就绪进程队列的方式也不同。调度策略的不同，组织就绪进程队列的方式也不同。优先调度原则优先调度原则优先调度原则优先调度原则进程就绪队列按进程优先级高低排序进程就绪队列按进程优先级高低排序进程就绪队列按进程优先级高低排序进程就绪队列按进程优先级高低排序 先来先服务原则先来先服务原则先来先服务原则先来先服务原则进程就绪队列按进程来到的先后次序排序进程就绪队列按进程来到的先后次序排序进程就绪队列按进程来到的先后次序排序进程就绪队列按进程来到的先后次序排序22 3.实施处理机的分配实施处理机的分配调度时机（调度时机（UNIX系统中）：系统中）：（1）进程完成；）进程完成；（2）进程阻塞；）进程阻塞；（3）进程出错挂起；）进程出错挂起；（4）分时系统中时间片到；）分时系统中时间片到；（5）高优先级进程就绪（抢占式系统）；）高优先级进程就绪（抢占式系统）；4.进程调度的准则进程调度的准则（1）CPU使用率；使用率；40%90%（2）吞吐率；单位时间内所完成的进程数）吞吐率；单位时间内所完成的进程数（3）周转时间；）周转时间；（4）响应时间；交互式系统）响应时间；交互式系统（5）等待时间；）等待时间；23 三三三三.进程调度方式进程调度方式进程调度方式进程调度方式1.1.什么是调度方式什么是调度方式什么是调度方式什么是调度方式当一进程正在处理机上执行时，若有某个更为当一进程正在处理机上执行时，若有某个更为当一进程正在处理机上执行时，若有某个更为当一进程正在处理机上执行时，若有某个更为“重要而紧重要而紧重要而紧重要而紧迫迫迫迫”的进程需要进行运行，系统如何分配处理机。的进程需要进行运行，系统如何分配处理机。的进程需要进行运行，系统如何分配处理机。的进程需要进行运行，系统如何分配处理机。2.2.非剥夺方式非剥夺方式非剥夺方式非剥夺方式一种是让正在执行的进程继续执行，直到该进程完成或一种是让正在执行的进程继续执行，直到该进程完成或一种是让正在执行的进程继续执行，直到该进程完成或一种是让正在执行的进程继续执行，直到该进程完成或发生某事件而进入发生某事件而进入发生某事件而进入发生某事件而进入“完成完成完成完成”或或或或“阻塞阻塞阻塞阻塞”状态时，才把处理机分状态时，才把处理机分状态时，才把处理机分状态时，才把处理机分配给配给配给配给“重要而紧迫重要而紧迫重要而紧迫重要而紧迫”的进程。的进程。的进程。的进程。3.3.剥夺方式剥夺方式剥夺方式剥夺方式当当当当“重要而紧迫重要而紧迫重要而紧迫重要而紧迫”的进程一到，便暂停正在执行的进程，立的进程一到，便暂停正在执行的进程，立的进程一到，便暂停正在执行的进程，立的进程一到，便暂停正在执行的进程，立即把处理机分配给优先级更高的进程。即把处理机分配给优先级更高的进程。即把处理机分配给优先级更高的进程。即把处理机分配给优先级更高的进程。24 四四四四.进程调度算法（进程调度算法（进程调度算法（进程调度算法（与作业调度算法有何关系？与作业调度算法有何关系？与作业调度算法有何关系？与作业调度算法有何关系？）1.1.进程优先数调度算法进程优先数调度算法进程优先数调度算法进程优先数调度算法(1)(1)什么是进程优先数调度算法什么是进程优先数调度算法什么是进程优先数调度算法什么是进程优先数调度算法预先确定各进程的优先数，系统把处理机的使用权赋预先确定各进程的优先数，系统把处理机的使用权赋预先确定各进程的优先数，系统把处理机的使用权赋预先确定各进程的优先数，系统把处理机的使用权赋予就绪队列中具备最高优先权予就绪队列中具备最高优先权予就绪队列中具备最高优先权予就绪队列中具备最高优先权(优先数和一定的优先级相优先数和一定的优先级相优先数和一定的优先级相优先数和一定的优先级相对应对应对应对应)的就绪进程。的就绪进程。的就绪进程。的就绪进程。n n 优优优优先先先先数数数数调调调调度度度度算算算算法法法法是是是是目目目目前前前前操操操操作作作作系系系系统统统统广广广广泛泛泛泛采采采采用用用用的的的的一一一一种种种种进进进进程程程程调调调调度度度度算算算算法法法法，这这这这种种种种算算算算法法法法按按按按照照照照某某某某种种种种原原原原则则则则由由由由系系系系统统统统（或或或或用用用用户户户户、或或或或系系系系统统统统与与与与用用用用户户户户结结结结合合合合）赋赋赋赋予予予予每每每每个个个个进进进进程程程程一一一一个个个个优优优优先先先先数数数数，在在在在处处处处理理理理机机机机空空空空闲闲闲闲时时时时，进进进进程程程程调调调调度度度度程程程程序序序序就就就就从从从从就就就就绪绪绪绪进进进进程程程程中中中中选选选选择择择择一一一一个个个个优优优优先先先先数数数数最最最最大大大大（或或或或者者者者最最最最小小小小）的的的的进进进进程程程程占占占占用用用用CPUCPU（该该该该进进进进程程程程就就就就从从从从就就就就绪绪绪绪状状状状态态态态转转转转换换换换成运行状态）。成运行状态）。成运行状态）。成运行状态）。25 (2)(2)优先数的分类及确定优先数的分类及确定优先数的分类及确定优先数的分类及确定n n 静态优先数静态优先数静态优先数静态优先数*在进程被创建时确定，且一经确定后在整个进程运行期间在进程被创建时确定，且一经确定后在整个进程运行期间在进程被创建时确定，且一经确定后在整个进程运行期间在进程被创建时确定，且一经确定后在整个进程运行期间不再改变。不再改变。不再改变。不再改变。*静态优先数的确定静态优先数的确定静态优先数的确定静态优先数的确定系统确定：运行时间、使用资源，进程的类型系统确定：运行时间、使用资源，进程的类型系统确定：运行时间、使用资源，进程的类型系统确定：运行时间、使用资源，进程的类型用户确定：紧迫程度，计费标准用户确定：紧迫程度，计费标准用户确定：紧迫程度，计费标准用户确定：紧迫程度，计费标准系系系系统统统统与与与与用用用用户户户户结结结结合合合合：用用用用户户户户可可可可以以以以为为为为本本本本用用用用户户户户的的的的进进进进程程程程设设设设置置置置优优优优先先先先数数数数，但但但但不不不不是是是是作作作作调调调调度度度度用用用用，系系系系统统统统还还还还要要要要根根根根据据据据系系系系统统统统情情情情况况况况把把把把用用用用户户户户设设设设置置置置的进程优先数作为确定进程优先数的一个参数的进程优先数作为确定进程优先数的一个参数的进程优先数作为确定进程优先数的一个参数的进程优先数作为确定进程优先数的一个参数26 n n动态优先数动态优先数动态优先数动态优先数*进程优先数在进程运行期间可以改变。进程优先数在进程运行期间可以改变。进程优先数在进程运行期间可以改变。进程优先数在进程运行期间可以改变。*动态优先数的确定动态优先数的确定动态优先数的确定动态优先数的确定进程使用进程使用进程使用进程使用CPUCPU超过一定数值时，降低优先数；超过一定数值时，降低优先数；超过一定数值时，降低优先数；超过一定数值时，降低优先数；进程进行进程进行进程进行进程进行I/OI/O操作后，增加优先数操作后，增加优先数操作后，增加优先数操作后，增加优先数进程等待时间超过一定数值时，提高优先数进程等待时间超过一定数值时，提高优先数进程等待时间超过一定数值时，提高优先数进程等待时间超过一定数值时，提高优先数27 2.循环轮转调度算法循环轮转调度算法(1)什么是循环轮转调度算法什么是循环轮转调度算法当当CPU空闲时，选取就绪队列首元素，赋予一个时间片，空闲时，选取就绪队列首元素，赋予一个时间片，当时间片用完时，该进程转为就绪态并进入就绪队列末端。当时间片用完时，该进程转为就绪态并进入就绪队列末端。该队列排序的原则是什么？该队列排序的原则是什么？该队列排序的原则是什么？该队列排序的原则是什么？pcb1pcb2pcbnCPU完成完成28 (2)(2)简单循环轮转调度简单循环轮转调度简单循环轮转调度简单循环轮转调度就绪队列中的所有进程以等速度向前进展就绪队列中的所有进程以等速度向前进展就绪队列中的所有进程以等速度向前进展就绪队列中的所有进程以等速度向前进展q=q=t/nt/ntt为响应时间，为响应时间，为响应时间，为响应时间，n n为进入系统的进程数目。为进入系统的进程数目。为进入系统的进程数目。为进入系统的进程数目。q q值如何确定值如何确定值如何确定值如何确定?(3)(3)循环轮转调度算法的发展循环轮转调度算法的发展循环轮转调度算法的发展循环轮转调度算法的发展可变时间片轮转调度、多重时间片循环调度可变时间片轮转调度、多重时间片循环调度可变时间片轮转调度、多重时间片循环调度可变时间片轮转调度、多重时间片循环调度29 系系系系统统统统按按按按进进进进程程程程转转转转换换换换成成成成就就就就绪绪绪绪状状状状态态态态的的的的时时时时间间间间的的的的降降降降序序序序排排排排队队队队，调调调调度度度度程程程程序序序序每每每每次次次次调调调调度度度度，总总总总是是是是从从从从队队队队首首首首移移移移出出出出一一一一程程程程的的的的PCBPCB，然然然然后后后后，将将将将此此此此进进进进程程程程投投投投入入入入运运运运行行行行（由由由由就就就就绪绪绪绪状状状状态态态态转转转转换换换换成成成成运运运运行行行行状状状状态态态态）。一一一一个个个个运运运运行行行行时时时时间间间间片片片片到到到到的的的的进进进进程程程程从从从从运运运运行行行行状状状状态态态态转转转转换换换换成成成成就就就就绪绪绪绪状状状状态态态态后后后后，排排排排在在在在就就就就绪绪绪绪队队队队列列列列的的的的队尾。队尾。队尾。队尾。评价：评价：评价：评价：优点是实现简单、系统开销小优点是实现简单、系统开销小优点是实现简单、系统开销小优点是实现简单、系统开销小缺点是不灵活，当系统中进程较少时，系统开销变大缺点是不灵活，当系统中进程较少时，系统开销变大缺点是不灵活，当系统中进程较少时，系统开销变大缺点是不灵活，当系统中进程较少时，系统开销变大为什么？为什么？为什么？为什么？由由由由于于于于该该该该算算算算法法法法简简简简单单单单易易易易于于于于实实实实现现现现，且且且且系系系系统统统统开开开开销销销销较较较较小小小小，早早早早期期期期的的的的分分分分时时时时操操操操作作作作系系系系统统统统和和和和目目目目前前前前一一一一些些些些应应应应用用用用系系系系统统统统中中中中广广广广泛泛泛泛采采采采用用用用了了了了这这这这种种种种调调调调度度度度算算算算法。法。法。法。30 (3)(3)循环轮转调度算法的发展循环轮转调度算法的发展循环轮转调度算法的发展循环轮转调度算法的发展n n可变时间片轮转调度可变时间片轮转调度可变时间片轮转调度可变时间片轮转调度将固定时间片改为可变时间片将固定时间片改为可变时间片将固定时间片改为可变时间片将固定时间片改为可变时间片 为为为为了了了了克克克克服服服服前前前前种种种种调调调调度度度度算算算算法法法法的的的的缺缺缺缺点点点点，人人人人们们们们设设设设计计计计出出出出一一一一种种种种可可可可变变变变时时时时间间间间片片片片的的的的调调调调度度度度算算算算法法法法，其其其其思思思思想想想想是是是是：时时时时间间间间片片片片的的的的大大大大小小小小是是是是可可可可变变变变的的的的，系统可根据系统中当前的进程数来确定时间片的大小。系统可根据系统中当前的进程数来确定时间片的大小。系统可根据系统中当前的进程数来确定时间片的大小。系统可根据系统中当前的进程数来确定时间片的大小。这这这这种种种种算算算算法法法法从从从从理理理理论论论论上上上上克克克克服服服服了了了了系系系系统统统统中中中中进进进进程程程程数数数数很很很很少少少少时时时时系系系系统统统统开开开开销销销销大大大大的的的的缺缺缺缺点点点点，但但但但修修修修改改改改时时时时间间间间片片片片的的的的大大大大小小小小，统统统统计计计计系系系系统统统统进进进进程程程程的的的的数数数数量量量量也也也也需需需需要要要要消消消消耗耗耗耗系系系系统统统统时时时时间间间间，还还还还有有有有一一一一个个个个调调调调整整整整时时时时间间间间片片片片大大大大小小小小的的的的周周周周期期期期，太太太太大大大大，等等等等于于于于是是是是固固固固定定定定时时时时间间间间片片片片，太太太太小小小小，系系系系统统统统开开开开销销销销很很很很大大大大，得得得得不不不不尝尝尝尝失。失。失。失。例如，响应时间例如，响应时间例如，响应时间例如，响应时间t=3st=3s，当，当，当，当n=30n=30，q=0.1sq=0.1s；当；当；当；当n=6n=6，q=0.5sq=0.5sn n多重时间片循环调度多重时间片循环调度多重时间片循环调度多重时间片循环调度将单一就绪队列改为多就绪队列（见下页）将单一就绪队列改为多就绪队列（见下页）将单一就绪队列改为多就绪队列（见下页）将单一就绪队列改为多就绪队列（见下页）31 五五五五.调度用的进程调度变迁图（多重时间片循环调度）调度用的进程调度变迁图（多重时间片循环调度）调度用的进程调度变迁图（多重时间片循环调度）调度用的进程调度变迁图（多重时间片循环调度）运行运行500ms100ms因因IO而等待而等待高优先高优先就绪就绪低优先低优先就绪就绪进程进程调度调度进程调度进程调度时间片到时间片到请求请求I/OI/O完成完成32 1.队列结构队列结构 I/O等待队列等待队列一个进程如果请求一个进程如果请求I/O，进入，进入I/O等待队列等待队列 低优先就绪队列低优先就绪队列一个进程如果在运行中超过了它的时间量，进入低优先一个进程如果在运行中超过了它的时间量，进入低优先就绪队列就绪队列 高优先就绪队列高优先就绪队列当进程从等待状态变为就绪状态时，进入高优先就绪队当进程从等待状态变为就绪状态时，进入高优先就绪队列列2.进程调度算法进程调度算法优先调度与时间片调度相结合的调度策略优先调度与时间片调度相结合的调度策略33 (1)当当CPU空闲时，若高优先就绪队列非空，则从高优先空闲时，若高优先就绪队列非空，则从高优先就绪队列中选择一个进程运行，分配时间片为就绪队列中选择一个进程运行，分配时间片为100ms。(2)当当CPU空闲时，若高优先就绪队列为空，则从低优先空闲时，若高优先就绪队列为空，则从低优先就绪队列中选择一个进程运行，分配时间片为就绪队列中选择一个进程运行，分配时间片为500ms。3.调度效果调度效果优先照顾了优先照顾了IO量大的进程；量大的进程；适当照顾了计算量大的进程。适当照顾了计算量大的进程。34 【问问】某计算机系统中，进程调度采用时间片轮转调度算法。某计算机系统中，进程调度采用时间片轮转调度算法。每个进程得到的时间片可随进程的执行情况而变化，在过去每个进程得到的时间片可随进程的执行情况而变化，在过去的时间里，若进程经常启动外设则给它分配的时间里，若进程经常启动外设则给它分配较短较短的时间片；的时间片；若启动外设次数很少则分配一个若启动外设次数很少则分配一个较长较长的时间片。为什么？的时间片。为什么？【答答】这种分这种分配方法配方法能够提高处理器（能够提高处理器（CPUCPU）的利用率。）的利用率。因为启动外设的速度是很慢的，在某个进程使用外设的过程因为启动外设的速度是很慢的，在某个进程使用外设的过程中是处于一种阻塞的状态，中是处于一种阻塞的状态，CPUCPU只能闲置，极大地降低了只能闲置，极大地降低了CPUCPU利用率，利用率，CPUCPU完全可以利用该进程读写外设的时间运行其他的完全可以利用该进程读写外设的时间运行其他的进程。进程。比如一个进程比如一个进程A A每使用每使用CPUCPU时间为时间为1ms1ms就要进行外设操作，假设就要进行外设操作，假设外设操作时间为外设操作时间为30ms30ms，那么如果给他分配的时间片为，那么如果给他分配的时间片为1ms1ms，好，好，那么那么CPUCPU没有被耽误；如果分配没有被耽误；如果分配5ms5ms，那么，那么CPUCPU闲置闲置4ms4ms；如果；如果分配分配30ms30ms，那，那29ms29ms中中CPUCPU都没事干。都没事干。35 【问问】在系统中设置两个就绪队列，一个是时间片较短的进程就在系统中设置两个就绪队列，一个是时间片较短的进程就绪队列，另一个是时间片较长的进程就绪队列。那么，在进程调绪队列，另一个是时间片较长的进程就绪队列。那么，在进程调度时应优先从哪个队列中选取一个就绪进程占有度时应优先从哪个队列中选取一个就绪进程占有CPU？为什么？为什么？【答答】这是这是进程调度进程调度中的短任务优先原则。中的短任务优先原则。如果两个进程如果两个进程A A和和B B，A A要要1ms1ms就能做完，就能做完，B B要要30ms30ms才能做完，那么如才能做完，那么如果果A A不幸排在不幸排在B B后面，那么后面，那么A A要等要等30ms30ms才能运行，那么程序才能运行，那么程序响应时间响应时间和交互体验很差。和交互体验很差。如果先如果先A A 后后B B，那么，那么A A的的响应时间响应时间为为1ms1ms，B B为为31ms31ms；如果先如果先B B 后后A A，那么，那么A A的的响应时间响应时间为为31ms31ms，B B为为30ms30ms。36 第六章第六章小结小结一一一一.处理机的两级调度处理机的两级调度处理机的两级调度处理机的两级调度二二二二.作业调度作业调度作业调度作业调度 1.1.作业的四种状态作业的四种状态作业的四种状态作业的四种状态 2.2.作业控制块作业控制块作业控制块作业控制块3.3.周转时间、带权周转时间：定义周转时间、带权周转时间：定义周转时间、带权周转时间：定义周转时间、带权周转时间：定义 物理意义物理意义物理意义物理意义4.4.常用的作业调度算法常用的作业调度算法常用的作业调度算法常用的作业调度算法先来先服务先来先服务先来先服务先来先服务 短作业优先短作业优先短作业优先短作业优先对一批作业，若采用两中不同的调度算法，能分析、计对一批作业，若采用两中不同的调度算法，能分析、计对一批作业，若采用两中不同的调度算法，能分析、计对一批作业，若采用两中不同的调度算法，能分析、计算调度性能的好坏。算调度性能的好坏。算调度性能的好坏。算调度性能的好坏。37 三三.进程调度进程调度1.调度方式调度方式非剥夺方式非剥夺方式剥夺方式剥夺方式2.常用的进程调度算法常用的进程调度算法优先数调度优先数调度循环轮转调度循环轮转调度3.调度用的进程状态变迁图调度用的进程状态变迁图通过调度用的进程状态变迁图，能分析系统采用的调度通过调度用的进程状态变迁图，能分析系统采用的调度策略，调度性能的好坏。策略，调度性能的好坏。能分析因果变迁及条件。能分析因果变迁及条件。38（20132013真题）真题）45.(745.(7分分)某博物馆最多可容纳某博物馆最多可容纳500500人同时参观，人同时参观，有一个出入口，该出入口一次仅允许一个人通过。参观者的有一个出入口，该出入口一次仅允许一个人通过。参观者的活动描述如下：活动描述如下：cobegincobegin参观者进程参观者进程i i：进门；进门；参观；参观；出门；出门；coendcoend请添加必要的信号量和请添加必要的信号量和P P、V(V(或或wait()wait()、signal()signal()操作，以操作，以实现上述操作过程中的互斥与同步。实现上述操作过程中的互斥与同步。要求写出完整的过程，说明信号量含义并赋初值。要求写出完整的过程，说明信号量含义并赋初值。39解答：解答：main()main()intint empty=500 empty=500；/semaphoresemaphore empty=500;empty=500;/可容纳人数的上限可容纳人数的上限 intint mutexmutex=1=1；/用于出入口资源的控制用于出入口资源的控制 cobegincobeginvisitorivisitori();();coendcoend visitorivisitori()()P(emptyP(empty););P(mutexP(mutex););进门进门V(mutexV(mutex););参观参观P(mutexP(mutex););出门；出门；V(mutexV(mutex););V(emptyV(empty););40（20142014真题）真题）【4747】系统中有多个生产者进程和消费者进程，系统中有多个生产者进程和消费者进程，共享用一个可以存共享用一个可以存10001000个产品的缓冲区（初始为空），当缓个产品的缓冲区（初始为空），当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。否则等待。要求一个消费者进程从缓冲区连续取出要求一个消费者进程从缓冲区连续取出1010件产品后，其他消件产品后，其他消费者进程才可以取产品，请用信号量费者进程才可以取产品，请用信号量P P，V V（waitwait，signedsigned）操作实现进程间的互斥和同步，要求写出完整的过程；并指操作实现进程间的互斥和同步，要求写出完整的过程；并指出所用信号量的含义和初值。出所用信号量的含义和初值。41解答：解答：main()main()intint empty=1000 empty=1000，full;full;intint mutexmutex=1,s0j=0;=1,s0j=0;cobegincobeginPi();C0();Pi();C0();CjCj(););coendcoend Pi()Pi()while(1)while(1)生产一产品；生产一产品；P(emptyP(empty););P(mutexP(mutex););产品放入缓冲区；产品放入缓冲区；V(mutexV(mutex););V(fullV(full););42C0()C0()for(intfor(int t=1;t=10;t+)t=1;t0N0）个个单单元元的的缓缓冲冲区区。P1P1每每次次用用produceproduce（）生生成成一一个个正正整整数数并并用用putput（）送送入入缓缓冲冲区区某某一一空空单单元元中中；P2P2每每次次用用getoddgetodd（）从从该该缓缓冲冲区区中中取取出出一一个个奇奇数数并并用用countoddcountodd（）统统计计奇奇数数个个数数；P3P3每每次次用用getevengeteven（）从从该该缓缓冲冲区区中中取取出出一一个个偶偶数数并并用用countevencounteven（）统统计计偶偶数数个个数数。请请用用信信号号量量机机制制实实现现这这三三个个进进程程的的同同步步与与互互斥斥活活动动，并并说说明明所所定定义义的的信信号号量量的的含含义义。要要求求用用伪伪代代码码描描述述。47解答：解答：定义信号量定义信号量S12S12控制控制P1P1与与P2P2之间的同步；之间的同步；信号量信号量S13S13控制控制P1P1与与P3P3之间的同步；之间的同步；信号量信号量emptyempty控制生产者与消费者之间的同步；控制生产者与消费者之间的同步；信号量信号量mutexmutex控制进程间互斥使用缓冲区。控制进程间互斥使用缓冲区。main()main()ints12=0,s13=0,ints12=0,s13=0,empty=N,empty=N,mutexmutex=1;=1;cobegincobeginP1();P2();P3();P1();P2();P3();coendcoend 48P2()P2()P(s12