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.Sci. (Eng.), Professor, Department of Automation and Telemechanics, Perm National Research Polytechnic University. E-mail: mnn@pstu.ru

In the field of design 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. There is a scheduling problem of real-time tasks under fixed-priority scheduling. This problem is reduced to the problem of task attribute assignment for real-time tasks, namely the assignment of offset, period, and priority for each task. These attributes must guarantee the execution of these tasks such that their timing constraints are met. Many studies have examined the different types of extensions of the standard model of fixed-priority scheduling. Such extensions make it possible to take into account more information about the features of real-time tasks and their constraints. And this serves as a basis for a more effective scheduling of real-time tasks in information and control systems. One of the possible extensions of the standard model of fixed priority scheduling is a transition from the standard constraints expressed with periods and deadlines to the class of linear interval constraints which includes many of timing constraints of control tasks. Such extension has demanded the development of new algorithms of task attribute assignment for tasks with constraints from this class. In a previous work the authors proposed a number of such algorithms that have different values of speed and efficiency Performance evaluations of these algorithms obtained on the basis of simulations were presented earlier. This paper examines the time complexity of the previously developed algorithms. As a result of detailed analysis of each algorithm, the time complexity is obtained in the asymptotic form for the worst case. We obtained the expressions for the time complexity depending not only on the number of tasks, but also on the dimension of linear interval constraints. We have identified the key components of the algorithms that contribute to their time complexity, as well as their performance. The results help to understand the properties of the algorithms, as well as facilitate the modification of the existing scheduling algorithms and the development of new and more efficient algorithms.

 

1. Buttazzo G. Hard Real-Time Computing Systems. Springer. 2011. 521 p.
2. 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. №28. P. 101-155.
3. Velasco M., Marti P., Bini E. Control-driven Tasks: Modeling and Analysis // IEEE Real-Time Systems Symposium. 2008. P. 280-290.
4. Marti P., Fohler G., Ramamritham K., Fuertes J.M. Jitter Compensation for Real-Time Control Systems // Proceedings of 22nd IEEE Real-Time Systems Symposium. 2001. P. 39-48.
5. 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.
6. Kavalerov M.V., Matushkin N.N. Primenenie obobshhennykh nestandartnykh ogranichenijj realnogo vremeni v uslovijakh planirovanija s fiksirovannymi prioritetami // Informacionnye tekhnologii modelirovanija i upravlenija, 2005. № 6(24). S. 842-848.
7. Kavalerov M.V., Matushkin N.N. Planirovanie zadach v sistemakh avtomatizacii i upravlenija pri linejjnykh intervalnykh ogranichenijakh realnogo vremeni // Problemy upravlenija. 2008. №1. C. 51-61.
8. Kavalerov M.V. Preobrazovanie linejjnykh intervalnykh ogranichenijj realnogo vremeni v standartnye ogranichenija // Sistemy upravlenija i informacionnye tekhnologii. 2006. №4.2(26). S. 228-233.
9. Kavalerov M.V., Matushkin N.N. Primenenie algoritma poluchenija uslovija dopustimosti standartnogo ogranichenija realnogo vremeni dlja primerov linejjnykh intervalnykh ogranichenijj // Vestnik PNIPU. EHlektrotekhnika, informacionnyetekhnologii, sistemyupravlenija. 2012. № 6. S. 104-114.
10. Audsley N.C. Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times // Technical Report YCS164. Department of Computer Science. University of York. UK. 1991. 31 p.
11. Tindell K.W. An Extendible Approach for Analysing Fixed Priority Hard Real-Time Tasks // Technical Report YCS 189. University of York. 1992. 16 p.