Стр. 14 - Ил.С. Свирин, П.А. Силин, В.В. Сюзев - Математическая модель многопоточной программы и правила безопасного многопоточного программирования

его реализации необходимо, чтобы субъекты S

2

и S

3

одновременно

удерживали пятый исключающий семафор. Таким образом, введение

дополнительного семафора избавляет систему от потенциальных ситу-

аций взаимной блокировки. Примененная методика (и эквивалентные

ей) составляют суть вышеописанного правила.

Правило 2.

Если систему S не удается сделать сильно упорядо-

ченной относительно сигнальных переменных, то следует сделать ее

локально слабо упорядоченной.

Поясним понятие сильной упорядоченности (можно показать, что

оно влечет свойство слабой упорядоченности). Пусть есть система

субъектов S

=

{

S

1

, . . . ,

S

n

}

, пусть субъекты данной системы взаимо-

действуют с

i

-й сигнальной переменной (с памятью или без памя-

ти). Если у этой переменной есть хотя бы один оператор отправки

(широковещания или установки), характеризующийся тем, что субъ-

ект, которому принадлежит данный оператор, не содержит операторов

ожидания (для всех сигнальных переменных, с которыми оперирует

система), кроме того, он не содержит операторов захвата тех исключа-

ющих семафоров, которые локально меньше любой из сигнальных

переменных системы. Фактически, это означает, что на данный опе-

ратор локально не влияют никакие сигнальные переменные. В этом

случае присвоим сигнальной переменной 0-й порядок. Дальше будем

определять по индукции. Если у переменной есть хотя бы один опе-

ратор отправки (широковещания или установки), характеризующийся

тем, что на него влияют только сигнальные переменные 0-го поряд-

ка, то присвоим данной переменной 1-й порядок. Если у переменной

есть хотя бы один оператор отправки (широковещания или установ-

ки), характеризующийся тем, что на него влияют только сигнальные

переменные 0-го и 1-го порядка, то присвоим данной переменной

2-й порядок, и т.д. Если каждой сигнальной переменной (с памятью

или без памяти) в системе субъектов S можно присвоить некоторый

порядок, назовем эту систему сильно (локально) упорядоченной.

Если зависимости переменных устроены так, что систему не полу-

чается сделать сильно упорядоченной, то надо эти зависимости раз-

делить таким образом, чтобы они не реализовывались в одном состо-

янии, тогда система окажется локально слабо упорядоченной. В каче-

стве примера рассмотрим систему на рис. 9.

Данная система не является сильно упорядоченной, поскольку

субъект S

1

, содержащий единственный оператор отправки для вто-

рой сигнальной переменной, содержит оператор захвата четвертого

исключающего семафора, кроме того, выполнены следующие соотно-

шения:

τ

(

S

3

,

L

4

)

J

L

τ

(

S

3

,

L

3

)

,

τ

(

S

2

,

L

3

)

J

L

τ

(

S

2

,

W

1

)

.

108

ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012