M. V. Kavalerov – Ph.D. (Eng.), Department of Automation and Telemechanics, Perm National Research Polytechnic University. E-mail: email@example.com <>
N. N. Matushkin – Dr.Sci. (Eng.), Professor, Department of Automation and Telemechanics, Perm National Research Polytechnic University. E-mail: firstname.lastname@example.org
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.
Buttazzo G. Hard Real-Time Computing
Systems. Springer. 2011. 521 p.
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.
Velasco M., Marti P., Bini E. Control-driven
Tasks: Modeling and Analysis // IEEE Real-Time Systems Symposium. 2008. P.
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.
Tindell K.W. An Extendible Approach for
Analysing Fixed Priority Hard Real-Time Tasks // Technical Report YCS 189.
University of York. 1992. 16 p.