Heurystyczne algorytmy szeregowania wiadomości z terminami dostarczeń

• Autorzy: Piórkowski A.

Warianty tytułu

EN

Heuristic algorithms of message scheduling for messages with deadlines

• Języki publikacji: PL

Abstrakty

PL

Artykuł przedstawia problem optymalizacji komunikacji asynchronicznej w kontekście szeregowania wiadomości w systemach wiadomości kolejkowanych (MQ). Sporządzono model systemu i przedstawiono problem optymalnej komunikacji. Szczególną uwagą objęto zagadnienie podziału na pakiety sieciowe strumienia przesyłanych danych. Wyznaczono czas oczekiwania na wiadomość uwzględniający wymienione zjawisko. Określono wymagania czasu rzeczywistego adekwatne dla komunikacji asynchronicznej. Wskazano szkic dowodu na nieistnienie dokładnego algorytmu optymalizacji kosztu całkowitego sigmawjCj dla omawianego zagadnienia. Zaproponowano algorytmy heurystyczne, opierające się na sortowaniu bąbelkowym, przesuwaniem małych wiadomości do przodu kolejki oraz zamianie z szacowaniem potencjalnego zysku czy też drogi. Wykonano aplikację symulującą losowe zestawy danych i dokonującą optymalizacji proponowanymi algorytmami. Dla porównania przedstawiono wyniki algorytmu RT STD oraz przeglądu zupełnego. Otrzymane wyniki zinterpretowano.

EN

The article presents the problem of optimizing the asynchronous communication in message queuing systems. A system model is created and as well as the question of optimal communication discussed. A special importance is attached to the problem of dividing the stream of transmitted data into web packets. The time of awaiting for the message taking the occurrence mentioned above into consideration is stated. Lack of precise algorithm for optimizing the total cost sigmawjCj for discussed problem by it's transformation into the knapsack problem is proved. Heuristic algorithms based on bubble sorting, moving the small message into the front of the queue and changing with assessment of the potential gain or distance are proposed. An application simulating the random data sets and optimizing using methods previously described, is created. RT STD and permutations results are presented to compare. Achieved results are discussed.

Słowa kluczowe

PL

szeregowanie wiadomości; systemy czasu rzeczywistego; systemy rozproszone

EN

message scheduling; real-time systems; distributed systems

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2005
• Tom: T. 9, z. 1-2
• Strony: 201--210
• Opis fizyczny: Bibliogr. 4 poz., rys., wykr., tab.

Twórcy

autor

Piórkowski A.

• Zakład Informatyki w Naukach o Ziemi, WGGiOŚ, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Sysło M . M ., Narsingh D ., Kowalik J . S . : Algorytmy optymalizacji dyskretnej z programami w języku Pascal. Warszawa, PWN 1993, rozdział 4.2.5
• [2] Piórkowski A.: Szeregowanie wiadomości z uwzględnieniem podziału na pakiety sieciowe w systemach wiadomości kolejkowanych . W: Materiały Konferencyjne IX Konferencji Systemów Czasu Rzeczywistego, Ustroń 2002
• [3] Piórkowski A.: Heurystyczne algorytmy optymalizacji kosztu całkowitego w systemach wiadomości kolejkowanych. W: Półrocznik AGH Automatyka, t. 7, 2003
• [4] Piórkowski A.: Optymalizacja komunikacji asynchronicznej w systemach rozproszonych czasu rzeczywistego . Kraków, EAIiE AGH 2004 (Praca doktorska)