【作者】 张杰；

【导师】 卢炎生； 阳富民；

【作者基本信息】 华中科技大学 ， 计算机软件与理论， 2009， 博士

【摘要】 实时系统具有及时响应、高可靠性、专用性、少人工干预等特征,被广泛应用于工业控制、军事防御、信号处理、航空航天技术等方面。在实时系统研究和应用的各个领域中,实时调度算法都是其中的一个基础问题,针对各种实时问题的解决,都需要在采用某种实时调度算法的基础上,结合该实时调度算法的性质才能更好的证明其可行性,并且实时调度算法的研究也可以很好的启发各种实时问题的解决,因此实时调度算法的研究对实时系统的研究和应用有重要的意义。最早截止期优先(earliest deadline first,简称EDF)调度算法作为最优的动态优先级调度算法,调度策略简单,并且周期任务集的总负载可以达到100%,其研究具有重要的理论和实际意义。EDF算法调度周期任务集的最大可挪用时间在非周期任务调度、软实时任务调度和多处理器容错调度等方面都有重要的应用。通过对最大可挪用时间的性质进行分析,得出了最大可挪用时间等于系统中所有任务的最小可延迟时间且具有最小可延迟时间的任务发生在超周期的第一个繁忙区间等结论。在此基础上,提出一种可延迟时间逼近(delay time approximation,简称DTA)算法,利用EDF算法调度的最优性,通过最小周期任务的可延长执行时间逐次逼近,快速准确的计算最大可挪用时间。该算法的时间复杂度函数只和周期任务集的总负载、周期任务数有关,不需要在整个超周期中计算。现有的硬实时周期任务和非周期任务混合调度算法的目标是为了缩短非周期任务的响应时间,不能判断该调度能否满足非周期任务的时限要求,所以它们都只适用于软实时任务的调度,而不适用于偶发任务的调度。因为EDF算法根据实时任务的截止期进行调度,所以可以直接用EDF算法来统一调度硬实时周期任务和偶发任务,并且具有最优的可调度性。通过计算EDF算法调度过程中的空闲时间和可挪用时间,以及调度偶发任务后对空闲时间和可挪用时间的影响,提出一种空闲挪用时间(idle slack stealing,简称ISS)算法来进行偶发任务的可调度性判定。在多个实时任务之间有共享资源访问时,采用资源访问控制协议可以防止实时任务被无限期的阻塞,但是避免不了优先级反转引起的直接阻塞,还会导致继承阻塞。这些阻塞的过程都是低优先级的任务抢占高优先级的任务运行,打乱了EDF算法的正常调度。通过证明阻塞不会改变EDF调度时的空闲时间分布,并且在一个繁忙区间内,所有周期任务的每次运行最多都只会因为同一个资源的阻塞被推迟一次,然后把阻塞时间看成是挪用时间,根据最大可挪用时间的定义和性质提出了一种阻塞挪用时间(blocking translate stealing time,简称BTS)的可调度性判定条件:只要所有共享资源的最大临界区的长度之和不大于最大可挪用时间,硬实时周期任务集就是可以被调度的。更多还原

【Abstract】 The real-time system has some characters such as responsing in time, high dependability, dedication and less artificial interference, so it is widely applied in the industrial control, military defense, signal processing, and aerospace technology. In the real-time systems research and applications in various fields, real-time scheduling algorithms are one of the basic problems, For a variety solution of real-time problem, it need on the basis adopt some kind of real-time scheduling algorithm, testifying whose feasibility combining with owing real time scheduling algorithmic character ability more well. Therefore, real-time scheduling algorithm is important for the real-time systems research and popularization. The EDF (earliest deadline first) scheduling algorithm as the optimal dynamic priority scheduling algorithm, the scheduling strategy is simple and periodic task sets can reach 100% of the total load, so there are a very attractive prospect.The maximum stealing time of the EDF algorithm for scheduling periodic task has important application in many fields such as the non-periodic tasks scheduling, soft real-time tasks scheduling and multi-processor fault-tolerant scheduling, etc. Analysing of the nature of the maximum stealing time, giving the result that the maximum stealing time is equal to the minimum delayed time appears in the first busy time interval of the hyperperiod, presents the DTA (delay time approximation) algorithm. Using the optimal nature of EDF scheduling algorithm, and apporathing gradually by the delayed time of the task with the minimum period time, DTA algorithm can rapidly and accurate calculate the maximum stealing time. The algorithm’s time complexity is only related to the total load of the periodic task set and the number of periodic tasks.The existing hard real-time periodic tasks and non-periodic task scheduling algorithm aims to shorten the response time of aperiodic tasks and can not determine whether the task can meet the deadline tiem. So they are only suitable for soft real-time task scheduling, does not apply to sporadic task scheduling. Because EDF algorithm is based on the deadling time of each real-time task, so can use EDF scheduling algorithm to unified schedule real-time periodic tasks and sporadic tasks, and has the best schedulability. By calculating the idle time and the stealing time in the scheduling procedure with EDF algorithm, propose the ISS (idle slack stealing) algorithm to determine the schedulability of sporadic tasks.When there are mutual exclusion resources sharing between some real-time tasks, using resource access control protocol can prevent real-time task has been indefinitely blocked, but can not prevent the direct blocking caused by priority inversion. In blocking time, the low-priority task seizes the high-priority task to run, disrupting the normal EDF scheduling procedure. By proving that blocking time does not change the distribution of idle time, and in a busy time interval, all periodic tasks will only be postponed once due to the same mutual exclusion resource. Then the blocking time as steal time and according to the definition and nature of maximum steal time, put forward the BTS (blocking translate stealing time) algorithm, witch can determine the conditions for schedulability. As long as the sum of the most critical areas of resources is more than the length of the maximum steal time, the real-time periodic task set is to be scheduled with EDF algorithm.更多还原