ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 24.12.2021
Просмотров: 12219
Скачиваний: 10
5 3 8 Глава 7. Уровень языка ассемблера
При применении любого из этих способов мы пытаемся смоделировать
ассоциа-
тивную память,
которая представляет собой набор пар (символьное имя, значе-
ние). По имени ассоциативная память должна выдавать его значение.
Проще всего реализовать таблицу символьных имен в виде массива пар, где пер-
вый элемент является именем (или указателем на имя), а второй — значением (или
указателем на него). Если нужно найти какой-нибудь символ, то таблица символь-
ных имен просто последовательно просматривается, пока не будет найдено соответ-
ствие. Такой метод довольно легко запрограммировать, но он медленно работает, по-
скольку в среднем при каждом поиске придется просматривать половину таблицы.
Другой способ организации — отсортировать таблицу по именам и для поиска
имен использовать алгоритм
двоичного поиска.
В соответствии с этим алгорит-
мом средний элемент таблицы сравнивается с символьным именем. Если нужное
имя по алфавиту идет раньше среднего элемента, значит, оно находится в первой
половине таблицы. Если символьное имя по алфавиту идет после среднего эле-
мента, значит, оно находится во второй части таблицы. Если нужное имя совпада-
ет со средним элементом, то поиск на этом завершается.
Предположим, что средний элемент таблицы не равен символу, который мы
ищем. Мы уже знаем, в какой половине таблицы он находится. Алгоритм двоичного
поиска можно применить к соответствующей половине. В результате мы либо полу-
чим совпадение, либо определим нужную четверть таблицы. Таким образом, в таб-
лице из п элементов нужный символ можно найти примерно за lo&n попыток. Оче-
видно, что такой алгоритм работает быстрее, чем просто последовательный просмотр
таблицы, но при этом элементы таблицы нужно сохранять в алфавитном порядке.
Совершенно другой подход —
хэш-кодирование.
Для этого подхода требуется
хэш-функция, которая отображает символы (имена) в целые числа в промежутке
от 0 до к-1. Такой функцией может быть функция перемножения кодов ASCII
всех символов в имени. Можно перемножить все коды ASCII символов с игнори-
рованием переполнения, а затем взять значение по модулю
к
или разделить полу-
ченное значение на простое число. Фактически подойдет любая входная функция,
которая дает равномерное распределение значений.
Символьные имена можно хранить в таблице, состоящей из
к
участков, от 0 до
к-1. Все пары (символьное имя, значение), в которых имя соответствует i, сохра-
няются в связном списке, на который указывает слот i в хэш-таблице. Если в хэш-
таблице содержится п символьных имен и к слотов, то в среднем длина списка
будет n/k. Если мы выберем к, приблизительно равное п, то на нахождение нужно-
го символьного имени в среднем потребуется всего один поиск. Путем корректи-
ровки
к
мы можем сократить размер таблицы, но при этом скорость поиска сни-
зится. Хэш-код показан на рис. 7.1.
Связывание и загрузка
Большинство программ содержат более одной процедуры. Компиляторы и ассем-
блеры транслируют одну процедуру и помещают полученный на выходе результат
на диск. Перед запуском программы должны быть найдены и связаны все оттран-
Связывание и загрузка
539
слированные процедуры. Если виртуальной памяти нет, связанная программа долж-
на загружаться в основную память. Программы, которые выполняют эти функ-
ции, называются по-разному:
компоновщиками, связывающими загрузчиками
и
редакторами связей.
Для полной трансляции исходной программы требуется
два шага, как показано на рис. 7.2:
1. Компиляция или ассемблирование исходных процедур.
2. Связывание объектных модулей.
Andy
Anton
Cathy
Dick
Erik
Frances
Frank
Gerrit
Hans
Henri
Jan
Jaco
Maarten
Reind
Roel
Willem
Wiebern
14025
31253
65254
54185
47357
56445
14332
32334
44546
75544
17097
64533
23267
63453
76764
34544
34344
0
4
5
0
6
3
3
4
4
2
5
6
0
1
7
6
1
Хэш-
таблица
0
1
2
3
4
5
6
7
Связная таблица
Andy | 14025 | -Ы Maarten | 23267 | 4+-| Dick | 54185~
Reind | 63453
Henri
Hans
Jan
Jaco
Roel
75544
44546
17097
64533
76764
Wiebern | 34344
Frances | 56445 |
Ц->\
Frank | 14332
Gerrit
Willem
32334
* ^ H Cathy | 65254
34544
Anton
31253
Erjk
"r7357
Рис. 7 . 1 . Хэш-кодирование: символьные имена, значения и хэш-коды, образованные
от символьных имен (а); хэш-таблица из 8 элементов со связным списком символьных
имен и значений
(б)
Первый шаг выполняется ассемблером или компилятором, а второй — компо-
новщиком.
5 4 0 Глава 7. Уровень языка ассемблера
Трансляция исходной процедуры в объектном модуле — это переход на другой
уровень, поскольку исходный язык и выходной язык имеют разные команды и за-
пись. Однако при связывании перехода на другой уровень не происходит, поскольку
программы на входе и на выходе компоновщика предназначены для одной и той
же виртуальной машины. Задача компоновщика — собрать все процедуры, кото-
рые транслировались раздельно, и связать их вместе, чтобы в результате получился
исполняемый двоичный код.
В системах MS-DOS, Windows 95/98 и NT объект-
ные модули имеют расширение .obj, а исполняемые двоичные программы — рас-
ширение .ехе. В системе UNIX объектные модули имеют расширение .о, а испол-
няемые двоичные программы не имеют расширения.
Исходная
процедура 1
Исходная
процедура 2
Исходная
процедура 3
Транслятор
Объектный
модуль 1
Объектный
модуль 2
Объектный
модуль 3
Компоновщик
Исполняемый
двоичный
код
Рис. 7.2. Для получения исполняемой двоичной программы из совокупности
оттранслированных независимо друг от друга процедур используется компоновщик
Компиляторы и ассемблеры транслируют каждую исходную процедуру как от-
дельную единицу. На это есть веская причина. Если компилятор или ассемблер
считывал бы целый ряд исходных процедур и сразу переводил бы их в готовую
программу на машинном языке, то при изменении одного оператора в исходной
процедуре потребовалось бы заново транслировать все исходные процедуры.
Если каждая процедура транслируется по отдельности, как показано на рис. 7.2,
то транслировать заново нужно будет только одну измененную процедуру, хотя
понадобится заново связать все объектные модули. Однако связывание происхо-
дит гораздо быстрее, чем трансляция, поэтому выполнение этих двух шагов (транс-
ляции и связывания) сэкономит время при доработке программы. Это особенно
важно для программ, которые содержат сотни или тысячи модулей.
Задачи компоновщика
В начале первого прохода ассемблирования счетчик адреса команды устанавлива-
ется на 0. Этот шаг эквивалентен предположению, что объектный модуль во время
выполнения будет находиться в ячейке с адресом 0. На рис. 7.3 показаны 4 объек-
тных модуля для типичной машины. В этом примере каждый модуль начинается
с команды перехода BRANCH к команде
MOVE
в том же модуле.
Чтобы запустить программу, компоновщик помещает объектные модули в ос-
новную память, формируя отображение исполняемого двоичного кода (рис. 7.4,
а).
Цель — создать точное отображение виртуального адресного пространства ис-
Связывание и загрузка
541
полняемой программы внутри компоновщика и разместить все объектные модули
в соответствующих адресах. Если физической или виртуальной памяти не доста-
точно для формирования отображения, то можно использовать файл на диске.
Обычно небольшой раздел памяти, начинающийся с нулевого адреса, использует-
ся для векторов прерывания, взаимодействия с операционной системой, обнару-
жения неинициализированных указателей и других целей, поэтому программы
обычно начинаются не с нулевого адреса, а выше. В нашем примере программы
начинаются с адреса 100.
Объектный модуль В
Объектный модуль А
400
300
200
100
0
CALL В
MOVE P ТО X
BRANCH TO 200
еии
500
400
300
200
100
0
CALL С
MOVE Q ТО X
BRANCH TO 300
500
400
300
200
100
Объектный модуль С
CALLD
MOVE R ТО X
BRANCH TO 200
300
200
100
Объектный модуль D
MOVE S ТО X
BRANCH TO 200
Рис. 7.3. Каждый модуль имеет свое собственное адресное
пространство, начинающееся с нуля
Посмотрите на рис. 7.4,
а.
Хотя программа уже загружена в отображение ис-
полняемого двоичного файла, она еще не готова для выполнения. Посмотрим, что
произойдет, если выполнение программы начнется с команды в начале модуля А.
Программа не совершит перехода к команде MOVE, поскольку эта команда находит-
ся в ячейке с адресом 300. Фактически все команды обращения к памяти не будут
выполнены по той же причине.
5 4 2 Глава 7. Уровень языка ассемблера
1900
1800
1700
1600
1500
1400
1300
1200
1100
1000
900
800
700
600
500
400
300
200
100
п
MOVE S ТО X
BRANCH TO 200
CALLD
MOVE R ТО X
BRANCH TO 200
CALL С
MOVE Q ТО X
BRANCH TO 300
CALL В
MOVE P ТО X
BRANCH TO 200
Объектный
У
модуль D
Объектный
i Объектный
/ модуль В
Объектный
модуль А
1900
1800
1700
1600
1500
1400
модуль С
1 3 0 0
1200
1100
1000
900
800
700
600
500
400
300
200
100
0
MOVE S ТО X
BRANCH ТО 1800
CALL 1600
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
V Объектный
/ модуль С
v Объектный
}
модуль В
Объектный
модуль А
Рис. 7.4. Объектные модули после размещения в двоичном отображении,
но до перераспределения памяти и связывания (а); те же объектные модули
после связывания и перераспределения памяти (б). В результате получается
исполняемая двоичная программа, которую можно запускать