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

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

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

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

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

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

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

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

Задачи компоновщика

В начале первого прохода ассемблирования счетчик адресов команд устанавли­вается на 0. Этот шаг эквивалентен предположению, что объектный модуль во время выполнения будет находиться в ячейке с адресом 0. На рис. 7.3 показаны 4 объектных модуля, подготовленных для типичной машины. В этом примере каждый модуль начинается с команды перехода BRANCH к команде MOVE в том же модуле.

Чтобы можно было запускать программу, компоновщик помещает объектные модули в основную память, формируя образ исполняемого двоичного кода (рис. 7.4, а). Цель — создать точный образ виртуального адресного пространства

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

Посмотрите на рис. 7.4, а. Хотя программа уже загружена в образ исполняе­мого двоичного файла, она еще не готова для выполнения. Посмотрим, что про­изойдет, если выполнение программы начнется с команды в начале модуля А. Программа не совершит перехода к команде MOVE, поскольку эта команда нахо­дится в ячейке с адресом 300. Фактически все команды обращения к памяти по той же причине выполнены не будут.

Здесь возникает проблема перераспределения памяти, поскольку каждый объ­ектный модуль на рис. 7.3 занимает собственное адресное пространство. В маши­не с сегментированным адресным пространством (например, в Pentium 4) каж­дый объектный модуль теоретически может иметь собственное адресное про­странство, если его поместить в отдельный сегмент. Однако для Pentium 4 только система OS/2 поддерживает такую структуру⁶.

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

Более того, команды вызова процедур на рис. 7.4, а вообще не будут работать. В ячейке с адресом 400 программист намеревается вызвать объектный модуль В, но поскольку каждая процедура транслируется отдельно, ассемблер не может определить, какой адрес вставлять в команду CALL В, поскольку адрес объектного модуля В до компоновки неизвестен. Эта проблема называется проблемой внешней ссылки. Обе проблемы решаются с помощью компоновщика.

Компоновщик объединяет отдельные адресные пространства объектных мо­дулей в единое линейное адресное пространство. Для этого совершаются сле­дующие шаги:

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

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

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

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

Таблица 7.6 соответствует построенной на первом шаге таблице объектных модулей, представленных на рис. 7.4. В ней даются имя, длина и начальный ад­рес каждого модуля.

На рис. 7.4, б показано, как выглядит адресное пространство после заверше­ния работы компоновщика.

Таблица 7.6. Имя, длина и начальный адрес каждого модуля на рис. 7.4

Модуль	Длина	Начальный адрес
А	400	100
В	600	500
С	500	1100
D	300	1600

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

Объектные модули обычно состоят из шести частей:

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

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

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

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

5. Словарь перераспределения.

6. Конец модуля.

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

Вторая часть объектного модуля — это список символов, определенных в мо­дуле, вместе с их значениями. К этим символам могут обращаться другие моду­ли. Например, если модуль состоит из процедуры bigbug, то элемент таблицы бу­дет содержать символьную строку "bigbug" с соответствующим адресом. Программист, пишущий на языке ассемблера, с помощью директивы PUBLIC ука­зывает, какие символические имена считаются точками входа.

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

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

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

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

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

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

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

На рис. 7.5 показано, что произойдет, если уже распределенная в памяти про­грамма (см. рис. 7.4, б) будет загружена по адресу 400, а не по адресу 100, куда ее изначально поместил компоновщик. Все адреса памяти оказываются неправиль­ными, и это при отсутствии какой-либо информации о распределении памяти. Даже если эта информация была бы доступна, перераспределять все адреса при каждой загрузке программы было бы расточительно.

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

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

2. Когда программа транслируется.

3. Когда программа компонуется, но еще до загрузки.

4. Когда программа загружается.

5. Когда загружается базовый регистр, который используется для адресации.

6. Когда выполняется команда, содержащая требуемый адрес.

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

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

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

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

Второй механизм — применение регистра перераспределения времени испол­нения. Компьютер CDC 6600 и его последователи содержали такой регистр. В машинах, в которых используется эта технология перераспределения памяти, регистр всегда указывает на физический адрес начала текущей программы. Ап­паратно этот регистр добавляется ко всем адресам перед их распределением в па­мяти. Весь процесс перераспределения памяти является прозрачным для пользо­вательских программ. Пользовательские программы даже не подозревают, что происходит перераспределение памяти. Если программа перемещается, операци­онная система должна обновить регистр перераспределения. Такой механизм ме­нее распространен, чем разбиение на страницы, поскольку перемещаться должна вся программа целиком (если есть отдельные регистры перераспределения для кода и данных, как, например, в процессоре Intel 8088, то объектами перемеще­ния будут обе части программы).

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

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

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

