Reliability analysis of real-time fault-tolerant task models

One notable advantage of Model-Driven Architecture (MDA) method is that software developers could do sufficient analysis and tests on software models in the design phase, which helps construct high confidence on the expected software behaviors and performance, especially for safety-critical real-time software. Most existing literature of reliability analysis ignores the effects from those deadline requirements of tasks which are critical properties for real-time software and thus cannot be ignored. Considering the contradictory relationship between the deadline requirements and time costs of fault tolerance in real-time tasks, in this paper, we present a novel reliability model, which takes schedulability as one of the major factors affecting the reliability, to analyze reliability of the task execution model in real-time software design phase. The tasks in this reliability model has no restrictions on their distributions and thus could be distributed on a multiprocessor or on a distributed system. Furthermore, the tasks also define arrival rates of faults and fault-tolerant mechanisms to model the occurrences of non-permanent faults and the corresponding time costs of fault handling. By analyzing the probability of tasks still being schedulable in the worst-case execution scenario with faults occurring, reliability and schedulability are combined into an unified analysis framework, and two algorithms for reliability analysis are given. To make this reliability model more pragmatic, we also present an estimation technique for estimating the fault arrival rate of each task. We show through two case studies respectively the detailed derivation process under static-priority scheduling in a multiprocessor system and in the design process of avionics software, and then analyze the factors affecting the reliability analysis by setting up simulation experiments. When no assumptions of fault occurrences made on the task model, this reliability model regresses to a generic schedulability model.     

On the Consolidation of Mixed Criticalities Applications on Multicore Architectures

In this paper we propose a hybrid solution to ensure results correctness when deploying several applications with different safety requirements on a single multi-core-based system. The proposed solution is based on lightweight hardware redundancy, implemented using smart watchdogs and voter logic, combined with software redundancy. Two techniques of software redundancy are used: the first one is software temporal triple modular redundancy, used for those tasks with low criticality and no real-time requirement. The second software redundancy technique is triple module redundancy for tasks with high criticality and real-time requirements, assisted by a hardware voter. A hypervisor is used to separate each task in the system in an independent resource partition, thus ensuring that no functional interference is occurring. The proposed solution has been evaluated through hardware and software fault injection on two hardware platforms, featuring a dual-core processor and a quad-core processor respectively. Results show a high fault tolerance achieved using the proposed architecture.     

多功能相控阵雷达实时任务调度研究

针对多功能相控阵雷达资源调度问题,建立了合理的雷达任务模型并提出一种新的调度算法.在雷达任务模型中将每一类驻留请求合并为一种任务,这样可以为调度处理提供最大的灵活性,同时基于此任务模型分析了调度器的时间负载.所提出的调度算法综合考虑了任务的工作方式优先级和截止期两个参数,可以较好地适应不同的负载情况.给出了算法的具体实现步骤,并以截止期错失率作为评估指标进行了仿真验证.仿真结果表明,本文所提出的调度算法能够有效降低任务的截止期错失率,对调度性能有明显的改善.     

分布式开放实时系统调度策略研究

为有效管理分布式开放实时系统(Distributed Open Real-Time System,DORTS)的CPU和网络资源,提供实时应用端到端延时确保,提出一种基于资源预留的分层调度策略.对于任务的调度,首先利用最大需求任务优先与最小可利用率节点适应算法将任务分配到各节点,然后在节点上采用基于服务器的两层调度架构...     

遗传算法在硬实时系统预调度中的应用

针对硬实时系统的特性,改进了遗传算法的初始群体生成方法及交换变异算子。实现了硬实时系统任务预调度。对给出的任务集合找出了最佳调度序列。通过测试集合仿真,效果良好。     

Synthesis of Hard Real-Time Application Specific Systems

This paper presents a system level approach for the synthesis of hard real-time multitask application specific systems. The algorithm takes into account task precedence constraints among multiple hard real-time tasks and targets a multiprocessor system consisting of a set of heterogeneous off-the-shelf processors. The optimization goal is to select a minimal cost multi-subset of processors while satisfying all the required timing and precedence constraints. There are three design phases: resource allocation, assignment, and scheduling. Since the resource allocation is a search for a minimal cost multi-subset of processors, we adopted an A* search based technique for the first synthesis phase. A variation of the force-directed optimization technique is used to assign a task to an allocated processor. The final scheduling of a hard-real time task is done by the task level scheduler which is based on Earliest Deadline First (EDF) scheduling policy. Our task level scheduler incorporates force-directed scheduling methodology to address the situations where EDF is not optimal. The experimental results on a variety of examples show that the approach is highly effective and efficient.     

