基于图着色的事务调度算法的设计  

Based on Graph Coloring Affairs Schedule Algorithm for the Design

作　　者：刘智珺[1] 李腊元[1,2] 

机构地区：[1]武汉生物工程学院计算机与信息工程系,湖北武汉430415 [2]武汉理工大学计算机科学与技术学院,湖北武汉430063

出　　处：《微电子学与计算机》2012年第4期97-100,共4页Microelectronics & Computer

基　　金：国家自然科学基金项目(60773211);国家软件开发环境重点实验室开放基金(SKLSDE-2011KF-01);湖北省教育厅科研项目(320114605;B20094002)

摘　　要：将处理对象抽象转换为事务,对于事务的调度问题提出了基于图着色思想的算法.将事务以及之间的联系建立事务调度模型,同时等价地转化为图着色问题,通过对图中的顶点着色来实现具有冲突的事务的调度.与一般图着色处理方式不同的是,本算法思想采用了对节点进行着色的思想来实现事务调度.基于图着色的算法的设计与实现使多事务多冲突问题得到解决、并且最大程度满足事务执行所需各元素的特殊要求.The objects convert abstract affairs,proposed algorithm for the affairs scheduling problem based on graph coloring ideas.The link between the affairs established affairs scheduling model,and convert into equivalent graph coloring problem,vertices on graph coloring to achieve the affairs of a scheduling conflict.Compared with general graph coloring approach is different,the nodes are shaded to the thought to achieve affairs scheduling.The algorithm based on graph coloring the design and implementation of more than many affairs issue has been resolved,and conflict affairs executed satisfy needed the special requirements of each element.

关 键 词：图着色 事务 事务模型 二分图 调度算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]