EDF统一调度硬实时周期任务和偶发任务的可调度性判定算法

现有的硬实时周期任务和非周期任务的混合调度方法都没有保证非周期任务的实时性,所以不适合调度具有强实时要求的偶发任务.通过分析和计算EDF算法调度偶发任务所占用的空闲时间和挪用时间,以及调度后对空闲时间和最大可挪用时间的影响,提出一种采用EDF算法统一调度硬实时周期任务和偶发任务时的可调度性充分判定算法.最后用仿真实验得出了该算法在不同系统负载下的判定准确率和偶发任务的平均响应时间.     

先进飞机软件实时性能优化与测试算法

阐述了先进飞机电气系统处理机的功能;为了满足先进飞机电气系统处理机的强实时性能,着重探讨了在实时操作系统VxWorks下将电气系统处理机执行软件功能优化为若干任务,并针对普通RMS算法只能对系统中周期任务进行有效调度而不能对系统中的非周期任务进行有效调度的局限,利用分布假设检验改进RMS算法对非周期任务的调度能力,最后定量讨论了系统整个任务集的实时性和可调度性;由实际测试结果可知,该优化算法任务划分合理,可以保证强实时周期、非周期任务满足其时限要求.     

双头镜像磁盘的实时调度算法及性能评价

本文对双头镜像磁盘系统模型进行实时扩展,并提出了三种实时调度算法：最早截止期优先算法（ＥＤＦ）,可满足的最早截止期优先算法（Ｆ－ＥＤＦ）和忽视超时限请求算法（ＩＧＭ－ＥＤＦ）．这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头镜像磁盘系统能更好地满足实时需求．在进行了性能模拟后,发现实时调度算法比非实时算法能更好地满足实时Ｉ／Ｏ请求的时限要求．三种实时调度算法中,适用于硬实时应用的ＩＧＭ－ＥＤＦ的性能最好,Ｆ－ＥＤＦ算法的性能次之,它适用于软实时环境．     

科技文摘信息

用于实时多任务调度的软件时钟 DOS环境下进行实时多任务软件设计,为了使CPU对各任务有一个合理的时间分配,希望根据各任务对响应时间的要求,使不同的任务在不同周期时钟调度下运行。为此,作者研制了一个用于实时多任务调度的软件时钟平台,它能产生周期为1～55ms的时钟中断,不同响应时间的任务可以在它的调度下运行。作者提供了程序清单。 武汉华中理工大学塑性研究所(430074)     

基于动态优先级策略的最优软非周期任务调度算法

周期任务与非周期任务的混合调度是实时调度研究的一个重要方向 通过定义“调度”和“逆调度” ,对实时周期任务集在使用EDF算法调度时的可挪用时间进行分析 ,求出了周期任务集在使用EDF调度时的最大可挪用时间 在此基础上 ,提出用于缩短非周期任务响应时间和周转时间的调度算法———ISA(idlestealingalgorithm) ISA算法充分使用最大可挪用时间 ,在保证周期任务满足最后期限的同时能取得非周期任务的最优响应时间和周转时间 证明了ISA算法的最优性 ,并使用仿真实验进行了性能验证     

提高软非周期任务响应性能的调度算法

实时环境中常常既包含硬周期任务,又包含软非周期任务,引入一种改进软非周期实时任务响应时间的算法.已有的解决混合任务调度问题的方法都是基于速率单调（Rate Monotonic）策略的,其中从周期任务“挪用时间”的算法被证明优于其他所有算法.但是,速率单调算法限制了处理器的使用率,从而使周期任务的可“挪用”时间受到限制.最后期限驱动（Deadline Driven）策略DD可使潜在的处理器利用率达到100%.新算法正是在周期任务的调度中适当加入了DD策略,从而使非周期任务的响应时间得以缩短.仿真实验的结果表明,这种算法的性能优于已有的所有算法,而由它所带来的额外开销却不算很高.     

双头镜橡磁盘的实时调度算法及性能评价