An optimal checkpointing-strategy for real-time control systemsunder transient faults

Real-time computer systems are often used in harsh environments, such as aerospace, and in industry. Such systems are subject to many transient faults while in operation. Checkpointing enables a reduction in the recovery time from a transient fault by saving intermediate states of a task in a reliable storage facility, and then, on detection of a fault, restoring from a previously stored state. The interval between checkpoints affects the execution time of the task. Whereas inserting more checkpoints and reducing the interval between them reduces the reprocessing time after faults, checkpoints have associated execution costs, and inserting extra checkpoints increases the overall task execution time. Thus, a trade-off between the reprocessing time and the checkpointing overhead leads to an optimal checkpoint placement strategy that optimizes certain performance measures. Real-time control systems are characterized by a timely, and correct, execution of iterative tasks within deadlines. The reliability is the probability that a system functions according to its specification over a period of time. This paper reports on the reliability of a checkpointed real-time control system, where any errors are detected at the checkpointing time. The reliability is used as a performance measure to find the optimal checkpointing strategy. For a single-task control system, the reliability equation over a mission time is derived using the Markov model. Detecting errors at the checkpointing time makes reliability jitter with the number of checkpoints. This forces the need to apply other search algorithms to find the optimal number of checkpoints. By considering the properties of the reliability jittering, a simple algorithm is provided to find the optimal checkpoints effectively. Finally, the reliability model is extended to include multiple tasks by a task allocation algorithm     

Application-directed voltage scaling

Clock (and voltage) scheduling is an important technique to reduce the energy consumption of processors that support voltage scaling. It is difficult, however, to achieve good results using only statistics from the operating system level when applications show bursty (unpredictable) behavior. We take the approach that such applications must be made power-aware and specify their average execution time (AET) and the deadline to the scheduler controlling the clock speed and processor voltage. This paper describes our energy priority scheduling (EPS) algorithm supporting power-aware applications. EPS orders tasks according to how tight their deadlines are and how often tasks overlap. Low-priority tasks are scheduled first, since they can be easily preempted to accommodate for high-priority tasks later. The EPS algorithm does not always yield the optimal schedule, but has a low complexity. We have implemented EPS on a StrongARM-based variable-voltage platform. We conducted experiments with a modified video decoder that estimates the AET of each frame. Measurements show that application-directed voltage scaling reduces processor power consumption with 50% for the bursty video decoder without missing any frame deadlines.     

A Cooperative Management Scheme for Power Efficient Implementations of Real-Time Operating Systems on Soft Processors

A cooperative management scheme for power efficient implementations of real-time operating systems on field-programmable gate-array (FPGA)-based soft processors is presented. Dedicated power management hardware peripherals are tightly coupled to a soft processor by utilizing its configurability. These hardware peripherals manage tasks and interrupts in cooperation with the soft processor, while retaining the real-time responsiveness of the operating system. More specifically, the hardware peripherals perform the following power management functionalities: (1) control the on-chip clock distribution network for driving the soft processor, its hardware peripherals, and the bus interfaces between them; (2) perform task and interrupt management responsibilities of the operating system when the soft processor is turned off; and (3) selectively wake up the soft processor and its hardware components, and put them into proper activation states based on the hardware resource requirements of the tasks under execution. The implementations of two popular real-time operating systems on a state-of-the-art FPGA device are presented. Measurements on an experimental board show that the proposed power management scheme can lead to significant power savings.     

Real-time multimedia processing in video sensor networks

