Связывающий загрузчик
Связывающий загрузчик предназначен для создания программ из нескольких объектных модулей и загрузки ее в оперативную память.
Связывающий загрузчик разбивается на два модуля:
- Редактор связей.
- Перемещающий загрузчик.
Связывающий загрузчик может быть одной программой или двумя отдельными программами, т.е. редактор связей и перемещающий загрузчик.
Поскольку функции и принципы перемещающего загрузчика рассмотрены ранее, то при рассмотрении связывающего загрузчика основное внимание уделено редактору связей.
Основная задача редактора связей, это:
- Распределение памяти для модулей программы.
- Определение значений внешних переменных.
- Модификация кода программы в местах, где использованы внешние ссылки или перемещаемое выражение.
Если редактор связей является самостоятельной программой, то он формирует загрузочный модуль, в большинстве случаев это перемещаемый модуль, но может быть и абсолютным модулем.
Если редактор связей является модулем связей загрузчика. то редактор связей выполняет загрузку модуля, его модификацию и передачу управления.
Основная проблема связывающего загрузчика – формирование внешних ссылок, т.е. подставление вместо ссылок реальных значений соответствующих внешних переменных. Поскольку в программе могут быть перекрестные ссылки между модулями, то решить задачу за один просмотр невозможно.
В связи с тем, что при создании программы из нескольких модулей возможна ситуация, когда внешняя ссылка встречается раньше внешней переменной, для решения задачи необходимо два просмотра.
Задача первого просмотра:
- Определение длины модуля.
- Определение внешних переменных и их значений в модулях.
- Определение внешних ссылок модуля.
- Распределение памяти для модулей и расчет значений внешних переменных в программе.
Задачи второго просмотра:
- Загрузка кода программы в оперативную память.
- Модификация кода программы в соответствии со значениями внешних переменных.
- Передача управления загруженной программе.
Структура данных, используемых связывающим загрузчиком
1. Таблица распределения памяти. Содержит поля: ключ → имя модуля, длина модуля, адрес в оперативной памяти.
2. Список внешних имен (таблица). Содержит поля: имя внешней переменной, имя модуля, значение внешней переменной, перемещаемость, тип внешних переменных, ключ внешних переменных.
3. Список внешних ссылок (таблица). Содержит поля: имя внешней переменной, имя модуля.
Алгоритм первого просмотра
Задачей первого просмотра является формирование таблицы распределения памяти, таблицы внешних переменных и списка внешних ссылок. Для их формирования используются карты объектного модуля:
- для таблицы распределения памяти (Н);
- для таблицы внешних переменных (D);
- для списка внешних ссылок.
Алгоритм:
- Выделение памяти для двух таблиц и списка.
- Открытие очередного файла с объектным модулем. Если нет, то к п.10.
- Чтение очередной карты модуля.
- Если карта Н, то определение имени модуля и его длины и запись их в таблицу распределения памяти (ТРП), переход к п.3.
- Если карта D, то определение имени внешней переменной, ее значения и перемещаемость, запись новой строки в таблицу внешних переменных (ТВП), переход к п.3.
- Если карта R, то определение имени внешней ссылки, запись новой строки в список внешних ссылок (СВС), переход к п.3.
- Если карта Е, то закрыть файл объектного модуля и перейти к п.2.
- Пропустить карты Т, М, переход к п.3.
- Проверка на разрешимость внешних ссылок. Для всех имен внешних ссылок нужно найти соответствующие внешние переменные. Если имеются ссылки без переменных, то программа содержит ошибки, формирование сообщения, завершение работы загрузчика.
- Конец.
Алгоритм второго просмотра
Необходимо определить адреса модуля и значения внешних переменных и выполнить загрузку и модификацию программы в оперативной памяти.
При втором просмотре обрабатываются карты Н, Т, М и Е для главного модуля.
- Расчет длины программы. Это сумма длин всех модулей.
- Заказ в операционной системе блока памяти, равного длине программы. Если блок выделен, то адрес программы равен адресу выделенного блока, иначе сообщение об ошибке и завершение работы программы.
- Расчет адресов модулей в оперативной памяти. Первый модуль равен адресу программы, последний – адресу предыдущего модуля + его длина.
- Расчет значений внешних переменных. Для всех перемещаемых внешних переменных их значение увеличивается на адрес загрузки их модуля.
- Открытие очередного файла с оперативным модулем, переход к п.2.
- Чтение очередной карты.
- Если карта Н, то определение имени модуля и выборка адреса модуля по ТРП, переход к п.6.
- Если карта Т, то определение адреса и длины данных, загрузка данных из карты по адресу: адрес данных + адрес модуля. Переход к п.6.
- Если карта М, то определение адреса и длины модифицированных данных, выделение из карты фрагмента формулы модификации (???). Определяется значение внешней ссылки по таблице внешних переменных и прибавляется ими вычитается соответствующее значение по адресу: адрес данных + адрес модуля с учетом длины модифицируемых данных. Переход к п.6.
- Если карта Е или модуль является главным, то сформировать адрес первой выполняемой команды, который равен: точка входа + адрес модуля. Закрываем файл объектного модуля, переход к п.5.
- Если карты D, R, то пропустить их и переход к п.6.
- Конец.
Имя главного модуля является заранее определенным (например, в Си ‘main’, в Паскале - ‘program’ и т.д.) или главным модулем является первый модуль в списке объектных модулей (например, Ассемблер).