Таблицы и алгоритмы связывающего загрузчика

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

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

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

 

Pass 1:

 

begin

получить PROGADDR от операционной системы

занести в CSADDR значение PROGADDR {для первой управляющей секции}

while не конец входного потока do

begin

прочитать следующую входную запись

{запись- заголовок управляющей секции}

занести в CSLTH длину управляющей секции

поиск имен управляющей секции в ESTAB

if нашли then

занести признак ошибки (дважды определенное внешнее имя)

else

занести имя управляющей секции в ESTAB со значением CSADDR

while тип записи () "Е" do

begin

прочитать следующую входную запись

if тип записи = "D" then

for для каждого имени записи do

begin

поиск имени в ESTAB

if нашли then

занести признак ошибки

(дважды определенное внешнее имя)

else

занести имя в ESTAB со значением

(CSADDR + указанный адрес)

end { for }

end { while () "E" }

прибавить CSLTH к CSADDR

{ начальный адрес следующей управляющей секции }

end { while не конец }

end { Pass 1 }

 

Рис.3.10а. Алгоритм первого просмотра связывающего загрузчика.

 

Сам алгоритм показан на рис.3.10а и 3.10б. В процессе обсуждения этого алгоритма вам, возможно, будет полезно вспомнить примеры загрузки и связывания, рассмотренные в предыдущем разделе (рис. 3.8 и 3.9).

 

 

Pass 2:

 

begin

занести в CSADDR значение PROGADDR

занести в EXECADDR значение PROGADDR

while не конец входного потока do

begin

прочитать следующую входную запись { запись- заголовок }

занести в CSLTH длину управляющей секции

while тип записи () "E" do

begin

прочитать следующую входную запись

if тип записи = "T" then

begin

{ если объектный код представлен в символьном виде, то

преобразовать его во внутреннее представление }

занести объектный код записи по адресу

(CSADDR + указанный адрес)

end { if "T" }

else if тип записи = "М" then

begin

поиск модифицируемого имени в ESTAB

if нашли then

прибавить или вычесть значение имени к адресу

(CSADDR + указанный адрес)

else

занести признак ошибки

(неопределенное внешнее имя)

end { if "M" }

end { while () "E" }

if адрес определен { в записе-конец } then

занести в EXECADDR значение (CSADDR + указанный адрес)

прибавить CSLTH к CSADDR

end { while не конец }

перейти по адресу, заданному в EXECADDR { начать исполнение программы }

end { Pass2 }

 

Рис.3.10б. Алгоритм второго просмотра связывающего загрузчика.

 

Во время первого просмотра (рис.3.10а) загрузчик обрабатывает только запись-заголовок и записи-определения управляющих секций. Начальный адрес загрузки связываемой программы (PROGADDR) загрузчик получает от операционной системы. Этот адрес становится начальным адресом (CSADDR) первой управляющей секции входного потока. Имя управляющей секции, полученное из записи-заголовка, записывается в ESTAB и ему присваивается текущее значение CSADDR. Все внешние имена из записей-определителей также заносятся в ESTAB. Значение их адресов получаются путем сложения значения из записи-определения с CSDDR. После того как будет прочитана запись-конец, к CSADDR добавляется длина управляющей секции (CSLTH). (Длина была получена из записи-заголовка.). Таким образом, мы получаем начальный адрес для следующей управляющей секции.

После завершения первого просмотра ESTAB содержит все внешние имена, определенные в данном наборе управляющих секций, вместе с назначенными им адресами. Многие загрузчики могут по желанию пользователя выдавать на печать таблицу загрузки, в которой показаны внешние имена и их адреса. Эта информация часто используется для отладки программ. Для примеров, приведенных на рис. 3.8 и 3.9, такая таблица загрузки может выглядеть следующим образом:

 

Управляющая секция Имя Адрес Длина

__________________________________________________________

PROGA 4000 0063

LISTA 4040

ENDA 4054

PROGB 4063 007F

LISTB 40СЗ

ENDB 40D3

PROGC 40E2 0051

