高响应比优先算法又叫什么

① 高响应比优先调度算法的原理

高响应比优先调度算法既考虑作业的执行时间也考虑作业的等待时间，综合了先来先服务和最短作业优先两种算法的特点。
该算法中的响应比是指作业等待时间与运行比值，响应比公式定义如下：
响应比 =（等待时间+要求服务时间）/ 要求服务时间,即RR=（w+s）/s=1+w/s，因此响应比一定是大于1的。
如实例：
某系统有3个作业，系统确定它们在全部到达后，再开始采用响应比高者优先的调度算法，则它们的调度顺序是什么？各自的周转时间是什么？
作业号 提交时间 运行时间
1 8.8 1.5
2 9.0 0.4
3 9.5 1.0
(1)如果都到达再算的话,等待时间=最后一个的提交时间-该作业到达的时刻
1: 9.5-8.8=0.7
2: 9.5-9=0.5
3: 0
所以响应比为（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1
1: 0.7/1.5+1=1.47
2: 0.5/0.4+1=2.25
3: 1
所以2先运行,2从9.5开始运行到9.9结束;
再以9.9时刻算响应比:
1: (9.9-8.8)/1.5+1=1.73
3: (9.9-9.5)/1+1=1.4
所以2执行完后1开始执行,从9.9执行到11.4结束
最后一个是3:从11.4开始执行到12.4结束
(2)如果不是都到达后才运行，那么在8.8时只有作业1到达，所以先运行作业1
8.8+1.5（运行时间）=10.3
到10.3的时候作业1完成，此时作业2和3都已到达所以计算其响应比
（等待时间+要求服务时间）要求服务时间=等待时间/要求服务时间+1
作业2：（10.3-9.0）/0.4+1=4.325
作业3：（10.3-9.5）/1.0+1=1.8
所以先运行作业2
10.3+0.4=10.7
到10.7运行作业3
10.7+1.0=11.7
到11.7结束

② 高响应比优先进程调度算法的特点是什么

可以说是对先来先服务调度算法（FCFS）和短作业优先调度算法（SJF）的一种补充！FCFS只考虑等待时间（也就是谁等的时间长即谁来的最早优先级）而忽视了作业的运行时间。而SJF则相反，只考虑作业的运行时间，而忽视等待时间，高响应比调度算法公式（即对两者之间的平衡）
优先权=（等待时间+要求服务时间）/有求服务时间
；既考虑了等待时间和作业运行时间，增强了处理机的性能。抽象出来就是对二者极端的平衡！我们计算专业今天刚学！！哈哈，希望帮助你！

③ 2018-06-09

一、常见的批处理作业调度算法

1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。

2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。

3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。

4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。

5.均衡调度算法，即多级队列调度算法

基本概念：

  作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)

  作业平均周转时间(T)＝周转时间/作业个数

  作业带权周转时间（Wi）＝周转时间/运行时间

  响应比＝（等待时间＋运行时间）/运行时间

二、进程调度算法

1.先进先出算法(FIFO)：按照进程进入就绪队列的先后次序来选择。即每当进入进程调度，总是把就绪队列的队首进程投入运行。

2. 时间片轮转算法(RR)：分时系统的一种调度算法。轮转的基本思想是，将CPU的处理时间划分成一个个的时间片，就绪队列中的进程轮流运行一个时间片。当时间片结束时，就强迫进程让出CPU，该进程进入就绪队列，等待下一次调度，同时，进程调度又去选择就绪队列中的一个进程，分配给它一个时间片，以投入运行。

3. 最高优先级算法(HPF)：进程调度每次将处理机分配给具有最高优先级的就绪进程。最高优先级算法可与不同的CPU方式结合形成可抢占式最高优先级算法和不可抢占式最高优先级算法。

4. 多级队列反馈法：几种调度算法的结合形式多级队列方式。

三、空闲分区分配算法

\1. 首先适应算法：当接到内存申请时，查找分区说明表，找到第一个满足申请长度的空闲区，将其分割并分配。此算法简单，可以快速做出分配决定。

