Page 47 - 6571

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

ралельній програмі. При «поганому» стані два процеси такої про-
грами одночасно виконують дії в одній критичній секції. У «хо-
рошому» стані кожен процес виконується у своїй критичній сек-

ції.
Для перевірки того, що дана програма задовольняє бажаним
властивостям звичайний застосовується підхід, якій полягає у
тестуванні, або налагодженні. Його можна охарактеризувати

фразою «запусти програму і подивися, що вийде». Це відповідає
перебору деяких можливих історій програми і перевірці їх при-

йнятності. Недолік такої перевірки полягає в тому, що кожен тест
стосується тільки однієї історії виконання, а обмежене число тес-
тів навряд чи здатне продемонструвати відсутність поганих істо-
рій. Також в результаті тестування можна виявити тільки наяв-

ність помилок, а не гарантувати їх відсутність. Крім того, парале-
льні програми дуже складні в тестуванні та налагодженні, оскіль-
ки, по-перше, важко зупинити відразу всі процеси і перевірити їх

стан, і, по-друге, в загальному випадку кожне виконання програ-
ми призводить до нової історії.
Другий підхід – використання операторних міркувань, які
можна назвати «вичерпний аналіз варіантів виконання» (переби-

раються всі можливі історії виконання програми). Для цього ана-
лізуються способи чергування неподільних дій процесів. На
жаль, в паралельній програмі число можливих історій зазвичай

дуже велике (тому метод є «виснажливим»). Припустимо, що па-
ралельна програма містить n процесів і кожен з них виконує пос-
лідовність із m неподільних дій. Тоді число різних історій про-

грами складе (n m× )!/ ( ! )m n . Для програми з трьох процесів, кож-

ний з яких виконує всього дві неподільні операції, можливими є
90 різних історій! Чисельник у формулі – це кількість можливих
перестановок з n m× дій. Але, оскільки кожен процес виконує по-
слідовність дій, то для нього можливий тільки один порядок ви-

конаннядій. Знаменник відкидає всі варіанти з неправильним по-
рядком виконаннядій. Ця формула дає кількість, рівну числу спо-

46