Реклама

Наш канал:

Таненбаум Э.- Архитектура компьютера. стр.412

Совершенно другой подход — хэширование. В этом случае используется хэш-функция, которая отображает символы (имена) на целые числа в промежутке от 0 до к - 1. Такой функцией может быть функция перемножения АЗСП-кодов всех символов в имени. Можно перемножить все АЗСП-коды символов с игнорированием переполнения, а затем взять значение по моду лю к или разделить полученное значение на простое число. Фактически подойдет любая входная функция, которая дает равномерное распределение значений. Символические имена можно хранить в таблице, состоящей из к сегментов, от О до & - 1. Все пары (символическое имя, значение), в которых имя соответствует г, сохраняются в связном списке, на который указывает слот г в хэш-таблице. Если в хэш-таблице содержится п символических имен и к слотов, то в среднем длина списка будет п/к Если мы выберем к, приблизительно равное п, то на нахождение нужного символического имени в среднем потребуется всего один поиск. Путем корректировки & мы можем сократить размер таблицы, но при этом скорость поиска снизится. Процесс хэширования иллюстрирует рис. 7.1.

Рис. 7.1, Хэширование: символические имена, значения и хэш-коды, образованные от символических имен (а); хэш-таблица из 8 элементов со связным списком символических имен и значений (б)

Компоновка и загрузка

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

1. Компиляция или ассемблирование исходных процедур.

2. Компоновка объектных модулей.

Первый шаг выполняется ассемблером или компилятором, второй — компоновщиком.

Рис. 7.2. Для получения исполняемой двоичной программы из совокупности оттранслированных независимо друг от друга процедур используется компоновщик

Трансляция исходной процедуры в объектный модуль — это переход на другой уровень, поскольку исходный и выходной языки имеют разные команды и синтаксис. Однако при компоновке перехода на другой уровень не происходит, поскольку программы на входе и выходе компоновщика предназначены для одной и той же виртуальной машины. Цель компоновщика — скомпоновать вместе все процедуры, которые транслировались отдельно, чтобы в результате получился исполняемый двоичный код. В системах MS-DOS, Windows 95/98 и Windows NT объектные модули имеют расширение .obj, а исполняемые программы — .ехе. В UNIX объектные модули имеют расширение .о, а исполняемые программы расширения не имеют.

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