M.V. Kavalerov - Ph.D. (Eng.), Department of Automation and Telemechanics, Perm National Research Polytechnic University. E-mail: mkavalerov@gmail.com N.N. Matushkin  Dr.Sc. (Eng.), Professor, Department of Automation and Telemechanics, Perm National Research Polytechnic University. E-mail: mnn@pstu.ru

In the development of information and control systems, as real time systems, real-time scheduling techniques are applied to improve efficiency in the use of computational resources. In particular, more efficient scheduling of real-time tasks can make more stringent timing constraints to be met on a given hardware of an information and control system. In the case of complex information and control systems, it is necessary to provide efficient joint scheduling of aperiodic tasks and real-time tasks with standard constraints which are derived according to conditions of admissibility and on the basis of original linear interval constraints. Standard constraints are expressed with period, deadline and offset. Information and control systems are usually implemented on the basis of real-time computational tasks. Each task has a timing constraint imposing requirements on the process of execution of requests which are released by this task. Previously, an approach to scheduling of tasks having linear interval constraints has been developed for fixed priority scheduling framework. This approach can significantly improve the efficiency of computational resources utilization. The next obvious step in this approach is to solve the problem of joint scheduling of real-time hard tasks, having linear interval constraints, and aperiodic tasks. The set of aperiodic tasks produces the set of aperiodic requests, and, at this level of abstraction, a single stream of aperiodic requests is considered. Generally, there are many ways to transform a task with linear interval constraint to a task with admissible standard constraint. But the parameter values of standard constraint can significantly affect the efficiency of joint scheduling of hard real-time tasks and aperiodic requests. It is therefore important to choose the right transformation of original linear interval constraint to admissible standard constraint. However, the article shows that generally there is no optimal methods for transformation of linear interval constraint to admissible standard constraint on the criterion of minimizing the average response time of aperiodic tasks across the entire range of possible processor utilization by these aperiodic tasks. One of possible solutions of this problem is to dynamically choose one of the admissible standard constraints according to the current workload of aperiodic requests.

 

1. Sha L., Abdelzaher T., Årzén K. E., Cervin A., Baker T., Burns A., Buttazzo G., Caccamo M., Lehoczky J., Mok A. K. Real-Time Scheduling Theory: A Historical Perspective // Real-Time Systems. 2004. V. 28.P. 101-155.
2. Buttazzo G. Hard Real-Time Computing Systems. Springer. 2011. 521 p.
3. Kavalerov M.V., Matushkin N.N. Vozmozhnost sushhestvennogo povyshenija ehffektivnosti planirovanija na osnove neposredstvennogo primenenija linejjnykh intervalnykh ogranichenijj realnogo vremeni // Vestnik Permskogo nacionalnogo issledovatelskogo politekhnicheskogo universiteta. EHlektrotekhnika, informacionnye tekhnologii, sistemy upravlenija. 2011. № 5. S. 4-13.
4. Kavalerov M.V., Matushkin N.N. Novyjj algoritm naznachenija parametrov zadach realnogo vremeni s linejjnymi intervalnymi ogranichenijami v uslovijakh planirovanija s fiksirovannymi prioritetami, osnovannyjj na sokrashhennom perebore prioritetov // Nejjrokompjutery: razrabotka, primenenie. 2013. № 11. S. 12-17.
5. Kavalerov M.V., Matushkin N.N.Analiz vremennojj slozhnosti algoritmov, realizujushhikh naznachenie parametrov zadach realnogo vremeni s linejjnymi intervalnymi ogranichenijami dlja planirovanija s fiksirovannymi prioritetami // Nejjrokompjutery: razrabotka, primenenie. 2013. № 11. S. 18-24.
6. Hua Y., Rao L., Liu X., Feng D. Cooperative and efficient real-time scheduling for automotive communications // IEEE 34th International Conference on Distributed Computing Systems (ICDCS). 2014. P. 134-143.
7. Pop F., Dobre C., Cristea V., Bessis N. Scheduling of sporadic tasks with deadline constrains in cloud environments // IEEE 27th International Conference on Advanced Information Networking and Applications (AINA). 2013. P. 764-771.
8. Dadenkov S.A., Kon E.L. Issledovanie proizvoditelnosti algoritma dostupa k srede predictive p-persistent CSMA protokola // Vestnik Permskogo nacionalnogo issledovatelskogo politekhnicheskogo universiteta. 2012. № 6.  S. 217-230.
9. Dadenkov S.A., CHmykov V.V. K probleme analiza proizvoditelnosti promyshlennykh setejj (na primere LonWorks) // Sb. nauch. trudov «Sworld» po materialam Mezhdunar. nauch.-praktich. konf. 2014. T. 10. № 3. S. 81-87.
10. Lehoczky J. P., Ramos-Thuel S. Scheduling periodic and aperiodic tasks using the slack stealing algorithm // Advances in real-time systems. 1995. V. 8. P. 175-198.
11. Davis R.I. Approximate Slack Stealing Algorithms for Fixed Priority Preemptive Systems // Technical Report YCS-93-216. University of York. 1993.
12. Tia T.S., Liu J.W.S., Shankar M. Aperiodic Request Scheduling in Fixed-Priority Preemptive Systems // Technical Report UIUCDCS-R-94-1859. University of Illinois at Urbana-Champaign. 1994.
13. Fohler G. Dynamic Timing Constraints - Relaxing Over-constraining Specifications of Real-Time Systems // Proceedings of Work-in-Progress Session. 18th IEEE Real-Time Systems Symposium. 1997. P. 27-30.
14. Kavalerov M.V. Preobrazovanie linejjnykh intervalnykh ogranichenijj realnogo vremeni v standartnye ogranichenija // Sistemy upravlenija i informacionnye tekhnologii. 2006. № 4.2(26). S. 228-233.
15. Kavalerov M.V., Matushkin N.N.Primenenie algoritma poluchenija uslovija dopustimosti standartnogo ogranichenija realnogo vremeni dlja primerov linejjnykh intervalnykh ogranichenijj // Vestnik Permskogo nacionalnogo issledovatelskogo politekhnicheskogo universiteta. EHlektrotekhnika, informacionnye tekhnologii, sistemy upravlenija. 2012. № 6. S. 104-114.