短進(jìn)程優(yōu)先算法探討

1、短進(jìn)程優(yōu)先算法探討 摘要：短進(jìn)程優(yōu)先算法在實(shí)際生活中有著廣泛的應(yīng)用，通過分析內(nèi)排序算法中的交換排序算法思想，并對(duì)交換排序算法實(shí)現(xiàn)進(jìn)行了加工，提出了一種新算法證明短進(jìn)程優(yōu)先算法平均等待時(shí)間最短。 關(guān)鍵詞：短進(jìn)程優(yōu)先；平均等待時(shí)間；交換排序；冒泡排序 中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2011)24-5931-02 The Research of Short-job-first Algorithm LI Yong-xiang (The 404 Company Limited, China NationalNuclearCorporation, Lanzhou , C

2、hina) Abstract: The short-job-first algorithm has massive appliction in real life. In this paper, we analyze and revise the exchange sorting algorithm of the internal sorting category. Then we propose a new algorithm to prove that the short-job-first algorithm has the least mean waiting time. Key wo

3、rds: short-job-first; mean waiting time; exchange sorting; bubble sorting 短進(jìn)程優(yōu)先算法是進(jìn)程調(diào)度的一種算法，其平均等待時(shí)間最短是一個(gè)著名的結(jié)論，已有很多方法進(jìn)行了證明。對(duì)于一組待調(diào)度的進(jìn)程依據(jù)其完成時(shí)間的長短進(jìn)行由短到長的排序后進(jìn)行調(diào)度就是短進(jìn)程優(yōu)先算法，排序過程與平均等待時(shí)間最短的結(jié)論間存在著某種聯(lián)系。交換排序是一種重要的內(nèi)排序方法，分析交換排序算法思想，并在其基礎(chǔ)上提出了一種新的證明短進(jìn)程優(yōu)先算法平均等待時(shí)間最短的算法。 1 基本概念 1.1 短進(jìn)程優(yōu)先算法 短進(jìn)程優(yōu)先調(diào)度算法SPF是指對(duì)短進(jìn)程優(yōu)先調(diào)度的算法。SP

4、F算法是從就緒隊(duì)列中選出一估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使它立即執(zhí)行并一直執(zhí)行到完成，或發(fā)生某事件而被阻塞放棄處理機(jī)時(shí)，再重新調(diào)度。其進(jìn)程平均等待時(shí)間最短。 1.2 交換排序 兩兩比較待排序元素的排序碼，如果發(fā)生逆序(即排列順序與排序后的次序正好相反)，則交換之。直到所有元素都排好序?yàn)橹埂?冒泡排序是一種最簡(jiǎn)單的交換排序。：基本方法是：設(shè)待排序元素序列中的元素個(gè)數(shù)為 n。最多作 n-1 趟，i = 1, 2, n-1。在第 i 趟中從后向前，j = n-1, n-2, ,i，順次兩兩比較Vj-1.key和Vj.key。如果發(fā)生逆序，則交換Vj-1和Vj。 2 證明過程 設(shè)待調(diào)度的進(jìn)

5、程序列為p1, p2,pn;其完成所需要的時(shí)間分別為t1,t2,tn。 設(shè)函數(shù)：g=f(t1,t2,tn)；對(duì)于不同的進(jìn)程調(diào)度次序函數(shù)值可能不同。而n個(gè)進(jìn)程的平均等待時(shí)間取決于所有進(jìn)程總的等待時(shí)間g。 任取一進(jìn)程調(diào)度序列p1, p2,pn, t1,t2,tn。 其總的等待時(shí)間g= (n-1)t1+(n-2) t2+ tn-1，由此可見t 的發(fā)生次序即進(jìn)程的調(diào)度次序決定了g。 2.1 冒泡排序算法 template void BubbleSort (dataList& L, const int left,const int right) int pass = left+1,exchange =

