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

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

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

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

магістрант

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

Україна

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

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

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

Україна

Анотація

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

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

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

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

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

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

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

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

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

По завершенню першої фази матриця W відкидається, оскільки всі її елементи перетворені на нулі, а стовпці матриці В представляють базис

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

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

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

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

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

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

[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