Cтраница 1
Активация подпрограммы, которая должна выполняться параллельно, называется задачей. Основная структура этих средств ПЛ / 1 обсуждается в разд. Атрибуты TASK и PRIORITY используются для управления относительным приоритетом, который получает только что созданная задача от системного планировщика, если параллельное выполнение этой и исходной задач невозможно. Более важен атрибут EVENT, применяемый для синхронизации двух задач. [1]
Легко объяснить эту трудность с помощью активаций подпрограмм. При наличии рекурсии у одной подпрограммы может быть сколь угодно много активаций, поэтому очевидно, что одной ячейки для точки возврата недостаточно. Более того, недостаточно также выделить для точек возврата фиксированную область памяти, так как, вообще говоря, невозможно предсказать максимальный размер этой области. Вместо этого для записи точек возврата нам нужен стек, который может по мере необходимости расширяться во время выполнения программы. [2]
Обычно все элементы, связанные с одной активацией подпрограммы и требующие памяти в стеке, группируются в единую активационную запись. При вызове подпрограммы на вершине стека создается новая активационная запись. Завершение подпрограммы вызывает удаление активационной записи из стека. [3]
Говоря о планировании подпрограмм, мы имеем в виду пла-нирование активаций подпрограмм, поскольку планирование происходит во время выполнения программы и активации одной и той же программы могут быть запланированы в разных местах. При обобщенном планировании подпрограмм программист больше не пишет главной программы. Вместо этого главной является определенная в системе программа-планировщик, которая обычно ведет список текущих запланированных активаций программ, где программы расположены в том порядке, в котором они должны выполняться. В языке имеются инструкции, с помощью которых можно во время выполнения вставить подпрограмму в этот список. Действия планировщика заключаются в вызове подпрограмм, находящихся в списке, в указанной последовательности. Когда выполнение одной подпрограммы завершается, начинается выполнение следующей подпрограммы из списка. Как правило, обеспечивается также обычный вызов подпрограмм, иногда для этого просто разрешается приостановить выполнение подпрограммы и запланировать немедленное выполнение другой подпрограммы. [4]
Перед тем, как рассматривать различные варианты структур, управляющих подпрограммами, следует провести важное различие между определением подпрограммы и активацией подпрограммы. [5]
Самый распространенный подход к планированию подпрограмм в языках моделирования основан на обобщенных сопрограммах. Выполнение одной активации подпрограммы протекает в виде серии активных и пассивных фаз. В течение активной фазы подпрограмма имеет управление и выполняется; при наступлении пассивной фазы подпрограмма передает управление в другое место и ждет сигнала на возобновление. Однако в от личие от сопрограмм, которые при переходе от активной к пассивной фазе передают управление непосредственно другой сопрограмме, здесь управление возвращается планировщику, который передает управление следующей подпрограмме из списка запланированных активаций. Передача управления может принять вид сигнала на возобновление подпрограммы, если она уже частично выполнилась, либо может быть создана совершенно новая активация подпрограммы. [6]
Привлекательность стекового метода управления памятью легко объясняется характерной для многих языков строго вложенной структурой входов в подпрограммы и выходов из них, подчиняющейся правилу последний вошел - первый вышел. Многие элементы программы и данных, требующие памяти, связаны с активациями подпрограмм. Часто оказывается, что стековую память можно использовать как для точек возврата из подпрограмм, так и для таблиц локальной среды подпрограмм, о которых говорилось в предыдущих главах. Кроме того, выделение памяти для временных переменных, используемых при вычислении выражений и передаче параметров, в большинстве случаев также может быть связано с активациями подпрограмм. Обычно транслятор может определить число временных переменных, требуемых для каждой активации подпрограммы. [7]
Определение подпрограммы служит образцом для построения во время выполнения ее активации - Обычно результатом обработки определения подпрограммы транслятором является постоянная часть, содержащая выполняемые команды, константы и другие составные части программы, которые одинаковы во всех активациях, и шаблон активационной записи, представляющий ту часть подпрограммы, которая зависит от активации. Когда во время выполнения происходит вызов подпрограммы, этот шаблон используется при построении активационной записи для новой активации подпрограммы. В типичной активационной записи предусмотрено место для локальных данных подпрограммы, параметров, точки возврата, временной памяти и различных элементов системной информации. Акти-вационная запись вместе с постоянной частью подпрограммы составляют активацию этой подпрограммы. [8]
В большинстве реализаций Алгола используется центральный стек активационных записей для подпрограмм ( и блоков) и статически распределяемая область памяти, содержащая пользовательские и системные программы, буферы ввода-вывода и константы. Структура типичной активационной записи для Алгол-подпрограммы показана на рис. 7.1. Активационная запись содержит все переменные элементы информации, связанные с данной активацией подпрограммы. На рис. 7.2 показана типичная организация памяти при выполнении Алгол-программ. [9]
Управление памятью во время выполнения программ, написанных на ПЛ / 1, представляет довольно сложную проблему. Должна существовать большая статическая область, необходимая для хранения выполняемой программы, вспомогательных программ, структур данных, переменных с классом памяти STATIC, а также различных данных, определяемых системой. Для записей активаций подпрограмм и блоков используется центральный стек. Каждая запись активации в общем случае состоит из статического указателя цепочки, точки возврата, областей памяти для переменных и структур данных с классом памяти AUTOMATIC, системных данных, касающихся разрешения прерываний и программ прерываний, определяемых инструкциями ON, а также других системных данных. Обычно для выделения памяти во время выполнения программы используется центральный стек. [10]
В различ-ных языках моделирования применяются различные механиз-мы. В GPSS, например, в каждой активации подпрограммы можно обращаться только к локальной или глобальной среде Программист должен управлять разделением данных посред-ством глобальной среды, общей для всех активаций. [11]
На каждом из этих шагов нужно изменять среду ссылок. На рис. 6.16 изображены среды ссылок, действующие между любыми двумя соседними шагами. Заметим, что, когда процедура или метка передается новой активации подпрограммы в каче-стве параметра, передается также указатель на локальную таб-лицу, в которой была найдена ассоциация для фактического параметра. Например, на шаге 2 в качестве фактического параметра Р передается QHUM, а также указатель на локальную таблицу В, в которой имеется ассоциация для Q. На шаге 3, когда Р вызывает QHUxc через формальный параметр X, указатель статической цепи в таблице для ( ниж можно установить так, чтобы он указывал на таблицу В, создавая тем самым нужную для выполнения Qh m нелокальную среду. Читателю рекомендуется для каждого шага самостоятельно определить: каким образом можно перейти от предыдущей среды к следующей, имея только эту предыдущую среду; форматы таблиц, показанные на рис. 6.15; и выполняемую инструкцию программы. Заметим, что текущая локальная среда на каждом шаге задается специальным указателем головы статической цепи ( ГСЦ), который хранится в фиксированном месте. Чтобы яснее показать различные среды ссылок в разные моменты выполнения, мы использовали представление в виде дерева, а не непо средственно стековую структуру. Заметим, что локальные таблицы уничтожаются в порядке, строго обратном порядку их со-здания, и поэтому можно создавать и уничтожать таблицы, помещая их в единственный стек. [12]
Как влияют на выбор среды ссылок рекурсивные подпрограммы. В любой момент выполнения у рекурсивной подпрограммы может быть много одновременно существующих активаций. Среды ссылок в различных активациях одной подпрограммы могут в общем случае отличаться друг от друга. Таким образом, перед нами стоит задача определения среды ссылок для каждой активации подпрограммы. [13]
Нелокальные ссылки в рекурсивных подпрограммах не вызывают никаких особых проблем при любом из трех подходов к нелокальным средам. Каждый подход немедленно распространяется на случай рекурсии. При явно описываемой нелокальной среде X является глобальным и, следовательно, существует только в одной активации. В методе статической блочной структуры при обработке ссылки на X ассоциация для X будет выбираться из наиболее поздней активации подпрограммы, в которой описан X. В методе последней ассоциации нужная ассоциация будет, конечно, выбираться из последней активации в цепи вызовов. [14]
Привлекательность стекового метода управления памятью легко объясняется характерной для многих языков строго вложенной структурой входов в подпрограммы и выходов из них, подчиняющейся правилу последний вошел - первый вышел. Многие элементы программы и данных, требующие памяти, связаны с активациями подпрограмм. Часто оказывается, что стековую память можно использовать как для точек возврата из подпрограмм, так и для таблиц локальной среды подпрограмм, о которых говорилось в предыдущих главах. Кроме того, выделение памяти для временных переменных, используемых при вычислении выражений и передаче параметров, в большинстве случаев также может быть связано с активациями подпрограмм. Обычно транслятор может определить число временных переменных, требуемых для каждой активации подпрограммы. [15]