Порівняння ефективності методів інваріантного аналізу динамічних характеристик програмних компонентів

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Черкаський національний університет ім. Богдана Хмельницького

Порівняння ефективності методів інваріантного аналізу динамічних характеристик програмних компонентів

Весельський Олексій Сергійович

магістрант

Супруненко Оксана Олександрівна

канд.техн.наук, доцент

Анотація

У статті розглянуті методи для визначення мінімального набору інваріантів при розв'язанні системи лінійних діофантових рівнянь. Цей набір інваріантів застосовується у аналізі динамічних властивостей моделей, які характеризуються паралелізмом. Він має визначатись в режимі реального часу. В результаті проведеного теоретичного та експериментального дослідження були розглянуті методи Фаркаса, Алаівана та TSS. Найбільшу обчислювальну ефективність для визначення мінімального набору інваріантів у моделях малої та середньої розмірності показав TSS-метод.

Ключові слова: мережі Петрі, динамічні властивості, система лінійних діофантових рівнянь, інваріантний аналіз, мінімальний набір інваріантів.

Моделі програмного забезпечення мають численні паралельні та конкуруючі процеси, які ускладнюють їх аналіз та викликають необхідність застосування методів для виявлення динамічних характеристик моделей. Зокрема важливою задачею є виявлення явних та прихованих конфліктних ситуацій (помилок), якими є тупики та нескінченні цикли. Аналізувати та досліджувати наявність помилок дозволяють моделі на основі мереж Петрі [1]. Зокрема, наявність тупиків можна виявити, коли не дотримуються вимоги збережуваності або повної керованості. Про виявлення нескінченного циклу можуть свідчити недотримання вимоги живості (недосяжність певних вершин місць) чи повторюваності розмітки [2].

Для аналізу моделей на основі мереж Петрі застосовуються імітаційне моделювання та аналітичні методи дослідження імітаційних моделей. Застосування аналітичних методів можливо, оскільки мережі Петрі мають однозначний матричний опис [3], що дозволяє відслідковувати та аналізувати всі можливі варіанти функціонування досліджуваної моделі, в той час, як при застосуванні імітаційного моделювання вдається проаналізувати лише частину таких варіантів.

Таким чином, аналітичне представлення PN-моделей дозволяє досліджувати динамічні характеристики програмного забезпечення максимально повно, щоб забезпечити якість проектних рішень [3]. Для цього у роботі застосується метод інваріантів [1]. Його результати дозволяють підтвердити чи спростувати такі важливі характеристики моделей як живість (досяжність), повторюваність, обмеженість, збережуваність.

Для визначення цих характеристик важливим є розрахунок інваріантів, як розв'язків основного та додаткового рівнянь мереж Петрі [4]. При розв'язанні цих рівнянь вирішується задача пошуку розв'язків системи лінійних діофантових рівнянь, яких у загальному випадку може бути нескінченна множина. Але для дослідження моделей компонентів ПЗ потрібен мінімальний набір таких розв'язків.

Для визначення мінімального набору інваріантів відомі кілька методів, які мають різну обчислювальну ефективність, це метод Фаркаса [5], метод Алаівана [6], TSS-метод (truncated solution set) [7] та ін.

У цьому методі [5] матрицю інцидентності доповнюють матрицею інваріантності, яка відображає на кожному кроці ітерацій новостворювану вершину місця, яку створюють при видаленні вершини переходу, що є сусідньою до аналізованої вершини переходу. Такі ітерації продовжують, доки множини сусідів всіх вершин переходів не спорожніють. У даному методі застосовують перевірки, які дозволяють відсіяти надмірні розв'язки з використанням рангу матриці або порівняння нових розв'язків з отриманими. Дані перевірки значно знижують обчислювальну ефективність методу.

