Wyniki wyszukiwania - BazTech

1

Pareto-optymalne szeregowanie zadań wieloprocesorowych na procesorach dedykowanych

Obszarski P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

79-84

PL

Problem szeregowania jednostkowych zadań wieloprocesorowych na maszynach dedykowanych można modelować za pomocą hipergrafów. Znamy kilka klas hipergrafów, dla których szeregowanie z kryterium kosztu całkowitego jest wielomianowe. Pokażemy, jak za pomocą modelu z kosztem całkowitym można rozwiązać problemy z innymi kryteriami znanymi z teorii szeregowania oraz jak rozwiązać problemy dwukryterialne.

EN

Problem of scheduling multiprocessor tasks on dedicated machines can be modeled by hypergraphs. There are a few classes of hypergraphs for which polynominal time algorithms for scheduling with total cost criterion are known. Our aim is to show that other criteria and also bicriterial problems can be solved by the use of total cost criterion.

2

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.

3

Wybrane zagadnienia szeregowania zadań wieloprocesorowych dla dedykowanych procesorów

Gajer M.

Kwartalnik Elektroniki i Telekomunikacji

|

2003

|

Vol. 49, z. 2

163-173

PL

Systemy czasu rzeczywistego stanowią obecnie dobrze określoną i wyodrębnioną grupę systemów komputerowych. W systemach takich najważniejszą sprawą jest dochowywanie nałożonych na realizację zadań ograniczeń czasowych. Spełnienie wymogów czasowych wymusza często konieczność zastosowania w miejsce sekwencyjnych procesorów systemów wieloprocesorowych, które są w stanie dostarczyć wymaganego poziomu pracy obliczeniowej. Jednakże zastosowanie rozwiązań wieloprocesorowych powoduje konieczność rozwiązania niełatwego problemu szeregowania zadań wieloprocesorowych. W artykule po wstępnym wprowadzeniu w problematykę szeregownia zadań wieloprocesorowych, dokonano szczegółowej analizy przypadku szeregowania zadań wieloprocesorowych dla czterech dedykowanych procesorów. Rozważania teoretyczne zostały uzupełnione o wyniki symulacji komputerowych.

EN

In many modern computer systems multiprocessor solutions are more often applied. This concerns especially computer systems that are used in the real-time applications. At present the real-time systems constitute the well-defined class of computer systems. The real-time systems are getting more and more popular in many fields of industry and communication. The real-time systems are used to control telecommunication devices and systems, defense systems, avionics and modern factories. In fact many modern facilities cannot do without them. For example without the real-time systems there would be no nuclear power plants, space ships, jet aircrafts, modern factories with robots etc. The program realized by the real-time computer systems is divided into special tasks performing given functions. In the case of the real-time systems a very important matter is to guarantee that all the task are to be finished before their deadline points. In the case of the hard real-time systems any exceeding task deadline is absolutely intolerable. Such event if happens may lead to uncontrollable behavior of the system, which can cause a disaster, for example an aircraft carsh, a loss of human life etc. To guarantee that the task deadlines will be always met, the task scheduling theory was developed. The main goal of the task scheduling theory is to demonstrate at the system development phase that under all the possible to foreseen circumstances the task deadlines will always be met. There does not exist one universal task scheduling algorithm for all kinds of task. There are separate algorithms for periodic tasks and tasks that are event-triggered. Also there are different algorithms for tasks that are preemptive and for tasks that are not preemptive. There exist also quite different algorithms for tasks that are dedicated for one processor only and for so-called multiprocessor tasks that require for their execution two or more processor at the time. As was earlier mentioned in the case of the real-time systems the most important factor is whether the tasks meet the predefined time constraints. In order to meet the hard time constraints cery often a multiprocessor system is used in stead of a sequential system with only one processor. The multiprocessor system is expected to deliver much more computational power than a single processor system, however, the usage of a multiprocessor system requires simultaneously to solve a non-easy problem of multiprocessor task scheduling. In the paper a brif introduction to the problems of multiprocessor task scheduling is given. Further the case of scheduling a set of independent multiprocessor tasks for four dedicated processors is examined. Multiprocessor systems with four processors are very popular at the present time. For example the Texas Instruments TMS320C80 is a single-chip multiprocessor system composed of four DSP processors. Earlier Texas Instruments offered a personal computer boards with four TMS320C40 processors. The proposed algorithm of multiprocessor task scheduling was called a Divide Uniprocessor Task (DUT) algorithm, because all the tasks dedicated for a single processor are grouped together and then the whole set is divided into two subsets, one of which has the length as close as possible to the execution time of compatible tasks dedicated for orther three processors. In the paper the process of multiprocessor task scheduling is illustrated with examples and the results of computer simulations are also presented.