Контроль целостности информации

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

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

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

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

Более сложная схема – это CRC (Cycle Redundancy Code) – циклический избыточный код. При вычислении CRC разрядности N выбирают число R требуемой разрядности и вычисляют остаток от деления на R блока данных, сдвинутое влево на N битов. Двоичное число, образованное блоком данных и остатком, делится на R и это можно использовать для проверки целостности блока.

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

Широко применяемый код Хэмминга находится в близком родстве с параллельной четностью. Его идея состоит в том, чтобы снабжать каждый блок несколькими битами четности, подсчитанными по различным совокупностям битов данных. Этот код гарантирует обнаружение одиночной ошибки (в отличие от CRC, который имеет всего лишь вероятность обнаружения ошибки). Этот код позволяет устранить одиночную ошибку в блоке. Для работы алгоритма необходимо выполнять соотношение

где – количество битов данных, – разрядность контрольного кода.

Если это уравнение превращается в равенство, то этот код называют оптимальным кодом Хэмминга.

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

Введение в криптографию

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

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

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

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостью алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произвести полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требованию сообщение. При использовании ключей достаточно большой разрядности такая атака оказывается чрезмерно дорогой, однако прогресс вычислительной техники постоянно сдвигает границу "достаточности" все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взломала сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы. Простым и эффективным способом борьбы с такой атакой является расширение пространства ключей. Увеличение ключа на один бит приводит к увеличению пространства вдвое – таким образом, линейный рост размера ключа обеспечивает экспоненциальный рост стоимости перебора. Некоторые алгоритмы шифрования не зависят от разрядности используемого ключа – в этом случае расширение достигается очевидным способом. Если же в алгоритме присутствует зависимость от разрядности, расширить пространство можно, всего лишь применив к сообщению несколько разных преобразований, в том числе и одним алгоритмом, но с разными ключами. Еще один способ существенно усложнить работу взломщику – это упаковка сообщения перед шифрованием и/или дополнение его случайными битами. Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа является лишь оценкой объема пространства ключей сверху, и во многих ситуациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному условию – например, RSA использует простые числа. Это резко сужает объем работы по перебору, поэтому для обеспечения сопоставимой криптостойкости разрядность ключа RSA должна быть намного больше, чем у алгоритмов, допускающих произвольные ключи. Низкая криптостойкость может быть обусловлена. не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чисел, мы можем значительно сократить объем пространства, которое реально должен будет перебрать взломщик наших сообщений. Еще хуже ситуация, когда в качестве ключа используются легко запоминаемые слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различных значений.

Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом.

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

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

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

В системах цифровой связи широкое применение получили блочные алгоритмы, выполняющие над блоками данных фиксированной длины последовательности – иногда довольно сложные – перестановок, подстановок и других операций, чаще всего двоичных сложений данных с ключом по какому-либо модулю. В операциях используются компоненты ключевого слова относительно небольшой разрядности. Например, широко применяемый блочный алгоритм DES шифрует 64-битные блоки данных 56-битным ключом. Для современной вычислительной техники полный перебор 56-битного пространства возможен, поэтому сейчас все большее распространение получают алгоритмы с большей разрядностью ключа – Blowfish, IDEAL и др.

Шифры с открытым ключом называются также двухключевыми. Если в алгоритмах со скрытым ключом для кодирования и декодирования сообщений используется один и тот же ключ, то здесь используются два ключа: публичный и приватный. Для прочтения сообщения, закодированного публичным ключом, необходим приватный, и наоборот. Помимо обычных соображений криптостойкости, к таким алгоритмам предъявляется дополнительное требование: невозможность восстановления приватного ключа по публичному иначе как полным перебором пространства ключей. Двухключевые схемы шифрования намного сложнее в разработке, чем схемы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, но такое, чтобы с применением приватного ключа его все-таки можно было обратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптических кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA. Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Министерства торговли США устанавливали ограничения разрядности ключа, который мог использоваться в экспортируемом за пределы США программном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым – 480. Использование ключей большой разрядности требует значительных вычислительных затрат, поэтому двухключевые схемы чаще всего применяются в сочетании с обычными: обладатель публичного ключа генерирует случайную последовательность битов, кодирует ее и отправляет обладателю приватного ключа. Затем эта последовательность используется в качестве секретного ключа для шифрования данных. При установлении двустороннего соединения стороны могут сначала обменяться своими публичными ключами, а затем использовать их для установления двух разных секретных ключей, используемых для шифрования данных, передаваемых в разных направлениях. Такая схема делает практичной частую смену секретных ключей: так, в протоколе SSH ключ генерируется на каждую сессию, в протоколе виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами. Еще более широкое применение двухключевые схемы нашли в области аутентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа может проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисления контрольных сумм, затрудняющие подбор сообщения с требуемой суммой.

Загрузка программ

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

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

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

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

