高響應比優先演算法又叫什麼

① 高響應比優先調度演算法的原理

高響應比優先調度演算法既考慮作業的執行時間也考慮作業的等待時間，綜合了先來先服務和最短作業優先兩種演算法的特點。
該演算法中的響應比是指作業等待時間與運行比值，響應比公式定義如下：
響應比 =（等待時間+要求服務時間）/ 要求服務時間,即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）＝周轉時間/運行時間
響應比＝（等待時間＋運行時間）/運行時間