进程调度算法和作业调度算法。 （1） 先来先服务（FCFS）调度算法

Presentation on theme: "进程调度算法和作业调度算法。 （1） 先来先服务（FCFS）调度算法"— Presentation transcript:

1 进程调度算法和作业调度算法。 （1） 先来先服务（FCFS）调度算法
将用户作业和就绪进程按提交顺序或变为就绪状态的先后排成队列，并按照先来先服务的方式进行调度处理，是一种最普遍和最简单的方法。它优先考虑在系统中等待时间最长的作业，而不管要求运行时间的长短。

2 在单道环境下，某批处理显然有四道作业，已知他们的进入系统的时刻、估计运算时间如下：
进入时刻(h) 运行时间(h) 1 8.00 2.00 2 8.50 0.50 3 0.10 9.00 4 0.20 9.50 用FCFS算法计算作业的运行情况、平均周转时间和平均带权周转时间

3 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 1 1.00 8.00 2.00 8.00 10.00 2.00 2 8.50 0.50 10.00 10.50 2.00 4.00 3 9.00 0.10 10.50 10.60 1.60 16.00 10.60 4 9.50 0.20 10.80 1.30 6.50 平均周转时间T＝1.725（h） 平均带权周转时间T’＝6.875（h）

4 FCFS算法调度例2 作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60
D : E : 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法

5 作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50
有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法 作业名 进入时间 运行时间（分） 需内存量KB A : B : C : D : E : 15K 60K 10K 15K 9.18 100K

6 该算法总是优先调度要求运行时间最短的作业
（2）.最短作业优先法（SJF） 该算法总是优先调度要求运行时间最短的作业 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 平均周转时间 T＝1.55h 平均带权周转时间T’＝5.15h 运行顺序

7 SF算法例2 作业名 进入时间 运行时间（分） 需内存量KB A 8:06 42 15 B 8:18 30 60 C 8:30 24 50
D : E : 有用户空间100KB，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法

8 作业名 进入时间 运行时间（分） 需内存量KB
A : B : C : D : E :

9 最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义为系统对作业的响应时间与作业要求运行时间的比值
(3)最高响应比作业优先算法（HRN） 最高响应比作业优先算法是对FCFS方式和SJF方式的一种综合平衡响应比R定义为系统对作业的响应时间与作业要求运行时间的比值 R＝响应时间 / 要求运行时间 ＝(作业等待时间＋需运行时间)/ 需运行时间 ＝1＋已等待时间 / 需运行时间 ＝1＋W/T

10 响应比R不仅是要求运行时间的函数，而且还是等待时间的函数。
由于R与要求运行时间成反比，故对短作业是有利的，另一方面，因R与等待时间成正比，故长作业随着其等待时间的增长，也可获的较高的相应比。这就克服了短作业优先数法的缺点，既照顾了先来者，又优待了短作业，是上述两种算法的一种较好的折中。

11 (3)最高响应比作业优先算法（HRN） 作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转
作业 进入时刻 运行时间 开始时刻 完成时刻 周转时间 带权周转 平均周转时间1.625h 带权周转时间 5.675h

12 (4) 轮转法（RR） 时间片轮转法主要用于进程调度。采用此算法的系统，其程序就绪队列往往按进程到达的时间来排序。进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用先一个时间片后，进程还没又完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待在次运行。

13 时间片轮转策略特别适合于分时系统中使用，当多个进程驻留在主存中时，在进程间转接处理机的开销一般是不大的。
  在轮转法中，时间片长度的选取非常重要，时间片长度的选择会直接影响系统开销和响应时间，如果时间片长度过短，则调度程序剥夺处理机的次数增多，这将使进程上下文交换次数也大大增加，加重了系统开销。如果时间片长度选择过长（大）。大到一个进程足以完成其全部运行工作所需的时间，那么时间片轮转法就退化为先来先服务策略了。最佳的时间片量值应能使分时用户得到好的响应时间

14 响应时间 S＝RT/Nmax R——响应时间 Nmax——最大进程数 每当一轮调度开始时，系统便根据就绪队列中已有进程数目计算一次值。作为新一轮调度的时间片。这种方法得到的时间片是随就绪队列中的进程数变化的。

15 进程调度 进程调度的功能：从就绪队列中挑选一个进程到处理机上运行。 作业调度程序在挑选作业进入主存运行时，要为该作业建立相应的进程。在作业完成后要撤销该作业的全部进程。   一个进程被建立后，系统为了便于对进程的管理，将系统中的所有进程按其状态将其组织成不同的进程队列。