Більш ефективним є метод Алаівана [6], який у своїй оптимізованій версії показав кращу ефективність, зокрема на моделях великої розмірності. Алгоритм складається з двох фаз. На початку першої з них будується розширена матриця шляхом додавання рядків матриці ідентичності В (матриця, заповнена нулями, з одиницями на головній діагоналі) під рядками матриці інцидентності W. З такою розширеною матрицею виконуються перетворення, спрямовані на приведення значень всіх елементів матриці W до нульових. Для цього використовуються дві операції: додавання до розширеної матриці стовпців, що є лінійною комбінацією вже наявних в ній стовпців, та видалення існуючих стовпців. Визначення дій, які мають бути виконані, та стовпців, над якими вони мають бути виконані, здійснюється на основі значень елементів рядків матриці W. Тобто, на початку кожного кроку здійснюється розгляд рядка, який ще не є нульовим, і запропоновані роботою [6] вдосконалення полягають зокрема у принципах вибору таких рядків. Метою такої оптимізації є мінімізація кількості від'ємних значень у стовпцях, що додаються до матриці. Це дозволяє знизити складність другої фази алгоритму. Також завдяки оптимізованому підбору рядків для обробки вдається вилучити з матриці всі стовпці, які не впливають на інваріанти мережі, що дозволяє ввійти у другу фазу алгоритму з матрицею меншої розмірності, що також позитивно впливає на його швидкодію.

По завершенню першої фази матриця W відкидається, оскільки всі її елементи перетворені на нулі, а стовпці матриці В представляють базис розв'язків системи, що розглядається. Відповідно, якщо матриця не містить стовпців, то мережа Петрі, що розглядається, не має інваріантів. Втім, базис, знайдений в першій фазі алгоритму, не є мінімальним набором інваріантів, оскільки може містити від'ємні значення. Тому виникає потреба застосування другої фази алгоритму, яка також передбачає дії з додавання та видалення стовпців, але тепер з метою виключення з матриці всіх від'ємних значень.

В результаті застосування згаданих перетворень до матриці В можуть бути отримані інваріанти, що не входять до мінімального набору, тому важливо відсіяти надлишкові розв'язки шляхом порівняння з рештою стовпців. В результаті цього отримуємо мінімальний набір інваріантів, за аналізом якого можна робити висновки про виконуваність динамічних властивостей мережі Петрі. Складність першої фази алгоритму є кубічною, другої - експоненційною.

У TSS-методі будують початкову множину векторів, яка є векторами канонічного базису виду в_х = (1,0,...,0), e₂ = (0,1,...,0),..., e_n = (0,0,...,1). Після цього потрібно використати кожен з даних векторів у якості аргументу функції L₁(x) = a₁₁x₁ +... + a_1ix_i +... + a_1nx_n, побудованої на основі першого рівняння системи, що розглядається. Очевидно, що значення, отримане в результаті такого застосування функції, буде або більше за нуль М₁₊ = {e | L(e) > 0}, або менше за нуль М_х_ = {e | L(e) < 0}, або рівним нулеві ^М1(0) = ^{{е 1 L}1^(e) = ^0}. Саме за належністю до одного з таких випадків поділимо вектори канонічного базису на три групи. Тепер, використовуючи ці три множини, будуємо множину М':

^{М1 = М}10 U{У. І yu = -L1(ei)e- + І1(е)ei,ef Є М1+,ei Є М1_}

Таким чином, елементи множини М_1{0) входять до М' повністю. Решта векторів застосовується у наведеній формулі з використанням першого рівняння системи (L). Матрицю у можна уявити як таку, де стовпцями виступають елементи М, а рядками - М. Таким чином, потрібно по всіх клітинках такої матриці сформувавши всі можливі комбінації з векторів-рядків та векторів-стовпців. Після завершення побудови множини М', вона використовується в якості початкової (замість векторів канонічного базису) для наступної ітерації алгоритму. Здійснюється послідовна побудова множин М\, М',..., М'_p, де p - кількість рівнянь в системі. Ці множини і складають TSS даної системи лінійних діофантових рівнянь. Тобто, множина TSS відповідає мінімальному набору інваріант, за яким визначаються динамічні властивості мережі Петрі.

