Оверлейная структура программ

В разд. 2.4.1 мы обсуждали реализацию двухпросмотрового ассемблера и простой оверлейной структурой. Такой способ реализации позволяет сократить суммарный объем оперативной памяти, требуемой для ассемблирования, так как для первого и второго просмотров используется одно и то же пространство. В этом разделе мы рассмотрим более сложный пример и обсудим, как осуществляется управление самим оверлейным процессом. В качестве введения в данную тему вам следует обратиться к рис. 2.18 и 2.19 и материалу разд. 2.4.1.

На рис. 3.12а показана программа с оверлейной структурой, которую мы будем использовать в качестве примера. Буквами обозначены имена управляющих секций, а линиями - связи между ними по передаче управления. Таким образом, корневая управляющая секция (соответствующая ведущей подпрограмме на рис.2.18) имеет имя А. Управляющая секция А может вызывать секции В, С или D/E; секция В может вызывать F/G или Н и т. д. Обозначение D/E используется для спецификации двух управляющих секций (D и Е), которые тесно связаны между собой и всегда используются совместно. Хотя эти управляющие секции раздельно обрабатываются ассемблером и загрузчиком, однако в оверлейной структуре они рассматриваются как одно целое. Например, D может содержать исполняемые команды, в то время как Е - связанные с ними данные. Другой пример - Е может содержать часто используемые в D подпрограммы. На рис. 3.12в показана длина (в шестнадцатеричном виде) каждой управляющей секции.

 

A

 

 

B C D/E

 

 

F/G H I J K

a

 

Управляющая

секция Длина (в байтах)

A 1000

B 1800

C 4000

D 2800

E 800

F 1000

G 400

H 800

I 1000

J 800

K 2000

 

б

 

Рис.3.12. Пример оверлейной программы.

 

Большинство систем, поддерживающих оверлейные программы, требует, чтобы они имели древовидную структуру (т. е. такую, как на рис. 3.12а). Узлы такого дерева называются сегментами. Корневой сегмент загружается в самом начале исполнения программы и остается в памяти до окончания счета. Остальные сегменты загружаются тогда, когда к ним происходит обращение. Предположим, например, что управляющая секция А вызывает В. Этот вызов приведет к автоматической загрузке сегмента, содержащего В (если только он уже не находится в оперативной памяти), *ели позднее А вызовет D, то будет загружен сегмент, содержащий секцию D. Порядок расположения сегментов, находящихся на одном уровне сверленной структуры, значения не имеет. Например, А может сначала вызвать С, затем В, затем D/E, потом вновь С и т. д.

Предположим, что в некоторый момент времени исполняется управляющая секция Н. Она была вызвана секцией В, которую в свою очередь вызвала секция А. Таким образом, эти три сегмента являются активными и должны находиться в оперативной памяти. Другие сегменты не могут быть активными, поскольку нет путей, связывающих их с Н. Например, если ранее был вызван сегмент, содержащий К, то он должен был вернуть управление D/E (и затем А) прежде, чем В мог быть вызван из секции А. Данные рассуждения приводят нас к правилу, которое используется в большинстве систем, допускающих оверлейные структуры: если сегмент S находится в оперативной памяти, то все другие сегменты, расположенные на пути, ведущем из S к корню, также должны находиться в оперативной памяти. Соблюдение этого правила упрощает организацию оверлея. Если некоторый сегмент вызывает сегмент, расположенный на более низком уровне древовидной структуры (т. е. находящийся дальше от корня), то может потребоваться загрузка этого сегмента в оперативную память. С другой стороны, если некоторый сегмент ссылается на сегмент, лежащий между ним и корнем, то этот сегмент уже находится в памяти.

Поскольку сегменты одного уровня (например, В, С и D/E) могут вызываться только из сегмента вышестоящего уровня, то они не требуются одновременно. Поэтому они могут совместно использовать одну и ту же область оперативной памяти. Если передача управления вызывает загрузку некоторого сегмента, то он замещает в памяти сегмент, который находится на одном с ним уровне (и сегменты ему подчиненные). Таким образом, общий объем оперативной памяти, требуемой для исполнения программы, оказывается меньше. Это и является основной причиной использования оверлейных структур.

Оверлейная структура программы описывается при помощи команд загрузчика, похожих на те, что мы рассматривали в предыдущем разделе. На рис. 3.13 приведен набор команд, который задает оверлейную структуру, изображенную на рис. 3.12а. Команда

