Schedulability analysis and efficient scheduling of rate constrained messages in the TTEthernet protocol

Over time, cyber‐physical systems are becoming mixed criticality systems. As the complexity and the size of these systems grow, computation/communication resources should be more efficient than with traditional systems. TTEthernet is a communication infrastructure that enables the use of a single physical communication infrastructure for distributed mixed criticality applications while providing timely determinism. TTEthernet distinguishes between two traffic categories: the standard event triggered and the time triggered. The latter, for which higher priority is granted, is subject to strong timing guarantees because of strict periodicity constraint that fixes start‐time cycles of time‐triggered messages. In addition, event‐triggered traffic includes rate‐constrained messages that are of lower priority and have a minimum time interval between their transmission. The paper proposes both an on‐line efficient scheduling algorithm and a necessary and sufficient schedulability condition based on the worst case response time computation for rate‐constrained messages while taking into account time‐triggered messages transmission. Copyright © 2017 John Wiley & Sons, Ltd.     

多处理器混合关键性系统中的划分调度策略

多核处理器正越发广泛地应用到现代嵌入式系统的设计与实现当中,其强大的计算能力为将多个不同关键性级别的功能子系统集成到统一的共享资源平台提供了支持.混合关键性系统的调度问题即便在单处理器平台中都极具挑战性,在多处理器平台则更为困难.将目前资源利用率最高的单处理器混合关键性调度算法EY-VD扩展到多处理器平台中.首先,结合传统的划分调度策略提出了适用于多处理器混合关键性系统的MC-PEDF(mixedcriticality partitioned earliest deadline first)划分调度算法.尽管比之前的算法有更好的可调度性能,但传统的划分策略不能有效地平衡不同关键性级别下的负载,故其不完全适用于混合关键性系统.为了克服传统策略的不足,提出了划分调度策略OCOP(one criticality one partition).OCOP允许系统在关键性模式切换时对实时任务集进行重新划分,进而更好地平衡各个处理器在不同关键性模式中的资源利用率.基于OCOP,提出了第2种划分调度算法MC-MP-EDF(mixed-criticality multi-partitioned EDF).基于随机生成任务集的仿真实验结果表明,与MC-PEDF和已有的算法相比,MC-MP-EDF能够显著地提高系统的可调度性,尤其是在处理器数量较多的系统中.     

Data‐aware task scheduling on heterogeneous hybrid memory multiprocessor systems

In this paper, we propose a method about task scheduling and data assignment on heterogeneous hybrid memory multiprocessor systems for real‐time applications. In a heterogeneous hybrid memory multiprocessor system, an important problem is how to schedule real‐time application tasks to processors and assign data to hybrid memories. The hybrid memory consists of dynamic random access memory and solid state drives when considering the performance of solid state drives into the scheduling policy. To solve this problem, we propose two heuristic algorithms called improvement greedy algorithm and the data assignment according to the task scheduling algorithm, which generate a near‐optimal solution for real‐time applications in polynomial time. We evaluate the performance of our algorithms by comparing them with a greedy algorithm, which is commonly used to solve heterogeneous task scheduling problem. Based on our extensive simulation study, we observe that our algorithms exhibit excellent performance and demonstrate that considering data allocation in task scheduling is significant for saving energy. We conduct experiments on two heterogeneous multiprocessor systems. Copyright © 2016 John Wiley & Sons, Ltd.     

Effects of dynamic isolation for full virtualized RTOS and GPOS guests

Industrial systems currently include not only control processing with real-time operating system (RTOS) but also information processing with general-purpose operating system (GPOS). Multicore-based virtualization is an attractive option to provide consolidated environment when GPOS and RTOS are put in service on a single hardware platform. Researches on this technology have predominantly focused on the schedulability of RTOS virtual machines (VMs) by completely dedicated physical-CPUs (pCPUs) but have rarely considered parallelism or the throughput of the GPOS. However, it is also important that the multicore-based hypervisor adaptively selects pCPU assignment policy to efficiently manage resources in modern industrial systems. In this paper, we report our study on the effects of dynamic isolation when two mixed criticality systems are working on one platform. Based on our investigation of mutual interferences between RTOS VMs and GPOS VMs, we found explicit effects of dynamic isolation by special events. While maintaining low RTOS VMs scheduling latency, a hypervisor should manage pCPUs assignment by event-driven and threshold-based strategies to improve the throughput of GPOS VMs. Furthermore, we deal with implicit negative effects of dynamic isolation caused by the synchronization inside a GPOS VM, then propose a process of urgent boosting with dynamic isolation. All our methods are implemented in a real hypervisor, KVM. In experimental evaluation with benchmarks and an automotive digital cluster application, we analyzed that proposed dynamic isolation guarantees soft real-time operations for RTOS tasks while improving the throughput of GPOS tasks on a virtualized multicore system.     