2. 最佳适应算法：当接到内存申请时，查找分区说明表，找到第一个能满足申请长度的最小空闲区，将其进行分割并分配。此算法最节约空间，因为它尽量不分割到大的空闲区，其缺点是可能会形成很多很小的空闲分区，称为“碎片”。

3. 最坏适应算法：当接到内存申请时，查找分区说明表，找到能满足申请要求的最大的空闲区。该算法的优点是避免形成碎片，而缺点是分割了大的空闲区后，在遇到较大的程序申请内存时，无法满足的可能性较大。

四、虚拟页式存储管理中的页面置换算法

1.理想页面置换算法(OPT)：这是一种理想的算法，在实际中不可能实现。该算法的思想是：发生缺页时，选择以后永不使用或在最长时间内不再被访问的内存页面予以淘汰。

2.先进先出页面置换算法(FIFO)：选择最先进入内存的页面予以淘汰。

3. 最近最久未使用算法（LRU）：选择在最近一段时间内最久没有使用过的页，把它淘汰。

4.最少使用算法（LFU）：选择到当前时间为止被访问次数最少的页转换。

三、磁盘调度

1.先来先服务（FCFS）：是按请求访问者的先后次序启动磁盘驱动器，而不考虑它们要访问的物理位置

2.最短寻道时间优先（SSTF）：让离当前磁道最近的请求访问者启动磁盘驱动器，即是让查找时间最短的那个作业先执行，而不考虑请求访问者到来的先后次序，这样就克服了先来先服务调度算法中磁臂移动过大的问题

3.扫描算法（SCAN）或电梯调度算法：总是从磁臂当前位置开始，沿磁臂的移动方向去选择离当前磁臂最近的那个柱面的访问者。如果沿磁臂的方向无请求访问时，就改变磁臂的移动方向。在这种调度方法下磁臂的移动类似于电梯的调度，所以它也称为电梯调度算法。

4.循环扫描算法（CSCAN）：循环扫描调度算法是在扫描算法的基础上改进的。磁臂改为单项移动，由外向里。当前位置开始沿磁臂的移动方向去选择离当前磁臂最近的哪个柱面的访问者。如果沿磁臂的方向无请求访问时，再回到最外，访问柱面号最小的作业请求。

对一个进程来说,一个重要的指标是它执行所需要的时间. 从进程提交到进程完成的时间间隔为周转时间.也就是等待进入内存的时间,在就绪队列中等待的时间,在 CPU中执行的时间和I/O操作的时间的总和.

例1.设一个系统中有5个进程，它们的到达时间和服务时间如下，A的到达时间为0，服务时间为3；B的到达时间为2，服务时间为6；C的到达时间为4，服务时间为4；D的到达时间为6，服务时间为5；E的 到达时间为8，服务时间为2，忽略1/0以及其他开销时间，若分别按先来先服务（fFCFS）进行CPU调度，其平均周转时间为？

10.2

6.4

8.6

4.5

先来先服务调度算法

进程名  到达时间 服务时间  开始执行时间  完成时间  周转时间

A              0              3                0                3                3

B              2              6                3                9                7

C              4              4                9                13              9

D              6              5                13              18              12

E              8              2                18              20              12

周转时间 = 完成时间 - 到达时间

平均周转时间 = 所有进程周转时间 / 进程数 = （3+7+9+12+12）/ 5 = 8.6

单道批处理系统中有4个作业，J1的提交时间8.0，运行时间为2.0；J2的提交时间8.6，运行时间为0.6；J3提交时间8.8，运行时间为0.2；J4的提交时间9.0，运行时间为0.5。在采用响应比高者优先调度算法时，其平均周转时间为T为（）小时？

2.5

1.8

1.975

2.675

周转时间=作业完成时间-作业提交时间

响应比=（作业等待时间+作业执行时间）/作业执行时间

当提交J1时，只有J1作业，执行J1，J1的周转时间为2，此时时间为10.

J2、J3、J4提交时，由于正在执行J1，因此等待。