SEGMENT имя - сегмента (управляющая-секция...)

определяет сегмент (т. е. узел древовидной структуры). Данная команда задает имя сегмента и описывает список входящих в него управляющих секций. Первый определяемый сегмент - это корень. Два последовательных предложения SEGMENT задают между описываемыми сегментами отношение вида отец - сын. Поэтому на рис. 3.13 первые три предложения описывают самый левый путь *от корня к F/G) структуры на рис. 3.12а.

Остальные сегменты, имеющие общего отца, на рис. 3.13 задаются с помощью предложений другого типа. Предложение

PARENT имя – сегмента

описывает сегмент (ранее определенный), который является отцом следующего за ним сегмента. Таким образом, на рис. 3.13 первое предложение PARENT определяет, что SEG2 является отцом SEG4. Если бы этого предложения не было, то отцом SEG4 считался бы сегмент SEG3.

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

 

SEGMENT SEG1(A)

SEGMENT SEG2(B)

SEGMENT SEG3(F,G)

PARENT SEG2

SEGMENT SEG4(H)

PARENT SEG1

SEGMENT SEG5(C)

PARENT SEG1

SEGMENT SEG6(D,E)

SEGMENT SEG7(I)

PARENT SEG6

SEGMENT SEG8(J)

PARENT SEG6

SEGMENT SEG9(K)

 

Рис.3.13. Определения оверлейной структуры с помощью управляющих предложений.

 

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

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

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

 

Начальный адрес

Сегмент Относительный Фактический Длина

1 0000 8000 1000

2 1000 9000 1800

3 2800 A800 1400

4 2800 A800 800

5 1000 9000 4000

6 1000 9000 3000

7 4000 C000 1000

8 4000 C000 800

9 4000 C000 2000

 

a

 

· · · ·

· · · ·

· · · ·

8000

A A A

9000

· B

A000 ·

· D

H

B000

· E

C000 ·

·

·

D000 ·

·

 

E000

·

·

·

 

б

 

Рис.3.14. Распределение памяти для оверлейной программы.

 

Фактическая загрузка сегментов в процессе исполнения программы осуществляется специальной программой - менеджером оверлея (overlay manager). В нашем примере менеджер оверлея расположен в отдельной управляющей секции с именем OVLMGR. Эта секция автоматически включается загрузчиком в корневой сегмент оверлейной программы. Для управления загрузкой сегментов OVLMGR должен иметь информацию об оверлейной структуре программы. Эта информация хранится в таблице сегментов (SEGTAB), которая создается загрузчиком и включается в корневой сегмент в виде отдельной управляющей секции. Таблица SEGTAB описывает древовидную структуру, определяя уровень расположения каждого из сегментов. Для каждого сегмента она также содержит его начальный адрес загрузки, адрес входной точки и месторасположение сегмента в SEGFILE. (В данной реализации мы полагаем, что сегмент может вызываться только по одной входной точке).

Кроме того, для каждого сегмента, за исключением корня в SEGTAB, имеется область передачи управления. Она содержит команды, которые обеспечивают передачу управления на требуемый сегмент. Если сегмент уже загружен в оперативную память, то его область передачи управления содержит простую команду перехода на входную точку сегмента. Если сегмент не загружен, то область передачи управления содержит команды активизации OVLMGR и передачи ему информации, необходимой для загрузки сегмента. В процессе своей работы менеджер оверлея изменяет команды в области передачи управления так, чтобы они всегда соответствовали текущему статусу каждого из сегментов. Обращение одного сегмента к другому, стоящему на следующем уровне древовидной структуры (т. е. обращение, которое может потребовать оверлейную загрузку), преобразуется загрузчиком в обращение к области передачи управления соответствующего сегмента. Область передачи управления всегда присутствует в оперативной памяти, так как SEGTAB расположена в корневом сегменте. Затем команды области передачи управления либо непосредственно передают управление на требуемый сегмент, либо активизируют OVLMGR. В последнем случае OVLMGR загружает требуемый сегмент, обновляет SEGTAB и после этого передает управление сегменту.