Grasp: Visualizing the behavior of hierarchical multiprocessor real-time systems

Trace visualization is a viable approach for gaining insight into the behavior of complex distributed real-time systems. Grasp is a versatile trace visualization toolset. Its flexible plugin infrastructure allows for easy extension with custom visualization and analysis techniques for automatic trace verification. This paper presents its visualization capabilities for hierarchical multiprocessor systems, including partitioned and global multiprocessor scheduling with migrating tasks and jobs, communication between jobs via shared memory and message passing, and hierarchical scheduling in combination with multiprocessor scheduling. For tracing distributed systems with asynchronous local clocks Grasp also supports the synchronization of traces from different processors during the visualization and analysis.     

Robust adaptive tracking control of distributed delay systems with actuator and communication failures

This paper is concerned with the robust adaptive fault‐tolerant tracking control problem for a class of distributed delay systems against faulted and perturbed actuators and communications. As all the faults on actuators and communications, network delays in control and communication channels, and perturbations in communications and exogenous disturbances are unknown, some adaptation schemes are developed to adjust controller parameters in real‐time for constructing a class of distributed compensation controllers based on the delayed signals. Then, according to the information from the adaptive mechanism, the effect of each actuator and communication fault, network delay, channel perturbation and exogenous disturbance can be eliminated completely by using the proposed distributed adaptive‐state feedback controllers. Furthermore, asymptotic tracking results of the distributed closed‐loop systems can be achieved based on Lyapunov stability theory. An example is provided to further illustrate the effectiveness of the proposed direct adaptive design technique. Copyright © 2011 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

Taming Virtualization

Although the term virtualization has been around for decades, only recently has it become a buzzword in the computer systems community with the revival of virtual machines (VMs), driven by efforts in industry and academia. VMs are software entities that emulate a real machine's functionality; they execute under the control of a hypervisor that virtualizes and multiplexes low-level hardware resources. Hypervisors come in two flavors: non-hosted, which run directly on top of the hardware, and hosted, which are integrated with a host operating system (OS). The presence of a hypervisor makes VMs subject to a level of visibility and control that's hard to achieve with real machines. The small size, isolation, and mediation power of an ideal hypervisor over VMs make it an interesting candidate for a trusted computing base, with applications in security research fields such as intrusion detection, integrity protection, and malware analysis, among others.     

Partitioning and mapping nested loops on multiprocessor systems

A method for executing nested loops with constant loop-carried dependencies in parallel on message-passing multiprocessor systems to reduce communication overhead is presented. In the partitioning phase, the nested loop is divided into blocks that reduce the interblock communication, without regard to the machine topology. The execution ordering of the iterations is defined by a given time function based on L. Lamport's (1974) hyperplane method. The iterations are then partitioned into blocks so that the execution ordering is not disturbed, and the amount of interblock communication is minimized. In the mapping phase, the partitioned blocks are mapped onto a fixed-size multiprocessor system in such a manner that the blocks that have to exchange data frequently are allocated to the same processor or neighboring processors. A heuristic mapping algorithm for hypercube machines is proposed     

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.     

多核系统中基于动态电压频率调节的实时节能调度研究

在实时嵌入式领域,特别是无线移动和便携式计算领域,能耗是首要考虑的因素,这也是多核处理器尚未在嵌入式领域全面展开应用的首要因素。目前针对多核系统的实时应用,基于动态电压频率调节(DVFS)的实时节能调度技术研究得较少,还有许多问题亟待解决。本文介绍了多核系统中动态电压频率调节技术,分析讨论了当前多核系统中实时调度研究进展,主要针对同构多核、异构多核、并行任务模型和弱硬实时模型等方面,深入探讨了多核系统中基于DVFS的实时节能调度。本文结合多核系统、电压频率动态调节节能和实时调度,探索了多核系统中的实时节能调度,奠定了理论和技术基础,具有重大的理论意义和现实应用价值。     

Trends in multiprocessor and distributed operating systems designs

