Файл: Tannenbaum.pdf

Связывание и загрузка 543

Здесь возникает

 проблема перераспределения памяти,

 поскольку каждый

объектный модуль на рис. 7.3 занимает отдельное адресное пространство. В маши-
не с сегментированным адресным пространством (например, в Pentium II) каж-

дый объектный модуль теоретически может иметь свое собственное адресное про-

странство, если его поместить в отдельный сегмент. Однако для Pentium II только
система OS/2 поддерживает такую структуру

1

. Все версии Windows и UNIX под-

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

Более того, команды вызова процедур (см. рис. 7.4,

 а)

 вообще не будут рабо-

тать. В ячейке с адресом 400 программист намеревается вызвать объектный мо-
дуль В, но поскольку каждая процедура транслируется отдельно, ассемблер не
может определить, какой адрес вставлять в команду CALL В. Адрес объектного мо-
дуля В не известен до времени связывания. Такая проблема называется пробле-
мой

 внешней ссылки.

 Обе проблемы решаются с помощью компоновщика.

Компоновщик сливает отдельные адресные пространства объектных модулей

в единое линейное адресное пространство. Для этого совершаются следующие шаги:

1. Компоновщик строит таблицу объектных модулей и их длин.

2. На основе этой таблицы он приписывает начальные адреса каждому объект-

ному модулю.

3. Компоновщик находит все команды, которые обращаются к памяти, и при-

бавляет к каждой из них

 константу перемещения,

 которая равна начально-

му адресу этого модуля.

4. Компоновщик находит все команды, которые обращаются к процедурам,

и вставляет в них адрес этих процедур.

Ниже показана таблица объектных модулей рис. 7.4, построенная на первом

шаге. В ней дается имя, длина и начальный адрес каждого модуля.

Модуль Длина Начальный адрес

А

В
С
D

400
600

500
300

100

500

1100
1600

На рисунке 7.4, б показано, как адресное пространство выглядит после выпол-

нения компоновщиком всех шагов.

Структура объектного модуля

Объектные модули обычно состоят из шести частей (рис. 7.5). В первой части

содержится имя модуля, некоторая информация, необходимая компоновщику

(например, длины различных частей модуля), а иногда дата ассемблирования.

Необходимо отметить, что сегментный способ организации был использован только в первой версии
OS/2, которая была 16-битовой и разрабатывалась для 286-го микропроцессора. Поэтому относить эту
систему к Pentium II представляется не вполне правильно. Начиная с 1993 года все последующие версии
OS/2 были 32-битовыми и, как и остальные современные операционные системы, перестали поддер-
живать сегментирование, а стали использовать только страничный механизм. —

 Примеч. научн.ред.

5 4 4 Глава 7. Уровень языка ассемблера

Конец модуля

Словарь перемещений

Машинные команды и константы

Таблица внешних ссылок

Таблица точек входа

Идентификация

Рис. 7.5. Внутренняя структура объектного модуля

Вторая часть объектного модуля — это список символов, определенных в моду-

ле, вместе с их значениями. К этим символам могут обращаться другие модули.
Например, если модуль состоит из процедуры

 bigbug,

 то элемент таблицы будет

содержать цепочку символов «bigbug», за которой будет следовать соответствую-
щий адрес. Программист на языке ассемблера с помощью директивы PUBLIC указы-
вает, какие символьные имена считаются

 точками входа.

Третья часть объектного модуля состоит из списка символьных имен, которые

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

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

 внешними.

 В некоторых компьютерах точки входа и внешние ссылки объеди-

нены в одной таблице.

Третья часть объектного модуля — это машинные команды и константы. Это

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

Пятая часть объектного модуля — это словарь перемещений. К командам, ко-

торые содержат адреса памяти, должна прибавляться константа перемещения
(см. рис. 7.4). Компоновщик сам не может определить, какие слова в четвертой
части содержат машинные команды, а какие — константы. Поэтому в этой таблице
содержится информация о том, какие адреса нужно переместить. Это может быть
битовая таблица, где на каждый бит приходится потенциально перемещаемый
адрес, либо явный список адресов, которые нужно переместить.

Шестая часть содержит указание на конец модуля, а иногда — контрольную

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

