Adaptacja algorytmu Rate Monotonic Scheduling dla potrzeb szeregowania zadań wieloprocesorowych

• Autorzy: Gajer, M.
• Języki publikacji: PL

Abstrakty

PL

W przypadku systemów czasu rzeczywistego o ostrych ograniczeniach czasowych czas obliczeń jest najcenniejszym zasobem. W celu zagwarantowania dochowania ograniczeń czasowych przez szeregowane zadania rozwinięto metody formalne określane mianem teorii szeregowania zadań. Jednym z najbardziej popularnych algorytmów szeregujących jest Rate Monotonie Scheduling, przeznaczony do szeregowania zadań jednoprocesorowych. Artykuł stanowi propozycję adaptacji algorytmu szeregującego zadania Rate Monotonie Scheduling dla przypadku szeregowania zadań wieloprocesorowych. Istota metody zaproponowanej przez autora polega na binaryzacji okresów szeregowanych zadań i ich łączeniu w większe jednostki zwane super-zadaniami. Zaproponowana przez autora metoda pozwala na wykorzystanie podstawowych twierdzeń związanych z Rate Monotonie Scheduling do dowodzenia szeregowalności również zbiorów zadań wieloprocesorowych.

EN

In the case of hard real-time systems the computational time is the most precious resource that must be very carefully used. The theory of task scheduling delivers formal methods that can guarantee that time constraints are met for all the tasks being scheduled. One of the most popular scheduling algorithm is Rate Monotonic Scheduling that is devoted for the purpose of scheduling uniprocessor tasks. The paper is the proposition of implementation of Rate Monotonic Scheduling also for multiprocessor tasks. The clue of the method that was proposed by this author is the application of binarization of tasks periods and concatenation of tasks into the units of higher rank that was called by this author supertasks. The method allows for the application of Rate Monotonic Scheduling theory to prove the schedulability of the set of multiprocessor tasks.

Słowa kluczowe

PL

szeregowanie zadań; systemy wieloprocesorowe; obliczenia równoległe

EN

task scheduling; multiprocessor systems; parallel computing

• Czasopismo: Informatyka Teoretyczna i Stosowana
• Rocznik: 2006
• Tom: R. 6, nr 10
• Strony: 167-180
• Opis fizyczny: Bibliogr. 19 poz., rys., tab.

Twórcy

autor

Gajer, M.

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

Bibliografia

• [1] Szmuc T., Motet G., Specyfikacja i projektowanie oprogramowania czasu rzeczywistego, Krakowskie Centrum Informatyki Stosowanej, Kraków 1998.
• [2] Werewka J., Szmuc T., Analiza i projektowanie systemów czasu rzeczywistego o różnym stopniu rozproszenia, Polskie Towarzystwo Informatyczne - Oddział Małopolski, Kraków 2007.
• [3] Szmuc T., Zaawansowane metody tworzenia oprogramowania czasu rzeczywistego, Krakowskie Centrum Informatyki Stosowanej, Kraków 1998.
• [4] Szmuc T., Modele i metody inżynierii oprogramowania systemów czasu rzeczywistego, AGH – Uczelniane Wydawnictwa Naukowo-Dydaktyczne, Kraków 2001.
• [5] Miloško J., Kotov E., Algorithms, software and hardware of parallel computers, VEDA - Publishing House of the Slovak Academy of Sciences, Bratislava 1984.
• [6] Kwon O., Chwa K.Y., Approximation algorithms for general parallel task scheduling, Information Processing Letters 2002, 81, 143-150.
• [7] 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.
• [8] Nawrocki J., Czajka A., Binaryzacja okresów zadań cyklicznych, VII Konferencja Systemy Czasu Rzeczywistego, Kraków 2000, 41-51.
• [9] Werewka J., Zagadnienia alokacji zadań w rozproszonych systemach czasu rzeczywistego, Elektrotechnika 1995, 14, 4, 479-488.
• [10] Hsueh C., Lin K.J., Scheduling real-time systems with end-to-end timing constraints using the distributed pinwheel model, IEEE Transaction on Computers 2001, 50, 1, 51-68.
• [11] Kwon O.H., Chwa K.Y., Approximation algorithms for general parallel task scheduling, Information Processing Letters 2002, 81, 143-150.
• [12] Ye D., Zhang G., On-line scheduling with extendable working time on a small number of machines, Information Processing Letters 2003, 85, 171-177.
• [13] Kim J.H., Chwa K.Y., Online deadline scheduling on faster machines, Information Processing Letters 2003, 85, 31-37.
• [14] Shin KG., Ramanathan P., Real-time computing: A new discipline of computer science and engineering, Proceedings of the IEEE 1994, 82, 1, January, 6-24.
• [15] Liu L., Layland J.W., Scheduling algorithms for multiprogramming in a hard real time environment, Journal on Assoc. Comput. Mach. 1973, 20, 1, 46-61.
• [16] Stoyenko T., Baker P., Real-time schedulability-analyzable mechanizms in Ada9X, Proceedings of the IEEE 1994, 82, 1, January, 95-107.
• [17] Ramanathan K., Stankovic J.A., Scheduling algorithms and operating systems support for real-time systems, Proceedings of the IEEE 1994, 82, 1, January, 55-67.
• [18] Zalewski A., What every engineer needs to know about rate monotonic scheduling: A tutorial. Odessa, TX, 1995, 321-335.
• [19] Tanenbaum S., Rozproszone systemy operacyjne, WN PWN, Warszawa 1997.