Более гибкий способ компоновки раздельно скомпилированных процедур — компоновка каждой процедуры в тот момент, когда она впервые вызывается. Этот процесс называется динамической компоновкой. Впервые он был приме­нен в системе MULTICS. Давайте рассмотрим примеры динамической компо­новки в нескольких системах.

Динамическая компоновка в MULTICS

В системе MULTICS с каждой программой соотносится сегмент, так называе­мый сегмент компоновки (linkage segment). Он содержит один информацион­ный блок для каждой процедуры, которая может быть вызвана. Этот блок начи­нается со слова, зарезервированного для виртуального адреса процедуры, за ним следует имя процедуры, которое сохраняется в виде символьной строки.

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

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

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

Динамическая компоновка в Windows

Все версии Windows, в том числе Windows NT, поддерживают динамическую компоновку. При динамической компоновке используется специальный фай­ловый формат, который называется DLL (Dynamic Link Library — библиотека динамической компоновки). Библиотеки динамической компоновки могут со­держать процедуры, данные или то и другое вместе. Обычно они применяются для того, чтобы два и более процессов могли разделять процедуры и данные биб­лиотеки. Большинство DDL-файлов имеют расширение .dll, но встречаются и другие расширения, например .drv (для библиотек драйверов — driver libraries) и .fon (для библиотек шрифтов — font libraries).

Самая распространенная форма DLL — библиотека, состоящая из набора процедур, которые могут загружаться в память и к которым имеют доступ не­сколько процессов одновременно. На рисунке 7.7 показаны два процесса, кото­рые совместно используют DLL-файл, содержащий 4 процедуры, Л, В, С и D. Программа 1 использует процедуру А; программа 2 — процедуру С, хотя они вполне могли бы использовать одну и ту же процедуру.

DLL-файл строится компоновщиком из группы входных файлов. Построе­ние DDL напоминает создание исполняемого двоичного кода, только при создании DLL компоновщику передается специальный флаг, сообщающий о том, что требуется именно библиотека DLL. DLL-файлы обычно собираются из набора библиотечных процедур, которые могут понадобиться нескольким про­цессам. Типичными примерами DLL-файлов являются процедуры сопряжения с библиотекой системных вызовов Windows и большими графическими биб­лиотеками. Применяя DDL-файлы, мы экономим пространство в памяти и на диске. Если бы та или иная библиотека была связана статически с каждой ис­пользующей ее программой, эту библиотеку пришлось бы включать во все ис­полняемые двоичные программы в памяти и на диске, что не экономно. А при наличии DLL-файла на диске и в памяти будет находиться всего одна библио­тека.

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

Основное различие между DLL и исполняемой двоичной программой состо­ит в том, что DLL-файл не может запускаться и работать сам по себе (поскольку у него нет главной программы). Он также содержит совершенно другую инфор­мацию в заголовке. Кроме того, DLL-файл имеет несколько дополнительных процедур, не связанных с процедурами в библиотеке. Например, существует од­на процедура, которая вызывается автоматически всякий раз, когда новый про­цесс связывается с DLL-файлом, и еще одна процедура, которая вызывается ав­томатически всякий раз, когда связь процесса с DLL-файлом разрывается. Эти процедуры могут выделять и освобождать память или управлять другими ресур­сами, необходимыми DLL-файлу.

Программа может установить связь с DLL-файлом двумя способами: пу­тем неявной или явной компоновки. При неявной компоновке пользователь­ская программа статически компонуется со специальным файлом, так назы­ваемой библиотекой импорта. Библиотека импорта создается специальной утилитой, предназначенной для извлечения определенной информации из DLL-файла. Библиотека импорта предоставляет связующее звено, через кото­рое пользовательская программа получает доступ к DLL-файлу. Пользова­тельская программа может быть связана с несколькими библиотеками импор­та. Когда программа, в которой имеет место неявная компоновка, загружается в память для исполнения, Windows проверяет, какие DLL-файлы ей требуют­ся и все ли они находятся в памяти. Те файлы, которых еще нет в памяти, не­медленно туда загружаются (но необязательно целиком, поскольку они раз­биты на страницы). Затем производятся определенные изменения структур данных в библиотеках импорта так, чтобы можно было определить местопо­ложение вызываемых процедур (это похоже на изменения, которые иллюст­рирует рис. 7.6). Их тоже нужно отобразить на виртуальное адресное про­странство программы. С этого момента пользовательскую программу можно запускать, поскольку она может вызывать процедуры из DLL-файлов, как будто они статически с ней связаны.