Большинству компоновщиков требуется два прохода. На первом проходе

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

Связывание и загрузка 545

Время принятия решения и динамическое

перераспределение памяти

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

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

На рис. 7.6 показано, что произойдет, если уже перемещенная программа (см.

рис. 7.4,

 б)

 будет загружена в адрес 400, а не в адрес 100, куда ее изначально по-

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

Проблема перемещения программ, уже связанных и размещенных в памяти,

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

временем принятия решения.

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

времени принятия решения относительно привязок:

1. Когда пишется программа.

2. Когда программа транслируется.
3. Когда программа компонуется, но еще до загрузки.
4. Когда программа загружается.
5. Когда загружается базовый регистр, который используется для адресации.
6. Когда выполняется команда, содержащая адрес.
Если команда, содержащая адрес памяти, перемещается после связывания, этот

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

Здесь возникают два вопроса. Первый — когда символические имена связыва-

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

виртуальными адресами. Это наблюдение верно независимо от того, используется
виртуальная память или нет.

5 4 6 Глава 7. Уровень языка ассемблера

2200

2100

2000

1900

1800

1700

1600

1500

1400

1300

1200

1100

1000

900

800

700

600

500

400

MOVE S ТО X

BRANCH TO 1800

CALL 1800

MOVE R TO X

BRANCH TO 1300

CALL 1100

MOVE Q TO X

BRANCH TO 800

CALL 500

MOVE P TO X

BRANCH

 TO 300

Объектный

модуль D

Объектный

модуль С

Объектный

модуль В

Объектный

модуль А

Рис.

 7.6. Двоичная программа с рис. 7.4, б, передвинутая вверх на 300 адресов.

Многие команды теперь обращаются к неправильным адресам памяти

Предположим, что адресное пространство, изображенное на рис. 7.4,

 б,

 было

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

Связывание и загрузка 547

Любой механизм, который позволяет легко изменять отображение виртуаль-

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

таблицу страниц, но не саму программу.

Второй механизм — использование регистра перемещения. Компьютер CDC 6600

и его последователи содержали такой регистр. В машинах, в которых использует-
ся эта технология перемещения, регистр всегда указывает на физический адрес
начала текущей программы. Аппаратное обеспечение прибавляет регистр переме-
щения ко всем адресам памяти, прежде чем отправить их в память. Весь процесс
перемещения является «прозрачным» для каждой пользовательской программы.

Пользовательские программы даже не подозревают, что этот процесс происходит.
Если программа перемещается, операционная система должна обновить регистр
перемещения. Такой механизм менее обычен, чем разбиение на страницы, посколь-
ку перемещаться должна вся программа целиком (однако если есть отдельные ре-
гистры для перемещения кода и перемещения данных, как, например, в процессо-
ре Intel 8088, то в этом случае программу нужно перемещать как два компонента).

Третий механизм можно использовать в машинах, которые могут обращаться

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

 позиционно-независимой программой.

 Позиционно-независи-

мую процедуру можно поместить в любом месте виртуального адресного простран-
ства без настройки адресов.

Динамическое связывание

Стратегия связывания, которую мы обсуждали в разделе «Задачи компоновщи-
ка», имеет одну особенность: связь со всеми процедурами, нужными программе,
устанавливается до начала работы программы. Однако если мы будем устанавли-
вать все связи до начала работы программы в компьютере с виртуальной памятью,
то мы не используем всех возможностей виртуальной памяти. Многие программы
содержат процедуры, которые вызываются только при определенных обстоятель-
ствах. Например, компиляторы содержат процедуры для компиляции редко ис-
пользуемых операторов, а также процедуры для исправления ошибок, которые
встречаются редко.

Более гибкий способ связывания отдельно скомпилированных процедур — уста-

новление связи с каждой процедурой в тот момент, когда она впервые вызывается.
Этот процесс называется

 динамическим связыванием.

 Впервые он был применен

в системе MULTICS. В следующих разделах мы рассмотрим применение динами-
ческого связывания в нескольких системах.

Динамическое связывание в системе MULTICS

В системе MULTICS с каждой программой соотносится сегмент, так называемый

сегмент связи,

 содержащий один блок информации для каждой процедуры, кото-