This paper presents an overview of the developments in operating systems technology for distributed computing systems and multiprocessor machines. We focus on those design principles that are now widely accepted as useful design paradigms. Approaches common to distributed and multiprocessor operating systems are identified. Issues discussed include process scheduling and synchronization, load balancing, virtual and shared-memory management and parallel file systems. The task-thread model and the object model of computing are also discussed.     

Partitioned EDF scheduling on a few types of unrelated multiprocessors

A polynomial-time approximation scheme (PTAS) is derived for the partitioned EDF scheduling of implicit-deadline sporadic task systems upon unrelated multiprocessor platforms that are comprised of a constant number of distinct types of processors. This generalizes earlier results showing the existence of polynomial-time approximation schemes for the partitioned EDF scheduling of implicit-deadline sporadic task systems on (1) identical multiprocessor platforms, and (2) unrelated multiprocessor platforms containing a constant number of processors.     

RT-Hypervisor:用于实时嵌入式系统的虚拟机监视器

很多嵌入式系统应用系统,都需要把一个实时系统和一个非实时系统安装在同一个嵌入式设备上,让它们一起工作,发挥各自的优势.论述了RT-Hypervisor实时虚拟机监控程序的设计和实现,利用它可以在一个硬件设备上同时运行多个实时或是非实时操作系统.RT-Hypervisor是一个高效的实时虚拟化软件平台,它主要由操作系统域、CPU调度、操作系统域间通讯和虚拟中断控制器等模块组成.通过一些简单地移植操作,大部分嵌入式操作系统都可以高效地运行在RT-Hypervisor上.     

CORBA and MPI code coupling

Coupling of application programs designed for multiprocessor computing systems requires simultaneous use of several paradigms implemented as communication middleware. In this paper, we propose a method of integration of MPI, which is widely used in scientific parallel computations, and CORBA, which is designed for the development of object-oriented applications. This makes it possible to assemble integrated software systems for interdisciplinary computations on heterogeneous multiprocessor systems with the reuse of available application software. An example of inclusion of an MPI linear algebra package into a CORBA-based distributed object-oriented model for solving systems of equations is presented.     

Embedded simulation on a multiprocessor job scheduling system with inspection

This paper first develops architecture for a multiprocessor job scheduling system with an embedded simulation technique. The architecture provides a shell for applications that are characterized by two scheduling policies, a heuristic algorithm policy and a First-In-First-Out (FIFO) policy. These policies are implemented in the simulation model by using the embedded technique. The paper evaluates these two policies using the queue length, waiting time and flow time as the criteria to compare the performance of these two scheduling policies. Next we designed two simulation situations using two different real world applications. The purpose is to examine the performances of multiprocessor systems with and without inspection operations and two different scheduling policies. The two applications, berth allocation for the container terminal operations and production scheduling arrangement in an Original Equipment Manufacturer (OEM) power supply factory, are studied. The final results show that a proper scheduling policy will perform better than the traditional FIFO approach for a multiprocessor system. Our study also provides guidelines on balancing a system with the addition of a final inspection activity.     

A novel adaptive robust control architecture for bilateral teleoperation systems under time‐varying delays

Bilateral teleoperation technology has caused wide attentions due to its applications in various remote operation systems. The communication delay becomes one of the main challenging issues in the teleoperation control design. Meanwhile, various nonlinearities, parameter variations, and modeling uncertainties existing in manipulator and environment dynamics need to be considered carefully in order to achieve good control performance. In this paper, a globally stable nonlinear adaptive robust control algorithm is developed for bilateral teleoperation systems to deal with these control issues. Namely, the unknown dynamical parameters of the environmental force are estimated online by the improved least square adaptation law. A novel communication structure is proposed where only the master position signal is transmitted to the slave side for the tracking design, and the online estimators of the environmental parameters are transmitted from the slave to the master to replace the traditional environmental force measurement. Because the estimated environmental parameters are not power signals, the passivity problem of the communication channel and the trade‐off limitation between the transparency performance and robust stability in traditional teleoperation control are essentially avoided. The nonlinear adaptive robust control is subsequently developed to deal with nonlinearities, unknown parameters, and modeling uncertainties of the master, slave, and environmental dynamics, so that the guaranteed transient and steady‐state transparency performance can be achieved. The experiments on two voice‐coil motor‐driven manipulators are carried out, and the comparative results verify that the proposed control algorithm achieves the excellent control performance and the guaranteed robust stability simultaneously under time delays. Copyright © 2014 John Wiley & Sons, Ltd.     

Simulation of resource synchronization in a dynamic real‐time distributed computing environment

