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 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. 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. Among these algorithms, the algorithm with complete search of priority assignments is the most efficient but its use may be difficult for a large number of tasks due to long duration of the search. For example, on a personal computer in the case of twelve real-time tasks, this algorithm can run longer than a week. Therefore, there is a need to develop a more efficient version of the algorithm with incomplete search of priority assignments. In this paper, we propose a new algorithm of task attribute assignment, which is the most efficient among the algorithms that do not perform a complete search of priority assignments. We give a detailed description of the proposed algorithm. Also we present the results of simulations that show that the efficiency of the proposed algorithm approaches very closely to the efficiency of the algorithm with complete search of priority assignments.

 

1. Kopetz H. Real-Time Systems. Design Principles for Distributed Embedded Applications. Springer. 2011. 376 p.
2. Buttazzo G. Hard Real-Time Computing Systems. Springer. 2011. 521 p.
3. 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.
4. 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.
5. Kavalerov M.V. Preobrazovanie linejjnykh intervalnykh ogranichenijj realnogo vremeni v standartnye ogranichenija // Sistemy upravlenija i informacionnye tekhnologii. 2006. №4.2(26). S. 228-233.
6. Kavalerov M.V., Matushkin N.N.Primenenie algoritma poluchenija uslovija dopustimosti standartnogo ogranichenija realnogo vremeni dlja primerov linejjnykh intervalnykh ogranichenijj // Vestnik PNIPU. EHlektrotekhnika, informacionnye tekhnologii, sistemy upravlenija. 2012. №6. S. 104-114.
7. Kavalerov M.V., Matushkin N.N. Vozmozhnost sushhestvennogo povyshenija ehffektivnosti planirovanija na osnove neposredstvennogo primenenija linejjnykh intervalnykh ogranichenijj realnogo vremeni // Vestnik PNIPU. EHlektrotekhnika, informacionnye tekhnologii, sistemy upravlenija. 2011. № 5. S. 4-13.
8. 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.