当J1执行完毕（此时时间为10），J2、J3、J4的等待时间分别为：1.4,1.2,1，

其响应比分别为：1.4/0.6+1=3.33    1.2/0.2+1=7      1/0.5+1=3，因此执行J3，J3的周转时间为1.2+0.2=1.4

当J3执行完毕（此时时间为10.2），J2和J4的等待时间分别为1.6,1.2，

其响应比分别为：1.6/0.6+1=3.66      1.2/0.5+1=3.4，因此执行J2，J2的周转时间为1.6+0.6=2.2

执行J2完毕后时间为10.8，接下来执行J4，执行完后时时间为11.3，J4的周转时间为2.3

于是平均周转时间为（2+1.4+2.2+2.3）/4=1.975

如果系统作业几乎同时到达，则使系统平均作业周转时间最短的算法是短作业优先。

例3、

现有4个同时到达的作业J1,J2,J3和J4,它们的执行时间分别是3小时,5小时,7小时,9小时系统按单道方式运行且采用短作业优先算法,则平均周转时间是()小时

12.5

24

19

6

作业到达时间执行时间开始时间完成时间周转时间

J103033

J20 5388

J30781515

J409152424

平均周转时间（3+8+15+24）/4=12.5 

有4个进程A,B,C,D,设它们依次进入就绪队列，因相差时间很短可视为同时到达。4个进程按轮转法分别运行11,7,2,和4个时间单位，设时间片为1。四个进程的平均周转时间为 （）？

15.25

16.25

16.75

17.25

17.75

18.25

A:1  4  4  3  3  2  2  2  1  1  1  共24

B:2  4  4  3  3  2  2                  共20

C:3  4                                      共7

D:4  4  3  3                              共14

字母后面的数字为等待的时间加运行时间

平均周转时间为（24+20+7+14）/4=16.25

例5、假设系统按单值方式运行且采用最短作业优先算法，有J1,J2,J3,J4共4个作业同时到达，则以下哪几种情况下的平均周转时间为10分钟?

执行时间J1:1分钟 J2:5分钟 J3:9分钟 J4:13分钟

执行时间J1:1分钟 J2:4分钟 J3:7分钟 J4:10分钟

执行时间J1:2分钟 J2:4分钟 J3:6分钟 J4:8分钟

执行时间J1:3分钟 J2:6分钟 J3:9分钟 J4:12分钟

首先，短作业优先则短时间的作业利用资源，其余的作业等待

根据平均周转时间概念，将所有作业"等待时间"加上"运行时间"除以"作业数量"即可得到平均周转时间

A： (J1执行1分钟 + J2等待1分钟 + J2执行5分钟 + J3等待6分钟 + J3执行9分钟 + J4等待15分钟 + J4执行13分钟) / 4  = 50/4 = 12.5

B：  (J1执行1分钟 + J2等待1分钟 + J2执行4分钟 + J3等待5分钟 + J3执行7分钟 + J4等待12分钟 + J4执行10分钟) / 4  = 40/4 = 10

C： (J1执行2分钟 + J2等待2分钟 + J2执行4分钟 + J3等待6分钟 + J3执行6分钟 + J4等待12分钟 + J4执行8分钟) / 4    = 40/4 = 10

D：  (J1执行3分钟 + J2等待3分钟 + J2执行6分钟 + J3等待9分钟 + J3执行9分钟 + J4等待18分钟 + J4执行12分钟) / 4  = 50/4 = 12.5

例6、假设系统中有5个进程，它们的到达时间和服务时间见下表1，忽略I/O以及其他开销时间，若按先来先服务（FCFS）、非抢占的短作业优先和抢占的短作业优先三种调度算法进行CPU调度，请给出各个进程的完成时间、周转时间、带权周转时间、平均周转时间和平均带权周转时间，完成表2。  表1 进程到达和需要服务时间  进程    到达时间    服务时间  A          0            3  B          2            6  C          4            4  D          6            5  E          8            2

