将用户作业和就绪进程按提交顺序或变为就绪状态的先后.ppt

FCFS算法调度例2 作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法 SF算法例2 作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50 D 8:36 24 10 E 8:42 12 20 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法 进程调度程序：负责进程调度功能的内核程序。 作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。 进程调度的核心问题就是，采用什么算法把处理机分配给进程。 选择调度算法时应考虑的问题 进程调度的算法较多，在设计进程调度算 法时应考虑的因素多，比如：尽量提高资源利 用率，减少处理机的空闲时间，对于用户作业 要较合理的平均响应时间，以及尽可能地增强 CPU的处理能力。 §4.4 调度算法 1. FCFS(先来先服务调度算法) 最简单的调度原则是先进先出就绪队列 根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。 这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。 在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。 例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。 2. 作业要求的资源 根据作业要求系统提供的处理机时间，内存的大小和I/O设备的数量，来确定作业的优先数，如果系统赋予作业的反比于系统的估计执行时间，就形成短作业优先的算法。由于作业需要的执行时间事先难于确定，只是把用户自报的估计时间作为依据，为防止用户少报自己的作业时间以获得优先服务，在采用短作业优先算法时，应采取适当的防备措施。 4.时间片轮转算法 ①当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。 ②当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。 这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程异。 时间片的选取是实现各种调度算法的关键之处，而时间片的独额定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度。 5.优先级调度算法 一种常用的进程调度算法是把处理机分配给具有最高优先数的进程（用于实时系统） 在这种算法中，首先考虑的问题是如何确定进程的优先数。 一种是静态优先数，另一种是动态优先数。 1)静态优先数 静态优先数是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变，确定静态优先数的有关静特性是：在有的系统中，分配给作业的优先数还取决于它所占用的内存的多少，作业越大，占用内存越多，分配给它的优先数越低。显然，不论是根据作业的执行时间，还是根据作业的大小所确定的优先数，都有利于短作业。 2.动态优先数 虽然基于静态优先数的调度算法比较简单，也颇为流利，但毕竟不够精确。因为进程的优先数在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先数所依赖的特征很多