Video sensor networks (VSNs) has become the recent research focus due to the rich information it provides to address various data-hungry applications. However, VSN implementations face stringent constraints of limited communication bandwidth, processing capability, and power supply. In-network processing has been proposed as efficient means to address these problems. The key component of in-network processing, task mapping and scheduling problem, is investigated in this paper. Although task mapping and scheduling in wired networks of processors has been extensively studied, their application to VSNs remains largely unexplored. Existing algorithms cannot be directly implemented in VSNs due to limited resource availability and shared wireless communication medium. In this work, an application-independent task mapping and scheduling solution in multi-hop VSNs is presented that provides real-time guarantees to process video feeds. The processed data is smaller in volume which further releases the burden on the end-to-end communication. Using a novel multi-hop channel model and a communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously with a dynamic critical-path scheduling algorithm. Dynamic voltage scaling (DVS) mechanism is implemented to further optimize energy consumption. According to the simulation results, the proposed solution outperforms existing mechanisms in terms of guaranteeing application deadlines with minimum energy consumption.     

RTAI实时调度算法及其调度器的改进

在实时系统中,任务调度策略是内核设计的关键部分.如何进行实时的任务调度,使任务能在特定的周期内完成是实时操作系统领域研究的一个热点问题.文中将一种基于RM算法的改进算法CPSS算法引入到RTAI调度器中,针对RTAI调度器在系统过载情况下出现调度性能下降等缺点,对RTAI调度器进行优化和改进.对改进后的调度器在调度时延方面和调度算法仿真方面进行了测试,实验证明了改进后的调度器能够提高Linux系统的实时性.     

基于优先级降低策略的回卷恢复容错实时调度算法研究

实时系统中任务的超时完成将会导致灾难性后果,因此实时系统必须具备实时性和可靠性保障。为了提升系统的容错能力,该文基于回卷恢复容错模型,提出了容错优先级降低策略,并基于此策略对系统进行可调度性分析,推导出了任务最坏响应时间的计算公式。为了快速确定一组最优的容错优先级降低配置,该文提出了一种有效的搜索算法,该算法能够将容错优先级降低配置的搜索空间由O(n!)降低为O(n2)。最后,仿真实验表明容错优先级降低策略可以显著提升系统的容错能力。     

基于Android操作系统的实时系统监控研究Research for real-time system monitor based on Android system 石鑫, 夏青

针对大多数监控系统对实时性,稳定性,可操作性等要求,在Android嵌入式操作系统中,集成传感网模块,设计普通、紧急监控模块,剖析Android内核调度器工作原理等方法,提出了一种新的嵌入式实时监控系统。以体域网系统监控为平台进行测试,结果表明,该方案满足对网络监控实时性,可靠性的要求,方法具有良好的扩展性,利于向智能家居、物联网等领域中推广。     

Cross-Layer Collaborative In-Network Processing in Multihop Wireless Sensor Networks

Emerging wireless sensor network (WSN) applications demand considerable computation capacity for in-network processing. To achieve the required processing capacity, cross-layer collaborative in-network processing among sensors emerges as a promising solution: sensors do not only process information at the application layer, but also synchronize their communication activities to exchange partially processed data for parallel processing. However, scheduling computation and communication events is a challenging problem in WSNs due to limited resource availability and shared communication medium. In this work, an application-independent task mapping and scheduling solution in multihop homogeneous WSNs, multihop task mapping and scheduling (MTMS), is presented that provides real-time guarantees. Using our proposed application model, the multihop channel model, and the communication scheduling algorithm, computation tasks and associated communication events are scheduled simultaneously. The dynamic voltage scaling (DVS) algorithm is presented to further optimize energy consumption. Simulation results show significant performance improvements compared with existing mechanisms in terms of minimizing energy consumption subject to delay constraints     

A novel scheduling scheme for multiple traffic classes

In this paper, a novel scheduling scheme is proposed for multiple traffic classes to exploit multiuser diversity of the non-real-time (NRT) traffic. The proposed scheduling algorithm consists of two stages, i.e. at the first scheduling stage, the inter-traffic scheduler dynamically allocates the bandwidth resources to each traffic class by a periodic and triggered way with the objective of maximizing a room for NRT traffic while guaranteeing the quality of service (QoS) requirements of real-time (RT) traffics; at the second scheduling stage, the intra-traffic scheduler is used to schedule different users' packets within each traffic class simultaneously. The proposed algorithm not only enhances the system throughput but also satisfies the QoS requirements of RT traffic. Simulation results validate the effectiveness and good performance of the proposed scheme.     