6、1; while (pass = pass;j-) if (Tj-1 Tj) /逆序 Swap (Tj-1, Tj); /交換 exchange = 1; /標(biāo)志置為1,有交換 pass+; ; 2.2 加工的冒泡排序 在冒泡排序的每次交換時(shí)，總的等待時(shí)間g都會(huì)發(fā)生變化。由于j-1前面的所有進(jìn)程與j后面的所有進(jìn)程等待時(shí)間不變，只是進(jìn)程P 的等待時(shí)間增加了Tj,而進(jìn)程P 的等待時(shí)間減少了Tj-1,所以總的等待時(shí)間減少了Tj-1-Tj。 template void BubbleSort (dataList& L, const int left,const int right，double g) i

7、nt pass = left+1,exchange = 1; while (pass = pass;j-) if (Tj-1 Tj) /逆序 Swap (Tj-1, Tj); /交換 exchange = 1; /標(biāo)志置為1,有交換 g=g-(Tj-1-Tj)/修正總等待時(shí)間g pass+; ; 由于Tj-1-Tj大于0，所有g(shù)在每次交換時(shí)候都在減少。由此可見在按照進(jìn)程完成需要的時(shí)間由小到大排序的過程是一個(gè)總的等待時(shí)間逐漸變小的過程。當(dāng)排序完成后g應(yīng)該最小。如果沒有發(fā)生交換則進(jìn)程完成序列是短進(jìn)程優(yōu)先。 2.3 證明短進(jìn)程優(yōu)先算法平均等待時(shí)間最短 假設(shè)：存在一種進(jìn)程調(diào)度序列，其平均等等待時(shí)間比短

8、進(jìn)程優(yōu)先更小。 按照冒泡排序法進(jìn)行進(jìn)程完成時(shí)間由小到大的排序，如發(fā)生交換由2.2所述可知其總的等待時(shí)間即平均等待時(shí)間逐漸變小。因?yàn)榇诵蛄胁皇前凑者M(jìn)程完成時(shí)間由小到大的序列，所以必發(fā)生交換，所以不存在這樣的序列比短進(jìn)程優(yōu)先算法平均等待時(shí)間更短。由此可得結(jié)論短進(jìn)程優(yōu)先算法進(jìn)程平均等待時(shí)間最短。 3 結(jié)論 由于算法思想的產(chǎn)生，對(duì)于數(shù)學(xué)問題的證明提供了新的方法。短進(jìn)程優(yōu)先算法在日常生活中廣泛使用，關(guān)于此算法的證明都是純數(shù)學(xué)的，結(jié)合內(nèi)排序的交換排序算法思想，提出了一種新的證明短進(jìn)程優(yōu)先算法平均等待時(shí)間最短的算法。 參考文獻(xiàn)： 1 Tiejun,Jiang tianfa.Analysis of the s

9、equences in Bankers agorithmJ.Iournal of Wuhan University of Technology,2007,29(6):114-117. 2 Wang xiaodong.Design and Analysis of computer programmingM.2nd ed.Beijing:Publishing house of electronic industry,2004. 3 Chenlan.Adeadlock detection algorithm based on parallel calculationsJ.Journal of Gua

10、ngxi Science Institute,2003,2:64-68. 4 William S.Operating Systems:Internals and Design PrinciplesM.New Jersey:Prentice Hall,2003. 5 Nutt G.Operating Systems:A Modern PerspectiveM.New Jersey:Posts & Telecommunication Press,2002. 6 He yanxiang,Lifei,Lining,Operating systemsM.Modified ed.Tsinghua publ

11、ishing house,2001. 7 Lijing,Chen wanghu.Bankers algorithm based on generalized listsJ.Journal of northwest normal university,2002,38(3):30-33. 8 Duzhi hua.Use ofresource allocation graph in parallel programmingJ.Journal of Xin jiang normal university,1999,3:4-8. 9 Zhu lili,Jiao suyun,Zhou lijuan.Modification of deadlock detection based on resource allocation graphJ.Information Science,2000,5:453-455. 10 Tang xiaodan,Liang hongbing,Zhe fengping,Tang ziying.Computer operating SystemM,3rd ed.Xian:Xian ele