Page 39 - 4868

37 Ошибка! Стиль не определен.

змінює стан програми.
Процес виконує послідовність операторів.Оператор, у свою чергу,
реалізується послідовністю неподільних дій. Ці дії перевіряють або змінюють
стан програми неподільним чином. Прикладами неподільних дій є неперервні

машинні інструкції, які завантажують і зберігають слова пам’яті.
Виконання паралельної програми призводить до чергування
послідовностей неподільних дій, створених кожним процесом.Конкретне
виконання кожної програми може бути розглянуте як історія
s  s  ... s , деs – початковий стан.Переходи між станами
0 1 n 0
здійснюються неподільними діями, що змінюють стан.Історію також
називають трасою послідовності станів.Навіть паралельне виконання можна
представити у вигляді лінійної історії, оскільки паралельна реалізація набору
неподільних дій еквівалентна їх виконанню в деякому послідовному
порядку.Зміна стану, викликана неподільною дією є нероздільним процесом,
і, отже, на нього не можуть вплинути неподільні дії, створені приблизно в
той же час.
Кожне виконання паралельної програми породжує історію.Для всіх,
окрім хіба що самих тривіальних програм, число можливих історій є досить
великим.Справа в тому, що наступною в історії може стати неподільна дія
будь-якого процесу.Отже, існує багато способів чергування дій, навіть якщо
виконання програми завжди починається з одного і того ж вихідного
стану.Крім того, у кожному процесі зазвичай є умовні оператори, і, отже,
можливі різні дії при різних змінах в стані.
Мета синхронізації – виключити небажані історії паралельної
програми.Взаємне виключення полягає в комбінуванні неподільних дій, що
реалізуються безпосередньо апаратним забезпеченням у вигляді
послідовностей дій, які називаються критичними секціями. Вони повинні
бути неподільними, тобтоїх не можна перервати діями інших процесів, які
посилаються на ті ж змінні. Синхронізація за умовою (умовна синхронізація)
означає, що дію буде виконано, коли стан задовольнятиме заданій логічній
умові.Обидві форми синхронізації можуть призупиняти процеси, обмежуючи
множину наступних неподільних дій.
Властивістюпрограми називається атрибут, який є істинним при будь-
якій можливій історії програми і, отже, при всіх її виконаннях.Існує два типи
властивостей: безпека і живучість. Властивість безпеки полягає в тому, що
програма ніколи не потрапляє в «поганий» стан (при якому деякі змінні
можуть мати небажані значення). Властивість живучості означає, що
програма зрештою завжди потрапляє в «хороший» стан, тобтостан, в якому
всі змінні мають бажані значення.
Прикладом властивості безпеки єчасткова коректність
(правильність).Програма частково коректна (правильна), якщо правильний її
заключний стан (за умови, що програма завершується).Якщо програмі не
вдається завершити виконання, то вона може ніколи не видати правильний
результат, але не існує такої історії, при якій програма завершується з
неправильним результатом виконання. Завершуваність – цеприклад