本文对双头镜像磁盘系统模型进行实时扩展,并提出了三种实时调度算法：最早截止期优先算法（ＥＤＦ）,可满足的最早截止期优先算法（Ｆ－ＥＤＦ）和忽视超时限请求算法（ＩＧＭ－ＥＤＦ）。这三种算法充分考虑了Ｉ／Ｏ请求的截止期限,使双头镜像磁盘系统能更好地满足实时需求,在进行了性能模拟后,发现实时调度算法比非实时算法能更好地满足时Ｉ／Ｏ请求的时限要求。三种实时调度算法中,适用于硬实时应用的ＩＧＭ－ＥＤＦ的性能     

基于(m,k)-firm约束规范的混合任务调度算法研究

讨论了在准实时环境下,包括准实时周期任务和准实时非周期任务在内的混合任务调度算法HTSF.HTSF算法是在满足周期任务(m,k)-firm 约束规范的前提下提高非周期任务可调度性,同时合理利用可用空闲时间,提高整个系统的服务质量.HTSF算法给出了非周期任务的可调度性分析方法,同时采用静态调度与动态调度相结合的方法调度周期任务和非周期任务.模拟测试结果显示,系统对非周期任务的接收率比同类相关算法的接收率高.     

固定优先级抢占调度算法下非周期任务实时性能研究

嵌入式实时系统不仅要在功能上满足需求,而且要在性能上满足实时性需求.给定调度算法,实时性取决于各个任务的到达特征和执行时间.任务的到达特征由应用环境决定.为此,本文研究任务执行时间对实时性能的影响,为嵌入式系统设计提供参考.针对固定优先级抢占调度算法,应用排队论,提出一种非周期实时任务的理论模型.该理论模型包含两个优先级不同的非周期实时任务,给出了任务的执行时间长短对时限错过率、任务响应时间、任务队列长度等实时性能的影响.给出一个应用实例,仿真结果验证了理论模型的正确性.     

面向任务关键普适计算的安全自适应任务调度

为了增强普适计算环境下实时应用的安全性,建立了安全关键的实时周期任务模型、任务安全开销模型和任务安全风险模型,提出一种安全风险感知的自适应调度算法.该算法依据实时周期任务可调度的本质特性,将调度问题转化为安全风险最小化的多阶段决策过程,并基于近似动态规划策略实现了安全性能确保和低复杂度的调度机制.实验结果表明,该算法可明显降低应用的安全风险,满足应用的安全需求,自适应普适计算的动态变化.     

引入虚拟特征参数的混合实时任务调度及应用

提出了在实时环境下周期任务与非周期任务混合调度的一种新方法。引入非周期实时任务虚拟截止期、虚拟周期的特征参数,综合考虑各实时任务的多特征参数进行优先级设计,克服了单独考虑任务的个别参数以及忽略非周期任务自身特征的调度策略的局限性及调度风险,且能够尽可能地加快非周期任务的响应速度,提高系统整体的调度性能。将该方法在RT-Linux实时环境中实现,并针对无人飞艇的自动驾驶仪进行了任务实例的可调度性测试,证明了该调度策略的可行性。     

Reliability improvement of the dual-priority protocol under unreliable transmission

The dual-priority is a scheduling policy providing the guarantees needed by periodic or sporadic hard real-time tasks while decreasing the response time for aperiodic soft real-time tasks. This scheduling policy can be applied to message scheduling and its performance on controller area network (CAN) will be assessed. Nevertheless, when used in an electromagnetic stressed environment (e.g. automotive communication) leading to transmission errors, this scheduling strategy could lead to serious disappointments. It will be explained why the hard real-time traffic is highly sensitive to transmission errors. The risks of deadline failure will be quantified and a simple mechanism that provides probabilistic guarantees to prevent hard real-time frames from missing their deadlines, will be proposed. This mechanism is compared in terms of performance to the original dual-priority strategy. The chosen performance metrics are the deadline failure probability for hard real-time traffic, the average response time and the variance in response time for soft real-time traffic.     

Dynamic priority scheduling of periodic and aperiodic tasks in hard real-time systems

