Wyniki wyszukiwania - BazTech

1

Zastosowanie algorytmu Rate Monotonic Scheduling do szeregowania zadań w architekturach wieloprocesorowych o topologii hipersześcianu

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 2

141-152

PL

Artykuł stanowi propozycję rozszerzenia obszaru stosowalności popularnego algorytmu szeregujące zadania Rate Monotonic Scheduling (RMS) na przypadek zadań 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. Autor skupił swoją uwagę na architekturach 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, dzięki czemu stanowi jedno z bardziej popularnych rozwiązań wieloprocesorowych. Zaproponowane przez autora zastosowanie klasycznego algorytmu RMS do szeregowania zbioru zadań realizowanych w systemie równoległym o topologii hipersześcianu, polega na transformacji wartości okresów niektórych z zadań. W wyniku rozważanej transformacji wybrane zadania uzyskują identyczne wartości swoich 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 superzadania można potraktować w taki sam sposób, w jaki traktuje się zadania jednoprocesorowe, czyli można już bezpośrednio zastosować algorytm RMS. Zaprezentowana w artykule propozycja modyfikacji algorytmu RMS została zilustrowana na wybranym przykładzie szeregowania zadań dla systemu wieloprocesorowego o topologii hipersześcianu czterowymiarowego.

EN

The real-time systems are getting more and more popular. In fact most of contemporary industrail and communication systems could not do without them. The popularity 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 that are 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 proposed a new method of adaptation of Rate Monotonic Scheduling theory also for the purpose of scheduling multiprocessor tasks in the multiprocessor architectures of the topology of hypercube. The clue of the method proposed by this author is concatenation of many uniprocessor and multiprocessor tasks that should form one so called supertask. 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 of the same value of period should be made. Then each subset of tasks is treated as a uniprocesor supertask and for the set of such 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 the multiprocessor system of the topology of hypercube of dimension 4. The method can be easily extended for the higher dimensions of hypercube multiprocessor architectures.

2

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

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 1

73-87

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.

3

Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2005

|

Vol. 51, z. 3

373--385

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.

4

Adaptacja algorytmu rate monotonic scheduling dla architektur wieloprocesorowych

Gajer M., Handzel Z.

Informatyka Teoretyczna i Stosowana

|

2005

|

R. 5, nr 8

95-105

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.