Scheduling algorithm for delay and jitter reduction of periodic tasks in real-time systems

• Autorzy: Martyna J.

Warianty tytułu

PL

Algorytm szeregowania dla redukcji fluktuacji i opóźnień zadań okresowych w systemach czasu rzeczywistego

• Języki publikacji: EN

Abstrakty

EN

Real-time systems, especially software control systems, are developed to meet the requirements of real-time automation systems. One such crucial requirement is reducing the delay and jitter of periodic tasks in such systems. In this paper, we present a new method for reducing delays and jitters of periodic tasks, which are enforced by the operating system, control tasks, kernel mechanisms, etc. Our algorithm is evaluated and compared with other scheduling algorithms in terms of jitter. The effectiveness of our algorithm is confirmed by the experimental results.

PL

W pracy przedstawiono algorytm szeregowania dla redukcji fluktuacji i opóźnień zadań okresowych w systemach czasu rzeczywistego. Zastosowanie takiego algorytmu gwarantuje przewidywalność oraz poprawia efektywność działania systemów. Dodatkowo dzięki niemu jest możliwe zmniejszenie fluktuacji czasu odpowiedzi zadań okresowych. Możliwości działania prezentowanego algorytmu zostały potwierdzone w badaniach symulacyjnych.

Słowa kluczowe

EN

scheduling algorithms; real-time systems; periodic tasks; reducing the delay of periodic tasks; reducing the jitter of periodic tasks

PL

algorytmy szeregujące; systemy czasu rzeczywistego; redukcja fluktuacji zadań okresowych; redukcja opóźnień zadań okresowych

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2011
• Tom: R. 87, nr 1
• Strony: 236--239
• Opis fizyczny: Bibliogr. 19 poz., rys.

Twórcy

autor

Martyna J.

• Institute of Computer Science, The Faculty of Mathematics and Computer Science, Jagiellonian University, ul. Prof. S. Łojasiewicza 6, 30-348 Kraków,

Bibliografia

• [1] Balbastre P., Ripoll I., Crespo A.,: Optimal Deadline Assignment for Periodic Real-Time Dynamic Priority Systems, Proc. of of the 18th Euromicro Conference on Real-Time Systems, Dresden, Germany, pp. 65 – 74, 2006.
• [2] Baruah S., Buttazzo G.C., Gorinsky S., Lipari G., Scheduling Periodic Task Systems to Minimize Output Jitter, Proc. of the 6th IEEE Int. Conference on Real-Time Computing Systems and Applications, Hong Kong, pp. 62 – 69, Dec. 1999.
• [3] Bini E., Buttazzo G.C., Schedulability Analysis of Periodic Fixed Priority Systems, IEEE Trans. on Computers, 53(11), pp. 1462 – 1473, 2004.
• [4] Bini E., Di Natale M., Optimal Task Rate Selection In Fixed Priority Systems, in: Proc. of the 26th IEEE Real-Time Systems Symposium, Miami, USA, 399 - 409, 2005.
• [5] Bini E., Di Natale M., Buttazzo G., Sensitivity Analysis for Fixed-Priority Real-Time Systems, Real-Time Systems, 39, pp. 5 – 30, 2008.
• [6] Buttazzo G.C., Sensini F., Optimal Deadline Assignment for Scheduling Soft Aperiodic Task in Hard Real-Time Environments, IEEE Trans. on Computers, 48(10), pp. 1035 – 1052, 1999.
• [7] Buttazzo G.C., Cervin A., Comparative Assessment and Evaluation of Jitter Control Method, in: Proc. of the 15th Int. Conf. on Real-Time and Network Systems, Nancy, France, March 29 - 30, 2007.
• [8] Cervin A., Integrated Control and Real-Time Scheduling, Ph. D. Thesis, ISRN LUTFD2/TFRT-1065-SE, Dept. Of Automatic Control, Lund, Sweden, 2003.
• [9] Cervin A., Lincoln B., Eker J., Arzn K.-E., Buttazzo G.C., The Jitter Margin and Its Application in the Design of Real-Time Control Systems, Proc. of the 10th Int. Conf. on Real-Time and Embedded Computing Systems and Applications (RTCSA 2004), Gotheborg, Sweden, Aug. 25 – 27, pp. 1 – 9, 2004.
• [10] Di Natale M., Stankovic J., Scheduling Distributed Real-Time Tasks with Minimum Jitter, IEEE Trans. on Computers, 49(4), pp. 303 – 316, 2000.
• [11] Hamdaoui M., Ramanathan P., A Dynamic Priority Assignment Technique for Streams with (m, k)-Firm Guarantees, IEEE Trans. on Computers, 44(12), pp. 1443 – 1451, 1995.
• [12] Hoang H., Buttazzo G.C., Jonsson M., arlsson S., Computing the Minimum EDF Feasible Deadline in Periodic Systems, Proc. of the 12th IEEE Int. Conference on Embedded and Real-Time Computing Systems and Applications, Sydney, Australia, pp. 125 – 134, Aug. 2006.
• [13] Hoang H., Buttazzo G.C., Reducing Delay and Jitter in Software Control Systems, Proc. of the 15th Int. Conference on Real-Time and Network Systems, Nancy, March 29 - 30, 2007.
• [14] Kwiecień A., Sidzina M., Some Methods for Reduction of Cycle in Free-programmable Controllers and Their Basic Studies, Real-Time Systems, 2, Warszawa: Wydawnictwa Komunikacji i Łączności, pp. 85 – 98, 2005 (In Polish).
• [15] Liu C.L., Layland J.W., Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment, Journal of the Association for Computing Machinery, 20(1), pp. 46 – 61, 1973.
• [16] Marti P., Analysis and Design of Real-Time Control Systems with Varying Control Timing Constraints, Ph. D. Thesis, Dept. of Automatic Control, Technical University, Barcelona, Spain, 2002.
• [17] Michelon Ph., Quadri D., Negreiros M., On a Class of Periodic Scheduling Problems: Models, Lower Bounds and Heuristics, Proc. of the Int. Multiconference on Computer Science and Information Technology, 3, pp. 899 – 906, 2008.
• [18] Nilsson J., Bernhardsson B., Wittenmark B., Stochastic Analysis and Control of Real-Time Systems with Random Time Delays, Automatica, 34(1), pp. 57 – 64, 1998.
• [19] Shin I., Lee I., Compositional Real-Time Scheduling Framework with Periodic Model, ACM Trans. on Embedded Computing Systems, 7(3), pp. 30:1 – 30:39, 2008.