Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

• Autorzy: Gajer M.

Warianty tytułu

EN

The application of binarisation of tasks periods in multiprocessor systems

• Języki publikacji: PL

Abstrakty

PL

Artykuł dotyczy zastosowania techniki binaryzacji okresów zadań w systemach wieloprocesorowych. Binaryzacja okresów zadań jest techniką polegającą na takiej transformacji wartości okresów zadań periodycznych, aby były wielokrotnościami (będącymi naturalną potęga liczby 2) pewnego okresu bazowego r. Zatem w systemie o okresach binarnych szeregowaniu podlegają zadania o wartościach okresów r, 2r, 4r, 8r, 16r, 32r itd. Binaryzacja okresów zadań ułatwia znalezienie ich planu szeregowania, gwarantującego dotrzymanie ograniczeń czasowych przez wszystkie zadania. Binaryzacja jest stosowana powszechnie w systemach czasu rzeczywistego o ostrych ograniczeniach czasowych. Obecnie binaryzacji wartości okresów podlegają głównie zadania przeznaczone do realizacji w systemach jednoprocesorowych. Artykuł niniejszy stanowi propozycję rozszerzenia obszaru stosowalności techniki binaryzacji okresów zadań na systemy zbudowane z większej liczby jednostek obliczeniowych. Zgodnie z propozycją autora zastosowanie binaryzacji okresów zadań wieloprocesorowych stanowi klucz do zastosowania do ich szeregowania popularnego algorytmu Rate Monotonie Scheduling. Przedstawione w artykule rozważania teoretyczne zostały zilustrowane przykładem szeregowania zadań wieloprocesorowych o okresach binarnych dla systemu zbudowanego z czterech jednostek obliczeniowych.

EN

Nowadays the real-time systems find application in many branches of industry, science and transport. The most important factor in the real-time systems is the time of execution of tasks. The results that are correct but delivered with the violation of task deadline are useless. In the case of hard real-time systems the violation of task deadline can lead to a catastrophe or even loss of human life. This is the reason why the task scheduling theory developed strongly over the last years. In the computer systems with hard real-time constraints the most popular task scheduling algorithm is Rate Monotonie Scheduling (RMS). In RMS all tasks are assigned priorities. The rule is the shorter is task period the higher priority the task obtains. In a given moment the task that is read for execution and has the highest priority is executed. If any other task with higher priority arrives the task that is executed is pre-empted and the task that came is then executed. Together with RMS binarisation is often used. Binarisation is a technique that transforms the periods of tasks in the way that only tasks with harmonic values of periods exist. Up till now binarisation was used only for a uniprocessor systems. This author proposed a new solution in which binarisation is used for multiprocessor systems as well. Scheduling and allocation of multiprocessor tasks in a multiprocessor system is NP - complete optimisation problem. This is the reason why the optimal solution for scheduling of multiprocessor task can not be found in a reasonable time. In such case only suboptimal solutions can be found. This author proposed evolutionary algorithm as a solution to multiprocessor tasks allocation and scheduling. The way in which the order of execution of task is coded on the genetic material was illustrated on the example of scheduling the tasks for four processor systems. The genetic material also allows to code the way in which the proper binarisation is chosen. There are very few tasks scheduling algorithms that could be used for a general class of tasks. There are different scheduling algorithms for uniprocessor task and multiprocessor task and for tasks that are executed on arbitrary or dedicated processors. The algorithm of tasks scheduling and allocation that was proposed by this author is a general one, because it can be used for uniprocessor and multiprocessor tasks and for dedicated, arbitrary and partially arbitrary processors.

Słowa kluczowe

PL

binaryzacja okresów zadań; systemy wieloprocesorowe; zadania wieloprocesorowe; szeregowanie zadań

EN

binarisation of periods of tasks; multiprocessor systems; multiprocessor tasks; tasks scheduling

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2006
• Tom: Vol. 52, z. 4
• Strony: 545--561
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Gajer M.

• Katedra Automatyki AGH, al. Mickiewicza 30, 30-059 Kraków,

Bibliografia

• 1. T. Szmuc, G. Motet: Specyfikacja i projektowanie oprogramowania czasu rzeczywistego, Centrum Informatyki Stosowanej, Kraków, 1998.
• 2. J. Werewka, T. Szmuc: Analiza i projektowanie systemów czasu rzeczywistego o różnym stopniu rozproszenia, Polskie Towarzystwo Informatyczne - Oddział Małopolski, Kraków, 2001.
• 3. T. Szmuc: Zaawansowane metody tworzenia oprogramowania czasu rzeczywistego, Krakowskie Centrum Informatyki Stosowanej, Kraków, 1998.
• 4. T. Szmuc: Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego, AGH - Uczelniane Wydawnictwa Naukowo-Dydaktyczne, Kraków, 2001.
• 5. J. Miloško, E. Kotov: Algorithms, software and hardware of parallel computers, VEDA - Publishing House of the Slovak Academy of Sciences, Bratislava 1984.
• 6. O. Kwon, K.Y. Chwa: Approximation algorithms for general parallel task scheduling, Information Processing Letters 81 (2002), pp. 143-150.
• 7. A. Czajka, J. Nawrocki: Szeregowanie zadań o okresach binarnych w systemach silnie uwarunkowanych czasowo, I Krajowa Konferencja Metody i systemy komputerowe w badaniach naukowych i projektowaniu inżynierskim, Kraków, 1997, ss. 669-676.
• 8. J. Nawrocki, A. Czajka: Binaryzacja okresów zadań cyklicznych, VII Konferencja Systemy Czasu Rzeczywistego, Kraków, 2000, ss. 41-51.
• 9. J. Werewka: Zagadnienia alokacji zadań w rozproszonych systemach czasu rzeczywistego, Elektrotechnika, Tom 14, Zeszyt 4, 1995, ss. 479-488.
• 10. C. Hsueh, K.J. Lin: Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model, IEEE Transaction on Computers, vol. 50, no 1, 2001, ss. 51-68.
• 11. O.H. Kwon, K.Y. Chwa: Approximation algorithms for general parallel task scheduling, Information Processing Letters, 81, 2002, ss. 143-150.
• 12. D. Ye, G. Zhang: On-line scheduling with extendable working time on a small number of machines, Information Processing Letters 85, 2003, ss. 171-177.
• 13. J.H. Kim, K.Y. Chwa: Online deadline scheduling on faster machines, Information Processing Letters 85, 2003, ss. 31-37.
• 14. K.G. Shin, P. Ramanathan: Real-time computing: A new discipline of computer science and engineering, Proceedings of the IEEE, vol. 82, no 1, January 1994, pp. 6-24.
• 15. L. Liu, J.W. Layland: Scheduling algorithms for multiprogramming in a hard real time environment, Journal on Assoc. Comput. Mach., vol. 20, no 1, 1973, pp. 46-61.
• 16. T. Stoyenko, P. Baker: Real-time schedulability-analyzable mechanizms in Ada9X, Proceedings of the IEEE, vol. 82, no 1, January 1994, pp. 95-107.
• 17. K. Ramanathan, J.A. Stankovic: Scheduling algorithms and operating systems support for real-time systems, Proceedings of the IEEE, vol. 82, no 1, January 1994, pp. 55-67.
• 18. A. Zalewski: What every engineer needs to know about rate monotonic scheduling: A tutorial, Odessa, TX, 1995, pp. 321-335.
• 19. S. Tanenbaum: Rozproszone systemy operacyjne, PWN, Warszawa, 1997.