Альтернативой неявной является явная компоновка. Явная компоновка не требует ни библиотек импорта, ни одновременной загрузки DLL-файлов с пользовательской программой. Вместо этого пользовательская программа де­лает явный вызов прямо во время работы, чтобы установить связь с DLL-фай- лом, а затем совершает дополнительные вызовы, чтобы получить адреса про­цедур, которые ей требуются. Когда все это сделано, программа совершает финальный вызов, чтобы разорвать связь с DLL-файлом. Когда последний процесс разрывает связь с DLL-файлом, этот файл может быть выгружен из памяти.

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

Динамическая компоновка в UNIX

В UNIX используются библиотеки коллективного доступа, по сути напоминаю­щие библиотеки DLL Windows. Как и DLL-файл, библиотека коллективного доступа представляет собой архивный файл, содержащий несколько процедур или модулей данных, которые присутствуют в памяти во время работы програм­мы и одновременно могут быть связаны с несколькими процессами. Стандарт­ная библиотека С и большинство сетевых программ являются библиотеками коллективного доступа.

UNIX поддерживает только неявную компоновку, поэтому библиотека кол­лективного доступа состоит из двух частей: главной библиотеки (host library), которая статически скомпонована с исполняемым файлом, и целевой библиоте­ки (target library), которая вызывается во время работы программы. Несмотря на некоторые различия в деталях, по существу эта концепция соответствует кон­цепции DLL.

Краткое содержание главы

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

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

Во многих ассемблерах предусмотрены макросы, которые позволяют про­граммистам давать символические имена целым последовательностям команд. Обычно эти макросы могут быть параметризированы. Макросы реализуются с помощью алгоритма обработки строковых литералов.

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

Программы, которые ассемблируются независимо друг от друга, можно скомпоновать вместе и получить исполняемую двоичную программу. Эту ра­боту выполняет компоновщик. Его цель — это перераспределение в памяти и связывание имен. Динамическая компоновка — это технология, при которой определенные процедуры не компонуются до тех пор, пока они не вызваны. Библиотеки коллективного доступа в UNIX и библиотеки динамической ком­поновки (DLL) в Windows используют технологию динамической компо­новки.

Вопросы и задания

1. Всего 2 % кода программы отвечают за 50 % времени выполнения этой про­граммы. Сравните следующие три стратегии с точки зрения времени про­граммирования и выполнения. Предположим, что для написания программы

на языке С требуется 100 человеко-месяцев, а программу на ассемблере пи­сать в 10 раз труднее, но зато она работает в 4 раза эффективнее.

1. Вся программа написана на С.

2. Вся программа написана на ассемблере.

3. Программа сначала написана на С, а затем нужные 2 % программы пере­писаны на ассемблере.

2. Для двухпроходных ассемблеров существуют определенные соглашения. Могли бы они подойти и для следующих компиляторов:

1. Компилятор вместо ассемблерного кода генерирует объектные модули?

2. Компилятор генерирует символический язык ассемблера?

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

4. Можно ли следующую программу ассемблировать в два прохода? EQU — это директива, которая приравнивает метку к выражению в поле операнда.

A EQU В В EQU С С EQU D D EQU 4

5. Некая компания планирует разработать ассемблер для компьютера с 40-раз- рядным словом. Чтобы снизить стоимость, менеджер проекта решил огра­ничить длину символических имен, чтобы каждое имя можно было хранить в одном слове. Менеджер объявил, что символические имена могут состоять только из букв, причем буква Q запрещена. Какова максимальная длина сим­волического имени? Опишите вашу схему кодирования.

6. Чем отличается команда от директивы?

7. Чем отличается счетчик адресов команд от счетчика команд? А существует ли вообще между ними различие? Ведь тот и другой выполняют трассировку следующей команды в программе.

8. Какой будет таблица символов (имен) после обработки следующих операто­ров ассемблера Pentium 4 (первому оператору приписан адрес 1000)?