This paper addresses the problem of scheduling aperiodic tasks in real-time systems. The proposed scheme combines the Earliest-Deadline-First algorithm for scheduling periodic tasks with the Deferrable Server approach for servicing aperiodic tasks. Necessary and sufficient conditions are derived for guaranteeing feasibility of a given periodic task set when a deferrable server is present. An analytic model is proposed for selecting the best feasible period and computation time of the server to minimize the mean response time of aperiodic tasks. An evaluation of the proposed model using a simulator indicates that the server parameters selected by the model result in mean response times that are close to the best mean response time determined by the simulator.     

An optimal algorithm for scheduling soft aperiodic tasks indynamic-priority preemptive systems

The paper addresses the problem of jointly scheduling tasks with both hard and soft real time constraints. We present a new analysis applicable to systems scheduled using a priority preemptive dispatcher, with priorities assigned dynamically according to the EDF policy. Further, we present a new efficient online algorithm (the acceptor algorithm) for servicing aperiodic work load. The acceptor transforms a soft aperiodic task into a hard one by assigning a deadline. Once transformed, aperiodic tasks are handled in exactly the same way as periodic tasks with hard deadlines. The proposed algorithm is shown to be optimal in terms of providing the shortest aperiodic response time among fixed and dynamic priority schedulers. It always guarantees the proper execution of periodic hard tasks. The approach is composed of two parts: an offline analysis and a run time scheduler. The offline algorithm runs in pseudopolynomial time O(mn), where n is the number of hard periodic tasks and m is the hyperperiod/min deadline     

Minimizing aperiodic response times in a firm real-time environment

In certain real-time applications, ranging from multimedia to telecommunication systems, timing constraints can be more flexible than scheduling theory usually permits. In this paper, we deal with the problem of scheduling hybrid sets of tasks, consisting of firm periodic tasks (i.e. tasks with deadlines which can occasionally skip one instance) and soft aperiodic requests, which have to be served as soon as possible to achieve good responsiveness. We propose and analyze an algorithm, based on a variant of earliest-deadline-first scheduling, which exploits skips to minimize the response time of aperiodic requests. One of the most interesting features of our algorithm is that it can easily be tuned to balance performance vs. complexity, for adapting it to different application requirements. Extensive simulation experiments show the effectiveness of the proposed approach with respect to existing methods. Schedulability bounds are also derived to perform off-line analysis     

长释放时间间隔优先的混合任务调度算法

针对混合任务实时调度的需求和MUF算法的局限性,提出了一种长释放时间间隔优先的混合任务实时调度算法LRIF,该算法除了可对周期性硬实时任务提供调度保证外,同时还可确保非周期性软实时任务的可调度率。论文还提出了LRIF调度算法的可调度性分析方法,并讨论了LRIF调度算法的实现方法。     

Improving responsiveness of soft aperiodic tasks using proportional slack time

In a real-time system with both hard real-time periodic jobs and soft real-time aperiodic jobs, it is important to guarantee that the deadline of each periodic job is met, as well as to provide a fast response time for each aperiodic job. We propose an algorithm, called Proportional Slack Reserve (PSR), that produces an efficient schedule for such an environment. For every execution unit of a periodic job, the PSR algorithm reserves time which can be used for execution of aperiodic jobs. If reserved time is not available, the algorithm assigns a deadline to an aperiodic job for achieving better responsiveness of aperiodic jobs. The proposed algorithm can fully utilize processing power while meeting all deadlines of periodic jobs. It can also easily reclaim the time unused by the periodic job. We analytically show that for each aperiodic job, the response time in a PSR schedule is no longer than that in a TBS schedule, which is known to be efficient for servicing aperiodic jobs. We also present simulation results in which the response time of PSR is significantly improved over that of TBS, and moreover the performance of PSR compares favorably with TB(N) considering scheduling overhead.     

硬实时环境下截止期缓冲区管理方法

针对硬实时环境的特点，提出了一种新的利用任务截止期来管理缓冲区的方法，前提是该环境下使用最早截止期优先的任务调度算法。该截止期缓冲区管理方法的主要特点是：在保证周期任务的缓冲区可用的同时，有效利用缓冲区资源，得到最佳的非周期实时任务缓冲区请求响应。详细讨论了该方法及其实现。