Deadline scheduling in the Linux kernel

During the last decade, there has been a considerable interest in using Linux in real‐time systems, especially for industrial control. The simple and elegant design of Linux guarantees reliability and very good performance, while its open‐source license allows to modify and change the source code according to the user needs. However, Linux has been designed to be a general‐purpose operating system. Therefore, it presents some issues like unpredictable latencies and limited support for real‐time scheduling. In this paper, we present our experience in the design and implementation of the real‐time scheduler that has been recently included in the Linux kernel. The scheduler is based on the Resource Reservation paradigm, which allows to enforce temporal isolation between the running tasks. We describe the genesis of the project, the challenges we have encountered, the implementation details and the API offered to the programmers. Then, we show the experimental results measured on a real hardware. Copyright © 2015 John Wiley & Sons, Ltd.     

基于Pfair的分布式实时调度策略Linux下实现

任务调度策略是嵌入式分布式实时系统关键问题之一,以Pfair公平调度为代表的全局调度技术是当前研究的热点,调度方法要在实际中得到应用,需要与具体的操作系统相结合.分析了分布式实时系统的调度理论,比较研究了几种Pfair算法,通过修改Linux内核的数据结构和调度函数,初步实现了Pfait的PD2算法,实验证明达到了预期的实验结果.     

Fault‐tolerant RT‐Mach (FT‐RT‐Mach) and an application to real‐time train control

Even though real‐time systems have the stringent constraint of completing tasks before their deadlines, many existing real‐time operating systems do not implement fault tolerance capabilities. In this paper we summarize fault tolerant real‐time scheduling policy for dynamic tasks with ready times and deadlines. Our focus in this paper is the implementation, which includes fault‐tolerant scheduling, re‐scheduling, and recovery mechanisms in the FT‐RT‐Mach operating system, a fault‐tolerant version of RT‐Mach. A real‐time train control application is then implemented using the FT‐RT‐Mach operating system. Copyright © 1999 John Wiley & Sons, Ltd.     

HARTEX—a safe real‐time kernel for distributed computer control systems

A hard real‐time kernel is presented for distributed computer control systems (DCCS), highlighting a number of novel features, such as integrated scheduling of hard and soft real‐time tasks as well as tasks and resources; high‐performance time management supporting safe DCCS operation in a hard real‐time environment; synchronization and communication featuring event notification via vector semaphores and transparent communication through implicit (content‐oriented) message addressing. Conventional queues have been substituted by Boolean vectors and vector processing techniques throughout the kernel, resulting in efficient and highly deterministic behaviour, which is characterized by very low overhead and constant execution time of kernel operations, independent of the number of tasks involved. Copyright © 2001 John Wiley & Sons, Ltd.     

RT—Mach：基于Mach的实时微内核

ＲＴ－Ｍａｃｈ是ＣＭＵ在原标准Ｍａｃｈ微内核之上开发的实时微内核，它的目标是提供一个公用的实时计算环境。与Ｍａｃｈ相比，ＲＴ－Ｍａｃｈ增加了实时线程模型、实时同步、实时调度、实时时钟和计时器，以及实时ＩＰＣ等新特点，本文将介绍ＲＴ－Ｍａｃｈ的这些新特点。     

基于RT-Linux的实时机器人控制器研究

本文结合机器人控制器的特点，提出了采用RT-Linux操作系统改进机器人控制实时性的方法，并对机器人控制器任务采用多线程机制进行实时域和非实时域的划分。最后给出了一个在RT-Linux操作系统下实现硬件设备实时驱动程序的实例。     

Linux实时调度方案的设计与实现

作为一个分时系统，Linux的设计目标为提高吞吐率和平均响应时间，因此采取了基于时间片的调度策略，显然这种机制无法保证实时任务得到及时响应和调度．为了改进Linux操作系统的实时性能，探讨了基于Linux的实时操作系统RFRTOS中的实时调度机制．实验验证，所做改进有效地提高了Linux的调度精度，满足了软实时方面的需求．     

嵌入式Linux操作系统实时性的分析与研究

