輪轉(zhuǎn)調(diào)度算法中動態(tài)時間片的CPN實現(xiàn)

趙麗敏 鄭文艷 王文博

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

關(guān)鍵詞： 輪轉(zhuǎn)調(diào)度算法;顏色Petri網(wǎng);時間片

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

本文著錄格式：趙麗敏，鄭文艷，王文博. 輪轉(zhuǎn)調(diào)度算法中動態(tài)時間片的CPN實現(xiàn)[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 ?引言

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

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

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

1 ?相關(guān)知識

1.1 ?進程的屬性信息

進程的屬性信息定義為如下八元組：（ID，到達時間，優(yōu)先級，burst time，開始時間，結(jié)束時間，等待時間，周轉(zhuǎn)時間）。

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

1.2 ?就緒隊列的生成

進程的產(chǎn)生根據(jù)函數(shù)隨機生成，在不同的算法開始調(diào)度前，按策略重新對進程排序，從而生成就緒隊列。比如按先來先服務(wù)的原則，首先按到達時間進行排序，如果到達時間相同，再按優(yōu)先級進行排序，如果優(yōu)先級相同，那么按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）

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

1.4 ?基于時間片的輪轉(zhuǎn)調(diào)度算法的CPN模型

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

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

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

2 ?實驗分析

2.1 ?時間片大小與等待時間的關(guān)系

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

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

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

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

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

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

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

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

2.2 ?時間片大小與輪轉(zhuǎn)次數(shù)的關(guān)系

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

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

3 ?結(jié)論

時間片的取值影響著整個調(diào)度的性能，如果取值為固定值，既不能體現(xiàn)進程的優(yōu)先級也不能很好的照顧到公平性。而進程的到達時間和burst time的大小關(guān)系也影響了時間片的取值。考慮以上各種因素改進的動態(tài)時間片取值方法可以減少等待時間和切換次數(shù)。

參考文獻

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

[2] 黃輝. 基于權(quán)重的MPTCP 數(shù)據(jù)調(diào)度算法設(shè)計[J]. 軟件， 2016， 37（02）; 77-80.

[3] 李嘯劍， 王智立. 虛擬化環(huán)境中服務(wù)監(jiān)控調(diào)度系統(tǒng)的設(shè)計與實現(xiàn)[J]. 軟件， 2016， 37（02）： 103-106.

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

[5] 肖建明， 張向利. 一種改進的時間片輪轉(zhuǎn)調(diào)度算法[J]. 計算機應(yīng)用， 2005（S1）： 447-448.

[6] 李正平， 程八意， 陳軍寧. 優(yōu)先級驅(qū)動的短任務(wù)優(yōu)先RTOS進程調(diào)度算法[J]. 計算機應(yīng)用研究， 2014， 31（04）： 1020- 1022+1026.

[7] 李薛劍， 李凱. 一種基于動態(tài)優(yōu)先級的RQ作業(yè)調(diào)度算法[J]. 小型微型計算機系統(tǒng)， 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網(wǎng)的不確定庫存模型性能仿真[J].計算機工程與應(yīng)用， 2014， 50（22）： 250-255.