Складність побудови методу TSS складає O(ql³), де q - кількість рівнянь, а l = max(m, n), де n - кількість невідомих, m - максимальна довжина двійкового представлення коефіцієнтів рівняння.

За результатами теоретичного дослідження методів знаходження мінімальної множини інваріантів було вирішено в практичному дослідженні розглянути TSS-метод та метод Алаівана, як найбільш ефективні методи знаходження такої множини, а також параметричний спосіб розрахунку інваріантів для порівняння. Вибрані методи та підхід до їх порівняння в ході експерименту відображено у моделі дослідження (рис. 1).

Рис. 1. Модель дослідження ефективності методів розрахунку мінімального набору інваріантів.

Для проведення експерименту було розроблене програмне середовище, що дозволяє будувати графічне відображення моделі на основі мереж Петрі, формувати її матричне представлення (матрицю інцидентності), проводити імітацію роботи моделі та здійснювати інваріантний аналіз динамічних характеристик моделі зазначеними вище методами. Спершу була розглянута робота вибраних методів на прикладі моделі невеликої розмірності (менше 10 вершин найбільшої множини P чи T) (рис. 2).

В ході аналізу даної моделі за допомогою TSS-методу та методу Алаівана були отримані однакові результати:

T = [1ДЛЛД]

р = [ 1,1,1,1,1,0 ]

р = [ 1,0,1,1,0,1]

Рис. 2. Перша модель для експерименту в моделюючому середовищі

інваріантний аналіз динамічний програмний

Одержані значення інваріантів збігаються з отриманими в ході ручних обрахунків, з чого можемо зробити висновок про коректність роботи реалізованих методів. Суттєвих відмінностей в швидкодії способів виявлено не було. Аналіз отриманих інваріантів показує, що динамічні властивості першої моделі, за які відповідають 7"-інваріанти (живість, повторюваність) та Р-інваріанти (обмеженість, збережуваність) [2], виконуються.

Для подальшого дослідження ефективності методів визначення мінімального набору інваріантів була використана друга модель, що має більшу розмірність [8], тобто більше 10 вершин найбільшої множини P чи T (рис. 5).

Рис. 5. Друга модель [8] для експерименту, побудована в моделюючому середовищі

При застосуванні до другої моделі інваріантного аналізу за допомогою TSS-методу було знайдено п'ятнадцять Т-інваріантів та один Р-інваріант, аналіз яких показав виконання всіх динамічних властивостей мережі:

Ті = [1, 0, 1,0, 1,0, 0, 2, 0, 0, 1, 1, 1,3, 0, 0, 1,0, 0, 2]

Т2 = [2, 0, 2, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 4, 2, 0, 2, 0, 0, 2]

Тз = [1, 1,0, 0, 0, 0, 0, 1,0, 0, 1,0, 0, 2, 0, 1, 1,0, 0, 1]

Т4 = [1,0, 1,0, 1,0, 0, 2, 0, 0, 1, 1, 1, 1,0, 0, 1,0, 2, 0]

Т₅ = [2, 0, 2, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 2, 2, 0, 2, 0, 2, 0]

Тб = [1, 1,0, 0, 0, 0, 0, 1,0, 0, 1,0, 0, 1,0, 1, 1,0, 1,0]

Ту = [1,0, 1,0, 1,0, 0, 2, 0, 0, 1, 1, 1, 1,0, 0, 0, 1,0, 1]

Те = [1,0, 1,0, 1,0, 0, 2, 0, 0, 1, 1, 1,0, 0, 0, 0, 1, 1,0]

Т9 = [2, 0, 2, 0, 2, 0, 0, 2, 0, 0, 2, 0, 0, 0, 2, 0, 0, 2, 0, 0]

Т_ю = [1, 1,0, 0, 0, 1, 1,2, 0, 0, 1,0, 0, 0, 0, 0, 0, 1,0, 1]

