Теория распараллеливания и синхронизация. Демьянович Ю.К - 12 стр.

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

может меняться в весьма широких пределах (в другой терминоло-
гии и, может быть, с несколько иной точки зрения, объединения в
группы неделимых действий соответствует объединению операций
в ярусы при распараллеливании “алгоритма”). Благодаря этому, су-
ществует огромное количество вариантов реализации параллельной
программы (каждый вариант реализации соответствует временн´ой
развертке алгоритма).
Каждый из таких вариантов определяет историю выполне-
ния параллельной программы. Историй выполнения огромное ко-
личество. Все истории делятся на желательные и нежелательные.
Условно говоря, желательные истории — это истории, приводящие
к правильному результату в рассматриваемом классе данных.
Для отделения желательных историй от нежелательных слу-
жит механизм синхронизации. Синхронизация бывает условная и
безусловная. Обе формы синхронизации могут приостанавливать
те или иные п роце ссы и ограничивать набор последующих недели-
мых действий.
Основное средство синхронизации — последовательность кри-
тический секций. Эти секции (которые появляются в процессе ре-
ализации и отражены в программе) должны быть неделимыми и
их нельзя прервать действиями других процессов.
Имеется два фундаментальных свойства программы:
— безопасность;
— живучесть.
Эти свойства в той ил и мной мере должны сопр овождать лю-
бую правильную программу, т.е. программу, которая имеет только
желательные истории при любом допустимом наборе данных.
Свойство безопасности состоит в том, что программа нико-
гда не попадает в плохое состояние, т.е. в состояние, при котором
некоторые переменные имеют нежелательные (неправильные) зна-
чения.
Свойство живучести состоит в том, что программа в конце
концов всегда попадает в хорошее состояние, т.е. в состояние, при
котором все переменные имеют желаемые (правильные) значения.
К безопасности относится частичная корректность програм-
мы. Программа называется частично корректной, если она
— либо завершается и при завершении всегда выдает желаемый
(правильный) результат;
13

Страницы