一种基于分组与适当选取策略的实时多处理器系统的动态调度算法  

A New Dynamic Scheduling Algorithm for Real()-Time Multiprocessor Systems Based on Grouping and Properly Choosing Policies

作　　者：宾雪莲[1] 杨玉海[1] 金士尧[2] 

机构地区：[1]空军雷达学院信息工程系,武汉430019 [2]国防科技大学并行与分布处理国家重点实验室,长沙410073

出　　处：《计算机学报》2006年第1期81-91,共11页Chinese Journal of Computers

基　　金：国家自然科学基金(60073003)资助.~~

摘　　要：在分析了近视算法和节约算法缺点的基础上,提出了一种新的实时多处理器系统的动态调度算法———分组适度算法.分组适度算法包括两个策略:分组策略和适当选取策略.分组策略是为了提高资源的利用率,在保证具有较小目标函数值的任务截止期限的情况下,优先选择可以共享访问资源的任务进行扩展.适当选取策略是为了提高处理器的利用率,当任务不访问资源以及任务所需资源的最早可用时间小于系统中处理器的最小最早可用时间时,选择最早可用时间最小的处理器;否则,选择最早可用时间最接近资源的最早可用时间的处理器.模拟结果表明,分组适度算法的任务接受率高于近视算法和节约算法的任务接受率.Dynamic scheduling algorithms for real-time multiprocessor are important components of real-time systems. In this paper, a new algorithm, named Group-Proper （GP）, is presented based on analysis of the shortcomings of myopic algorithm and thrift algorithm. GP algorithm includes two policies： grouping policy and properly choosing policy （PCP）. Grouping policy is aimed to increase the utilization of resources. PCP is aimed to enlarge the utilization of CPU. On the condition of ensuring not missing the deadlines of tasks with smaller heuristic value, grouping policy prior chooses the task accessing resources in the shared mode to extend. If a task needn＇t access resources or the earliest available times of resources required by it are earlier than that of the CPU, PCP assigns the task to the CPU with the earliest available time. Otherwise, PCP assigns the task to the CPU with the closest available times to that of the resources required by it. Simulation results show that acceptance ratio of GP algorithm is higher than that of myopic and thrift.

关 键 词：多处理器 实时系统 动态调度 近视算法 最早可用时间 

分 类 号：TP302[自动化与计算机技术—计算机系统结构]