GL-моделі для аналізу багатопроцесорних систем, стійких до однієї та двох відмов

Анотація

Роботу присвячено проблемі побудови GL-моделей поведінки в потоці відмов небазових відмовостійких багатопроцесорних систем. Розглядаються системи, які є стікими до будь-якої однієї відмови, а за певної умови – до будь-яких двох відмов своїх процесорів. При цьому передбачається, що такій умові відповідає деякий булевий вираз, що залежить від станів процесорів системи. Для побудови моделей таких систем застосовується запропонований раніше спосіб, який базується на комбінуванні виразів реберних функцій допоміжних базових GL-моделей, що відповідають 1- та 2-відмовостійким системам. Розглядається два альтернативних способи побудови допоміжних моделей K(2, n). Показано, що отримані GL-моделі базуються на однакових циклічних графах, і відрізняються лише виразами своїх реберних функцій. Виконано аналіз складності виразів реберних функцій отриманих моделей, для випадків використання допоміжних GL-моделей кожного типу. Отримано формули для оцінки складності цих виразів (кількості елементарних логічних операцій) в залежності від кількості процесорів в системі, зокрема, для випадків, коли ця кількість є ступенем двійки. Також, для випадку використання однієї з допоміжних моделей, виявлено можливість додаткового спрощення виразів деяких із реберних функцій. Визначено, в яких випадках, а саме, для якої кількості процесорів системи, доцільно використовувати допоміжні моделі того чи іншого типу. Проведені експерименти підтверджують, що побудовані розглянутим способом GL-моделі адекватно відображають поведінку системи. Наведено приклади, що демонструють застосування розглянутого способу побудови небазових GL-моделей та підтверджують коректність оцінки складності виразів їх реберних функцій при використанні допоміжних моделей різних типів. Показано також, що в деяких випадках існує можливість додаткового спрощення виразів реберних функцій GL-моделей, що будуються, зокрема за рахунок зміни порядку ребер у допоміжних моделях. Проте, в рамках даної статті цю можливість не досліджено в загальному випадку.