Adaptacja algorytmu rate monotonic scheduling dla architektur wieloprocesorowych

• Autorzy: Gajer M. , Handzel Z.

Warianty tytułu

EN

The adaptation of rate monotonic scheduling algorithm for multiprocessor architectures

• Języki publikacji: PL

Abstrakty

PL

Artykuł stanowi propozycję rozszerzenia obszaru stosowalności popularnego algorytmu szeregujące zadania Rate Monotonie Scheduling (RMS) dla architektur wieloprocesorowych. Dotychczas algorytm RMS wykorzystywany był do szeregowania zbioru niezależnych, wywłaszczalnych i periodycznych zadań przeznaczonych tylko dla jednego procesora. Rosnąca coraz bardziej popularność rozwiązań wieloprocesorowych wymusza dokonanie takiej adaptacji algorytmu RMS, aby algorytm ten nadawał się również do szeregowania zadań wieloprocesorowych. Artykuł poświęcony został architekturom wieloprocesorowych o topologii hipersześcianu. Topologia ta charakteryzuje się bardzo korzystnym stosunkiem liczby połączeń komunikacyjnych pomiędzy poszczególnymi jednostkami obliczeniowymi do maksymalnej długości drogi przesyłu komunikatu, co jest bezpośrednią przyczyną jej dużej i wciąż wzrastającej popularności. Zaproponowana przez autorów modyfikacja klasycznego algorytmu RMS, umożliwiająca jego implementację również dla przypadku szeregowania zbioru zadań realizowanych w systemie równoległym o topologii hipersześcianu, polega na dokonaniu binaryzacji okresów zadań. W wyniku binaryzacji wybrane zadania uzyskują identyczne wartości okresów, dzięki czemu mogą zostać połączone w jedno większe tzw. superzadanie, do realizacji którego wymagana jest jednoczesna dostępność wszystkich jednostek obliczeniowych występujących w systemie. Następnie zbiór superzadań może zostać potraktowany tak, jak zbiór zadań jednoprocesorowych, do realizacji których wymagana jest jednostka obliczeniowa specjalnego typu, tzn. taka, która stanowi klaster zbudowany z odpowiedniej liczby procesorów. Jednak z punktu widzenia programu szeregującego superzadania, wewnętrzna budowa jednostki obliczeniowej nie jest istotna, a szeregowane super zadania można potraktować w taki sam sposób, w jaki traktuje się zadania jednoprocesorowe, czyli można już bezpośrednio zastosować algorytm RMS.

EN

The real-time systems are getting more and more popular. In fact most of contemporary industrial and communi-cation systems could not do without them. The popularity of real-time systems with bard real-time constraints forced the extensive development of task scheduling theory. In the case of real-time systems with bard 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 su ch systems even logically correct results that are delivered with the violation of their time constraints are totally useless. Moreover, the consequences of violation of time constraints tan very often be quite severe and tan cause the great economic losses and even losses of human lives, e.g. in the case of controi systems of nuclear reac-tors, space ships etc. The main goal of the łask scheduling theory is to prove at the stage of the system project that the time eonstraints for all tasks will always be met under any possible circumstances. In the case of the real-time systems with bard real-time constraints there is very often a necessity of seheduling a set of independent, pre-emptive and periodic tasks. The most popular algorithm for scheduling such set of inde-pendent, pre-emptive and periodic tasks is the Rate Monotonie Scheduling (RMS) algorithm. The paper is the proposition of applying RMS in multiprocessor architectures. The architecture of hyper-cube was chosen because of its many useful properties. The method proposed by these authors consists on the binarization of the periods of tasks and grouping the tasks into task-clusters called supertasks. Then the supertasks are scheduled as if they were normał uniprocessor tasks, only hole hypercube architecture most be available in order to perform their execution. In the paper the method of tasks seheduling proposed by these authors were illustrated on the exampłe of seheduling 20 tasks for four dimensional hypercube.

Słowa kluczowe

PL

szeregowanie zadań; Rate Monotonie Scheduling; systemy wieloprocesowe; hipersześcian; binaryzacja okresów zadań

EN

task scheduling theory; Rate Monotonic Scheduling; binarization

• Wydawca: Wydawnictwo Politechniki Częstochowskiej
• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2005
• Tom: R. 5, nr 8
• Strony: 95--105
• Opis fizyczny: Bibliogr. 11 poz., rys., tab.

Twórcy

autor

Gajer M.

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

autor

Handzel Z.

• Wydział Zarządzania i Komunikacji Społecznej, Uniwersytet Jagielloński

Bibliografia

• [1] Szmuc T., Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego, Uczelniane Wydawnictwa Naukowo-Dydaktyczne AGH, Kraków, 2001.
• [2] Shin K.G., Ramanathan P., Real-time computing: A new discipline of computer science and engineering. Proceedings of them EE, vol. 82, no. 1, January 1994, pp. 6-24.
• [3] Liu L., Layland JW., Scheduling algorithms for multiprogramming in a hard real time environment Journal on Assoc. Comput. Mach., vol. 20, no. 1, 1973, pp. 46-61.
• [4] Stoyenko T., Baker P., Real-time schedulability-analyzable mechanizms in Ada9X. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 95-107.
• [5] Ramanathan K., Stankovic J.A., Scheduling algorithms and operating systems support for real time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 55-67.
• [6] Zalewski, What every engineer needs to know about rate monotonic scheduling: A tutorial. Odessa, TX, 1995, pp. 32 l-335.
• [7] Tanenbaum S., Rozproszone systemy operacyjne, PWN, Warszawa, 1997.
• [8] Varriet J., Scheduling inverted-ordered task with non-uniform deadlines subject to non-zero communication delay, Parallel Computing 25 (1999), pp. 3-21.
• [9] Kwon O., Chwa K.Y., Approximation algorithms for general parallel task scheduling, Information Processing Letters 81(2002), pp. 143-150.
• [10] Czajka A., Nawrocki J., 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] Czajka A., Nawrocki J., Binaryzacja okresów zadań cyklicznych, VII Konferencja Systemy Czasu Rzeczywistego, Kraków, 2000, Ss. 41-51.