An extendible approach for analyzing fixed priority hard real-time tasks

As the real-time computing industry moves away from static cyclic executive-based scheduling towards more flexible process-based scheduling, so it is important for current scheduling analysis techniques to advance and to address more realistic application areas. This paper extends the current analysis associated with static priority pre-emptive based scheduling; in particular it derives analysis for tasks with arbitrary deadlines that may suffer release jitter due to being dispatched by a tick driven scheduler. We also consider bursty sporadic activities, where tasks arrive sporadically but then execute periodically for some bounded time. The paper illustrates how a window-based analysis technique can be used to find the worst-case response time of a task set, and shows that the technique can be easily extended to cope with realistic and complex task characteristics.     

分时EDF算法及其在多媒体操作系统中的应用

提出了一种新的CPU调度算法－－分时EDF（Earliest Deadine First)算法,该算法能保证硬实时任务不丢失死线,并易于在分时系统中实现。以分时EDF算法为基础,提出一种新的CPU层次调度算法－－HRFSFQ,该算法用于多媒体操作系统时能保证各类任务的QoS。最后通过大量实验证明了上述算法的有效性和正确性。     

A methodology for digital real time simulation of dynamic systems using modern DSPs

The speedup factor in real time simulation of dynamic systems using multiprocessor resources depends on: the architecture of the multiprocessor system, type of interconnection between parallel processors, numerical methods and techniques used for discretization and task assignment and scheduling policy. The minimization of the number of processors needed for real time simulation requires the minimization of processors times for interprocessor communications and efficient scheduling policy. Therefore, this article presents a methodology for the real time simulation of dynamic systems including a new pre-emptive static assignment and scheduling policy. The advantages of applying digital signal processor with parallel architecture, for example TMS320C40, in real time simulation have been described. Some important issues in real time architectures necessary for efficient multiprocessor real time simulations, such as multiple I/O channels, concurrent I/O and CPU processing, direct high speed interprocessor communications, fast context switching, multiple busses, multiple memories, and powerful arithmetic units are inherent to this processor. These features minimize interprocessor communication time and maximize sustained CPU performance.     

A constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling

Scheduling activities in concurrent product development process is of great sig-nificance to shorten developements lead time and minimize the cost.Moreover,it can eliminate the unnecessary redesign periods and guarantee that serial activities can be executed as concurrently as possible,This paper presents a constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling.In the combined approack,the neural network is used to obtain a feasible starting time of all the activities based on sequence constraints ,the heuristic algorithm is used to obtain a feasible solution of the scheduling problem based on resource constrainsts.The feasible scheduling solution is obtained by a gradient optimization function .Sim-ulations have shown that the proposed combined approach is efficient and fasible with respect to concurrent activities scheduling.     

A Constraint Satisfaction Neural Network and Heuristic Combined Approach for Concurrent Activities Scheduling

Scheduling activities in concurrent product development process is of great significance to shorten development lead time and minimize the cost. Moreover, it can eliminate the unnecessary redesign periods and guarantee that serial activities can be executed as concurrently as possible. This paper presents a constraint satisfaction neural network and heuristic combined approach for concurrent activities scheduling. In the combined approach, the neural network is used to obtain a feasible starting time of all the activities based on sequence constraints, the heuristic algorithm is used to obtain a feasible solution of the scheduling problem based on resource constraints. The feasible scheduling solution is obtained by a gradient optimization function. Simulations have shown that the proposed combined approach is efficient and feasible with respect to concurrent activities scheduling.     

实时系统中的非定期任务调度算法综述

非定期任务调度是实时系统中的一个重要研究内容，综述了实时系统中非定期任务调度算法的研究与进展，按照这些算法的特征分为基于服务器的算法与基于空闲时间的算法两大类别，并着重对每个类别中的不同算法的特征与性能进行了分析，通过对这些算法的比较与分析，希望为实时系统的研究与开发者提供有意义的参考，最后还给出了非定期任务调度进一步研究的思路与建议。     

Setup times and fast tracking in resource-constrained project scheduling

Resource-constrained project scheduling with activity pre-emption assumes that activities are allowed to be interrupted and restarted later in the schedule at no extra cost. In the current paper, we extend this pre-emptive scheduling problem with setup times between activity interruptions and the possibility to schedule pre-emptive sub-parts of activities in parallel.

The contribution of the paper is twofold. First, we briefly show that an efficient exact branch-and-bound procedure from the literature to solve the resource-constrained project scheduling problem can be easily adapted to cope with our problem extensions. Second, we extensively test the impact of these pre-emptive extensions to the quality of the schedule from a makespan point-of-view.     

MINIMIZING SERVICE DELAY OF APERIODIC TASKS IN DYNAMIC‐PRIORITY NON‐PREEMPTIVE HARD REAL‐TIME SYSTEMS

