Multiprocessor platform for partitioned real‐time systems

Two current trends in the real‐time and embedded systems are the multiprocessor architectures and the partitioning technology that enables several isolated applications with different criticality levels to share the same computer. This paper presents a real‐time platform for multiprocessor and partitioned systems, in which communication requirements are also considered. The paper describes the adaptation of MaRTE OS (a monoprocessor real‐time operating system) to the XtratuM hypervisor for the multiprocessor Intel x86 architecture. This adaptation makes two contributions to ease the development process of future mixed‐criticality applications: firstly, it integrates the hypervisor technology and the fully partitioned scheduling in a multiprocessor environment, and secondly, it provides the basis to interconnect partitioned and non‐partitioned applications via a homogeneous communication subsystem. Copyright © 2016 John Wiley & Sons, Ltd.     

嵌入式操作系统混合任务调度技术与策略研究

针对当前嵌入式系统中时间触发与事件触发混合任务的特点,以μC/OS-II操作系统架构为基础,设计了一种能够同时支持时间触发与事件触发的混合操作系统内核架构。该架构符合OSEK/VDX标准,具有良好的可移植性。针对混合任务调度问题,提出了一种静态周期性可抢占式混合任务调度策略,该策略同时支持中断级与任务级的任务切换,并采用EDF（最早截止时间优先）算法对被抢占的时间触发任务进行恢复,相比OSEKtime OS只能在中断级进行任务切换以及FIFO（先进先出）恢复算法,能够提高系统资源利用率,并最大限度保证任务实时性。实验分析结果表明,所设计的混合操作系统架构移植方便,所提出的混合任务调度策略可行有效,调度过程具有良好的可预测性。     

基于PBS的集群作业调度策略的设计与实现

调度策略是作业管理系统的关键内容，首先介绍了OpenPBS体系结构及工作原理，提出了OpenPBS中默认调度器FIFO存在的问题，然后通过分析通常的调度策略和影响调度决策的主要元素，设计和实现了多分区装填策略，最终根据模拟实验结果，分析了该策略的性能改进。     

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.     

多机多任务实时系统云调度策略

采用云方法对多要实时系统任务的重要性和任务处理的适时性进行分析,实时计算被激活任务的价值及其在不同资源条件下的作业执行时间,提出一种兼顾任务价值和作业执行时间两方面因素的新的调度策略－云调度策略,有效地解决了任务优先级的判定和任务处理适时性问题,提高了系统资源利用效率、运行质量和系统整体效能。仿真证明,此策略优于现在广泛采用的固定优先级和先到先处理调度策略。     

嵌入式Forth虚拟机架构的多任务调度算法设计与实现

针对嵌入式应用领域对操作系统在重构、扩展、移植、交互、安全、高效等方面日趋苛刻的现实需求及Forth系统所固有的特性,采用Forth虚拟机技术,对基于Forth虚拟机架构的嵌入式操作系统关键技术进行探索,提出一种具有良好扩展和移植特性、高效精简的基于Forth虚拟机架构的嵌入式多任务操作系统调度算法。该算法采用了以Forth虚拟机指令同步的协同式多任务调度机制,缩短了任务切换时间,将上下文切换操作简化为只需保存数据堆栈指针。实验结果表明,基于Forth虚拟机架构的多任务调度算法发挥了Forth系统所固有的特性,针对特定应用,提高了效率,适合资源有限的嵌入式环境。     

Hierarchical Scheduling for Symmetric Multiprocessors

Hierarchical scheduling has been proposed as a scheduling technique to achieve aggregate resource partitioning among related groups of threads and applications in uniprocessor and packet scheduling environments. Existing hierarchical schedulers are not easily extensible to multiprocessor environments because 1) they do not incorporate the inherent parallelism of a multiprocessor system while resource partitioning and 2) they can result in unbounded unfairness or starvation if applied to a multiprocessor system in a naive manner. In this paper, we present hierarchical multiprocessor scheduling (H-SMP), a novel hierarchical CPU scheduling algorithm designed for a symmetric multiprocessor (SMP) platform. The novelty of this algorithm lies in its combination of space and time multiplexing to achieve the desired bandwidth partition among the nodes of the hierarchical scheduling tree. This algorithm is also characterized by its ability to incorporate existing proportional-share algorithms as auxiliary schedulers to achieve efficient hierarchical CPU partitioning. In addition, we present a generalized weight feasibility constraint that specifies the limit on the achievable CPU bandwidth partitioning in a multiprocessor hierarchical framework and propose a hierarchical weight readjustment algorithm designed to transparently satisfy this feasibility constraint. We evaluate the properties of H-SMP using hierarchical surplus fair scheduling (H-SFS), an instantiation of H-SMP that employs surplus fair scheduling (SFS) as an auxiliary algorithm. This evaluation is carried out through a simulation study that shows that H-SFS provides better fairness properties in multiprocessor environments as compared to existing algorithms and their naive extensions.     

Hybrid power management in real time embedded systems: an interplay of DVFS and DPM techniques

