短进程优先算法探讨

1、短进程优先算法探讨 摘要：短进程优先算法在实际生活中有着广泛的应用，通过分析内排序算法中的交换排序算法思想，并对交换排序算法实现进行了加工，提出了一种新算法证明短进程优先算法平均等待时间最短。 关键词：短进程优先；平均等待时间；交换排序；冒泡排序 中图分类号：TP312文献标识码：A文章编号：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 短进程优先算法是进程调度的一种算法，其平均等待时间最短是一个著名的结论，已有很多方法进行了证明。对于一组待调度的进程依据其完成时间的长短进行由短到长的排序后进行调度就是短进程优先算法，排序过程与平均等待时间最短的结论间存在着某种联系。交换排序是一种重要的内排序方法，分析交换排序算法思想，并在其基础上提出了一种新的证明短进程优先算法平均等待时间最短的算法。 1 基本概念 1.1 短进程优先算法 短进程优先调度算法SPF是指对短进程优先调度的算法。SP

4、F算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。其进程平均等待时间最短。 1.2 交换排序 两两比较待排序元素的排序码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之。直到所有元素都排好序为止。 冒泡排序是一种最简单的交换排序。：基本方法是：设待排序元素序列中的元素个数为 n。最多作 n-1 趟，i = 1, 2, n-1。在第 i 趟中从后向前，j = n-1, n-2, ,i，顺次两两比较Vj-1.key和Vj.key。如果发生逆序，则交换Vj-1和Vj。 2 证明过程 设待调度的进

5、程序列为p1, p2,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 冒泡排序算法 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; /标志置为1,有交换 pass+; ; 2.2 加工的冒泡排序 在冒泡排序的每次交换时，总的等待时间g都会发生变化。由于j-1前面的所有进程与j后面的所有进程等待时间不变，只是进程P 的等待时间增加了Tj,而进程P 的等待时间减少了Tj-1,所以总的等待时间减少了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; /标志置为1,有交换 g=g-(Tj-1-Tj)/修正总等待时间g pass+; ; 由于Tj-1-Tj大于0，所有g在每次交换时候都在减少。由此可见在按照进程完成需要的时间由小到大排序的过程是一个总的等待时间逐渐变小的过程。当排序完成后g应该最小。如果没有发生交换则进程完成序列是短进程优先。 2.3 证明短进程优先算法平均等待时间最短 假设：存在一种进程调度序列，其平均等等待时间比短

8、进程优先更小。 按照冒泡排序法进行进程完成时间由小到大的排序，如发生交换由2.2所述可知其总的等待时间即平均等待时间逐渐变小。因为此序列不是按照进程完成时间由小到大的序列，所以必发生交换，所以不存在这样的序列比短进程优先算法平均等待时间更短。由此可得结论短进程优先算法进程平均等待时间最短。 3 结论 由于算法思想的产生，对于数学问题的证明提供了新的方法。短进程优先算法在日常生活中广泛使用，关于此算法的证明都是纯数学的，结合内排序的交换排序算法思想，提出了一种新的证明短进程优先算法平均等待时间最短的算法。 参考文献： 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