Wyniki wyszukiwania - BazTech

1

Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2006

|

Vol. 52, z. 4

545-561

PL

Artykuł dotyczy zastosowania techniki binaryzacji okresów zadań w systemach wieloprocesorowych. Binaryzacja okresów zadań jest techniką polegającą na takiej transformacji wartości okresów zadań periodycznych, aby były wielokrotnościami (będącymi naturalną potęga liczby 2) pewnego okresu bazowego r. Zatem w systemie o okresach binarnych szeregowaniu podlegają zadania o wartościach okresów r, 2r, 4r, 8r, 16r, 32r itd. Binaryzacja okresów zadań ułatwia znalezienie ich planu szeregowania, gwarantującego dotrzymanie ograniczeń czasowych przez wszystkie zadania. Binaryzacja jest stosowana powszechnie w systemach czasu rzeczywistego o ostrych ograniczeniach czasowych. Obecnie binaryzacji wartości okresów podlegają głównie zadania przeznaczone do realizacji w systemach jednoprocesorowych. Artykuł niniejszy stanowi propozycję rozszerzenia obszaru stosowalności techniki binaryzacji okresów zadań na systemy zbudowane z większej liczby jednostek obliczeniowych. Zgodnie z propozycją autora zastosowanie binaryzacji okresów zadań wieloprocesorowych stanowi klucz do zastosowania do ich szeregowania popularnego algorytmu Rate Monotonie Scheduling. Przedstawione w artykule rozważania teoretyczne zostały zilustrowane przykładem szeregowania zadań wieloprocesorowych o okresach binarnych dla systemu zbudowanego z czterech jednostek obliczeniowych.

EN

Nowadays the real-time systems find application in many branches of industry, science and transport. The most important factor in the real-time systems is the time of execution of tasks. The results that are correct but delivered with the violation of task deadline are useless. In the case of hard real-time systems the violation of task deadline can lead to a catastrophe or even loss of human life. This is the reason why the task scheduling theory developed strongly over the last years. In the computer systems with hard real-time constraints the most popular task scheduling algorithm is Rate Monotonie Scheduling (RMS). In RMS all tasks are assigned priorities. The rule is the shorter is task period the higher priority the task obtains. In a given moment the task that is read for execution and has the highest priority is executed. If any other task with higher priority arrives the task that is executed is pre-empted and the task that came is then executed. Together with RMS binarisation is often used. Binarisation is a technique that transforms the periods of tasks in the way that only tasks with harmonic values of periods exist. Up till now binarisation was used only for a uniprocessor systems. This author proposed a new solution in which binarisation is used for multiprocessor systems as well. Scheduling and allocation of multiprocessor tasks in a multiprocessor system is NP - complete optimisation problem. This is the reason why the optimal solution for scheduling of multiprocessor task can not be found in a reasonable time. In such case only suboptimal solutions can be found. This author proposed evolutionary algorithm as a solution to multiprocessor tasks allocation and scheduling. The way in which the order of execution of task is coded on the genetic material was illustrated on the example of scheduling the tasks for four processor systems. The genetic material also allows to code the way in which the proper binarisation is chosen. There are very few tasks scheduling algorithms that could be used for a general class of tasks. There are different scheduling algorithms for uniprocessor task and multiprocessor task and for tasks that are executed on arbitrary or dedicated processors. The algorithm of tasks scheduling and allocation that was proposed by this author is a general one, because it can be used for uniprocessor and multiprocessor tasks and for dedicated, arbitrary and partially arbitrary processors.

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

Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych

Giaro K., Kubale M.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2005

|

T. 9, z. 1-2

85-94

PL

W artykule rozważono rozrzedzone systemy niepodzielnych zadań 1- i 2-procesorowych o jednostkowych czasach wykonywania. Przedstawiono wielomianowe algorytmy wykorzystujące programowanie dynamiczne, pozwalające na znalezienie optymalnego uszeregowania względem szerokiej rodziny funkcji kryterialnych. Stopień rozrzedzenia systemu zdefiniowano, posługując się jego modelem grafowym - w zakresie naszego zainteresowania leżą jedynie takie instancje problemów szeregowania, których modelami są grafy o ograniczonej liczbie cyklomatycznej. Istotnym elementem opracowanych procedur są algorytmy rozwiązujące pewne zagadnienia związane z wyszukiwaniem skojarzeń w grafach.

EN

In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.

5

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

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2004

|

Vol. 50, z. 2

231-249

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.