LISTC 4112

ENDC 4124

__________________________________________________________

 

 

По существу это та же информация, которая содержится в ESTAB в конце первого просмотра.

Собственно загрузка, перемещение и связывание программы осуществляются во время второго просмотра (рис.3.10б). Переменная CSADDR используется так же, как и во время первого просмотра. Она всегда содержит фактический начальный адрес загружаемой в данный момент управляющей секции. После того, как считана очередная запись тела программы, содержащийся в ней объектный код помещается по указанному адресу (плюс текущее значение CSADDR). Когда встречается запись-модификатор, то имя, требуемое для модификации, ищется в ESTAB и затем его значение прибавляется к заданному адресу или вычитается из него.

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

Вам следует применить данный алгоритм (вручную) для загрузки и связывания объектной программы, изображенной на распечатке 13. Если для PROGADDR использовать 4000, то полученный результат; должен быть таким, как показано на рис. 3.9.

Можно несколько повысить эффективность данного алгоритма, если слегка изменить формат объектной программы. Суть этих изменений заключается в том, что каждой внешней ссылке присваивается специальный ссылочный номер. Эти ссылочные номера используются в записях-модификатоpax вместо имен.

Предположим, что имя управляющей секции всегда имеет ссылочный номер 01. Ссылочные номера остальных внешних ссылок определены в записи-ссылке объектной программы данной управляющей секции. На рис.3.11 показано, как будет выглядеть объектная программа, изображенная на рис.3.8, после внесения в нее указанных изменений. Для удобства чтения объектной программы ссылочные номера подчеркнуты. Описанный здесь механизм часто используется в реальных загрузчиках, и это была одна из причин, почему мы включили наше объектное представление записи-ссылки. Вы могли заметить, что в алгоритме на рис. 3.10 эти записи не использовались.

 

H_PROGA _000000_000063

D_LISTA _000040_ENDA _000054

R_ 02 LISTB _ 03 ENDB _ 04 LISTC _ 05 ENDC

*

*

T_000020_0A_03201D_77100004_050014

*

*

T_000054_0F_000014_FFFFF6_00003F_000014_FFFFC0

M_000024_05_+ 02

M_000054_06_+ 04

M_000057_06_+ 05

M_000057_06_- 04

M_00005A_06_+ 05

M_00005A_06_- 04

M_00005A_06_+ 01

M_00005D_06_- 03

M_00005D_06_+ 02

M_000060_06_+ 02

M_000060_06_- 01

E_000020

 

 

H_PROGB _000000_00007F

D_LISTB _000060_ENDB _000070

R_ 02 LISTA _ 03 ENDA _ 04 LISTC _ 05 ENDC

*

*

T_000036_0B_03100000_772027_05100000

*

*

T_000070_0F_000000_FFFFF6_FFFFFF_FFFFF0_000060

M_000037_05_+ 02

M_00003E_05_+ 03

M_00003E_05_- 02

M_000070_06_+ 03

M_000070_06_- 02

M_000070_06_+ 04

M_000073_06_+ 05

M_000073_06_- 04

M_000076_06_+ 05

M_000076_06_- 04

M_000076_06_+ 02

M_000079_06_+ 03

M_000079_06_- 02

M_00007C_06_+ 01

M_00007C_06_- 02

E

 

 

H_PROGС _000000_000051

D_LISTС _000030_ENDС _000042

R_ 02 LISTA _ 03 ENDA _ 04 LISTB _ 05 ENDB

*

*

T_000018_0C_03100000_77100004_05100000

*

*

T_000042_0F_000030_000008_000011_000000_000000

M_000019_05_+ 02

M_00001D_05_+ 04

M_000021_05_+ 03

M_000021_05_- 02

M_000042_06_+ 03

M_000042_06_- 02

M_000042_06_+ 01

M_000048_06_+ 02

M_00004B_06_+ 03

M_00004B_06_- 02

M_00004B_06_- 05

M_00004B_06_+ 04

M_00004E_06_+ 04

M_00004E_06_- 02

E

 

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

 

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