QCSP Based Schedulability Test of Real-Time System

Ju Yang Zhang; Yi Xiang Chen

doi:10.4028/www.scientific.net/AMM.313-314.1214

Paper Titles

An Iris Image Acquisition Method Based on Embedded System
p.1197

Positive Solutions for Nonlinear Lidstone Boundary Value Problems
p.1201

Method of Forecast Wind Speed Based on Wavelet Analysis and Quantile Regression
p.1205

Stress Analysis for Electric Stop Valve of Nuclear Power Plant Considering Action of Preload and Stem Force
p.1210

QCSP Based Schedulability Test of Real-Time System
p.1214

A Method for Extracting Characteristic Frequency Components of Blood Flow Signals Based on Wavelet Transform
p.1221

Pipeline Leak Detection Based on Double Sensor Negative Pressure Wave
p.1225

Space-Time Adaptive Processing Used for Underwater LFM and CW
p.1229

Short-Term Noise and the Robustness of Two Log-Periodogram Estimators in Long Memory Series
p.1235

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 313-314QCSP Based Schedulability Test of Real-Time System

QCSP Based Schedulability Test of Real-Time System

Abstract:

The problem of schedulability test of real-time task in scheduling system has been addressed. In such as real-time scheduling problems with uncertain interrupt operation, Quantified Constraint Satisfaction Problems (QCSP) were introduced to model and solve CSP involving uncertainty or uncontrollability on the value taken by some variables. In this paper, we propose to a novel approach to schedulability test based on the QCSP model. Based on the QCSP model of scheduler and interrupter in the real-time scheduling system, we transform the schedulability test into the satisfability problem. Finally, we design the algorithm QCSP-SchTest for judging the satisfability of a schedule S(α). This leads to a new schedulability test method without considering the specific scheduling algorithm or strategy.

You might also be interested in these eBooks

Machinery Electronics and Control Engineering II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 313-314)

Pages:

1214-1217

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.313-314.1214

Citation:

Cite this paper

Online since:

March 2013

Authors:

Ju Yang Zhang, Yi Xiang Chen

Keywords:

Constraint Programming, Quantified Constraint Satisfaction Problem, Real-Time Scheduling System, Schedulability Test

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] J.A. Stankovic and K. Ramamritham, eds., Hard Real-Time Systems, IEEE Computer Society. (1988)

Google Scholar

[2] C. C. Han and H. Y. Tyan. A Better Polynomial-Time Schedulability Test for Real-Time Fixed Priority Scheduling Algorithms, IEEE 18th Real-Time Systems Symposium. (1997)

DOI: 10.1109/real.1997.641267

Google Scholar

[3] Krzysztof R. Apt. The Principles of Constraint Programming. Cambridge University press. (2003)

Google Scholar

[4] Tsang, E. P. K., Foundations of Constraint Satisfaction, San Diego, Calif.: Academic, p.53-63J. (1993)

Google Scholar

[5] L. Bordeaux and E. Monfroy. Beyond NP: Arc-consistency for Quantified Constraints. In Proceedings of CP-2002. (2002)

DOI: 10.1007/3-540-46135-3_25

Google Scholar

[6] I. Gent, P. Nightingale, and A. Rowley. Encoding Quantified CSPs as Quantified Boolean Formulae. In Proceedings of ECAI-2004, pp.176-180. (2004)

Google Scholar

[7] Benedetti, M., Lallouet, A., Vautard, J. QCSP Made Practical by Virtue of Restricted Quantification. In: Proc. of IJCAI 2007, pp.38-43 (2007)

Google Scholar

[8] Gent, I.P., Nightingale, P., Stergiou, K. QCSP-Solve: A Solver for Quantified Constraint Satisfaction Problems. In: Proc. of IJCAI 2005, pp.138-143 (2005)

Google Scholar

[9] SUN Jigui, ZHANG Juyang, CHEN Shangwei. Non-binary Constraint Hybrid Search Algorithm, Acta Automatica Sinica 33(9), pp.974-978. (2007)

Google Scholar