5.3. Понятие коллектива алгоритмов

Совокупность всех алгоритмов, связанных некоторым буфером (посредством системы регулирующих предикатов), называется элементарным коллективом алгоритмов. Однако понятие коллектива алгоритмов шире и не сводится к понятию элементарного коллектива.

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

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

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

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

№ 1 - пишущий отрезок; № 2 - три только читающих отрезка; № 3 - читающий и пишущий отрезок; № 4 (последний в серии) - два читающих критических отрезка.

Всякое "постороннее" обращение к несобственному элементу после того, как было произведено обращение № 1 некоторой серии, и до того, как будут выполнены в присущем серии специальном порядке все ее критические отрезки, должно быть исключено.

С одним и тем же несобственным элементом операнда может быть связано несколько критических серий. При этом возможны два случая:

• критические серии естественно упорядочены в силу того, что в них встречаются критические отрезки одного и того же алгоритмического процесса; такие серии называются фиксированными друг относительно друга;
• между двумя критическими сериями нет естественной упорядоченности, так как в них нет критических отрезков, принадлежащих одному и тому же алгоритмическому процессу; такие серии называются плавающими друг относительно друга.

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

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

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

Как и для отдельного алгоритма, для коллектива алгоритмов возможны два случая: коллектив может делать результативную остановку (и тогда он называется применимым к операнду) или быть неприменимым к операнду (безрезультатно останавливаться или никогда не останавливаться). Схватывание - это бесконечно длящийся безрезультатный процесс (кроме случаев остановки коллектива на открытом буфере).