Szeregowanie niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych dla trzech procesorów

• Autorzy: Gajer M.

Warianty tytułu

EN

The scheduling of independent, pre-emptive, and periodic multiprocessor tasks for three processors

• Języki publikacji: PL

Abstrakty

PL

W artykule poruszono tematykę szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych przeznaczonych do realizacji w systemie wieloprocesorowym zbudowanym z trzech procesorów. Rozważane zadania niezależne, wywłaszczalne i periodyczne stanowią najbardziej popularną klasę zadań występujących w komputerowych systemach czasu rzeczywistego. Do szeregowania zbioru tego typu zadań wykorzystywany jest najczęściej algorytm RMS (ang. Rate Monotonic Scheduling). Równie często stosowaną techniką w połączeniu z algorytmem RMS jest binaryzacja okresów zadań, mająca na celu skrócenie długości horyzontu czasowego systemu. Dotychczas algorytm RMS stosowany był wyłącznie do szeregowania zadań jednoprocesorowych. Natomiast autorowi artykułu nic nie jest wiadomo o próbach zastosowania algorytmu RMS do szeregowania zadań wieloprocesorowych. Stąd artykuł niniejszy stanowi propozycję takiej modyfikacji algorytmu RMS, która pozwoliłaby na jego zastosowanie również do szeregowania zadań wieloprocesorowych. Zamieszczone w artykule rozważania zostały zilustrowane na przykładzie szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań wieloprocesorowych przeznaczonych dla trzech procesorów. Rozważono zarówno przypadek procesorów dedykowanych, jak i arbitralnych.

EN

At the present moment real-time systems constitute a well-defined and separate class of computer systems. There exist three main factors that make the real-time systems to be totally different from the so-called general-purpose computer systems. First of all in the case of real-time systems the time of computations is the most precious resource, which must be used with a lot of care and attention. Even if the results of computations are correct but they are delivered too late, they are of no value in reat-time system with hard time constraints. Second, any time constraint violation can make the controlled system unstable and thus can cause a catastrophe leading to great economic losses. And last but not least, real-time systems are in most cases integrated very closely with the object being controlled. All these factors cause the necessity of formal analysis of real-time systems before they are put into operations. It must be proved that real-time systems will behave in a deterministic way under any possible conditions and in all the possible scenarios of its work. This necessity of formal analysis of real-time systems has caused the development of task scheduling theory and mathematical methods that allow prove in a formal way that time constraint will be met for each task under any circumstances. The topic of the paper is about scheduling of the set of independent, pre-emptive, and periodic multiprocessor tasks that are to be performed in a multiprocessor system. Such independent, pre-emptive, and periodic tasks constitute the most popular class of the tasks that are to be met in real-time computer systems. In most cases the Rate Monotonic Scheduling (RMS) algorithm is used in order to schedule such set of tasks. The rules of RMS algorithm are as follows: * Each task is assigned a priority * The shorter is the period of task the higher priority is assigned to that task * In every moment only the task with the highest priority from all the tasks that are ready for execution is performed * The task can be pre-emptied by any other task with a higher priority always when such a task enters into a ready state * The pre-emptied task can be resumed only when there is no other task with a higher priority that is ready for the execution Very often a binarisation of the periods of tasks is used together with the RMS algorithm. The purpose of this is to make shorter the time horizon of the scheduled set of tasks. The time horizon is the least common multitude of the periods of all tasks. The binarisation of the periods of tasks transforms the periods in such a way that they are the multitudes of some base period. Only the multitudes that are the powers of two are allowable. According with this author knowledge, the RMS algorithm has been applied only for tasks that are executed on a single processor up till now. This author has found nothing about the trials of implementing the RMS algorithm also for scheduling multiprocessor tasks. The paper is a proposition of new approach in which the RMS algorithm is modifield in such a way that it can also been applied for the purpose of scheduling a set of multiprocessor independent, pre-emptive, and periodic tasks. The proposition of using the RMS algorithm for multiprocessor task scheduling is the following. At the beginning the binarisation of the periods of tasks is performed. Then the tasks are concatenated into so called supertasks in such a way so that the total execution time of the supertasks was as short as possible. In the next step the supertasks are treated as normal uniprocessor tasks, so the RMS algorithm can be directly applied. In the paper both the case of task for dedicated processors and for arbitrary processors is considered. These are illustrated by the scheduling of an example multiprocessor task set.

Słowa kluczowe

PL

szeregowanie zadań; zadania wieloprocesorowe; system czasu rzeczywistego; systemy wieloprocesorowe

EN

task scheduling; multiprocessor tasks; real-time systems; multiprocessor systems

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2004
• Tom: Vol. 50, z. 2
• Strony: 231--249
• 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. Krakowskie Centrum Informatyki Stosowanej , Kraków, 1998.
• 2. T. Szmuc, G. Motet: Programowanie systemów czasu rzeczywistego. Krakowskie Centrum Informatyki Stosowanej , Kraków, 2000.
• 3. T Szmuc: Zaawansowane metody tworzenia oprogramowania systemów czasu rzeczywistego. Krakowskie Centrum Informatyki Stosowanej , Kraków, 1998.
• 4. T. Szmuc: Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego. Uczelniane Wydawnictwa Naukowo-Dydaktyczne AGH, Kraków, 2001.
• 5. 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.
• 6. K. Ramamrilham, 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.
• 7. Zalewski: What every engineer needs to know about rate-monotonic schecheding: A tutorial. Department of Computer Science, The University of Texas of the Permian Basin, Odessa, TX, 1995, pp. 321-335.
• 8. S. Tanenbaum: Rozproszone systemy operacyjne. Wydawnictwo Naukowe PWN, Warszawa, 1997.
• 9. 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, pp. 669-676.
• 10. J. Nawrocki, A. Czajka: Binaryzacja okresów zadań cyklicznych. VII Konferencja Systemy Czasu Rzeczywistego, Kraków, 2000, ss. 41-51.
• 11. W. Hsueh, K. J. Lin: Scheduling real-time systems with·end-to-end timing constraints using the distributed pinwheel model. IEEE Transactions on Computers, vol. 50, no. 1, January, 2001, pp. 51-67.
• 12. O. Kwon, K. Y. Chwa: Approximation algorithms for general parallel task scheduilng. Information Processing Letters 81 (2002), pp. 143-150.
• 13. J. Verriet: Schecheduling interval-ordered task with non-uniform deadlines subject to non-zero communication delays. Parallel Computing 25, 1999, pp. 3-21.
• 14. R. H. Möhring, M. W. Schäffter: Scheduling series-parallel orders subject 0/1-communication delays. Parallel Computing 25, 1999, pp. 23-40.
• 15. A. Munier: Approximation algorithms for scheduling trees with general communication delays. Parallel Computing 25, 1999, pp. 41-48.
• 16. K. Amoura, E. Bampis, Y. Manoussakis, Z. Tuza: A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors. Parallel Computing 25, 1999, pp. 49-61.
• 17. C. Boeres, V. E. F. Rebello: A versatile cost modeling approach for multicomputer task scheduling. Parallel Computing 25, 1999, pp. 63-86.
• 18. J. Błażewicz, M. Drozdowski, M. Markiewicz: Divisible task scheduling - Concept and verification. Parallel Computing 25, 1999, pp. 87-98.
• 19. Z. Kowalczuk: Ewolucyjna optymalizacja wielokryterialna w automatyce i diagnostyce. AUTOMATION 2003, Konferencja Naukowo-Techniczna Automatyzacja-Nowości i Perspektywy, Warszawa, 2-4 kwietnia 2003, pp. 23-38.