表2 进程的完成时间和周转时间

                  进程                  A      B        C      D      E        平均

  FCFS          完成时间      3      9      13      18      20 

                周转时间            3      7        9      12      12      8.6

            带权周转时间      1.00 1.17  2.25  2.40    6.00      2.56

  SPF(非抢占)  完成时间    3      9      15      20      11 

                周转时间            3      7      11      14      3        7.6

            带权周转时间      1.00  1.17  1.75    2.80    1.50    1.84

  SPF(抢占)    完成时间    3      15      8      20      10 

                周转时间            3      13      4      14      2        7.2

            带权周转时间      1.00  2.16  1.00  2.80  1.00    1.59

例7、假定在单道批处理环境下有5个作业，各作业进入系统的时间和估计运行时间如下表所示：    作业  进入系统时间    估计运行时间/分钟      1            8:00                40      2            8:20                30      3            8:30                12      4            9:00                18

      5            9:10                5

如果应用先来先服务和应用最短作业优先的作业调度算法，试将下面表格填写完整。

(1) 如果应用先来先服务的作业调度算法，试将下面表格填写完整。

    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟

    1        8:00            40            8：00    8：40        40

    2        8:20            30            8：40    9：10        50

    3        8:30            12            9：10    9：22        52

    4        9:00            18            9：22    9：40        40

    5        9:10            5              9：40    9：45        35

作业平均周转时间T= 43.4  217

2）如果应用最短作业优先的作业调度算法，试将下面表格填写完整。    作业  进入系统时间  估计运行时间/分钟  开始时间  结束时间  周转时间/分钟    1        8:00            40              8：00    8：40          40    2        8:20            30              8：52    9：22          62    3        8:30            12              8：40    8：52          22    4        9:00            18              9：27    9：45          45    5        9:10            5              9：22    9：27          17作业平均周转时间T= 37.2  186

CPU和两台输入/输出设备(I1,I2)多道程序设计环境下,同时有三个作业J1,J2,J3进行,这三个作业

使用CPU和输入/输出设备的顺序和时间如下所示:

J1:I2(35ms);CPU(15ms);I1(35ms);CPU(15ms);I2(25ms)

J2:I1(25ms);CPU(30ms);I2(35ms)

J3:CPU(30ms);I1(25ms);CPU(15ms);I1(15ms);

假定CPU,I1,I2都能并行工作,J1的优先级最高,J2次之,J3优先级最低,优先级高的作业可以抢占优先级低的作业的CPU,但不能抢占I1,I2,作业从J3开始到完成需要多少时间?

④ 操作系统响应比高者优先调度算法的思想

最高响应比优先法(HRN，Highest Response_ratio Next)是对FCFS方式和SJF方式的一种综合平衡。FCFS方式只考虑每个作业的等待时间而未考虑执行时间的长短，而SJF方式只考虑执行时间而未考虑等待时间的长短。因此，这两种调度算法在某些极端情况下会带来某些不便。HRN调度策略同时考虑每个作业的等待时间长短和估计需要的执行时间长短，从中选出响应比最高的作业投入执行。 响应比R定义如下： R =(W+T)/T = 1+W/T
其中T为该作业估计需要的执行时间，W为作业在后备状态队列中的等待时间。每当要进行作业调度时，系统计算每个作业的响应比，选择其中R最大者投入执行。这样，即使是长作业，随着它等待时间的增加，W / T也就随着增加，也就有机会获得调度执行。这种算法是介于FCFS和SJF之间的一种折中算法。由于长作业也有机会投入运行，在同一时间内处理的作业数显然要少于SJF法，从而采用HRN方式时其吞吐量将小于采用SJF 法时的吞吐量。另外，由于每次调度前要计算响应比，系统开销也要相应增加

(1)等待时间相等时。则服务时间越短，优先级越高，符合SJF思想。

(2)服务时间相等时，则等待时间越长，优先级越高，符合FCFS思想。

(3)对于长作业，只要其等待时间足够长，也能获得处理机。

⑤ 高响应比算法是抢占式算法吗

非抢占式的算法。因此只有当前运行的作业/进程主动放弃处理机时，才需要调度，才需要计算响应比。