16 进程调度程序：负责进程调度功能的内核程序。 作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。
进程调度程序：负责进程调度功能的内核程序。 作业调度与进程调度程序的区别：前者是挑选作业进主存运行、后者是挑选就绪进程到处理机上运行。 进程调度的核心问题就是，采用什么算法把处理机分配给进程。

17 选择调度算法时应考虑的问题 进程调度的算法较多，在设计进程调度算 法时应考虑的因素多，比如：尽量提高资源利 用率，减少处理机的空闲时间，对于用户作业 要较合理的平均响应时间，以及尽可能地增强 CPU的处理能力。

18 §4.4 调度算法 1. FCFS(先来先服务调度算法) 最简单的调度原则是先进先出就绪队列 CPU 完成 D C B A

19 根据进程到达就绪队列的时间来分配中央处理机，一旦一个进程获得了中央处理机，就一直运行到结束，先来先服务是非剥夺调度。
这种调度从形式上讲是公平的，但它使短作业要等待长作业的完成，重要的作业要等待不重要作业的完成。从这个意义上讲又是不公平的。 先进先出调度使响应时间的变化较小，因此它比其它大多数调度都可预测。由于这种调度方法不能保证良好的响应时间，在处理交互式用户时很少用这种方法。

20 在当今系统中，先进先出很少作为调度模式，而是常常嵌套在其它的调度模式中。
例如，许多调度模式根据优先级将处理机分配给进程，但具有相同优先级的进程却按先进先出进行分配。

21 2. 作业要求的资源 根据作业要求系统提供的处理机时间，内存的大小和I/O设备的数量，来确定作业的优先数，如果系统赋予作业的反比于系统的估计执行时间，就形成短作业优先的算法。由于作业需要的执行时间事先难于确定，只是把用户自报的估计时间作为依据，为防止用户少报自己的作业时间以获得优先服务，在采用短作业优先算法时，应采取适当的防备措施。

22 …. 4.时间片轮转算法 ①当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。
CPU F C B A 完成 A B C ①当时间片很大时，每个进程得到比完成该进程多的处理机时间，此时轮转调度模式退化为先进先出模式。 ②当时间片非常小时，上下文转换开销就成了决定因素，系统性能降低，大多数时间都消耗在处理机的转换上，只有少许用在用户的计算上。

23 这个最佳的时间片值是多少呢？显然，它将随系统而异。随负载而异，同时也随进程异。
时间片的选取是实现各种调度算法的关键之处，而时间片的独额定通常应考虑终端数目，处理机能力、各终端任务的急迫程度、外存传输速度等方面的因素。时间片轮转法亦可应用于批处理系统的处理机调度。

24 5.优先级调度算法 一种常用的进程调度算法是把处理机分配给具有最高优先数的进程（用于实时系统）
在这种算法中，首先考虑的问题是如何确定进程的优先数。 一种是静态优先数，另一种是动态优先数。 1)静态优先数 静态优先数是在系统创建时确定的，一经确定之后在整个进程运行期间不再改变，确定静态优先数的有关静特性是：在有的系统中，分配给作业的优先数还取决于它所占用的内存的多少，作业越大，占用内存越多，分配给它的优先数越低。显然，不论是根据作业的执行时间，还是根据作业的大小所确定的优先数，都有利于短作业。

25 2.动态优先数 虽然基于静态优先数的调度算法比较简单，也颇为流利，但毕竟不够精确。因为进程的优先数在它执行前就已算好，且在整个执行期间都保持不变，但随着进程的推进，计算优先数所依赖的特征很多都将随之改变，因此静态优先数并非自始至终都能准确地反映出这些特性，如果能在进程运行中，不断的随着特性的改变而修改其优先数，显然可以实现更多精确的调度，从而获得更好的调度性能，这对分时系统显得格外重要.

26 进程类型 系统中由两类进程，系统进程和用户进程。系统进程的优先数比用户进程的优先数高，特别是某些系统进程，必须赋予它一种特权，当它需要处理机时，应尽快的到满足。 例如，设备管理器中的I/O进程便是如此。这不仅是为了保证I/O设备尽可能忙碌，一提高设备利用率，，更主要的是为了避免由于响应不及时，将造成信息的丢失。在用户进程中，I/O繁忙的进程应优先与CPU繁忙的进程，以保证CPU和I/O设备之间的并行操作。在分时系统中，前台进程应优先于后台进程。

27 6 多级反馈队列 调度算法的考虑方面 调度算法的实施过程： 1 设置多级就绪队列； 2 各级就绪队列具有不同大小的时间片； 3 一个新进程在系统队列； 4 按队列优先级高到低进行进程调度； 5 一进程进入较高优先级队列时可能要重新调度。 调度算法的性能：具有较好的性能，能照顾到各种用户利益