Иллюстрация описанного процесса дана на рис. 3.15. На рис. 3.156 показано содержимое оперативной памяти на некотором этапе исполнения программы. В данный момент загружены Сегменты 1, 2, 4 и исполняются команды управляющей секции А. Сегменты 2 и 4 были загружены в ответ на ранее выполненные команды вызова. Хотя сейчас управление вернулось Сегменту 1, однако Сегменты 2 и 4 продолжают оставаться в оперативной памяти до тех пор, пока их не заменят другие сегменты. Области передачи управления Сегментов 2 и 4 содержат команды перехода на управляющие секции В и Н. Остальные области передачи управления содержат команды активизации OVLMGR (соответствующие им поля SEGTAB заштрихованы). Если в управляющей секции А сейчас будет выполнена команда вызова секции В (в исходной программе команда +JSUB В), то в результате выполнится переход в область передачи управления Сегмента 2. Как показано на рисунке, это приведет к прямой передачи управления на секцию В.

·

·

·

OVLMGR

 

2

3

4

5 SEGTAB

6 Корневой сегмент

7 (SEG1)

8

9

 

+JSUB B

A

 

 

B Сегмент#2

(SEG2)

H Сегмент#4

(SEG4)

 

·

·

·

 

 

а

 

 

 

·

·

·

OVLMGR

 

2

3

4

5 SEGTAB

6 Корневой сегмент

7 (SEG1)

8

9

 

 

A

+JSUB D

 

B Сегмент#2

(SEG2)

H Сегмент#4

(SEG4)

 

·

·

·

 

б

 

·

·

·

OVLMGR

2

3

5 SEGTAB

6 Корневой сегмент

7 (SEG1)

8

9

 

 

A

 

 

 

D Сегмент#6

(SEG6)

 

 

E

 

·

·

·

 

 

в

 

Рис.3.15. Пример управления оверлеем.

 

Предположим теперь, что А вызывает D. На рис. 3.15 показано, что область передачи управления, соответствующая Сегменту 6, содержит команды активизации OVLMGR. Менеджер оверлея загрузит Сегмент 6 из SEGFILE на выделенное ему место в оперативной памяти. Затем он обновит SEGTAB, указав, что в данный момент Сегмент 6 находится в памяти, а Сегменты 2 и 4 нет. Заметим, что Сегмент 4 должен быть удален из памяти (даже если занятое им пространство не требуется для нового сегмента), так как удален его отец. Теперь для вызова секции D остается передать управление на входную точку Сегмента 6 (см. рис. 3.15в).

Возврат управления из вызванного сегмента (например, из D в А) может выполняться обычным образом. (Активизация OVLMGR для этого не требуется.) Например, команда JSUB (рис. 3.156) может занести адрес возврата в регистр L. Менеджер оверлея сохранит это значение. Таким образом, по завершению своей работы управляющая секция D может просто выполнить команду RSUB. Это тот же самый механизм, который используется для программ без оверлейной структуры.

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

 

Варианты построения загрузчиков

В данном разделе мы рассмотрим некоторые общие варианты реализации функций загрузчика, включая перемещение и связывание. Связывающие загрузчики, рассмотренные в разд. 3.2.3, выполняют связывание и перемещение в процессе загрузки. Здесь мы обсудим две альтернативные схемы-редакторы связей, выполняющие связывание перед загрузкой, и динамическое связывание, в котором функции связывания осуществляются во время исполнения программы.

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

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

В разд. 3.4.3 мы обсудим раскручивающие загрузчики (boot-strap loaders). Такие загрузчики могут использоваться для программ, выполняемых без операционной системы или системного загрузчика. Они также могут применяться для загрузки в оперативную память самой операционной системы или системного загрузчика.

Редакторы связей

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

 

 

 

 

 

 

		Оператив ная память

 

 

а

 

		Перемещающий загрузчик
		Оператив ная память

 

 

б

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

 

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

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

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

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

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

INCLUDE PLANNER(PROGLIB)

DELETE PROJECT (Исключить из старой версии)

INCLUDE PROJECT(NEWLIB) Включить новую версию)

REPLACE PLANNER(PROGLIB)

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

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

INCLUDE READR(FTNLIB)

INCLUDE WRITER(FTNLIB)

INCLUDE BLOCK(FTNLIB)

INCLUDE DEBLOCK(FTNLIB)

INCLUDE ENCODE(FTNLIB)

INCLUDE DECODE(FTNLIB)

.

.

.

SAVE FTNIO(SUBLIB)

 

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

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

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

Динамическое связывание