Szeregowanie zadań w systemach czasu rzeczywistego z zastosowaniem techniki obliczeń ewolucyjnych

• Autorzy: Gajer, M.

Warianty tytułu

EN

Task scheduling in real-time computer systems with the use of an evolutionary computations technique

• Języki publikacji: PL

Abstrakty

PL

W artykule rozważono zastosowanie techniki obliczeniowej opartej na algorytmach ewolucyjnych w celu optymalizacji procesu szeregowania zadań w systemach czasu rzeczywistego z ostrymi ograniczeniami czasowymi. Na potrzeby realizacji procesu szeregowania zadań wybrana została metoda Rate Monotonic Scheduling (RMS), która bazuje na systemie przydziału priorytetów i jest przewidziana do szeregowania zbiorów wywłaszczalnych, periodycznych i niezależnych zadań. Przeprowadzone eksperymenty numeryczne wykazały, że algorytmy ewolucyjne mogą stanowić skuteczne narzędzie pozwalające na równoważenie obciążenia jednostek obliczeniowych w systemach wieloprocesorowych.

EN

In the paper we discuss the use of a computational technique based on evolutionary algorithms for the purpose of optimizing the task scheduling process in real-time computer systems with hard time constraints. The process of task scheduling was realized with the use of Rate Monotonic Scheduling (RMS) method which is based on the system of priorities assignment and is designed for scheduling sets of pre-emptive, periodic, and independent tasks. We conducted numerical experiments which prove that evolutionary algorithms can constitute an effective tool that ensures balancing the load in multiprocessor systems.

Słowa kluczowe

PL

czas rzeczywisty; systemy wieloprocesorowe; równoważenie obciążenia jednostek; szeregowanie zadań

EN

real-time systems; task scheduling; multiprocessor systems; load balancing

• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2010
• Tom: R. 86, nr 10
• Strony: 293-298
• Opis fizyczny: Bibliogr. 18 poz., rys., wykr.

Twórcy

autor

Gajer, M.

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

Bibliografia

• [1] Szmuc T., Motet G., Specyfikacja i projektowanie oprogramowania czasu rzeczywistego, Wydawnictwo CCATIE, Kraków, 1998
• [2] Shin K. G., Ramanathan P., Real-time computing: A new discipline of computer science and engineering, Proceedings of the IEEE, vol. 82, no. 1, 1994, 6-24
• [3] Lala J. H., Harper R. E., Architectural principles for safetycritical real-time applications, Proceedings of the IEEE, vol. 82, no. 1, 1994, 25-41
• [4] Stoyenko T., Baker P., Real-time schedulability analyzable mechanisms in Ada9X, Proceedings of the IEEE, vol. 82, no. 1, 1994, 95-107
• [5] Ramamritham K., Stankovic J. A., Scheduling algorithms and operating systems support for real-time systems, Proceedings of the IEEE, vol. 82, no. 1, 1994, 55-67
• [6] Suri N., Hugue M. M., Walter C. J., Synchronization issues in real-time systems, Proceedings of the IEEE, vol. 82, no. 1, 1994, 41-53
• [7] Sha L., Rajkumar R., Sathaye S. S., Generalized ratemonotonic scheduling theory: A framework for developing realtime systems, Proceedings of the IEEE, vol. 82, no. 1, 1994, 68-82
• [8] Zalewski A., Whatevery engineer needs to know about ratemonotonic scheduling: A tutorial, The University of Texas of the Permian Basin, Department of Computer Science, 1995, 321- 335
• [9] Czajka A., Nawrocki J., Szeregowanie zadań o okresach binarnych w systemach silnie uwarunkowanych czasowo, I Krajowa Konferencja: Metody i systemy komputerowe w badaniach naukowych i projektowaniu inżynierskim, Kraków, 1997, 669-676
• [10] Hsueh W., Lin K. J., Scheduling real-time systems with endto- end timing constraints using the distributed pinwheel model, IEEE Transactions on Computers, vol. 50, no. 1, 2001, 51-67
• [11] Goldberg D. E., Algorytmy genetyczne i ich zastosowania, Wydawnictwa Naukowo-Techniczne, Warszawa, 1996
• [12] Rutkowska D., Piliński M., Rutkowski L., Sieci neuronowe, algorytmy genetyczne i systemy rozmyte, Wydawnictwo Naukowe PWN, Warszawa-Łódź, 1997
• [13] Michalewicz Z., Algorytmy genetyczne + struktury danych = programy ewolucyjne, Wydawnictwa Naukowo-Techniczne, Warszawa, 2003
• [14] Arabas J., Wykłady z algorytmów ewolucyjnych, Wydawnictwa Naukowo-Techniczne, Warszawa, 2004
• [15] Rutkowska D., Inteligentne systemy obliczeniowe i sztuczna inteligencja, [w] Biocybernetyka i inżynieria biomedyczna 2000, pod redakcją Macieja Nałęcza, Tom 6 – Sieci neuronowe, 2000, 765-784
• [16] Maniadaki s M., Trahanias P., Ant-Based Brain Modeling by Means of Hierarchical Cooperative Coevolution, Artificial Life, Vol. 15, 2009, 293-336
• [17] Stanley K. O., Ambrosio D. B., Gauci J., A hypercubebased encoding for evolving large-scale neural networks, Artificial Life, Vol. 15, 2009, 185-212
• [18] Ampatzis C., Tuci E., Triannini V., Christensen A. L., Dorigo M., Evolving Self-Assembly in Autonomous Homogeneous Robots: Experiments with Two Physical Robots, Artificial Life, Vol. 15, 2009, 185-212