【作者】 周双娥；

【导师】 袁由光；

【作者基本信息】 哈尔滨工程大学 ， 计算机应用技术， 2003， 博士

【摘要】 实时分布系统的任务调度问题是一个富有挑战性的问题，也是当前的一个研究热点。由于任务的调度是一个典型的NP问题，同时它又是直接影响分布式系统性能的关键因素，因此，研究实时分布计算机系统的任务调度策略具有重要的理论意义和实际意义。本文以“十五”国家重点预先研究项目为背景，针对实际应用中大量的实时相关周期多任务及容错任务，对分布实时系统的调度理论与工程实践问题进行了深入的探索与研究。 首先，根据实时分布系统的体系结构模型及特点，从理论上对实时分布系统的任务调度策略进行了研究，提出了任务划分的准则及方法，给出了任务可调度性证明以及调度算法的评价体系。 针对实时分布系统中大量的相关周期性多任务，在分析、总结了前人对此类任务的调度算法解决方案所存在的问题基础上，构造了一种新的启发函数，该启发函数充分考虑了任务之间的前驱、后继关系，以当前任务的直接后继具有最早开始执行时间为目标。通过理论证明与模拟实验表明：本文构造的启发函数具有较强的启发能力，对DAG图的调度具有较优的效果。 利用本文所构造的启发函数，针对相关周期性多任务，提出了一种基于任务复制的启发式静态调度算法(DAG任务图的处理器预分配算法PPA)。证明了该算法能使整个任务的调度时间为最短以及在保证系统实时性的前提下能够减少处理机数目。对算法复杂性进行了理论分析，给出了实验数据及与其它同类算法的比较结果。由于该算法对任务粒度未做任何限制，因而对研究实时分布式计算机系统的任务调度算法具有普遍意义。 结合实时分布系统中容错任务的特点，根据容错调度原理，给出了容错任务的调度模型、实现机制及动态容错调度算法FTPB，并对算法进行了复杂 哈尔滨工程大学博士学位论文;;;二;;奋石石奋;性分析，给出了算法实验数据及与其它同类算法的比较结果。理论和实践证明:该算法在系统不增加额外资源的前提下，能有效地利用CPU资源，并提高了任务的接受率，因而既有较好的容错能力又保证了任务的实时性，使算法更加实用。另外，本文提出的算法不仅适用于周期性任务，而且也适用于非周期性任务。 最后，本文针对“十五”国家重点预先研究项目，给出了实时分布容错系统的体系结构，提出了整个系统的容错设计方案及高性能容错服务器的容错功能实现技术。给出了实时分布容错系统的任务调度结构图、调度机制与实现方案，并给出了相应的演示系统。更多还原

【Abstract】 Task scheduling in Real-time Distributed Computer Systems (RTDCS) is an issue mat is full of challenge, also a hot research subject nowadays. Because task scheduling problem is a typical NP problem and a critical aspect which directly impacts the system performance, to study task scheduling scheme in RTDCS is of great significance. With the support of the key national preresearch project for the 10th five-year plan, this paper has deeply studied scheduling theory and engineering practice of RTDCS, aimed at large amount of existing real-time relevant period multitasks (RTRPMT) and tasks to be fault-tolerant (TFT).Firstly, the paper studies the theory of task scheduling scheme in RTDCS according to the architecture model and property of RTDCS , proposes principles and method for partitioning tasks, gives the proof of task schedulability and an evaluation system for schedule algorithm.Based on summarized and analyzed the existing problems of the solution for scheduling RTRPMT and TFT, the author constructs a new heuristic function which adequately takes predecessor and successor relation among tasks into account, targeting that the direct successor of current running task is to be given the earliest time to be run. Theoretical proof and simulation suggests that this constructive function has stronger heuristic power, and has better effectiveness for scheduling DAGA task-replication based heuristic static scheduling algorithm is also proposed (namely Processor Pre-allocation Algorithm for DAG tasks, PPA), utilizing the aforementioned heuristic function aimed at RTRPMT. It is demonstrated that PPA is capable of getting shortest scheduling time for the tasks as a whole to be scheduled, and able to reduce the number of processors used while meeting the real-tune requirement Theoretical analysis and simulation is also made, experimental data and comparison table with other algorithms are also presented. Because of no limitation to task granularity, PPA is especially suitable for scheduling fine granularity tasks (also suitable for coarse and medium tasks of course), consequently helpful theoretically and practically for studying task schedule algorithm for RTDCS.According to the principle of fault-tolerant scheduling, combined with characteristics of TFT in RTDCS, the paper puts forward the scheduling model of TFT, corresponding implementation mechanism and the dynamic fault-tolerant scheduling algorithm (namely FTPB) and analyzes its complexity, with experimental data and contrast table compared with other analogic algorithm.Both theoretical proof and practice show that FTPB can efficiently utilize CPU resource and increase the task acceptance ratio without adding extra resource to the system. So FTPB has better fault-tolerant capability and at the same time guarantees the real-time demand of task. Not only is FTPB applicable for periodic tasks, but also for non-periodic tasks.Lastly, the paper proposes the architecture of a fault-tolerant RTDCS, the fault-tolerant design skeleton of the whole system, and the implementation technique of fault-tolerance of a high performance fault-tolerant server, with the presentation of the task scheduling structure figure, schedule mechanism, implementation scheme and a corresponding demonstration system, all of which will be used in the project.更多还原