多处理器调度算法实现及其Petri网建模与仿真  

Realization of multiprocessor scheduling algorithm and its modeling simulation based on Petri net

作　　者：王异奇[1] 刘青昆[1] 张健[1] 

机构地区：[1]辽宁师范大学计算机与信息技术学院,辽宁大连116081

出　　处：《计算机应用》2011年第4期938-941,共4页journal of Computer Applications

摘　　要：多处理器调度算法在嵌入式实时系统领域中起着关键的作用。根据多处理器的特点,提出一种实时多处理器动态分割并行调度算法SPara。该算法解决了此前多处理器算法,如Myopic、EDPF等仅依据截止期对任务调度产生的问题,实现了增加任务紧迫度限制的调度策略,以及针对执行时间长、截止期紧迫任务的有效调度方法。同时算法结合高级颜色时间Petri网理论进行建模并仿真。测试结果表明,SPara算法在处理器利用率以及调度成功率方面较Myopic等算法有较大提高。Multiprocessor scheduling algorithm is the key in the embedded real-time systems.According to the multiprocessor features,a new dynamic parallel scheduling algorithm of real-time multiprocessor,named Split-Parallel（SPara）,was proposed.The algorithm solved the problem that the previous algorithms,such as Myopic,EDPF,only judge by the deadline to schedule the tasks,and it was also developed by adding the restriction of the urgency and an effective method as the task with long execution time and tight deadline.Furthermore,the multiprocessor scheduling algorithm which combined the theory of high-level coloured time Petri net was analyzed by modeling,and according to the model,an example of SPara algothrim was simulated and tested.The experimental results show that SPara performances are much better than the other algorithms like Myopic in processor utilization and scheduling success ratio.

关 键 词：实时多处理器 并行调度 任务分割 PETRI网仿真 可达标识图 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]