Некоторые системы предоставляют и более крупные структурные единицы, чем процесс. Например, в системах семейства Unix существуют группы процессов, которые используются для реализации логического объединения процессов в задания (job). Ряд систем имеют также понятие сессии – совокупности всех заданий, которые пользователь запустил в рамках одного сеанса работы. Впрочем, соответствующие концепции часто плохо определены, а их смысл сильно меняется от одной ОС к другой.

В более старых системах и в старой литературе называют результат загрузки задачей, а процессами – отдельные нити управления. Однако в наиболее распространенных ныне ОС семейств Unix и Win32, принято задачу называть процессом, а процесс – нитью (tread).

Абсолютная загрузка

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

1. Система может предоставить каждому процессу свое адресное пространство. Это возможно только на процессорах, осуществляющих трансляцию виртуального адреса в физический.

2. Система может исполнять в каждый момент только один процесс. Так ведет себя СР/М, так же устроено большинство загрузочных мониторов для самодельных компьютеров. Похожим образом устроена система RT-11.

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

Начальное содержимое образа процесса формируется путем простого копирования модуля в память. В системе RT-11,например, такие файлы имеют расширение sav от saved – сохраненный.

Разделы памяти

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

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

Относительная загрузка

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

Сложность здесь в том, что если абсолютные адресные поля можно найти анализом кодов команд (деассемблированием), то значение в адресный регистр может загружаться задолго до собственно адресации, причем формирование значения регистра может происходить и по частям. На практике содействие программиста загрузчику состоит в том, что программист старается без необходимости не использовать в адресных полях и в качестве значений адресных регистров произвольные значения. Вместо этого, программист применяет ассемблерные символы, соответствующие адресам. Ассемблер при каждой ссылке на такой символ генерирует не только “заготовку” адреса в коде, но и запись в таблице перемещений (relocation table). Эта запись хранит место ссылки на такой символ в коде или данных.

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

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

Наиболее поучительна в этом отношении система RT-11, в которой существуют загружаемые модули обоих типов. Обычные программы имеют расширение sav, представляют собой абсолютные загружаемые модули и грузятся всегда с адреса 01000. Ниже этого магического адреса находятся векторы прерываний и стек программы. Сама операционная система вместе с драйверами размещается в верхних адресах памяти. Естественно, нельзя загрузить одновременно два sav-файла.

Однако, если обязательно нужно исполнять одновременно две программы, можно собрать вторую из них в виде относительного модуля: файла с расширением rel. Такая программа будет загружаться в верхние адреса памяти, каждый раз разные, в зависимости от конфигурации ядра системы, количества загруженных драйверов устройств и других геl-модулей.

Базовая адресация

Если мы полагаемся на содействие программиста, можно пойти дальше: мы объявляем один или несколько регистров процессора базовыми (несколько регистров могут использоваться для адресации различных сегментов программы, например, один – для кода, другой – для статических данных, третий – для стека) и договариваемся, что значения этих регистров программист принимает как данность и никогда сам не модифицирует, зато все адреса в программе он вычисляет на основе значений этих регистров. В этом случае для перемещения программы нам нужно только изменить значения базовых регистров, и программа даже не узнает, что загружена с другого адреса. Статически инициализованными указателями в этом случае пользоваться либо невозможно, либо необходимо всегда прибавлять к ним значения базовых регистров. Именно так происходит загрузка COM-файлов в системе MS DOS. Система выделяет свободную память, настраивает для программы базовые регистры DS и CS, которые называются сегментными, и передает управление на стартовый адрес. Ничего больше делать не надо.

Позиционно-независимый код

Третий способ – это относительная адресация, когда адрес получается сложением адресного поля команды и адреса самой этой команды – значения счетчика команд. Код, в котором используется только такая адресация, можно загружать с любого адреса без всякой перенастройки. Такой код называется позиционно-независшлым (position-independent). Позиционно-независимые программы очень удобны для загрузки, но, к сожалению, при их написании следует соблюдать довольно жесткие ограничения, накладываемые на используемые в программе методы адресации. Например, нельзя пользоваться статически инициализованными переменными указательного типа. Возникают сложности при сборке программы из нескольких модулей. К тому же, на многих процессорах, например, на Intel 8080/8085 или многих современных RISC-процессорах, описанная выше реализация позиционно-независимого кода вообще невозможна, так как эти процессоры не поддерживают соответствующий режим адресации для данных. На процессорах гарвардской архитектуры адресовать данные относительно счетчика команд вообще невозможно – команды находятся в другом адресном пространстве. Поэтому такой стиль программирования используют только в особых случаях.

Оверлеи (перекрытия)

