Наиболее простой алгоритм работы Загрузчика — двухпроходный.
На вход Загрузчика обязательно подается список объектных модулей, из которых составляется программа. Этот список может быть параметром программы-Загрузчика или находиться в отдельном файле. На первом проходе Загрузчик просматривает все объектные модули по списку и решает 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-й проход заканчивается.
