輪轉調度算法中動態時間片的CPN實現

趙麗敏 鄭文艷 王文博

摘 ?要： 基于時間片的輪轉調度算法中時間片大小影響著進程切換次數以及等待時間等方面。本文改進了時間片的取值方法，并通過顏色Petri網對該算法進行建模仿真，實驗結果證明改進后的算法在進程切換次數，等待時間方面有著更好的性能。

關鍵詞： 輪轉調度算法;顏色Petri網;時間片

中圖分類號： TP391.41 ? ?文獻標識碼： A ? ?DOI：10.3969/j.issn.1003-6970.2020.08.035

本文著錄格式：趙麗敏，鄭文艷，王文博. 輪轉調度算法中動態時間片的CPN實現[J]. 軟件，2020，41（08）：129-131

【Abstract】： The time slice size affects the process of switching times and waiting time in round robin scheduling algorithm. The paper improve the value of time slice， model and simulate of the algorithm based on the Color Petri nets. The experimental results prove that the improved algorithm has a better performance in switching times and waiting time.

【Key words】： Round robin scheduling algorithm; Coloured Petri nets; Slice

0 ?引言

基于時間片的輪轉調度算法[1-4]的基本思想是把CPU的處理時間劃分為一個固定的時間片，就緒隊列中的進程依次占用CPU。如果在當前時間片內，進程調度全部完成那么就退出就緒隊列，否則必須釋放CPU，并返回就緒隊列進行排隊，等待再次調度。

在該算法中，時間片大小的設置非常關鍵。如果時間片過大，則算法退化為FCFS算法，如果過小，則會頻繁切換進程，增加系統開銷。國內外大量學者從各個方面對輪轉調度算法進行了改進。文獻[5]對進程最后一次執行時的時間片進行適當增加，從而減少進程的切換次數。文獻[6]提出了短任務優先的動態時間片輪轉調度算法提高了調度性能。文獻[7]為解決公平性和優先級之間的矛盾提出了一種基于動態優先級驅動的RQ算法，為任務分配優先級不同的隊列，調度過程中動態調整任務優先級從而動態調整就緒隊列。文獻[8]提出動態修改時間片，隨著進程的減少，動態更改時間片為burst time的平均數，調度一次，時間片的大小更新一次。文獻[9]根據進程的到達時間和burst time動態調整每個進程時間片的大小。

本文利用顏色Petri網（CPN：Coloured Petri Nets）[10]對FCFS算法及基于時間片的輪轉調度算法進行建模仿真。通過具體實例展示等待時間與時間片取值間的關系，從而調整時間片從固定到動態取值。實驗表明，動態時間片可以減少切換次數和等待時間。

1 ?相關知識

1.1 ?進程的屬性信息

進程的屬性信息定義為如下八元組：（ID，到達時間，優先級，burst time，開始時間，結束時間，等待時間，周轉時間）。

其中，進程ID從編號1按順序自動生成;進程到達時間、服務時間分布服從參數不同的指數分布;優先級從1到10隨機生成。

1.2 ?就緒隊列的生成

進程的產生根據函數隨機生成，在不同的算法開始調度前，按策略重新對進程排序，從而生成就緒隊列。比如按先來先服務的原則，首先按到達時間進行排序，如果到達時間相同，再按優先級進行排序，如果優先級相同，那么按id進行排序。

1.3 ?就緒隊列的更新

fun RRTaskUpdateN（time： INT，startt ： INT，ltask ： LTask）=

if ltask = [] then []

else

let

val hdt = List.hd ltask

val lg= length ltask

val tst = #4hdt

in

if lg =1 andalso tst >= time then

