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

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

Эта проблема уже рассматривалась автором в работе [2], в которой, в частности, показана возможность автоматизации построения структуры перекрытия для транслированных программ, компонуемых из объектных модулей, и описана реализация в ДОС АСВТ автоматического метода перекрытия, позволяющего построить структуру перекрытия, при которой требования программы на память минимальны.

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

Рассмотрим особенности оптимизируемой программы. Программа, написанная на языке модульного типа (например, на Фортране), состоит из основной программы (PROGRAM) и внешних подпрограмм (FUNCTION, SUBROUTINE), которые независимо транслируются и преобразуются в объектные модули. Любой модуль содержит команды программы или подпрограммы и определенные в ней данные. Кроме того, для связи подпрограмм по данным могут использоваться общие области (COMMON), которые определяются в подпрограммах, но размещаются вне их. Положение в памяти объектных модулей и общих областей определяется на этапе компоновки программы.

Таким образом, в общем случае транслированная программа состоит из множества М – (т объектных модулей и множества С={с/) общих областей. Логическая структура программы представляет собой иерархию подчинения модулей, которую можно изобразить ориентированным графом G={M, V}, вершины т{ графа соответствуют модулям, а дуги соединяют пары вершин, соответствующих парам модулей, находящихся в отношении непосредственного подчинения (считается, что модуль rns непосредственно подчинен модулю ть если mt при выполнении может вызвать тЛ. Граф G = (М, V) имеет одну основную вершину ти в которую не заходит ни одна дуга (она соответствует основному модулю); в остальные вершины может заходить одна или несколько дуг; однако в графе G не может быть контуров, так как в языках модульного типа рекурсивные вызовы подпрограмм недопустимы.