Э. Таненбаум - Архитектура компьютера (1127755), страница 147
Текст из файла (страница 147)
Программисты весьма изобретательны по части новых ошибок. Ошибки с неопределенным символом часто являются следствием опечаток. Хороший ассемблер может просчитать, какой из всех определенных символов в большей степени 578 Глава 7. Уровень ассемблера соответствует неопределенному, и подставить его вместо неопределенного символа. Для исправления других ошибок ничего кардинального предложить нельзя. Лучшее, что может сделать ассемблер при обнаружении оператора с ошибкой, — вывести сообщение об ошибке на экран и попробовать продолжить ассемблирование. Таблица символов Во время первого прохода ассемблер аккумулирует всю информацию о символах и их значениях.
Эту информацию он должен сохранить в таблице символических имен, к которой будет обращаться при втором проходе. Таблицу символических имен можно организовать несколькими способами. Некоторые из них мы опишем. При применении любого из этих способов мы пытаемся смоделировать ассоциативную память, которая представляет собой набор пар (символическое имя, значение). По имени ассоциативная память должна выдавать его значение. Проще всего реализовать таблицу символических имен в виде массива пар, где первый элемент является именем (или указателем на имя), а второй — значением (или указателем на него). Если нужно найти какой-нибудь символ, то таблица символических имен просто последовательно просматривается, пока не будет найдено соответствие.
Такой метод довольно легко запрограммировать, но он медленно работает, поскольку при каждом поиске в среднем придется просматривать половину таблицы. Другой способ организации — отсортировать таблицу по именам, и для поиска имен использовать алгоритм бинарного поиска. В соответствии с этим алгоритмом средний элемент таблицы сравнивается с символическим именем. Если нужное имя по алфавиту идет раньше среднего элемента, значит, оно находится в первой половине таблицы. Если символическое имя по алфавиту идет после среднего элемента, значит, оно находится во второй части таблицы. Если нужное имя совпадает со средним элементом, то поиск на этом завершается. Предположим, что средний элемент таблицы не равен искомому символу. Мы уже знаем, в какой половине таблицы он находится. Алгоритм двоичного поиска можно применить к соответствующей половине. В результате мы либо получим совпадение, либо определим нужную четверть таблицы.
Таким образом, в таблице из и элементов нужный символ можно найти примерно за 1оя2п попыток. Очевидно, что такой алгоритм работает быстрее, чем просто последовательный просмотр таблицы, но при этом элементы таблицы нужно сохранять в алфавитном порядке. Совершенно другой подход — хэширование. В этом случае используется хэш-функция, которая отображает символы (имена) на целые числа в промежутке от 0 до 1 — 1. Такой функцией может быть функция перемножения АВСП-кодов всех символов в имени. Можно перемножить все АБСП-коды символов с игнорированием переполнения, а затем взять значение по моду- Процесс ассемблирования 579 лю )г или разделить полученное значение на простое число.
Фактически подойдет любая входная функция, которая дает равномерное распределение значений. Символические имена можно хранить в таблице, состоящей из гг сегментов, от О до гг — 1. Все пары (символическое имя, значение), в которых имя соответствует г', сохраняются в связном списке, на который указывает слот г в хзш-таблице. Если в хзш-таблице содержится и символических имен и гт слогов, то в среднем длина списка будет и/)г.
Если мы выберем гг, приблизительно равное л, то на нахождение нужного символического имени в среднем потребуется всего один поиск. Путем корректировки гг мы можем сократить размер таблицы, но при этом скорость поиска снизится. Процесс хзширования иллюстрирует рис. 7.1. Хзштаблица Связная таблица Маалеп 23267 ряск 54185 ЧЧ!еоегп 34344 Егапх 14332 6егп( 32334 Ап(оп 31253 Са(лу 65254 ЧЧ(()егп 34544 Ег(Х 47357 Рис. 7.1. Хэширование: символические имена, значения и хзш-коды, образованные от символических имен (а); хзш-таблица из 8 элементов со связным списком символических имен и значений (б) 680 Глава 7.
Уровень ассемблера Компоновка и загрузка Большинство программ содержат более одной процедуры. Компиляторы и ассемблеры транслируют одну процедуру и записывают полученный результат на диск. Перед запуском программы должны быть найдены и скомпонованы все оттранслированные процедуры.
Если виртуальная память недоступна, скомпонованная программа должна загружаться непосредственно в основную память. Программы, которые выполняют эти функции, называются по-разному: компоновщиками, компонующими загрузчиками, редакторами связей. Для полной трансляции исходной программы требуется два шага (рис. 7.2): 1. Компиляция или ассемблирование исходных процедур. 2.
Компоновка объектных модулей. Первый шаг выполняется ассемблером или компилятором, второй — компоновщиком. Рис. 7.2. для получения исполняемой двоичной программы иэ совокупности оттранслированных независимо друг от друга процедур используется компоновщик Трансляция исходной процедуры в объектный модуль — это переход на другой уровень, поскольку исходный и выходной языки имеют разные команды и синтаксис. Однако при компоновке перехода на другой уровень не происходит, поскольку программы на входе и выходе компоновщика предназначены для одной и той же виртуальной машины. Цель компоновщика — скомпоновать вместе все процедуры, которые транслировались отдельно, чтобы в результате получился исполняемьтй двоичный код. В системах МБ-РОВ, 'уу'1пг1отуз 95/98 и Ж1пг1отуз 1х1Т объектные модули имеют расширение .оЬ1, а исполняемые программы — .ехе.
В Пй11Х объектные модули имеют расширение .о, а исполняемые программы расширения не имеют. Компиляторы и ассемблеры транслируют каждую исходную процедуру как отдельную единицу. На это есть веская причина. Если компилятор или ассемблер считывал бы целый ряд исходных процедур и сразу переводил бы их в готовую программу на машинном языке, то при изменении одного оператора в исходной процедуре потребовалось бы заново транслировать все исходные процедуры. Компоновка и загрузка 581 Если каждая процедура транслируется отдельно, как показано на рис. 7.2, то транслировать заново придется только одну измененную процедуру, хотя понадобится заново скомпоновать все объектные модули.
Однако компоновка происходит гораздо быстрее, чем трансляция, поэтому при доработке программы оба шага (трансляция и компоновка) выполняются быстро. Это особенно важно для программ, содержащих сотни нли тысячи модулей. Задачи компоновщика В начале первого прохода ассемблирования счетчик адресов команд устанавливается на О. Этот шаг эквивалентен предположению, что объектный модуль во время выполнения будет находиться в ячейке с адресом О.
На рис. 7.3 показаны 4 объектных модуля, подготовленных для типичной машины. В этом примере каждый модуль начинается с команды перехода ВВАМСН к команде МОЧЕ в том же модуле. Объектный модуль В Объектный модуль А 600 400 300 500 400 200 100 300 200 100 Объектный модуль С 500 400 Объектный модуль О 300 300 200 200 100 100 Рис. 7.3. Каждый модуль имеет собственное адресное пространство, начинающееся с нулевого адреса Чтобы можно было запускать программу, компоновщик помещает объектные модули в основную память, формируя образ исполняемого двоичного кода (рис. 7.4, а). Цель — создать точный образ виртуального адресного пространства 582 Глава 7. Уровень ассемблера исполняемой программы внутри компоновщика и разместить все объектные модули по соответствующим адресам.
Если физической или виртуальной памяти для формирования образа недостаточно, можно использовать дисковый файл. Обычно небольшой раздел памяти, начинающийся с нулевого адреса, используется для векторов прерываний, взаимодействия с операционной системой, обнаружения неинициализированных указателей и других целей, поэтому, как правило, программы начинаются не с нулевого адреса, а выше. В нашем примере программы начинаются с адреса 100.
Посмотрите на рис. 7.4, а. Хотя программа уже загружена в образ исполняемого двоичного файла, она еще не готова для выполнения. Посмотрим, что произойдет, если выполнение программы начнется с команды в начале модуля А. Программа не совершит перехода к команде МОЧЕ, поскольку эта команда находится в ячейке с адресом 300. Фактически все команды обращения к памяти по той же причине выполнены не будут. Здесь возникает проблема перераспределения памяти, поскольку каждый обьектный модуль на рис.
7.3 занимает собственное адресное пространство. В машине с сегментированным адресным пространством (например, в Реп11шп 4) каждый объектный модуль теоретически может иметь собственное адресное пространство, если его поместить в отдельный сегмент. Однако для Реп11шп 4 только система 05/2 поддерживает такую структуру'. Все версии тчг)пдотчз и ПХ1Х поддерживают одно линейное адресное пространство, поэтому все объектные модули должны быть объединены в одном адресном пространстве. Более того, команды вызова процедур на рис. 7.4, а вообще не будут работать.
В ячейке с адресом 400 программист намеревается вызвать объектный модуль В, но поскольку каждая процедура транслируется отдельно, ассемблер не может определить, какой адрес вставлять в команду САЕЕ В, поскольку адрес объектного модуля В до компоновки неизвестен. Эта проблема называется проблемой внешней ссылки. Обе проблемы решаются с помощью компоновщика.
Компоновщик объединяет отдельные адресные пространства объектных модулей в единое линейное адресное пространство. Для этого совершаются следующие шаги: 1. Компоновщик строит таблицу объектных модулей и их размеров. 2. На основе этой таблицы он приписывает начальные адреса каждому объектному модулю. 3. Компоновщик находит все команды, которые обращаются к памяти, и прибавляет к каждой из них константу перераспределения, равную начальному адресу этого модуля.
' Необходимо отметить, что сегментный способ организации был использован только в первой версия 08/2, которая была 16-разрядной и разрабатывалась для микропроцессора 286. Поэтому относить эту систему к Реппшп 4 представляется не вполне правильным. Начиная с 1993 года, все последуюшие версии 08/2 были 32-разрядиыми и, как и другие современные операционные системы, не поддерживают сегментирование, а используют только страничный механизм. — Примеч. науч н.
ред. Компоновка и загрузка 583 1900 1900 18ОО 1ВОО Объектный модуль О 1700 Объектный модуль О 1700 1800 1500 1400 Обьектный модуль С 1300 Об ьектный модуль С 1300 1200 1200 1100 1100 1000 1000 900 900 Объектный модуль В 80 Объектный модуль В 800 700 70 800 500 50 400 40 Объектный модульА 30 Объектный модуль А 300 20 100 10 Рис. 7.4.
Объектные модули после размещения в двоичном образе, но до перераспределения памяти и компоновки (з); те же объектные модули после компоновки и перераспределения памяти (б). В результате получается исполняемый двоичный код, который можно запускать 884 Глава 7. Уровень ассемблера 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
