实时系统的基于优先级的实时重构和不基于优先级的条件剥夺调度算法

发布时间：2018-03-16 02:23

本文选题：动态重构　切入点：实时系统　出处：《西安电子科技大学》2016年博士论文　论文类型：学位论文

【摘要】：在过去四十年中,实时系统调度与重构作为一大热点,已经被深入而广泛地研究过,成果丰硕。目前,在此研究领域里,已经建立了比较完善的基础理论体系。通常,实时系统的调度算法主要可以分为两大类：基于静态优先级与基于动态优先级的调度。最早截止时间优先算法是目前最为广泛使用的基于动态优先级的调度算法。相应地,最为常见的静态优先级的调度算法是固定优先级调度。此外,在实时系统的调度过程中,任务的执行方式可以分为可剥夺和不可剥夺两种方式。基于此,用户可以对实时系统进行动态的重构,以保证系统的正常运行。近年来,国内外学者对实时系统的低能耗动态重构进行了大量的研究与探讨。本毕业论文所要实现的第一个贡献就是,通过对实时系统进行低能耗的动态重构,以达到降低系统的能量消耗的重要目标。此部分主要是对具有实时周期任务和随机任务的系统执行低能耗重构。这些任务的运行与系统的内外部事件相对应。具体涉及对周期性任务和有硬／软截止时间的随机任务执行调度。这种基于事件的重构方案允许动态地添加／删除由系统指派的周期性任务或随机任务。但在任务增加之后,其中一些任务可能错过他们的硬截止时间,使调度失败。同时,系统的能耗也有可能会增加。为了使系统能够重新满足其调度的可行性与灵活性,并且节约系统的能耗,本文提出了一种基于智能代理的软件架构。此种智能代理构架,可以提供四种实时重构系统的解决方案。这些解决方案可以动态地修改系统中任务的时间参数,以保证其运行正常。此外,为了有效地执行随机任务并且降低系统的能耗,本代理通过动态地扩展周期性任务的运行周期,提供了三个虚拟处理器。最终,基于仿真研究,我们验证了该智能代理的有效性。过去三十年以来,离散事件系统的监督控制理论从诞生以来,一直受到广泛的关注和认可。基于离散事件系统,系统的行为可以被描述成形式语言。基于形式语言,用户可以方便地定义系统的行为约束。通常情况下,监督控制理论可以找到一组最优解,该最优解对系统的行为有最少的约束。用户对系统的行为可以提出一定的限制。结合这些限制,监督控制理可以设计控制器并找出最优解,使该控制问题可以被全面而有效的解决。时间离散事件系统的监督控制理论,通过在考虑时间因素的情况下,可寻找到系统的最优解。众所周知,传统的实时系统调度不能提供所有的安全运行路径。文献[32]通过将实时任务的基于动态优先级的调度和时间离散事件系统的监督控制进行结合,最终生成的控制器可以提供给系统所有的调度运行路径。以此文献为基础,本毕业论文的第二个贡献是：提出了一种能运行在单处理机上的实时系统动态调度重构技术。这种新模型可用来分配给每个周期性任务一组不同的周期。通过利用监督控制理论,在实时系统最初始的安全执行序列集合为空时,它可被动态地重构。在这个重构过程中,基于多周期的环境,监督控制器可以提供所有的安全执行路径。本部分还通过计算两个实例来进一步阐明,相较于最早截至时间优先调度算法,这种新调度方法可以提供的更多的安全执行路径的数量。由于时间离散事件系统中的时间是由唯一的时间事件表示,所以对实时系统行为的描述有一定的局限性。因此导致了其所建立的控制模型只能对静态(固定)优先级实时系统进行建模、调度和重构。为了能够提出一套更为普遍,更为完善的实时调度理论,本毕业论文的第三个贡献是：与基于优先级的实时调度方法相比,本文提出了一种更一般的基于离散事件系统的硬周期实时系统调度模型。该调度模型的调度过程是通过监督控制理论,而不是以任务的优先级去进行决策调度。该调度方法可用来处理单处理机或多处理机上运行的所有任务。其中,各实时任务的剥夺关系比基于优先级的剥夺更加一般化。在调度过程中,首先,计算机形式语言可以被用来描述各实时任务执行时所关联的处理器行为；其次,所有的计算机语言是用离散事件系统所生成的控制器来表示；第三,在离散事件系统控制器生成的同时,全局控制器也将产生。在此基础上,本部分创新地提出了一个新的调度策略——条件剥夺。在处理器和实时任务两个层面上,分别构建了两种条件剥夺的方式。此外,为了能够有效、无阻碍地控制系统,并且限制任务的最坏响应时间,本部分还提出了另外两组约束方式。在产生全局控制器后,通过执行监督控制理论,计算出的监控器可以提供所有的实时安全执行路径。这种监控器的计算速度可通过一个三步算法得以加快。最终,本部分用多个实例来验证了此种新调度算法。在今后的研究工作中,我们要在本毕业论文第三个贡献的基础上,对实时系统进行动态地重构。另外,现有的调度和重构方法只能提供所有的路径,而未能在其中找出一组最优路径。在今后的工作中,我们也要致力于这方面的研究。
[Abstract]:In the past forty years, real time scheduling and reconstruction as a hot spot, has been deeply and widely studied and achieved fruitful results. At present, in this field of research, has established a well-established theoretical system. Usually, scheduling algorithm for real-time system can be divided into two main categories: Based on static priority and based on dynamic priority scheduling. The earliest deadline first algorithm is currently the most widely used scheduling algorithm based on dynamic priority. Accordingly, the most common static priority scheduling algorithm is fixed priority scheduling. In addition, in the process of scheduling in real-time systems, tasks can be divided into deprivation and don't be deprived in two ways. Based on this, the user can dynamically reconfiguration of the real-time system, in order to ensure the normal operation of the system. In recent years, domestic and foreign scholars on the dynamic real-time system with low energy consumption State reconstruction was studied and discussed. A large number of the first contribution of this thesis is to be achieved through dynamic reconfiguration, low energy consumption of real-time system, in order to reduce the important goal of the energy consumption of the system. This part is mainly on the system with real-time periodic tasks and task execution machine with low energy reconstruction. The operation of these tasks and system of internal and external events. The corresponding specific scheduling of periodic tasks involving random tasks and hard / soft deadline. This event allows reconstruction scheme to dynamically add / delete by a system of periodic tasks assigned or random based tasks. But in the task after the increase, some of the task they may miss the hard deadline, the scheduling failure. At the same time, the energy consumption of the system is likely to increase. In order to make the system able to meet its feasibility and flexible scheduling Of energy consumption and saving system, this paper proposes an intelligent agent based software architecture. The intelligent agent architecture, can provide four solutions for real-time reconfigurable system. Time parameters of these solutions can dynamically modify the tasks in the system, to ensure its normal operation. In addition, in order to effectively execute the random task and to reduce the energy consumption of the system, the agency through dynamically extended periodic task cycle, provides three virtual processors. Finally, based on the simulation results, we verify the effectiveness of the intelligent agent. Since the past thirty years, the supervisory control theory of discrete event system from its inception, has been the subject of widespread concern and recognition. Based on discrete event system, the behavior of the system can be described as a form of language. Based on the form of language, the user can easily define the behavior of the system is usually binding. Under the condition of supervisory control theory can find a set of optimal solutions, the optimal solution of the behavior of the system is the least constrained. Users put forward certain restrictions on the behavior of the system. With these limitations, supervisory control theory can controller design and find out the optimal solution, the control problem can be comprehensive and effective solution. Time supervisory control theory of discrete event system, by considering the time factor, to find the optimal solution of the system. As everyone knows, the traditional real-time scheduling can provide safe operation of all paths of [32]. This will pass the real-time supervision of dynamic priority scheduling and time discrete event system control based on finally, the controller can be generated to provide dispatching system. This path all the literatures, the second contribution of this thesis is: a Can run on a single processor real-time dynamic scheduling system reconfiguration. The new model can be used to assign each periodic task a group of different periods. Through the use of supervisory control theory, the safety execution sequence of the initial real-time system set is empty, it can be reconstructed dynamically. In the process of reconstruction. Multi cycle based environment, the supervisory controller can provide safe execution path of all. This part also through two examples to further clarify, compared with the earliest deadline first scheduling algorithm, the number of the new scheduling method can provide a more secure execution path. Because of the time discrete event system in time is by the time the only event, so the real-time behavior of the system described has some limitations. Therefore only led to the establishment of control model of static (fixed) priority Modeling real-time system, scheduling and reconstruction. In order to put forward a more common, more real-time scheduling theory, the third contribution of this thesis is: compared with real time scheduling method based on priority, the paper presents hardware cycle based on discrete event system more generally a real-time scheduling model the scheduling process scheduling model. Through the supervisory control theory, rather than to the priority of the task to make decision scheduling. The scheduling method can be used to handle all tasks running on a single processor or multi processor. Among them, the real time task deprived than the priority based on the deprivation of more general. In the process of scheduling, first of all form, computer language can be used to describe the behavior of each processor tasks are associated; secondly, every computer language is generated by a discrete event system The controller to express; third, generated in the discrete event system controller at the same time, will also have a global controller. On this basis, this part proposes a new scheduling strategy - conditions deprived. In the two dimension processor and real-time tasks, we constructed two conditions of deprivation. In addition, in order to effectively and freely control system, task and limit the worst-case response time, this part also proposes the other two groups. In the global constraint controller, through the implementation of supervisory control theory, calculated the monitor can provide real-time security execution path. All the computing speed of the monitor by a three step algorithm is accelerated. In the end, this part with a number of examples to verify the new scheduling algorithm. In the future study, we will in this graduation thesis third contribution On the basis of this, we reconstruct the real-time system dynamically. In addition, the existing scheduling and refactoring methods can only provide all the paths, but fail to find a set of optimal paths. In the future work, we should also focus on this aspect.

【学位授予单位】：西安电子科技大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：TP301.6

【相似文献】