实时异构系统的集成动态调度模型与算法研究
|
摘要
实时异构系统已被广泛应用在航空航天、工业控制、电讯行业、图像处理以及Internet应用等诸多领域。在这些应用中，存在大量的硬、软实时任务共存的情况，对实时异构系统的集成动态调度模型与算法的研究具有重大理论和实际意义。本文对实时异构系统的集成动态调度问题进行了深入的研究，提出了一种实时异构系统的集成动态调度模型，基于这种模型，提出批优化的调度策略和批任务在处理器上运行的目标函数构造原则。在此基础上，提出了一种基于分批优化的实时异构系统的集成动态调度算法——GOIDSH算法。
本文针对实时异构多任务调度的特点，采用集中式调度模型；提出软、硬实时任务形式化描述非精确计算的统一任务模型，清晰地描述实时任务的特点。系统任务描述简单，节省存储空间，为实现基于批优化的集成动态调度打下基础。
论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础，主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分，采用统一形式完成了实时异构系统的集成动态调度。同时，在构造目标函数时，算法还引入软实时任务服务质量(Ouality of Service，Qos)降级策略来提高调度成功率。
GOIDSH算法的核心思想是：在每次扩充当前局部调度时，首先按一定规则在待调度的任务集中选取一批任务组成任务子集，保证所选取的任务子集中某一任务对某个资源有访问需求时，子集中的其它任务不能对该资源有访问需求。然后，综合各种因素，对该批任务中的每项任务在每个处理器上的运行构造目标函数，将问题转化为非平衡指派问题，利用非平衡指派问题直接解法对任务进行优化分配，一次性为这些任务分配一个处理器或为每个处理器分配一项任务，使得这种分配具有最好的“合适性”，增大未被调度任务的被成功调度的可行性。
论文通过仿真和模拟，从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面，验证了GOIDSH算法的有效性及其调度性能。在仿真实验时，提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则：
①任务的截止期越近，其价值越高；
②任务需要访问的资源越多，其价值越高；
③任务要需访问的资源中，互斥方式的访问越多，其价值越高；
④任务的空闲时间越短，其价值越高；
⑤相同情形下，硬实时任务的价值高于软实时任务的价值。
仿真实验结果表明，基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题，而且还有效地提高了调度成功率，确保了软实时任务具有良好的服务质量，与其它相关算法，如传统的近视算法和节约算法相比较，具有明显优势。
Real-time heterogeneous systems are used widely in the field of flight control and avionics, processing control, telecommunication, imagine processing and Internet applications. Many of these applications involve hard and soft real-time tasks. It is very important to study of integrated dynamic scheduling model and algorithm for real-time heterogeneous systems. This paper has made the research thoroughly on the integrated dynamic scheduling issue. In this paper, a new model for integrated dynamic scheduling of real-time heterogeneous systems is presented. Basing on the model, a new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems.
In allusion to characteristics of real-time heterogeneous multitask scheduling, a centralized scheme is assumed in this paper and an integrated task model for real-time heterogeneous systems, called uniform form task model, is proposed. This task model uniformly characterizes hard and soft real-time tasks in real-time heterogeneous systems clearly by using imprecise computing model. The new task model saves location and provides an efficient way to achieve integrated dynamic scheduling based on group optimization.
A new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems. This algorithm mainly includes three parts are called selecting a group of tasks and making target function as well as a new scheduling strategy based on group optimization. GOIDSH is based on heuristic searching and implements the integrated schedule in real-time heterogeneous systems with uniform form successfully. GOIDSH improves the scheduling success ratio by introducing a new task assignment policy and a Qos (Quality of Service) degradation policy for soft real-time tasks.
The kernel meaning of GOIDSH is that: Starting with an empty partial schedule, each step of the search in GOIDSH extends the current partial schedule with a group tasks selected from all pre-scheduling tasks. Each task in the group is assigned one processor before its deadline while its resource requirements can be satisfied. In GOIDSH, firstly one group tasks must be selected from all pre-scheduling tasks based on a special rule, which can ensure that a resource could not be visited by other tasks if one task in the group need to visit it. Secondly an object function matrix need to be created by synthesizing various characteristics of each task in the group which is running on each processor, then the problem is translated into the unbalanced assignment problem and solved.
In order to evaluate the performance of GOIDSH, an intensive simulation is made to analyze the impact of several task parameters on its scheduling success ratio and degradation ratio of soft real-time tasks as well as QoS(quality of service) of degraded soft real-time tasks. In the simulation, new priority sort rule, called Highest Value First, is represented to sort task queue, which is defined through follow ways:
①Earliest Deadline Highest Value
②Most Resources Highest Value
③Most Exclusive Access Highest Value
④Least Slack Highest Value
⑤The value of hard real time task is higher than that of soft real time task if there are no other different conditions in them.
The simulation results show that GOIDSH not only has successfully solved integrated dynamic scheduling of hard and soft real-time tasks in real-time heterogeneous systems, but also can offer superior scheduling success ratio and better QoS of soft real-time tasks than that of prior algorithms, such as myopic algorithm and thrift algorithm.
本文针对实时异构多任务调度的特点，采用集中式调度模型；提出软、硬实时任务形式化描述非精确计算的统一任务模型，清晰地描述实时任务的特点。系统任务描述简单，节省存储空间，为实现基于批优化的集成动态调度打下基础。
论文提出了一种新的实时异构系统的集成动态调度算法——基于分批优化的集成动态调度算法(GOIDSH算法)。该算法以启发式搜索为基础，主要包括任务分批、构造目标函数和基于批优化的调度策略三大部分，采用统一形式完成了实时异构系统的集成动态调度。同时，在构造目标函数时，算法还引入软实时任务服务质量(Ouality of Service，Qos)降级策略来提高调度成功率。
GOIDSH算法的核心思想是：在每次扩充当前局部调度时，首先按一定规则在待调度的任务集中选取一批任务组成任务子集，保证所选取的任务子集中某一任务对某个资源有访问需求时，子集中的其它任务不能对该资源有访问需求。然后，综合各种因素，对该批任务中的每项任务在每个处理器上的运行构造目标函数，将问题转化为非平衡指派问题，利用非平衡指派问题直接解法对任务进行优化分配，一次性为这些任务分配一个处理器或为每个处理器分配一项任务，使得这种分配具有最好的“合适性”，增大未被调度任务的被成功调度的可行性。
论文通过仿真和模拟，从调度成功率、软实时任务的降级比率(DR)和被降级软实时任务的服务质量(QoS)三个方面，验证了GOIDSH算法的有效性及其调度性能。在仿真实验时，提出了一种按如下顺序设定的价值最高最优先的任务队列排序原则：
①任务的截止期越近，其价值越高；
②任务需要访问的资源越多，其价值越高；
③任务要需访问的资源中，互斥方式的访问越多，其价值越高；
④任务的空闲时间越短，其价值越高；
⑤相同情形下，硬实时任务的价值高于软实时任务的价值。
仿真实验结果表明，基于分批优化的实时异构系统集成动态调度算法(GOIDSH算法)不仅成功地解决了实时异构系统中硬、软实时任务的集成动态调度问题，而且还有效地提高了调度成功率，确保了软实时任务具有良好的服务质量，与其它相关算法，如传统的近视算法和节约算法相比较，具有明显优势。
Real-time heterogeneous systems are used widely in the field of flight control and avionics, processing control, telecommunication, imagine processing and Internet applications. Many of these applications involve hard and soft real-time tasks. It is very important to study of integrated dynamic scheduling model and algorithm for real-time heterogeneous systems. This paper has made the research thoroughly on the integrated dynamic scheduling issue. In this paper, a new model for integrated dynamic scheduling of real-time heterogeneous systems is presented. Basing on the model, a new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems.
In allusion to characteristics of real-time heterogeneous multitask scheduling, a centralized scheme is assumed in this paper and an integrated task model for real-time heterogeneous systems, called uniform form task model, is proposed. This task model uniformly characterizes hard and soft real-time tasks in real-time heterogeneous systems clearly by using imprecise computing model. The new task model saves location and provides an efficient way to achieve integrated dynamic scheduling based on group optimization.
A new integrated dynamic scheduling algorithm that is based on group optimization, called GOIDSH, is developed to schedule a set of tasks in real-time heterogeneous systems. This algorithm mainly includes three parts are called selecting a group of tasks and making target function as well as a new scheduling strategy based on group optimization. GOIDSH is based on heuristic searching and implements the integrated schedule in real-time heterogeneous systems with uniform form successfully. GOIDSH improves the scheduling success ratio by introducing a new task assignment policy and a Qos (Quality of Service) degradation policy for soft real-time tasks.
The kernel meaning of GOIDSH is that: Starting with an empty partial schedule, each step of the search in GOIDSH extends the current partial schedule with a group tasks selected from all pre-scheduling tasks. Each task in the group is assigned one processor before its deadline while its resource requirements can be satisfied. In GOIDSH, firstly one group tasks must be selected from all pre-scheduling tasks based on a special rule, which can ensure that a resource could not be visited by other tasks if one task in the group need to visit it. Secondly an object function matrix need to be created by synthesizing various characteristics of each task in the group which is running on each processor, then the problem is translated into the unbalanced assignment problem and solved.
In order to evaluate the performance of GOIDSH, an intensive simulation is made to analyze the impact of several task parameters on its scheduling success ratio and degradation ratio of soft real-time tasks as well as QoS(quality of service) of degraded soft real-time tasks. In the simulation, new priority sort rule, called Highest Value First, is represented to sort task queue, which is defined through follow ways:
①Earliest Deadline Highest Value
②Most Resources Highest Value
③Most Exclusive Access Highest Value
④Least Slack Highest Value
⑤The value of hard real time task is higher than that of soft real time task if there are no other different conditions in them.
The simulation results show that GOIDSH not only has successfully solved integrated dynamic scheduling of hard and soft real-time tasks in real-time heterogeneous systems, but also can offer superior scheduling success ratio and better QoS of soft real-time tasks than that of prior algorithms, such as myopic algorithm and thrift algorithm.
引文
[1] Liu J. W. S, Real-time Systems, New Jersey: Prenticc-Hall, Inc., 2000
[2] Ramamritham, K., Dynamic Priority Scheduling, Real-time Systems, Specification, Verification and Analysis, in M. Joseph (Ed.), Prentice Hall, 1996.
[3] 郑宗汉，实时系统软件基础。北京：清华大学出版社，2003
[4] Schoeffler, J. D., Distributed Computer Systems for Industrial Process Control, ComputeR, Vol. 17, No. 2, February 1984, pp. 11--18.
[5] Ghosh, S., Melhem, R. and Mosse, D., Fault-tolerance Through Scheduling of Aperiodic Tasks in Hard Real-time Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 3, 1997, pp. 272-284.
[6] Manimaram, G. and Ram Murthy, C. S., A Fault-tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-time Systems and Its Analysis, IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 1, 1998, pp. 1137-1152.
[7] Ramamritham, K. and Stankovic, J. A., Scheduling Algorithms and Operating Systems Support for Real-time Systems, Proceedings of IEEE, Vol. 82, No. 1, 1994, pp. 55-67.
[8] Weizhao, K., Ramarnritham, K. and Stankovic, J. A., Preemptive Scheduling Under Time and Resource Constraints, IEEE Transactions on Computers, Vol. 36, No. 8, 1987, pp. 949-960.
[9] Bemat G., Bums A., Wealdy Hard Real-Time Systems, IEEE Trans. Computers, 50(4): 308-321, Apr, 2001
[10] John A. Stankovic, Real-time and Embedded Systems, ACM Computing Surveys, 28(1), Mar., 1996.
[11] John A. Stankovic et al., Strategic Directions in Real-Time and Embedded Systems, ACM Computing Surveys, 28(4), Dec., 1996.
[12] Yang C. H., and Deconinck G., A Fault-Tolerant Reservation-Based Strategy for Scheduling Aperiodic Tasks in Multiprocessor Systems, IEEE Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, GranCanaria, Spain, Jan2002. 319～326
[13] 乔颖．实时异构系统的集成动态调度算法研究[博士论文]，中国科学院软件研究所，北京，2001。
[14] Nimal Nissanke, Real-time System, prentice Hall, 1997.
[15] Shin K. G., Ramanathan R.. Real-time computing a new discipline of computer science and engineering. Proceedings of IEEE, 1994, 82(1): 6～24.
[16] C. L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment, JACM, Vol. 20, No. 1, pp. 46-61, 1973.
[17] Joseph M. & Pandya E, Finding Response Times in a Real-Time System, The Computer Journal, 1986, 29(3): 390-365.
[18] Leung J, and Whitehead J., On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation, no. 2, pp. 237-250, Dec. 182
[19] Dertouzos M. L., Control Robotics: the Procedural Control of Physical Processes, Information Processing, 1974
[20] Chetto H. and Chetto M., Some Results of the Earliest Deadline Scheduling Algorithm, IEEE Transaction on Software Engineering, 15(10), Oct. 1989
[21] 张怡，张拥军，彭宇行，陈福接，分时EDF算法及其在多媒体操作系统中的应用，计算机学报，2001，24(3)，315-320
[22] F. Glover, E. Taillard and D. Dewarra, A Users's Guide to Tabu Search, Annals of OR, 7(x): pp. 3-28, 1993.
[23] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, 220(4589): 671-680, 1983.
[24] G. Duck and T. Scheuer, Threshold Accepting: A General Purpose Optimization Algorithm Appearing Supior to Simulated Annealing, Journal of Computional Physics, pp. 161-175, 1990.
[25] D.E.Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Weley pub. Company Inc., 1989.
[26] C.Cardeira, Neural Network Versus Max-Flow Algorithms for ltiprocessor Real-time Scheduling, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 175-180,1996.
[27] K.Tindell, A.burns and A. wellings, Allocating Real-time Tasks (An NP-Hard Problem made Easy), Journal of Real-time Systems, 4(2): pp. 145-165,1992.
[28] M.Nicholson, Allocating and Scheduling Hard Real-time Tasks on s Point-to-point Distributed System, Proceedings of Workshop on Parallel and Distributed Real-time Systems, 1993.
[29] M. Coli and P.Palazza ri, A new Mehtod for Optimization of Allocation and Scheduling in Real-time Applications, Proceedings of the 7th Euromicro Workshop on Real-time Systems, PP.262-269, 1995.
[30] M.Dinatale and J.A.Stankovic, Applicability of Simulated Annealing Methods to Real-time Scheduling and Jitter Control, Proceedings of the IEEE Real-time Systems Symposium, 1995.
[31] Marco Di Natale and John A. Stankovic, Scheduling Distributed eal-time Tasks with Minimum Jitter, Ieeee Transactions on Computers, 49(4), April 2000.
[32] Gaetano Borriello, Daniel M, Miles, Task Scheduling for Real-time Multiprocessor Simulations, 11th Real-time Workshop on Operating System and Software, 1994.
[33] K. Ramamritham, Allocation and Scheduling of Complex Periodic Tasks, Proceedings of the 10th International conference on Distributed Computing Systems, pp.108-115, 1990.
[34] J.M.Adan, M.F.Magalhaes and K.Ramamritham, Meeting Hard Real-time Constraints Using a client-server Model of Interaction, Proceedings of the 7 Euromicro Workshop on Real-time systems, pp.286-293,1995.
[35] J.Jonsson, A.Olsson and J.Vasell, Predicting Real-time Behavior for Data-Flow Computations, Proceeding of the 7th Euromicro work-shop on Real-time systems, pp. 270-275, 1995.
[36] 邱卫东，陈燕，李洁萍，彭澄廉，一种实时异构嵌入式系统的任务调度算法，软件学报，2004，15(4)：504～511．
[37] Peter Altenbernd, The Slack Method: A new Method for Static Allocation of Hard Real-time Tasks, Real-time Systems, vol. 15, pp. 103-150, 1998.
[38] J. Xu and D. L. Parnas, Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations, IEEE Transactions on Software Engineering, 16(3): 360-369, March. 1990.
[39] A. K. Mok, and M. L. Dertouzos, Multiprocessor Scheduling in a Hard Real-time Environment, Proc. Seventh Texas Conf. Comput. Syst., Nov. 1978.
[40] A. K. Mok, The Design of Real-time Programming Systems based on Process Models, Proc. IEEE Real-time Syst. Symp., Dec. 1984.
[41] Stankovic J., Spuri M., Di Natale, M., and Butcal. Scheduling Results for Real-time Systems, IEEE Computer, 28(6), pp. 16-25.
[42] Dertouzos, M. and Mok, A. K. (1989), Multiprocessor On-line Scheduling of Hard Real-time Tasks, IEEEE Trans. On Software Engineering, 15912, pp. 1497-1506.
[43] M. Dominic and Bijendra N. Jain, Conditions for On-line Scheduling of Hard Real-time Tasks on Multiprocessors, Journal of Parallel and Distributed Computing, 55, pp 121-137, 1998.
[44] S. K. Baruah, N. Cohen, C. Plaxton, and D. Varvel, Proportionate Progress: A Notion of Fairness in Resource Allocation, Algorithmica, 15: pp. 600-625, 1996
[45] Almut Burchard, Yingfeng Oh, Jorg Liebeherr, Sang H. Son, A Linear-time Online Task Assignment Scheme for Multiprocessor Systems, 11th Real-time Workshop on Operating System and Software, 1994.
[46] Coffman, E. G., Computer and Job-Shop Scheduling Theory, Wiley, New York, 1976.
[47] Davari, S., and S. K. Dhall, An On Line Algorithm for Real-time Tasks Allocation Proc. Ieee Real-time Systems Symp, pp. 194-200. IEEE, Los Alamitos. CA, 1986.
[48] K. Ramamaritham, J. A. Stankovic, Distributed Scheduling of Tasks with Deadlines and Resource Requirements, IEEE Trans. On Computers, 38(8): pp. 1110-1122, 1989.
[49] K. Pamamritham, J. Stankovic, and W. Zhao, Dynamic Task Scheduling in Distributed Hard Real-time Systems, IEEE Software, vol. 1, may 1984.
[50] J. A. Stankovic, K. Ramamritham, and S. Cheng, Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-time Systems, IEEE Trans. Computers, Dec. 1985.
[51] K. G. Shin, and Y. -C. Chang, Load Sharing in Distributed Real-time Systems with State-Change Broadcasts, IEEE Trans. Computers 38: pp. 1124-1142, 1989.
[52] Azer Besttavros and Dimitrios Spartiotis, Probabilistic Job Scheduling for Distributed Real-time Applications, Proceedings of the First IEEE Workshop on Real-timeApplications, New York, NY, May 1993.
[53] Azer Bestavros, Load Profiling a Mehodology for Scheduling Real-time Tasks in a Distributed Systems, proceedings of ICDCS'97, the IEEE International Conference on Distributed Computing Systems, Baltimore, Maryland, May 1997.
[54] Ramamritham, K. J., Stankovic, A., Shiah, P. -F. Efficient scheduling algorithms for real-time multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(2): 184～194.
[55] 乔颖，王宏安，戴国忠。一种新的实时多处理器系统的动态调度算法，软件学报，2002，13(1)：51～58。
[56] 王堃，乔颖，王宏安，方亭，邹冰，戴国忠。实时异构系统的动态调度算法研究，计算机研究与发展，2002，39(6)：725～732。
[57] 乔颖，邹冰，方亭，王宏安，戴国忠。一种实时异构系统的集成动态调度算法研究，软件学报，2002，13(12)：2251～2258。
[58] Zhu Xiangbin; Tu Shiliang: An improved dynamic scheduling algorithm for multiprocessor real-time systems. Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on, 27-29 Aug. 2003. PP: 710-714
[59] Mittal, A., Manimaran, G., Murthy, C. S. R. Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems. In: mork, A. K., Tokuda, H., eds. Proceedings of the 5th International conference on Real-Time Computing Systems and Applications. Los Alamitos, CA: IEEE Press, 1998, 162～172.
[60] Basheer Duwairi, G. Manimaran: Combined Scheduling of Hard and Soft Real-Time Tasks in Multiprocessor Systems. HiPC 2003: 279-289
[61] Manimaran, G., Murthy, C. S. R. An efficient dynamic scheduling algorithm for multiprocessor real-time systems. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(3): 312～319.
[62] 宾雪莲，杨玉海，金士尧，一种基于分组与适当选取策略的实时多处理器系统的动态调度算法，计算机学报，2006，29(1)：81～91．
[63] G. Manimaran, C. S. R. Murthy and K. Ramamritham, A new Approach for Scheduling of Parallelizable Tasks in Real-time Multiprocessor Systems, Real-time Systems, 15, pp. 39-60, 1998.
[64] Gruian F. System-level design methods for low-energy architectures containing variable voltage processors[C]. In: Proc. Work-shop Power-Aware Computing Systems, 2000.
[65] Shriver P M, Gokhale M B, et al. A power-aware, satellitebased parallel signal processing scheme, Chapter 13, power aware computing[M], In: Plenum/Kluwer Publishers, 2002, 243～259.
[66] Dakai Zhu, Rami Melhem, Bruce R Childers. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems[J]. IEEE transaction on parallel and distributed Systems, July, 2003, 14(7): 686～699.
[67] 韩建军，李庆华，缪天鹏，Abbas．Essa．实时多处理器系统中基于能量节约的动态调度算法小型微型计算机系统．2006，27(4)，691～694．
[68] 阳春华，桂卫华，计莉，基于多处理机的混合实时任务容错调度，计算机学报，2003，26(11)，1479～1486。
[69] Liestman A. L. and Cambell R. H., A Fault-Tolerant Scheduling Problem, IEEE Trans. Soflware Engineering, 12(11): 1089-1095, Nov. 1988
[70] Al-Omari R., Manimaran G., and Somani A. K., An Efficient Backup-Overloading for Fault-Tolerant Parallel and Distributed Systems, pp. 1291-1295, 2000
[71] 张坤龙，秦啸，韩宗芬，庞丽萍，异构分布式实时系统中容错调度模型的研究，华中理工大学学报，2000，28(8)：17-18．
[72] Dima C., Girault A., Lavarenne C., and Sorel Y., Off-Line Real-Time Fault-Tolerant Scheduling, In proceedings of the IEEE EuroMicro Workshops on Parallel and Distributed Processing, Mantova, Italy, Feb. 2001
[73] 秦啸，韩宗芬，庞丽萍，基于异构分布式系统的实时容错调度算法，计算机学报，25(1)：49-56，Jan．2002
[74] R. Al_Omari, Arun K. Somani, G. Manimaran: A New Fault-Tolerant Technique for Improving the Schedulability in Multiprocessor Real-time Systems. IPDPS 2001: 32
[75] R. Al_Omari, Arun K. Somani, G. Manimaran: An Adaptive Scheme for Fault-Tolerant Scheduling of Soft Real-Time Tasks in Multiprocessor Systems. HiPC 2001: 68-80
[76] 郭辉，王智广，周敬利：异构分布式系统中基于负载均衡的容错调度算法．计算机学报，2005，28(11)：1807—1816．
[77] 秦啸，庞丽萍，韩宗芬，李胜利：分布式实时系统的容错调度算法．计算机学报，2000，23(10)：1056—1063．
[78] Yang C. H., and Deconinck G., Design of a Power Quality Assessment System and the Role of Information Redundancy, The 6th Interational Conference: Engineering of Modern Electric'01 Systems, Oradea, Romania, May 2001
[79] Yang C. H., and Deconinck G., A Fault-tolerant reservation-based strategy for scheduling speriodic tasks in multiprocessor systems, IEEE Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Gran Canaria, Spain, Jan 2002. 319～326
[80] Yang C. H., and Deconinck G., Fault-Tolerant Scheduling of Periodic and Aperiodic Tasks in Multiprocessor Systems, IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 535-542, California, USA, Aug. 2001
[81] 阳春华，沈德耀，桂卫华，实时多处理机系统BEST—FIT启发式容错调度，计算机工程与科学，2003，25(5)，P．61-64，85
[82] Terrier F, Chen Z. Fuzzy calculus applied to real time scheduling. In: Yen J, ed. Proc. of the 3rd IEEE Conf. On Fuzzy Systems, Vol 3. Piscataway: IEEE Computer Society. 1994. 1905～1910.
[83] Litoiu M, Tadei R. Real-Time task scheduling with fuzzy deadlines and processing times. Fuzzy Set and Systems, 2001, 117(1): 35～45.
[84] 金宏，王宏安，傅勇，王强，王晖．模糊反馈控制实时调度算法，2004，15(6)，791～798
[85] 金宏，王宏安，王强，傅勇，王晖：模糊动态抢占调度算法．计算机学报，2004，27(6)：812-818．
[86] 金宏，王宏安，唐雪梅，王晖：计算机控制中的模糊调度设计．计算机学报，2006，29(3)，414-422．
[87] Yao F, Demers A, Shenker S. Ascheduling model foe reduced CPU energy[C].In: Proc. 36th Symp. Foundations of Computer Science, 1995, 374～382.
[88] Krishna C M K, Lee Y H. Voltage clock scaling adaptive scheduling techniques or low power in hard real-time systems[C]. In: Proc. 6th IEEE Real-Time Technology and Applications Symp, 2000.
[89] Mosse D, Aydin H, Childers B, et al. Compiler-assisted dynamic power-aware scheduling for real-time applications[C]. In: proc. Workshop Compiler and OS for Low Power, 2000.
[90] D. W. Waston et al. A framework for compile-time selection of parallel modes in an SIMD/SPMD heterogeneous environment, Proc. WHP'93, Newport Beach, CA, Apr. 1993, pp 57-64.
[91] I. Ekrnecic, T.Tartalja, and V.Milutinovic, EM~3: A contribution to taxonomy of heterogeneous computing systems, IEEE computer, vol. 28, pp68-70, Dec. 1995.
[92] J. W. S. Lieu, W. K. Shin, K. J. Liu, R. Bettati and J. Y. Chung, Impercise Computations, Proc. IEEE, 1994, 82(1), 83-94.
[93] 张尧学，方存好，王勇．非精确计算中基于反馈的CPU在线调度算法．软件学报，2004，17(4)：616～623．
[94] 李建国，陈松乔，鲁志辉。实时多处理器系统的动态分批优化调度算法．小型微型计算机系统．2005，26(1)，84～89．
[95] 李建国，陈松乔，鲁志辉．实时异构系统的动态分批优化调度算法．计算机学报．2006，29(6)，976～984．
[96] 李建国，陈松乔，王建新，鲁志辉：基于分批优化的实时多处理器系统的集成动态调度算法．小型微型计算机系统．2006，27(9)：1641～1647．
[97] 吉勒特BE(美)著；蔡宣三，陈伟基，王永县译。运筹学导论——计算机算法。北京，机械工业出版社，1985，180
[98] 田庆辉，李建国，非平衡分配问题，湘潭大学自然科学学报，1992，第14卷，第2期：78～82．
[99] 刘仁舟，湘潭师范学院学报(自然科学版)，1988；4；15～19
[100] Mok, A. K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment [Ph. D. Thesis]. Cambridge, MA: Department of Electronic Engineering and Computer Sciences, MIT, 1983.
[101] Garey MR, Johnson Ds. Computers and Intractability - A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Co., 1979.
[102] 刘云生，何新贵，唐常杰，李霖。特种数据库技术。北京：科学出版社，2000。
[103] Jensen ED, Locke CD, Toduda H. A Time-driven scheduling model for real-time operating systems. In: Proceedings of the IEEE Real-time Systems Symposium. Washington, DC: IEEE Computer society Press, 1985, 112～122.
[104] Hou, E. S., Ansari, N. and Ren, H., Genetic Algorithm for Multiprocessing Scheduling, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 2,1994, pp. 113-120.
[105] J. A. Stankovic, M. Spuri, K. Rarnamritham, and G. C. Buttazzo, deadline Scheduling for Real-time, Systems — EDF and Related algorithms, Kluwer Academic Publishers, 1998.
[106] G. Buttazzo and J. A. Stankovic, Adding Robustness in Dynamic Preemptive Scheduling, Responsive Computer Systems: steps Toward Fault-tolerant Real-Time System, Kluwer Academic Publishers, 1995.
[107] C. Lu, J. A. Stankovic, T.F.Abdelzaher, G. Tao, S.H. Son and M. Marley, Performance Specifications and Metrics for Adaptive Real-Time Systems, IEEE Real-Time Systems Symposium, Orlando, FL, Dec 2000.
[108] C. Y. Lu, H.A.Stankovic, Gang Tao and Sang H, Son Design and Evaluation of a Feedback Control EDF Scheduling, 20th IEEE Real-Time Systems Symposium, 1-3 December, 1999, Phoenix, Arizona.
[109] J.Baccouche, Multiprocessor Task Scheduling with Resource Requirements, Journal of Real-time Systems, 6(1), January 1994.
[110] G. Duck and T.Scheuer, Threshold Accepting: A General Purpose Optimization Algorithm Appearing Supior to Simulated Annealing, Journal of Computional Physics, pp.161-175, 1990.
[111] C.Cardeira, Neural Network Versus Max-Flow Algorithms for Multiprocessor Real-time Sacheduling, Preoceedings o9f the 8th Euromicro Workshop on Real-time Systems, pp. 175-180, 1996.
[112] Luca Abeni and Giorgio Buttazzo, Adaptive Bandwidth Reservation for Multimedia Computing, Sixth International Conference on Real-time Computing Systems and Applications, 13-15 December, 1999,Hong Kong,China.
[113] C.M.Krishna and K.GShin, Real-time Systems, pp.15, The McGraw-Hill Companies, Inc, 1997.
[114] Ekmecic, Tartalja, Milutinovic, A Survery of Heterogeneous Computing: Cnocepts and Systems, Proceedings of the IEEE, 1996, VOL. 84, No.8, pp.1124-1126.
[115] S.S.Skiena and Skiena, The Alogrithm design Manual, Telos/Sprnger-Verlag, New York, November 1997.
[116] Jane W.S.Liu, Real-time Systems, Prentice Hall, 2000.
[117] J.A. Stankovic, Marco Spuri, Macro Di Natale, and Giorgio, Buttazzo, Implicatoins of Classical scheduling Results For Real-time Systems, IEEE computer, vol. 28, No.6, pp.16-25, June 1995.
[118] J.K.Dey, J.F.Kurose, D.F.Towsley, C.M.Krishna and M.Girkar, Efficient On-line Processor Scheduling for a Calss of IRIS Real-time Tasks, SIGMETERICS 1993,pp.217-228, ACM, New York, 1993.
[119] Gerhard Fohler, Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems, IEEE Real-time symposium, 1994.
[120] Chi ashen, Krithi Ramamritham, J. A. Stankovic, Resource Reclaiming in Multiprocessor Real-time Systems, IEEE Transaction on Parallel and Distributed System. Vol.4, No.4, April 1993.
[121] Hermann Kopetz, Real-time Systems: Design Principles for Distributed Enbedded Applications, pp.12-16, Kluwer Academic Publishers, 1997.
[122] Hiroyuki Kaneko, John A. Stankovic, Intergrated Scheduling of Multimedia and Hard Real-time Tasks, IEEE Real-time Symposium, 1995.
[123] John P. Lehoczky, S. Ramos-Thuel, An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed Priority Preemptive Systems, IEEE Real-time System Symposium, 1992.
[124] J. A. Stankovic, C. Y. Lu, Sang H, Son and Gang Tao, The Case for Feedback Control Real-time Scheduling, EuroMicro Conference on Real-Time Systems, June 1999.
[125] K.Tindell, A.bums and A. wellings, Allocating Real-time Tasks (An NP-Hard Problem made Easy), Journal of Real-time Systems, 1992,4(2): pp.145-165.
[126] C.J.Hou and K.G.Shin, Allocation of Periodic Task Modules with Precedence and Deadline Constraints in Distributed Real-time Systems, Proceedings of 13th Real-time Systems Symposium, 1992.
[127] R.A1-Omari, Arun K.Somani, G. Manimaran: Efficient overloading techniques for primary-backup scheduling in real-time systems.J.Parallel Distrib. Comput.64(5): 629-648 (2004)
[128] R.Al_Omari, G. Manimaran, M.V.Salapaka, Arun K.Somani:Novel Algorithms for Open-Loop and Closed-Loop Scheduling of Real-Time Tasks in Multiprocessor Systems Based on Execution Time Estimation.IPDPS 2003:7
[129] GGreenwood, C.Lang and S.Hurley, An, Evolutionary Strategy for Scheduling Periodic Tasks in Real-time Systems, Applied Decision Technologies, pp.171-188,1995.
[130] F.E.Sandnes, A Hybrid Genetic Algorithm Applied to Automatic Parallel Controller Code Generation, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp.70-75, 1996.
[131] Indranil Gupta, G. Manimaran, C.Siva Ram Murthy: A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems. J.Parallel Distrib. Comput.2000, 60(1): 113-133.
[132] G. Manimaran, C.Siva Ram MURTHY, Machiraju Vijay, Krithi Ramamritham: New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems.J.Parallel Distrib.COMPUT. 1997,44(2): 123-132.
[133] Douglas Antony Louis Piriiyakumar, C. Siva Ram Murthy: Optimal Compile-Time Multiprocessor Scheduling Based on the 0-1 Linear Programming Algorithm with the Branch and Bound Technique. J.Parallel Distrib.Comput. 1996,35 (2): 199-204 .
[134] K.Mahesh, G. Manimaran, and C.S.R. Murthy, Scheduling Algorithms with Fault Detection and Location Capabilities for Real-time Multiprocessor Systems, Journal of Parallel and Distributed Computing 51(2), 136-150, 1998.
[135] L. Baccouche, Efficient Static Allocation of Real-time Tasks Using Genetic Algorithms, Internal Reprot, Image Institute, Laboratoire de genie informatique, 1995.
[136] S. Ronngren and B. A. Shirazik Static Multiprocessor Scheduling of Periodic Real-time Tasks with precedence constraints and communication costs, Proceedings of the 28th Annual Hawaii International Conference on System Sciences, pp. 145-152, 1995.
[137] 邹勇，淮晓永，李明树：开放式实时系统中的自适应调度方法．计算机学报，2004，27(1)：58-65．
[138] J. S. Antos, J. Oroico and R. Cayssials, A Heuristic Approach to the Multitask- Multipocessor Assignment Problem Using the Empty-slots Method and Rate Monotonic Scheduling, Real-time Systems, 13, pp. 167-199. 1997.
[139] S. Saez, J. Vila and A. Crespo, A Dynamic Real-time Scheduler for Shared Memorty Multiprocessors, Proc, 8th Euromicro Workshop on Real-time Systems, pp. 158-163, L, Aquila, Italy, June 12-14, 1996.
[140] 王永吉，陈秋萍：单调速率及其扩展算法的可调度性判定．软件学报．2004，15(6)：799-814．
[141] 刘军祥，王永吉，Matthew Cartmell：一种改进的RM可调度性判定算法．软件学报．2005，16(1)：89-100．
[142] S. Saez, J. Vila and A. Crespo, Dynamic Scheduling Sohations for Real-time Multiprocessor Systems, IFAC Real-time Programming, Gramado, RS, Brazil, 1997.
[143] Gilad Koren, Dennis Shasha and Shih-Chen Huang, MOCA: a Multiprocessor On-line Competitive Algorithm for Real-time System Scheduling, IEEE Real-time Systems Symposium, 1993.
[144] G.Manimaran, C. S. R. Murthy, M. Vijay, and K. Ramamritham, New Algorithms for Resource Reclaiming from Precedence Constrained Tashk in Multiprocessor Real-time Systems, Journal of Parallel and Distributed Computing 44, no. 2, pp. 123-132, 1997.
[145] J. Orozco, R. Cayssials, J. Santos, and E. Ferro, Design of a Learning Fuzzy Production System to Solve and NP-Hard Real-time Assignment Problem, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 146-150, 1996.
[146] E. Ferro, J. Sautos, J. Drozco, and R. Cayssials, Tuning Parameters to Improve a Heuristic Mehtod: More and better Solutions to an NP-Hard Real-time Problem, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 47-51, 1996.
[147] S. Lee, S. K. Oh and C. H. Woo, Dual-token-based Fault-tolerant Scheduling for Hard Real-time Multiprocessor Systems, 5th International Conference on Real-time Computin Systems and Applications, 1998.
[148] Sylvain Lauzac, R. Melhem and Daniel Mosse, Adding Fault-tolerance to p-Fair Real-time Scheduling, International Workshop on Embedded Fault-Tolerant systems, pp. 34-37, 1998.
[149] Songqiao Chen, Jingui Huang, Jianer Chen. Approximation algorithm for parallel job scheduling 中南大学学报(英文版) 2002, 9(4), 267-272.
[150] 黄金贵，陈建二，陈松乔：网络集群计算系统中的并行任务调度．计算机学报．2004，27(6)：765-771．
[151] Jingui Huang, Jianer Chen, Songqiao Chen. A simple and improved approximation algorithm for scheduling multiprocessor-jobs on 3-processor systems, 16th World Computer conference (WCC'2000, Beijing), Software theory and practical, (2000), pp800-806.
[152] Jingui Huang, Jianer Chen, Songqiao Chen. A simple linear time approximation algorithm for multiprocessor job on four processors, Lecture Notes in Computer science(ISAA'00, Taibei), 2000, pp. 60-71, Springer.
[153] Jianer Chen, Jingui Huang. Semi-Normal schedulings: Improvement on Goemans, 12th Annual International Sysposium on Algorithm and Computation(ISAAC'01) Lecture Notes in Computer science(2001, Newzeland), pp. 60-71, Springer.
[154] 黄金贵，陈建二，陈松乔：并行环境下基于多处理机任务的调度模型和算法．计算机科学．2002，29(4)：1-3．
[155] 陈松乔，黄金贵，陈建二：网络并行环境下多处理机任务的调度．小型微型计算机系统．2003，24(7)，1144-1147．
[156] 黄金贵，陈建二，陈松乔：网络计算系统中基于多处理机任务的调度模型．计算机工程与应用．2003，39(29)，54-58，83．
[2] Ramamritham, K., Dynamic Priority Scheduling, Real-time Systems, Specification, Verification and Analysis, in M. Joseph (Ed.), Prentice Hall, 1996.
[3] 郑宗汉，实时系统软件基础。北京：清华大学出版社，2003
[4] Schoeffler, J. D., Distributed Computer Systems for Industrial Process Control, ComputeR, Vol. 17, No. 2, February 1984, pp. 11--18.
[5] Ghosh, S., Melhem, R. and Mosse, D., Fault-tolerance Through Scheduling of Aperiodic Tasks in Hard Real-time Multiprocessor Systems, IEEE Transactions on Parallel and Distributed Systems, Vol. 8, No. 3, 1997, pp. 272-284.
[6] Manimaram, G. and Ram Murthy, C. S., A Fault-tolerant Dynamic Scheduling Algorithm for Multiprocessor Real-time Systems and Its Analysis, IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 1, 1998, pp. 1137-1152.
[7] Ramamritham, K. and Stankovic, J. A., Scheduling Algorithms and Operating Systems Support for Real-time Systems, Proceedings of IEEE, Vol. 82, No. 1, 1994, pp. 55-67.
[8] Weizhao, K., Ramarnritham, K. and Stankovic, J. A., Preemptive Scheduling Under Time and Resource Constraints, IEEE Transactions on Computers, Vol. 36, No. 8, 1987, pp. 949-960.
[9] Bemat G., Bums A., Wealdy Hard Real-Time Systems, IEEE Trans. Computers, 50(4): 308-321, Apr, 2001
[10] John A. Stankovic, Real-time and Embedded Systems, ACM Computing Surveys, 28(1), Mar., 1996.
[11] John A. Stankovic et al., Strategic Directions in Real-Time and Embedded Systems, ACM Computing Surveys, 28(4), Dec., 1996.
[12] Yang C. H., and Deconinck G., A Fault-Tolerant Reservation-Based Strategy for Scheduling Aperiodic Tasks in Multiprocessor Systems, IEEE Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, GranCanaria, Spain, Jan2002. 319～326
[13] 乔颖．实时异构系统的集成动态调度算法研究[博士论文]，中国科学院软件研究所，北京，2001。
[14] Nimal Nissanke, Real-time System, prentice Hall, 1997.
[15] Shin K. G., Ramanathan R.. Real-time computing a new discipline of computer science and engineering. Proceedings of IEEE, 1994, 82(1): 6～24.
[16] C. L. Liu and J. W. Layland, Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment, JACM, Vol. 20, No. 1, pp. 46-61, 1973.
[17] Joseph M. & Pandya E, Finding Response Times in a Real-Time System, The Computer Journal, 1986, 29(3): 390-365.
[18] Leung J, and Whitehead J., On the complexity of fixed-priority scheduling of periodic real-time tasks, Performance Evaluation, no. 2, pp. 237-250, Dec. 182
[19] Dertouzos M. L., Control Robotics: the Procedural Control of Physical Processes, Information Processing, 1974
[20] Chetto H. and Chetto M., Some Results of the Earliest Deadline Scheduling Algorithm, IEEE Transaction on Software Engineering, 15(10), Oct. 1989
[21] 张怡，张拥军，彭宇行，陈福接，分时EDF算法及其在多媒体操作系统中的应用，计算机学报，2001，24(3)，315-320
[22] F. Glover, E. Taillard and D. Dewarra, A Users's Guide to Tabu Search, Annals of OR, 7(x): pp. 3-28, 1993.
[23] S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, 220(4589): 671-680, 1983.
[24] G. Duck and T. Scheuer, Threshold Accepting: A General Purpose Optimization Algorithm Appearing Supior to Simulated Annealing, Journal of Computional Physics, pp. 161-175, 1990.
[25] D.E.Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Weley pub. Company Inc., 1989.
[26] C.Cardeira, Neural Network Versus Max-Flow Algorithms for ltiprocessor Real-time Scheduling, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 175-180,1996.
[27] K.Tindell, A.burns and A. wellings, Allocating Real-time Tasks (An NP-Hard Problem made Easy), Journal of Real-time Systems, 4(2): pp. 145-165,1992.
[28] M.Nicholson, Allocating and Scheduling Hard Real-time Tasks on s Point-to-point Distributed System, Proceedings of Workshop on Parallel and Distributed Real-time Systems, 1993.
[29] M. Coli and P.Palazza ri, A new Mehtod for Optimization of Allocation and Scheduling in Real-time Applications, Proceedings of the 7th Euromicro Workshop on Real-time Systems, PP.262-269, 1995.
[30] M.Dinatale and J.A.Stankovic, Applicability of Simulated Annealing Methods to Real-time Scheduling and Jitter Control, Proceedings of the IEEE Real-time Systems Symposium, 1995.
[31] Marco Di Natale and John A. Stankovic, Scheduling Distributed eal-time Tasks with Minimum Jitter, Ieeee Transactions on Computers, 49(4), April 2000.
[32] Gaetano Borriello, Daniel M, Miles, Task Scheduling for Real-time Multiprocessor Simulations, 11th Real-time Workshop on Operating System and Software, 1994.
[33] K. Ramamritham, Allocation and Scheduling of Complex Periodic Tasks, Proceedings of the 10th International conference on Distributed Computing Systems, pp.108-115, 1990.
[34] J.M.Adan, M.F.Magalhaes and K.Ramamritham, Meeting Hard Real-time Constraints Using a client-server Model of Interaction, Proceedings of the 7 Euromicro Workshop on Real-time systems, pp.286-293,1995.
[35] J.Jonsson, A.Olsson and J.Vasell, Predicting Real-time Behavior for Data-Flow Computations, Proceeding of the 7th Euromicro work-shop on Real-time systems, pp. 270-275, 1995.
[36] 邱卫东，陈燕，李洁萍，彭澄廉，一种实时异构嵌入式系统的任务调度算法，软件学报，2004，15(4)：504～511．
[37] Peter Altenbernd, The Slack Method: A new Method for Static Allocation of Hard Real-time Tasks, Real-time Systems, vol. 15, pp. 103-150, 1998.
[38] J. Xu and D. L. Parnas, Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations, IEEE Transactions on Software Engineering, 16(3): 360-369, March. 1990.
[39] A. K. Mok, and M. L. Dertouzos, Multiprocessor Scheduling in a Hard Real-time Environment, Proc. Seventh Texas Conf. Comput. Syst., Nov. 1978.
[40] A. K. Mok, The Design of Real-time Programming Systems based on Process Models, Proc. IEEE Real-time Syst. Symp., Dec. 1984.
[41] Stankovic J., Spuri M., Di Natale, M., and Butcal. Scheduling Results for Real-time Systems, IEEE Computer, 28(6), pp. 16-25.
[42] Dertouzos, M. and Mok, A. K. (1989), Multiprocessor On-line Scheduling of Hard Real-time Tasks, IEEEE Trans. On Software Engineering, 15912, pp. 1497-1506.
[43] M. Dominic and Bijendra N. Jain, Conditions for On-line Scheduling of Hard Real-time Tasks on Multiprocessors, Journal of Parallel and Distributed Computing, 55, pp 121-137, 1998.
[44] S. K. Baruah, N. Cohen, C. Plaxton, and D. Varvel, Proportionate Progress: A Notion of Fairness in Resource Allocation, Algorithmica, 15: pp. 600-625, 1996
[45] Almut Burchard, Yingfeng Oh, Jorg Liebeherr, Sang H. Son, A Linear-time Online Task Assignment Scheme for Multiprocessor Systems, 11th Real-time Workshop on Operating System and Software, 1994.
[46] Coffman, E. G., Computer and Job-Shop Scheduling Theory, Wiley, New York, 1976.
[47] Davari, S., and S. K. Dhall, An On Line Algorithm for Real-time Tasks Allocation Proc. Ieee Real-time Systems Symp, pp. 194-200. IEEE, Los Alamitos. CA, 1986.
[48] K. Ramamaritham, J. A. Stankovic, Distributed Scheduling of Tasks with Deadlines and Resource Requirements, IEEE Trans. On Computers, 38(8): pp. 1110-1122, 1989.
[49] K. Pamamritham, J. Stankovic, and W. Zhao, Dynamic Task Scheduling in Distributed Hard Real-time Systems, IEEE Software, vol. 1, may 1984.
[50] J. A. Stankovic, K. Ramamritham, and S. Cheng, Evaluation of a Flexible Task Scheduling Algorithm for Distributed Hard Real-time Systems, IEEE Trans. Computers, Dec. 1985.
[51] K. G. Shin, and Y. -C. Chang, Load Sharing in Distributed Real-time Systems with State-Change Broadcasts, IEEE Trans. Computers 38: pp. 1124-1142, 1989.
[52] Azer Besttavros and Dimitrios Spartiotis, Probabilistic Job Scheduling for Distributed Real-time Applications, Proceedings of the First IEEE Workshop on Real-timeApplications, New York, NY, May 1993.
[53] Azer Bestavros, Load Profiling a Mehodology for Scheduling Real-time Tasks in a Distributed Systems, proceedings of ICDCS'97, the IEEE International Conference on Distributed Computing Systems, Baltimore, Maryland, May 1997.
[54] Ramamritham, K. J., Stankovic, A., Shiah, P. -F. Efficient scheduling algorithms for real-time multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems, 1990, 1(2): 184～194.
[55] 乔颖，王宏安，戴国忠。一种新的实时多处理器系统的动态调度算法，软件学报，2002，13(1)：51～58。
[56] 王堃，乔颖，王宏安，方亭，邹冰，戴国忠。实时异构系统的动态调度算法研究，计算机研究与发展，2002，39(6)：725～732。
[57] 乔颖，邹冰，方亭，王宏安，戴国忠。一种实时异构系统的集成动态调度算法研究，软件学报，2002，13(12)：2251～2258。
[58] Zhu Xiangbin; Tu Shiliang: An improved dynamic scheduling algorithm for multiprocessor real-time systems. Parallel and Distributed Computing, Applications and Technologies, 2003. PDCAT'2003. Proceedings of the Fourth International Conference on, 27-29 Aug. 2003. PP: 710-714
[59] Mittal, A., Manimaran, G., Murthy, C. S. R. Integrated dynamic scheduling of hard and QoS degradable real-time tasks in multiprocessor systems. In: mork, A. K., Tokuda, H., eds. Proceedings of the 5th International conference on Real-Time Computing Systems and Applications. Los Alamitos, CA: IEEE Press, 1998, 162～172.
[60] Basheer Duwairi, G. Manimaran: Combined Scheduling of Hard and Soft Real-Time Tasks in Multiprocessor Systems. HiPC 2003: 279-289
[61] Manimaran, G., Murthy, C. S. R. An efficient dynamic scheduling algorithm for multiprocessor real-time systems. IEEE Transactions on Parallel and Distributed Systems, 1998, 9(3): 312～319.
[62] 宾雪莲，杨玉海，金士尧，一种基于分组与适当选取策略的实时多处理器系统的动态调度算法，计算机学报，2006，29(1)：81～91．
[63] G. Manimaran, C. S. R. Murthy and K. Ramamritham, A new Approach for Scheduling of Parallelizable Tasks in Real-time Multiprocessor Systems, Real-time Systems, 15, pp. 39-60, 1998.
[64] Gruian F. System-level design methods for low-energy architectures containing variable voltage processors[C]. In: Proc. Work-shop Power-Aware Computing Systems, 2000.
[65] Shriver P M, Gokhale M B, et al. A power-aware, satellitebased parallel signal processing scheme, Chapter 13, power aware computing[M], In: Plenum/Kluwer Publishers, 2002, 243～259.
[66] Dakai Zhu, Rami Melhem, Bruce R Childers. Scheduling with dynamic voltage/speed adjustment using slack reclamation in multiprocessor real-time systems[J]. IEEE transaction on parallel and distributed Systems, July, 2003, 14(7): 686～699.
[67] 韩建军，李庆华，缪天鹏，Abbas．Essa．实时多处理器系统中基于能量节约的动态调度算法小型微型计算机系统．2006，27(4)，691～694．
[68] 阳春华，桂卫华，计莉，基于多处理机的混合实时任务容错调度，计算机学报，2003，26(11)，1479～1486。
[69] Liestman A. L. and Cambell R. H., A Fault-Tolerant Scheduling Problem, IEEE Trans. Soflware Engineering, 12(11): 1089-1095, Nov. 1988
[70] Al-Omari R., Manimaran G., and Somani A. K., An Efficient Backup-Overloading for Fault-Tolerant Parallel and Distributed Systems, pp. 1291-1295, 2000
[71] 张坤龙，秦啸，韩宗芬，庞丽萍，异构分布式实时系统中容错调度模型的研究，华中理工大学学报，2000，28(8)：17-18．
[72] Dima C., Girault A., Lavarenne C., and Sorel Y., Off-Line Real-Time Fault-Tolerant Scheduling, In proceedings of the IEEE EuroMicro Workshops on Parallel and Distributed Processing, Mantova, Italy, Feb. 2001
[73] 秦啸，韩宗芬，庞丽萍，基于异构分布式系统的实时容错调度算法，计算机学报，25(1)：49-56，Jan．2002
[74] R. Al_Omari, Arun K. Somani, G. Manimaran: A New Fault-Tolerant Technique for Improving the Schedulability in Multiprocessor Real-time Systems. IPDPS 2001: 32
[75] R. Al_Omari, Arun K. Somani, G. Manimaran: An Adaptive Scheme for Fault-Tolerant Scheduling of Soft Real-Time Tasks in Multiprocessor Systems. HiPC 2001: 68-80
[76] 郭辉，王智广，周敬利：异构分布式系统中基于负载均衡的容错调度算法．计算机学报，2005，28(11)：1807—1816．
[77] 秦啸，庞丽萍，韩宗芬，李胜利：分布式实时系统的容错调度算法．计算机学报，2000，23(10)：1056—1063．
[78] Yang C. H., and Deconinck G., Design of a Power Quality Assessment System and the Role of Information Redundancy, The 6th Interational Conference: Engineering of Modern Electric'01 Systems, Oradea, Romania, May 2001
[79] Yang C. H., and Deconinck G., A Fault-tolerant reservation-based strategy for scheduling speriodic tasks in multiprocessor systems, IEEE Proceedings of 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Gran Canaria, Spain, Jan 2002. 319～326
[80] Yang C. H., and Deconinck G., Fault-Tolerant Scheduling of Periodic and Aperiodic Tasks in Multiprocessor Systems, IASTED International Conference on Parallel and Distributed Computing and Systems, pp. 535-542, California, USA, Aug. 2001
[81] 阳春华，沈德耀，桂卫华，实时多处理机系统BEST—FIT启发式容错调度，计算机工程与科学，2003，25(5)，P．61-64，85
[82] Terrier F, Chen Z. Fuzzy calculus applied to real time scheduling. In: Yen J, ed. Proc. of the 3rd IEEE Conf. On Fuzzy Systems, Vol 3. Piscataway: IEEE Computer Society. 1994. 1905～1910.
[83] Litoiu M, Tadei R. Real-Time task scheduling with fuzzy deadlines and processing times. Fuzzy Set and Systems, 2001, 117(1): 35～45.
[84] 金宏，王宏安，傅勇，王强，王晖．模糊反馈控制实时调度算法，2004，15(6)，791～798
[85] 金宏，王宏安，王强，傅勇，王晖：模糊动态抢占调度算法．计算机学报，2004，27(6)：812-818．
[86] 金宏，王宏安，唐雪梅，王晖：计算机控制中的模糊调度设计．计算机学报，2006，29(3)，414-422．
[87] Yao F, Demers A, Shenker S. Ascheduling model foe reduced CPU energy[C].In: Proc. 36th Symp. Foundations of Computer Science, 1995, 374～382.
[88] Krishna C M K, Lee Y H. Voltage clock scaling adaptive scheduling techniques or low power in hard real-time systems[C]. In: Proc. 6th IEEE Real-Time Technology and Applications Symp, 2000.
[89] Mosse D, Aydin H, Childers B, et al. Compiler-assisted dynamic power-aware scheduling for real-time applications[C]. In: proc. Workshop Compiler and OS for Low Power, 2000.
[90] D. W. Waston et al. A framework for compile-time selection of parallel modes in an SIMD/SPMD heterogeneous environment, Proc. WHP'93, Newport Beach, CA, Apr. 1993, pp 57-64.
[91] I. Ekrnecic, T.Tartalja, and V.Milutinovic, EM~3: A contribution to taxonomy of heterogeneous computing systems, IEEE computer, vol. 28, pp68-70, Dec. 1995.
[92] J. W. S. Lieu, W. K. Shin, K. J. Liu, R. Bettati and J. Y. Chung, Impercise Computations, Proc. IEEE, 1994, 82(1), 83-94.
[93] 张尧学，方存好，王勇．非精确计算中基于反馈的CPU在线调度算法．软件学报，2004，17(4)：616～623．
[94] 李建国，陈松乔，鲁志辉。实时多处理器系统的动态分批优化调度算法．小型微型计算机系统．2005，26(1)，84～89．
[95] 李建国，陈松乔，鲁志辉．实时异构系统的动态分批优化调度算法．计算机学报．2006，29(6)，976～984．
[96] 李建国，陈松乔，王建新，鲁志辉：基于分批优化的实时多处理器系统的集成动态调度算法．小型微型计算机系统．2006，27(9)：1641～1647．
[97] 吉勒特BE(美)著；蔡宣三，陈伟基，王永县译。运筹学导论——计算机算法。北京，机械工业出版社，1985，180
[98] 田庆辉，李建国，非平衡分配问题，湘潭大学自然科学学报，1992，第14卷，第2期：78～82．
[99] 刘仁舟，湘潭师范学院学报(自然科学版)，1988；4；15～19
[100] Mok, A. K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment [Ph. D. Thesis]. Cambridge, MA: Department of Electronic Engineering and Computer Sciences, MIT, 1983.
[101] Garey MR, Johnson Ds. Computers and Intractability - A Guide to the Theory of NP-Completeness. New York: W. H. Freeman and Co., 1979.
[102] 刘云生，何新贵，唐常杰，李霖。特种数据库技术。北京：科学出版社，2000。
[103] Jensen ED, Locke CD, Toduda H. A Time-driven scheduling model for real-time operating systems. In: Proceedings of the IEEE Real-time Systems Symposium. Washington, DC: IEEE Computer society Press, 1985, 112～122.
[104] Hou, E. S., Ansari, N. and Ren, H., Genetic Algorithm for Multiprocessing Scheduling, IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 2,1994, pp. 113-120.
[105] J. A. Stankovic, M. Spuri, K. Rarnamritham, and G. C. Buttazzo, deadline Scheduling for Real-time, Systems — EDF and Related algorithms, Kluwer Academic Publishers, 1998.
[106] G. Buttazzo and J. A. Stankovic, Adding Robustness in Dynamic Preemptive Scheduling, Responsive Computer Systems: steps Toward Fault-tolerant Real-Time System, Kluwer Academic Publishers, 1995.
[107] C. Lu, J. A. Stankovic, T.F.Abdelzaher, G. Tao, S.H. Son and M. Marley, Performance Specifications and Metrics for Adaptive Real-Time Systems, IEEE Real-Time Systems Symposium, Orlando, FL, Dec 2000.
[108] C. Y. Lu, H.A.Stankovic, Gang Tao and Sang H, Son Design and Evaluation of a Feedback Control EDF Scheduling, 20th IEEE Real-Time Systems Symposium, 1-3 December, 1999, Phoenix, Arizona.
[109] J.Baccouche, Multiprocessor Task Scheduling with Resource Requirements, Journal of Real-time Systems, 6(1), January 1994.
[110] G. Duck and T.Scheuer, Threshold Accepting: A General Purpose Optimization Algorithm Appearing Supior to Simulated Annealing, Journal of Computional Physics, pp.161-175, 1990.
[111] C.Cardeira, Neural Network Versus Max-Flow Algorithms for Multiprocessor Real-time Sacheduling, Preoceedings o9f the 8th Euromicro Workshop on Real-time Systems, pp. 175-180, 1996.
[112] Luca Abeni and Giorgio Buttazzo, Adaptive Bandwidth Reservation for Multimedia Computing, Sixth International Conference on Real-time Computing Systems and Applications, 13-15 December, 1999,Hong Kong,China.
[113] C.M.Krishna and K.GShin, Real-time Systems, pp.15, The McGraw-Hill Companies, Inc, 1997.
[114] Ekmecic, Tartalja, Milutinovic, A Survery of Heterogeneous Computing: Cnocepts and Systems, Proceedings of the IEEE, 1996, VOL. 84, No.8, pp.1124-1126.
[115] S.S.Skiena and Skiena, The Alogrithm design Manual, Telos/Sprnger-Verlag, New York, November 1997.
[116] Jane W.S.Liu, Real-time Systems, Prentice Hall, 2000.
[117] J.A. Stankovic, Marco Spuri, Macro Di Natale, and Giorgio, Buttazzo, Implicatoins of Classical scheduling Results For Real-time Systems, IEEE computer, vol. 28, No.6, pp.16-25, June 1995.
[118] J.K.Dey, J.F.Kurose, D.F.Towsley, C.M.Krishna and M.Girkar, Efficient On-line Processor Scheduling for a Calss of IRIS Real-time Tasks, SIGMETERICS 1993,pp.217-228, ACM, New York, 1993.
[119] Gerhard Fohler, Joint Scheduling of Distributed Complex Periodic and Hard Aperiodic Tasks in Statically Scheduled Systems, IEEE Real-time symposium, 1994.
[120] Chi ashen, Krithi Ramamritham, J. A. Stankovic, Resource Reclaiming in Multiprocessor Real-time Systems, IEEE Transaction on Parallel and Distributed System. Vol.4, No.4, April 1993.
[121] Hermann Kopetz, Real-time Systems: Design Principles for Distributed Enbedded Applications, pp.12-16, Kluwer Academic Publishers, 1997.
[122] Hiroyuki Kaneko, John A. Stankovic, Intergrated Scheduling of Multimedia and Hard Real-time Tasks, IEEE Real-time Symposium, 1995.
[123] John P. Lehoczky, S. Ramos-Thuel, An Optimal Algorithm for Scheduling Soft-Aperiodic Tasks in Fixed Priority Preemptive Systems, IEEE Real-time System Symposium, 1992.
[124] J. A. Stankovic, C. Y. Lu, Sang H, Son and Gang Tao, The Case for Feedback Control Real-time Scheduling, EuroMicro Conference on Real-Time Systems, June 1999.
[125] K.Tindell, A.bums and A. wellings, Allocating Real-time Tasks (An NP-Hard Problem made Easy), Journal of Real-time Systems, 1992,4(2): pp.145-165.
[126] C.J.Hou and K.G.Shin, Allocation of Periodic Task Modules with Precedence and Deadline Constraints in Distributed Real-time Systems, Proceedings of 13th Real-time Systems Symposium, 1992.
[127] R.A1-Omari, Arun K.Somani, G. Manimaran: Efficient overloading techniques for primary-backup scheduling in real-time systems.J.Parallel Distrib. Comput.64(5): 629-648 (2004)
[128] R.Al_Omari, G. Manimaran, M.V.Salapaka, Arun K.Somani:Novel Algorithms for Open-Loop and Closed-Loop Scheduling of Real-Time Tasks in Multiprocessor Systems Based on Execution Time Estimation.IPDPS 2003:7
[129] GGreenwood, C.Lang and S.Hurley, An, Evolutionary Strategy for Scheduling Periodic Tasks in Real-time Systems, Applied Decision Technologies, pp.171-188,1995.
[130] F.E.Sandnes, A Hybrid Genetic Algorithm Applied to Automatic Parallel Controller Code Generation, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp.70-75, 1996.
[131] Indranil Gupta, G. Manimaran, C.Siva Ram Murthy: A New Strategy for Improving the Effectiveness of Resource Reclaiming Algorithms in Multiprocessor Real-Time Systems. J.Parallel Distrib. Comput.2000, 60(1): 113-133.
[132] G. Manimaran, C.Siva Ram MURTHY, Machiraju Vijay, Krithi Ramamritham: New Algorithms for Resource Reclaiming from Precedence Constrained Tasks in Multiprocessor Real-Time Systems.J.Parallel Distrib.COMPUT. 1997,44(2): 123-132.
[133] Douglas Antony Louis Piriiyakumar, C. Siva Ram Murthy: Optimal Compile-Time Multiprocessor Scheduling Based on the 0-1 Linear Programming Algorithm with the Branch and Bound Technique. J.Parallel Distrib.Comput. 1996,35 (2): 199-204 .
[134] K.Mahesh, G. Manimaran, and C.S.R. Murthy, Scheduling Algorithms with Fault Detection and Location Capabilities for Real-time Multiprocessor Systems, Journal of Parallel and Distributed Computing 51(2), 136-150, 1998.
[135] L. Baccouche, Efficient Static Allocation of Real-time Tasks Using Genetic Algorithms, Internal Reprot, Image Institute, Laboratoire de genie informatique, 1995.
[136] S. Ronngren and B. A. Shirazik Static Multiprocessor Scheduling of Periodic Real-time Tasks with precedence constraints and communication costs, Proceedings of the 28th Annual Hawaii International Conference on System Sciences, pp. 145-152, 1995.
[137] 邹勇，淮晓永，李明树：开放式实时系统中的自适应调度方法．计算机学报，2004，27(1)：58-65．
[138] J. S. Antos, J. Oroico and R. Cayssials, A Heuristic Approach to the Multitask- Multipocessor Assignment Problem Using the Empty-slots Method and Rate Monotonic Scheduling, Real-time Systems, 13, pp. 167-199. 1997.
[139] S. Saez, J. Vila and A. Crespo, A Dynamic Real-time Scheduler for Shared Memorty Multiprocessors, Proc, 8th Euromicro Workshop on Real-time Systems, pp. 158-163, L, Aquila, Italy, June 12-14, 1996.
[140] 王永吉，陈秋萍：单调速率及其扩展算法的可调度性判定．软件学报．2004，15(6)：799-814．
[141] 刘军祥，王永吉，Matthew Cartmell：一种改进的RM可调度性判定算法．软件学报．2005，16(1)：89-100．
[142] S. Saez, J. Vila and A. Crespo, Dynamic Scheduling Sohations for Real-time Multiprocessor Systems, IFAC Real-time Programming, Gramado, RS, Brazil, 1997.
[143] Gilad Koren, Dennis Shasha and Shih-Chen Huang, MOCA: a Multiprocessor On-line Competitive Algorithm for Real-time System Scheduling, IEEE Real-time Systems Symposium, 1993.
[144] G.Manimaran, C. S. R. Murthy, M. Vijay, and K. Ramamritham, New Algorithms for Resource Reclaiming from Precedence Constrained Tashk in Multiprocessor Real-time Systems, Journal of Parallel and Distributed Computing 44, no. 2, pp. 123-132, 1997.
[145] J. Orozco, R. Cayssials, J. Santos, and E. Ferro, Design of a Learning Fuzzy Production System to Solve and NP-Hard Real-time Assignment Problem, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 146-150, 1996.
[146] E. Ferro, J. Sautos, J. Drozco, and R. Cayssials, Tuning Parameters to Improve a Heuristic Mehtod: More and better Solutions to an NP-Hard Real-time Problem, Proceedings of the 8th Euromicro Workshop on Real-time Systems, pp. 47-51, 1996.
[147] S. Lee, S. K. Oh and C. H. Woo, Dual-token-based Fault-tolerant Scheduling for Hard Real-time Multiprocessor Systems, 5th International Conference on Real-time Computin Systems and Applications, 1998.
[148] Sylvain Lauzac, R. Melhem and Daniel Mosse, Adding Fault-tolerance to p-Fair Real-time Scheduling, International Workshop on Embedded Fault-Tolerant systems, pp. 34-37, 1998.
[149] Songqiao Chen, Jingui Huang, Jianer Chen. Approximation algorithm for parallel job scheduling 中南大学学报(英文版) 2002, 9(4), 267-272.
[150] 黄金贵，陈建二，陈松乔：网络集群计算系统中的并行任务调度．计算机学报．2004，27(6)：765-771．
[151] Jingui Huang, Jianer Chen, Songqiao Chen. A simple and improved approximation algorithm for scheduling multiprocessor-jobs on 3-processor systems, 16th World Computer conference (WCC'2000, Beijing), Software theory and practical, (2000), pp800-806.
[152] Jingui Huang, Jianer Chen, Songqiao Chen. A simple linear time approximation algorithm for multiprocessor job on four processors, Lecture Notes in Computer science(ISAA'00, Taibei), 2000, pp. 60-71, Springer.
[153] Jianer Chen, Jingui Huang. Semi-Normal schedulings: Improvement on Goemans, 12th Annual International Sysposium on Algorithm and Computation(ISAAC'01) Lecture Notes in Computer science(2001, Newzeland), pp. 60-71, Springer.
[154] 黄金贵，陈建二，陈松乔：并行环境下基于多处理机任务的调度模型和算法．计算机科学．2002，29(4)：1-3．
[155] 陈松乔，黄金贵，陈建二：网络并行环境下多处理机任务的调度．小型微型计算机系统．2003，24(7)，1144-1147．
[156] 黄金贵，陈建二，陈松乔：网络计算系统中基于多处理机任务的调度模型．计算机工程与应用．2003，39(29)，54-58，83．