通过分析嵌入式Linux在实时应用中的不足,从软中断模拟技术、可抢占式内核机制和实时调度策略等方面给出了改善系统实时性能的方法,同时提出了宏观调度结构,拓展了实时系统的应用范围。     

基于Linux的嵌入式工业测控系统

该文针对当前工业控制领域网络控制技术的快速发展，给出了一种应用于测控系统的基于Linux的嵌入式系统的设计方案。利用Linux自身提供的条件编译系统，初步解决了Linux作为嵌入式操作系统面临的一些问题。并利用实时应用接口（RTAI）来增强Linux的实时性，引入实时硬件抽象层结构（RTHAL），利用Linux的内核模块机制提供实时服务和完成实时任务，解决了LinuX实时性不足的问题。通过数据采集程序的实现给出了在RTAI-Linux环境下开发实时应用程序的设计方法。     

增强Linux内核实时任务调度性能的研究

分析基本Linux内核的调度策略,指出其应用于实时系统时存在的不足,提出了一种增强Linux内核调度性能的实时任务调度策略和调度算法。结合任务的关键性、截止期和执行时间三要素,该调度策略通过三运行队列代替原Linux内核的单运行队列,分别对应系统的硬实时、软实时和非实时任务,保证了硬实时任务的实时性;不同于简单的FIFO调度算法,该调度算法根据任务的最小松弛时间和重要性来确定其在当前运行队列中的优先级,仿真结果表明此算法提高了实时调度性能。     

一种基于时钟粒度细化的Linux实时化方案

时钟精度直接影响到任务能否被及时响应和调度，作为一个分时系统，Linux的10ms周期性时钟粒度是必要而且合适的．但是实时系统一般都要求微秒级的响应精度，显然Linux的时钟粒度过于粗糙．然而简单地提高时钟频率意味着时钟中断的相应处理过程将占用过多的处理器时间，从而使得整个系统的有效利用率急剧下降．为了改进Linux的实时性能，讨论了基于Linux的实时操作系统RFRTOS中的时钟粒度细化方案．实验结果显示所做改进以不大的代价有效地提高了Linux的时钟精度．     

REDUCING CONTROL LATENCY AND JITTER IN REAL‐TIME CONTROL

This paper analyses control computation latency and jitter, which have been largely ignored in the control community for real‐time (RT) control. The focus is on RT control systems with multiple control tasks running on a uniprocessor. Three strategies are proposed to reduce control latency and/or jitter: introduction of offsets into control task scheduling, decomposition of control tasks; and increasing the priority levels of output subtasks. Examples are given to demonstrate the effectiveness of the proposed methods.     

通用调度框架的改进及其在Linux中的实现

在嵌入式Linux实时系统中,要求内核对不同时问约束的任务采用不同的调度算法.但目前Linux内核采用单一的实时调度模式,不能灵活地执行多种调度算法,也就无法满足实时系统中实时任务的时间约束.引入了一种能够在Linux内核调度中执行多种调度算法的框架,即通用调度框架(GSF),并改进了其中的多算法调用机制,从而更好地在Linux内核中实现GSF.     

Design and analysis of target‐sensitive real‐time systems

A significant number of real‐time control applications include computational activities where the results have to be delivered at precise instants, rather than within a deadline. The performance of such systems significantly degrades if outputs are generated before or after the desired target time. This work presents a general methodology that can be used to design and analyze target‐sensitive applications in which the timing parameters of the computational activities are tightly coupled with the physical characteristics of the system to be controlled. For the sake of clarity, the proposed methodology is illustrated through a sample case study used to show how to derive and verify real‐time constraints from the mission requirements. Software implementation issues necessary to map the computational activities into tasks running on a real‐time kernel are also discussed to identify the kernel mechanisms necessary to enforce timing constraints and analyze the feasibility of the application. A set of experiments are finally presented with the purpose of validating the proposed methodology. Copyright © 2015 John Wiley & Sons, Ltd.     

机器人控制器核心设备的实时性研究