Energy-aware scheduling of real time applications over multiprocessor systems is considered in this paper. Early research reports that while various energy-saving policies, for instance Dynamic Power Management (DPM) and Dynamic Voltage & Frequency scaling (DVFS) policies, perform well individually for a specific set of operating conditions, they often outperform each other under different workload and/or architecture configuration. Thus, no single policy fits perfectly all operating conditions. Instead of designing new policies for specific operating conditions, this paper proposes a generic power/energy management scheme that takes a set of well-known existing (DPM and DVFS) policies, each of which performs well for a set of conditions, and adapts at runtime to the best-performing policy for any given workload. Experiments are performed using state-of the-art DPM and DVFS policies and the results show that our proposed scheme adapts well to the changing workload and always achieves overall energy savings comparable to that of best-performing policy at any point in time.     

Adaptive data-aware utility-based scheduling in resource-constrained systems

This paper addresses the problem of the dynamic scheduling of data-intensive multiprocessor jobs. Each job requires some number of CPUs and some amount of data that needs to be downloaded into a local storage. The completion of each job brings some benefit (utility) to the system, and the goal is to find the optimal scheduling policy that maximizes the average utility per unit of time obtained from all completed jobs. A co-evolutionary solution methodology is proposed, where the utility-based policies for managing local storage and for scheduling jobs onto the available CPUs mutually affect each other’s environments, with both policies being adaptively tuned using the Reinforcement Learning (RL) methodology. The simulation results demonstrate that the performance of the scheduling policies increases significantly as a result of being tuned with RL, to the point that they significantly outperform the best scheduling algorithm suggested in the literature for jobs with soft-deadline utility functions.     

Fast heuristic scheduling based on neural networks for real-time systems

As most of the real-time scheduling problems are known as hard problems, approximate or heuristic scheduling approaches are extremely required for solving these problems. This paper presents a new heuristic scheduling approach based on a modified Hopfield-Tank neural network to schedule tasks with deadlines and resource requirements in a multiprocessor system. In this approach, fast heuristic scheduling is achieved by performing a heuristic scheduling policy in conjunction with backtracking on the neural network. The results from our previous work, using the same neural network architecture without backtracking, are included here as a case with zero backtracking. Extensive simulation, which includes comparison with the conventional heuristic approach, is used to validate the effectiveness of our approach.     

Semaphore queue priority assignment for real-time multiprocessorsynchronization

Prior work on real time scheduling with global shared resources in multiprocessor systems assigns as much blocking as possible to the lowest priority tasks. We show that better schedulability can be achieved if global blocking is distributed according to the blocking tolerance of tasks rather than their execution priorities. We describe an algorithm that assigns global semaphore queue priorities according to blocking tolerance, and we present simulation results demonstrating the advantages of this approach with rate monotonic scheduling. Our simulations also show that a simple FIFO usually provides better real time schedulability with global semaphores than priority queues that use task execution priorities     

Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded Systems

We present an approach to the analysis and optimisation of heterogeneous multiprocessor embedded systems. The systems are heterogeneous not only in terms of hardware components, but also in terms of communication protocols and scheduling policies. When several scheduling policies share a resource, they are organised in a hierarchy. In this paper, we first develop a holistic scheduling and schedulability analysis that determines the timing properties of a hierarchically scheduled system. Second, we address design problems that are characteristic to such hierarchically scheduled systems: assignment of scheduling policies to tasks, mapping of tasks to hardware components, and the scheduling of the activities. We also present several algorithms for solving these problems. Our heuristics are able to find schedulable implementations under limited resources, achieving an efficient utilisation of the system. The developed algorithms are evaluated using extensive experiments and a real-life example.     

实时嵌入式多处理器操作系统实现框架

描述了针对实时嵌入式应用的多处理器操作系统的实现框架，简单介绍了常用的多处理器系统所采用的架构，提出了另外一种多处理器系统的实现架构，并讨论了与之相关的通信、全局资源管理、调度、cache一致性和异构性的问题。     

SLA-aware energy-efficient scheduling scheme for Hadoop YARN

Apache Hadoop becomes ubiquitous for cloud computing which provides resources as services for multi-tenant applications. YARN (a.k.a. MapReduce 2.0) is one of the key features in the second-generation Hadoop, which provides resource management and scheduling for large-scale MapReduce environments. Two enormous challenges in the YARN scheduler are the abilities to automatically tailor and control resource allocations to different jobs for achieving their Service Level Agreements (SLAs), and minimize energy consumption of the overall cloud computing system. In this work, we propose an SLA-aware energy-efficient scheduling scheme which allocates appropriate amount of resources to MapReduce applications with YARN architecture. In our task scheduling policy, We consider the data locality information to save the MapReduce network traffic. Furthermore, the slack time between the actual execution time of completed tasks and expected completion time of the application is utilized to improve the energy-efficiency of the system. An online userspace governor-based dynamic voltage and frequency scaling (DVFS) scheme is designed in the YARN per-application ApplicationMaster to dynamically change the CPU frequency for upcoming tasks given the slack time from previous completed tasks. Experimental evaluation shows that our proposed scheme outperforms the existing MapReduce scheduling policies in terms of both resource ultization and energy-efficiency.     

