Szeregowanie niezależnych, wywłaszczalnych zadań periodycznych jedno- i dwuprocesowych z wykorzystaniem metody super zadań

• Autorzy: Gajer M.

Warianty tytułu

EN

Scheduling the set of independent, pre-emptive and periodic uni-and biprocessor tasks with the application of the method of super tasks

• Języki publikacji: PL

Abstrakty

PL

Artykuł został poświęcony problematyce szeregowania zbioru niezależnych i wywłaszczalnych zadań periodycznych. Zadania o takich właściwościach należą do najbardziej rozpowszechnionych we wszelkiego rodzaju systemach czasu rzeczywistego o ostrych ograniczeniach czasowych. W literaturze przedmiotu zaproponowano wiele różnych algorytmów służących do generacji planów szeregowania rozważanych zadań, które są w stanie zagwarantować dotrzymanie ograniczenia czasowego przez każde z zadań podlegających szeregowaniu. Jednym z najpowszechniej stosowanych algorytmów szeregujących jest algorytm RMS (ang. Rate Monotonie Scheduling), który bazuje na priorytetach przypisywanych zadaniom w ten sposób, że zadania o krótszych wartościach okresu otrzymują wyższy priorytet. Pewnym ograniczeniem algorytmu RMS jest to, iż w swej klasycznej postaci nadaje się wyłącznie do szeregowania zadań przeznaczonych tylko dla jednego procesora. Tymczasem obecnie coraz większą popularność zaczynają zdobywać rozwiązania wieloprocesorowe. W związku z powyższym w artykule została przedstawiona propozycja rozszerzenia obszaru stosowalności algorytmu RMS, tak aby mógł posłużyć również do szeregowania zadań przeznaczonych dla dwóch procesorów. Autor zaproponował wykorzystanie algorytmu genetycznego w celu optymalizacji rozdziału zadań do poszczególnych procesorów, tak aby zapewnić jak najmniejsze obciążenie jednostki przetwarzającej dane, co zwiększa szansę na szeregowalność zbioru zadań.

EN

The popularity and ubiquity of real-time systems with hard real-time constraints forced the extensive development of task scheduling theory. In the case of real-time systems with hard real-time constraints it does not suffice that the task produces logically correct results but these results must be delivered within their time constraints. In such systems even logically correct results but delivered with the violation of their time constraints are totally useless. Moreover, the consequences of violation of time constraints can very often be quite severe and can cause the great economic losses and even losses of human lives, e.g. in the case of control systems of nuclear reactors, space ships etc. The main goal of the task scheduling theory is to prove at the stage of the system project that the time constraints for all tasks will always be met under any possible circumstances. In the case of the real-time systems with hard real-time constraints there is very often a necessity of scheduling a set of independent, pre-emptive and periodic tasks. The most popular algorithm for scheduling such set of independent, pre-emptive and periodic tasks is the Rate Monotonic Scheduling algorithm. In the case of Rate Monotonic Scheduling each task is assigned a priority. There are several rules basing on which the priorities are assigned to the tasks and then the tasks are being scheduled. First of all, the shorter the period of task is the higher priority it is assigned. Then, in a given moment, among all the tasks actually in a ready state the one is being executed that has the highest priority. If some task with higher priority enters into the ready state the task being executed is automatically pre-empted and the task with higher priority begins its execution. The pre-empted task can restart its execution only in the case if there is actually no other task with higher priority in the ready state. The Rate Monotonic Scheduling in its classical form is adequate only for scheduling uniprocessor tasks. This author has propsed a new method of adaptation of Rate Monotonic Scheduling in such a way that it should also be adequate for scheduling the sets of uni- and biprocessor tasks. The clue of the method proposed by this author is concatenation of uniprocessor tasks that form the so called biprocessor super tasks. In order to achieve this the periods of some tasks must be transformed, i.e. they must be shortened in such a way that a subset of uniprocessor tasks could be made. Then each subset of tasks is treated as a uniprocesor task and for the set of such tasks (called by this author super tasks) the Rate Monotonic Scheduling algorithm can be used directly. The method developed by this author was illustrated on the example of scheduling set of tasks for two arbitrary processors. The method can be easily extended both for the case of greater number of processors and for the systems with dedicated processors. For the purpose of finding the suboptimal schedule the use of genetic algorithm was proposed. The method of coding the solution on the genetic material was illustrated on the example.

Słowa kluczowe

PL

szeregowanie zadań; zadania wieloprocesorowe; algorytm szeregujący RMS

EN

task scheduling theory; Rate Monotonic Scheduling; multiprocessor tasks

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2006
• Tom: Vol. 52, z. 1
• Strony: 73--87
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Gajer M.

• Katedra Automatyki, Akademia Górniczo-Hutnicza, al. Mickiewicza 30, 30-059 Kraków,

Bibliografia

• 1. T. Szmuc: Zaawansowane metody tworzenia oprogramowania systemów czasu rzeczywistego, Krakowskie Centrum Informatyki Stosowanej, Kraków, 1998.
• 2. T. Szmuc: Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego, AGH - Uczelniane Wydawnictwa Naukowo-Dydaktyczne, Kraków 2001.
• 3. T. Szmuc, G. Motet: Specyfikacja i projektowanie oprogramowania czasu rzeczywistego, Krakowskie Centrum Informatyki Stosowanej, Kraków, 1998.
• 4. T. Czachórski: Modele kolejkowe w ocenie efektywności sieci i systemów komputerowych, Wydawnictwo Pracowni Komputerowej Jacka Skalmierskiego, Gliwice, 1999.
• 5. A. S. Tanenbaum: Rozproszone systemy operacyjne, Wydawnictwo Naukowe PWN, Warszawa, 1997.
• 6. 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.
• 7. K. Ramamritham, 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.
• 8. A. Zalewski: What every engineer needs to know about rate-monotonic scheduling: A tutorial. Department of Computer Science, The University of Texas Of the Permian Basin, Odessa, TX, 1995, pp. 321-335.
• 9. 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.
• 10. R. Negre: EUROPRO: A new open VMEbus multiprocessor computer for signal processing and intensive data processing. Real-Time Magazine, No 1/1997, pp. 16-20.
• 11. M. Gajer: Jak szybko może liczyć komputer? Wiadomości Elektrotechniczne, nr 12/2002, ss. 519-521
• 12. A. Kowalczuk: Ewolucyjna optymalizacja wielokryterialna w automatyce i diagnostyce AUTOMATION 2003, Konferencja Naukowo-Techniczna, Warszawa, 2-4 kwietnia 2003, ss. 23-38.
• 13. J. Werewka: Zagadnienia alokacji zadań w rozproszonych systemach komputerowych czasu rzeczywistego Elektrotechnika - Kwartalnik AGH, T. 14, z. 4, 1995, ss. 479-488
• 14. O. Kwon, K.Y. Chwa: Approximation algorithms for generał parallel task scheduling, Information Processing Letters 81 (2002), pp. 143-150.
• 15. C.L. Liu, J.W. Layland: Scheduling algorithms for multiprogramming in a hard real time environment Journal of Association of Computing Machines, vol. 20, No 1, 1973, pp. 46-61.