一种改进有限期作业排序算法研究.docVIP

一种改进的有限期作业排序算法研究 　　摘要:提出了作业最晚运行次序的概念,改进算法的时间复杂度完全取决于排序算法的时间复杂度,并且改进算法可以直接得到最大效益作业子集的一种可行运行次序。 　　关键词:有限期作业;贪心方法;作业最晚运行次序;排序 　　中图分类号:TP301.6 文献标识码:A 文章编号:1672-3198(2010)02-0252-02 　　 　　1 改进算法 　　1.1 算法思想 　　改进的有限期作业排序的贪心方法:取得最大效益的作业子集一定是运行作业数目最多的子集,在不考虑获得最大效益的前提下,首先将n个作业按有限期从小到大排序,然后求出在一批作业中CPU最多能运行的作业数目m(m* pData,int count) 　　{ int i,j; 　　 int k; 　　 Job* t; 　　 for(i=0;ideadline(*pData)[j]-deadline)k=j; 　　if(k!=i){t=(*pData)[i];(*pData)[i]=(*pData)[k];(*pData)[k]=t;} 　　 } 　　} 　　long runMostJobNumber(vector* pVecPJob) 　　{ int t=0; 　　int i; 　　for(i=0;ideadline )t++; 　　 return t; 　　} 　　1.3 设置作业的最晚运行次序 　　作业最晚运行次序依赖于具体一个作业集合,同一个作业在不同作业集合中时其最晚运行次序值可能是不同的。如果一个作业在一个作业集中运行的次序大于它的最晚运行次序,那么无法获得该作业的效益值,因为CPU运行到改该作业时作业已过期。根据m给每个作业设置CPU运行该作业的最晚次序(lateRunOrder)。作业集仍按deadline从小到大有序,将排列中最后一个作业的最晚运行次序设为m。然后从排列倒数第二个作业开始依次给剩下的作业设置最晚运行次序,作业的最晚运行次序按以下原则设置:对于任一对相邻的两个作业,如果前一个作业的期限值小于它后面作业的期限值,那么前一个作业的最晚运行次序等于它后面一个作业最晚运行次序减1,否则两个作业的最晚运行次序相同。具体算法如下: 　　void setJobLateRunOrder(vector* pVecPJob,int mostJobNumber) 　　{ int i; 　　 int lateRunOrder=mostJobNumber; 　　 int s=(*pVecPJob).size(); 　　 ((*pVecPJob)[s-1])-lateRunOrder=lateRunOrder; 　　 for(i=s-2;i=0;i--){ 　　if(((*pVecPJob)[i])-deadlinedeadline ){ 　　lateRunOrder--; 　　((*pVecPJob)[i])-lateRunOrder=lateRunOrder; 　　} 　　else ((*pVecPJob)[i])-lateRunOrder=lateRunOrder; 　　 } 　　} 　　1.4 求解作业集的最大效益 　　定义一个能存储m个Job对象的数组,数组初始化为空,即未保存任何作业对象。首先将作业集按效益值从大到小排序,然后按下述规则用m个Job对象把数组填满:取有序排列中的第一个作业,试着将作业放入数组中,首先尝试作业在数组中存放位置和该作业的lateRunOrder相同。如果第lateRunOrder数组元素没有放入作业,则将作业放放在此第lateRunOrder数组元素中;如果第lateRunOrder数组元素中早有作业放入,则从数组的第lateRunOder-1个数组元素直到第1个数组元素反向查找作业在数组中的放入位置,如果能找到,就将作业放在首次发现的未放入作业的数组元素中,如果找不到就将该作业舍弃,然后开始查找下一个作业在数组中的存放位置,也就是首先试着将作业放入第lateRunOder-1个数组元素,如果该数组元素中没有作业,那么作业就放入这个数组元素中,否则将作业放入它左边的第1个空着的数组元素中。按着上述规则试着依次将作业放入数组中,只要数组中填满m个Job对象,就停止比较其它作业能否放在数组中,剩余的作业全部被忽略,此时数组中存放的作业子集j就是CPU运行作业集能获得最大效益的作业子集,并且数组中作业的存放次序就是CPU运行该子集的一种可行顺序。之所以按上述规则将作业放入数组中,是因为作业运行地最晚次序是lateRunOrder,但作业可以在最晚运行次序之前运行。具体算法如下: 　　void so