Составители:
Вместо индивидуального вычисления итерации цикла для точ-
ки с индексами i, j с помещением результата в grid[i, j] исполь-
зуется расширение:
1) берется другой массив, куда присваивается полученный ре-
зультат;
2) производится барьерная синхронизация — шаг вычисления
для всех процессов;
3) массивы меняются местами;
4) проводится следующий шаг вычисления.
§13 Глобальные инварианты
Эффективным способом избежать взаимного вмеш ательства явля-
ются глобальные инварианты.
Предположим, что I — предикат, который ссылается на гло-
бальные переменные. Предикат I называется глобальным инвари-
антом по отношению к рассматриваемому множеству процессов,
если
1) I является истинным в начале выполнения процессов,
2) I остается истинным при каждом присваивании.
Условие 1) удовлетворяется, если I — истина в начале каждого
процесса, а условие 2) выполняется, если для любого действия при-
сваивания I – истина после п рис ваивания, если I был истинным до
присваивания (математическая индукция).
Теперь предположим, что предикат I является глобальным ин-
вариантом. Предположим, что любое критическое
1
утвержд ен ие C
в обосновании каждого процесса P
j
имеет вид I ∧ L
j
, гд е L
j
—
предикат относительно локальных (для P
j
) переменных, т.е. каж-
дая переменная, на которую ссылается L
j
, является либо локальной
для процесса P
j
, либо глобальной, но такой, которой делается лишь
присваивание и присваивает только данный процесс.
Если все критические утверждения можно представить в виде
I ∧ L
j
, то процессы будут свободны от взаимного вмешательства.
1
Напомним, что критическое утверждение — это предусловие или постусло-
вие вне оператора await (т.е. это предусловие или постусловие, ссылающееся на
переменные, которые могут быть изменены другими процессами). Если a —
действие присваивания в другом процесса, то a не вмешивается в C, если
истинна тройка {C ∧ pre(a)} a {C}.
37
Страницы
- « первая
- ‹ предыдущая
- …
- 34
- 35
- 36
- 37
- 38
- …
- следующая ›
- последняя »