分层异构信号处理平台调度方法研究

异构多处理器的高效性和可靠性能够满足日趋复杂的信号处理任务需求,因此分层异构系统已成为信号处理平台的发展趋势.为提高平台强实时性并解决高吞吐量的问题,文中对分层异构信号处理平台的软硬件模块及架构进行了研究,并采用有向无环图对组件任务及硬件资源进行建模.将已提出的调度算法按照任务类型、调度目标、调度过程和研究方法进行分类...     

Secure and reliable computation offloading in blockchain-assisted cyber-physical IoT systems

With the development of the Cyber-Physical Internet of Things System (CPIoTS), the number of Cyber-Physical System (CPS) applications accessed in networks has increased dramatically. Latency-sensitive resource orchestration in CPS applications is extraordinarily essential for maintaining the Quality of Experience (QoE) for users. Although edge-cloud computing performs effectively in achieving latency-aware resource allocation in CPIoTS, existing methods fail to jointly consider the security and reliability requirements, thereby increasing the process latency of tasks and degrading the QoE of users. This paper aims to minimize the system latency of edge-cloud computing coupled with CPS while simultaneously considering the security and reliability requirements. We first consider a time-varying channel model as a Finite-State Markov Channel (FSMC) and propose a distributed blockchain-assisted CPIoTS to realize secure consensus and reliable resource orchestration by offloading computation tasks in edge-cloud computing. Moreover, we propose an efficient resource allocation algorithm, PPO-SRRA, that optimizes computing offloading and multi-dimension resource (e.g., communication, computation, and consensus resource) allocation by using a policy-based Deep Reinforcement Learning (DRL) method. The experimental results show that the proposed resource allocation scheme can reduce the system latency and ensure consensus security.     

A hierarchical fair service curve algorithm for link-sharing,real-time, and priority services

We study hierarchical resource management models and algorithms that support both link-sharing and guaranteed real-time services with priority (decoupled delay and bandwidth allocation). We extend the service curve based quality of service (QoS) model, which defines both delay and bandwidth requirements of a class in a hierarchy, to include fairness, which is important for the integration of real-time and hierarchical link-sharing services. The resulting fair service curve (FSC) link-sharing model formalizes the goals of link-sharing, real-time and priority services and exposes the fundamental trade-offs between these goals. In particular, with decoupled delay and bandwidth allocation, it is impossible to simultaneously provide guaranteed real-time service and achieve perfect link-sharing. We propose a novel scheduling algorithm called hierarchical fair service curve (H-FSC) that approximates the model closely and efficiently. The algorithm always guarantees the service curves of leaf classes, thus ensures real-time and priority services, while trying to minimize the discrepancy between the actual services provided to and the services defined by the FSC link-sharing model for the interior classes. We have implemented the H-FSC scheduler in NetBSD. By performing analyzes, simulations and measurement experiments, we evaluate the link-sharing and real-time performances of H-FSC, and determine the computation overhead     

Downlink scheduling of multiuser MIMO systems with transmit beamforming

This article deals with downlink scheduling for multiuser multiple-input multiple-output （MIMO） systems, where the base station communicates with multiple users simultaneously through transmit beamforming. Most of the existing transmission schemes for multiuser MIMO systems focus on optimizing sum rate performance of the system. The individual quality of service （QoS） requirements （such as packet delay and minimum transmission rate for the data traffic） are rarely considered. In this article, a novel scheduling strategy is proposed, where we try to optimize the global system performance under individual QoS constraints. By performing scheduling into two steps, namely successive user selection and power allocation, the scheduler can achieve efficient resource utilization while maintaining the QoS requirements of all users. Extensive simulations and analysis are given to show the effectiveness of the proposed scheduler.     

设备级OS中任务调度的IO抖动优化策略

 为了减小任务调度产生的抖动对设备级操作系统的稳定性和可靠性的影响,提出了一种带有抢占阈值的任务分割模型RJPS.根据抢占阈值对任务调度的抖动与延迟的影响及该模型下任务可调度性的分析,分别设计了基于固定优先级调度和动态优先级调度策略的最小阈值分配算法.仿真结果表明,该模型可以在保证任务集可调度的前提下明显减少任务的IO抖动.