A scheduling technique is presented to minimize service delay of aperiodic tasks in hard real‐time systems that employ dynamic‐priority scheduling and do not allow task preemption. In a real‐time scheduling process, the execution of periodic tasks can be deferred as long as this does not cause other tasks to violate their time constraints. However, aperiodic tasks that usually have urgent missions should complete execution as early as possible. In this paper, it is assumed that aperiodic tasks also have time constraints. Thus, the problem of deciding whether an aperiodic task with an unpredictable arrival time can be scheduled successfully or not is difficult to solve because delaying periodic tasks may cause them to fail to meet their time constraints. We present a dynamic scheduling technique to solve this problem which makes use of the symmetric property of a schedule. The maximum possible idle slot is always reserved at every scheduling point so that aperiodic tasks can be serviced immediately if the reserved idle slot is big enough to service them. The proposed technique also maximizes utilization of idle slots by reserving them for the longest possible time span.     

异构多核处理器的任务分配及能耗的研究*

异构多核处理器采用不同的任务分配与调度算法,会导致不同的时间消耗与能量消耗,采用合适的任务分配与调度算法能节省较多的能耗。目前普遍认为最有发展前途的任务分配与调度技术是先用启发式方法进行分组,然后再用遗传算法进行调度。在改进任务分组后,又首次提出了用遗传算法解决能耗问题。实验结果表明在实时要求不高的情况下,能以较小的时间代价来节省较多的能耗。     

TDCS: a new scheduling framework for real-time multimedia OS

ABSTRACT

The emerging real-time hyper-physical system (CPS), such as autonomous vehicle and live interactive media application, requires time deterministic behaviour. This is challenging to achieve by using the traditional general purpose operating system (GPOS). This paper presents a new design of the real-time operating system (OS) scheduling mechanism called ‘time deterministic cyclic scheduling’ (TDCS) mainly for live multimedia tasks processing. This new scheduler shares a similar philosophy as classic cyclic execution but with flexibility and dynamic configuration. This hybrid design is based on both time-reserved based cyclic execution and priority-based pre-emptive scheduling for mixed criticality applications. The simulation results show that this scheduling scheme can achieve predictable timing behaviour of task delay and jitter under high CPU utilisation. This shows that the proposed scheme is promising for low latency high-performance multimedia censoring tasks that occur in a periodic manner.     

P2P媒体分发网络中的数据下载调度策略

在P2P媒体分发网络中,当一个节点同时从若干个其他节点获取数据时,为了按时完成更多的下载任务,需要对数据下载任务进行合理调度,为此该文提出了一种基于多任务关联的数据下载调度策略,通过统筹调度一段时间内的下载任务,可有效提高系统的并发服务能力。实验结果表明该策略能提高约10%的并发处理能力。     

异构分布式控制系统中实时任务的调度算法

分布式控制系统是一种应用极为广泛的异构分布式实时系统，系统中同时存在有多种实时任务，如何将这些任务分配到各个处理器上并保证它们的时限是系统关键技术之一．在结合启发式任务分配算法和单处理器任务调度算法的基础上，提出了一种分布式控制系统的调度算法．该算法考虑了各个处理器的负载均衡，同时又能满足所有任务的时限．仿真结果表明了算法的有效性．     

Timing analysis of the PREEMPT RT Linux kernel

In the theory of real‐time scheduling, tasks are described by mathematical variables, which are used in analytical models in order to prove schedulability of the system. On real‐time Linux, tasks are computer programs, and Linux developers try to lower the latencies caused by the Linux kernel, trying to achieve faster response for the highest‐priority task. Although both seek temporal correctness, they use different abstractions, which end up separating these efforts in two different worlds, making it hard for the Linux practitioners to understand and apply the formally proved models to the Linux kernel and for theoretical researchers to apply the restrictions imposed by Linux for the theoretical models. This paper traces a parallel between the theory of response‐time analysis and the abstractions used in the Linux kernel. The contribution of this paper is threefold. We first identify the PREEMPT RT Linux kernel mechanisms that impact the timing of real‐time tasks and map these impacts to the main abstractions used by the real‐time scheduling theory. Then, we describe a customized trace tool, based on the existing trace infrastructure of the Linux kernel, that allows the measurement of the delays associated with the main abstractions of the real‐time scheduling theory. Finally, we use this customized trace tool to characterize the timing lines resulting from the behavior of the PREEMPT RT Linux kernel. Copyright © 2015 John Wiley & Sons, Ltd.     

The Non-Optimality of the Monotonic Priority Assignments for Hard Real-Time Offset Free Systems

In this paper, we study the problem of scheduling hard real-time periodic tasks with static priority pre-emptive algorithms. We consider tasks which are characterized by a period, a hard deadline, a computation time and an offset (the time of the first request), where the offsets may be chosen by the scheduling algorithm, hence the denomination offset free systems.We study the rate monotonic and the deadline monotonic priority assignments for this kind of system and we compare the offset free systems and the asynchronous systems in terms of priority assignment. Hence, we show that the rate and the deadline monotonic priority assignments are not optimal for offset free systems.     

Worst-case response time analysis of real-time tasks under fixed-priority scheduling with deferred preemption

