趙麗敏 鄭文艷 王文博

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

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

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

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

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

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

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

1 ?相關(guān)知識

1.1 ?進(jìn)程的屬性信息

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

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

1.2 ?就緒隊(duì)列的生成

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

1.3 ?就緒隊(duì)列的更新

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）

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

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

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

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

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

2 ?實(shí)驗(yàn)分析

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

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

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

基于此對時(shí)間片大小進(jìn)行如下改進(jìn)：

如果burst time小于到達(dá)時(shí)間，則時(shí)間片改為burst time的最小值;

如果burst time與到達(dá)時(shí)間差值小于最小值則用進(jìn)程的burst time;

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

如果burst time大于到達(dá)時(shí)間，則時(shí)間片改為burst time的最大值。

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

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

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

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

3 ?結(jié)論

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

參考文獻(xiàn)

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

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

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

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

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

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

[7] 李薛劍， 李凱. 一種基于動(dòng)態(tài)優(yōu)先級的RQ作業(yè)調(diào)度算法[J]. 小型微型計(jì)算機(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].計(jì)算機(jī)工程與應(yīng)用， 2014， 50（22）： 250-255.