Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

• Autorzy: Gajer M.

Warianty tytułu

EN

The adaptation of rate monotonic scheduling algorithm for scheduling of multiprocessor tasks

• Języki publikacji: PL

Abstrakty

PL

Artykuł niniejszy poświęcony został zagadnieniom związanym z szeregowaniem jed-noprocesorowych i wieloprocesorowych zadań dla systemu komputerowego zbudowanego z pewnej liczby procesorów. W systemach czasu rzeczywistego o ostrych ograniczeniach czasowych (ang. hard real-time systems) bardzo często występuje konieczność znalezienia planu szeregowania zbioru niezależnych i wywłaszczalnych zadań periodycznych. Ponadto zwykle już na etapie projektowania systemu należy wykazać w sposób formalny, że ograniczenia czasowe będą zawsze zachowane dla wszystkich zadań. W tym celu w przypadku zadań jednoprocesorowych powszechnie wykorzystywany jest algorytm RMS (ang. Rate Monotonic Scheduling) oraz związane z nim formalne metody dowodzenia szeregowalności zbioru zadań. Autor niniejszego artykułu zaproponował rozszerzenie zakresu stosowalności algorytmu RMS również dla przypadku zadań wieloprocesorowych. Podejście zaproponowane przez autora bazuje na konkatenacji zadań jedno- i wieloprocesorowych oraz na transformacji wartości okresów wybranych zadań. W artykule rozważono zarówno przypadek zbioru zadań przeznaczonych dla procesorów arbitralnych, jak i dedykowanych.

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 is adequate for scheduling uniprocessor tasks. This author has not known so far any method of adaptation of Rate Monotonic Scheduling theory for the purpose of scheduling multiprocessor tasks. According with this author's knowledge the proposed by himself method of scheduling of the set of uniprocessor and multiprocessor tasks is the first method of the kind and thus has totally pioneer character. The clue of the method proposed by this author is concatenation of uniprocessor and multiprocessor 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 several subsets of tasks are made. Then each subset of tasks is treated as a uniprocesor task and for the set of such tasks (called by this author supertasks) 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 three dedicated processors. The method can be easily extended both for the case of greater number of processors and for the systems with arbitrary processors.

Słowa kluczowe

PL

szeregowanie zadań; Rate Monotonic Scheduling; systemy wieloprocesorowe; zadania wieloprocesorowe

EN

task scheduling; Rate Monotonic Scheduling; multiprocessor systems; multiprocessor task

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2005
• Tom: Vol. 51, z. 3
• Strony: 373--385
• Opis fizyczny: Bibliogr. 12 poz., tab.

Twórcy

autor

Gajer M.

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

Bibliografia

• 1. T. Szmuc: Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego. Uczelniane Wydawnictwa Naukowo-Dydaktyczne AGH, Kraków, 2001.
• 2. 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.
• 3. 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.
• 4. T. Stoyenko, P. Baker: Real-time schedulability-analyzable mechanizms in Ada9X.. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 95-107.
• 5. 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.
• 6. A. Zalewski: What every engineer needs to know about rate monotonic scheduling: A tutorial. Odessa, TX, 1995, pp. 321-335.
• 7. A. S. Tanenbaum: Rozproszone systemy operacyjne. PWN, Warszawa, 1997.
• 8. J. Varriet: Scheduling inverted-ordered task with non- uniform deadlines subject tonon-zero-communication delay. Parallel Computing 25 (1999), pp. 3-21.
• 9. O. Kwon, K. Y. Chwa: Approximation algorithms for general parallel task scheduling. Information Processing Letters 81 (2002), pp. 143-150.
• 10. 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.
• 11. J. Nawrocki, A. Czajka: Binaryzacja okresów zadań cyklicznych. VII Konferencja Systemy Czasu Rzeczywistego, Kraków, 2000, ss. 41-51.
• 12. K. Wale: How VМЕ facilitates the implementation of real-time DSP systems. Real Time Magazine, 1/1997, pp. 21-28.