Dual-Priority versus Background Scheduling: A Path-Wise Comparison

In this paper, two well-known scheduling policies for real-time systems, namely background scheduling (BS) and dual-priority (DP) are compared in terms of response times for soft real-time traffic (SRT). It is proved in the preemptive as well as in the non-preemptive case that, when the SRT traffic is FIFO, the DP policy always outperforms BS for all instances of SRT tasks. When the SRT traffic is not FIFO but if all tasks are of equal size then, in the non-preemptive case, the average response times is shown to be always better under DP than under BS. As a complementary result, some non-FIFO examples where BS behaves better than DP for some SRT tasks but also on the average of the SRT response times, are given. The proofs are based on a trajectorial method that may be used for comparing other scheduling policies.     

Scheduling image processing tasks in a multilayer system

Multilayer multiprocessor systems are generally employed in real-time applications such as robotics and computer vision. This paper introduces three heuristic algorithms for multiprocessor task scheduling in such systems. In our model, tasks with arbitrary processing times and arbitrary processor requirements are considered. The scheduling aims at minimising completion time of processes in a two-layer system. We employed an effective lower bound (LB) for the problem. Then, we analysed the average performance of the heuristic algorithms by computing the average percentage deviation of each heuristic solution from the LB on a set of randomly generated problems. We have also applied these algorithms for scheduling computer vision tasks running on prototype multilayer architecture. Our computational and empirical results showed that the proposed heuristic algorithms perform well.     

Scheduling cross docking operations under full,partial and no information on inbound arrivals

Cross docking is a logistic technique which seeks to reduce the inventory holding, order picking, transportation costs and delivery time. Little attention has been given to the transshipment operations inside a cross dock. In this article, we study the transshipment scheduling problem in a single receiving and a single shipping door cross dock under three scheduling policies: In the first policy, we assume to have complete information on the order of arrivals and the contents of all inbound trucks. The second and the third policies assume the availability of partial and no information on the sequence of upcoming trucks. An optimal graph based model is proposed for the full information case, and a polynomial time algorithm is given. Heuristics are developed for the other two cases. The comparison of the costs associated to each policy helps evaluating the value of information in cross dock scheduling problems.     

Using processor-cache affinity information in shared-memorymultiprocessor scheduling

In a shared-memory multiprocessor system, it may be more efficient to schedule a task on one processor than on another if relevant data already reside in a particular processor's cache. The effects of this type of processor affinity are examined. It is observed that tasks continuously alternate between executing at a processor and releasing this processor due to I/O, synchronization, quantum expiration, or preemption. Queuing network models of different abstract scheduling policies are formulated, spanning the range from ignoring affinity to fixing tasks on processors. These models are solved via mean value analysis, where possible, and by simulation otherwise. An analytic cache model is developed and used in these scheduling models to include the effects of an initial burst of cache misses experienced by tasks when they return to a processor for execution. A mean-value technique is also developed and used in the scheduling models to include the effects of increased bus traffic due to these bursts of cache misses. Only a small amount of affinity information needs to be maintained for each task. The importance of having a policy that adapts its behavior to changes in system load is demonstrated     

Resource-efficient routing and scheduling of time-constrained streaming communication on networks-on-chip

Network-on-chip-based multiprocessor systems-on-chip are considered as future embedded systems platforms. One of the steps in mapping an application onto such a parallel platform involves scheduling the communication on the network-on-chip. This paper presents different scheduling strategies that minimize resource usage by exploiting all scheduling freedom offered by networks-on-chip. It also introduces a technique to take the dynamism in applications into account when scheduling the communication of an application on the network-on-chip while minimizing the resource usage. Our experiments show that resource-utilization is improved when compared to existing techniques.     

Tradeoff exploration between reliability, power consumption, and execution time for embedded systems

For autonomous critical real-time embedded (e.g., satellite), guaranteeing a very high level of reliability is as important as keeping the power consumption as low as possible. We propose an off-line scheduling heuristic which, from a given software application graph and a given multiprocessor architecture (homogeneous and fully connected), produces a static multiprocessor schedule that optimizes three criteria: its length (crucial for real-time systems), its reliability (crucial for dependable systems), and its power consumption (crucial for autonomous systems). Our tricriteria scheduling heuristic, called TSH, uses the active replication of the operations and the data-dependencies to increase the reliability and uses dynamic voltage and frequency scaling to lower the power consumption. We demonstrate the soundness of TSH. We also provide extensive simulation results to show how TSH behaves in practice: first, we run TSH on a single instance to provide the whole Pareto front in 3D; second, we compare TSH versus the ECS heuristic (Energy-Conscious Scheduling) from the literature; and third, we compare TSH versus an optimal Mixed Linear Integer Program.