Алгоритм работы Непосредственно Связывающего Загрузчика

Наиболее простой алгоритм работы Загрузчика — двухпроходный.

На вход Загрузчика обязательно подается список объектных модулей, из которых составляется программа. Этот список может быть параметром программы-Загрузчика или находиться в отдельном файле. На первом проходе Загрузчик просматривает все объектные модули по списку и решает 2 задачи:

u определяет общий объем области памяти, необходимый для программы и размещение объектных модулей в этой области;

u составляет Глобальную таблицу внешних имен программы.

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

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

Алгоритм выполнения 1-го прохода — следующий:

F Блок1: 1-й проход Загрузчика.

F Блок2: Начальные установки. Создание пустой Глобальной таблицы. Стартовый адрес=пусто. Относительный адрес 1-го сегмента — 0. Размер программы — 0.

F Блок3: Выборка следующего имени из списка объектных модулей. Если весь список объектных модулей обработан — переход на окончание 1-го прохода.

F Блок4: Чтение заголовка очередной записи объектного модуля, если объектный модуль обработан полностью — переход к следующему модулю.

F Блок5: Чтение остальной части записи (размер записи содержится в ее заголовке).

F Блок6: Разветвление в зависимости от типа записи.

F Блок7: При обработке записи окончания проверяется, имеется ли в записи стартовый адрес. Если стартового адреса нет — никакая другая обработка записи не производится.

F Блок8: Если в записи есть стартовый адрес, проверяется, не был ли он уже установлен.

F Блок9: Если стартовый адрес не был установлен, он устанавливается.

F Блок10: Если стартовый адрес был установлен, выдается сообщение об ошибке. (Ни эта, ни последующие рассмотренные ошибки не приводят к немедленному завершению 1-го прохода, однако, если на 1-м проходе были ошибки, 2-й проход не выполняется).

F Блок11: При обработке записи связывания выполняется перебор элементов Таблицы внешних символов...

F Блок12:...и разветвление — в зависимости от типа элемента.

F Блок13: Для элемента — сегмента вычисляется начальный адрес следующего сегмента и длина сегмента прибавляется к общему размеру программы.

F Блок14: Для элемента — входной точки ищется имя точки в Глобальной таблице.

F Блок15: Если имя не найдено в Глобальной таблице, в таблицу добавляется новый элемент.

F Блок16: Если имя найдено в Глобальной таблице, — ошибка, неуникальное внешнее имя.

F Блок17: При окончании 1-го прохода проверяется, установился ли адрес стартовой точки программы.

F Блок18: Если этот адрес не установлен — ошибка.

F Блок19: Если этот адрес установлен и в ходе выполнения 1-го прохода не было других ошибок, Загрузчик продолжает работу.

F Блок20: Выделяется память для программы в соответствии с ее размером.

F Блок21: В Глобальную таблицу внешних символов записываются фактические адреса.

F Блок22: Выполняется 2-й проход.

F Блок23: Освобождается Глобальная таблица

F Блок24: Если не было ошибок на 2-м проходе

F Блок25:...управление передается на стартовый адрес программы

F Блок26: Загрузчик завершает работу.

Алгоритм выполнения 2-го прохода — следующий:

F Блок1: 2-й проход Загрузчика

F Блок2: Установка на начало списка имен объектных модулей.

F Блок3: Выборка следующего имени из списка объектных модулей. Если весь список объектных модулей обработан — переход на окончание 2-го прохода.

F Блок4: Создание для модуля Локальной таблицы внешних символов и Таблицы перемещений — пустых.

F Блок5: Чтение заголовка очередной записи объектного модуля, если все записи модуля прочитаны — переход к обработке перемещений в модуле.

F Блок6: Чтение остальной части записи (размер записи содержится в ее заголовке).

F Блок7: Разветвление в зависимости от типа записи.

F Блок8: Для кодовой записи считывается относительный адрес записи и переводится в фактический.

F Блок9: Тело кодовой записи считывается и размещается в памяти по фактическому адресу.

F Блок10: Для записи связывания перебираются находящиеся в ней элементы Таблицы имен

F Блок11: Обработка разветвляется в зависимости от типа имени.

F Блок12: Для имен сегментов или входных точек относительный адрес переводится в фактический.

F Блок13: Имя внешней точки ищется в Глобальной таблице внешних имен.

F Блок14: Если имя не найдено в Глобальной таблице, выдается сообщение об ошибке.

F Блок15: Если имя найдено в Глобальной таблице, в значение адреса из Глобальной таблицы становится значением этого имени.

F Блок16: Элемент с откорректированным адресом заносится в Локальную таблицу имен.

F Блок17: Для записи перемещения перебираются находящиеся в ней элементы Таблицы перемещения.

F Блок18: Относительный адрес в элементе заменяется на фактический...

F Блок19:...и элемент добавляется в Таблицу перемещений.

F Блок20: После того, как весь модуль прочитан, выполняется перебор Таблицы перемещений модуля.

F Блок21: Для каждого элемента Таблицы перемещений имя, записанное в его поле имени ищется в Локальной таблице имен и из Локальной таблицы имен выбирается связанный с этим именем адрес.

F Блок22: Из кода программы выбирается код, адрес и длина которого записаны в элементе Таблицы перемещений.

F Блок23: Над выбранным кодом и адресом, выбранным из Таблицы имен выполняется операция сложения или вычитания, результат записывается на место кода.

F Блок24: После перебора всей Таблицы перемещений, освобождаются Таблица перемещений и Локальная таблица имен модуля, и управление передается на обработку следующего модуля.

F Блок25: После обработки всех объектных модулей 2-й проход заканчивается.

Лекция 17.
Кросс-системы