Wyniki wyszukiwania - BazTech

1

Minimization of the total completion time for asynchronous transmission in a packet data-transmission system

Piórkowski A., Werewka J.

International Journal of Applied Mathematics and Computer Science

|

2010

|

Vol. 20, no 2

391-400

EN

The minimization of the total completion time for asynchronous transmission in distributed systems is discussed. Attention is focused on the problem of message scheduling on part of the sender. Messages to be sent form a queue, and the order in which they are to be sent has to be first established. The methods of scheduling messages, which minimize the factor of the total completion time, are presented herein. The message-scheduling problem becomes considerably complicated when the stream of data transmitted between the sender and the receiver is organized into packets. A scheduling rule, according to which the shortest messages (SPT-Shortest Processing Time) are selected as the first to be sent, has been proven to be appropriate for the proposed model. A heuristic algorithm for scheduling messages with real-time constraints is proposed. The performance of the scheduling algorithm is experimentally evaluated. The results of the study show the possibility of improving the total completion time from a few to ten percent, depending on the characteristics of the sender. Thus, the practicability of the method has been proved.

2

Heurystyczne algorytmy szeregowania wiadomości z terminami dostarczeń

Piórkowski A.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2005

|

T. 9, z. 1-2

201-210

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.

3

Szeregowanie dynamiczne dla grup wiadomości w rozproszonych systemach czasu rzeczywistego

Żaba S.

Kwartalnik Elektroniki i Telekomunikacji

|

2004

|

Vol. 50, z. 2

179-207

PL

W artykule przedstawiono nową metodę szeregowania wiadomości. W zaproponowanej metodzie (Dynamic Priority Group Scheduling) szeregowanie wiadomości odbywa się w oparciu o dynamicznie przydzielany priorytet dla grup wiadomości. Opracowany został także wariant omawianej metody umożliwiający szeregowanie wiadomości z mieszanym przydziałem priorytetu (Mixed Priority Group Scheduling). Przedstawiono sposób sprawdzania dotrzymywania warunków RT dla metod DPGS i MPGS. Dla trzech wybranych magistral miejscowych (PROFIBUS FMS, CAN, InterBus-S) przeprowadzono badania, mające na celu porównanie wiadomości opracowanych metod z metodami GRMS i EDF.

EN

In this paper new methods of messages scheduling are presented. The first method, Dynamic Priority Group Scheduling method is based on assigning dynamic priorities not to individual message, but to group of messages. The second method, Mixed Priority Group Scheduling method enable to assign to group of messages static priorities as well. A procedure of checking RT-constraint fulfilment of messages in distributed real time system based on fieldbus for DPGS and MPGS methods are presented. For three fieldbuses PROFIBUS FMS, CAN and InterBus tests were performed in order to compare properties of created methods to GRMS and EDF methods. New methods take into consideration specificity of distributed real time system based on fieldbus and adapt message deadlines to time properties of distributed system. It is very importent that new methods have less calculating time than GRMS and EDF methods. Tests which were performed give results as follow: * Performances of new methods depend on message model parameters, but obtained resuts have never been worst than results for GRMS method, * In the case, when results are almost the same as the results for EDF method, and it takes into consideration the smallest calculating time of new methods, it can say that new methods are most effectively.

4

Badania eksperymentalne magistral miejscowych dla wybranych metod szeregowania wiadomości

Żaba S.

Kwartalnik Elektroniki i Telekomunikacji

|

2004

|

Vol. 50, z. 2

261-286

PL

W artykule przedstawiono właściwości i prametry czasowe trzech wybranych magistral miejscowych: PROFIBUS FMS, CAN i InterBus-S. Prezentowane wyniki uzyskano na podstawie badań, polegających na sprawdzeniu dotrzymania ograniczeń czasowych dla wiadomości w rozproszonym systemie czasu rzeczywistego z magistralą miejscową przy założeniu, że wiadomości szeregowane są przy użyciu metod szeregowania : FIFO, GRMS, EDF. Badania przeprowadzone były dla najgorszego przypadku, tzn. zostało założone, że w chwili t = 0 zostały aktywowane wszystkie zadania w systemie. Uwzględniono także czasy blokowania wiadomości. Wyniki badań zaprezentowano w postaci graficznej i tabelarycznej.

EN

In this paper properties and time parameters of three fieldbuses PROFIBUS FMS, CAN, InterBus are presented as the result of research based on checking of RT - constraint fulfilment of messages in distributed real time system based on fieldbus. Research was done for FIFO method and real time methods scheduling GRMS and EDF. Tests were performed for the worst case - it was assumed that all messages in system were activated in instant zero. The message blocking is also considered. Results of testing were obtain by using computer algorithms created by author. On the basis of performing tests we can draw conclusions as follow: * FIFO method is very simple and requires small calculating time, bul its performance are the least from among priorities method, * Dynamic methods have better performance than static priority for each fieldbus (except for CAN fieldbus, becouse there is impossible to apply dynamic method to this fieldbus), * InterBus-S fieldbus has the best effects for transmitting 1 or 2 bytes data length, CAN fieldbus has the best effects for transmitting 3 to 8 bytes data length and PROFIBUS FMS fieldbus has the best effects for transmitting massages with data length above 8 bytes.