Today, more and more distributed computer applications are being modeled and constructed using real‐time principles and concepts. In 1989, the Object Management Group (OMG) formed a Real‐Time Special Interest Group (RT SIG) with the goal of extending the Common Object Request Broker Architecture (CORBA) standard to include real‐time specifications. This group's most recent efforts have focused on the requirements of dynamic distributed real‐time systems. One open problem in this area is resource access synchronization for tasks employing dynamic priority scheduling. This paper presents two resource synchronization protocols that the authors have developed which meet the requirements of dynamic distributed real‐time systems as specified by Dynamic Scheduling Real‐Time CORBA (DSRT CORBA). The proposed protocols can be applied to both Earliest Deadline First (EDF) and Least Laxity First (LLF) dynamic scheduling algorithms, allow distributed nested critical sections, and avoid unnecessary runtime overhead. In order to evaluate the performance of the proposed protocols, we analyzed each protocol's schedulability. Since the schedulability of the system is affected by numerous system configuration parameters, we have designed simulation experiments to isolate and illustrate the impact of each individual system parameter. Simulation experiments show the proposed protocols have better performance than one would realize by applying a schema that utilizes dynamic priority ceiling update. Copyright © 2004 John Wiley & Sons, Ltd.     

Guidelines for supporting real‐time multi‐touch applications

Multi‐touch driven user interfaces are becoming increasingly prevalent because of their intuitiveness and because of the reduction in the associated hardware costs. In recognition of this trend, multi‐touch software frameworks (MSFs) have begun to emerge. These frameworks abstract the low level issues of multi‐touch software development and deployment. MSFs therefore enable software developers who are unfamiliar with the complexities of multi‐touch software development to implement and deploy multi‐touch applications more easily. However, some multi‐touch applications have real‐time system requirements, and at present, no MSFs provide support for the development and deployment of such real‐time multi‐touch applications. The implication of this is that software developers are unable to take advantage of MSFs and, therefore, are forced to handle the complexities of multi‐touch and real‐time systems development and deployment for themselves in an ad hoc manner. The primary consequence of this is that the multi‐touch and/or real‐time aspects of the application may not function correctly. In this paper, guidelines are presented for applying real‐time system concepts to support the development and deployment of real‐time multi‐touch applications using MSFs. This serves to increase the probability that the application will meet its timing requirements while also reducing the complexity of the development and deployment process associated with multi‐touch applications. Copyright © 2013 John Wiley & Sons, Ltd.     

Cluster-based multicore real-time mixed-criticality scheduling

Cluster-based scheduling is recently gaining importance to be applied to mixed-criticality real-time systems on multicore processors platform. In this approach, the cores are grouped into clusters, and tasks that are partitioned among different clusters are scheduled by global scheduler in each cluster. This research work introduces a new cluster-based task allocation scheme for the mixed-criticality real-time task sets on multicore processors. For task allocation, smaller clusters sizes (sub-clusters) are used for mixed-criticality tasks in low criticality mode, while relatively larger cluster sizes are used for high criticality tasks in high criticality mode. In this research paper, the mixed-criticality task set is allocated to clusters using worst-fit heuristic. The tasks from each cluster are also allocated to its sub-clusters, using the same worst-fit heuristic. A fixed-priority response time analysis approach based on Audsley’s approach is used for the schedulability analysis of tasks in each cluster and sub-cluster. If the high criticality job is not completed after its worst case execution time in low mode, then the system is switched to high criticality mode. After mode switch, all the low criticalities tasks are discarded and only high criticality tasks are further executed in high criticality mode. Simulation results indicate that the percentage of schedulable task sets significantly increases under cluster scheduling as compared to partitioned and global mixed-criticality scheduling schemes.     

Distributed control of LPV systems over arbitrary graphs with communication latency

This paper focuses on spatially distributed control systems where the controller sensing and actuation topology is inherited from that of the plant. Specifically, this paper considers distributed systems composed of discrete‐time linear parameter‐varying subsystems interconnected over general graph structures. These distributed systems are subject to a communication latency of one sampling period, where the information sent by a subsystem at the current time step is received by the target subsystem at the next time step. Analysis and synthesis conditions are derived for control design in this setting using a parameter‐dependent Lyapunov approach with the ?₂‐induced norm as the performance measure. Fast and easy‐to‐implement algorithms are also provided for constructing the controller in real time. The techniques developed are finally applied to a leader‐follower formation problem with intermittent communications.