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

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

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

Вычислительные системы

Исходная вычислительная система (ВС) — та ВС, на которой программа готовится к выполнению.

Целевая ВС — та ВС, на которой программа выполняется.

Эти две ВС не обязательно совпадают. Макропроцессор, Ассемблер, Редактор Связей — программы, обрабатывающие данные. Ассемблер, например, получает на входе одни код (текст) и производит на выходе другой код (объектный модуль). При этом Ассемблер не рассматривает свой выходной код как команды именно своей ВС, это просто некоторые данные. Ничто не мешает нам сделать Ассемблер, на выходе которого будут генерироваться коды не той ВС, в которой работает Ассемблер, а некоторой другой ВС.

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

Для чего может понадобиться кросс-система?

Часто кросс-системы применяются для разработки программного обеспечения встроенных вычислительных систем. Для встроенных ВС характерен малый объем ресурсов: ограничение оперативной памяти, возможно, отсутствие внешней памяти (программы и постоянные данные размещаются в ПЗУ), отсутствие должного набора внешних устройств. Иногда ресурсов целевой ВС просто недостаточно для выполнения на ней системного программного обеспечения подготовки программ, тем более — для выполнения интерактивных систем программирования с развитым интерфейсом пользователя.

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

В простейшем случае процесс подготовки программы на кросс-системе аналогичен процессу их подготовки в однородной системе.

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

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

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

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

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

u обращение по адресу несуществующей памяти

u попытка записи в защищенную от записи память

u модификация программой команд и констант

u передача управления на данные

u выборка неинициализированных данных

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

u модель регистров

u модель оперативной памяти

u модель процессора

u модель системы прерывания

u модель системы ввода-вывода.

Модель регистров

Модель регистров включает в себя, как минимум:

u регистры общего назначения

u регистр-счетчик адреса

u регистр состояния

Регистры моделируются переменными интерпретатора.

РОН во время выполнения программы содержат обрабатываемые данные. РОН могут моделироваться как отдельными переменными, так и массивами — в зависимости от их количества и свойств.

В тех ВС, где РОН немного и некоторые из них обладают собственными индивидуальными свойствами (напр., Intel) удобно представлять каждый РОН в виде отдельной переменной.

Для тех ВС, где РОН много и/или они одинаковы во всем (напр., S/390, все RISC), их целесообразно представлять в виде массива. Характерно, что в ВС первого типа РОН обычно имеют собственные имена, а в ВС второго типа РОН идентифицируются номерами.

Счетчик адреса содержит адрес текущий выполняемой команды и представляется в виде отдельной переменной.

Регистр состояния содержит признаки результата выполнения предыдущей команды — больше, меньше, равен нулю (не все команды устанавливают эти признаки) и, возможно, признак привилегированного/непривилегированного режима. Эти признаки могут «упаковываться» в одну переменную или представляться отдельной переменной каждый.

Модель оперативной памяти

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

Интерпретатор должен «знать» конфигурацию реальной памяти в целевой ВС. Возможные варианты задания такой конфигурации:

Потребовать, чтобы любая ячейка памяти, к которой обращается программа, была описана в программе (директивой DD или BSS).

Описать конфигурацию памяти в отдельном файле, являющимся входным для Интерпретатора.

Представляется, что второй подход более универсальный, так как:

u обращение в программе по неописанному в ней адресу памяти возможно (особенно это касается программ для встроенных ВС с абсолютными программами и жестки распределением памяти);

u определение памяти в программе также является объектом проверки/отладки может содержать ошибки;

u в Ассемблере нет средств описания ОЗУ/ПЗУ.

Внешнее описание памяти считывается Интерпретатором в начале работы и превращается в таблицу фрагментов.

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

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

Среди этих признаков могут быть такие:

u a) признак 1-го байта команды (управление можно передавать только на 1-й байт команды);

u b) признак команды/данных

u c) признак инициализированных/неинициализированных данных

u d) признак изменяемых/неизменяемых данных

u e) признак останова при передаче управления

u f) признак останова при передаче записи

u g) признак останова при передаче чтении

Все названные признаки — однобитные. Признаки a, b устанавливаются Кросс-ассемблером при трансляции программы и не изменяются при выполнении. Признак с устанавливается Кросс-ассемблером, но может изменяться Интерпретатором в процессе выполнения. Признак d устанавливается Интерпретатором перед началом выполнения на основе таблицы фрагментов и, возможно, дополнительной информации, вводимой программистом (отдельно от программы) и может изменяться программистом в ходе интерактивной отладки. Признаки e-f устанавливаются перед началом выполнения на основе дополнительной информации и может изменяться программистом в ходе интерактивной отладки.

Дополнительная информация о памяти, таким образом, состоит из таблицы фрагментов, списка переменных в ОЗУ, которые не разрешается изменять, списка переменных, при обращении к которым должен происходить останов, и меток, при передаче управления на которые должен происходить останов.

Каждое обращение к памяти в программе характеризуется типом: R (чтение), W (запись) или X (передача управления). При любом типе обращения проверяется попадание в реально существующий фрагмент памяти. При обращении типа X проверяется бит a признака, управление может быть передано только на байт с установленным признаком a. При обращениях типа R и W проверяется бит b признака, обращения этого типа могут происходить только к данным При обращениях типа R проверяется бит c признака, читаться могут только инициализированные данные При обращениях типа W проверяется бит d признака, данные должны быть изменяемые, бит с признака при этом устанавливается, то есть, данные становятся инициализированными.

Модель процессора

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

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

Далее алгоритм Интерпретатора разветвляется, в общем случае число ветвей равно числу возможных кодов операции.

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

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

