Journal of Software:2000.11(1):95-103

Predicting Allocation Algorithm in Distributed Real-Time Systems
XU Jian-feng,ZHU Qing-bo,HU Ning,XIE Li
Chart / table
Similar Articles
Article :Browse 3425   Download 2792
Received:November 25, 1998    Revised:February 02, 1999
> 中文摘要: 对于分布式实时系统中的周期性任务,人们提出了一系列静态分配调度算法,有效地解决了各种特定条件下的任务分配和调度问题.这些算法的主要特点是,它们均要求被调度任务的特征参数为已知条件.然而在很多实时系统中,周期性任务的运行时间或任务数量常常是一些具有一定规律的随机过程,因而上述静态算法的效能将受到限制.在分析了特定应用背景中的处理流程之后,抽象得到两类随机任务模型,针对这两类模型介绍了在分布式实时系统中已经得到应用的静态分配调度算法SAA(static allocation algorithms),进而提出了多任务分配调度的预测算法PAA(predicting allocation algorithm).它根据周期性任务执行时间或子任务数量的统计特性,实现任务参量的合理预测和多任务的动态调度,以提高系统的实时性能.仿真结果表明,对于两类任务模型,PAA算法与SAA算法相比,在任务完成时间、负载均衡度、系统响应时间及任务夭折率等多方面均有显著改善.
Abstract:For periodic tasks in a distributed real-timesystem, a number of static allocation algorithms have been developed which solve the problem of assigning and scheduling tasks effectively under some determined conditions. The principal limitation of these approaches is that the attributes of the tasks have to be known. Sometimes the execution time or the number of subtasks of a periodic task might be a stochastic process obeying some rule. In such cases, the performance of the static schemes will decrease greatly. According to the analysis of the processing in specific application fields, the authors model two types of random tasks in distributed real-time systems and introduce the static allocation algorithms (SAA) which have been applied in engineering for the two task models separately. On the basis of SAA, a predicting allocation algorithm (PAA) is presented for the assignment and the scheduling of multitasks in distributed systems. The proposed algorithm, depending on the statistic features of the task execution time or of the number of subtasks included in the tasks, can predict the task parameters reasonably and implement dynamic allocation of the tasks, so that the system can meet the timing requirements more efficiently. The results of the simulation of the two task models have shown that compared with SAA scheme, the performance of PAA is significantly better in task finishing time, load balancing, system response time, ratio of discarded tasks, etc.
文章编号:     中图分类号:    文献标志码:
基金项目:本文研究得国家863高科技项目基金(No.863-308-19-01,863-308-19-02)资助。 本文研究得国家863高科技项目基金(No.863-308-19-01,863-308-19-02)资助。
Foundation items:
Reference text:


XU Jian-feng,ZHU Qing-bo,HU Ning,XIE Li.Predicting Allocation Algorithm in Distributed Real-Time Systems.Journal of Software,2000,11(1):95-103