EVEREST:	POP BX	(1 байт)
К2:	PUSH BP	(1 байт)
WHITNEY:	MOV BP.SP	(2 байта)
MCKINLEY:	PUSH X	(3 байта)
FUJI:	PUSH SI	(1 байт)
KIBO:	SUB SI,300	(3 байта)

9. Можете ли вы представить себе обстоятельства, при которых метка совпадет с кодом операции (например, может ли команда MOV использоваться в качест­ве метки)? Аргументируйте.

10. Какие шаги нужно совершить, чтобы путем двоичного поиска найти эле­мент «Berkeley» в следующем списке: Ann Arbor, Berkeley, Cambridge, Eugene, Madison, New Haven, Palo Alto, Pasadena, Santa Cruz, Stony Brook, Westwood, Yellow Springs. Когда будете вычислять средний элемент в спи­ске из четного числа элементов, возьмите элемент, который идет сразу по­сле среднего.

И. Можно ли использовать двоичный поиск в таблице, в которой содержится простое число элементов?

12. Вычислите хэш-код для каждого из следующих символических имен. Для этого сложите буквы (а = 1, Ъ = 2 и т. д.) и возьмите результат по модулю раз­мера хэш-таблицы. Хэш-таблица содержит 19 слотов (от 0 до 18).

els, jan, jelle, maaike

Образует ли каждое символическое имя уникальное значение хэш-функции? Если нет, то как разрешить эту коллизию?

12. Метод хэширования, описанный в тексте главы, позволяет скомпоновать все элементы, имеющие один хэш-код, в связном списке. Альтернативный ме­тод — иметь только одну таблицу из п слотов, в которой в каждом слоте име­ется пространство для одного ключа и его значения (или для указателей на них). Если алгоритм хэширования порождает слот, который уже заполнен, производится вторая попытка с использованием того же алгоритма хэширо­вания. Если и на этот раз слот заполнен, алгоритм применяется снова и т. д. Так продолжается до тех пор, пока не будет найден пустой слот. Если доля слотов, которые уже заполнены, составляет R, сколько попыток в среднем по­надобится для того, чтобы ввести в таблицу новый символ?

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

14. Pentium 4 имеет сегментированную архитектуру. Сегменты независимы. Ас­семблер для этой машины может содержать директиву SEG N, которая помеща­ет последующий код и данные в сегмент N. Повлияет ли такая схема на счет­чик адресов команд?

15. Программы часто компонуются с многочисленными библиотеками DLL. А не будет ли более эффективным просто поместить все процедуры в один боль­шой DLL-файл, а затем скомпоновать его?

16. Можно ли отобразить DLL-файл на виртуальные адресные пространства двух процессов с разными виртуальными адресами? Если да, то какие про­блемы при этом возникают? Можно ли их разрешить? Если нет, то что можно сделать, чтобы устранить их?

17. Опишем один из способов компоновки (статическая компоновка). Перед ска­нированием библиотеки компоновщик составляет список необходимых про­цедур, то есть имен, которые в компонуемых модулях определены как внеш­ние (EXTERN). Затем компоновщик последовательно просматривает всю библиотеку, извлекая каждую процедуру, которая находится в списке нуж­ных имен. Будет ли работать такая схема? Если нет, то почему и как это мож­но исправить?

18. Может ли регистр использоваться в качестве фактического параметра в мак­ровызове? А константа? Если да, то почему? Если нет, то почему?

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

20. Подумайте, как можно поместить макроассемблер в бесконечный цикл.

21. Компоновщик считывает 5 модулей размером 200, 800, 600, 500 и 700 слов со­ответственно. Если они загружаются в этом порядке, то каковы константы пе­рераспределения памяти?

22. Напишите модуль таблицы символов, состоящий из двух процедур: enter(symbol, value) и lookup (symbol, value). Первая вводит новые символиче­ские имена в таблицу, а вторая ищет их в таблице. Используйте какой-либо вариант хэширования.

23. Напишите простой ассемблер для компьютера Mic-1, о котором мы гово­рили в главе 4. Помимо оперирования машинными командами, обеспечьте возможность приписывать константы символическим именам во время ас­семблирования, а также возможность ассемблировать константу в машин­ное слово.

24. Добавьте макросы к ассемблеру, который вы должны были написать, выпол­няя предыдущее задание.