Еще более интересный способ загрузки программы — это оверлейная загрузка (over-lay, лежащий сверху) или, как это называли в старой русскоязычной литературе, перекрытие. Смысл оверлея состоит в том, чтобы не загружать программу в память целиком, а разбить ее на несколько модулей и помещать их в память по мере необходимости. При этом на одни и те же адреса в различные моменты времени будут отображены разные модули. Отсюда и название. Потребность в таком способе загрузки появляется, если у нас виртуальное адресное пространство мало, например 1 Мбайт или даже всего 64 Кбайт, а программа относительно велика. На современных 32-разрядных системах виртуальное адресное пространство обычно измеряется гигабайтами, и большинству программ этого хватает. Основная проблема при оверлейной загрузке состоит в следующем: прежде чем ссылаться на оверлейный адрес, мы должны понять, какой, из оверлейных модулей в данный момент там находится. Для ссылок на функции это просто: вместо точки входа функции мы вызываем некую процедуру, называемую менеджером перекрытий (overlay manager). Эта процедура знает, какой модуль куда загружен, и при необходимости “подкачивает” то, что загружено не было. Перед каждой ссылкой на оверлейные данные мы должны выполнять аналогичную процедуру, что намного увеличивает и замедляет программу. Иногда такие действия возлагаются на программиста (Win 16, Mac OS до версии 10), иногда – на компилятор (handle pointer в Zortech C/C++ для MS DOS), но чаще всего с оверлейными данными вообще предпочитают не иметь дела. В таком случае оверлейным является только код.

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

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

Сборка программ

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

В большинстве современных языков программирования программа состоит из отдельных слабо связанных модулей. Как правило, каждому такому модулю соответствует отдельный файл исходного текста. Эти файлы независимо обрабатываются языковым процессором (компилятором), и для каждого из них генерируется отдельный файл, называемый объектным модулем. Затем запускается программа, называемая редактором связей, компоновщиком или линкером (linker — тот, кто связывает), которая формирует из заданных объектных модулей цельную программу. Общая структура процесса компоновки представлена на рисунке.

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

Кроме ссылок на собственные метки, объектный модуль имеет право ссылаться на символы, определенные в других модулях. Типичный пример такой ссылки – обращение к функции, которая определена в другом файле исходного текста.

Сборка в момент загрузки

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

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

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

Сборка при загрузке замедляет процесс загрузки программы но упрощает, с одной стороны, разделение кода, а с другой стороны – разработку программ. Действительно, из классического цикла внесения изменения в программу: редактирование текста – перекомпиляция – пересборка – перезагрузка (программы, не обязательно всей системы) выпадает целая фаза. В случае большой программы это может быть длительная фаза. В случае Novell Netware решающим оказывается первое преимущество, в случае систем реального времени одинаково важны оба.

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

Динамические библиотеки

В Windows и OS/2 используется именно такой способ загрузки. Исполняемый модуль в этих системах содержит ссылки на другие модули, называемые DLL (Dynamically Loadable Library, динамически загружаемая библиотека). Фактически, каждый модуль в этих системах обязан содержать хотя бы одну ссылку на DLL, потому что интерфейс к системным вызовам в этих ОС также peaлизован в виде DLL.

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

Главное достоинство DLL состоит в том, что модуль (как основной, так и библиотечный), по собственному желанию, может выбирать различные библиотеки, подгружая их уже после своей собственной загрузки. При этом нет даже строгого ограничения на совместимость этих библиотек по вызовам (две библиотеки совместимы по вызовам, если они имеют одинаковые точки входа с одинаковой семантикой): загрузчик предоставляет возможность просмотреть список глобальных символов, определенных в библиотеке, и получить указатель на каждый символ, обратившись к нему по имени.

Особенно удобна возможность вызывать любую функцию по имени при обращении к внешним модулям из интерпретируемых языков.

Концепция разделяемых DLL наиболее естественна в системах, где все задачи используют единое адресное пространство – но при этом ошибка в любой из программ может привести к порче данных или кода другой задачи. Стандартный же способ борьбы с этой проблемой — выделение каждому процессу своего адресного пространства – значительно усложняет разделение кода. Другая проблема, обусловленная широким использованием разделяемого кода, состоит в слежении за версией этого кода. Действительно, представим себе жизненную ситуацию: в системе одновременно загружены тридцать программ, использующие библиотеку LIBC.DLL. При этом десять из них разрабатывались и тестировались с версией 1.0 этой библиотеки, пять – с версией 1.5 и пятнадцать – с версией 1.5а. Понятно, что рассчитывать на устойчивую работу всех тридцати программ можно только при условии, что все три версии библиотеки полностью совместимы снизу вверх не только по набору вызовов и их параметров, но и по точной семантике каждого из этих вызовов. Последнее требование иногда формулируют как bug-for-bug compatibility (полная совместимость не только по спецификациям, но и по отклонениям от них).

Загрузка самой ОС

При загрузке самой ОС возникает специфическая проблема: в пустой машине, скорее всего, нет программы, которая могла бы это сделать.

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

При разработке программ для встраиваемых приложений часто используются внутрисхемные имитаторы ПЗУ, доступные целевой системе как ПЗУ, а системе разработчика – как ОЗУ или специальное внешнее устройство.

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