Fixed-priority scheduling with deferred preemption (FPDS) has been proposed in the literature as a viable alternative to fixed-priority pre-emptive scheduling (FPPS), that obviates the need for non-trivial resource access protocols and reduces the cost of arbitrary preemptions. This paper shows that existing worst-case response time analysis of hard real-time tasks under FPDS, arbitrary phasing and relative deadlines at most equal to periods is pessimistic and/or optimistic. The same problem also arises for fixed-priority non-pre-emptive scheduling (FPNS), being a special case of FPDS. This paper provides a revised analysis, resolving the problems with the existing approaches. The analysis is based on known concepts of critical instant and busy period for FPPS. To accommodate for our scheduling model for FPDS, we need to slightly modify existing definitions of these concepts. The analysis assumes a continuous scheduling model, which is based on a partitioning of the timeline in a set of non-empty, right semi-open intervals. It is shown that the critical instant, longest busy period, and worst-case response time for a task are suprema rather than maxima for all tasks, except for the lowest priority task. Hence, that instant, period, and response time cannot be assumed for any task, except for the lowest priority task. Moreover, it is shown that the analysis is not uniform for all tasks, i.e. the analysis for the lowest priority task differs from the analysis of the other tasks. These anomalies for the lowest priority task are an immediate consequence of the fact that only the lowest priority task cannot be blocked. To build on earlier work, the worst-case response time analysis for FPDS is expressed in terms of known worst-case analysis results for FPPS. The paper includes pessimistic variants of the analysis, which are uniform for all tasks, illustrates the revised analysis for an advanced model for FPDS, where tasks are structured as flow graphs of subjobs rather than sequences, and shows that our analysis is sustainable.     

FF现场总线系统中实时任务的建模与调度

本文研究了单网段 FF现场总线系统中具有时间约束和次序约束的实时任务，即 功能块任务和通信任务的建模与调度．首先，将功能块任务和通信任务等视为相同的任务， 在只考虑任务间次序约束的情况下，提出了基于紧凑模式的任务模型，以保证每个作业被尽 可能早地完成．其次，考虑单网段通信任务共享一个传输介质而引起的通信超时，提出了基 于作业速率单调优先级算法的扩展紧凑模式的任务调度算法，以满足实时任务的时间约束 和次序约束．最后，通过一个应用实例来描述实时任务的调度过程．     

Novel multi-objective resource allocation and activity scheduling for fourth party logistics

In order to reduce logistic costs, the scheduling of logistic tasks and resources for fourth party logistics (4PL) is studied. Current scheduling models only consider costs and finish times of each logistic resource or task. Not generally considered are the joint cost and time between two adjacent activities for a resource to process and two sequential activities of a task for two different resources to process are ignored. Therefore, a multi-objective scheduling model aiming at minimizing total operation costs, finishing time and tardiness of all logistic tasks in a 4PL is proposed. Not only are the joint cost and time of logistic activities between two adjacent activities and two sequential activities included but the constraints of resource time windows and due date of tasks are also considered. An improved nondominated sorting genetic algorithm (NSGA-II) is presented to solve the model. The validity of the proposed model and algorithm are verified by a corresponding case study.     

传感器网络中协作任务的实时调度

在传感器网络实时监测应用中,大量传感器散布在监测区域中感知监测域的各种环境或监测对象的信息,一组功能有限的传感器往往相互协作地完成一个大的实时感知任务,协作性是传感器网络的重要特性,它要求实时任务之间的资源共享。单纯的实时系统为保证任务的实时性通常采用资源隔离机制而不能很好地解决传感器网络环境中的采集流数据处理的协作性问题。本文基于服务器的调度框架,使用了实时环境中的时间属性,将数据时间与程序时间相结合,从而将应用语义与系统中运行的程序相联系,提出了一种基于时间依赖关系的实时调度模式,并给出了基于此模式的事件驱动并发数据流程图模型及其实现机制。分析表明,该模型能有效地解决传感器网络监测区域中采集流数据处理过程的协作性问题,减少了数据丢失,提高了系统响应的实时性。     

基于EDF算法的可行性判定及实现

实时调度算法是实时系统中的关键技术。验证实时调度算法的可行性是在实时系统中实施某种调度算法的必经环节。在介绍实时系统中常用的各种实时调度算法,包括固定优先级调度算法和动态优先级调度算法基础上,详细分析了动态优先级调度算法EDF算法的运算过程和使用条件。提出了该算法在实际应用中存在的问题。针对该硬实时调度算法,提出了分别在简单模型上和复杂模型上如何判定实时任务的可行性。为实际应用中实现该实时调度算法确定了依据。     

基于反馈控制的开放式实时系统自适应调度算法设计与实现

对于负载不可预测且资源受限的开放式实时系统,传统"开环"调度算法不能根据系统负载情况调整调度策略,影响系统实时性能或造成资源浪费.采用双闭环反馈控制方法,改进目前开放式实时系统常用的时限驱动总带宽利用率服务器.本方法根据负载情况,动态地为不同实时性能需求的任务分配资源,保证硬实时任务满足时限要求并且提高资源利用率.实验表明,系统负载存在突发的情况下,算法既很好地控制了任务的时限错过率,又得到了较高的资源利用率.