Квазипараллельное выполнение

Состояние выполнения программы лучше всего можно опи­сать структурой дерева, узлы которого являются экземпля­рами блоков с префиксами. Поддерево, «корнем» которого является экземпляр блока с префиксом, называется «квази­параллельной системой». Экземпляр блока с префиксом, включая экземпляры блоков, динамически вложенных в него, называется «главной программой» данной квазипараллельной системы.

С каждой квазипараллельной системой связан «уровень системы», т. е. количество экземпляров блоков с префиксами, объемлющих ее главную программу. Программа в целом яв­ляется квазипараллельной системой с уровнем системы, рав­ным нулю.

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

С любой компонентой системы связано «локальное упра­вление» (ЛУ), а с каждой квазипараллельной системой в це­лом - «внешнее управление» (ВУ), Внешнее управление на уровне системы, равном нулю, совпадает с УП. ВУ некоторой квазипараллельной системы на уровне k (k>=1) совпадает с ЛУ той компоненты на (k - 1)-м уровне системы, которая объемлет данную систему.

Для любой данной квазипараллельной системы в каждый данный момент одна и только одна из ее компонент является «активной». ЛУ этой компоненты совпадает с ВУ квазипарал­лельной системы.

Экземпляр блока с префиксом вначале активен, т. е. вна­чале ВУ его собственной квазипараллельной системы нахо­дится в нем самом. ВУ некоторой системы может переходить из компоненты в компоненту в результате действия некото­рых операторов, которые будут описаны в последующих раз­делах. ЛУ некоторой компоненты, не содержащей ВУ, остает­ся в той точке программы, в которой ВУ покинуло объект в последний раз.

В любой данный момент существует такая последователь­ность компонент систем X₁, Х₂,..., Х_n, что:

· Xk активна на уровне системы k (k = 0, 1,..., n);

· Xk вложена в Xk-1 (k = 1,2,..., n);

· в Хn не вложено никакой квазипараллельной системы.

Эта последовательность называется «работающей цепоч­кой». Все компоненты системы в работающей цепочке содер­жат УП и поэтому называются работающими. ЛУ некоторой компоненты остается неподвижным до тех пор, пока эта ком­понента не станет членом работающей цепочки.