Online deadline scheduling with preemption penalties

This paper presents a study of the problem of online deadline scheduling under the preemption penalty model of Zheng, Xu, and Zhang (2007). In that model, each preemption incurs a penalty of ρ times the weight of the preempted job, where ρ ? 0 is the preemption penalty parameter. The objective is to maximise the total weight of jobs completed on time minus the total penalty.     

Speed scaling with a solar cell

We consider the setting of a device that obtains its energy from a battery and some regenerative source such as a solar cell. We consider the speed scaling problem of scheduling a collection of tasks with release times, deadlines, and sizes, so as to minimize the energy recharge rate of the regenerative source. This is the first theoretical investigation of speed scaling for devices with a regenerative energy source. We show that the problem can be expressed as a polynomial sized convex program. We show that, using the KKT conditions, one can obtain an efficient algorithm to verify the optimality of a schedule. We show that the energy optimal YDS schedule is 2-approximate with respect to the recharge rate. We show that the online algorithm BKP is O(1)$O\left(1\right)$-competitive with respect to recharge rate.     

A general distributed scalable grid scheduler for independent tasks

We consider non-preemptively scheduling a bag of independent mixed tasks (hard, firm and soft) in computational grids. Based upon task type, we construct a novel generalized distributed scheduler (GDS) for scheduling tasks with different priorities and deadlines. GDS is scalable and does not require knowledge of the global state of the system. It is composed of several phases: a multiple attribute ranking phase, a shuffling phase, and a task-resource matched peer to peer dispatching phase. Results of exhaustive simulation demonstrate that with respect to the number of high-priority tasks meeting deadlines, GDS outperforms existing approaches by 10%–25% without degrading schedulability of other tasks. Indeed, with respect to the total number of schedulable tasks meeting deadlines, GDS is slightly better. Thus, GDS not only maximizes the number of mission-critical tasks meeting deadlines, but it does so without degrading the overall performance. The results have been further confirmed by examining each component phase of GDS. Given that fully known global information is time intensive to obtain, the performance of GDS is significant. GDS is highly scalable both in terms of processors and number of tasks—indeed it provides superior performance over existing algorithms as the number of tasks increase. Also, GDS incorporates a shuffle phase that moves hard tasks ahead improving their temporal fault tolerance. Furthermore, since GDS can handle mixed task types, it paves the way to open the grid to make it amenable for commercialization. The complexity of GDS is O(n²m)$O\left(n^{2}m\right)$ where n$n$ is the number of tasks and m$m$ the number of machines.     

The space of EDF deadlines: the exact region and a convex approximation

It is well known that the performance of computer controlled systems is heavily affected by delays and jitter occurring in the control loops, which are mainly caused by the interference introduced by other concurrent activities. A common approach adopted to reduce delay and jitter in periodic task systems is to decrease relative deadlines as much as possible, but without jeopardizing the schedulability of the task set. In this paper, we formally characterize the region of admissible deadlines so that the system designer can appropriately select the desired values to maximize a given performance index defined over the task set. Finally we also provide a sufficient region of feasible deadlines which is proved to be convex.

分布实时系统中的点到点通信

本文给出了一种由点到点互连网络连接的实时系统通信方法,分析了通道建立过程,消息调度算法,缓冲预留方案,以及消息传递时间的计算模型,可提供确定性的消息传递延迟。     

一种数据流上截止期敏感的滑动窗口处理策略

在数据流上定义了截止期作为连续查询的实时约束,并建立了基于截止期的滑动窗口处理模型;提出了一种基于预测的截止期敏感的滑动窗口处理策略;在多滑动窗口查询处理环境中,提出了一种（k,m ）截止期约束机制,在提高查询实时性的前提下,尽可能的满足不同查询对结果丢失率的不同约束。实验结果表明该处理策略能够有效提高数据流上滑动窗口查询的截止期满足率。     

最晚截止期优先带宽转让算法

基于最早截止期优先调度的实时系统，针对有新任务插入(与/或)现行任务加速但系统带宽不足的问题，提出一种最晚截止期优先(LDF)算法，用于系统在运行时选择现行任务转让带宽。采用从最晚作业截止期任务开始判断的方法，经过尽可能少的比较次数，找到合适的受压任务，平滑地完成带宽转让。算法需要的最多比较次数为2n。仿真结果表明，该算法在大多情况下只需要比较1~2次即可完成压缩任务。     

Rate Monotonic vs. EDF: Judgment Day

Since the first results published in 1973 by Liu and Layland on the Rate Monotonic (RM) and Earliest Deadline First (EDF) algorithms, a lot of progress has been made in the schedulability analysis of periodic task sets. Unfortunately, many misconceptions still exist about the properties of these two scheduling methods, which usually tend to favor RM more than EDF. Typical wrong statements often heard in technical conferences and even in research papers claim that RM is easier to analyze than EDF, it introduces less runtime overhead, it is more predictable in overload conditions, and causes less jitter in task execution.Since the above statements are either wrong, or not precise, it is time to clarify these issues in a systematic fashion, because the use of EDF allows a better exploitation of the available resources and significantly improves system's performance.This paper compares RM against EDF under several aspects, using existing theoretical results, specific simulation experiments, or simple counterexamples to show that many common beliefs are either false or only restricted to specific situations.     

实时系统任务模型初探

关于实时系统,本文列出了7种典型的任务模型,分析了它们各自的特点,给出了一个新的统一模型.     

COTS Switch工业以太网实时调度算法

针对基于商用现成组件技术（Commercial Off-The-Shelf,COTS）的交换式以太网不能满足工业数据通信的实时性要求问题,给出了改进的FTT（Flexible Time-Triggered communication paradigm）网络调度模型,提出了新的周期性实时消息链路可调度性优化判定方法,在此基础上设计了一种基于EDF（Earliest Deadline First）的实时调度算法。算法通过对网络消息流量进行有效控制防止交换机缓冲区溢出,同时充分发挥网络在同一时间存在多个并行传输链路的优势,提高了网络实时性。仿真实验表明该算法在提高网络的聚合带宽、减小消息的平均等待延时和丢失率方面均有明显的优势。