Т11 = [1, 1,0, 0, 0, 0, 0, 1,0, 0, 1,0, 0, 0, 0, 1,0, 1,0, 0]

Ти = [1, 1,0, 0, 0, 1, 1,2, 0, 0, 1,0, 0, 2, 0, 0, 1,0, 0, 2]

Тіз = [1, 1,0, 0, 0, 1, 1,2, 0, 0, 1,0, 0, 0, 0, 0, 1,0, 2, 0]

Т14 = [1,0, 1,0, 0, 0, 0, 0, 1, 1,0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Т15 = [1,0, 0, 1,0, 0, 0, 0, 0, 1,0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Рі = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

Час аналізу (в середньому близько 0.001 мілісекунди) при цьому несуттєво перевищував такий при першому досліді та цілком задовольняв критерії системи реального часу.

Втім, методу Алаівана, при спробі застосування його до даної моделі, такі критерії не задовольнив. Під час другої фази алгоритму, яка, як згадувалося, має експоненційну складність, була утворена велика кількість надлишкових розв'язків, перевірка і відсіювання яких зайняла недопустимо багато часу. Таким чином, проведений експеримент вказав на критичність даного недоліку методу Алаівана при роботі з моделями середньої розмірності.

Таким чином, в результаті проведених експериментів метод Алаівана показав прийнятні результати лише на моделях малої розмірності (min(n(t_t), m(p_j) < 10). Натомість, доведена ефективність TSS-метода для моделей, як малої, так і більшої розмірності. Він є перспективним і для дослідження динамічних властивостей моделей великої розмірності, що дозволить виявляти явні та приховані помилки у компонентах програмного забезпечення, які мають паралельні та конкуруючі процеси.

Список використаних джерел

[1 ] Гломодза Д.К. (2016). Застосування методу інваріантів до аналізу кольорових мереж Петрі із дедлоками. Вісник НТУУ КПІ. Інформатика, управління та обчислювальна техніка, (64), 38-46.

[2] Suprunenko O.O., Onyshchenko B.O., Grebenovych J.E. (2022). Analysis of hidden errors in the models of software systems based on Petri nets. Electronic Modeling, 2(44), 38-50. https://doi.org/10.15407/emodel.44.02.038

[3] Suprunenko, O., Onyshchenko, B., & Grebenovich, J. (2023). Improving the efficiency of

dynamic analysis of the combined simulation model for software with parallelism. Eastern-European Journal of Enterprise Technologies, 3(2(123)), 26-34. https://doi.org/10.15587/1729-4061.2023.283075

[4] Нестеренко Б.Б., Новотарський М.А. (2012). Формальні засоби моделювання паралельних процесів та систем. Праці Інституту математики НАН України, (Т. 90, с. 334). - Київ: Інститут математики НАН України. ISBN 978-966-02-2571-7, ISBN 978966-02-6506-6.

[5] Marinescu Dan C., Beaven Mike, Stansifer Ryan. (1991). A Parallel Algorithm for Computing Invariants of Petri Net Models. Department of Computer Science Technical Reports. Paper 873.

[6] Mario D'Anna, Sebastiano Trigila. (1988). Concurrent system analysis using Petri nets: an optimized algorithm for finding net invariants. Computer Communications. 11(4), 215220.

[7] Крывый С.Л. (2001). О вычислении минимального множества инвариантов сети Петри. Искусственный интеллект, (3), 199-206.

[8] Suprunenko, O., Onyshchenko, B., Grebenovych, J., Nedonosko, P. (2023) Applying a Combined Approach to Modeling of Software Functioning. Lecture Notes on Data Engineering and Communications Technologies. Vol. 178. Springer, Cham. P. 30-48. https://doi.org/10.1007/978-3-031 -35467-0_3

[9] Kuzmuk V.V., Suprunenko O.A. (2014). The means for the description of information flows in dynamic models of medical hardware-software systems. Theoretical and Applied Science, 15(7), 11-18. http://dx.doi.org/10.15863/TAS.2014.07.15.2

Размещено на Allbest.ru