机器人控制器核心系统的实时性提高与改进是一个关键问题,结合机器人控制器的特点对操作系统平台的实时性进行分析,着重比较了Linux操作系统和改进的RTLinux实时操作系统在实时性上的区别,对机器人控制器任务采用多线程机制进行实时域和非实时域的重新划分,并提出一套实时性改造方案,完成机器人控制器的任务,最后给出了一个在RTLinux操作系统下实现硬件设备实时驱动程序的一个例子。     

嵌入式Linux中调度算法的实现及优化

本文论述实时嵌入式Linux的多任务调度算法实现机制。结合嵌入式操作系统的特点，重点介绍基于优先级驱动嵌入式系统的一种实时调度优化算法的实现机制，讨论如何在GPL下充分利用现有的实时调度算法开发适合嵌入式Linux的优化调度方法，并提出了具体的实现思路。     

Catching two rabbits: adaptive real‐time support for embedded Linux

The trend of digital convergence makes multitasking common in many digital electronic products. Some applications in those systems have inherent real‐time properties, while many others have few or no timeliness requirements. Therefore the embedded Linux kernels, which are widely used in those devices, provide real‐time features in many forms. However, providing real‐time scheduling usually induces throughput degradation in heavy multitasking due to the increased context switches. Usually the throughput degradation becomes a critical problem, since the performance of the embedded processors is generally limited for cost, design and energy efficiency reasons. This paper proposes schemes to lessen the throughput degradation, which is from real‐time scheduling, by suppressing unnecessary context switches and applying real‐time scheduling mechanisms only when it is necessary. Also the suggested schemes enable the complete priority inheritance protocol to prevent the well‐known priority inversion problem. We evaluated the effectiveness of our approach with open‐source benchmarks. By using the suggested schemes, the throughput is improved while the scheduling latency is kept same or better in comparison with the existing approaches. Copyright © 2008 John Wiley & Sons, Ltd.     

基于Linux的多核实时任务调度算法改进

嵌入式实时系统通常被实现为多任务系统,以满足多个外部输入的响应时间的最后期限约束。Linux内核中已经实现了基于EDF(Earliest Deadline First)调度算法的DL调度器,使得实时任务能在截止期限内运行完成。但对于多核处理器,由于实时任务在EDF算法下会出现Dhall效应,论文对 Linux内核中实时任务调度算法进行了改进。在EDF算法的基础上,实现LLF(Least Laxity First)调度算法并对其加以改进,通过降低任务上下文切换频率以及减少松弛度的计算来减小调度过程中的颠簸现象。实验证明该方法既避免了Dhall效应,又减少了任务上下文切换带来的系统开销,并使得任务能在截止期限内完成调度,取得了较好的调度性能。     

改善嵌入式Linux实时性能的方法研究

分析了Linux的实时性,针对其在实时应用中的技术障碍,在参考了与此相关研究基础上,从三方面提出了改善Linux实时性能的改进措施。为提高嵌入式应用响应时间精度,提出两种细化Linux时钟粒度方法;为增强系统内核对实时任务的响应能力,采用插入抢占点和修改内核法增强Linux内核的可抢占性;为保证硬实时任务的时限要求,把原Linux的单运行队列改为双运行队列,硬实时任务单独被放在一个队列中,并采用MLF调度算法代替原内核的FIFO调度算法。     

Improving responsiveness of time‐sensitive applications by exploiting dynamic task dependencies

In this paper, a mechanism is presented for reducing priority inversion in multiprogrammed computing systems. Contrary to well‐known approaches from the literature, this paper tackles cases where the dependency relationships among tasks cannot be known in advance to the operating system. The presented mechanism allows tasks to explicitly declare aforementioned relationships, enabling the operating system scheduler to take advantage of such information and trigger priority inheritance, resulting in reduced priority inversion. We present the prototype implementation of the concept within the Linux kernel in the form of modifications to the standard Portable Operating System Interface (POSIX) condition variable code, along with an extensive evaluation, including a quantitative assessment of the benefits for applications making use of the technique and comprehensive overhead measurements. In addition, we present an associated technique for the theoretical schedulability analysis of a system using the new mechanism, which is useful to determine whether all tasks can meet their deadlines or not, in the specific scenario of tasks interacting only through remote procedure calls and under partitioned scheduling.