优点： 综合考虑了等待时间和运行时间（要求服务时间）等待时间相同时，要求服务时间短的优先（SJF的优点）。要求服务时间相同时，等待时间长的优先（FCFS的优点）。对于长作业来说，随着等待时间越来越久，其响应比也会越来越大，从而避免了长作业饥饿的问题。

高响应比优先算法：非抢占式的调度算法，只有当前运行的进程主动放弃cpu时（正常/异常完成，或主动阻塞）,才需要进行调度，调度时计算所有就绪进程的响应比，选响应比最高的进程上处理机。响应比=（等待时间+要求服务时间）/ 要求服务时间。

⑥ 作业调度的算法有哪些

作业调度的算法有：算法有先来先服务、最短作业优先算法、最高响应比优先算法、基于优先数调度算法。

1、算法有先来先服务

最简单的调度算法，按作业的先后顺序进行调度，只考虑每个作业的等待时间而未考虑执行时间的长短。

2、最短作业优先算法

最短作业优先算法是对先来先服务算法的改进，其目标是减少平均周转时间。对预计执行时间短的作业优先分派处理机。通常后来的短作业不抢先正在执行的作业。 只考虑执行时间而未考虑等待时间的长短。

3、最高响应比优先算法

最高响应比优先算法是对先来先服务方式和最短作业优先算法方式的一种综合平衡。最高响应比优先法调度策略同时考虑每个作业的等待时间的长短和估计需要的执行时间长短，从中选出相应比最高的作业投入执行。

4、基于优先数调度算法

优先数调度算法常用于批处理系统中。在进程调度中，每次调度时，系统把处理机分配给就绪队列中优先数最高的进程。它又分为两种：非抢占式优先数算法和抢占式优先数算法。

(6)高响应比优先算法又叫什么扩展阅读：

作业调度是指按照时间周期(年、月、日、时、分、秒等)对作业进行分割，并根据业务需求、作业长度、存储管理及依赖性关系对作业的执行方式加以调度。主要任务是从作业后备队列中选择作业进入主存运行。作业调度的功能主要有以下几方面：

1、记录各作业在系统中的状态；

2、从后备队列中挑选一部分作业投入运行；

3、从被选中的作业做好执行前的准备工作；

4、在作业执行结束时，做善后处理工作。

进行作业调度有很多作业调度算法，这些作业调度算法要实现的目标是：

1、调度对所有作业都是公平合理的；

2、应使设备有较高的利用率（提供系统利用率）；

3、每次运行尽可能多的作业（提高系统吞吐量）；

4、较快的相应时间。

⑦ 高响应比优先调度算法

- - 你是西农的吧

⑧ 怎样实现短作业优先和高响应比优先算法

1.先来先服务调度算法（FCFS）:就是按照各个作业进入系统的自然次序来调度作业。这种调度算法的优点是实现简单，公平。其缺点是没有考虑到系统中各种资源的综合使用情况，往往使短作业的用户不满意，因为短作业等待处理的时间可能比实际运行时间长得多。
2.短作业优先调度算法(SPF): 就是优先调度并处理短作业，所谓短是指作业的运行时间短。而在作业未投入运行时，并不能知道它实际的运行时间的长短，因此需要用户在提交作业时同时提交作业运行时间的估计值。
3.最高响应比优先算法(HRN)：FCFS可能造成短作业用户不满，SPF可能使得长作业用户不满，于是提出HRN，选择响应比最高的作业运行。响应比=1+作业等待时间/作业处理时间。
4. 基于优先数调度算法(HPF)：每一个作业规定一个表示该作业优先级别的整数，当需要将新的作业由输入井调入内存处理时，优先选择优先数最高的作业。
5.均衡调度算法，即多级队列调度算法
基本概念：
作业周转时间（Ti）＝完成时间(Tei)－提交时间(Tsi)
作业平均周转时间(T)＝周转时间/作业个数
作业带权周转时间（Wi）＝周转时间/运行时间
响应比＝（等待时间＋运行时间）/运行时间