Java任务调度（精选4篇）
Java任务调度 篇1
0 引言
信息物理融合系统 (Cyber-Physical System, 简称CPS) 是重要而且全新的研究领域。2007年7月, 美国总统科学技术顾问委员会 (PCAST) 在题为《挑战下的领先———竞争世界中的信息技术研发》的报告中将CPS列为八大关键信息技术的首位[1]。CPS是集3C (Computation、Communication、Control) [2]技术于一体的网络化物理设备系统, 可实现大型工程系统的实时感知、动态控制和信息服务, 在环境感知的基础上强调人、机、物的互联互通和深度融合, 高性能的计算能力是CPS必不可少的, 为CPS提供可能的分布式技术得以飞速发展。所谓分布式技术[3]主要指资源分布和计算分布, 资源分布是指资源分散的存储在不同计算机中;计算分布则是将计算任务分配给不同的计算节点进行分布处理, 实现快速准确的分布式管理, 保证系统的可靠性, 任务优化调度方法尤为重要。
本文在构建建筑环境CPS系统结构的基础上, 利用CPS可靠感知、实时传输、虚实同变的特点, 主要针对负责任务调度的传感器计算节点进行设计, 针对每个传感器计算节点, 按照调度优先级序列表进行任务的调度, 找寻任务被合理调度的过程, 实现更高的任务调度成功率, 有效降低任务总体完成时间。
1 CPS系统设计
世界国家的网络, 尤其是发展中国家的网络, 其资源利用率非常低。据有关统计, 网络系统的平均使用效率仅为30%左右, 甚至有的空闲率竟达到91%[4]当一些计算机处于重载状态时, 另一些计算机却处于轻载或空闲状态, 所以利用这些闲散资源为量大的计算任务服务, 能够有效的利用空闲资源, 完成大规模分布式计算, 同时可以提高系统性能[5]。
本文建筑环境CPS系统中, 在传感器普通节点中, 为其一部分节点即传感器计算节点增加配置了计算、分析和处理的功能, 实现安全资源管理、合理任务分配以及快速结果输出, 并提供各种资源环境接口。据此设计了如图一所示的CPS系统结构图。传感器普通节点感知的建筑物理环境数据信息以及用户终端的任务请求命令均发送至传感器计算节点中进行数据分析和任务处理, 信息中心将所有任务及处理结果储存, 方便用户查询, 同时根据任务处理结果发送控制命令, 通过执行器节点控制建筑物理环境。其中本文的任务调度设计主要由传感器计算节点来完成。
2 基于建筑环境CPS的RM任务调度设计
1973年1月, Liu和Layland在题为“Scheduling Algorithm for Multiprogramming in a Hard Real Time Environment”[6]的学术论文中提出了速率单调 (Rate monotonic-RM) 算法, 这是一种简单有效的按实时任务发生周期来分配任务优先级的方法, 即每个任务都有其固有的周期, 并按照任务周期的长短排列其优先级, 任务发生周期越短, 它的优先级越高, 调度总是从任务队列中先运行周期最短的任务。之后他们又相继提出了一系列基于RM调度算法的扩展算法, 均作为静态调度算法的典型代表算法被后人研究和应用。目前, RM调度算法[7]已经被用于控制系统[8]、容错系统[9]、网络系统[10]等各种不同的实时系统环境中。RM算法的任务调度过程如图二所示。
处于就绪状态的任务根据其优先级的先后等待运行, 而运行的任务可能会被更高优先级的任务抢占, 所以还需返回就绪状态, 重新排列。在RM算法中用定义DAG中的任务ti=[Ti, BLi*, Ui] (i=1, 2…, n) 来表示, 其中Ti为任务的周期, Li*表示任务的优先级 (Pi越小, 优先级越高) , 表示CPU负载率, 即所有任务的CPS负载率之和, Pi为ti的执行时间, Ti为ti任务的请求周期。
RM算法只考虑任务的周期, 为了同时兼顾具有同一周期的任务的优先级问题, 本节增加了优先权值;在调度任务的时候, 可能同时存在多个任务且其中一些任务周期很短、优先级较高, 因此本节增加了延迟状态。
2.1 增加优先权值
采用式 (1) 作为任务的优先权值。首先, 将请求任务中的一级任务标记为关键任务, 对于同一请求任务中的任务, 任务的优先级由其级数决定, 同一级的任务按优先权值排列, 但同一计算节点中需要调度的任务可能是多个请求任务中的子任务, 则按优先权值排列任务的同时还要兼顾是否为关键任务。
式 (1) 中, MP为处理单元计算能力中值, MC为链路传输能力中值。
2.2 增加延迟状态
在RM调度算法的就绪和运行两种原有状态的基础上, 增加了延迟状态, 即将未标记的非关键任务加入到延迟状态中, 使延迟状态的优先级小于就绪状态, 在就绪状态后被调度。同时, 未被标记的非关键任务只有加入到延迟状态中才可直接进入就绪状态, 其他非关键任务的请求则应首先进入延迟状态。任务ti在延迟状态中需要等待△1=r1-e1, 任务ti (i=2, 3, …, n-1) 需要等待△i=α×γi×Ui+1…n, 其中α∈[0, 1]。
当标记的关键任务ti进入到就绪状态时, ti优先进入任务调度序列表排列, 按照优先权值从大到小的顺序运行, 然后从延迟状态中选取优先权值最高的任务进入调度序列中, 等待运行;但当就绪列表中出现更高优先级的任务需要处理时, 此时运行的任务需要返回就绪状态或延迟状态 (关键任务返回就绪状态, 非关键任务返回延迟状态) 重新加入调度序列表等待运行, 如图三所示。
执行过程流程如图四所示, 将任务进行分类, 优先级高的和优先级相对较低的分别被定义为关键任务集S和非关键任务集N, 当当前任务完成时, S队列中的个数减1, 并判断S队列是否还有任务存在, 如果有, 继续调度运行;如果没有, 则将非空的N队列中的优先级最高的任务移入S中, 如此循环, 直至所有任务都完成, 其中Sum用于计数。
改进后的RM调度算法将非关键任务送入延迟状态, 推迟了其进入就绪状态的时间, 从而保护了已经进入就绪状态或已经运行的任务请求。
2.3 基于建筑环境CPS的RM任务调度设计
针对某一计算节点上的任务 (子任务) 的调度进行设计, 程序流程如图五所示。
输入:一个物理环境发出的任务信息或用户提出的任务信息 (G, t) , 其中:任务模型G, 时间限制t。
输出:最优调度列表f。
第1步:用式 (2) 判断当前系统是否调度可行, 如可行, 继续;否则重新进行路径选择, 找出其他合适的计算节点。
式 (2) 中, L () 表示一个任务的CPU占用率即负载的最小上界, 当n→∞时, L () →ln (2) ≈0.693, 当整个任务集的负载小于L () 时, RM算法调度可行。
第2步:检查就绪列表是否为空, 如果不为空, 继续;否则结束任务调度。
第3步:查询任务, 获取输入任务的有向无环图DAG参数。
第4步:随机生成的调度列表f, 求解过程中用于记录最新的调度列表。
第5步:通过式 (3) 、 (4) 算任务的优先级程度, 如果任务ti的优先级最高, 则更新调度列表;如果无最高优先级, 按照原调度列表运行。
第6步:判断是否满足最小makespan, 如果满足则结束;否则返回步骤5。
makespan表示任务的运行时间, 即任务从起始节点开始计算到终止节点完成计算所经历的时间长度, Pi, j (式3) 和Wi, j (式4) 所示:
式 (3) 中, Pi, j为执行代价, 表示任务ti在处理器节点Vj上的执行时间;假定任务ti运行在处理器节点Vf上, ti运行在处理器V上, 式 (4) 中, Wi, j为处理器Vf和Vt之间的通信时间, 如果任务ti、tj被分配到统一计算节点上, 通信时间为0。
在任务调度的过程中采用改进RM调度算法, 以运行时间最短为目标, 同时在延迟等待时间上兼顾了网络负载, 在以可计算复杂度的准确任务分配和蚁群的路径选择的基础上, 通过分别考虑关键任务和非关键任务的优先权值且增加延迟状态, 在缩短任务的执行时间和平衡方面均得到了一定的优化。
3 仿真结果与分析
在分布式CPS的计算节点中, 根据可计算复杂性的思想进行任务分配, 再采用动态调度算法进行任务调度, 并通过MATLAB仿真实验验证其优越性。
结合本文的分布式任务管理模型, 利用MAT-LAB进行仿真实验。20种传感器普通节点, 其中10个设置为传感器计算节点, 随机产生10、50、60、800和100个任务。资源的参数设置如表一所示。
对任务的完成时间makespan进行了仿真实验, 并通过与蚁群算法、遗传算法和Min-Min算法三种较为经典的任务调度算法的比较, 得出任务完成时间比较图, 如图六所示。采用本文算法, 任务完成时间均比其他三种算法短, 并随着任务数量的增加, 在缩短任务完成时间方面优势越来越明显。
在任务调度成功率方面, 本文算法较蚁群算法、遗传算法和Min-Min算法体现了优越性, 如图七所示。
从图七中可以看出, 本文算法的调度成功率几乎都达到了90%以上, 在网络环境复杂繁多的CPS中, 其具有非常好的应用前景。
通过仿真实验表明, 相对于蚁群算法、遗传算法和Min-Min算法三种比较经典的任务调度算法, 采用任务分配、路径选择和任务调度独立工作但结果又相互融合的方式进行任务调度的方案是可行的, 既可以加快任务处理的速度, 又可以增加任务调度成功率, 同时在任务分配和处理的同时, 通过图灵机服务器的记忆功能, 加快了未来数据访问速度和任务的处理速度。
参考文献
[1]President's Council of Advisers on Science and Technology (PCAST) , USA.Leadership Under Challenge:Information Technology R&D in a Competitive World:An Assessment of the Federal Networking and Information Technology R&D Program[EB/OL].
[2]何积丰.Cyber-physical Systems[J].中国计算机学会通讯, 2010, 6 (01) :25-29.
[3]张栋, 吴春明, 姜明.分布式系统中资源分配的一致性算法综述[J].信息工程大学学报, 2009, 10 (01) :37-40.
[4]王金良, 苏志强.网络使用研究进展——影响因素、后果变量及影响机制[J].西南大学学报 (社会科学版) , 2012, 38 (03) :82-88.
[5]谭朋柳, 舒坚, 吴振华.一种信息—物理融合系统体系结构[J].计算机研究与发展, 2010, (S2) :312-316.
[6]Lehoczky J P, Sha L, Ding Y.The rate-monotonic scheduling algorithm:exact characterization and average case behavior[C]Proceedings of the 10th Real-Time Systems Symposium, 1989:166-171.
[7]Tindell K W, Burns A P, Wellings A J.An extendable approach for analysing fixed priority hard real-time tasks[J].Real-Time Systems, 1994, 6 (02) :133-151.
[8]Ghosh S, Melhem R, MosséD, et al.Fault-tolerant rate-monotonic scheduling[J].Read-Time Systems, 1998, 15 (02) :149-181.
[9]Pandya M, Malek M.Minimum achievable utilization for fault-tolerant processing of periodic tasks[J].IEEE Transactions on Computers, 1998, 47 (10) :1102-1112.
[10]王宁, 屈国栋, 张洪群, 等.一种基于Eclipse RCP的任务管理系统设计与实现[J].微计算机信息, 2011, 27 (04) :119-121.
Java任务调度 篇2
任务成功概率是装备在规定任务剖面内能完成任务的概率, 是任务成功性的度量指标, 也是重要的装备保障性评估指标。当前任务成功概率评估模型多是针对单系统开展研究, 系统组成结构串联或是并联, 根据系统部件的可修复情况和修复时间分布给出任务成功概率计算公式[2—4]。文献[5, 6]给出了多种任务特点及要求情况下可修系统的任务成功概率评估模型。对多阶段任务则是研究备件保障水平对任务成功概率的影响[7—10]。网络计划技术非常适用于复杂系统的分析, 其中主要的PERT技术主要考虑工序的时间取值对任务工期的影响[11,12], 没有考虑工序单元故障及修复情况;GERT模型根据概率有多个不同的引出端[13,14], 能够很好地描述流程中活动之间的关系及状态转移, 但不适用于逻辑关系要求严格的系统可靠性问题。多数方法研究保障系统本身的可靠性及维修策略问题, 而对保障任务组成及复杂度关注不够。
鉴于此, 本文基于流水网络计划技术提出一种较为通用的任务成功概率评估仿真方法, 面向多任务要求, 在考虑系统故障及维修资源的基础上, 处理诸如弹药调度系统等此类复杂系统的任务可靠性评估问题。
1 面向多任务的调度系统分析
弹药调度系统具有显著的网络计划性质, 多任务调度过程可理解为流水网络计划的任务分段处理, 但时距关系要求严格。分析其特征如下。
(1) 调度系统由多个相互独立的分系统组成, 分系统之间工作不交叉, 都可独自进行调度任务, 只是在管理系统的统一布置下并行工作。
(2) 分系统具有相同的工序组成, 逻辑关系相同并且要求严格, 分系统按照工序关系组成调度网络计划图, 流水网络计划以此为基础。
(3) 根据资源人员等限制, 确定某些分系统参与调度工作, 最后一个分系统完成任务后才算所要求调度任务的结束。
(4) 根据任务批次量及参与调度的分系统数量, 合理分配调度任务, 工作过程中可根据状态实时调整任务分配。
(5) 分系统中工序单元故障服从一定的分布, 可通过更换件等维修工作进行完全修复, 即故障后恢复为初始完整的功能状态。
(6) 暂不考虑修复失败的情况。
通常的解析方法针对的是串 (并) 联系统的单任务成功性, 或是单部件中多任务的成功性。而弹药调度系统由于其网络结构复杂, 且任务批次量多, 尤其是工序自由时差的存在导致工序单元故障率分布函数取值范围各相不同, 系统的故障率分布函数几乎不可整合, 特别是当工序单元分布函数不同的情况下更是如此。故而采用Monte Carlo仿真方法进行任务成功概率评估, 根据各工序单元分布产生随机数, 以此计算所需数据进行统计分析。
2 基于流水网络计划的任务总工期
2.1 分系统时间参数计算
一般流水网络计划是将一个任务计划分解为多个阶段实施, 以利于工程任务连续紧凑地进行。其区别于网络计划技术的特点是工序间存在时距关系, 即某工序只需其紧前工序开始一段时间后即可实施, 而不需要其完全结束, 如图1所示。
满足时距方程的网络计划才具有流水关系, 方程如下:
式 (1) 中, Ki, i+1为开始时距 (Ki, i+1>0) ;Ji, i+1为结束时距 (Ji, i+1>0) ;ti为活动的持续时间 (ti>0) ;i为活动的代号 (i≥0) 。
而调度任务本身具有多阶段性质, 单个调度分系统任务计划的实施由多个相同的任务流程组成, 每个任务流程都具有相同逻辑顺序关系的网络图, 依照约束条件多个任务流程顺次展开, 最后一个任务流程完成时整个任务计划才算结束。只是其时距关系相对较为严格, 同一流程的工序只有在紧前工序完成后方可开始, 需要对一般流水网络计划的时距方程加上Ki, i+1≥ti条件, 关系如图2所示。此时的工序显然也满足时距关系, 这里仍称作流水网络计划技术。
在此时距关系基础上计算流水网络计划的时间参数, 这里仍以网络计划通常使用的参数作为对象;但需做出调整。假设参与调度任务的分系统共计M个, 第m个调度分系统负责Qm个批次量的任务。双代号网络计划图有n个工作节点组成, 第q个任务流程的工序i-j的时间参数以此表示为:工序持续时间Dm, qi-j、工序最早开始时间Em, qS, i-j、工序最早完成时间Em, qF, i-j、网络计划工期Tm, qp、工序最迟完成时间Lm, qF, i-j、工序最迟开始时间Lm, qS, i-j、工序总时差Tm, qF, i-j等。由于约束条件的变化, 对多任务流程的流水网络计划时间参数的通用计算公式进行修正。
2.1.1 工序最早开始 (完成) 时间
此参数不仅受同一任务流程下其紧前工序的约束, 也受限于前一任务流程的同一工序的完成时间。
(1) 网络计划起始工序:
(2) 其他工序:
式 (3) 中, Em, qS, h-i为工序i-j的各项紧前工序h-i的最早开始时间;Dm, qh-i为工序i-j的紧前工序h-i的持续时间;Em, q-1F, i-j为工序i-j的前一流程的最早完成时间。
计算从网络计划的起节点开始, 各任务流程顺着箭线方向依次逐项计算。
多任务流程的工序最早完成时间计算方法与单流程的网络计划相同, 公式为
2.1.2 网络计划工期
单个调度分系统的任务完成工期为最后一个任务流程的最后一道工序的完成时间, 本文流水网络计划中属于无规定工期情况, 各任务流程的计划工期即等于计算工期Tm, qc=max{Em, qF, i-n}, 其中Em, qF, i-n为第q个流程以终节点为完成节点的工序i-n的最早完成时间。显然此调度分系统的网络计划工期为Tmp=Tm, Qmc。则各任务流程的计划工期为不耽误下一流程完工的完成时间:
2.1.3 工序最迟完成 (开始) 时间
与最早开始时间类似, 受到其紧后工序和下一任务流程中同一工序的最迟开始时间约束。
(1) 以终节点为完成节点的工序:
(2) 其他工序:
多任务流程的工序最迟开始时间计算方法与单流程相同, 公式为
2.1.4 工序总时差
工序总时差表示该工序可以利用的机动时间, 这里仍用单流程计算公式
需要说明的是, 多任务流程工序总时差不仅对其本流程紧前紧后工序有影响, 而且影响到了其他流程工序的可利用时间。正是此参数的存在导致了不同工序相同的故障恢复时间对本分系统任务总工期的影响不同。流水网络计划中, 以各工序最迟开始时间为实际执行时间, 此时可充分利用总时差进行准备工作及任务间的休整。
2.2 总工期确定
基于单个调度分系统流水网络计划时间参数的计算, 确定整个调度任务的总工期。由2.1节可知, 只要确定了调度分系统各任务流程的工序持续时间Dm, qi-j, 就可计算出此系统的任务工期, 因此可将其表示为工序持续时间集合的函数形式:
式 (10) 中, 所有流程工序持续时间集合, 而各任务流程工序时间参数集合
整个调度任务中所有调度分系统全部完成工作后任务才算完成, 亦即是任务总工期由最后完成任务的分系统工期决定, 表示为
2.3 任务分配调整方法
由于各调度分系统组成结构相同, 对每批次调度任务的相同工序持续时间可认为是无差别的, 在任务进展顺利 (即系统各阶段无故障现象发生) 时, 分系统工期与任务批次量有关。此种情况下调度系统可靠性达到100%, 依据对式 (11) 的最小化原则即可确定各分系统的任务批次量。然而, 调度任务风险就是由系统不可预测的故障所造成的, 分析任务成功性则是考虑可能出现的系统故障对任务总工期的影响。
可以设定各分系统的同一工序i-j的故障修复时间为Ri-j。为方便计算操作, 调度任务进行时若分系统m的第q批次任务流程中某工序i-j发生故障, 可任务此时的工序持续时间增加了修复时间的增量, 表示为
考虑修复时间的分系统可形成新的工序持续时间集合, 若任务批次量不作调整, 则其工期表示为。发生故障的情况下, 分系统工期可能显著延长, 必要的情况下则需要向其他分系统转移尚未开始的任务, 其工期又与调度任务量有关, 修正分系统工期表示函数为
设定各分系统的任务量为Q=[Q1…Qm…QM], 依据式 (10) 得到的工期值, 各分系统任务量调整方法如图3所示。
在这种情况下, 以整个调度任务总工期最小化为目标, 以动态调整各分系统的任务批次量为手段来调整调度过程中个别工序故障造成的影响, 在实际可操作情况下获得了任务总工期及各分系统任务量。
3 任务成功概率计算模型
3.1 任务成功率模型
弹药调度的任务成功性表现为调度系统设定保障资源的情况下按时完成规定任务的可能性, 对应的任务成功概率是指其规定任务剖面中成功完成的概率。则可定义弹药调度系统任务成功概率为其任务成功完成总次数与任务执行总次数的比值, 应用蒙特卡罗仿真方法可以简化任务成功概率的计算, 即任务成功概率PMCS=成功完成任务的总次数/仿真总次数。
由第2节的计算可知, 调度任务成功性与上级下达的调度时间有直接关系, 这里要求的调度时间表示为TR, 第w次仿真的任务完成工期为T (w) 。显然, 当T (w) ≤TR时任务成功, 否则失败。统计得出在共计W次仿真中, 按升序关系出现的任务完工期有T=[T1T2…Tc…], 对应出现的频数为N=[N1N2…Nc…], 即有∑Nc=W, 表示其出现概率为P=[P1P2…Pc…]。以要求调度时间TR确定截断位置c', 即当c≤c'时Tc≤TR, 当c>c'时Tc>TR。根据以上描述, 则可得到仿真方法下与TR有关的任务成功概率模型:
式 (14) 表示了任务成功概率与任务要求调度时间的关系, 在加上第2节中考虑到的计划工期与流水网络计划中工序持续时间及故障修复时间的关系, 任务成功概率仿真方法如实反映了调度系统结构组成及可靠性对调度任务的影响。
3.2 仿真操作方法
3.2.1 随机数产生方法
蒙特卡洛仿真的基础工作即是产生合理的随机数, 就本文而言需要产生调度各分系统所有任务流程下的工序持续时间, 以及在此基础上根据工序单元的可靠性分布产生故障点, 进一步修复时间也可随机产生。
设总的调度任务批次量为Q, 各分系统的任务量为Q=[Q1…Qm…QM], 由于调度过程中不可预测故障的出现, Q是动态调整的。而对于每一次仿真过程而言, 各分系统工序的持续时间一旦产生之后就是固定的, 不可随任务量的增减而改变。这里为保证操作方便, 在第w次仿真过程中, 对每个分系统m的工序i-j持续时间都产生Q个, 即, 任务工期计算过程中, 根据分系统的任务量取其前Qm个进行运算, 可保证Qm≤Q。具体的数值根据工序的持续时间分布随机产生。
随机产生的时刻点落在范围内, 表示该工序单元此阶段任务过程中出现故障, 则应用公式 (12) 处理其持续时间。需要说明的是, 由于故障均可通过更换备件等措施予以排除, 可认为单元“修复如新”, 即其累计工作时间需要从0重新开始算起。
以上的相关随机数产生方法确定了各调度分系统的时间参数, 只是的维数全为总任务批次量Q, 通过任务工期的计算及任务量的调整, 可最终确定此次仿真过程中的任务总工期及各分系统的任务量。
3.2.2 仿真流程
根据随机数产生方法及通用Monte Carlo方法, 基于仿真过程的多任务调度系统任务成功概率评估流程如下。
步骤1:设定仿真次数W、调度批次量Q、参与调度的分系统数量M, w=1;
步骤2:产生各分系统工序的Q维持续时间集合, 以此为基础产生随机故障点, 修正持续时间集合为
步骤3:确定各分系统任务量Q=[Q1…Qm…QM];
步骤5:如果需要根据2.3节方法调整Q, 转步骤3, 否则转步骤6;
步骤6:若w<W, w=w+1转步骤2, 否则转步骤7;
步骤7:统计总工期为Tc的次数Nc, 获取各总工期值出现的频率P=[P1P2…Pc…];
步骤8:根据式 (14) 得到任务成功概率与要求调度时间的关系PMCS (TR) ;
步骤9:结束。
3.3 几类情况考虑
考虑到调度系统工序持续时间分布、故障概率分布、修复时间分布以及保障资源配置对任务成功性的影响, 将调度任务可能遇到的情况分为以下几类。
3.3.1 Ⅰ类情况
此类情况属于无故障条件下的任务调度, 调度系统各设施设备可靠性极高, 或设定任务下故障现象不可能发生。则仿真过程中只需确定工序持续时间, 根据均衡化原则确定调度任务分配方案, 以任务总工期最小化为目标静态确定调度时间。
3.3.2 Ⅱ类情况
通常情况下需要考虑工序可能的故障情况。工序单元的可靠性函数与其累计工作时间有关, 实际情况中必须考虑发生故障情况下的调度任务风险。由于故障发生的不可预测性, 工序故障修复时间显然影响了此分系统的任务工期, 进而可能影响调度任务总工期。若分系统的任务工期由于故障而显著延长, 则需随时调整任务分配方案, 仿真过程中这是个动态过程。进一步可讨论工序故障修复持续时间的取值, 通过其分布函数同样随机产生式 (12) 中的Ri-j。
3.3.3 Ⅲ类情况
以上两种情况下没有考虑维修资源的限制, 而有些情况下维修小组数量级备件数量会限制到故障的即是修复。此类情况下可能会出现两种结果: (1) 维修小组的限制, 倘若某工序故障时所有的维修小组已经处于忙的状态, 则修复时间Ri-j还需加上等待时间; (2) 备件数量的限制, 如果某工序故障时缺乏相应备件, 则其处于不可修复状态, 此分系统只能完成本工序之后业已开始的任务, 之前的乔杜批次量需要调整给其他分系统。
4 算例
某调度系统包括6个工序逻辑关系相同的分系统, 网络计划关系如图5所示。系统中各工序执行小组兼有维修职责, 故可不考虑维修资源对任务进度的影响, 显然属于Ⅱ类情况。下面对调度任务批次量为Q=20的任务成功概率进行仿真分析。
工序持续时间采用三时估计法确定, 其概率分布可认为是正态分布, 分布形状可由乐观时间a、最可能时间m和悲观时间b确定, 计算公式:期望、方差。工序单元故障率服从指数分布F (t) =1-e-t/λ, 故障修复时间认为是固定的。相关时间参数见表1, 时间单位为同一量纲。
仿真次数设置为W=10 000, 图6所示为当参与调度任务的分系统数量为3时的一次仿真结果, 进度条中间的数字表示此分系统的第几批次任务, 3个分系统的任务批次量依次为7、7、6, 调度时间由分系统1决定, 进度条中浅颜色为故障修复时间。调度任务成功概率随要求调度时间的变化情况如图7所示。
当参与调度的分系统数量不同时, 对应的任务成功概率及要求任务工期显然不同, 图8所示为任务成功概率分别为99.9%、99.0%和90.0%时不同分系统数量对应的要求任务工期大小。参与调度的分系统数量要求越多, 需要的资源及人员也就越多, 此参数的意义在于可供指挥决策人员综合任务工期、可靠性要求以及调度资源来确定调度方案。
5 总结
从弹药调度系统执行多任务情况出发, 分析提取了此类复杂系统的特征。应用流水网络计划技术确定了分系统固定任务下的进度时间参数, 在确定任务总工期的基础上建立了任务成功概率仿真模型。此模型具有广泛的通用性, 工序单元可服从不同的可靠性函数, 甚至只需知道工序持续时间及故障时间的取值规则和范围便可进行仿真分析, 系统结构越复杂越能体现其优越性。此方法给出了几类不同保障情形下的应用形式, 正确评估了复杂多任务下的任务成功概率, 为弹药调度方案的制定及保障资源的优化配置提供决策依据。
摘要：正确评估弹药调度系统的任务成功概率, 作为装备可靠性分析的重要内容, 是制定装备保障方案和优化配置保障资源的重要依据。针对多任务调度系统的复杂性, 以流水网络计划为框架, 计算分系统调度进度时间参数。考虑工序单元故障及修复时间的情况下动态调整分系统的任务量, 最终确定任务总工期。以此将任务总工期作为任务成功概率的比较数据, 根据工序持续时间及故障时间分布产生随机数据, 应用蒙特卡洛方法对仿真结果进行统计分析, 建立了任务成功概率评估模型。并且分析了几类维修资源配置情形下的仿真操作方法, 提高了评估方法的实际应用能力。最后, 通过一个算例验证评估方法的有效性和实用性。
总线任务随机调度技术研究 篇3
多媒体处理器要肩负着大量的音视频数据存取任务。大量多媒体数据读写任务将周期性频繁出现, 当某一任务被执行时, 就会相应延迟了总线对其他任务的响应[1]。因此, 研究如何在多媒体处理器总线对多媒体处理任务的调度十分必要而且迫切。
调度的方法有很多文献[2,3,4,5]进行了研究, 其主要的关注点在于制定优先级别和制定公平性原则。但这两者往往是矛盾的。以优先级别为主的原则, 优先级别高的任务会占据了大量的处理器时间和资源, 导致其余低级别任务无法被服务。而以公平性为主的原则, 会忽略任务的重要性, 每种类型的任务都按平均时间进行服务, 这无疑是会把一些不重要的任务抢先占据处理器的时间和资源。
本文主要研究如何兼顾考虑优先级别和公平性原则, 并调度决策过程引入随机性因素, 避免瞬时任务激增的情况影响。
1 加权公平调度
在多媒体处理器的任务队列中, 如不采用专门的调度机制, 则以先来先服务的原则进行处理。先来先服务最大的缺点就是缺少时间敏感性, 排在长任务后面的短任务要等待很长的时间。为此, 在先来先服务的基础上可以增加按优先级排队的原则, 就能使优先级高的任务优先得到服务。但是, 这种按优先级排队的方式也会带来一个问题, 就是在高优先级队列中有任务时, 低优先级队列中的任务就长期得不到服务。这导致了不公平。
为了兼顾优先级和公平性, 本文提出了加权公平调度方式。即对每种优先级的任务设置一个队列, 对队列i指派一个权重wi, 于是队列i得到的平均服务时间为wi/∑wi。这样, 多媒体处理器总线的数据率为R, 那么队列i将得到的有保证数据率Ri为
2 随机性权重
由于多媒体处理器的总线上任务不断会发生变化, 导致了每个队列中的任务数量也时刻变化。因此, 预先给每个队列指派一个固定的权重, 会给往后的任务调度造成影响。我们设计出一种新的随机性权重指派方法。
对队列i, 先指派一个值相对较大的权重wi, 按总线调度的每个时刻计算概率pi, 即
其中, 是概率pi的最大值, Liav是队列i的平均队列长度, Tmax和Tmin是平均队列长度的两个阈值。
这里采用平均队列长度的意义在于克服多媒体处理器瞬时任务激增情况导致的调度算法执行不稳定。其计算方式如下
δ为0到1之间的数。
按以上原则, 可以分析概率的变化如图1所示
最后, 队列i将得到的有保证数据率Ri修改为
3 结束语
本文主要研究了多媒体处理器在总线任务调度时的原则与技术, 提出了加权公平调度和随机性加权公平调度两种技术方案, 为芯片处理低功耗发挥作用。
摘要：多媒体处理器总线上任务繁忙, 需要有合理的调度方式才能对各种数据存储任务进行服务, 提高处理器的性能。为了兼顾任务的优先级和公平性, 本文提出了随机的加权公平调度方法, 同时克服了由于瞬时任务激增导致的调度方案不稳定的情况。
关键词：多媒体处理器,总线任务调度,随机
参考文献
[1]T.D.Riehardson, C.NicoPoulos, P.Dongkook, etal.AHy-brid SoC Interconnect with Dynamie TDMA-BasedTransaction-Less Buses and On-ChiP Networks[C].Pro-ceeding of the 19th International Conference onVLSI De-sign, Hyderabad, India, Jan 3-7, IEEE, 2006, pp.657-664.
[2]王知学嵌入式操作系统调度算法研究[D].北京中国科学院自动化研究所博士学位论文, 2003
[3]Chen J Y, Jone W B, Wang J S, et al, SegmentedBus De-sign for Low-Power System[J].IEEETransactions on VLSI Systems, vol.7, no.1, 25-29, 1999
[4]陈琳, 汪健甄, 安万先, 熊华钢.多路数据总线任务调度和仿真评价技术[J].电光与控制, 2005, 第2期, 22-26
网格任务调度模型的研究 篇4
网格任务调度模型是对网格任务调度问题的一个映射或是一种解释。一个结构合理的调度模型应该能够很好地反映任务调度问题的相关流程，完整地解释所要讨论的问题范围，并给出严密的条件约束，不至使建立的模型无解或是无可行解。本文分析研究了经典的任务调度模型，提出了一个具有两层结构的调度模型，包含树形全局调度模型和局部调度模型两层,很好地解决经典模型中存在的问题，并保证了网格调度系统具有高安全性和活性等其他优点。
1 网格任务调度模型
中心式网格调度模型和分布式网格调度模型是两种经典的网格任务调度模型。中心式网格调度模型便于管理整个网格系统，但如果发生单点失效，后果是严重的，适用于中小规模、单管理域的网格系统中;分布式网格调度模型解决了中心式模型单点失效的问题，但是也存在不足。
1.1 中心式网格调度模型
中心式网格调度模型[1,2,3,4]只有一个网格调度器(Grid Scheduler,GS)。调度器负责接受用户提交的应用并监测网格中所有计算资源的静态和动态信息，为每一个或是每一批任务映射合适的资源。中心式调度模型可分两层：第一层为网格调度器，第二层为各个网格资源的资源代理。调度器通过与资源代理通信来监测网格资源和任务的分配。
中心式网格调度模型中只有一个网格调度器，如果发生单点失效，整个网格系统就会瘫痪，用户提交的任务也将丢失，资源上处理完的任务结果无法进行返回，所以必须保证其安全性和可靠性。有效的措施是建立备用网格调度器，这样就增加了额外的经济开销。因此，中心式网格调度模型适用于中小规模、单管理域的网格系统中。
1.2 分布式网格调度模型
在分布式网格调度模型中，每个网格调度器只管理本地域的任务调度和资源管理。通过多个调度器之间的协作，为任务选择合适的资源。网格调度模型的拓扑结构是网格调度器之间相邻关系的集合。中心式模型中只有一个网格调度器，不存在调度器之间的协作，所以网格调度器的拓扑结构是空集。文献[5]中把分布式调度模型器的拓扑结构描述成一个完全图，即每个网格调度器都互相直接连接;文献[6]中把拓扑结构描述成一个非完全图;文献[7]中则把拓扑结构描述成一棵树。
完全图结构的调度模型中，当某一个单点失效时，剩余调度器的拓扑结构依然是完全图，可保证系统的安全性和可靠性，也可保证失效节点上任务的最终执行。因为每个调度器都与其它调度器连接，可以实现任务与资源的最优映射，调度器之间的任务迁移代价最小。缺点是在大规模网格中的实现代价昂贵。非完全图结构的调度模型是完全图结构调度模型的简化形式，其拓扑结构是不规则的。因此发生单点失效时，拓扑结构会发生很大的变化，原本具有相邻关系的调度器可能会不再相邻。如果非完全图具有桥[8]，失效节点恰恰是桥的端点，则该拓扑结构将分裂成两个独立的调度空间。
2 树结构的网格调度模型
树形结构的调度模型可简化网格平台的实现，降低节点的通信复杂度和便于网格资源的管理。树形结构是一种规则的拓扑结构，当发生单点失效时，可利用有关树的相关算法，对分裂成两个独立空间的部分进行合并。本文提出的调度模型采用树形结构的网格调度模型。调度模型采用两层结构：全局调度和局部调度。
2.1 全局调度模型
每个节点有一个权值P，表示该节点单位任务的处理能力。新的网格调度器加入网格或是一个网格调度器退出网格系统，此拓扑结构就根据平衡二叉树的插入和删除算法进行调整，把分裂成两个独立结构的树重新进行组合。由此可以实现网格系统的可扩展性、安全性和可靠性，如图一所示。
根节点调度器是网格系统的入口，负责接收任务和向其子节点分配任务。调度过程为：当根节点接收到任务集合时，向负载较轻的子结点进行负载迁移。如果子节点负载较重，则使任务处于等待状态，直到其子节点负载较轻或是能够自己进行处理。各层的节点与根节点的工作原理一样，负载较轻时，接受父节点分配的任务;负载较重时，向其子结点分配任务。树形结构的全局调度过程是一个可实现各个网格节点负载平衡的任务迁移过程。因此，树形结构的网格调度模型具有天然的负载平衡的优点。
2.2 局部调度模型
局部调度模型的主要功能是负责管理本地域内的任务调度和信息检测。主要模块包含有任务池、容错处理器、任务调度器和信息检测器，如图二所示。
(1)任务池
任务池保存了本域内新到达的和以往已经映射过但还没有调度的任务，任务池中的任务都是已分解的独立任务，不包含优先约束关系。任务池保存任务副本直到其执行完毕并返回结果。
(2)任务调度器
任务调度器为每个任务按照其特性分配一个相应特性的机器，并把任务发送到指定的机器上运行。任务调度器在内部节点无任务或是负载较轻的前提下向其分配任务。为了防止出现任务总是得不到执行的情况，引入了老化因子。基本思想是，将上次没有得到执行的任务在下次重新映射时让它变老，相应的提高了该任务的执行优先级。任务调度器根据老化因子来对任务进行调度。
(3)容错处理器
容错处理器具有任务死锁的检测和处理功能。当任务的等待时间超过了生命周期规定的期限，但是依然没有反馈信息，容错处理器自动认为此任务处于死锁状态，杀死此任务并重新调度。容错处理器具有节点失效的检测、处理功能。当局部管理域中的一个站点失效不可用时，任务调度器将保存在任务池中的任务副本重新分配，保证任务的最终完成。
(4)信息检测器
信息检测器的功能是及时地检测资源的动态信息。节点的负载情况采用状态驱动策略[9]，状态驱动策略可以有效地避免负载抖动，降低通信开销。如果节点的CPU占用率过低或过高，信息检测器及时主动地向任务调度器发送信息，任务调度器将根据情况进行追加调度或是进行负载迁移。
3 结束语
本文首先介绍了两种经典的网格任务调度模型，中心式网格调度模型和分布式网格调度模型，分析了各自的优点和缺点，并在其基础之上设计了具有两层结构的调度模型：全局调度和局部调度。全局调度模型采用二叉树拓扑结构，很好地解决了网格调度器的单点失效问题，并且很好地实现了各个网格调度器之间的负载平衡。
摘要：网格任务调度是采用适当的调度策略把应用程序分配到异构的计算节点上进行高效的执行并返回正确结果的过程。本文研究了经典网格任务调度模型,分析了各自的优缺点,并提出了一种包含有树形全局调度模型和局部调度模型的两层结构模型,此树形全局调度模型通过负载从根节点自上而下的迁移,能够很好地实现网格系统的负载平衡。通过二叉树的节点删除算法能够很好地解决模型中节点的失效问题,因此具有很好的安全性和可靠性。
关键词：网格,任务调度模型,树形调度模型
参考文献
[1]Martino D,Sub V.Optimal Scheduling in a Grid Using Genetic Algorithms.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:148-154.
[2]Ernemann C,Hamscher V,Schwiegelshohn U,et a1.On Advantages of Grid Computing for Parallel Job Scheduling.2nd IEEE/ACM International Sympo-sium on Cluster Computing and the Grid(CC-GRID2002),2002:31-38.
[3]Ranganathan K,Foster I.Decoupling Computa-tion and Data Scheduling in Distributed Data-Inten-sive Applications.11th IEEE International Sympo-sium on High Performance Distributed Computing,2002:352-258.
[4]Subramani V,Kettimuthu R,Srinivasan S,eta1.Distributed Job Scheduling on Computational Grids Using Multiple Simultaneous Requests.11th IEEE International Symposium on High Performance Distributed Computing,2002:359-366.
[5]Chen Hongtu,Maheswaran M.Distributed Dynam-ic Scheduling of Composite Tasks on Grid Computing Systems.16International Parallel and Distributed Processing Symposium(IPDPS’02),2002:88—97.
[6]Arora M,Das S K,Biswas R.A De-Centralized Scheduling and Load Balancing Algorithm for Hetero-geneous Grid Environments.International Conference on Parallel Processing Workshops,2002:499-505.
[7]Cao Junwei,Spooner D P,Jarvis S A,et a1.A-gent-based Grid Load Balancing Using Perfor-mance-driven Task Scheduling.International Paral-lel and Distributed Processing Symposium(IPDPS’03),2003:49-58.
[8]左孝陵,李为监,刘永才等.离散数学[M].上海:上海科学技术文献出版社,2003:280-286.