短进程优先算法探讨

短进程优先算法探讨摘要：短进程优先算法在实际生活中有着广泛的应用，通过分析内排序算法中的交换排序算法思想，并对交换排序算法实现进行了加工，提出了一种新算法证明短进程优先算法平均等待时间最短。关键词：短进程优先；平均等待时间；交换排序；冒泡排序中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)24-5931-02TheResearchofShort-job-firstAlgorithmLIYong-xiang(The404CompanyLimited,ChinaNationalNuclearCorporation,Lanzhou730020,China)Abstract:Theshort-job-firstalgorithmhasmassiveapplictioninreallife.Inthispaper,weanalyzeandrevisetheexchangesortingalgorithmoftheinternalsortingcategory.Thenweproposeanewalgorithmtoprovethattheshort-job-firstalgorithmhastheleastmeanwaitingtime.Keywords:short-job-first;meanwaitingtime;exchangesorting;bubblesorting短进程优先算法是进程调度的一种算法，其平均等待时间最短是一个著名的结论，已有很多方法进行了证明。对于一组待调度的进程依据其完成时间的长短进行由短到长的排序后进行调度就是短进程优先算法，排序过程与平均等待时间最短的结论间存在着某种联系。交换排序是一种重要的内排序方法，分析交换排序算法思想，并在其基础上提出了一种新的证明短进程优先算法平均等待时间最短的算法。1基本概念1.1短进程优先算法短进程优先调度算法SPF是指对短进程优先调度的算法。SPF算法是从就绪队列中选出一估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时，再重新调度。其进程平均等待时间最短。1.2交换排序两两比较待排序元素的排序码，如果发生逆序(即排列顺序与排序后的次序正好相反)，则交换之。直到所有元素都排好序为止。冒泡排序是一种最简单的交换排序。：基本方法是：设待排序元素序列中的元素个数为n。最多作n-1趟，i=1,2,…,n-1。在第i趟中从后向前，j=n-1,n-2,…,i，顺次两两比较V[j-1].key和V[j].key。如果发生逆序，则交换V[j-1]和V[j]。2证明过程设待调度的进程序列为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'+…+t'n-1，由此可见t的发生次序即进程的调度次序决定了g。2.1冒泡排序算法templatevoidBubbleSort(dataList&L,constintleft,constintright){intpass=left+1,exchange=1;while(pass=pass;j--)if(T[j-1]T[j]){//逆序Swap(T[j-1],T[j]);//交换exchange=1;//标志置为1,有交换}pass++;}};2.2加工的冒泡排序在冒泡排序的每次交换时，总的等待时间g都会发生变化。由于j-1前面的所有进程与j后面的所有进程等待时间不变，只是进程P的等待时间增加了T[j],而进程P的等待时间减少了T[j-1],所以总的等待时间减少了T[j-1]-T[j]。templatevoidBubbleSort(dataList&L,constintleft,constintright，doubleg){intpass=left+1,exchange=1;while(pass=pass;j--)if(T[j-1]T[j]){//逆序Swap(T[j-1],T[j]);//交换exchange=1;//标志置为1,有交换g=g-(T[j-1]-T[j])//修正总等待时间g}pass++;}};由于T[j-1]-T[j]大于0，所有g在每次交换时候都在减少。由此可见在按照进程完成需要的时间由小到大排序的过程是一个总的等待时间逐渐变小的过程。当排序完成后g应该最小。如果没有发生交换则进程完成序列是短进程优先。2.3证明短进程优先算法平均等待时间最短假设：存在一种进程调度序列，其平均等等待时间比短进程优先更小。按照冒泡排序法进行进程完成时间由小到大的排序，如发生交换由2.2所述可知其总的等待时间即平均等待时间逐渐变小。因为此序列不是按照进程完成时间由小到大的序列，所以必发生交换，所以不存在这样的序列比短进程优先算法平均等待时间更短。由此可得结论短进程优先算法进程平均等待时间最短。3结论由于算法思想的产生，对于数学问题的证明提供了新的方法。短进程优先算法在日常生活中广泛使用，关于此算法的证明都是纯数学的，结合内排序的交换排序算法思想，提出了一种新的证明短进程优先算法平均等待时间最短的算法。参考文献：[1]Tiejun,Jiangtianfa.AnalysisofthesequencesinBanker’sagorithm[J].IournalofWuhanUniversityofTechnology,2007,29(6):114-117.[2]Wangxiaodong.DesignandAnalysisofcomputerprogramming[M].2nded.Beijing:Publishinghouseofelectronicindustry,2004.[3]Chenlan.Adeadlockdetectionalgorithmbasedonparallelcalculations[J].JournalofGuangxiScienceInstitute,2003,2:64-68.[4]WilliamS.OperatingSystems:InternalsandDesignPrinciples[M].NewJersey:PrenticeHall,2003.[5]NuttG.OperatingSystems:AModernPerspective[M].NewJersey:Posts&TelecommunicationPress,2002.[6]Heyanxiang,Lifei,Lining,Operatingsystems[M].Modifieded.Tsinghuapublishinghouse,2001.[7]Lijing,Chenwanghu.Banker’salgorithmbasedongeneralizedlists[J].Journalofnorthwestnormaluniversity,2002,38(3):30-33.[8]Duzhihua.Useofresourceallocationgraphinparallelprogramming[J].JournalofXinjiangnormaluniversity,1999,3:4-8.[9]Zhulili,Jiaosuyun,Zhoulijuan.Modificationofdeadlockdetectionbasedonresourceallocationgraph[J].InformationScience,2000,5:453-455.[10]Tangxiaodan,Lianghongbing,Zhefengping,Tangziying.ComputeroperatingSystem[M],3rded.Xi’an:Xi’anelectronicpublishinghouse,2007.[11]AndrewS.Tananbuam.DistributedOperatingSystem[M].Tsinghuapublishinghouse,PrenticeHall,1997.[12]StallingW.OperatingSystem[M],NewYork:MacMillan,1992.