现代电力调度系统通过分散分布的各个远端采集单元调度终端采集覆盖密集的电网上的信息, 可实现实时数据的采集、数据计算统计和自动化系统运行状态监视等功能。为了帮助调度员及时了解掌握电力情况、更有效地利用和调配有限的电力资源, 实时监控技术一直在电力调度系统中发挥重要作用。可随着计算机技术的快速发展, 现代电力系统的结构日益复杂、规模日益扩大, 串行电力系统结构很难适应将来的运行要求, 在电力系统中引入并行处理技术成为必然趋势, 从而对实时监控技术提出更高要求。
实现并行处理机技术在电力系统的应用虽然是非常有前景的途径, 但利用并行计算必然要涉及并行算法设计、任务划分、通信的协调和同步、任务调度等难题, 其中任务调度是重中之重。如果调度问题解决得不合理, 则可能导致并行计算效率低下, 甚至计算失败。因此研究多处理机任务调度问题具有重要意义, 目前已出现了多种调度方式:排队论法、轮转法和状态空间搜索法等。本文提出一种混合任务调度算法, 该方法应用于实时监控系统能够充分挖掘出电力任务系统的并行性, 从而有效地进行任务调度。
实时监控系统主要用于实现完整的、高性能的实时数据采集和监控, 为其他应用提供全方位、高可靠性的数据服务, 从而提高系统大规模数据处理的实时性。如何将电力系统任务调度系统资源上在实时监控系统中显得至关重要。任务调度就是按照某种策略将多个任务合理或优化地分配到系统中的资源上, 以达到使任务系统执行时间最短、提高任务的相应速度并且优化系统运行效率等目标。好的调度算法能够合理运用和管理资源, 充分发挥并行的优势, 提供高性能的实时监控服务。该实时监控系统的逻辑结构图如图1所示。
现代电力调度系统通常由m个同构的处理机P={P1, P2, Pm}、f个文件服务器或数据存储系统S={S1, S2, Sf}所组成。
假设现有k个任务T={T1, T2, Tk}, 每个任务的输入为一组存储在某个数据源上的文件和数据, 数据量的大小已知, 一个文件或数据源可以为多个任务所共享。通常, 实时监控系统中的每个任务内部可能包含独立的或相互依赖的子任务, 大致可以将其划分为两种类型:独立任务和依赖任务。对于处理庞大数据量的工作任务, 将其数据分布到多个资源上并行处理, 相互之间不存在通信等问题, 这样的任务称为独立任务。依赖任务指可以划分成许多具有偏序关系的子任务的工作任务, 这些子任务可并行或串行地执行, 以便原本只能在一个资源上运行的大任务能够分配到多个资源上并行执行, 通常用DAG (Directed Acyclic graph) 图表示。
针对实时监控系统中具有内部并行性的不同类型任务, 本文提出HSA (Hybrid Scheduling Algorithm) 调度算法, 首先将每个任务划分成可并行执行的多个子任务, 然后根据各自的特征选取合适的调度方法将其分配到处理器上, 以使整个任务系统的执行时间最小, 从而有效地提高电力系统的性能。
根据实时监控系统中的任务特征, HSA调度结构图如图2所示。
本文主要用于充分考虑实时监控系统任务内的并行性并依据不同的任务特征进行任务分配, 因此, HSA调度的基本内容是:
(1) 每当有任务到达时, 调度器按照先来先服务策略将其放入调度队列。
(2) 调度器不断重复以下做法直到所有任务调度完毕:判断任务类型, 若是独立任务则调用IndepTaskSchedule划分任务并将其分配到可利用的资源上, 否则转 (3) 。
IndepTaskSchedule () 描述如下:
(1) 依据数据划分算法, 将给定任务划分为若干个没有通信和数据依赖的子任务。
(2) Repeat。
(3) 确定执行时间最长的任务为调度任务task。
(4) for each PEi∈P do。
(5) 计算ST (task, PEi) 。
(6) if (ST (task, PEi)
(7) minPE=PEi。
(8) 将任务task调度到处理机minPE上。
(9) Until所有的子任务调度完毕。
(3) 调用DAGTaskSchedule。
DAGTaskSchedule () 描述如下。
(1) 依据功能划分算法, 对给定任务进行划分并表示成DAG任务图。
(2) Repeat。
(3) 计算任务图中当前的关键路径并标识关键节点为true, 计算所有任务的最早启动时间EPST, 并将未调度的就绪CPN作为就绪任务队列的第一个节点。
(4) while仍有就绪节点未入就绪队列do。
(5) 令next为下一个就绪节点, cur为就绪任务队列的第一节点。
(6) if (flag[next]==true) 。
(7) while (EPST (next) >EPST (cur) 。
&&flag[cur]==true) 。
(8) 将cur后移, 指向下一个元素。
(9) else。
(10) while (flag[cur]==true。
||EPST (next) >EPST (cur) )
(11) cur后移一个位置。
(12) 将next插入到cur位置。
(13) 取就绪任务队列中的第一个节点为调度节点task。
(14) for each PEi∈P do。
(15) 计算ST (task, PEi) 。
(16) if (ST (task, PEi)
(17) minPE=PEi。
(18) 将task调度到处理机minPE上。
(19) Until所有节点都已调度完毕。
假定实时监控系统中依次到达3个任务, 分别为T1, T2, T3;电力系统中有4个处理器, 分别为P1, P2, P3, P4。任务T1和任务T3均为独立任务, 分解成多个互无交涉的子任务, 而依赖任务T2按功能划分为若干个具有约束关系的子任务, 用DAG图表示。各任务的划分情况见表1和图3, 其中任务旁的数值表示任务的执行时间, 边上的数值表示任务间的通信开销。
传统的调度算法从不考虑任务内部的并行性, 通常按照先来先服务策略将到达的任务分配到能够使其最早启动的系统资源上, 产生的调度情况见图4, 调度长度为30。
然而, 依据本文HSA算法, T1、T2、T3首先被划分成多个子任务, 然后再依次被分配到电力系统的各个处理器上, 其中T1和T3使用IndepTaskSchedule算法进行调度, 而T2应用DAGTaskSchedule算法。这时, 该调度器产生的调度情形如图5所示, 调度长度为21, 减少了9个执行单位。相比较传统调度算法而言, 本算法有效地减少了任务系统的执行时间。
本文将混合任务调度算法应用于实时监控系统, 能够充分发挥电力系统任务内部的并行性使得所有任务尽快完成, 并合理地利用了系统资源, 从而有效地解决电力系统调度问题。
摘要：调度问题是现代电力系统中的一个重要问题。本文分析了实时监控系统的基本结构, 根据电力系统中的任务特点提出一种混合任务调度算法, 此算法可以充分挖掘电力任务系统的并行性, 有效地提高系统性能。
关键词：电力系统,实时监控系统,混合任务调度算法,并行性
[1] Yu-Kwong Kwok, Ishfaq Ahmad.Benchmarking and Comparison of theTask Graph Scheduling Algorithms[J].Parallel and Distributed Computing, 1999, 59 (3) :381～422.
[2] T.Hagras, J.Janecek.Static vs.DynamicList-Scheduling Performance Comparision[J].Acta Polytechnica, 2003.
[3] Hwang J J, Chow Y C, F, Anger FD, Lee C Y.Scheduling PrecedenceGraphs in Systems with InterprocessorCommunication Times[J].SIAM Jour-nal on Computing, 1989, 18 (2) :244～257.
[4] Wang M Y, Gajski D D.Hypertool:AProgramming Aid for Message-pass-ing Systems[J].IEEE Transactions onParallel and Distributed Systems, 1990, 1 (3) :330～343.
[5] 石威, 郑纬民.相关任务图的均衡动态关键路径调度算法[J].计算机学报, 2001, 24 (9) :991～997.SHI Wei, ZHENG Wei-Min.The Bal-anced Dynamic Critical Path Schedul-ing Algorithm of Dependent TaskG ra p hs[J].C h in es e J o ur na l o fComputers, 2001, 24 (9) :991～997.
[6] J.B arbos a, A.P.Mon teiro.A L istScheduling Algorithm for SchedulingMuti-user Jobs on Clusters[J].Com-puter Science, 2008, 5336:123～136.
[7] Ishfaq Ahmad, Yu-Kwong Kwok.OnExploiting Task Duplication in ParallelProgram Scheduling[J].IEEE Transac-tions on Parallel and DistributedSystems, 1998, 9 (9) :872～892.
[8] H.Topcuoglu, S.Hariri, M.Y.W u.Performance-Effective and Low-Com-plexity Task Scheduling for Hetero-geneous Computing[J].IEEE Transac-tions on Parallel and DistributedSystems, 2002, 13 (3) :260～27.
推荐阅读：
电网监控与调度自动化06-05
监测监控系统在煤矿中的重要性05-25
船舶机舱智能监控系统的研究06-05
传输网管监控系统设计和应用研究论文06-29
机房监控系统05-26
小区监控系统方案05-28
机房环境监控系统方案06-29
闭路监控系统设计方案06-06
监控采购协议06-14
