Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: binaryzacja okresów zadań

Sortuj według:

Ogranicz wyniki do:

Zastosowanie binaryzacji okresów zadań w systemach wieloprocesorowych

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

2006

Vol. 52, z. 4

545-561

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.

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.

Adaptacja algorytmu rate monotonic scheduling dla architektur wieloprocesorowych

Gajer M., Handzel Z.

Informatyka Teoretyczna i Stosowana

2005

R. 5, nr 8

95-105

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.

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.