操作系统课件06处理机调度.ppt

第六章 处理机调度,（一）处理机的多级调度（二）作业调度（三）进程调度,处理机调度的目标：CPU使用率高：使处理机尽可能忙响应时间快：与用户交互快捷周转时间短：用户等待输出的时间短等待时间小：公平，确保每个进程都能公平地占有处理机系统吞吐量大：相同时间内完成的作业（进程）尽可能多,处理机的调度通常可分为两级调度：作业调度和进程调度。操作系统类型的不同，处理机的调度等级也是不同的：1、批处理系统中的处理机调度 2、多任务操作系统中的处理机调度 3、多线程操作系统中的处理机调度,（一）处理机的多级调度,1、批处理系统中的处理机调度处理机调度分两级：作业调度和进程调度。作业调度(又称宏观调度)：对存放在辅存设备上的大量作业，以一定的策略进行挑选，分配主存等必要的资源，建立作业对应的进程，使其投入运行。进程调度(又称微观调度)：对进入主存的所有进程，确定哪个进程在什么时候获得处理机，使用多长时间。,4,2.多任务操作系统中的处理机调度 在分时系统或支持多任务并发执行个人计算机操作系统中，系统将用户提交的任务处理为进程，一个进程又可以创建多个子进程，形成可以并发执行的多进程。进程调度的任务是：当处理机空闲时，以某种策略选择一个就绪进程去运行，并分配处理机的时间。,6,3.多线程操作系统中的处理机调度 在支持多线程运行的系统中，一个进程可以创建一个线程，也可以创建多个线程。系统为进程分配它所需要的资源，而处理机的分配单位则为线程。系统提供线程调度程序，其功能是当处理机空闲时，以某种策略选择一个就绪线程去运行，并分配处理机时间。,7,作业调度的主要任务是完成作业从后备状态到执行状态和从执行状态到完成状态的转变。,（二）作业调度,1、作业的状态作业在整个活动期间一共有三种状态：后备状态：作业已存放在磁盘上，等待掉进主存。执行状态：作业在主存中运行。完成状态：作业计算完成开始，退出主存。,2、作业调度功能：确定数据结构：为作业分配控制块JCB；确定调度算法：按一定的调度算法，从后备作业中选择一个或几个作业进入系统内存；分配资源：为被选中的作业创建进程，并且为其申请系统资源；善后处理：作业结束后作善后处理工作。,10,3、作业控制块 作业控制块JCB（Job Control Block)，它是存放作业控制和管理信息的数据结构，是作业存在的唯一标识，是操作系统调度的依据。主要信息见右图。,11,4、作业调度算法的性能衡量指标：平均周转时间和带权平均周转时间周转时间完成时间提交时间等待时 间执行时间平均周转时间周转时间总和作业数带权周转时间周转时间执行时间平均带权周转时间=带权周转总和作业数,5、作业调度算法先来先服务FCFS短作业优先SJF响应比高优先优先调度,13,（1）作业调度算法（一）先来先服务调度算 法(FCFS)策略：作业来到的先后次序进行调度优点：实现简单缺点：效率较低,（2）作业调度算法（二）短作业优先调度 算法（SJF）,策略：考虑作业的运行时间，每次总是选择一个 运行时间最小的作业调入内存（系统）。优点：易实现，系统吞吐量高 缺点：只考虑短作业，而没有考虑长作业的利益。如果作业的到来顺序及运行时间不合适，会出现饿死现象。,讨论在两种调度算法下的周转时间与带权周转时间,（3）作业调度算法（三）：响应比高者优先调度算法,响应比高者优先调度算法是介于前两种算法之间的一种折衷的算法。响应比 周转时间/执行时间 1 等待时间/执行时间,（4）作业调度算法（四）：优先调度算法,优先数调度算法综合考虑各方面的因素（作业等待时间、运行时间、缓急程度，系统资源使用等），给每个作业设置一个优先数，调度程序总是选择一个优先数最大（或者最小）的作业调入（系统）内存。这种算法实现的困难在于如何终合考虑，这些因素之间的关系怎样处理。,(三)进程调度,1、调度/分派结构处理机分配由调度和分派两个功能组成。1）调度组织和维护就绪进程队列。包括确定调度算法、按调度算法组织和维护就绪进程队列。（按调度原则选择进程）。2）分派当处理机空闲时，从就绪队列队首中移一个PCB，并将该进程投入运行。（赋予使用处理机的权限）。,20,调度与分派结构图,2、进程调度的功能,记录和保持系统中所有进程的有关情况和状态特征（PCB）决定分配（处理机）策略实施处理机的分配和回收,3、进程调度方式,基本的方式有二种：1）非剥夺方式2）剥夺方式,4、进程调度算法进程优先级调度算法循环轮转调度（RR）多级反馈队列调度,23,1）进程优先数调度算法是目前操作系统广泛采用的一种进程调度算法，这种算法按照某种原则由系统（或用户、或系统与用户结合）赋予每个进程一个优先数，在处理机空闲时，进程调度程序就从就绪进程中选择一个优先数最大（或者最小）的进程占用CPU（该进程就从就绪状态转换成运行状态）。采用这种调度算法的关键是如何确定进程的优先数、一个进程的优先数确定之后是固定的，还是随着该进程运行的情况的变化而变化。,2）循环轮转调度算法,循环轮转调度实际上是一种特殊的先来先服务算法的调度算法，它把系统的响应时间分成大小相等（或不相等）的时间单位，称为时间片。每个进程被调度到后，占用一个时间片，片用完后，该进程让出CPU，由运行状态转换成就绪状态，排在就绪队列的队尾。多个进程循环轮转。,【例】有5个进程（A，B，C，D，E）几乎同时到进入就 绪队列，估计的运行时间分别为2，4，6，8，10分钟，分别计算作业的平均周转时间。时间片轮转（时间片为2分钟）,26,A B C D E B C D E C D E D E E t 0 2 4 6 8 1012 1416182022 242628 30 t=(2+12+20+26+30)/5=18 分钟,作业,第6章 6题,28,