《短进程优先算法探讨.docx》由会员分享，可在线阅读，更多相关《短进程优先算法探讨.docx（9页珍藏版）》请在三一文库上搜索。
1、短进程优先算法探讨摘要：短进程优先算法在实际生活中有着广泛的应用，通过分析内排序算法中的交换排序算法思想，并对交换排序算法实现进行了加工，提出了一种新算法证明短进程优先算法平均等待时间最短。关键词：短进程优先；平均等待时间；交换排序；冒泡排序中图分类号：TP312文献标识码：A文章编号： 1009-3044(2011)24-5931-02The Research of Short-job-first AlgorithmLI Yong-xiang(The 404 Company Limited, ChinaNationalNuclearCorporation, Lanzhou 730020, 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 word
3、s: short-job-first; mean waiting time; exchange sorting; bubble sorting短进程优先算法是进程调度的一种算法，其平均等待时间最短是一个著名的结论，已有很多方法进行了证明。对于一组待调度的进程依据其完成时间的长短进行由短到长的排序后进行调度就是短进程优先算法，排序过程与平均等待时间最短的结论间存在着某种联系。交换排序是一种重要的内排序方法，分析交换排序算法思想，并在其基础上提出了一种新的证明短进程优先算法平均等待时间最短的算法。1 基本概念1.1 短进程优先算法短进程优先调度算法SPF是指对短进程优先调度的算法。SPF算法是从就
4、绪队列中选由一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。其进程平均等待时间最短。1.2 交换排序两两比较待排序元素的排序码， 如果发生逆序 （即排列顺序与排序后的次序正好相反） ， 则交换之。 直到所有元素都排好序为止。冒泡排序是一种最简单的交换排序。 ：基本方法是：设待排序元素序列中的元素个数为n。最多作n-1趟，i = 1, 2,，n-1 o在第i趟中从后向前，j = n-1, n-2,i,顺次两两 比较Vj-1.key和Vj.key。如果发生逆序，贝U交换Vj-1和Vj2 证明过程设待调度的进程序列为p1, p2
5、,pn;其完成所需要的时间分别为t1,t2,tn。设函数：g=f(t1,t2,tn);对于不同的进程调度次序函数值可能不同。而n 个进程的平均等待时间取决于所有进程总的等待时间 g。任取一进程调度序列p1, p2,pn, t1,t2,tn。其总的等待时间 g= (n-1)t1+(n-2) t2+ + tn-1 ,由此可见 t 的发生次序即进程的调度次序决定了 g。2.1 冒泡排序算法templatevoid BubbleSort (dataList& L, const int left,const int right) int pass = left+1,exchange = 1;while
6、(pass = pass;j-)if (Tj-1 Tj) / 逆序Swap (Tj-1, Tj); / 交换exchange = 1; / 标志置为 1,有交换pass+;在冒泡排序的每次交换时，总的等待时间 g 都会发生变化。 由于 j-1 前面的所有进程与 j 后面的所有进程等待时间不变，只是进程P的等待时间增加了Tj,而进程P的等待时间减少了 Tj-1, 所以总的等待时间减少了 Tj-1-Tj 。templatevoid BubbleSort (dataList& L, const int left,const int right ， double g) int pass = left+
7、1,exchange = 1;while (pass = pass;j-)if (Tj-1 Tj) / 逆序Swap (Tj-1, Tj); / 交换exchange = 1; /标志置为1,有交换g=g-(Tj-1-Tj)/ 修正总等待时间 gpass+;由于 Tj-1-Tj 大于 0， 所有 g 在每次交换时候都在减少。由此可见在按照进程完成需要的时间由小到大排序的过程是一个总的等待时间逐渐变小的过程。当排序完成后 g 应该最小。如果没有发生交换则进程完成序列是短进程优先。2.3 证明短进程优先算法平均等待时间最短假设：存在一种进程调度序列，其平均等等待时间比短进程优先更小。按照冒泡排序法
8、进行进程完成时间由小到大的排序，如发生交换由 2.2所述可知其总的等待时间即平均等待时间逐渐变小。因为此序列不是按照进程完成时间由小到大的序列，所以必发生交换，所以不存在这样的序列比短进程优先算法平均等待时间更短。由此可得结论短进程优先算法进程平均等待时间最短。3 结论由于算法思想的产生，对于数学问题的证明提供了新的方法。短进程优先算法在日常生活中广泛使用，关于此算法的证明都是纯数学的，结合内排序的交换排序算法思想，提出了一种新的证明短进程优先算法平均等待时间最短的算法。参考文献：1 Tiejun,Jiang tianfa.Analysis of the sequences in Banker
9、 s 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 Guangxi Science Instit
10、ute,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,OperatingsystemsM.Modified ed.Tsinghua publishing house,2001.7 Lij
11、ing,Chen wanghu.Banker s 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 det
12、ection 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. Xi an:Xi an electronic publishing house,2007.11 Andrew S.Tananbuam.Distributed OperatingSystemM.Tsinghua publishing house,Prentice Hall,1997.12 Stalling W.OperatingSystemM,NewYork:MacMillan,1992.