5.4. Важные возможности коллективов алгоритмов

Защита буферов с помощью регулирующих предикатов не является единственным способом объединения алгоритмов в коллектив. Рассмотрим случай "захвата" резерва. Если ограничиться коллективом двух алгоритмов, то схема пользования резервом такова: любой алгоритм обращается к резерву, если им не пользуется другой, и на время пользования запрещает другому алгоритму обращаться к резерву. Оказывается, проблема защиты резерва гораздо сложнее, чем проблема защиты буфера другого типа.

Для облегчения анализа этого случая сделаем одно общее замечание. Для защиты как буфера, так и резерва вовсе не обязательно применять предикаты, которые выражали бы глобальные свойства всей защищаемой подконструкций. Можно выбрать в ней очень простую под-подконструкцию и на нее наложить проверяемое условие. Ведь изменить только одну букву - это уже изменить всю подконструкцию. Такие под-подконструкции обычно называют ячейками. Ячейка, состояние которой используют для проверки состояния всей подконструкций, называется сигнальной. Нужно помнить, что сигнальная ячейка - это часть защищаемой подконструкций. В следующих семантических схемах я буду ячейки обозначать малыми латинскими курсивными буквами с черточкой над ними и, если надо, с постоянным или буквенным (переменным) индексом внизу.

Теория изучает потенциально осуществимые процессы, т. е. отвлекается от ограниченности ресурсов. С помощью такого приема теоретики обеспечивают себе относительно "легкую жизнь". Практики, увы, вынуждены считаться с наличием ресурсов. Если для теоретика резерв - это, в лучшем случае, занятная головоломка, то для практика - это вопрос успеха. Военные специалисты говорят, что резерв - это не запас, а силы для нанесения главного удара.

Итак, вернемся к вопросу защиты резерва, или, если хотите, его захвата и защиты. Пусть даны два алгоритма, претендующих на резерв . Для обеспечения бесконфликтности нужны три простых буфера, сводящихся к отдельным ячейкам. Обозначим их и . Предположим, что каждый из двух первых может принимать значения либо 0, либо 1, а третий - либо 1, либо 2. Начальное состояние буферов может быть следующим: начальное состояние буфера принципиального значения не имеет. Та часть первого алгоритма, которая производит захват резерва может иметь следующую семантическую схему ( - собственная подконструкция):

Соответствующую часть схемы второго алгоритма получим, меняя ролями и и предписывая приказом 56 ждать = 2. Понятно, что номера приказов (метки и отсылки) могут быть сдвинуты. Обе схемы алгоритмов A₁ и А₂ графически изображены на рис. 5.2.

Рис. 5. 2. Схема двух алгоритмов, 'претендующих' на один и тот же резерв R

В приведенной схеме приказы 57 и 58 изображают работу с резервом. В приказе 51 предусмотрена запись в буфер значения 1 (до этого там был 0). Если бы я был педантом, то перед приказом 51 я поставил бы приказ но он пропущен потому, что это условие в момент выполнения приказа 51 всегда выполняется. Этим приказом первый алгоритм сообщает второму о том, что захват резерва им начат. Затем приказ 52 предусматривает проверку того, начал ли также захватывать резерв второй алгоритм. Если не начал (т. е. если ), то первый алгоритм занимает резерв. Второй алгоритм его уже не сможет занять до конца работы первого. Кончив работу с резервом, первый алгоритм делает равным 2 и равным 0 (приказы 59 и 60).

50) Ожидать

Если бы приказ 52 установил, что второй алгоритм тоже начал захват резерва, то было бы проверено значение буфера , говорящего о том, чья сейчас очередь занимать резерв. Если очередь первого алгоритма, то начинается ожидание условия , которое второй алгоритм должен будет выполнить (своим приказом 55). если же очередь второго, то первый алгоритм начинает ждать свою очередь (приказ 56) и занимает буфер тогда, когда эта очередь придет.

Приказ 52 фактически представляет собой "кусочек" ожидания, оторвавшийся от приказа 54. Прерывать ожидание для выполнения преобразований нельзя, а для выполнения логических операций, не изменяющих состояние буфера,- можно.

В последнем примере буферы и не совсем обычны. Например, буфер может изменяться только первым алгоритмом, тогда как во втором алгоритме предусмотрено только ожидание предикатов . Такое применение буфера называется задержкой с помощью предиката. В данном случае, записывая (приказ 51) в ячейку значение 1, первый алгоритм производит задержку, а приказом 60 ее снимает. Аналогично, второй алгоритм производит задержку первого, записывая в ячейку значение 1, а после конца работы с резервом ее снимает.

Задержка предикатом действительно приостанавливает процесс выполнения только в случае, если "задерживаемый" процесс еще не миновал приказа, содержащего операцию ожидания задерживающего предиката. Сработает или нет задержка, зависит от соотношения между скоростями протекания алгоритмических процессов. Это заставляет проявлять большую осторожность, применяя задержки.

