多核下一种线程调度算法的研究与实现.pdfVIP

第23卷摇 第10期 计 算机 技 术 与发 展 Vol.23摇 No.10 2013年10月 摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 COMPUTERTECHNOLOGY AND DEVELOPMENT摇 摇 摇 摇 摇 摇 摇 摇 摇 摇 Oct.摇 2013 多核下一种线程调度算法的研究与实现 林摇 英,孟摇 正,康摇 雁,于摇 倩 (云南大学软件学院,云南 昆明 650091) 摘摇 要:随着多核处理器的出现,多核系统线程调度算法成为了一个重要的研究方向,基于DAG表示并行任务在多处理机 上进行处理的研究由来已久。 文中提出一个基于DAG及Petri 网的调度算法,通过把DAG转换为Petri 网,希望以直观的 方式表达需调度任务的并发、顺序、冲突、同步等关系。 该算法充分考虑调度任务之间的并行性,使得并行任务能够并行 调度在不同的处理器上,从而有效缩短任务图的调度长度。 结果表明,通过有效挖掘Petri 网的并行性,能够得到具有较好 并行性的任务调度序列,通过合理分配该任务调度序列,可以得到较好的调度性能。 关键词:多核;线程调度;有向图环图;Petri 网 中图分类号:TP391摇 摇 摇 摇 摇 摇 文献标识码:A摇 摇 摇 摇 摇 摇 摇 文章编号:1673-629X(2013)10-0019-04 doi:10.3969/ j.issn.1673-629X.2013.10.005 Research and Implementation of a Thread Scheduling Algorithm in Multi-core Environment LIN Ying,MENG Zheng,KANG Yan,YU Qian (College of Software,Yunnan University,Kunming650091,China) Abstract:With the emergence of multi-core processors,thread scheduling algorithm in multi-core environment has been becoming an important researchdirection,andtheresearchoftheparalleltasksbasedonDAGinthemultiprocessingmachineforprocessinghasalong history.By converting DAGtoPetri net,proposeda schedulingalgorithmbased on DAGandPetri net,andhopedto expressconcurrent, sequential,conflict and synchronizationrelationshipsof schedulingtasksin aintuitiveway.Through schedulingparalleltaskson different processors,it can effectively shorten the scheduling length.The results showed that through effectively mining the parallelism of Petri nets,can obtain better parallelism task scheduling sequence,by reasonable distribution of the task scheduling sequence,can get a better scheduling performance. Key words:multi-core;thread scheduling;DAG;Petri net 0摇 引摇 言