高回響比優先調度算法

高回響比優先調度算法(Highest Response Ratio Next)是一種對CPU中央控制器回響比的分配的一種算法。HRRN是介於FCFS(先來先服務算法)與SJF(短作業優先算法)之間的折中算法,既考慮作業等待時間又考慮作業運行時間,既照顧短作業又不使長作業等待時間過長,改進了調度性能。

定義

高回響比優先調度算法的基本思想是把CPU分配給就緒佇列中回響比最高的進程。

基本思想

短作業優先調度算法 + 動態優先權機制

既考慮作業的執行時間也考慮作業的等待時間,綜合了先來先服務和最短作業優先兩種算法的特點。

原理

高回響比優先調度算法既考慮作業的執行時間也考慮作業的等待時間,綜合了先來先服務和最短作業優先兩種算法的特點。

該算法中的回響比是指作業等待時間與運行比值,回響比公式定義如下:

回響比 =(等待時間+要求服務時間)/ 要求服務時間,即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.25

作業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結束

優缺點

短作業與先後次序的兼顧,且不會使長作業長期得不到服務

回響比計算系統開銷,增加系統開銷

適用場合

批處理系統

主要用於作業調度

相關詞條

相關搜尋

熱門詞條

聯絡我們