欢迎来到知嘟嘟! 联系电话:13095918853 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13095918853
知嘟嘟经纪人
收藏
专利号: 2018109893185
申请人: 西安工业大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2024-01-05
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.基于准划分思想的混合关键任务调度方法,其特征在于,具体包括以下步骤:步骤1、对于具有M个处理器核的混合关键系统中n个周期性混合关键任务,按照基于负载均衡的分配方法对其进行局部划分和全局划分;

步骤2、按照基于高利用率的准划分方法对于全局调度队列中的每个任务进行全局调度;

步骤3、按照基于最少迁移度的准划分方法对系统中每一个处理器核在其运行周期内的任务预分配。在系统运行过程中,如果系统关键级别提升时,则执行步骤4,如果系统关键级别降低时,则执行步骤5;

步骤4、根据当系统关键级别提升时的任务负载均衡分配方法对系统中部分任务进行调整,转去执行步骤1;

步骤5、根据当系统关键级别降低时的任务负载均衡分配方法对系统中部分任务进行调整,转去执行步骤1。

2.根据权利要求1所述调度方法,其特征在于,步骤1中的基于负载均衡的分配方法具体包括以下步骤:步骤101、将n个待分配任务队列中的周期性混合关键任务,计算各个任务的最大利用率wi,并以此对待分配任务队列的任务进行降序排序;

步骤102、选择在系统当前关键级时利用率最低的处理器核corep(1≤p≤M),如果该处理器核利用率Up与待分配任务队列中的队首任务τi(1≤i≤n)的利用率ui之和小于等于1,则将任务τi加入到处理器核corep的局部就绪任务队列,并计算该任务在核运行周期θp内的执行时间片数δi,p,从待分配任务队列中删除任务τi,更新处理器核corep的利用率Up,否则,将任务τi从待分配任务队列中删除,将其加入到全局调度队列,重复第102步,直到待分配任务队列为空,算法结束。

3.根据权利要求1所述调度方法,其特征在于,步骤2中的基于高利用率的准划分方法具体包括以下步骤:步骤201、对于全局调度队列中的周期性混合关键任务,按照系统当前关键级别时任务的利用率进行降序排序;

步骤202、对于全局调度队列中的每一个任务τi,选择M个处理器核中剩余核利用率与该任务τi的利用率最接近的处理器核corep,计算在核运行周期θp内任务τi在处理器核corep上的可分配的执行时间片额度δi,p,并将其加入到该核的局部就绪任务队列;在核运行周期θp内任务τi的剩余执行时间片数按照同样方法分配到其它核上。

4.根据权利要求1所述调度方法,其特征在于,步骤3中的基于最少迁移度的准划分方法具体包括以下步骤:步骤301、计算处理器核corep的运行周期分段划分基数ωp;

步骤302、计算处理器核corep的运行周期内的预分配时间分段数υp;

步骤303、每个任务τi(0≤i≤np)的剩余预分配时间额度σi置为0,并设k=1,k表示预分配时间分段序号,1≤k≤υp;

步骤304、计算任务τi在第k个预分配时间分段上预分配的时间片数tsi,k;

步骤305、如果tsi,k≤δi,p,则计算任务τi在第k个预分配时间分段内实际预分配的时间片数dtsi,k,修改δi,p=δi,p-dtsi,k,同时,计算该任务的剩余预分配时间额度σi,否则dtsi,k=δi,p,修改δi,p=0,σi=0;同样方法,依次处理下一个任务,直到该核上局部就绪任务队列的所有任务都处理完毕;

步骤306、计算该核在运行周期的第k个预分配时间分段内实际已分配的时间片数cdtsk;

步骤307、如果cdtsk<ωp,则从{σ1,σ2,L,σnp}中选择其中的最大值σx(σx>0)对应的任务τx,将其dtsx,k的值加1,同时修改δx,p=δx,p-1,σx=σx-1;重复执行第306步,直到cdtsk=ωp或σx=0为止;

步骤308、完成下一个预分配时间分段的时间片分配,即k=k+1,如果k≤υp,则重复执行第304步;

步骤309、对于预分配时间分段内的时间片具体分配,根据任务到达时间,以可抢占方式,按照时限的先后进行分配。

5.根据权利要求1所述调度方法,其特征在于,步骤4中的当系统关键级别提升时的任务负载均衡分配方法具体包括以下步骤:步骤401、计算系统在关键级l下的系统利用率U(l),如果U(l)>M,那么,在当前系统关键级下,系统不可调度,算法结束;

步骤402、依次判断全局调度队列中的每一个任务的关键级别是否小于系统当前关键级别l(1≤l≤L),如果是,则将该任务从全局调度队列中删除,同时,将其加入到任务挂起队列,否则,将任务从全局调度队列中删除,同时,将其加入到待分配任务队列;

步骤403、判断处理器核corep(1≤p≤M)上已经分配的所有任务的关键级别是否小于系统当前关键级别l,如果是,则将该任务从该处理器核的局部就绪任务队列中删除,同时,将其加入到任务挂起队列;

步骤404、按照系统当前的关键级别,重新计算该处理器核的利用率Up;如果Up大于1,则依次将该核局部就绪任务队列中在当前系统关键级别下利用率最低的任务删除,将其加入到待分配任务队列,直到Up小于等于1;

步骤405、处理下一个处理器核,重复第402步,直到所有的处理器核处理结束;

步骤406、对于待分配任务队列,按照基于负载均衡的分配算法重新分配任务。

6.根据权利要求1所述调度方法,其特征在于,步骤5中的当系统关键级别降低时的任务负载均衡分配方法具体包括以下步骤:步骤501、依次判断任务挂起队列中的每一个任务的关键级别是否大于等于系统当前关键级别,如果是,则将该任务从任务挂起队列中删除,同时,将其加入到待分配任务队列;

步骤502、依次将全局调度队列中的每一个任务从全局调度队列中删除,同时,将其加入到待分配任务队列;

步骤503、对于待分配任务队列,按照基于负载均衡的分配算法重新分配任务。