【作者】 巴巍；

【导师】 王伟； 张大波；

【作者基本信息】 大连理工大学 ， 控制理论与控制工程， 2010， 博士

【摘要】 实时系统计算结果的准确性及输出结果的及时性使得其在工业、国防、一医疗和通信等诸多领域得到越来越广泛的应用。随着对实时系统性能要求的不断提高,传统任务调度算法的调度性能越来越难以满足应用的要求。论文围绕实时系统单处理器任务调度和多处理器任务调度两个方面展开研究,特别针对动态优先级任务调度算法中存在的若干问题,进行了深入研究。本文主要研究工作归纳如下：针对单处理器最小空闲时间优先调度算法作业切换常出现颠簸的现状,提出一种改进的动态模糊阈值最小空闲时间优先软实时调度算法。给出“模糊阈值系数”的概念,选取当前作业的剩余空闲时间和周期为模糊输入,运用模糊理论生成模糊阈值系数,用动态模糊阂值作为当前作业的虚拟剩余空闲时间参予优先级比较以尽量避免抢占。仿真结果表明,与最小空闲时间优先调度算法相比,该算法在不降低调度成功率的同时有效地减少了作业的切换次数。针对最早截止期优先调度算法作业切换多、超载时错失率高的现状,提出两种改进的最早截止期优先软实时动态调度算法。两种算法选取当前作业的剩余空闲时间和关键性系数为模糊输入以生成动态模糊阈值系数,分别通过缩短和延长当前作业的绝对截止期至动态模糊阈值的方法减少抢占、避免作业错失。阈值的大小由作业的多种参数共同决定,大大提高了重要作业被成功调度的几率。仿真结果表明,与最早截止期优先调度算法比较,两种算法有效地提高了重要作业的完成率,当截止期被延长时,错失率明显降低,当截止期被缩短时,作业间的切换次数大大减少。针对优先级个数受限系统中调度算法难以确保分组准确性问题,提出一种改进的组优先级最早截止期优先调度算法。给出作业分组可调度性能测试,将满足分组可调度测试公式的作业作为一个作业组,以作业组内最早绝对截止期为作业组优先级,作业组与其他作业按照最早截止期优先调度,在作业组得到系统资源后,作业组内按照最短作业优先的原则执行作业。仿真结果表明,与最早截止期优先调度算法、尽力服务调度算法及其他组优先级调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高调度的成功率,缩短平均响应时间,减少作业切换次数。针对同构多处理器动态优先级局部调度中密度算法和DBF*算法的判据存在可能将可调度任务误判为不可调度的情况,提出一种新的高效需求界限函数局部调度算法。算法采用更为精准的可调度性判据,分别在最小数目处理器以及固定数目处理器两种情况下,通过多阶跟踪需求界限函数轨迹确保了对任务可调度性判断的准确性。仿真结果表明,新算法与密度算法和DBF*算法相比,可调度任务的数量大大提升。针对异构多处理器局部调度算法复杂度高且难以实现最优分配的问题,提出一种新的整数线性规划局部调度算法。在准确表达处理器之间的差异以及任务参数后,设定总处理器利用率为目标函数,通过建立约束条件求取目标函数的最小值,将异构多处理器调度问题描述为整数线性规划问题,利用Lingo快速求解整数线性规划问题,进而求得异构多处理器任务的优化分配。仿真结果表明了新算法的有效性。更多还原

【Abstract】 The accuracy of the computing results and the timeliness when the results come out in a real time system make it widely used in more and more areas, such as industry, defense, medical care and communications.However, with the higher demands of schedulability of real time systems, it is harder and harder for the traditional real-time scheduling algorithms to satisfy the demands of the applications.In this dissertation, we have researched on the scheduling on uniprocessor systems and multiprocessor systems, especially focused on the dynamic prioritiy scheduling algorithms.The main contributions and achievements of this dissertation are stated as follows:The least slack time first scheduling algorithm may frequently cause switching or serious thrashing among jobs.In this dissertation, an improved dynamic fuzzy threshold least slack time first scheduling algorithm for soft real-time sytems is proposed. The notion of fuzzy threshold coefficient is given. The slack time and the period of the running job are selected as the fuzzy inputs.The fuzzy threshold coefficient is generated by fuzzy theory.We regard the dynamic fuzzy threshold as the virtual slack time of the running job to avoid preemption. The simulation results show that, the dynamic fuzzy threshold makes the switching number of the improved algorithm smaller and the ratio of success not descreased.To avoid the frequenty switching and decrease the missed deadline percentage when the systems is overloaded in earliest deadline first scheduling algorithm, two improved earliest deadline first algorithms are presented in this dissertation. In the two algorithms, the slack time and the cruces coefficient of the running job are selected to be the fuzzy inputs in order to genenrate the fuzzy threshold coefficient. The absolute deadline of the running job is extended to save the resource in one algorithm and is shorten to increase the ratio of success in the other. The threshold is decided by several parameters of the running job, as a result, the ratio of success for important jobs is increased in both of two algorithms. The performance of the algorithms is experimentally examined and compared with the earliest deadline algorithm in detail.Results show that, the missed deadline percentage is decreased obviously while the deadline is extended and the switching number is reduced greatly while the deadline is shortened. The ratio of success for important jobs is increased efficiently by using these two algorithms. When the number of priority levels supported by the system is limited, it is hard to ensure the accuracy of grouping method in the scheduling algorithms.To solve this problem, an improved group priority earliest deadline first scheduling algorithm is proposed. We give the schedulability test. All the jobs satisfying the schedulability test are formed into a group and the earliest absolute deadline of the jobs in the group is chosen to be the priority of the group. The group and the other jobs in the system are scheduled under earliest deadline first. When the group gets the system resource, the jobs in the group are scheduled under shortest job first. Compared with earliest deadline first algorithm, best effort algorithm and other grouping algorithms, the simulation results show that the novel algorithm not only can decrease the priority levels effectively, but only can increase the ratio of success, shorten the average response time and reduce the switching number.In the scheduling of sporadic tasks on identical unit-capacity mulitiprocessors, the criterions used in density algorithm and the DBF* algorithm may cause the tasks which are feasible under the partitioned paradigm be flagged as "infeasible" sometimes.In this dissertation, a novel efficient demand bound function partitioned scheduling algorithm is proposed. A criterion which tracks the demand bound function exactly as needed is used on least-number processors and fixed-number processors respectively to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the novel algorithm. The experimental results demonstrate that the number of tasks schedulable in the novel algorithm is much higher than in density algorithm and DBF* algorithm.The partitioned scheduling on heterogeneous multiprocessors is complicated and hard to be optimal.To solve the problem, a novel integer linear programming partitioned scheduling algorithm is proposed. After describing the parameters of the tasks and the processors correctly,we regard the total utilization as the objective function and get the minimal value of the objective function by the constraints.The scheduling problem is changed to an integer linear programming problem.We use Lingo to get the solutions and assign the tasks according to it. The simulation results show the validity of the novel algorithm.更多还原