作业管理及调度.ppt

第三章 处理机调度与死锁,3.1 处理机调度的基本概念,一、高级调度 High Scheduling(Long-Term Scheduling)二、低级调度 Low-Level Scheduling(Short-Term Scheduling P71三、中级调度 Intermediate-Level Scheduling(Medium-Term Scheduling,按OS的类型分：,批处理调度分时调度和实时调度多处理机调度等,按调度层次分：,处理机调度的基本类型：,中级调度,高级调度,低级调度,一、高级调度（作业调度）High Level Scheduling,决定允许哪些作业竞争系统资源。也就是说，高级调度用于把外存上处于后备状态的作业按照一定的算法，选取出一个作业，当内存空间满足其要求时，为它分配存储空间，调入内存，创建该作业的进程，再分配它所需的I/0设备及其它资源，再将新进程排在就绪队列上，使新进程具有了获得处理机的资格。,二、低级调度（Low Level Scheduling）,也称进程调度，它决定在就绪队列中哪一个进程将分配到处理机，并由分派程序把处理机实际分配给这个进程。,进程调度可采用下述两种方式：,非抢占方式 抢占方式抢占原则：（1）时间片原则（2）优先权原则（3）短作业优先原则,三、中级调度（Intermediate Level Scheduling）,涉及进程在内外存间的交换，从存储器资源管理的角度来看，把进程的部分或全部换出到外存上，可为当前运行进程的执行提供所需内存空间，将当前进程所需部分换入到内存。指令和数据必须在内存里才能被处理机直接访问目的：是为了提高内存的利用率和系统吞吐量。,3.1.2 进程调度队列模型,1、仅有进程调度的调度队列模型2、具有高级和低级调度的调度队列模型3、同时具有三级调度的调度队列模型,进程完成,cpu,进程调度,时间片完,阻 塞 队 列,就 绪 队 列,事件出现,交互用户,等待事件,仅有进程调度的调度队列模型(分时系统）,具有高,低两级调度的调度队列模型（批处理系统）,processor,进程调度,作业调度,超时,就绪队列,等待事件2,事件2出现,后备作业队列,事件n出现,事件1出现,等待事件n,等待事件1,完成,中级调度,processor,进程调度,作业调度,完成,超时,挂起就绪队列,挂起等待队列,等待队列,就绪队列,等待事件,交互式用户,事件出现,后备作业队列,中级调度,具有三级调度时的调度队列模型,3.1.3 选择调度方式和调度算法的若干准则,1、面向用户的准则（1）周转时间短（2）响应时间快（3）截止时间的保证（4）优先权准则,2、面向系统的准则（1）系统吞吐量高。（2）处理机利用率好。（3）各类资源的平衡利用。,选择调度方式和调度算法的若干准则（续）,作业调度,作业调度是针对多道程序系统设计的。它主要是完成作业从后备状态到执行状态的转变以及从执行状态到完成状态的转变。,执行状态,运行,就绪,等待,输入状态,后备状态,完成状态,进程调度中级调度,缓输出,作业调度,预输入完成,作业调度与进程调度的关系,执行状态,输入状态：作业的信息正在从输入设备上预输入。后备状态：作业预输入结束但尚未被选中执行。执行状态：作业已经被选中并构成进程去竞争处理器资源以获得运行。完成状态：作业已经运行结束，正在等待缓输出。,作业的四个状态:,作业调度功能,1、记录系统中各作业的状态。不同的批处理系统，作业控制块JCB的内容也不同。一般JCB有以下内容：（1）作业名：由用户提供，系统把它转换为系统可识别的作业标识符。（2）作业类型：计算型、管理型、图形设计型。（3）资源要求：由用户提供，要求的内、外存大小，外设类型台数，软件支持，作业估计执行时间。,（4）资源使用情况。作业进入系统时间：所有信息输入到输入井，作业的状态成为后备状态的时间。开始执行时间：作业被作业调度程序选中，状态由后备转为执行的时间。内存地址：作业的内存区起始地址。外设台数：系统分配的外设实际台数。（5）优先级：可由用户给定也可由系统动态产生，决定作业的调度次序。（6）当前状态：作业当前所处的状态。,2、从后备队列中挑选一部分作业投入运行,作业调度程序根据一定调度的算法，从后备队列中挑选出一部分作业进入内存。,3、为被选中作业做好执行前的准备工作,作业调度程序为作业建立进程，分配它们所需要的系统资源。,4、在作业执行结束时做善后处理工作,输出作业管理信息，回收资源、撤消与该作业有关的所有进程，以及作业控制块。,作业调度目标和性能评价,一、作业调度目标作业调度的主要原则应是在单位时间内运行尽可能多的作业并且应使CPU尽可能处于运行状态，使CPU的利用率最大；作业调度还应使输入输出设备并行运行；处于多道程序中的各个作业还应具有平等的运行机会。,一般地说，作业调度目标主要有以下四点：（1）对所有的作业应该是公平合理的；（2）应使设备有高的利用率；（3）每天执行尽可能多的作业；（4）有快的响应时间。,二、作业调度算法的性能评价,1.周转时间：Ti=Tei-Tsi 由等待时间、执行时间 组成 Tei为作业i的完成时间，Tsi为作业的提交时间。平均周转时间：T=Ti/n n=1，n为作业流的作业个数。,2、带权周转时间,带权周转时间：Wi=Ti/Tr 作业周转时间与作业执行时间之比。Ti：周转时间，Tr：实际执行时间平均带权周转时间：W=Wi/n n为作业个数。,3、分时系统中，还要考虑响应时间,响应时间是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。或者说直到屏幕上显示出结果为止的一段时间间隔。包括：（1）从键盘输入的请求信息传送到处理机的时间；（2）处理机对请求信息进行处理的时间；（3）将所形成的响应回送到终端显示器的时间。,进程调度,进程调度的任务就是按照一定的策略负责把处理机分配给某一就绪进程。由进程调度程序具体实现处理机在进程之间的转换。,进程调度的时机,进程调度的时机与引起进程调度的原因以及进程调度的方式有关。一、引起进程调度的原因（1）正在执行的进程执行完毕。（2）执行中的进程提出I/O请求后被阻塞。（3）执行某种原语操作，比如wait(s)，block原语，wakeup原语。,（4）分时系统中，由于分配给该进程的时间片已经用完。（5）执行中进程自己调用阻塞原语将自己阻塞起来。（6）执行完系统程序后返回用户进程时，可看作系统进程执行完毕，从而可以调度选择一个新的用户进程执行。以上是在不可剥夺方式下的引起进程调度的原因，在CPU执行方式是可剥夺时，还有一个原因。,（7）一个比正在运行进程的优先数更高的进程进入就绪队列，从而引起调度。在以上所列的几种原因之一发生的情况下，OS进行进程调度。,3.2 调度算法,在OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。,先来先服务和短作业优先调度算法,1、先来先服务调度算法 先来先服务FCFS调度算法是一种最简单的调度算法。作业调度中采用该算法时，每次调度是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。,在进程调度中，采用FCFS时每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行，该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。,可见，FCFS调度算法有利于CPU繁忙型的作业，FCFS调度算法不利于I/0繁忙型作业。,FCFS在一定意义上是公平合理的。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。先来先服务不能保证良好的响应时间，在处理交互用户时很少用这种方法。,2.短作业（进程）优先调度算法（Shortest Job First）SJF,短作业（进程）优先调度算法SJ(P)F，是指对短作业或进程优先调度的算法。它们可分别用于作业调度(SJF)和进程调度(SPF)。,二、实例,二、实例,作业调度情况算法,进程名,A,B,C,D,E,平均,到达时间,0,1,2,3,4,服务时间,4,3,5,2,4,FCFS,完成时间,4,7,12,14,18,周转时间,4,7-1=6,12-2=10,14-3=11,18-4=14,(4+6+10+11+14)/5=9,带权周转时间,1,63=2,105=2,112=5.5,144=3.5,(1+2+2+5.5+3.5)/5=2.8,SJF,完成时间,4,周转时间,4,带权周转时间,1,二、实例,二、实例,二、实例,二、实例,二、实例,FCFS:只考虑等待时间，而不考虑运行时间。,SJF调度算法能有效地降低作业的平均等待时间和提高系统的吞吐量。,SPJ、SJF：根据作业（进程）占用处理机时间长短而定，注重了作业运行时间。,SJ(P)F调度算法的缺点：（1）该算法对长作业非常不利。（2）该算法完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）会得到及时处理；,（3）由于作业（进程）的长短只是根据用户所提供的估计执行时间而定，而用户又可能会有意或无意地缩短其作业的估计执行时间，致使该算法不一定能真正做到短作业优先调度。,FCFS与SJF都属于非剥夺调度，不适用在合理的响应时间应得到保证的分时环境中。,FCFS与SJF属于非剥夺调度，还是可剥夺调度？,一、优先权调度算法的类型,当用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，这时又可进一步把该算法分成两种方式：1.非抢占式优先权算法 2.抢占式优先权调度算法,优先权（级）调度算法,二、优先权类型,设计优先权的主要原则是充分地利用处理机，使用户进程尽可能地并行运行。优先权可分为静态优先权和动态优先权。,确定作业的静态优先权可根据以下原则：,（1）由用户自己根据作业的紧急程度输入一个适当的优先权。（2）由系统或操作员根据作业类型指定优先权。作业类型可由用户约定，也可以由操作员指定。（3）作业使用资源的多少。,1).静态优先权,进程的静态优先权确定原则：,（1）进程类型。（2）进程对资源的要求。（3）根据用户的要求。（4）将作业的静态优先权作为它所属进程的优先级。,静态优先权法简单易行，系统开销小，但不够精确，很可能出现优先权低的作业或进程，长期没有被调度的情况，而且静态优先级一旦确定之后，直到执行结束为止始终保持不变，从而系统效率较低，调度性能不高。因此，仅在要求不太高的系统中才使用静态优先权。,2).动态优先权,动态优先权把作业或进程的静态特性和动态特性结合起来确定作业或进程的优先权，随着作业或进程的执行过程，其优先权不断变化。,动态优先权的确定原则：,（1）根据进程占有CPU时间的长短来决定。（2）根据就绪进程等待CPU的时间长短来决定。,3 高响应比优先调度算法(High Response-ratio Next),最高响应比优先调度策略修正了最短作业优先调度的某些弱点，特别是后者忽视长作业，优待新的短作业的弱点。,HRN是一种非剥夺调度,优先权的变化可描述为：,该算法既照顾了短作业，又考虑了作业到达的先后次序，也不会使长作业长期得不到服务，是介于FCFS与SJF之间的一种算法，由于每次调用前，都要先进行响应比的计算，这会增加系统的开销。,响应比高者优先调度算法（十进制）,分析：开始只有作业1，故运行它。当作业1完成后，调度时刻为10.00,此时作业2，3，4均已进入系统，计算它们的响应比：作业2(0.5+1.5)/0.5=4,作业3(0.11)/0.1=11,作业4(0.2+0.5)/0.2=3.5,故选择作业3运行。当作业3完成后又计算作业2和作业4的响应比：作业2（0.51.6)/0.5=4.2,作业4（0.2+0.6)/0.2=4,故选择作业2运行。最后选择作业4运行。,分别采用先来先服务、短作业优先、高响应比优先调度算法，求周转时间、平均周转时间、带权周转时间、平均带权周转时间。,作业,基于时间片的轮转调度算法（Round Robin）,一、基本原理 系统将所有的就绪进程按先来先服务原则，排成一个队列，每次调度时把CPU分配给队首进程，并令其执行一个时间片，当执行的时间片用完时，由计时器发出时钟中断，调度程序根据这个信号来停止该进程的执行，把它放到就绪队列的末尾，等待下一次执行；然后再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就保证就绪队列中的所有进程，在一个给定的时间内，均能获得一时间片的处理机执行时间。,在时间片轮转法中，就绪进程按照先来先服务的原则排队，每个进程轮流地运行大小相等的时间片，对短作业和I/O操作较高的作业是不利的。如果有紧急进程进入就绪队列，并不能得到及时响应。,2 多级反馈队列调度算法,多级反馈队列调度算法，事先不必知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而是目前公认的较好的调度算法。,2 多级反馈队列调度算法,多级反馈队列调度的要求：设置多个就绪队列，各个队列赋予不同的优先级。优先级越高，每个进程的执行时间片越小。一个新进程进入内存后，首先将它放入第一队列末尾。如果它能够在一个时间片内完成，则可撤离。否则将其转入第二队列末尾。仅当第一队列空闲时，才调度第二队列中的进程运行。新来的进程如果优先级较高，可以抢占正在运行进程的处理机。,在采用多级反馈队列调度算法的系统中，调度算法的实施过程如下：,3、多级反馈队列调度算法的性能,1、终端型作业用户：作业通常较小，一个时间片就可完成。2、对于中短批处理型作业：只需少量几个时间片就可完成，周转时间依然较短。3、长批处理作业用户（不会长期得不到处理）,