"Firm Real-Time System Scheduling Based on a Novel QoS Constrain" ,D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling , in the 24th IEEE International Real-Time Systems Symposium (RTSS2003), December 3-5, 2003 Cancun, Mexico,

"Scheduling Tasks with Markov-Chain Based constraint" ,D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling , in the 17th Euromicro Conference on Real-Time Systems (ECRTS2005)

"Firm Real-Time System Scheduling Based on a Novel QoS Constrain" ,D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling , Will appear in IEEE Transactions on Computers (TC)

Introduction

Quantifying the occasional deadline misses is critical for evaluating the Quality of Service (QoS) of a firm real-time system (FRTS). Often used QoS metrics for FRTS are: Deadline miss ratio,effective processor utilization and completion count discussed in [1, 2]. The advantage of these metrics is that they can be estimated off-line and used directly to guide the scheduler design. Also, a variety of window-based QoS constraints have been proposed for FRTS, e.g., (m;k)-firm constraint, Skip factor constraint, and Weakly hard real-time system constraint.

In this project we investigate alternative QoS metrics/constraints for FRTS that are more general and flexible. We are interested in capturing the probabilistic behaviors of the system by the new QoS metrics/constraints. Based on top of that, we also need to design new scheduling algorithms that can satisfy the new QoS constraints to improve the system performance. During the last two years, we had proposed four new scheduling algorithms[4][5] for FRTS and shown the effectiveness of these algorithms by simulation and experiment.

A typical Firm Real-Time system: Networked control system

A networked control system is a control system whose feedback path from the sensor to the plant is realized over a communication network. Feedback measurements are occasionally dropped for one of two reasons; either the medium is unreliable or the measurement is purposely dropped to stay within an allocated transmission rate. The diagram in Figure 1 shows the NCS under consideration. Such an NCS model is widely used in modern control applications.

Figure1: NCS model

Our proposed approaches

In [4], we proposed to use a Markov-Chain based QoS metric ( MC constraint ) to describe the desired behavior of a NCS. This QoS metric captures the more favorable deadline-miss patterns which can be obtained by analyzing the plant[3]. Furthermore, the Markov Chain based QoS can be directly related to the overall control system performance.

To improve the schedule quality under this QoS metric, we developed 3 new scheduling algorithms in [4].

Markov Chain Driven Algorithm (MDA)

Dropout-rate Driven Algorithm (DDA)

Feedback Driven Algorithm (FDA)

These algorithms are online algorithms. The common idea of them is to partition jobs dynamically into different groups depends on job's current history patterns (dropout patterns of previous jobs of the same task). Some groups are given higher priorities than others so that the dropout processes of tasks can follow the desired Markov-Chain based QoS constraints. Within each group, either a priority-based scheduling algorithm, such as EDF or RM, or a scheduling scheme which uses a randomized priority assignment is used depending on the feature of that group.

In [5], we considered FRTS containing multiple tasks with different MC constraints. Such FRTS can be found in a number of applications, e.g., a robot control system which must execute several control tasks on one resource. In such a system, the performance of each control task is a function of the respective dropout process and the control tasks need to be coordinated to accomplish some common goal. Existing scheduling algorithms are not able to achieve good overall performance due to their various drawbacks. There are 3 unique challenges in designing scheduler for tasks with MC constraints.

The scheduling goal for a task with an MC constraint is to achieve a dropout process, not a dropout pattern nor a dropout rate.

Merely forcing the dropout process of a task to follow the given MC constraints without any concern for the average dropout rate could still hurt the task performance. Thus, the scheduler must ``fairly'' allocate the resource.

Dropping a job at different state (previous dropout pattern) leads to different performance degradation. To solve these scheduling problem, it is desirable to have a strategy for evaluating the criticality of each state. We presented two new scheduling approaches, the State Sensitivity based algorithm (SSA) and Grouped Fair Dropout Rate algorithm (GFDR). By carefully using the pre-scheduling analysis of the plant and judiciously choosing the feedback information used by the scheduler, both algorithms effectively overcome the shortcomings of the existing algorithms and thus further improve the performance of the NCS.

Simulation and experiment

In our work, real-time tasks have firm deadline constraints. They are periodic but their execution times can vary between the best case execution time (BCET) and worst case execution time (WCET). In [4], the NCS system is modeled by MATLAB Simulink , the scheduler is modeled by software written in C and C++. To further validates the usefulness of SSA, we implemented our scheduling algorithms as well as other comparable scheduling methods in a Real Time Operating System, QNX 4.25. Figure 2 shows the overall system setup. Both simulation result in QNX and experimental result using C program shows SSA outperforms other scheduling algorithms.

Figure2: Simulation Setup in QNX

References

[1] On the competitiveness of on-line real-time task scheduling , S. Baruah, el. al., RealTime Systems,Vol. 4, 1992, pp. 125-144.

[2] Scheduling for overload in real-time systems ,S. Baruah and J. Haritsa, and N. Sharma, IEEE Transactions on computers, Vol. 46, No. 9, 1997, pp. 1034-1039.

[3] Soft real-time scheduling of networked control systems with dropouts governed by a Markov chain , Q. Ling and M.D. Lemmon, American Control Conference, June 2003.

[4] "Firm Real-Time System Scheduling Based on a Novel QoS Constrain" ,D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling , in the 24th IEEE International Real-Time Systems Symposium (RTSS2003), December 3-5, 2003 Cancun, Mexico,

[5] "Scheduling Tasks with Markov-Chain Based constraint" ,D. Liu, X. Sharon Hu, M. Lemmon and Q. Ling , in the 17th Euromicro Conference on Real-Time Systems (ECRTS2005)

Last changed on Sep 11 2005 by

Donglin Liu