Итак, рассмотрев последний пример, мы изучили сразу две новые возможности коллективов: захват резерва и задержку посредством предиката.

Обобщение описанного приема захвата резерва с двух на n алгоритмов оказывается чрезвычайно трудным. Это связано с необходимостью учитывать соотношения между конкурирующими алгоритмическими процессами во всевозможных их сочетаниях. Значительно проще организовать очередь и предоставлять резерв в соответствии с занятой очередью. Для ведения очереди можно отвести один из алгоритмов коллектива. Посмотрим, как это сделать.

Предположим, что для ведения очереди выделены 2n+1 ячеек: и Для того чтобы занять очередь, n-й алгоритм должен в ячейку записать значение 1 (а до этого там должно быть значение 0). Затем нужно ожидать появления в ячейке числа i (номера алгоритма) и приступить к работе с резервом. Приказы для записи в очередь будут:

Если в последнем приказе вместо отсылки "4" поставить "стоп", то эти три приказа образуют запись алгоритма. Объявим индуцируемую им функцию операцией и обозначим ее "Занять ". Для того чтобы процесс "нахождения в очереди" более заметно выражался в записи семантической схемы алгоритма, объявим еще с помощью алгоритма

операцию, которую обозначим "Освободить ()".

Теперь участок захвата резерва в записи схемы может иметь вид

Здесь i - номер алгоритма, - его собственная подконструкция, - как и прежде, резервная подконструкция операнда.

Алгоритм ведения очереди может иметь простой вид, если сначала объявить две следующие операции:

1. Операция объявляется в соответствии с алгоритмом, имеющим запись

Рис. 5.3. Схема алгоритма, индуцирующего операцию img src='pic/000117.gif' border='0'

До начала работы алгоритма, ведущего очередь, а значит, и до первого выполнения данной операции, i может иметь любое целое значение из интервала [1, n]. На рис. 5.3 показано, что до начала работы выполняется операция (но это не существенно).

Рис. 5.4. Схема, поясняющая возникновение мерцающего клинча

Алгоритм, индуцирующий операцию , в скрытом виде имеет аргументы - имена ячеек, в которые алгоритмы-клиенты записывают "заявку" на включение в очередь (A_i записывает код 1 в ячейку ). Он эти ячейки просматривает (в кольцевом порядке) и, как только обнаруживает очередную заявку, записывает вместо нее 0, а переменной j присваивает номер алгоритма, сделавшего заявку. Если при просмотре 1-, 2-, ..., n-й ячейки ни одной "заявки" не обнаружено, производится присваивание и алгоритм настраивается на новый просмотр ячеек, начиная с 1-й.

2. Операция "Сделать шаг" объявляется по алгоритму

Эта операция продвигает очередь на один шаг и освобождает в ней последнее место для очередного "претендента" на резерв.

Теперь без труда сделаем запись алгоритма ведения очереди:

Приведенная семантическая схема алгоритма ведения очереди предполагает простейшую организацию очереди. Ячейки просматриваются в порядке их номеров и все обнаруженные в них заявки последовательно включаются в очередь. Если заявок нет, в очередь заносится нуль. После того, как резерв освобождается, очередь продвигается на один шаг (в том числе и нули, если они стоят в очереди). При необходимости можно реализовать более сложное ведение очереди.

Говоря о захватах резервов, нельзя ничего сказать об особом случае схватывания, который с ними связан.

Захват резерва одним из алгоритмов запрещает обращения всех других алгоритмов к этому резерву на время захвата. Представим теперь, что коллектив состоит из двух алгоритмов и что имеется два резерва R и Q. Пусть в первом алгоритме предусмотрен захват резерва б в то время, когда R уже захвачен, но еще не освобожден, а во втором - захват резерва R, когда уже захвачен, но еще не освобожден резерв Q. Описанную ситуацию поясняет рис. 5.4. При выполнении таких алгоритмов возможны два случая:

1. один из алгоритмов успеет захватить оба резерва раньше, чем второй захватит хотя бы один;
2. первый алгоритм успеет захватить R, но не Q, а второй успеет захватить Q, но не R.

В первой из указанных ситуаций выполнение обоих алгоритмов произойдет беспрепятственно, а во второй алгоритмы схватятся (будет клинч). Произойдет или не произойдет схватывание - зависит от соотношения скоростей выполнения алгоритмов. Описанное схватывание (клинч) является мерцающим. На рис. 5.4. области алгоритмических процессов, одновременное вхождение в которые вызывает наступление мерцающего клинча, обозначены соответственно буквами А к В.

Мерцающий клинч предотвращается объединением двух ресурсов R и Q в один объединенный ресурс (если невозможно так перестроить алгоритмы, чтобы области А и В отсутствовали). Это должно быть сделано в процессе разработки алгоритмов.

В более общем случае захваты резервов могут осуществляться не одиночными алгоритмами, а их группами.