При реализации алгоритмов выполнения отдельных команд возможны два подхода, которые мы называем RISC и CISC-моделями, по аналогии с архитектурами процессоров (однако выбор программной RISC или CISC-модели необязательно должен совпадать с реальной архитектурой процессора).

Смысл RISC-модели состоит в том, что разветвление алгоритма выполняется сразу же после распознавания команды и выполнение каждой команды полностью реализуется кодами соответствующей ветви.

Смысл CISC-модели состоит в том, что выполнение каждой команды представляется в виде последовательности выполнения простых процедур («микрокоманд»). Список микрокоманд, составляющих выполнение каждой команды, может быть «зашит» в программу в виде последовательности вызовов или представлен в виде данных, например, в виде списка номеров процедур. В последнем случае алгоритм не требует ветвления, а сводится к циклу, в каждой итерации которого выбирается номер очередной процедуры и вызывается процедура с данным номером. В предельном случае выполнение каждой команды может быть представлено в виде исходного текста на языке макрокоманд, который интерпретируется Интерпретатором.

Пример

Пусть в языке микрокоманд имеются следующие (показаны не все) микрокоманды:

GETR n,rx

Выборка номера регистра, заданного в n-ом операнде в промежуточную переменную rx

GETA n,ax

Выборка адреса, заданного в n-ом операнде в промежуточную переменную ax

LDR dx,rx

Выборка данных из регистра, номер которого находится в промежуточной переменной rx в промежуточную переменную dx

LDM dx,ax

Выборка данных из памяти по адресу, находящемуся в промежуточной переменной ax промежуточную переменную dx

SDR rx,dx

Запись данных из промежуточной переменной dx в регистр, номер которого находится в промежуточной переменной rx

SDM dx,ax

Запись данных из промежуточной переменной dx в память по адресу, находящемуся в промежуточной переменной ax промежуточную переменную dx

ADD dx1,dx2

Сложение данных из промежуточной переменной dx1 с данными из dx2; результат — в dx1

SIG dx

Инверсия знака данных, содержащихся в промежуточной переменной dx

CC1 dx

Установка признаков «больше», «меньше», «равно» по значению, содержащемуся в промежуточной переменной dx

CC2 dx

Установка признака переполнения по значению, содержащемуся в промежуточной переменной dx

PC1

Увеличение регистра-счетчика адреса на длину команды

PC2 dx

Запись данных из промежуточной переменной dx в регистр-счетчика адреса

END

Окончание микропрограммы

Тогда реализация некоторых машинных команд может быть «замикропрограммирована» следующим образом:

LR регистр2,регистр1

Пересылка данных из регистра1 в регистр2

GETR 2, r1;

LDR d1,r1;

GETR 1,r2;

SDR r2,d1,

PC1;

END;

L регистр,память

Пересылка данных из памяти по адресу память в регистр

GETA 2,a1;

LDM d1,a1;

GETR 1,r1;

SDR r1,d1;

PC1;

END;

AR регистр2,регистр1

Сложение данных из регистра1 с данными в регистре2; результат — в регистре1

GETR 2, r1;

LDR d1,r1;

GETR 1,r2;

LDR d2, r2;

ADD d1,d2;

SDR r1;

PC1;

END;

CMP регистр,память

Сравнение данных, содержащихся в регистре с данными по адресу память

GETR 1,r1;

LDR d1,r1;

GETA 2, a1;

LDM d2,a1;

SIG d2;

ADD d1,d2;

CC1 d1;

CC2 d1;

PC1;

END;

JMP память

Переход по адресу память

GETA 2,a2;

PC2 a2;

END;

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

Время

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

Важно понимать, что время выполнения программы на Интерпретаторе ни в коей мере не соответствует времени ее выполнения на реальной ВС. Более того, временные соотношения между выполнением различных частей программы на модели также не соответствуют соотношениям выполнения частой программы на реальном оборудовании. Поэтому время также является моделируемым компонентом. Моделью времени является целая переменная большой разрядности. В этой переменной на каждом шаге выполнения содержится число машинных тактов, выполненных с начала выполнения программы. Исходное значение этой переменной — 0, после выполнения каждой команды ее значение увеличивается на время выполнения данной команды (время выполнения может быть столбцом в таблице команд).

Система прерываний

Является самым сложным для моделирования компонентом. Трудность состоит в том, что прерывания поступают асинхронно, без привязки к выполнению программы. Следовательно, прерывания должны «зарождаться» где-то вне собственно выполняемой программы.

При выполнении Интерпретатора в пошаговом режиме прерывания могут задаваться командами, вводимыми человеком-оператором. Более универсальным является прием, предполагающий создание в отдельном файле «программы поступления прерываний». Каждый «оператор» этой «программы» содержит идентификатор типа прерывания и время (модельное) поступления прерывания. Эти «операторы» должны быть упорядочены по возрастанию времен поступления. Поскольку ВС обладают свойством непрерываемости команд, условие поступления прерывания может проверяться только после окончания обработки очередной команды.

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

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

Ввод-вывод

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

Ввод-вывод может быть синхронным или асинхронным. При синхронном вводе-выводе (например, через порты) операция ввода-вывода завершается вместе с завершением команды ввода-вывода. Моделирование такого ввода-вывода сложностей не представляет. При асинхронном вводе-выводе (КПДП, каналы ввода-вывода) команда ввода-вывода только запускает операцию ввода-вывода и заканчивается. Выполнение операции ввода-вывода далее происходит параллельно с выполнением команд программы, а об окончании ввода-вывода устройство сигнализирует прерыванием. И здесь «срабатывают» трудности, присущие моделированию системы прерываний. Одно из возможных решений — при инициализации операции ввода-вывода добавлять в программу поступления прерываний новый элемент, соответствующий прерыванию, которое поступит через какой-то интервал времени после текущего момента.

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