М. 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. 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 previous papers the authors proposed a number of such algorithms that have different values of speed and efficiency. These algorithms can be used only if we know estimates (lower and upper bounds) of real-time job execution parameters. Therefore, we must be able to obtain these estimates on the basis of information about given real-time tasks. Execution parameters are defined as intervals between time instants related to job execution. For example, one of the best known is the so-called response time that equals to time interval between release time and finish time of a job. We must be able to estimate how external events and other jobs affect the response time, i.e., we must be able to obtain upper and lower bounds of the response time. However, apart from the response time, there are other job execution parameters. When the model of linear interval constraints is used, there are 10 execution parameters for each job. A new algorithm obtaining the estimates of these parameters is proposed. A proof is given that estimates obtained by this algorithm are correct

 

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. 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.
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. Gerber R., HongS. Semantics-BasedCompilerTransformationsforEnhancedSchedulability // Proceedingsof 14thIEEEReal-TimeSystems Symposium. Raleigh-Durham. 1993. P. 232-242.
7. 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.
8. Fuhrmann I., Broman D., Smyth S., von Hanxleden R. Towards Interactive Timing Analysis for Designing Reactive Systems // Workshop on Reconciling Performance with Predictability (RePP-14). ETAPS. 2014.
9. Dadenkov S.A., Kon E.L. Issledovanie proizvoditelnosti algoritma dostupa k srede predictivep-persistentCSMA protokola // Vestnik PNIPU. EHlektrotekhnika, informacionnye tekhnologii, sistemy upravlenija. 2012. № 6. S. 217-230.
10. Dadenkov S.A., Kon E.L. Podkhod k postroeniju analiticheskojj modeli informacionno-upravljajushhejj seti LonWorks na osnove nejjrochipov // Nejjrokompjutery: razrabotka, primenenie. 2013. №11. S. 64-69.
11. Tindell K.W. An Extendible Approach for Analysing Fixed Priority Hard Real-Time Tasks // Technical Report YCS-92-189. University of York. York. 1992. 16 p.
12. Redell O., Sanfridson M. Exact Best-Case Response Time Analysis of Fixed Priority Scheduled Tasks // Proceedings of 14th Euromicro Conference on Real-Time Systems. ECRTS-02. Vienna: 2002. P. 165-172.