Wybrane zagadnienia szeregowania zadań wieloprocesorowych dla dedykowanych procesorów

• Autorzy: Gajer M.

Warianty tytułu

EN

The chosen problems of multiprocessor task scheduling for dedicated processors

• Języki publikacji: PL

Abstrakty

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.

Słowa kluczowe

PL

szeregowanie zadań; systemy wieloprocesorowe; systemy czasu rzeczywistego

EN

task scheduling; multiprocessor systems; multiprocessor task; real-time system

• Wydawca: Wydawnictwo Naukowe PWN SA
• Czasopismo: Kwartalnik Elektroniki i Telekomunikacji
• Rocznik: 2003
• Tom: Vol. 49, z. 2
• Strony: 163--173
• Opis fizyczny: Bibliogr. 17 poz

Twórcy

autor

Gajer M.

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

Bibliografia

• 1. K. G. Shin, P. Ramanathan: Real-Time computing: A new discipline of computer science and engineering. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 6-24.
• 2. K. Ramamritham, J. A. Stankovic: Schedulig algorithms and operating systems support for real-time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 55-67.
• 3. L. Sha, R. Rajkumar, S. S. Sathaye: Generalized rate-monotonic scheduling theory: A framework for developing real-time systems. Proceedings of the IEEE, vol. 82, no. 1, January 1994, pp. 68-82.
• 4. J. Veriet: Scheduling interval-ordered tasks with non-uniform deadlines subject to non-zero communication delays. Parallel Computing 25 (1999), pp. 3-21.
• 5. R. H. Mohring, M. W. Schaffter: Scheduling series-parallel orders subject to O/1- communication delays. Parallel Computing 25 (1999), pp. 23-40.
• 6. Munier: Approximation algorithms for scheduling trees with general communication delays. Parallel Computing 25 (1999), pp. 41-48.
• 7. Boeres, V. E. F. Rebello: A versatile cost modelling approach for multicomputer task scheduling. Parallel Computing 25 (1999), pp. 63-86.
• 8. J. Błażewicz, M. Drozdowski, M. Markiewicz: Divisible task scheduling - Concept and verification. Parallel Computing 25 (1999), pp. 87-98.
• 9. K. Amoura, E. Bampis, Y. Manoussakis, Z. Tuza: A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors. Parallel Computing 25 (1999), pp. 49-6l.
• 1O. Błażewicz, P. Dell'Olmo, M. Drozdowski, M. G. Speranza: Scheduling multiprocessor tasks on three dedicated processors. Information Processing Letters 49 (1994), pp. 269-270.
• 11. M. X. Goemans: An approximation algorithm for scheduling on three dedicated processors. Discrete Applied Mathematics 61 (1995), pp. 49-59.
• 12. Bianco, P. Dell'Olmo, M. G. Speranza: Nonpreemptive scheduling of independent tasks with prespecified processor allocation. Naval research Logistics 41 (1994), pp. 959-971.
• 13. G. Bozoki, J. P. Richar d: A branch-and-bound algorithm for the continuous-process task shop scheduling problem. AIIE Transactions 2 (1970), pp. 246-252.
• 14. S. Johnson: Approximation algorithms for combinatorial problems. Journal of Computer and System Science 9 (1974), pp. 256-278.
• 15. T. H. Cormen, C. E. Leiserson, R. L. Rivest: Introduction to algorithms. MIT Press, Cambridge, MA, 1990.
• 16. H. Kellerer, R. Mansini, U. Pferschy, M. G. Speranza: An efficient fully polynomial approximation scheme for the subset-sum problem. Technical Report, University of Brescia, 1997.
• 17. M. Gajer: Porównanie efektywności różnych algorytmów szeregowania zadań wieloprocesorowych. Kwartalnik Elektroniki i Telekomunikacji, 2000, 46, z. 1, pp. 21-34.