[（#1 hdt， #2 hdt， # 3 hdt，# 4 hdt -time，startt， startt + time， startt -#2 hdt， 0）]

else if lg 1 = andalso tst < time then []

else

let

val tlt = List.tl ltask

val tlthd = List.hd tlt

val tlthd 4=#2 tlthd

in

if tst <= time then tl t

else

if tst > time

else

[（#1 hdt， #2 hdt # 3 hdt， # 4 hdt-time，startt，startt+time， startt-#2hdt， 0）] ^ ^tlt

else

tlt ^ ^[（#1 hdt， #2 hdt， #3 hdt， #4 hdt-time，sta rtt， startt+time， startt-#2 hdt， 0）]

end

end （2）

按時間片大小，對整個就緒隊列進行更新，如果判斷該進程在時間片內完成調度，那么從就緒隊列移除，否則，比較該進程在調度完成后，與下一個進程的到達時間進行比較，如果完成本次調度，下一個進程還未到達就緒隊列那么把該進程放置就緒隊列隊首，否則放在隊尾。并更新進程的剩余burst time和等待時間。

1.4 ?基于時間片的輪轉調度算法的CPN模型

圖1是基于時間片的輪轉調度算法的CPN模型。整個流程是先按照進程到達時間的先后進行排序，然后按照初始時間片進行調度，并更新就緒隊列和此輪被調度的進程信息，最后根據時間片大小調整算法，調整時間片的大小，對就緒隊列再次進行調度。重復以上過程，直至就緒隊列為空。

其中sort變遷完成根據指定的規則（可按到達時間或burst time）對進程進行排序生成就緒隊列。Compute變遷完成三部分計算，第一部分根據時間片的大小，就緒隊列隊頭的進程信息，可以占用CPU的起始時間對就緒隊列中的進程進行更新，要么進程移除就緒隊列，要么進程繼續排在隊首，要么進程排在隊尾，此項信息存在庫所SortTask中;第二部分根據時間片大小，就緒隊列中隊首進程的信息，更新下一次可以占用CPU的起始時間，此項信息存在庫所FirstTaskInformation中;第三部分更新調度完成的進程隊列信息，包括更新進程的開始服務時間，結束服務時間，等待時間和周轉時間等信息，此項信息存在庫所UpdateTask中，初始值為空。

一個進程在一個時間片的調用過程中，會出現以下兩種情況，第一，一個時間片內完成了調度，此時需要退出就緒隊列;第二，該時間片完成后并未完成整個調度，此時需要再次加入就緒隊列等待下次調度，再次加入就緒隊列分兩種情況，第一，其完成時間大于就緒隊列隊首進程的開始時間，那么需要加入隊尾;第二，其完成時間小于就緒隊列隊首的開始時間，那么需要加入隊首，直接開始下一輪調度。

2 ?實驗分析

2.1 ?時間片大小與等待時間的關系

對于基于時間片的輪轉調度算法，觀察進程的服務時間（burst time）、進程的到達時間與等待時間三者間的關系如圖2所示。圖2中FCFS/RRavg/RRmedian/ Rmax/Rmin wait time分別代表FCFS算法、時間片取值為burst time的平均值/中位數/最大值/最小值的等待時間。通過觀察發現：

對于到達時間比burst time大的進程來說，等待時間依次為FCFS最大，然后是時間片大小取值為平均值，中位數，最小值;對于到達時間比burst time小的話，時間片取值為最小值反而等待時間最長，取值為中位數稍好一些;到達時間和burst time差不多的情況下，時間片取值為最小值等待時間最短。

基于此對時間片大小進行如下改進：

如果burst time小于到達時間，則時間片改為burst time的最小值;

如果burst time與到達時間差值小于最小值則用進程的burst time;

如果差值大于最小值，則用burst time的中位數;

如果burst time大于到達時間，則時間片改為burst time的最大值。

改進后的進程等待時間與其他時間片取值對比圖如圖3所示，其中RD wait time是改進時間片取值后的等待時間，其余同圖2。

2.2 ?時間片大小與輪轉次數的關系

圖4展示了時間片大小不同的輪轉調度算法中，進程切換的次數。其中x軸取值為1代表FCFS調度算法，2-5時間片取值為burst time的最大值，最小值，平均值，中位數，6代表改進后的算法產生的切換次數。

綜合圖3和圖4可知，利用本文采用的時間片大小的取值算法，不僅切換次數可以保持最低，而且等待時間也比其他取值更短。

3 ?結論

時間片的取值影響著整個調度的性能，如果取值為固定值，既不能體現進程的優先級也不能很好的照顧到公平性。而進程的到達時間和burst time的大小關系也影響了時間片的取值?？紤]以上各種因素改進的動態時間片取值方法可以減少等待時間和切換次數。

參考文獻

[1] 湯小丹編著. 計算機操作系統第4版[M]. 西安： 西安電子科技大學出版社， 2014.

[2] 黃輝. 基于權重的MPTCP 數據調度算法設計[J]. 軟件， 2016， 37（02）; 77-80.

[3] 李嘯劍， 王智立. 虛擬化環境中服務監控調度系統的設計與實現[J]. 軟件， 2016， 37（02）： 103-106.

[4] 詹文濤， 艾中良， 劉忠麟， 等. 一種基于YARN 的高優先級作業調度實現方案[J]. 軟件， 2016， 37（3）： 84-88.

[5] 肖建明， 張向利. 一種改進的時間片輪轉調度算法[J]. 計算機應用， 2005（S1）： 447-448.

[6] 李正平， 程八意， 陳軍寧. 優先級驅動的短任務優先RTOS進程調度算法[J]. 計算機應用研究， 2014， 31（04）： 1020- 1022+1026.

[7] 李薛劍， 李凱. 一種基于動態優先級的RQ作業調度算法[J]. 小型微型計算機系統， 2017， 38（01）： 124-128.

[8] Amar Ranjan Dash， Sandipta kumar Sahu， Sanjay Kumar Samantra. An Optimized Round Robin CPU Scheduling Algorithm with Dynamic Time Quantum[J]. International Journal of Computer Science， Engineering and Information Technology. 2015： 7-26.

[9] Dibyendu Barman. Dynamic Time Quantum in Round Robin Algorithm （DTQRR） Depending on Burst and Arrival Time of the Processes[J]. International Journal of Innovative Technology and Exploring Engineering. 2013， Vol. 2（No. 4）： 60-64.

[10] 鄭文艷. 基于顏色Petri網的不確定庫存模型性能仿真[J].計算機工程與應用， 2014， 50（22）： 250-255.