25处理器调度

1主要内容：一、处理机调度的层次二、高级调度三、中级调度四、低级调度五、选择调度算法的原则六、作业和进程的关系七、批处理作业的组织和管理八、交互型作业的组织和管理九、Linux进程间共享内存通信2.5处理器调度2一、处理机调度的层次(1)•处理器调度考虑如何从多个作业中选择一些作业加载到内存为其创建进程（称为作业调度或高级调度、长程调度)和如何从多个进程中选择一个进程占有处理器运行（称为进程/线程调度、低级调度或短程调度）的问题。•用户作业包括批处理作业和终端交互型作业。批处理作业进入系统后在磁盘后备队列中等候作业调度，终端交互型作业一旦被接纳，则直接创建进程，接受进程调度。3一、处理机调度的层次(1)•从系统接收作业到作业运行结束退出系统为止，可能要经历如图所示的三级调度过程：即高级调度、中级调度和低级调度。•处理器调度层次与进程状态转换关系图：4一、处理机调度的层次(2)中级调度新建态高级调度低级调度运行态就绪态等待态终止态挂起等待态挂起就绪态处理器调度的层次5一、处理机调度的层次(4)高级调度中级调度低级调度运行态就绪态终止态新建态挂起就绪态中级调度挂起等待态等待态高级调度高级调度中级调度处理器调度与进程状态转换6二、高级调度(作业调度、长程调度)(1)高级调度是在多道批处理系统中设置的调度层级，高级调度从磁盘后备作业队列中挑选若干作业进入内存，为其分配资源，创建进程；作业完成后还要做善后处理工作。高级调度根据CPU空闲时间控制多道程序的道数，每当作业结束后，补充装入新的作业到内存。高级调度发生在新进程的创建中，它决定一个进程能否被创建，或者创建后能否被置成就绪状态；中级调度反映到进程状态上就是挂起和解除挂起，它根据系统的当前负荷情况决定停留在主存中进程数；低级调度决定哪一个就绪进程占有CPU。7二、高级调度(作业调度、长程调度)(2)中级调度处理器低级调度高级调度完成超时挂起就绪队列挂起等待队列等待队列就绪队列等待事件交互式用户事件出现后备作业队列中级调度处理器的调度模型8三、中级调度(平衡调度,中程调度)•根据主存资源决定主存中所能容纳的进程数目，并根据进程的当前状态来决定辅存和主存中进程的对换。•中级调度决定那些进程被允许参与竞争处理器资源，使用的方法是通过把一些进程换出主存，使之进入“挂起”状态，不参与进程调度，起到平滑和调整系统负荷的作用。提高主存利用率和系统吐吞率。9四、低级调度（进程调度/线程调度、短程调度）主要功能是按照某种原则决定就绪队列中的哪个进程或内核级线程能获得处理器,并将处理机出让给它进行工作。低级调度执行分配CPU的程序称为分派程序（dispatcher）。低级调度程序是操作系统最为核心的部分，执行十分频繁。低级调度策略的优劣直接影响到整个系统的性能。10四、低级调度（进程调度/线程调度、短程调度）低级调度是各类操作系统中必须具有的功能；在纯粹的分时或实时操作系统中，通常不需要配备高级调度，而仅配置低级调度；一般的操作系统都配置高级调度和低级调度；而引进中级调度有利于提高主存利用率和作业吞吐量。11五、选择调度算法的原则(进程调度、短程调度)(1)无论哪一个层次的处理器调度，都由操作系统的调度程序（scheduler）实施，调度程序所使用的算法称为调度算法。根据调度所要达到的目标，设计调度算法通常应考虑如下原则：（前三条是面向系统的性能指标，后两条是面向用户的性能指标）1.资源利用率CPU利用率=CPU有效工作时间/CPU总的运行时间CPU总的运行时间=CPU有效工作时间+CPU空闲等待时间12五、选择调度算法的原则(进程调度、短程调度)(1)资源包括CPU及I/O设备等其它资源。在一定I/O操作等待时间的比率下，运行程序的道数越多，CPU空闲时间所占的百分比越低。2.吞吐率单位时间内CPU处理的作业数。显然处理的长作业多则吞吐率低，短作业多则吞吐率高。这是批处理系统调度性能的一个指标。13五、选择调度算法的原则(进程调度、短程调度)(1)3.公平性确保每个用户每个进程获得合理的CPU份额或其他资源份额，不会出现饥饿现象。4.响应时间交互式进程从提交一个请求(命令)到接收到响应之间的时间间隔称响应时间。包括命令传输到CPU的时间、CPU处理命令的时间和处理结果返回终端的时间。使交互式用户的响应时间尽可能短，或尽快处理实时任务，这是分时系统和实时系统衡量调度性能的一个重要指标。14五、选择调度算法的原则(进程调度、短程调度)(2)5.周转时间批处理用户从作业提交给系统开始，到作业完成为止的时间间隔称作业周转时间。包括：作业在后备队列等待时间、作业进程在就绪队列等待时间、进程在CPU上运行时间和等待事件（在等待队列）时间。应使作业周转时间或平均作业周转时间尽可能短，这是批处理系统衡量调度性能的一个重要指标。15五、选择调度算法的原则(进程调度、短程调度)(3)批处理系统的调度性能指标：批处理系统的调度性能主要用作业周转时间和作业带权周转时间来衡量，此时间越短，则系统效率越高，作业吞吐量越大。如果作业i提交给系统的时刻是ts，完成时刻是tf，该作业的周转时间ti为：ti=tf-ts实际上，它是作业在系统里的等待时间与运行时间之和。16五、选择调度算法的原则(进程调度、短程调度)(3)为了提高系统的性能，要让若干个用户的平均作业周转时间和平均带权周转时间最小。平均作业周转时间T=(Σti)/n如果作业i的周转时间为ti，所需运行时间为tk，则称wi=ti/tk为该作业的带权周转时间。ti是等待时间与运行时间之和，故带权周转时间总大于1。平均作业带权周转时间W=(Σwi)/n17五、选择调度算法的原则(进程调度、短程调度)(4)通常用平均作业周转时间来衡量对同一作业流施行不同作业调度算法时，它们呈现的调度性能；用平均作业带权周转时间来衡量对不同作业流施行同一作业调度算法时，它们呈现的调度性能。这两个数值均越小越好。18六、作业和进程的关系(1)作业(JOB)是用户提交给操作系统计算的一个独立任务。一般每个作业必须经过若干个相对独立又相互关联的顺序加工步骤才能得到结果，其中，每个加工步骤称一个作业步。例如，一个作业可分成“编译”、“连接装配”和“运行”三个作业步，往往上一个作业步的输出是下一个作业步的输入。作业由用户组织，作业步由用户指定，一个作业从提交给系统，直到运行结束获得结果，要经过提交、收容、执行和完成四个阶段。19六、作业和进程的关系(1)进程是对系统中已提交完毕并选中运行的任务（程序）的执行过程，也是为完成作业任务向系统申请和分配资源的基本单位。用户进程在执行过程中可生成作业步子进程，子进程还可以生成其它的子进程。进程还可以生成线程。20六、作业和进程的关系(2)作业和进程的关系：•作业是任务实体，进程是完成任务的执行实体；没有作业任务，进程无事可干，没有进程，作业任务没法完成。•作业概念更多地用在批处理操作系统，而进程则可以用在各种多道程序设计系统。作业分为批处理作业和交互型作业。21七、批处理作业的组织和管理(1)1、批处理作业的组成结构批处理作业采用脱机控制方式，作业实体由程序、数据和作业说明书组成。作业说明书是按规定格式书写的一个文件，把用户对系统的各种请求和对作业的控制要求集中描述，并与程序和数据一起提交给系统（管理员）。计算机系统成批接受用户作业输入，把它们放到输入井，然后，在操作系统的管理和控制下执行。22七、批处理作业的组织和管理(1)2.批处理作业的创建多道批处理操作系统具有独立的作业管理模块，必须像进程管理一样为每一个作业建立作业控制块（JCB）。JCB通常是在批作业进入系统时，由Spooling系统建立的，它是作业存在于系统的标志，作业撤离时，JCB也被撤销。23七、批处理作业的组织和管理(2)JCB的主要内容包括：(1)作业情况(用户名、作业名、语言名)，(2)资源需求(估计CPU运行时间、最迟截止期、主存量、设备类型/台数、文件数和数据量、函数库/实用程序等)，(3)资源使用情况(进入系统时间、开始运行时间、己运行时间)，作业控制(优先数、控制方式、操作顺序、出错处理等)作业类型（CPU繁忙型、I/O繁忙型、批量型、终端型）等信息。24七、批处理作业的组织和管理(2)3.作业生命周期状态的构成•输入状态：此时作业的信息正在从输入设备上预输入。•后备状态：此时作业预输入结束但尚未被选中执行。•执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。•完成状态：作业已经运行结束，正在等待缓输出运算结果。25七、批处理作业的组织和管理(3)4.批处理作业的调度作业调度程序完成以下几项任务：（1）选择作业由作业调度程序根据资源状况和多道程序道数决定选择哪些作业。（2）分配资源分配内存、设备等。（3）创建进程进程调度程序负责为进程分配处理器。进入计算机系统的作业只有经过两级调度后才能占用处理器。第一级是作业调度，使作业进入主存储器；第二级是处理器调度，使作业进程占用处理器。作业调度与处理器调度的配合能实现多道作业的同时执行。26七、批处理作业的管理(4)执行状态运行就绪等待输入状态后备状态完成状态进程调度中级调度缓输出作业调度（创建用户进程）预输入完成作业调度与进程调度的关系27七、批处理作业的组织和管理(3)（4）作业控制作业控制块和SPOOLing管理程序控制作业的启动、作业步转接、程序调入、数据I/O、异常处理。（5）后续处理作业正常结束或出错终止时，作业调度程序回收资源、撤销作业控制块，并选择新作业进入主存。28八、交互型作业的组织和管理交互型作业采用联机控制方式，是一个上机过程，在分时系统中需要配置交互型作业管理程序。操作系统启动时，为连接至系统的每个终端创建一个终端进程，该进程接收用户输入的交互型命令、解释和执行命令。用户输入退出命令则结束本次上机过程。分时系统的作业就是用户的一次上机过程，交互型作业开始于终端进程的创建，结束于退出命令。用户输入一条命令，操作系统就创建一个或若干进程。一个命令即一个作业步。现代操作系统很少使用真正的批处理策略，往往以联机方式执行批处理命令，以减少重复输入多个命令。