Algorytm scalania diagramów stanu w modelowaniu systemów wbudowanych

Abstract

W artykule przedstawiono aspekt implementacyjny algorytmu scalania grafów stanu, modelujących kooperujące systemy wbudowane, a także wykazano jego wielomianową złożoność. Znajomość takiego grafu jest istotna, ponieważ pozwala na analizę zachowania złożonego systemu, a w szczególności na wykrywanie sytuacji niepożądanych, takich jak zakleszczenia. Nawet dla małej liczby prostych podsystemów, o niewielkiej liczbie stanów, diagram otrzymany w wyniku scalenia może charakteryzować się znaczna liczbą stanów, co praktycznie wyklucza jego ręczną generację. Z tego powodu niezbędne jest posiadanie narzędzia umożliwiającego automatyzację tego procesu. In the paper implementation issues related to algorithm of merging state diagrams for cooperating embedded systems, are shown. Its polynomial complexity is also proven. The knowledge of such a merged graph enables one to detect deadlocks or other unwanted effects. Even for a few smali graphs a resultant graph being their superposition may be large enough to make a manual merging impossible. For that reason one needs a tool automatizing that task.